Mathematical Methods for Image Based Localization

På svenska Var är bilden tagen? Det är en fråga som vi ofta ställer oss och som denna avhandling innehåller matematiska metoder för att låta en dator besvara. Om vi lyckas svara på frågan kan metoderna för att hitta svaret användas till vitt skilda saker. Det går att använda för att låta robotar navigera med hjälp av kameror men också för att sortera privata bilder i digitala fotoalbum efter var de är tagna.

För att lösa lokaliseringsproblemet har flera delproblem studerats. I ett av delproblemen har en tredimensionell modell av Malmö byggts upp utifrån 95~000 bilder tagna utmed stadens gator. Med hjälp av modellen går det för en ny bild, tagen någonstans i Malmö att avgöra var fotografen befann sig. Det görs genom att titta på många små områden i den nya bilden. De områdena beskrivs sedan med en uppsättning tal så att liknande områden går att hitta i den tredimensionella modellen. Om tillräckligt mycket är känt om kameran som tagit bilden går det att räkna ut vilken vinkel det är mellan riktningarna till två punkter som avbildats i bilden, sett från kameran. Tack vare den tredimensionella modellen av staden är det sedan möjligt att räkna ut var i Malmö den vinkeln kan uppstå mellan punkterna. Med hjälp av det går det att få fram en lista på platser där bilden kan vara tagen.

Det som hittills har beskrivits kan fungera som ett första steg i en lokaliseringsprocess. För att ta reda på mera om kamerans position, så som riktning, eller för att få en högre precision i resultatet kan man utgå från resultatet av den första delen för att hitta positioner att undersöka noggrannare. Även de fortsatta algoritmerna för att söka efter position har utvecklats i avhandlingen. När antalet tänkbara platser begränsats efter det första steget är det möjligt att utföra mera resurskrävande beräkningar som en dator inte skulle klara av för en hel stad på rimlig tid. I arbetet har det utvecklats två typer av algoritmer för detta problem, dels en som är optimal, alltså att det är säkert att det inte finns en bättre lösning, dels metoder som går snabbare men som inte garanterat ger ett optimalt resultat.

Det kan låta konstigt att inte nöja sig med en metod som ger ett optimalt svar, men dessa algoritmer tar ofta för lång tid att använda, och då får vi hoppas på att kunna ta en genväg för att hitta en nästan lika bra lösning. Det visar sig också att det i de flesta fallen blir fullt tillfredsställande lösningar även när den snabba vägen används.

Det arbete som gjorts på de snabbare metoderna i avhandlingen handlar till stor del om beräkningar kopplade till hur kameror avbildar omgivningen. För olika matematiska modeller av en kamera, som är beroende av hur mycket som är känt om kamerans konstruktion och även vilken brännvidd som användes vid fototillfället, blir det olika geometriska problem att lösa. Vid användning av de snabba algoritmerna utnyttjas ett minimalt antal punkter i bilden, som har kopplats samman med punkter i den tredimensionella modellen, för att problemet ska kunna lösas. Sedan löses problemet för denna minimala uppsättning punkter. Lösningen testas hur väl den stämmer överens med de övriga punkterna som kopplats samman mellan bilden och modellen. Många tidigare olösta sådana problem, där ett minimalt antal punkter är kopplade mellan kameran och modellen, presenteras det lösningar på i avhandlingen. Lösningarna blir då en viktig kugge i ett fullständigt lokaliseringssystem.