Inhaltsbasierte Bildersuche als notwendige Vorbereitung ... · informationssystemen verwendet. Google Earth und Microsoft Virtual Earth sind zwei popul are Beispiele, die zeigen,

Masterarbeit am Institut fur Informatik der Freien Universitat Berlin,

Arbeitsgruppe Intelligente Systeme und Robotik

Inhaltsbasierte Bildersuche als notwendige

Vorbereitung zur 3D Rekonstruktion

Ulrich WesthoffMatrikelnummer: 4341933

[email protected]

Betreuer:

Prof. Dr. Raul Rojas

Dipl.-Inf. Fabian Wiesel

Berlin, 6. November 2011

mailto:[email protected]

Zusammenfassung

Um dreidimensionale Rekonstruktionen aus großen unstrukturier-ten Bildbestanden zu berechnen, ist die vorherige Gruppierung ahnlicherBilder unumganglich. In dieser Arbeit wurde ein System entwickelt, mitdem es moglich ist, eine solche Gruppierung durchzufuhren. Die extra-hierten Bildgruppen enthalten dabei nur Aufnahmen derselben Szene.Ein großer Datenbestand wird dazu mittels Methoden aus dem Such-maschinenbereich indexiert. Durch die Indexierung konnen ahnlicheBilder effizient gesucht werden. Die gefundenen Beziehungen zwischeneinzelnen Bildpaaren werden durch geometrische Eigenschaften vali-diert und auf einem Graph abgebildet. Die Analyse der Zusammen-hangskomponenten des Graphen liefert Bildgruppen, die eine verlasslicheGrundlage fur eine mogliche dreidimensionale Rekonstruktion darstel-len. Um große Datenmengen auf gewohnlicher Desktop Hardware ana-lysieren zu konnen, wurden besonders die Skalierbarkeit und die effi-ziente Implementierung berucksichtigt. Das entwickelte System wurdemit einem umfangreichen Bestand historischer Aufnahmen uberpruft.

Eidesstattliche Erklarung

Ich versichere hiermit an Eides Statt, dass diese Arbeit von niemand ande-rem als meiner Person verfasst worden ist. Alle verwendeten Hilfsmittel wieBerichte, Bucher, Internetseiten oder ahnliches sind im Literaturverzeichnisangegeben, Zitate aus fremden Arbeiten sind als solche kenntlich gemacht.Die Arbeit wurde bisher in gleicher oder ahnlicher Form keiner anderenPrufungskommission vorgelegt und auch nicht veroffentlicht.

Berlin, 6. November 2011

Ulrich Westhoff

Inhaltsverzeichnis

1 Einleitung 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Aufbau der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Stand der Technik 3

3 Theoretische Grundlagen 53.1 Information Retrieval . . . . . . . . . . . . . . . . . . . . . . 5

3.1.1 Indexierung . . . . . . . . . . . . . . . . . . . . . . . . 63.1.2 tf-idf Gewichtung . . . . . . . . . . . . . . . . . . . . . 73.1.3 Visuelle Vokabeln . . . . . . . . . . . . . . . . . . . . . 8

3.2 Lokale Bildmerkmale . . . . . . . . . . . . . . . . . . . . . . . 93.2.1 DoG Detektor . . . . . . . . . . . . . . . . . . . . . . 103.2.2 Harris affin invarianter Detektor . . . . . . . . . . . . 133.2.3 SIFT Deskriptor . . . . . . . . . . . . . . . . . . . . . 15

3.3 Projektives Kameramodell . . . . . . . . . . . . . . . . . . . . 173.3.1 Externe Kalibrierung . . . . . . . . . . . . . . . . . . . 183.3.2 Interne Kalibrierung . . . . . . . . . . . . . . . . . . . 193.3.3 Projektionsmatrix . . . . . . . . . . . . . . . . . . . . 20

3.4 Epipolargeometrie . . . . . . . . . . . . . . . . . . . . . . . . 203.4.1 Fundamentalmatrix . . . . . . . . . . . . . . . . . . . 223.4.2 RANSAC . . . . . . . . . . . . . . . . . . . . . . . . . 23

4 Entwurf 254.1 Systemubersicht . . . . . . . . . . . . . . . . . . . . . . . . . 254.2 Retrievalsystem . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.2.1 Extraktion der Bildmerkmale . . . . . . . . . . . . . . 254.2.2 Generierung des visuellen Vokabulars . . . . . . . . . . 264.2.3 Indexierung . . . . . . . . . . . . . . . . . . . . . . . . 30

4.3 Szenenclustering . . . . . . . . . . . . . . . . . . . . . . . . . 324.3.1 Geometrische Validierung . . . . . . . . . . . . . . . . 324.3.2 Szenengraph . . . . . . . . . . . . . . . . . . . . . . . 344.3.3 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.4 Implementierungsdetails . . . . . . . . . . . . . . . . . . . . . 39

5 Diskussion 425.1 Zusammenfassung der wesentlichen Ergebnisse . . . . . . . . 425.2 Diskussion der Ergebnisse . . . . . . . . . . . . . . . . . . . . 425.3 Kritische Methodenreflexion . . . . . . . . . . . . . . . . . . . 435.4 Schlussfolgerung . . . . . . . . . . . . . . . . . . . . . . . . . 44

1 Einleitung

1 Einleitung

Die Entwicklung leistungsfahiger Algorithmen im Bereich des maschinellenSehens hat in den vergangenen Jahrzehnten große Fortschritte gemacht. Injungerer Vergangenheit wurden wesentliche Erfolge bei der dreidimensiona-len Rekonstruktion aus zweidimensionalen Aufnahmen erzielt. Ziel der drei-dimensionalen Rekonstruktion ist die moglichst genaue Reproduktion derUmwelt in Form eines dreidimensionalen digitalen Modells. Diese Modellebieten fur eine Vielzahl von Anwendungen einen großen Mehrwert. Thema-tisch kann das Problem unterschiedlichen wissenschaftlichen Disziplinen zu-geordnet werden. Die Geowissenschaften untersuchen Satellitenaufnahmen,um detaillierte dreidimensionale Karten zu erstellen. Die Medizin verwen-det die Aufnahmen verschiedener bildgebender Verfahren, um genaue drei-dimensionale Modelle zur Diagnose, Planung und Durchfuhrung operativerEingriffe zu erzeugen. In der Informatik wird die Technologie in der Robotik,der Kunstlichen Intelligenz sowie bei verschiedenen Internet basierten Geo-informationssystemen verwendet. Google Earth und Microsoft Virtual Earthsind zwei populare Beispiele, die zeigen, wie Gebaude und Landschaften vi-sualisiert werden konnen. Diese Systeme nutzten anfangs Satellitenbilderund Luftaufnahmen, werden jedoch momentan mit immer besseren dreidi-mensionalen Modellen angereichert. Die Modelle konnen dabei inzwischenaus Videodaten und Fotos automatisch generiert werden. Meist sind die Be-dingungen, unter denen die Bilder entstehen, bekannt und Aufnahmen diedieselbe Szene abbilden, konnen leicht identifiziert werden. Um jedoch auseinem unstrukturierten Bildbestand automatisiert dreidimensionale Model-le zu erzeugen, mussen Bildgruppen, welche dieselbe Szene abbilden, erstextrahiert werden. Im Rahmen dieser Arbeit wurde ein Verfahren zur Ex-traktion solcher Bildgruppen entworfen.

1.1 Motivation

Die Bundesrepublik Deutschland verfugt uber sehr umfangreiche Samm-lungen historischer Aufnahmen. Das Bundesarchiv verwaltet einen Bestandvon ca. elf Millionen Bildern. Weitere Bestande befinden sich in den Lan-desarchiven und in privater Hand. Ein kleiner Teil der Bilder wurde bereitsdigitalisiert. Die Digitalisierung des archivierten Bestandes wird angestrebt.Im Rahmen dieser Arbeit soll untersucht werden, ob diese Daten fur ei-ne dreidimensionale Rekonstruktion genutzt werden konnen. Die effizienteAnalyse des Datenbestandes, die lokalen Bildmerkmale sowie die zur dreidi-mensionalen Rekonstruktion genutzte Geometrie spielen dabei eine zentraleRolle.

1

1.2 Aufbau der Arbeit

1.2 Aufbau der Arbeit

Im folgenden Kapitel 2 werden die Methoden vorgestellt, die den heuti-gen Stand der Technik im Bereich der dreidimensionalen Rekonstruktionvon Gebauden und Platzen wiederspiegeln. Kapitel 3 fuhrt in Grundlagenein, die zum Verstandnis des entwickelten Verfahrens benotigt werden. Eswerden dazu in Abschnitt 3.1 erst die Methoden des Information Retrie-vals erlautert, die zur effizienten Suche in großen Datenbestanden genutztwerden. Im Falle von bildbasierten Datenbestanden spielen dabei die Grund-lagen zur Detektion und Beschreibung lokaler Bildmerkmale eine wichtigeRolle, diese werden daher in 3.2 thematisiert. In Abschnitt 3.3 wird dann inden Bildgebungsprozess eingefuhrt, um in 3.4 die Geometrie zwischen zweiAufnahmen vorzustellen. In Kapitel 4 wird die entwickelte Losung darge-stellt. Nachdem in Abschnitt 4.2 das Retrivalsystem erlautert wurde, wirdin 4.3 erklart, wie Gruppen ahnlicher Bilder extrahiert werden konnen. DieErgebnisse werden abschließend in Kapitel 5 diskutiert.

2

2 Stand der Technik

2 Stand der Technik

In diesem Kapitel werden Forschungsarbeiten vorgestellt, die im Zusam-menhang mit der vorliegenden Arbeit relevant sind und zum großen Teil dieSuche nach einer geeigneten Aufgabenstellung in diesem Gebiet motivierthaben.

Longuet-Higgins zeigte 1981 wie mithilfe von zwei Bildern und 8 korre-spondierenden Punkten die dreidimensionale Struktur einer Szene rekonstru-iert werden kann [Lon81]. Dieser Algorithmus wurde spater von Hartley wei-ter optimiert und findet heute vielfach Anwendung [Har95]. Die Korrespon-dierenden werden seit dem meist durch die 1999 von Lowe eingefuhrte Scaleinvariant Feature Transform (SIFT ) beschrieben [Low99]. SIFT ermoglichtes, bestimmte Punkte in einem Bild so zu beschreiben, dass diese in ei-nem anderen Bild trotz veranderter Aufnahmebedingungen wiedergefundenwerden konnen. Dieses Verfahren ist bis heute fur die Bildverarbeitung vongroßer Bedeutung. Die gefundenen paarweisen Losungen werden dann mit-tels Bundelblockausrichtung zu einer global konsistenten Losung optimiert.Diese Methoden bilden die Grundlage fur die dreidimensionalen Rekonstruk-tion [TMHF00].

Die Modellbildung aus fotografisch erfassten Bildern erfordert die paar-weise Korrespondenzanalyse zwischen den einzelnen Aufnahmen. Falls keineweiteren Informationen bekannt sind, mussen die paarweise Korresponden-zen zwischen allen Bildern berechnet werden, wodurch die Skalierbarkeitstark eingeschrankt ist. Um die explizite Korrespondenzanalyse zwischenallen Aufnahmen zu umgehen, setzten Sivic und Zisserman 2003 erstmalseine Methode aus dem Suchmaschinenbereich ein, um ahnliche Objekte undSzenen innerhalb eines Videos zu identifizieren. Sie berechneten dazu SIFTMerkmalsvektoren ausgewahlter Frames. Diese Vektoren bildeten sie mittelsVektorquantisierung auf einige wenige, moglichst aussagekraftige Vektorenab. Sie bestimmten die Haufigkeit, mit der die einzelnen Quantisierungenim Bild auftreten und speicherten diese in einem Vektor. Die Ahnlichkeitvon Bildern kann dann durch den Abstand der zugehorigen Vektoren be-stimmt werden. Da die Korrespondenzanalyse somit nicht mehr explizit furjedes Bildpaar durchgefuhrt werden muss, kann die Suche nach Bildern mitahnlichem Inhalt signifikant beschleunigt werden [SZ03]. Philbin et al. ver-besserten die Methode spater, indem sie die Treffer geometrisch verifizierten[PCI+07].

Basierend auf diesen Arbeiten entwickelte Agarwal et al. in [AFS+10]ein parallelisiertes System zur Rekonstruktion dreidimensionaler Szenen ausgroßen Bildbestanden. Diese System indexiert den Datenbestand und uberprufteinen Teil der Treffer mittels Epipolargeometrie. Die gefunden Gruppen wer-den erweitert, indem weitere Treffer der enthaltenen Bilder geometrisch ve-rifizieren werden. Durch Einsatz eines von Snavely et al. entwickelten Al-gorithmus entfernen sie anschließend redundante sowie fehlerhafte Bilder

3

2 Stand der Technik

[SSS08]. Mittels Bundelblockausrichtung werden anschließend aus den Grup-pen Punktwolken erzeugt. Dieses System nutzt eine ganze Reihe verschie-dener Techniken, die in den letzten Jahren entwickelt wurden und zeigteindrucksvoll die Modellbildung aus großen unstrukturierten Bildersamm-lungen.

Die so erzeugten Modelle bestehen jedoch nur aus sehr dunn besetztenPunktwolken. Multiview Stereo Algorithmen werden daher genutzt, um dieRekonstruktion zu optimieren.

Es wurden außerdem Systeme vorgestellt, die die Rekonstruktion inEchtzeit durchfuhren. Pollefeys nutzte 2007 [PNF+08] GPS und Tragheitsmessung,um die enormen Datenmengen zu verarbeiten. Die erste echtzeitfahige Losung,die keine weiteren externen Sensordaten benotigte, wurde von Klein undMurray [KM07] vorgestellt und ist in der Lage, dunn besetze Punktwol-ken in Echtzeit zu erzeugen. Stuhmer et al. sowie Newcombe und Davisonstellen erstmals Methoden vor, die in Echtzeit prazise Modelle mit geschlos-senen Oberflachen erzeugen [SGC10],[NLD11]. Diese Systeme nutzen einTrackingsystem, welches die Position der Kamera simultan zur Rekonstruk-tion bestimmt. Fur die Rekonstruktion aus unstrukturierten Bildersamm-lungen sind solche Systeme somit nicht geeignet und werden daher nichtweiter betrachtet.

4

3 Theoretische Grundlagen

3 Theoretische Grundlagen

In diesem Abschnitt werden Grundlagen eingefuhrt, die beim spateren Ent-wurf von Bedeutung sein werden. Die inhaltsbasierte Bildersuche spielt hier-bei eine zentrale Rolle. Sie ersetzt die ansonsten notwendige paarweise Kor-respondenzanalyse aller Bilder und wird zuerst erlautert. Nachdem in Ab-schnitt 3.1 eine Einfuhrung in die Grundlagen des dokumentenbasierten In-formation Retrievals erfolgt, werden diese um die bildbasierten Methodenerweitert. In 3.2 werden Varianten zur Detektion und Beschreibung lokalerBildmerkmale eingefuhrt. Die darauf folgenden Abschnitte bauen aufeinan-der auf und fuhren vom projektiven Kameramodell zur Epipolargeometriebis hin zum Konzept der Fundamentalmatrix.

3.1 Information Retrieval

Die weit fortgeschrittene Digitalisierung vieler Informationen fuhrt zu einerSituation, in der ohne eine Struktur, geeignete Filterung oder Sortierungentsprechende Datenbestande nicht nutzbar sind. Information Retrieval be-zeichnet Techniken zur Suche innerhalb unstrukturierter Datenbestande. Re-trievalsysteme beantworten Anfragen meist mit sortierten Listen von Tref-fern. Die Art der Daten sowie die Form, in der Anfragen gestellt werden,legen dabei die Auspragung des Information Retrievalsystems fest. Die ers-ten Information Retrieval Systeme dienten zur Suche innerhalb von doku-mentbasierten Datenbestanden und verarbeiteten textuelle Anfragen, diemit booleschen Operatoren kombiniert wurden. Diese Systeme pruften binar,auf welche Dokumente die Worter der Anfrage passten und kombiniertendie einzelnen Treffer durch Bildung der Vereinigungsmenge. Da die Verei-nigungsmenge bezuglich der Relevanz nicht weiter sortiert wurde, musstedie Anfrage so gestellt werden, dass die Vereinigungsmenge uberschaubarblieb. Anfang der 90er Jahre, ungefahr zum Zeitpunkt des Internet Booms,entstand das Ranked-Retrieval. Diese Methode liefert auf eine Anfrage ei-ne nach Relevanz sortierte Liste von Inhalten und ist heute Standard beiInternet- und Literatur- Suchmaschinen. Eine ausfuhrliche Darstellung derverschiedenen Methoden befindet sich unter anderem in [MRS08].

Ziel der inhaltsbasierten Bildersuche (Content Based Image Retrieval,CBIR) ist das Auffinden von Bildern, die eine große visuelle Ahnlichkeitbezuglich eines Anfragebildes aufweisen. Die ersten CBIR Systeme vergli-chen Bilder uber ihre globalen Eigenschaften wie Farben, Formen und Tex-tur. Moderne Ansatzen basieren auf dem Vergleich lokaler Bildmerkmalewie z.B. SIFT. Jedes Bild wird dabei durch eine Vielzahl lokaler Merkmals-vektoren reprasentiert. Die Ahnlichkeit zwischen zwei Bildern kann durchVergleich dieser Merkmale ermittelt werden. Die dazu notwendige Korre-spondenzanalyse ist sehr rechenintensiv und ist bei großen Datenbestandenunpraktikabel. Selbst wenn die Korrespondezanalyse in 10ms durchgefuhrt

5


werden kann, wurde eine einzelne Anfrage an eine Datenbank mit 1.000.000Bildern ca. 3 Stunden dauern. Moderne CBIR Systeme fuhren das Pro-blem daher auf die schnellen Methoden des dokumentenbasierten Retrievalszuruck. Eine Untersuchung uber die Entwicklung von CBIR Systemen be-findet sich in [DJLW08].

Nachfolgend wird das Modell des Vektorraum Information Retrieval an-hand von textuellen Dokumenten eingefuhrt und anschließend um die bild-basierten Methoden erweitert.

3.1.1 Indexierung

Sollen große Datenbestande durchsucht werden, ist es notwendig, den Inhaltjedes einzelnen Dokumentes zu berucksichtigen. Der explizite Abgleich derInhalte ist jedoch zum einen sehr aufwendig, zum anderen ist es aufgrund derDatenmenge nicht moglich, alle Inhalte im Arbeitsspeicher des Systems zuhalten. Gleichzeitig ist das Transferieren eines jeden Dokumentes vom Datei-system in den Arbeitsspeicher sehr ineffizient. Bei der Indexierung wird derInhalt der Dokumente erfasst und in einen vergleichsweise kleinen Index ein-getragen. Dieser Index kann im Arbeitsspeicher gehalten und effizient durch-sucht werden. Der Inhalt von Dokumenten wird dazu mittels Schlagworternzusammengefasst. Die Schlagworter sind dabei nicht frei wahlbar, sondernwerden aus einem fur den Datenbestand passenden Pool ausgewahlt. DerPool an Schlagwortern mithilfe dessen ein Dokument beschrieben werdenkann, wird kontrolliertes Vokabular genannt. Die Dokumente werden da-bei durch einen Parser in Worter zerlegt, anhand lexikalischer Analyse aufihren Wortstamm zuruckgefuhrt und mit der Schlagwortliste verglichen. Je-des Dokument kann so durch eine Menge von Schlagwortern reprasentiertwerden. Die Beschreibung eines Dokumentes durch eine unsortierte Mengevon Wortern wird als Bag-of-Words bezeichnet. Bei k Vokabeln kann je-des Dokument durch einen k-dimensionalen Vektor beschrieben werden. Imeinfachsten Fall stellen die Eintrage des Vektors nur die sogenannte Term-frequenz dar und beschreiben, wie oft eine Vokabel innerhalb des Dokumen-tes vorkommt (Tabelle 1). Der Index besteht dann bei k Vokabeln und nDokumenten aus einer n× k großen Tabelle. Da jedes Dokument nur einenkleinen Teil des Vokabulars enthalt, sind die meisten Komponenten des Vek-tors Null. Die Matrix ist also nur sehr dunn besetzt. Dieser Umstand ist beider Indexierung sehr wichtig, da der Speicherbedarf der n × k Matrix sostark reduziert werden kann. Um die Dokumente bezuglich einer Anfrage zuranken, wird die Anfrage selbst auf den Vektorraum abgebildet. Fur jedesDokument kann dann durch Berechnung des Abstandes zwischen Anfrage-und Dokumentenvektor ein Score ermittelt werden.

Die Verwendung der Termfrequenz ist nicht optimal, da die globalenEigenschaften des Datenbestandes nicht berucksichtigt werden. Im folgendenAbschnitt 3.1.2 wird daher eine geeignete Gewichtung eingefuhrt.

6


Tabelle 1: Term Count MatrixDokument Vokabel#1 Vokabel#2 Vokabel#3

1 52 83 972 40 87 03 36 0 414 30 14 2365 48 30 0

3.1.2 tf-idf Gewichtung

Der Score eines Dokumentes sollte die globalen Eigenschaften des Datenbe-standes sowie die lokalen Eigenschaften der Dokumente berucksichtigen. Diein Abschnitt 3.1.1 eingefuhrte Termfrequenz bezieht sich jedoch nur auf dielokalen Eigenschaften des Dokumentes. Die TF-IDF term frequency–inversedocument frequency Gewichtung der Termfrequenz lost dieses Problem undwird unter anderem von [SZ03], [NS06] und [PCI+07] eingesetzt. Der Doku-mentenvektor wird dabei so verandert, dass sowohl die Haufigkeit mit der einWort innerhalb eines Dokumentes vorkommt, als auch dessen Haufigkeit in-nerhalb des gesamten Datenbestandes Berucksichtigung findet. Dieses Maßzur Ermittlung des Scores hat sich beim Ranked-Retrieval als de-facto Stan-dard etabliert. Die Term Frequenz tft,d entspricht der Haufigkeit, mit derein Term (Wort) t in Dokument d vorkommt. Da die Relevanz eines Doku-mentes nicht proportional mit der Termfrequenz zunehmen sollte, also einDokument, in dem ein Term n mal vorkommt, nicht gleich n mal wichtigerist, wird der Einfluss der Termfrequenz logarithmisch gedampft.

wt,d =

{1 + log tft,d, if tft,d > 0

0, otherwise

Bei einer Anfrage, die einen sehr seltenen Term beinhaltet, sollten Doku-mente, die diesem Term entsprechen, eine sehr hohe Relevanz haben. SelteneTerme sollen daher hoher gewichtet werden. Die Dokumenten Frequenz dftist die Haufigkeit, mit der ein Term t im gesamten Datenbestand auftrittund stellt ein Maß fur den Informationsgehalt eines Terms dar. Mittels deridf (inverse document frequency) inversen Dokumenten Frequenz

idft = logN

dft

kann so der globale Informationsgehalt aller Terme berucksichtigt werden,wobei der Logarithmus wiederum dampfend wirkt. N entspricht der An-zahl aller Dokumente. Der finale tf − idf Score steigt also mit der Vorkom-menshaufigkeit innerhalb eines Dokumentes sowie mit dem globalen Infor-

7


mationsgehalt und kann mit

tfidft,d = (1 + log tft,d) ∗ logN

dft

berechnet werden.Jedes Dokument kann so auf einem Zeilenvektor in Rk abgebildet werden.

Die gesamte tf-idf gewichtete Indextabelle besteht dann aus der Menge allerZeilenvektoren und entspricht bei k Vokabeln und n Dokumenten einer n×kMatrix (Tabelle 2).

Die tf-idf Gewichtung weist also einem Term t im Dokument d ein Ge-wicht zu, welches :

� maximal ist, wenn t haufig in einer kleinen Anzahl an Dokumentenvorkommt.

� niedrig ist, wenn t selten im Dokument vorkommt oder t in vielenDokumenten enthalten ist.

� minimal ist, wenn t in fast jedem Dokument vorkommt.

Tabelle 2: TFIDF MatrixDokument Vokabel#1 Vokabel#2 Vokabel#3

1 0 0,292 0,662 0 0,294 03 0 0 0,574 0 0,214 0,745 0 0,248 0

3.1.3 Visuelle Vokabeln

Wie bereits erwahnt, beschreiben Sivic and Zisserman in [SZ03] einen gene-ralisierten Ansatz des Dokument Retrievals, der es ermoglicht, nicht textu-elle Informationen zu verarbeiten. Sie wenden diese Variante auf Videodatenan und demonstrieren die Moglichkeiten eines hocheffizienten bildbasiertenObjektretrievalsystems. Sie extrahieren dazu Bildbereiche, die bestimmteMerkmale aufweisen und beschreiben diese durch Merkmalsvektoren, soge-nannte Deskriptoren. Diese Deskriptoren nutzen sie analog zu den Worternbeim dokumentbasierten Retrieval. Da das zur Indexierung notwendige kon-trollierte Vokabular somit nicht wie beim dokumentenbasierten Retrievalaus Wortern besteht, sondern aus der abstrakten Beschreibungen bestimm-ter Bildbereiche, kann keine Liste von Schlagwortern verwendet werden. Si-vic and Zisserman clustern daher einen Teil der Merkmalsvektoren mittels

8

3.2 Lokale Bildmerkmale

k-means in k Prototypen und nutzen diese als kontrolliertes visuelles Voka-bular. Abbildung 1 zeigt exemplarisch die zugeordneten Daten zweier Pro-totypen. Bei der Indexierung ersetzen sie die Abbildung von Wortern aufden Wortstamm durch die Zuweisung der Deskriptoren zu dem Prototypenmit der geringsten Distanz. Dieser Vorgang wird als Vektorquantisierungbezeichnet. Die Indexierung erfolgt dann, analog zum dokumentbasiertenRetrieval, durch den Aufbau des Index und TFIDF Gewichtung. Zur Erzeu-gung des visuellen Vokabulars nutzen Nister und Stewenius in [NS06] einhierarchisches Clusterverfahren. Philbin et al. verwenden k-means Cluste-ring, welches sie durch eine approximierte Suche des Nachbarn beschleunigen[PCI+07]. Da sie die besseren Eigenschaften experimentell belegen, wurdediese Variante im Rahmen der vorliegenden Arbeit implementiert und wirdim Detail in Abschnitt 4.2.2 vorgestellt. Im folgenden wird nun beschrieben,wie relevante Bildbereiche detektiert und mittels Deskriptoren Blickwinkel-unabhangig notiert werden konnen.

Abbildung 1: Zugehorige Daten zweier k-means Prototypen


Die Verwendung lokaler Bildmerkmale zur Korrespondenzanalyse zwischenBildern oder zur Erkennung von Objekten hat sich als sehr erfolgreich erwie-sen. In den letzten Jahren sind daher eine Vielzahl von Detektoren zur Loka-lisierung sowie Deskriptoren zur Beschreibung dieser Bildbereiche entwickeltworden. Die Schwierigkeit bei der Detektion und Beschreibung lokaler Bild-merkmale ist es, Punkte zu finden, die sich trotz abweichender Aufnahme-bedingungen zuordnen lassen. Die Aufnahmen, zwischen denen eine Korre-spondenzanalyse durchgefuhrt wird, konnen sich dabei hinsichtlich des Blick-winkels, der Beleuchtung sowie des Aufnahmezeitpunktes unterscheiden. DieDetektion sowie die Beschreibung der Bildpunkte sollte daher entsprechen-de Invarianten aufweisen. Das bekannteste Verfahren wurde 1999 von DavidLowe vorgestellt [Low99], [Low04]. Die von ihm vorgeschlagenen Methodeder scale invariant Feature Transfor (SIFT) ist invariant gegenuber Skalie-rung, Translation, Rotation und mit Einschrankungen invariant gegenuberBeleuchtungsunterschieden sowie affinen und projektiven Abbildungen. Auf-grund dieser vorteilhaften Eigenschaften ist die Beschreibung von Bildberei-chen durch SIFT Deskriptoren ein haufig genutztes Verfahren und gut zumEinsatz bei der Korrespondenzanalyse geeignet. Mittlerweile existieren eine

9


Vielzahl weiterer Detektoren und Deskriptoren. Die unterschiedlichen Va-rianten werden unter anderem in [MS05] und [MTS+05] untersucht. Zwarhangt die Performance stets stark von der Anwendung und den damit ver-bunden Daten ab, die Notation der Bildmerkmale in Form SIFT basierterDeskriptoren liefert jedoch in den meisten Fallen die besten Ergebnisse.Trotzdem ist SIFT nur teilweise robust gegenuber Anderungen des Blick-winkels. Mikolajczyk und Schmid fuhren in [MS04] einen skalierungs- undaffine-invarianten Detektor ein, der dieses Problem zum Teil lost. In denfolgenden Abschnitten werden der von Lowe sowie der von Mikolajczyk undSchmid entwickelte Detektor und die Notation der Bildbereiche mittels SIFTDeskriptor beleuchtet.

3.2.1 DoG Detektor

Der von Lowe genutze Detektor extrahiert die SIFT Deskriptoren in einemmehrstufigen Prozess. Ein initialer Test sucht auf allen Ebenen einer Bild-pyramide nach Punkten, die invariant gegenuber Skalierung und Rotationsind. Fur diese Punkte wird die genaue Lage sowie die Ebene der Bildpy-ramide ermittelt. Abschließend werden Punkte ausgewahlt, die ein Stabi-litatskriterium erfullen. Die erste Stufe des Detektors ermittelt Stellen desBildes, welche trotz Anderung der Aufnahmeposition zuverlassig erkanntwerden konnen. Das Bild wird dazu auf verschiedenen Skalen analysiert.Lowe verwendet zur Erzeugung der Bildpyramide eine Gaussfunktion alsSkalierungskernel. Durch Faltung des Bildes I(x, y) mit der zweidimensio-nalen Gaussfunktion

G(x, y, σ) =1

2πσ2e−(x

2+y2)/2σ2(1)

entsteht der Skalenraum

L(x, y, σ) = G(x, y, σ) ∗ I(x, y). (2)

Die blickwinkelstabilen Punkte werden durch Faltung des Bildes mit derdifference-of-Gaussian (DoG) Funktion detektiert.

D(x, y, σ) = (G(x, y, kσ)−G(x, y, σ)) ∗ I(x, y)

= L(x, y, kσ)− L(x, y, σ).(3)

Lowe wahlt diese Funktion, da die Bildpyramide ohnehin zur spateren De-skriptorberechnung benotigt wird und D sich effizient durch einfache Sub-traktion ermitteln lasst (Abbildung 2). Der letzte Schritt besteht in derAnalyse der von 3 gelieferten Werte. Dazu wird untersucht, ob ein Punktgroßer oder kleiner ist als die acht Nachbarn der gleichen Skalierungsebe-ne, sowie der neun Nachbarn der daruber und darunterliegenden Skalie-rungsebene (Abb. 3). Ist das der Fall, handelt es sich um ein Extremum.

10


Abbildung 2: Links, mittels Gausskernel mehrfach geglattete Eingangsbilderjeder Oktave. Rechts, Ergebnis von Subtraktion der benachbarten Ebenen

Diese Prufung kann meist vorzeitig abgebrochen werden. Ein letzter wich-tiger Aspekt bei der Detektion der lokalen Extrema betrifft die Sampling-frequenz im Skalen- und Ortsraum. Die Samplingfrequenz im Skalenraum

Abbildung 3: Detektion der Extrema

bestimmt die Anzahl der Skalierungen innerhalb einer Oktave. Im Orts-bereich entspricht die Samplingfrequenz der Anzahl der Abtastungen proIntervall. Lowe ermittelt die optimalen Werte experimentell und bestimmtdrei Skalierungen pro Oktave als optimal. Im Ortsbereich wird das erste Bildjeder Oktave mit σ = 1, 6 geglattet. Um den mit der Glattung entstehen-den Verlust der hohen Frequenzen im Eingangsbild zu kompensieren, wirddas Eingangsbild noch initial um den Faktor 2 mittels Linearinterpolation

11


vergroßert.In der ersten SIFT Version von 1999 wird die Position der Keypunk-

te durch Ort und Skalierungsebene beschrieben. Um die Genauigkeit zuerhohen, wurde spater das Fitten einer dreidimensionalen quadratischenFunktion eingefuhrt, wodurch eine Lokalisierung im Subpixelbereich ermoglichtwird. Durch diese Optimierung konnte das Matching sowie die Stabilitatweiter verbessert werden. Das Extremum wird dabei durch die verschobeneVersion der ersten drei Terme der Taylerreihe von D(x, y, σ) approximiert.Das Ableiten und Nullsetzen der Funktion

D(x) = D +∂DT

∂x+

1

2x2∂

2D

∂b2 x (4)

an der Position des gefundenen Extremums x = (x, y, σ) ergibt

x =∂2D−1

∂x2

∂D

∂x(5)

Die partiellen ersten und zweiten Ableitungen werden durch die Differenz-bildung der Nachbarpunkte approximiert. Sollte eine Dimension des so be-rechneten Offsets x großer als 0,5 sein, existiert ein zum Extremum nahergelegener und somit besserer Punkt. In diesem Fall wird der Vorgang wie-derholt. Der so ermittelte Offset mit Subpixelgenauigkeit wird abschließendzum ursprunglich gefundenen Extremum addiert.

Bereiche, die einen niedrigen Kontrast aufweisen, sind generell schlechtgeeignet und sollten verworfen werden. Lowe evaluiert daher noch den Funk-tionswert von D(x). Indem er x durch x substituiert und in (4) einsetzt,erhalt er

x = D +1

2

∂DT

∂xx. (6)

Extrema, die bei normiertem Wertebereich von [0,1] nur einen Kontrastvon unter 0,03 erreichen, werden verworfen. Ein weiteres Problem bei derstabilen Detektion der Keypunkte betrifft Kanten. Da die DOG Funktiongerade an Kanten sehr sensibel ist, werden hier haufig Extrema erkannt. Furdie Stabilitat der Keypunkte sind diese Stellen allerdings schlecht geeignet,da in Richtung der Kante schon kleine Storungen ausreichen, um den Punktzu verschieben. Durch Berechnung der 2x2 Hessematrix

H =

[Dxx Dxy

Dxy Dyy

](7)

an entsprechender Position und Skala kann die Krummung in der jeweili-gen Richtung bestimmt werden. Die Ableitungen werden wiederum durchDifferenzenbildung der Nachbarpunkte gewonnen. Die Verhaltnisse der Ei-genwerte der Hessematrix sind proportional zur Krummung von D. Loweverwirft dann alle Punkte, deren Verhaltnis zwischen den Krummungen 10ubersteigt.

12


3.2.2 Harris affin invarianter Detektor

Detektoren, wie der von Lowe eingefuhrte DOG Detektor, ermitteln Punk-te, welche durch einen Deskriptor notiert werden und eine Zuordnung vonKorrespondenzen zwischen verschiedenen Aufnahmen ermoglichen. Im Falleperspektivischer Abbildungen ist die Zuordnung zwischen den verschiedenenAufnahmen jedoch erschwert. Meist wird versucht, die Korrespondenzana-lyse adaptiv an diese Bedingungen anzupassen. Der von Mikolajczyk undSchmid vorgestellte affin- und skalierungsinvariente Detektor lost das Pro-blem hingegen schon bei der Detektion dieser Punkte. Die durch dieses Ver-fahren detektierten Punkte werden, neben der Position, durch eine nichtuniforme Skalierung beschrieben. Indem die detektierten Bereiche vor derBeschreibung zu einem Kreis normiert werden, konnen die bei der perspek-tivischen Abbildung aus verschiedenen Blickwinkeln auftretenden Differen-zen zum Teil ruckgangig gemacht werden. Diese Methode wird in [MS04]ausfuhrlich beschrieben und nun vorgestellt.

Perspektivische Abbildungen konnen fur kleine, und somit meist annaherndplanare Bereiche durch affine Transformationen approximiert werden. Deraffininvariante Detektor erlaubt nicht-uniforme Skalierungen und kann da-her als Generalisierung des skalierungsinvarianten Detektors aufgefasst wer-den. Nicht-uniforme Skalierungen, wie sie bei affinen Abbildungen auftreten,haben in den verschiedenen Richtungen unterschiedliche Skalierungsfakto-ren. Da derartige Skalierungen einen Einfluss auf die Form der abgebildetenStruktur haben, versagen in solchen Fallen uniform skalierungsinvariente De-tektoren. Mikolajczyk und Schmid nutzen zur Detektion relevanter Punkteeinen Harris Detektor, den sie mit einer Methoden zur automatischen Ska-lierungsauswahl adaptiv an verschiedene Skalierungen anpassen und so imMultiskalenraum verwenden konnen. Die Autokorrelationsmatrix des HarrisDetekors wird dazu um eine Skalierungensteuerung erweitert und ist durch

µ(X, σI , σD) =

[µ11 µ12µ21 µ22

]= σ2Dg(σI) ∗

[L2x(X, σD) LxLy(X, σD)

LxLy(X, σD) L2y(X, σD)

](8)

definert. Die Matrix beschreibt die Verteilung der Gradienten im lokalenUmfeld. Die lokalen Ableitungen werden mittels Gausskernel der Große σD(differentiation scale) berechnet. Die Gradienten im lokalen Umfeld werdendann mit einem Gausskernel der Große σI geglattet (integration scale). Diezwei Eigenwerte dieser Matrix beschreiben die Signalanderungen im Um-feld des Punktes X. Aufgrund dieser Eigenschaft konnen Punkte bestimmtwerden, die eine signifikante Krummung in orthogonalen Richtungen besit-zen. Die detektierten Punkte liegen z.B. auf Ecken oder Verbindungsstellen.Die so erweiterte Autokorrelationsmatrix kann nun mit dem Harris-Detektorverwendet werden.

hm(X, σI , σD) = det(µ(X, σI , σD))− αtrace2(µ(X, σI , σD)) (9)

13


Mikolajczyk und Schmid fuhren danach ein Verfahren ein, mit dem sichdie optimale Skalierung automatisch bestimmen lasst. Die Skalierung sollso gewahlt werden, dass die Struktur, die den Punkt umgibt, moglichstgut erfasst wird. Diese Skalierung kann durch Maximierung einer Zielfunk-tion ermittelt werden. Um eine geeignete Zielfunktion zu wahlen, untersu-chen sie verschiedene Varianten und entscheiden sich fur LoG (Laplacian-of-Gaussians), da diese in ihren Auswertungen den hochsten Anteil korrekterSkalierungen liefern. Die Funktion

| LoG(X, σn) |= σ2n | Lxx(X, σn) + Lyy(X, σn) | (10)

erreicht ihr Maximum, wenn die Große des LoG Kernels die Große der Struk-tur erreicht (Abbildung 4). Der vorgestellte Detektor wird als Harris LaplaceDetektor bezeichnet und nutzt die Funktion 8, um relevante Punkte im Ska-lenraum zu detektieren. Aus diesen Punkten wird derjenige ausgewahlt, beidem die Funktion 10 ihr Maximum erreicht. Den eingefuhrten skalierungs-

Abbildung 4: Aufnahmen mit unterschiedlicher fokaler Lange und Antwortder LoG Funktion

invarianten Harris Laplace Detektor erweitern Mikolajczyk und Schmid umaffine Invarianz. Wie eingangs bereits erwahnt, enthalten affine Transforma-tionen nicht uniforme Skalierungen. Da diese nicht uniformen Skalierungenbisher nicht berucksichtigt werden, unterscheiden sich die vom Detektor er-fassten Bereiche. Damit trotz einer affinen Transformation die erfassten Be-reiche gleich sind, muss die Skalierung in orthogonaler Richtung unabhangigsein. Abbildung 5 verdeutlicht den Zusammenhang. Den Skalenraum erset-zen sie dazu durch einen affinen Skalenraum. Die Autokorrelationsmatrix µist darin durch

µ(X,ΣI ,ΣD) = det(ΣD)g(ΣI) ∗ ((5L)(X,ΣD)(5L)(X,ΣD)T ) (11)

14


Abbildung 5: Links:Uniforme Skalierung. Rechts:Nicht-uniforme Skalierung

definiert. Die Autoren zeigen, dass unter Annahme einer beliebigen affinenTransformation XR = AXL, die Bedingung

µL(XL,ΣI,L,ΣD,L) = ATµR(XR,ΣI,R,ΣD,R)A

= ATµ(AXL, AΣI,L, ATΣD,LA

T )A(12)

gegeben ist und die zugrunde liegende affine Transformation A allein durchdie beiden MatrizenML = µL(XL,ΣI , L,ΣD, L) undMR = µR(XR,ΣI , R,ΣD, R)gewonnen werden kann.

Abbildung 6: Extrahierte Regionen bei einer Skalierungsanderung von 1,8und Anderung des Betrachtungswinkels um 30°

3.2.3 SIFT Deskriptor

Es wurden zwei Verfahren zur Detektion relevanter Punkte vorgestellt. Diesesollen nun durch einen Merkmalsvektor beschrieben werden. Um Bilder ver-gleichen zu konnen, die unter verschiedenen Aufnahmebedingungen entstan-den sind, sollte der Merkmalsvektor den sich andernden Aufnahmebedingun-gen gegenuber invariant und gleichzeitig moglichst diskriminativ sein. Loweermittelt dazu, basierend auf den Richtungen der lokalen Bildgradienten,fur jeden Punkt eine oder mehrere Orientierungen. Da der Merkmalsvek-tor dann relativ zu dieser Orientierung sowie der vom Detektor geliefertenSkalierung notiert wird, ist er sehr robust gegenuber veranderten Aufnah-mebedingungen.

15


Zur Bestimmung der Orientierung werden Maxima in einem lokalenOrientierungshistogramm ermittelt. Dazu wird der Betrag des Gradientenm(x, y) und die Orientierung Θ(x, y) fur jeden Punkt L(x, y) mittels Pixel-differenzen

m(x, y) =√

((L(x+ 1, y)− L(x− 1, y))2 + (L(x, y + 1)− L(x, y − 1))2)

θ(x, y) = arctan((L(x, y + 1)− L(x, y − 1))/(L(x+ 1, y)− L(x− 1, y)))

(13)

berechnet. Das Orientierungshistogramm besteht aus 36 Bins und wird ausden Punkten im Umkreis gebildet. Jedes Sample θ(x, y) wird beim Hinzu-addieren mit dem Betrag m(x, y) sowie mit einer Gaussglocke gewichtet.Das Sigma der Gaussglocke betragt dabei das 1,5 fache der vom Detektorermittelten Skalierungsebene. Da bei ca. 15% aller Punkte mehrere Maximaim Histogramm vorkommen, werden in Fallen, bei denen Bins großer sindals 80% des Maximums, mehrere Deskriptoren fur die unterschiedlichen Ori-entierungen berechnet. Um die Genauigkeit der Orientierung zu verbessern,wird diese abschließend durch Fitten einer Parabel interpoliert. Da der De-

Abbildung 7: Bildgradienten und Deskriptor

skriptor jetzt relativ zu Skalierung und Orientierung notiert werden kann,ist er diesbezuglichen Anderungen gegenuber invariant. Im folgenden wirdeine Beschreibung des Punktes eingefuhrt, die in gewissem Maß invariant istgegenuber Helligkeitsanderungen sowie Anderungen des Blickwinkels. Loweuberpruft unterschiedliche Moglichkeiten der Notation, wobei die Beschrei-bung durch ein lokales Orientierungshistogramm die stabilsten Ergebnisseliefert. Der entwickelte Deskriptor besteht aus Orientierungshistogrammen,die relativ zur Hauptrichtung notiert werden und ist in vier Quadrantenunterteilt. Abbildung 7 zeigt links die im Umfeld ermittelten Gradienten.Die einzelnen Gradienten werden wie schon zuvor durch eine Gaussglockegewichtet, so dass der Einfluss entfernter Punkte reduziert wird. In der Fol-ge verursachen geringe Positionsanderungen des Keypunktes keine abrupten

16

3.3 Projektives Kameramodell

Anderungen des Deskriptors. Werte, die raumlich und wertmaßig in Grenz-bereichen liegen, konnen ebenfalls plotzliche Anderungen des Deskriptorsverursachen. Die einzelnen Gradienten werden daher bei der Histogramm-bildung trilinar interpoliert und fließen so in mehrere Bins und mehrereHistogramme ein. Lowe ermittelt experimentell, daß die Orientierungshisto-gramme der vier Quadraten am besten mit 8 Bins aufgelost werden. Derresultierende Merkmalsvektor enthalt somit 4x4x8 = 128 Elemente. DieserVektor wird abschließend invariant gegen Beleuchtungsanderungen gemacht.Eine Kontrastanderung entspricht der Multiplikation aller Bildpunkte miteiner Konstante. Die Normalisierung des Vektors kompensiert diesen Effekt.Eine Helligkeitsanderung verursacht die Addition einer Konstanten mit allenBildpunkten, da die Gradienten jedoch durch Differenzen ermittelt werden,hat diese ohnehin keinen Einfluss. Da bei der Aufnahme auch nichtlinea-re Effekte auftreten und Gradienten mit großem Betrag starker betroffensind, werden diese mittels Schwellwert gefiltert und der Vektor anschließenderneut normiert.

Die von den Detektoren extrahierten Punkte werden durch den SIFTDeskriptor beschrieben. Ahnliche Bildpunkte konnen somit durch Vergleichder Deskriptoren auf unterschiedlichen Aufnahmen wiedergefunden werden.Dieser Vorgang ist selten fehlerfrei. Die fehlerhaften Zuordnungen konnendurch Uberprufung geometrischer Eigenschaften gefiltert werden. Die da-zu genutzten Grundlagen der Epipolargeometrie werden im folgenden Ab-schnitt aufgezeigt.


Die Grundlage jeder Form von Bildverarbeitung ist die Bildentstehung. Beijeder Aufnahme, die eine Kamera macht, wird die dreidimensionale Welt aufder zweidimensionalen Bildebene der Kamera abgebildet. Der Abbildungs-prozess kann durch das Modell der projektiven Kamera beschrieben werden.

Punkte aus dem Weltkoordinatensystem werden dazu in das Kamerako-ordinatensystem transformiert und von dort mittels Zentralprojektion aufder zweidimensionalen Bildebene abgebildet und abschließend in das Bild-koordinatensystem verschoben. Von Bedeutung ist dabei die interne Kali-brierung, welche die Abbildungsgeometrie bei der Projektion innerhalb desKameramodells beschreibt sowie die externe Kalibrierung, die die Positionsowie Orientierung der Kamera im Raum definiert. Die Projektionsmatrixfasst alles in einer kompakten Form zusammen und beschreibt die Projektionvollstandig.

Homogene Darstellung und Notation vereinfachen die perspektivi-sche Projektion wesentlich und werden daher zuerst erlautert. Ein großerVorteil bei der Darstellung in homogenen Koordinaten ist die Durchfuhrungvon projektiven Abbildungen durch einfache Matrixmultiplikation. Ein Punkt

17


des euklidischen Raumes Xe ∈ Rn wird dazu um eine Dimension erweitertund so in den Raum Xh ∈ Rn+1 transformiert. Eine projektive Abbildung,die in R3 durch x′ = P3x3 ∗Xe + t3x1 erfolgt, reduziert sich in homogenenKoordinaten auf die Matrixmultiplikation x′ = P4x4 ∗Xh. Ein dreidimensio-naler Punkt X = (x, y, z)T wird in homogener Darstellung zu einem Vektorder Form X = (λx, λy, λz, λ)T und beschreibt eine Linie durch den Ursprungdes Koordinatensystems. Die Rucktransformation in kartesische Koordina-ten erfolgt durch Division mit der n+1 Komponente des erweiterten Vektors.

(λx, λy, λz, λ)T → (x

λ,y

λ,z

λ)T = (x′, y′, z′)T

3.3.1 Externe Kalibrierung

Die externe Kalibrierung beschreibt die außere Orientierung der Kamerarelativ zur Welt. Bevor ein Weltpunkt mittels Zentralprojektion auf derBildebene der Kamera abgebildet werden kann, muss er mittels Koordi-natentransformation vom Weltkoordinatensystems in das Kamerakoordina-tensystem transferiert werden. Die Position der Kamera wird durch Trans-

Abbildung 8: Beziehung zwischen Welt- und Bildkoordinatensystem

lation des Kamerakoordinatensystem C relativ zum WeltkoordinatensystemW beschrieben. Die Orientierung der Kamera stellt eine dreidimensionaleDrehung im Raum dar und kann durch eine Rotationsmatrix ausgedrucktwerden. Die Kenntnis von Position sowie Orientierung der Kamera zum Zeit-punkt der Aufnahme wird externe Kalibrierung genannt. Translation undRotation sind affine Abbildungen und konnen bei homogener Darstellung in

18


einer Matrix zusammengefasst werden.

Xc =

[R −Rt0 1

]Xw (14)

Der transformierte Punkt Xc kann nun mithilfe der Zentralprojektion aufdie zweidimensionale Bildebene der Kamera projiziert werden.

3.3.2 Interne Kalibrierung

Die interne Kalibrierung beschreibt die Geometrie innerhalb der Kamerazum Zeitpunkt der Aufnahme. Der Abbildung 9 kann entnommen werden,wie ein dreidimensionaler Punkt des Kamerakoordinatensystems mit den ho-mogenen Koordinaten X = (x, y, z, 1)T durch das optische Zentrum O aufdie Bildebene B der Lochkamera projiziert wird. Um den Punkt Xc im Ko-

Abbildung 9: Geometrie der Lochkamera

ordinatensystem der Bildebene zu erhalten, muss dieser noch um den Vektor(px, py, 1)T verschoben werden. Die Kalibrierungsmatrix K beschreibt dasModell der Kamera.

K =

fx s pxfy py

1

(15)

F ist die fokale Lange, s beschreibt eine eventuelle vorhandene Scherung undist bei realen Systemen meistens 0. Um das Modell auf eine echte Kameraanzuwenden, gelten folgende Beziehungen:

� fx = F in mm * Pixel pro mm in X Richtung

� fy = F in mm * Pixel pro mm in Y Richtung / sin(Scherungswinkel)

19

3.4 Epipolargeometrie

� s = F in mm * Pixel pro mm in X Richtung * -cot(Scherungswinkel)

� px, py = Bildzentrum in Pixel

Die Abbildung vom Kamerakoordinatensystem in das Koordinatensystemder Bildebene B erfolgt durch

xy1

=

fx px 0fy py 0

1 0

xyz1

(16)

Die Zentralprojektion und die externe Kalibrierung wurden bereits vorge-stellt, es werden nun beide Konzepte durch die Projektionsmatrix zusam-mengefasst.

3.3.3 Projektionsmatrix

Die Projektionsmatrix beschreibt wie mittels Zentralprojektion und Kennt-nis von interner und externer Kalibrierung Punkte von Weltkoordinaten aufBildkoordinaten abgebildet werden. Durch die Kombination von 14 und 16kann der gesamte Abbildungsprozess in einer Matrix zusammengefasst wer-den.

P =

fx px 0fy py 0

1 0

[R −Rt0 1

]=

p11 p12 p13 p14p21 p22 p23 p24p31 p32 p33 p34

(17)

Ist die Projektionsmatrix bekannt, kann die dreidimensionale Geometriedurch Triangulation gewonnen werden. Aus diesem Grund ist die Projekti-onsmatrix von großer Bedeutung. Die Projektionsmatrix lasst sich aus derFundamentalmatrix gewinnen. Da die Fundamentalmatrix und die Epipo-largeometrie außerdem bei der Korrespondenzanalyse eine wichtige Rollespielen, wird auf beides nachfolgend eingegangen.


In Abschnitt 3.3 wurde gezeigt, wie eine Szene auf die Bildebene einer Kame-ra projiziert wird. Dieser Abschnitt behandelt die geometrische Beziehungzwischen 2 projektiven Abbildungen. Als zentrale Frage soll dabei geklartwerden, wie die Epipolargeometrie bestimmt wird und wie diese bei derKorrespondenzanalyse genutzt werden kann.

Abbildung 10 zeigt wie ein Strahl r durch das optische Zentrum O derersten Kamera und den Punkt x in den dreidimensionalen Raum fallt. DieProjektion dieses Strahls auf die Bildebene der zweiten Kamera wird Epi-polarlinie genannt. Die optischen Zentren beider Kameras sind durch dieBasislinie b miteinander verbunden. Diese schneidet die Bildebenen an denEpipolen e und e′. Abbildung 11 zeigt, dass jede Ebene, die die Basislinie

20


Abbildung 10: Epipolargeometrie

beinhaltet, Epipolarlinien l und l′ erzeugt. Die Linien verlaufen durch diezugehorigen gemeinsamen Epipole e und e′. Jede dieser Flachen wird Epi-polarebene genannt. Diese Zusammenhange werden durch die Fundamental-

Abbildung 11: Basislinie und Epipolarebene

matrix F beschrieben, welche die gesamte Epipolargeometrie reprasentiertund die Bildpunkte der beiden Aufnahmen miteinander verbindet. Hartleyzeigt in [HZ04], dass die Bedingung (x′)TFx = 0 fur die Menge aller Punktebeider Bilder gilt. Diese Eigenschaft wird bei der Berechnung genutzt undermoglicht die Bestimmung der Fundamentalmatrix allein aus den Punkt-korrespondenzen zweier Aufnahmen. Durch Multiplikation der Fundamen-

21


talmatrix F mit einem Bildpunkt x entsteht die Epipolarlinie l′ auf derzweiten Bildebene. Der zu x korrespondierende Punkt x′ liegt auf der durchl = Fx definierten Epipolarlinie l. Ein Algorithmus zur Berechnung derFundamentalmatrix sowie eine Methode zur robusten Anwendung bei starkfehlerbehafteten Daten wird vorgestellt.

3.4.1 Fundamentalmatrix

Normalisierter 8 Punkt Algorithmus

Das Konzept der Fundamtalmatrix ist zur Gewinnung dreidimensionalerStrukturinformationen aus einem Bildpaar von großer Bedeutung. Ein Al-gorithmus zur Bestimmung der Fundamtelmatrix wurde 1981 erstmals vonLonguet-Higgins prasentiert [Lon81]. Hartley veroffentlichte danach unteranderem in [HZ04] eine normalisierte Version, welche robuster gegenuberfehlerbehafteten Daten ist und besser konvergiert. Diese vorteilhaften Ei-genschaften werden in [CB03] sowie [Har95] untersucht und bestatigt. DieNormalisierung der Daten bezieht sich auf eine Translation sowie Skalierungbeider Eingangsbilder. Alle Punkte x und x’ werden dabei so verschoben,dass sich der Schwerpunkt im Zentrum des Koordinatensystems befindet undder mittlere quadratische Abstand der Punkte zum Zentrum

√2 betragt.

Sind mindestens 8 korrespondierende Punkte bekannt, kann die Fundamen-talmatrix berechnet werden. Da diese durch x′TFx = 0 definiert ist, kannmit jedem Paar von korrespondierenden Punkten eine lineare Gleichung auf-gestellt werden. Fur ein Paar von Punkten x = (x, y, 1) und x’ = (x′, y′, 1)gilt:

xx′f11 +xy′f21 +xf31 +yx′f12 +yy′f22 +yf32 +x′f13 +y′f23 +f33 = 0 (18)

Die 8 unbekannten Parameter der Fundamentalmatrix konnen nun durchAufstellen eines Gleichungssystems ermittelt werden. Durch Darstellung desGleichungssystems in Matrixform ergibt sich

Af = 0 (19)

A enthalt in jeder Reihe eine Parametrisierung der Gleichungen in der Form

xx′, xy′, x, yx′, yy′, y, x′, y′, 1 (20)

Aus dem Vektor f kann die Matrix

F =

f1 f2 f3f4 f5 f6f7 f8 f9

(21)

gebildet werden. Da aufgrund von Messfehlern numerische Probleme bei derLosung entstehen, schlagen Tsai und Huang in [TH81] die Losung mittelsSingularwertzerlegung vor. Dieses Verfahren wird heute ublicherweise ange-wandt und in [HZ04] ausfuhrlich diskutiert.

22


3.4.2 RANSAC

Die im vorherigen Abschnitt vorgestellte Methode benotigt zur Ermittlungder Fundamentalmatrix 8 korrespondierende Punkte. In der Regel stehenjedoch deutlich mehr Korrespondenzen zur Verfugung als zur Berechnungbenotigt werden. Gleichzeitig ist im reellen Anwendungsfall nicht sicherge-stellt, dass die Korrespondenzen fehlerfrei erkannt werden. Da es sich bei denfehlerhaften Zuordnungen raumlich betrachtet um grobe Ausreißer handelt,ist eine Losung mittels Ausgleichsrechnung nicht moglich. Die Auswahl einerfehlerfreien Untermenge ist daher von entscheidender Bedeutung. Fischlerund Bolles stellen in [FB81] mit Random Sampling Consensus (RANSAC )einen Algorithmus vor, der das Modell mehrfach mittels zufalliger Auswahleiner Untermenge parametrisiert und dann das Modell wahlt, welches vonder großten Anzahl an Daten unterstutzt wird. Rodenhorst lost das Problemin [Rod04] durch einen genetischen Algorithmus. Beide Algorithmen sind ro-bust gegenuber groben Ausreißern. RANSAC wird jedoch bereits erfolgreichbei der Bestimmung der Fundamentalmatrix eingesetzt, der genetische Al-gorithmus wird daher nicht betrachtet.

Die ublichen Ausgleichsverfahren verwenden alle Messwerte gleichzeitigund ermitteln eine Losung, die bezogen auf alle Messwerte, einen moglichstkleinen Fehler produzieren. Grobe Ausreißer konnen dabei das Ergebnisstark negativ beeinflussen. RANSAC hingegen wahlt zufallig eine minimaleAnzahl an Daten aus, die zur Modellbildung notwendig sind. Das vorliegendeModell wird dann gegen alle ubrigen Daten getestet. Dabei wird gespeichert,welche Daten unterhalb eines Schwellwertes liegen (Inlier) und das Modellunterstutzen (Consensus set). Der Vorgang von zufalliger Auswahl und Testwird solange wiederholt, bis ein Abbruchkriterium erfullt ist. Das großteConsensus set enthalt dann eine Untermenge, die moglichst frei von gro-ben Ausreißern ist. Bei der Bestimmung der Epipolargeometrie entsprichtdas Modell der Fundamentalmatrix. Ob ein korrespondierendes Paar dasModell unterstutzt, kann durch Ermittlung des Abstandes zwischen proji-zierter Epipolarlinie und korrespondierendem Punkt festgestellt werden. Der

Algorithm 1 8-Point und RANSAC

Require: n ≥ 8while Abbruchkriterium do

1: Wahle zufallig 8 koorespondierende Punkte aus der Datenmenge2: Bestimme mittels 8-Point Algorithmus die Fundamentalmatrix3: Prufe den Abstand d zwischen Punkten und zugehorigen Epipolarli-nienif d ≤ Schwellwert thenKorrespondenz ⇒ Consensus set.

end ifend while

23


Algorithmus kann z.B. nach einer festen Anzahl an Iterationen oder nachErreichen einer Mindestmenge an Inliern abgebrochen werden. Es kann au-ßerdem eine Mindestanzahl an Iterationen bestimmt werden. Wenn pm dieWahrscheinlichkeit ist, mit der die maximale Anzahl an Inliern gefundenwerden soll, und und pi die Wahrscheinlichkeit ist, mit der Korresponden-zen Inlier sind, kann mit log(1−pm)

log(1−(pc)c) die mindestens notwendige Anzahl anIterationen bestimmt werden. Hierbei stellt c die Anzahl der fur das Modellnotwendigen Parameter dar.

24

4 Entwurf

4 Entwurf

4.1 Systemubersicht

Basierend auf dem Stand der Technik und den eingefuhrten Grundlagen wirdin diesem Kapitel der Entwurf dargestellt. Das entwickelte System wurde inzwei Module unterteilt (Abb. 4.1).

Das Retrievalsystem extrahiert die Bildmerkmale, erzeugt das visuelleVokabular und indexiert den gesamten Datenbestand. Anschließend vali-diert das Szenenclustering die vom Retrievalsystem gelieferten Trefferlisten,erzeugt daraus einen Graphen und berechnet Bildgruppen selben Inhalts.Abbildung 4.1 stellt die einzelnen Komponenten schematisch dar. Beide Mo-dule werden nun im Detail vorgestellt.

4.2 Retrievalsystem

4.2.1 Extraktion der Bildmerkmale

Die Bildmerkmale werden mit den von Vedaldi und Mikolajczyk veroffentlichtenBibliotheken extrahiert [Mik], [Ved]. Die Qualitat historischer Bilder ist imVergleich zu solchen, die mit modernen Kameras aufgenommen werden, alsschlecht zu bezeichnen. Bildrauschen, Fehler bei der Digitalisierung oder Al-terungsprozesse haben zur Folge, dass ein Teil der extrahierten Merkmale un-brauchbar ist. Auf Bildern, die zwar dieselbe Struktur zeigen, extrahiert derDetektor nicht dieselben Punkte oder die Merkmalsvektoren unterscheidensich stark. Des weiteren kann davon ausgegangen werden, dass die Zeitraumezwischen den Aufnahmen zum Teil relativ groß sind. Witterungseinflusseund bauliche Veranderungen stellen daher eine weitere Schwierigkeit bei derSuche von Korrespondenzen dar. Trotz der erschwerten Bedingungen kannmit den vorgestellten Detektoren und der Beschreibung mittels SIFT haufigeine große Anzahl gultiger Korrespondenzen ermittelt werden. Abbildung12 zeigt exemplarisch die durch den Harris affin invarianten Detektor gefun-denen Bereiche.

25

4.2 Retrievalsystem

Abbildung 12: Detektierte Bereiche des Harris affin invarianten Detektors

4.2.2 Generierung des visuellen Vokabulars

Fur die Qualitat des Retrievalsystems ist das kontrollierte Vokabular vongroßer Bedeutung. Aufgrund der Datenmenge stellt das Erzeugen des visu-ellen Vokabulars eine große Herausforderung an das Clusterverfahren dar.Die Datenmenge kann zwar durch zufallige Auswahl reduziert werden, je-doch entsprechen z. B. 5% von 100.000 Bildern mit jeweils ca. 500 Merk-malen immer noch 2,5 Millionen Deskriptoren. Da jede Iteration beim k-means Clustering eine algorithmische Komplexitat von O(NK) besitzt, istdie Große des Volkabulars beschrankt. Nister und Henrik Stewenius nutzendaher in [NS06] ein hierarchisches Clusterverfahren mit einer Komplexitatvon O(Nlog(K)) und zeigen, dass die Performance sich mit dem von ihnengenerierten Vokabular deutlich verbessert. N entspricht der Anzahl der De-skriptoren, K ist die Menge der visuellen Vokabeln. Da die Laufzeit beimk-means Clustering maßgeblich durch die Suche nach den nachsten Nach-barn beeinflusst wird, ersetzten Philbin et al. in [PCI+07] spater die naiveSuche durch eine schnelle approximierte Variante und reduzieren die algo-rithmische Komplexitat einer Iteration so auf O(Nlog(K)). Sie zeigen perexperimentellem Vergleich aller drei Verfahren, dass das mittels approxi-miertem k-means generierte Vokabular beim Retrieval die besten Ergebnis-se liefert. Sie testen diese Variante erfolgreich mit einer Millionen Bildern.Aufgrund der vorteilhaften Eigenschaften wurde diese Methode implemen-tiert. Die Details des Verfahrens sowie die Ergebnisse der durchgefuhrtenParameter-Evaluierung werden nun vorgestellt.

26

4.2 Retrievalsystem

k-means K-means unterteilt eine Datenmenge X = (x1,x2, ...,xn) ink Cluster mit den Untermengen S = (s1, s2, ..., sk). Hierbei stellt sk die zuCluster k zugeordnete Untermenge der Daten dar. Diese Untermengen wer-den gebildet, indem jedem Datenpunkt x das Clusterzentrum mk (Schwer-punkt) mit dem geringsten Abstand zugewiesen wird. Diese Einteilung wirdauch Voronoi Partitionierung genannt. Der bekannteste Algorithmus zur Be-rechnung wurde 1982 von Lyod veroffentlicht.

Algorithm 2 approximiertes K-means

Require: n ≥ kInitialisierung: Wahle zufallig k Punkte als Clusterzentren Mwhile Si! = Si−1 do

1: Teile X in k Untermengen sk, so dass sk = {x | argmin ‖ x−mk ‖=k} (Voronoi Partitionierung)2: Berechne die neuen Clusterzentren mk fur jede Untermenge sk mit

mk =

∑x∈sk

x

|sk|end while

Der Algorithmus optimiert die Funktion

S =k∑k=1

∑x∈Sk

‖ x−mk ‖2 . (22)

Dabei ist nicht garantiert, dass er in einem globalen Minimum terminiert.Des weiteren hangt das Ergebnis von der Initialisierung der Clusterzentrenab. Der Algorithmus wird daher meist mehrfach mit unterschiedlichen Initia-lisierungen gestartet, wobei die beste Partitionierung gewahlt. Eine optimaleLosung ist gefunden, wenn das globale Minimum der Funktion 22 erreichtist.

Approximiertes k-means Wie einleitend bereits erwahnt, wird dieLaufzeit maßgeblich durch die Suche der nachsten Nachbarn bestimmt. Mit-tels linearer Suche kann bei N Daten mit D Dimensionen der nachste Nach-bar mit einer Laufzeit von O(ND) ermittelt werden. K-d Baume benotigenzur Suche des nachsten Nachbarn bei niedrig dimensionalen Daten durch-schnittlich eine Laufzeit von O(logN), verlieren aber ihre Effizienz mit stei-gender Anzahl der Dimensionen. Bis heute sind keine schnelleren exaktenMethoden bekannt. Es gibt jedoch Methoden, die mit relativ hoher Genau-igkeit den richtigen nachsten Nachbarn finden und wesentlich schneller sindals die lineare Suche. Muja und Lowe stellen in [ML09] mit FLANN einSoftwarepaket vor, dass entsprechende Algorithmen und Datenstrukturenbeinhaltet. Diese Bibliothek enthalt unter anderem die 2008 von Silpa-Ananund Hartley eingefuhrte approximierte Suche durch die Kombination meh-rerer randomisierter k-dimensionaler Baume [SAH08]. Einfache K-d Baume

27

4.2 Retrievalsystem

teilen an jedem Knoten die zugehorigen Daten entlang der Dimension, inwelcher die Daten die hochste Varianz aufweisen. Bei jeder Suche werdendann alle potentiell in Frage kommenden Blatter traversiert. Bei der ap-proximierten Suche wird lediglich eine feste Anzahl an Blattern untersuchtund somit ein Fehler akzeptiert. Die Laufzeit kann dadurch jedoch erheblichverkurzt werden. Ein randomisierter k-d Baum wahlt die Dimension, aufwelcher die Daten geteilt werden, zufallig aus den ersten D Dimensionen,welche die großten Varianzen aufweisen. Durch paralleles Abfragen mehre-rer solcher randomisierter Baume und Auswahl des besten Datums, kannder Fehler, der durch die approximierte Suche entsteht, zum Teil kompen-siert werden. Muja und Lowe stellen außerdem fest, dass es ausreicht, diefunf Dimensionen mit den großten Varianzen fur die zufallige Auswahl zuberucksichtigen. Die Parameter, die die Laufzeit und Qualitat der Suchebeeinflussen, sind also:

� Anzahl der parallelen k-d Baume

� Anzahl der zu traversierenden Blatter

Um K-means zu beschleunigen, werden bei jeder Iteration mehrere rando-misierte k-d Baume uber die Clusterzentren erzeugt. Jeder Baum enthaltdie k Clusterzentren und wird fur jedes Datum einmal abgefragt. Die Wahlgeeigneter Parameter hangt von den Daten selbst sowie der Anforderung andie Suche ab. Die Ergebnisse der experimentellen Auswertung werden nunbeschrieben.

0

10

20

30

40

50

60

70

80

90

100

10 20 30 40 50 60 70 80 90 100 0

10

20

30

40

50

60

70

80

90

100

Pre

cisi

on

Speedup

c

Precision

Speedup

1 Baum4 Bäume8 Bäume

16 Bäume24 Bäume

Abbildung 13: Entwicklung der Prazision in Abhangigkeit der zu traversie-renden Knoten und Geschwindigkeitsvorteil gegenuber linearer Suche (3000Datenpunkte)

28

4.2 Retrievalsystem

Parameterevaluierung Da bereits aus den Veroffentlichungen vonMuja und Lowe hervorgeht, dass der Zuordnungsfehler von der Parametri-sierung der k-d Baume sowie von den Daten selbst abhangt, wurden zunachstverschiedene Konfigurationen der k-d Baume anhand von SIFT Merkmals-vektoren getestet. Laufzeit und Ergebnis der approximierten Suche wur-den dazu jeweils mit der exakten linearen Suche verglichen. Die Anzahl der

0

10

20

30

40

50

60

70

80

90

100

500 1000 1500 2000 2500 3000 0

10

20

30

40

50

60

70

80

90

100

Pre

cisi

on

Speedup

n

1 Baum, 1 Blatt1 Baum, 100 Blätter

8 Bäume, 100 Blätter

Abbildung 14: Entwicklung der Prazision in Abhangigkeit der zugrunde lie-genden Datenmenge und Geschwindigkeitsvorteil gegenuber der linearer Su-che

Baume beeinflusst die Laufzeit bei der Suche nur marginal (Abbildung 13).Speicherverbrauch, sowie die Zeit zum Aufbau der Baume sind jedoch lineargekoppelt. Im weiteren Verlauf wurden daher 8 parallele Baume verwendet.Die Anzahl der zu traversierenden Blatter hat maßgeblichen Einfluss aufdie Prazision der approximierten Suche, beeinflusst aber gleichzeitig starkdie Laufzeit. Es werden daher fur die Suche 100 Blatter traversiert. Die-se Konfiguration fuhrt bei 85% der Abfragen zu einem korrekten Ergebnis,gleichzeitig wachst der Geschwindigkeitsvorteil gegenuber der naiven Sucheannahernd linear mit der Anzahl der Datenpunkte (Abbildung 14).

Wie Muja und Lowe bereits in [ML09] zeigen, nimmt der Zuordnungs-fehler mit zunehmender Korrelation der Daten ab. Dieser Effekt spiegeltsich beim Clustering wieder. Da die Korrelation zwischen Prototypen undDaten mit jeder Iteration zunimmt, verbessert sich die Prazision der Sucheschrittweise (Abbildung 15). Letztendlich erreicht die Prazision der Sucheso beim Clustern von SIFT Deskriptoren den ebenfalls von Philbin et al.ermittelten Fehler von 1%.

29

4.2 Retrievalsystem

86

88

90

92

94

96

98

100

0 20 40 60 80 100

90

100

k-d t

ree p

reci

sion

J(C

) =

sum

of

the s

quare

d e

rrors

iteration

PrecisionJ(C)

Abbildung 15: Entwicklung der Prazision beim approximierten K-meansClustering

4.2.3 Indexierung

Es wurde gezeigt, wie die SIFT Merkmalsvektoren extrahiert werden. Durchdas im vorherigen Abschnitt vorgestellte Verfahren konnen daraus großeVokabulare zur Vektorquantisierung berechnet werden. Auf Basis der in 3.1eingefuhrten Grundlagen des Information Retrieval wurde ein System imple-mentiert, mit dem große Bildbestande indexiert werden konnen. Der Indexwird dabei in einem mehrstufigen Prozess generiert. Die SIFT Merkmals-vektoren aller Bilder werden dazu extrahiert und binar auf dem Dateisys-tem gespeichert. Aus den extrahierten SIFT Merkmalsvektoren wird zufalligund gleich verteilt eine Untermenge ausgewahlt. Die Große der Untermengewird dabei so gewahlt, dass jedem Prototypen beim Clustering im Mittel100 Datenpunkte zur Verfugung stehen. Diese Merkmalsvektoren werdenmittels approximiertem K-means in k Prototypen partitioniert. Die Merk-malsvektoren aller Bilder werden dann durch Vektorquantisierung auf diek Prototypen abgebildet und der tf − idf Index erstellt. Um den Prozessder Quantisierung zu beschleunigen, wurden auch hier 8 parallelisierte k-dBaume uber das Vokabular erzeugt und 100 Blatter gepruft. Das Clusteringwurde jeweils mehrfach durchgefuhrt und das Vokabular gewahlt, welchesbeim Retrieval die besten Ergebnisse erzielt. Als Distanzmaß wurden derKosinus zwischen den Vektoren gewahlt. Um die Funktionalitat des imple-mentierten Systems zu prufen, wurden zwei Datensatzen mit bekanntemGoldstandard indexiert [PZ] [SN] . Bei der qualitativen Bewertung des Sys-tems, muss berucksichtigt werden, wie die relevanten Bilder in der Trefferlis-te verteilt sind. Ublicherweise erfolgt die Bewertung von Retrievalsystemenuber die mittlere durchschnittliche Prazision (Mean Average Precision kurz:

30

4.2 Retrievalsystem

mAP). Die durchschnittliche Prazision ist dabei die Fahigkeit, relevante Bil-der weit vorne zu ranken. Im Optimum belegen alle relevanten Bilder dievordersten Platze. Fur das Beispiel ergibt sich bei acht relevanten Bildern

Position 1 2 3 4 5 6 7 8 9 10

Bild 12 2 35 21 6 9 14 8 25 1

Relevant X X X X X

eine durchschnittliche Prazision von:

AP = ((1/1) + (2/3) + (3/4) + (4/6) + (5/7))/8

= (1 + 0, 67 + 0, 75 + 0, 67 + 0, 71)/8 = 0.47(23)

Die mittlere Durchschnittsprazision entspricht dem Mittelwert der Prazisionbei mehreren Anfragen. Beide Datensatzen wurden mit den Bildmerkmalenbeider Detektoren sowie deren Kombination indexiert. Tabelle 3 zeigt diedurchschnittliche Prazision des Retrievalsystems bei Verwendung der ver-schiedenen Detektoren. Das Clustering wurde jeweils mehrfach ausgefuhrt.Die experimentelle Auswertung zeigt, dass der Harris affine-invariante De-tektor in allen Fallen die besten Ergebnisse liefert. Dieser wird daher imweiteren Verlauf verwendet. Der Abstand zwischen den Zeilenvektoren des

Datensatz Detektor 10K 20k 50k

OX Dog 0,29 0,31 0,32OX HarAff 0,30 0,32 0,36OX Dog + HarAff 0,28 0,26 0,23

UK Dog 0,58 0,59 0,62UK HarAff 0,63 0,64 0,66UK Dog + HarAff 0,61 0,59 0,56

Tabelle 3: Vergleich der Detektoren

tfidf Index wird durch die Kosinus-Metrik ermittelt. Tabelle 4 stellt die Er-gebnisse des experimentellen Vergleichs verschiedener Metriken dar. Tabelle

Datensatz L1 L2 Kosinus

OX 0,29 0,1 0,36UK 0,57 0,29 0,66

Tabelle 4: Vergleich der Metriken, 50k Vokabular

5 zeigt außerdem die Entwicklung der durchschnittlichen Prazision im Zu-sammenhang mit der Große des Vokabulars.

31

4.3 Szenenclustering

Datensatz Deskriptoren Vokabeln mAP

OX 100k 1000 0,27OX 1M 10000 0,30OX 2M 20000 0,32OX 5M 50000 0,36OX 16.7M 1M 0,45

UK 100k 1000 0,60UK 1M 10000 0,63UK 2M 20000 0,64UK 5M 50000 0,66UK 9,9M 1M 0,75

Tabelle 5: mAP bei unterschiedlicher Vokabulargroße


Mit dem implementierten Retrievalsystem ist es moglich, große Bildbestandezu durchsuchen. Fur die dreidimensionale Rekonstruktion sollen nun Bild-gruppen extrahiert werden, welche dieselbe Szene abbilden. Fur jedes Bilddes Datenbestandes wird dazu vom Retrievalsystem eine Trefferliste gene-riert. Diese Trefferlisten werden validiert und aus den validierten Treffernwird ein Graph erzeugt. Dieser Graph wird abschließend auf Zusammen-hangskomponenten untersucht. Auf das Vorgehen wird nun eingegangen.

4.3.1 Geometrische Validierung

Die vom Retrievalsystem gelieferten Trefferlisten enthalten eine Vielzahl anBildern, die fur eine dreidimensionale Rekonstruktion nicht in Frage kom-men. Durch Korespondenzanalyse der Merkmalsvektoren, Bestimmung derEpipolargeometrie und anschließende Filterung der Trefferlisten konnen die-se Bilder effektiv entfernt werden. Die drei Schritte werden nachfolgend dar-gestellt.

Korrespondenzanalyse Zur Bestimmung der Epipolargeometrie mussenKorrespondenzen zwischen den Deskriptoren der Bilder gefunden werden.Da die Menge der Bilder sowie die Anzahl der extrahierten Deskriptorensehr groß ist, darf die Korrespondenzanalyse nur wenig Zeit in Anspruchnehmen. Aufgrund der Tatsache, dass fur jeden Deskriptor des ersten Bildesder Deskriptor des zweiten Bildes mit dem kleinsten euklidischen Abstandgesucht werden muss, sind bei N Deskriptorn pro Bild und einer symme-trischen Distanzfunktion N2

2 Abstande zu berechnen. Die Suche kann durchEinsatz der bereits mehrfach genutzten randomisierten kd-Baume verbessertwerden. Die Menge der zu traversierenden Blatter wurde aufgrund der zeit-kritischen Anwendung auf 50 begrenzt. Die approximierte Suche ist dadurch

32


jedoch im Vergleich zur exakten Suche nur zu 70 % korrekt. Ein Teil derKorrespondenzen, die auch bei der exakten Suche falsch sind, werden durchDeskriptoren verursacht, bei denen mehrere Kandidaten einen ahnlichen Ab-stand haben. Lowe zeigt, dass der Zuordnungsfehler reduziert werden kann,indem Treffer verworfen werden, bei denen das Verhaltnis der Abstande vomnachsten Nachbarn zum zweit nachsten Nachbarn großer ist als 0,8. 90%der fehlerhaften Zuordnungen werden so gefiltert, wahrend lediglich 5% derkorrekten Korrespondenzen verworfen werden. Das Matching mit den so un-terstutzten k-d Baumen liefert in 94% der Falle identische Ergebnisse wiedie exakte Suche. Abbildung 16 zeigt die gefundenen Zuordnungen. In Be-zug auf den Abstand der Deskriptoren sind diese Zuordnungen korrekt. Esist jedoch offensichtlich, daß es sich bei einem großen Teil raumlich gese-hen um Fehler handelt, im folgenden Abschnitt werden diese Fehler durchBestimmung der Epipolargeometrie gefiltert.

Abbildung 16: Zuordnung der SIFT Deskriptoren

Bestimmung der Epipolargeometrie Die erkannten Korresponden-zen konnen nun genutzt werden, um die Epipolargeometrie zwischen denAufnahmen zu ermitteln. Zur Bestimmung der Fundamentalmatrix wurdeder in 3.4.1 vorgestellte normalisierte 8 Punkt Algorithmus in Kombinationmit RANSAC genutzt. Abbildung 17 zeigt die gefilterten Korrespondenzen.Es ist ersichtlich, dass lediglich korrekte Zuordnungen die Filterstufe passie-ren.

Filterung Da Korrespondenzanalyse und Bestimmung der Epipolar-geometrie trotz effizienter Implementierungen verhaltnismaßig aufwendigsind, werden nur die besten 50 Treffer validiert. Paarungen, die wenigerals 100 korrekte Zuordnungen enthalten, werden verworfen. Im folgendenAbschnitt wird aus den so validierten Paarungen ein Graph erzeugt undzusammenhangende Bildgruppen extrahiert.

33


Abbildung 17: Zuordnung nach Filterung durch Epipolargeometrie

4.3.2 Szenengraph

Es wurde gezeigt, wie zu einem Ia Bild eine geometrisch validierte MengeM = [I0, I1, ...Im] von ahnlichen Bildern aus der Datenbank extrahiert wer-den kann. Davon ausgehend kann nun ein Graph aufgebaut werden, der dieZusammenhange zwischen den Bildern beschreibt. Jeder Knoten V des Gra-phen G(V,Eg) reprasentiert dabei ein Bild. Die gerichteten Kanten Eg ent-sprechen den Beziehungen zwischen Bild Ia der Anfrage und den validiertenTreffern M . Der so aufgebaute Graph Gg enthalt Knoten, die nur durch einegerichtete Kante miteinander verbunden sind. Bildersuche bzw. Validierungwar also nur fur I → J nicht aber fur J ← I erfolgreich. Diese Zuordnungensind nicht stabil und konnen leicht entfernt werden, indem nur bidirektiona-le Kanten beibehalten werden. Der ungerichtete Graph Gu = (V,Eu) bildetdann nur noch Paarungen ab, die in beide Richtungen bestatigt wurden.Abbildung 18 stellt den Vorgang anhand eines kleinen Beispiels dar.

Abbildung 18: Uberfuhrung vom gerichteten in den ungerichteten Graphen

4.3.3 Clustering

Der ungerichtete Graph Gu verbindet jetzt genau die Bildpaare, bei deneneine starke Ahnlichkeit vorliegt und die Epipolargeometrie bestimmt wer-

34


den konnte. Der Graph enthalt dabei Gruppen von Bildern, die mit relativvielen Kanten verbunden sind. Diese Gruppen entsprechen den einzelnenSzenen des Datenbestandes. Durch Analyse der Zusammenhangskomponen-ten konnen diese Gruppen einfach detektiert werden. Innerhalb einer Gruppekann es jedoch vorkommen, dass bestimmte Bereiche nur schwach verbun-den sind. In diesen Fallen ist ein Bereich der zugrunde liegenden Szeneentweder nur schwach reprasentiert, oder es handelt sich um eine fehlerhafteZuordnung. Um den Erfolg der dreidimensionalen Rekonstruktion sicher zustellen, sollten die Gruppen daher an Stellen mit geringer Dichte getrenntwerden. Clauset et al. stellt in [CNM04] einen Algorithmus vor, mit dem esmoglich ist, diese Untermengen selbst in extrem großen Netzwerken zu fin-den. Eine Implementierung findet sich in der Graphenbibliothek SNAP [Les].Abbildung 19 verdeutlicht das Vorgehen. Abbildung 20 zeigt den Graph fur

Abbildung 19: Dichtebasierte Analyse der Zusammenhangskomponenten

einen Teil des Oxford Datensatzes. Einige Gruppen des gerichteten Graphensind noch durch vereinzelte Kanten miteinander verbunden. Der ungerichte-te Graph enthalt diese Verbindungen nicht mehr. Die Graphenbibliothek ex-trahiert hier lediglich die Zusammenhangskomponenten. Die nachfolgendenAbbildungen 21 und 22 zeigen exemplarisch gefundene Szenen des Oxfordsowie Wikimedia Datensatzes.

35


Abbildung 20: Darstellung der Graphen fur einen Teil des Oxford Datensat-zes. Unten der gerichtete Graph, in der Mitte der ungerichtete Graph, obennur Untermengen, aus mindestens 10 Bildern

36


Abbildung 21: Zwei der gefundenen Szenen, Oxford Datensatz

37


Abbildung 22: Großte sowie weitere Szenen des Wikimedia Datensatzes

38

4.4 Implementierungsdetails


Ein Prototyp des Retrivalsystems konnte relativ schnell umgesetzt werden.C++ in Kombination mit STL und OpenCV sind außerst nutzlich bei derEntwicklung von Software. Da Teile der STL jedoch uber eigene Allokati-onsmechanismen verfugen, wurde eine effiziente Speichernutzung behindert.OpenCV vereinfacht die Bildverarbeitung enorm, aber auch hier erschwer-ten einige Konzepte die Skalierbarkeit. Aus diesem Grund wurde eine zweiteeffizientere Version implementiert und auf beides weitestgehend verzichtet.Alle relevanten Bereiche wurden speicher- und laufzeitoptimiert implemen-tiert. Diese Version wurde mit 81K Bildern erfolgreich getestet. Im folgendenwerden kurz zwei relevante Aspekte beleuchtet.

Indexierung. In 3.1.1 wurde bereits darauf hingewiesen, dass die tf-idfMatrix sehr dunn besetzt ist. Bei der Implementierung musste dieser Um-stand ausgenutzt werden, da die naive Implementierung einer tf-idf Matrixbei einer großen Menge an Bilddaten schlecht skaliert. 23 zeigt den linearenAufbau der Datenstruktur. N entspricht der Anzahl unterschiedlicher Quan-tisierung von Bild k, I speichert den Index der Vokabel, V enthalt die tfidfGewichtung.

Abbildung 23: tfidf format

Pro Bild werden maximal nur soviele Werte gespeichert wie unter-schiedliche Quantisierungen existie-ren. Im ungunstigsten Fall wird je-der Merkmalsvektor auf einer anderen Vokabel abgebildet. Bei m Merk-malsvektoren werden also maximal 32Bit(Anzahl) +m ∗ (32Bit(Indices) +32Bit(tfidfd,t)) = m ∗ 64bit+ 32Bit benotigt. Bei 3.000 Merkmalsvektorenpro Bild entspricht das ca. 24KB. Gleichzeitig kann die Matrix so bei Be-darf sequenziell von der Festplatte gelesen werden. Der Index fur die 81.331Bilder des Wikimedia-Datensatzes belegt 1,4GB bei 50k Vokabeln. Das Ran-king benotigt ca. 23s. Bei einer noch großeren Anzahl an Bildern sollte dieStruktur durch einen invertierten Dateiindex ersetzt werden. Das Rankingaller 81K Bilder wurde auf 8 Threads verteilt durchgefuhrt und benotigt aufdem Testsystem ca. 16 Stunden.

Deskriptor Datenbank. Die Deskriptoren werden nicht nur bei derIndexierung sondern auch bei der Validierung der Trefferlisten benotigt undmussen deswegen auf dem Dateisystem gespeichert werden. Auch hier gilt eszu berucksichtigen, dass trotz der großen Datenmenge ein effizienter Zugriffgewahrleistet sein muss. Die Deskriptoren eines jeden Bildes in einzelnen Da-teien zu speichern, ist aufgrund des Overheads beim Offnen und Schließender Dateien wenig effizient. Die Deskriptoren wurden daher binar in einerDatei abgelegt. Der Zugriff erfolgt uber eine Indexstruktur, in der Positionund Große der Deskriptoren gespeichert sind. Die 233M Merkmalsvektoren

39


des Wikimedia-Datensatzes belegen so 32,2GB. Die Funktionalitat der De-skriptordatenbank wurde mit synthetischen Daten getestet. Tabelle 6 zeigtden wahlfreien sowie sequentiellen lesenden Zugriff auf die Deskriptordatenbei unterschiedlichen Konfigurationen. Notiert ist jeweils die durchschnittli-che Zeit, die benotigt wird, um alle Merkmalsvektoren eines Bildes zu lesen.

HW Bilder rnd serial DB Große

SSD 10000 5,6ms 2,5ms 4,4 GBDISK 10000 9,5ms 3,3ms 4,4 GBDISK 100000 11,2ms 3,3ms 44 GB

Tabelle 6: Zugriffszeiten der Deskriptordatenbank, 3.000 Merkmale pro Bild

Laufzeiten. Die Laufzeiten der einzelnen Module wurden mit drei Da-tensatzen und unterschiedlichen Konfigurationen evaluiert. Alle Tests wur-den auf einem Intel I7-860 durchgefuhrt. Die folgende Tabelle zeigt die Ant-wortzeiten des Retrievalsystems.

Datensatz VokabularName Bilder � Features 1k 10k 20k 50k 1M

Oxford 5,1k 3322 0,21 0,77s 1,1s 1,7s 23sUK 10,2k 977 0,24 0,78s 1,2s 2,4s 44sWikimedia 82k 2874 - - - 23s -

Tabelle 7: Antwortzeiten des Retrievalsystems

Die Laufzeiten der einzelnen Schritte des Szenenclustering wurden mitdurchschnittlich 3080 Merkmalsvektoren ermittelt. Die Korrespondenzana-lyse benotigt dabei im Mittel 177ms. Die Bestimmung der Epipolargeometrieerfolgt durchschnittlich in 38ms. Die Gesamtlaufzeit zur Extraktion der Bild-gruppen bei 50k Vokabeln betragt fur den Oxford Datensatz 17,4h und dieBildgruppen des UK Datensatzes konnen in 11,9 berechnet werden. DurchParallelisierung konnte die Laufzeit auf 2,8 bzw. 1,9 Stunden reduziert wer-den. Die parallelisierte Extraktion der Bildgruppen des Wikimediadatensat-zes benotigt ca. 4 Tage.

Parallelisierung. Um die Geschwindigkeit weiter zu erhohen und dieheute ubliche Multicore-Prozessor Architektur optimal zu nutzen, wurdenalle rechenintensiven Operationen mittels OpenMP parallelisiert. Abbildung24 zeigt den parallelisierten Programmfluss. Da der schreibende Zugriff aufdie Deskriptordatenbank als kritische Sektion behandelt wird, konnen die

40


Abbildung 24: Parallelisierung der einzelnen Module

Merkmale parallelisiert extrahiert werden. Um das Clustering weiter zu be-schleunigen, werden die Daten aufgeteilt und die kd-Baume parallel abge-fragt. Bei der Erzeugung des Szenengraphs werden die Anfragen an dasRetrievalsystem und die Validierung der Trefferlisten parallel durchgefuhrt.

41

5 Diskussion

5 Diskussion

5.1 Zusammenfassung der wesentlichen Ergebnisse

Im Rahmen dieser Arbeit wurde ein System entwickelt, mit dem es moglichist, große unstrukturierte Bildbestande automatisiert fur eine dreidimen-sionale Rekonstruktion zu gruppieren. Es wurden bestehende Systeme undMethoden vorgestellt und basierend auf dem Stand der Technik eine Losungentworfen. Das implementierte System ermittelt die Ahnlichkeiten zwischenden Bildern des Datenbestandes und extrahiert automatisiert Gruppen vonBildern, welche dieselbe Szene abbilden. Es werden affin-invariante Bild-merkmale extrahiert und mittels Vektorquantisierung auf ein vorher erzeug-tes visuelles Vokabular abgebildet. Jedes Bild wird anhand der quantisiertenVektoren indexiert. Ahnliche Bilder werden uber den erstellten und tfidf ge-wichteten Index effizient ermittelt. Die geometrische Uberprufung der Bild-paarungen stellt anschließend sicher, dass eine dreidimensionale Rekonstruk-tion erfolgreich durchgefuhrt werden kann. Die Implementierung wurde wei-testgehend parallelisiert und verarbeitet Datenbestande von bis zu 100k aufgewohnlicher Desktop Hardware. Das System wurde abschließend mit einemumfangreichen Bestand historischer Aufnahmen gepruft. Die untersuchten82.519 Bilder stammen aus dem vom Bundesarchiv verwalteten historischenAufnahmenbestand Deutschlands. Diese Aufnahmen wurde am 4. Dezember2008 der Wikimedia Foundation ubergeben und sind frei zuganglich.

5.2 Diskussion der Ergebnisse

Generierung des visuellen Vokabulars. Die mittels approximiertemk-means erzeugten Vokabulare sind zur Vektorquantisierung geeignet. Dieapproximierte Suche des nachsten Nachbarn fuhrt bei großen Datenmengenzu einem deutlichen Geschwindigkeitsvorteil. Gleichzeitig verbessert sich diePrazision durch parallele Suche in mehreren randomisierten k-d Baumen si-gnifikant. Die Prazision ist jedoch an die Korrelation zwischen Daten undden k-means Prototypen gekoppelt. Beim Clustering steigt die Korrelationzwar stetig, letztendlich ist diese jedoch abhangig von den zugrunde liegen-den Daten. Der Zusammenhang zwischen Parametrisierung der Suche undPrazision beim k-means Clustering ist somit nicht trivial.

Retrievalsystem. Die inhaltsbasierte Bildersuche wurde mit unterschied-lichen Konfigurationen getestet. Die experimentelle Auswertung belegt dievorteilhaften Eigenschaften des Harris affine-invarianten Detektors. Die Co-sinus Metrik, als Maß zwischen den tfidf gewichteten Vektoren des Index,liefert die besten Ergebnisse. Verglichen mit den in [PCI+07] veroffentlichtenErgebnissen ist die implementierte Variante jedoch schlechter. Ursache konntehier die bei der Indexierung verwendete approximierte Variante der Vektor-

42

5.3 Kritische Methodenreflexion

quantisierung sein.

Szenenclustering. Die vom Szenenclustering gelieferten Bildgruppen zei-gen ausschließlich Aufnahmen derselben Szene. Die Validierung der Tref-ferlisten durch Epipolargeometrie sowie das Verwerfen aller unidirektiona-len Korrespondenzen filtern verlasslich fehlerhafte Zuordnungen. Die fur dieBestimmung der Epipolargeometrie notwendige Korrespondenzanalyse derFeaturevektoren wurde ebenfalls durch approximierte Suche beschleunigt.Der Vorgang bleibt trotzdem rechenintensiv, weswegen lediglich die ersten50 Treffer einer jeden Liste untersucht werden.

5.3 Kritische Methodenreflexion

Die Generierung des visuellen Vokabulars mittels approximiertemk-means ist eine mogliche Losung. Die Abhangigkeit zwischen Parametrisie-rung und Eingangsdaten fuhrt jedoch zu einer komplexen Situation. DieseKomplexitat konnte auch die Ursache sein, warum sich Agarwal et al. in[AFS+10] fur das von Nister und Henrik Stewenius eingefuhrte [NS06] hier-archische Clustern entscheiden.

Die approximierte Vektorquantisierung fuhrt zu einer teilweise feh-lerhaften Indexierung. Hier sollte genauer untersucht werden, wie stark sichder Fehler auf die Qualitat beim Retrieval auswirkt. Eine exakte Suchekonnte parallelisiert durchgefuhrt werden, um den Geschwindigkeitsverlustzumindest teilweise zu kompensieren.

Die Indexierung und tfidf Gewichtung ist weitestgehend alternativlosbei Analyse großer Datenbestande. Bei der Implementierung der tfidf Matrixwurde berucksichtigt, dass ein Großteil der Eintrage ungenutzt bleibt. DieImplementierung ist speichereffizient, das Ranking sollte jedoch durch eineninvertierten Dateiindex beschleunigt werden.

Das Szenenclustering extrahiert die Bildgruppen zuverlassig. Die Ver-wendung der SNAP Bibliothek zur Extraktion der Gruppen ist nicht un-bedingt notwendig. Eine simple Analyse der Zusammenhangskomponentenscheint hier ausreichend und konnte durch Query Expansion weiter verbes-sert werden [AFS+10]. Der von SNAP verwendete Algorithmus verursachtaußerdem in Ausnahmefallen bei großen Szenen, die durch relativ viele Auf-nahmen erfasst wurden, die Teilung der Szene in mehrere Gruppen. DieserEffekt tritt auf, wenn einzelne Bereiche sich bezogen auf die Gesamtgroßeder Gruppe, nur wenig uberlappen und konnte bei einer Szene des OxfordDatensatzes beobachtet werden.

43

5.4 Schlussfolgerung

5.4 Schlussfolgerung

Das implementierte System stellt nur die erste Stufe der zur 3D Rekon-struktion benotigten Software dar. Es wurde gezeigt, dass mit der imple-mentierten Losung umfangreiche Bildbestande erfolgreich analysiert werdenkonnen. Aufgrund der gefundenen Korrespondenzen konnen die Kamerapo-sition und einige 3D Punkte berechnet werden. Zur 3D Visualisierung sindjedoch relativ dichte Punktewolken notig. Im Bezug auf die zum Teil sehrunterschiedlichen historischen Aufnahmen werden die bekannten Verfahrenzur Erstellung solch dichter Punktwolken nicht ohne spezielle Optimierun-gen anwendbar sein. Eine einfachere, jedoch eingeschrankte Losung bei derVisualisierung, scheinen hier die Methoden des View Morphing zu bieten,bei dem zwischen den Bildern ubergeblendet wird. Da bei vielen der archi-vierten Bilder das Aufnahmedatum bekannt ist, bietet sich bei einer entspre-chend großen Datenbasis außerdem die Moglichkeit, die Szenen im Laufe derZeit zu betrachten. Da die Menge der verfugbaren Bilder kritisch ist, solltedie Nutzung historischer Videoaufnahmen in Betracht gezogen werden. Zurdreidimensionalen Rekonstruktion historischer Bilder bleiben also weitereoffene Problemstellungen. In jedem Fall hangt der Erfolg von der Menge derarchivierten und digital verfugbaren Bilder ab.

44

Literatur

Literatur

[AFS+10] Sameer Agarwal, Yasutaka Furukawa, Noah Snavely, Brian Cur-less, Steven M. Seitz, and Richard Szeliski. Reconstructing rome.Computer, 43:40–47, 2010.

[CB03] W. Chojnacki and M. J. Brooks. Revisiting Hartley’s normali-zed eight-point algorithm. Pattern Analysis and Machine Intel-ligence, IEEE Transactions on, 25(9):1172–1177, 2003.

[CNM04] Aaron Clauset, M. E. J. Newman, and Cristopher Moore. Fin-ding community structure in very large networks. Physical Re-view E, 70(6):066111+, December 2004.

[DJLW08] Ritendra Datta, Dhiraj Joshi, Jia Li, and James Z. Wang. Imageretrieval: Ideas, influences, and trends of the new age. ACMComput. Surv., 40(2):1–60, May 2008.

[FB81] Martin A. Fischler and Robert C. Bolles. Random sample con-sensus: A paradigm for model fitting with applications to imageanalysis and automated cartography. Communications of theACM, 24(6):381–395, 1981.

[Har95] R.I. Hartley. In defence of the 8-point algorithm. ComputerVision, IEEE International Conference on, 0:1064, 1995.

[HZ04] R. I. Hartley and A. Zisserman. Multiple View Geome-try in Computer Vision. Cambridge University Press, ISBN:0521540518, second edition, 2004.

[KM07] Georg Klein and David Murray. Parallel Tracking and Mappingfor Small AR Workspaces. In Mixed and Augmented Reality,2007. ISMAR 2007. 6th IEEE and ACM International Sympo-sium on, pages 1–10, November 2007.

[Les] Jure Leskovec. http://snap.stanford.edu/snap/.

[Lon81] Longuet. A computer algorithm for reconstructing a scene fromtwo projections. Nature, 293:133–135, September 1981.

[Low99] David G. Lowe. Object recognition from local scale-invariant fea-tures. In Proceedings of the International Conference on Com-puter Vision-Volume 2 - Volume 2, ICCV ’99, pages 1150–, Wa-shington, DC, USA, 1999. IEEE Computer Society.

[Low04] David G. Lowe. Distinctive image features from scale-invariantkeypoints. Int. J. Comput. Vision, 60:91–110, November 2004.

45

Literatur

[Mik] Mikolajczyk. http://www.robots.ox.ac.uk/ vgg/research/affi-ne/detectors.html.

[ML09] Marius Muja and David G. Lowe. Fast approximate nearestneighbors with automatic algorithm configuration. In In VIS-APP International Conference on Computer Vision Theory andApplications, pages 331–340, 2009.

[MRS08] Christopher D. Manning, Prabhakar Raghavan, and HinrichSchutze. Introduction to Information Retrievalm. CambridgeUniversity Press, 1 edition, July 2008.

[MS04] Krystian Mikolajczyk and Cordelia Schmid. Scale & affine inva-riant interest point detectors. Int. J. Comput. Vision, 60:63–86,October 2004.

[MS05] K. Mikolajczyk and C. Schmid. A performance evaluation oflocal descriptors. IEEE Transactions on Pattern Analysis andMachine Intelligence, 27(10):1615–1630, October 2005.

[MTS+05] K. Mikolajczyk, T. Tuytelaars, C. Schmid, A. Zisserman, J. Ma-tas, F. Schaffalitzky, T. Kadir, and L. Gool. A Comparison ofAffine Region Detectors. International Journal of Computer Vi-sion, 65(1):43–72, November 2005.

[NLD11] Richard Newcombe, Steven Lovegrove, and Andrew Davison.DTAM: Dense Tracking and Mapping in Real-Time. In 13thInternational Conference on Computer Vision (ICCV2011), No-vember 2011.

[NS06] David Nister and Henrik Stewenius. Scalable recognition witha vocabulary tree. In Proceedings of the 2006 IEEE ComputerSociety Conference on Computer Vision and Pattern Recognition- Volume 2, CVPR ’06, pages 2161–2168, Washington, DC, USA,2006. IEEE Computer Society.

[PCI+07] James Philbin, Ondrej Chum, Michael Isard, Josef Sivic, andAndrew Zisserman. Object retrieval with large vocabularies andfast spatial matching. In Computer Vision and Pattern Recogni-tion, 2007. CVPR ’07. IEEE Conference on, pages 1–8, 2007.

[PNF+08] M. Pollefeys, D. Nister, J. M. Frahm, A. Akbarzadeh, P. Mor-dohai, B. Clipp, C. Engels, D. Gallup, S. J. Kim, P. Merrell,C. Salmi, S. Sinha, B. Talton, L. Wang, Q. Yang, H. Stewenius,R. Yang, G. Welch, and H. Towles. Detailed Real-Time Urban3D Reconstruction from Video. Int. J. Comput. Vision, 78:143–167, July 2008.

46

Literatur

[PZ] James Philbin and Andrew Zisserman.http://www.robots.ox.ac.uk/ vgg/data/oxbuildings/in-dex.html.

[Rod04] Volker Rodehorst. Photogrammetrische 3D-Rekonstruktion imNahbereich durch Auto-Kalibrierung mit projektiver Geometrie.Ph.d. dissertation, Berlin University of Technology, June 2004.

[SAH08] C. Silpa-Anan and R. Hartley. Optimised KD-trees for fastimage descriptor matching. In Computer Vision and PatternRecognition, 2008. CVPR 2008. IEEE Conference on, pages 1–8, June 2008.

[SGC10] Jan Stuhmer, Stefan Gumhold, and Daniel Cremers. Real-TimeDense Geometry from a Handheld Camera. In Michael Goesele,Stefan Roth, Arjan Kuijper, Bernt Schiele, and Konrad Schind-ler, editors, Pattern Recognition, volume 6376 of Lecture Notesin Computer Science, chapter 2, pages 11–20. Springer Berlin /Heidelberg, Berlin, Heidelberg, 2010.

[SN] Henrik Stewenius and David Nister.http://www.vis.uky.edu/ stewe/ukbench/.

[SSS08] Noah Snavely, Steven M. Seitz, and Richard Szeliski. Skeletalgraphs for efficient structure from motion. Computer Visionand Pattern Recognition, IEEE Computer Society Conferenceon, 0:1–8, 2008.

[SZ03] J. Sivic and A. Zisserman. Video Google: a text retrieval ap-proach to object matching in videos. Computer Vision, IEEEInternational Conference on, 2:1470–1477 vol.2, October 2003.

[TH81] R. Y. Tsai and T. S. Huang. Estimating three-dimensional moti-on parameters of a rigid planar patch. IEEE Trans. on Acoustics,Speech and Signal Processing, ASSP-29(6):1147–1152, 1981.

[TMHF00] Bill Triggs, Philip F. McLauchlan, Richard I. Hartley, and An-drew W. Fitzgibbon. Bundle adjustment - a modern synthesis.In Proceedings of the International Workshop on Vision Algo-rithms: Theory and Practice, ICCV ’99, pages 298–372, London,UK, 2000. Springer-Verlag.

[Ved] Vedaldi. http://www.vlfeat.org/ vedaldi/code/siftpp.html.

47

Abbildungsverzeichnis

Abbildungsverzeichnis

1 Vgl. [SZ03] Abbildung 2, Zugehorige Daten zweier k-meansPrototypen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Vgl. [Low04] Abbildung 1, Skalenraum . . . . . . . . . . . . . 113 [Low04] Abbildung 2, Detektion der Extrema . . . . . . . . . 114 Vgl. [MS04] Abbildung 1, Aufnahmen mit unterschiedlicher

fokaler Lange und Antwort der LoG Funktion . . . . . . . . . 145 Uniforme und nicht-uniforme Skalierung . . . . . . . . . . . . 156 Affine und Skalierungsinvariente Regionen . . . . . . . . . . . 157 Vgl. [Low04] Abbildung 7, Bildgradienten und Deskriptor . . 168 Beziehung zwischen Welt- und Bildkoordinatensystem . . . . 189 Geometrie der Lochkamera . . . . . . . . . . . . . . . . . . . 1910 Vgl. [HZ04] S.240, Epipolargeometrie . . . . . . . . . . . . . . 2111 Vgl. [HZ04] S.240, Basislinie und Epipolarebene . . . . . . . . 2112 Detektierte Bereiche des Harris affin invarianten Detektors . . 2613 Entwicklung der Prazision in Abhangigkeit der zu traversie-

renden Knoten und Geschwindigkeitsvorteil gegenuber linea-rer Suche (3000 Datenpunkte) . . . . . . . . . . . . . . . . . . 28

14 Entwicklung der Prazision in Abhangigkeit der zugrunde lie-genden Datenmenge und Geschwindigkeitsvorteil gegenuberder linearer Suche . . . . . . . . . . . . . . . . . . . . . . . . 29

15 Entwicklung der Prazision beim approximierten K-means Clus-tering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

16 Zuordnung der SIFT Deskriptoren . . . . . . . . . . . . . . . 3317 Zuordnung nach Filterung durch Epipolargeometrie . . . . . . 3418 Uberfuhrung vom gerichteten in den ungerichteten Graphen . 3419 Dichtebasierte Analyse der Zusammenhangskomponenten . . 3520 Darstellung der Graphen fur einen Teil des Oxford Datensat-

zes. Unten der gerichtete Graph, in der Mitte der ungerichteteGraph, oben nur Untermengen, aus mindestens 10 Bildern . . 36

21 Zwei der gefundenen Szenen, Oxford Datensatz . . . . . . . . 3722 Großte sowie weitere Szenen des Wikimedia Datensatzes . . . 3823 tfidf format . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3924 Parallelisierung der einzelnen Module . . . . . . . . . . . . . . 41

48

Documents

Inhaltsbasierte Bildersuche als notwendige Vorbereitung ... · informationssystemen verwendet. Google Earth und Microsoft Virtual Earth sind zwei popul are Beispiele, die zeigen,