Algebraic Advances in Multiview Geometry

QC2024-05-23

Abstract

 Datorseende är vetenskapen kring hur datorer kan förstå och klassificera bilder lika väl eller bättre än människor, på en bråkdel av tiden. Ett fundamentalt problem inom detta område är Struktur-från-Rörelse, vilket ämnar att skapa en 3D-modell av ett objekt utifrån 2D-fotografier. Tillämpningar inkluderar självkörande bilar, autonoma fordon och visuell media så som filmer och datorspel.  

Geometrin som uppstår i 3D-rekonstruktion kallas multivygeometri, och studiet av algebraiska strukturer som uppstår från multivygeometri kallas algebraiskt seende. Det senare är ämnet för denna avhandling. Vårt fokus ligger på optimeringsproblem, att hitta relevanta polynomekvationer och konstruktionen av nya algoritmer. Ett huvudmål med avhandlingen är att generalisera begrepp och idéer inom algebraiskt seende.

I Artikel A undersöker vi en klassisk fråga inom datorseende, nämligen kompatibiliteten hos fundamentala matriser. Vi bevisar att fyrfaldig kompatibilitet implicerar global kompatibilitet. Givet en sexfald av kompatibla fundamentala matriser, finns det fyra möjliga fall för geometrin hos deras epipoler. För varje fall ger vi nödvändiga och tillräckliga villkor för kompatibilitet i termer av explicita homogena polynom i de fundamentala matriserna och deras epipoler.

I Artikel B bygger vi vidare på teorin från Artikel A. Närmare bestämt uttrycker vi nödvändiga och tillräckliga villkor på ett ekvivalent sätt med intuitiva geometriska villkor. Som medföljd får vi enklare bevis.

I Artikel C undersöker vi problemet om hur man bäst identifierar och filtrerar bort avvikande data från en given datamängd. En datapunkt bör behållas om dess euklidiska avstånd till den matematiska modellen är tillräckligt litet. Detta avstånd är dyrt att beräkna. I praktiken skattas det effektivt av Sampsonfelet. Vi ger teoretiska gränser för när Sampsonfelet är en bra skattning av det euklidiska avståndet och visar, via numeriska experiment, nya scenarier där det kan tillämpas, såsom trevygeometri.

I Artikel D studerar vi projektionen av linjer i rummet på en given uppsättning kameraplan. Slutna höljet av denna projektionsavbildning är en linjemultivyvarietet. Vårt huvudteorem är att en linjemultivyvarietet skärs ut av villkoret att de bakprojicerade planen möts i en linje om och endast om alla centra är parvis distinkta och inga fyra centra ligger på en linje. Här är släta kvadratiska ytor och deras familjer av linjer viktiga verktyg. Vi studerar också släthet, multigrader och euklidiska avståndsgrader.

I Artikel E använder vi teorin om Cohen--Macaulay ideal för att under tillräckligt allmänna situationer bevisa att idealet beskrivet i Artikel D är det definierande idealet för linjemultivyvarieten. Vi beräknar Gröbnerbaser och diskuterar i vilken utsträckning våra resultat överförs till fallet med kameror vars centra ligger på en linje.

I Artikel F löser vi problemet om hur man utför 3D-rekon- struktion så att incidensrelationer mellan punkter och linjer bevaras. I denna riktning introducerar vi förankrade multivyvarieteter. Baserat på dessa beskriver vi nya rekonstruktionsalgoritmer. På simulerade data jämför vi de olika tillvägagångssätten med individuell rekonstruktion av punkter och linjer. Vårt tillvägagångssätt ger jämförbar noggrannhet och betydande förbättring av hastighet. Denna hastighetsförbättring stöds teoretiskt av våra beräkningar av euklidiska avståndsgrader. Vi utnyttjar observationen att dessa förankrade multivyvarieteter är linjärt isomorfa med multivyvarieteter som uppstår från projektionen av punkter från plan och linjer.

 I Artikel G utforskar vi den ovanstående observationen från Artikel F i större detalj. Vi börjar med att bestämma alla möjliga förankrade multivyvarieteter som uppstår från projektioner av punkter och linjer i 1, 2 och 3-dimensionella projektiva rum. Vi säger att två sådana varieteter är ED-ekvivalenta om det finns en linjär isomorfi mellan dem som bevarar ED-kritiska punkter. Detta ger upphov till fjorton ekvivalensklasser; en multivyvarietetskatalog. I fallet med punkter presenterar vi också en studie av alla associerade resektionsvarieteter. Slutligen föreslår vi förmodanden om euklidiska avståndsgrader för alla varieteter som förekommer i vår omfattande lista.

I Artikel H presenterar vi en algebraisk studie av projektionen av plankurvor och vridna kubiska kurvor i rummet på flera bilder givet hålkameror. Zariski-slutna höljet av bilden av projektionen av andragradskurvor kallas en kägelsnittsmultivyvarietet. Vi utökar tidigare arbete för punkt- och linjemultivyvarieteter genom att arbeta med bakprojicerade koner. För två vyer ger vi de definierande idealen för kägelsnittsmultivyvarieteter. För godtyckligt antal vyer anger vi när den enklaste möjliga mängdteoretiska beskrivningen uppnås baserat på geometrin hos kamerornas centra. Slutligen ger vi en förmodan om den euklidiska avståndsgraden för kägelsnittsmultivyvarieteter givet två kameror.

I Artikel I introducerar vi en generalisering av multivyvarieteter som slutna höljet av bilder som erhålls genom att projicera delrum av en given dimension på flera vyer, från fotografiska och geometriska perspektiv. Vi undersöker när den associerade projektionsavbildningen är generellt injektiv, vilket är ett avgörande krav för framgångsrik triangulering. Vi ger en komplett karaktärisering av denna egenskap genom att bestämma två formler för dimensionerna hos dessa varieteter. På liknande sätt beskriver vi för vilka arrangemang av centra som kalibrering av kameraparametrar är möjlig. Vi bestämmer exakt när multivyvarieter är naturligt isomorfa med sin associerade uppblåsning, i fallet med generiska centra.

I slutet av denna avhandling bifogas fyra ytterligare artiklar och ett utökat abstrakt. Eftersom dessa inte ingår i temat om algebraiskt seende, beskriver vi dem inte här. De inkluderas i avhandlingen som en del av den kompletta samlingen av kandidatens arbeten.

urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-346681