Diplomarbeit - TU Dresden · Diplomarbeit zur Erlangung des akademischen Grades Diplom-Informatikerin Entwicklung eines Verfahrens zur automatischen relativen Orientierung zwischen

TECHNISCHEUNIVERSITÄT DRESDEN

FAKULTÄT INFORMATIK

INSTITUT FÜR SOFTWARE- UND MULTIMEDIATECHNIK

PROFESSUR FÜRCOMPUTERGRAPHIK UNDV ISUALISIERUNG

PROF. DR. STEFAN GUMHOLD

Diplomarbeit

zur Erlangung des akademischen GradesDiplom-Informatikerin

Entwicklung eines Verfahrens zur automatischenrelativen Orientierung zwischen

Laserscannerpunktwolken und Bilddaten auf Basisvon Intensitätsdaten

Anita Schilling(Geboren am 11. März 1985 in Dresden)

Betreuer: Prof. Dr. Stefan GumholdProf. Dr. Hans-Gerd Maas

Dresden, 9. April 2010

Aufgabenstellung

Die Registrierung von 2D-Bilddaten einer Kamera mit 3D-Daten desselben Objekts, die mittels eines

terrestrischen Laserscanners akquiriert wurden, ist eine Voraussetzung für die Generierung detaillierter

texturierter dreidimensionaler Objektmodelle. Ziel der Arbeit ist die Bestimmung der relativen Orien-

tierung eines von einem frei gewählten Standort aufgenommenen RGB-Bildes zu einer Laserscanner-

punktwolke. Für die Registrierung sollen die Intensitätswerte des vom Laserscanner ausgesendeten und

vom Objekt reflektierten Laserimpulses genutzt werden. Durch Abbildung dieser Intensitätswerte auf ei-

ne Ebene kann ein Intensitätsbild des Objekts berechnet werden. Da die Intensitätsdaten mit demselben

Laserimpuls wie die Punktwolke ermittelt werden, ist das Intensitätsbild bereits perfekt mit der Lasers-

cannerpunktwolke registriert. Somit kann die relative Orientierung des RGB-Bildes zur Punktwolke auf

Basis der gefundenen Korrespondenzen mit den Intensitätsdaten bestimmtwerden.

Der Kern der Arbeit liegt in der automatischen Detektion und Zuordnung von Merkmalen im Intensitäts-

und RGB-Bild. Die zu detektierenden Merkmale für die Registrierung müssenaußerdem so ausgewählt

werden, dass die unterschiedlichen Modalitäten der Bilder berücksichtigtwerden. Dabei ist auch zu be-

rücksichtigen, dass der von Scanner und Kamera abgebildete Objektbereich möglicherweise nicht iden-

tisch ist. Die berechnete relative Orientierung soll anschließend durch Texturierung der Punktwolke mit

dem RGB-Bild visualisiert werden.

Detailaufgaben:

• Auswahl und Diskussion geeigneter Verfahren der Merkmalserkennung und -zuordnung.

• Untersuchung der unterschiedlichen Eigenschaften von Intensitäts- und RGB-Bildern.

• Merkmalserkennung und Registrierung des RGB-Bildes mit dem Intensitätsbild sowie Bestim-

mung der relativen Orientierung.

• Identifikation von Parametern zur Beschreibung der Genauigkeit und Zuverlässigkeit der Lösung,

Vergleich mit Referenzmessungen.

• Visualisierung der Ergebnisse als (teil)texturierte Punktwolke.

Selbstständigkeitserklärung

Hiermit erkläre ich, dass ich die von mir am heutigen Tag dem Prüfungsausschuss der Fakultät Informa-

tik eingereichte Diplomarbeit zum Thema:

Entwicklung eines Verfahrens zur automatischen relativen Orientierung zwischen

Laserscannerpunktwolken und Bilddaten auf Basis von Intensitätsdaten

vollkommen selbstständig verfasst und keine anderen als die angegebenen Quellen und Hilfsmittel be-

nutzt sowie Zitate kenntlich gemacht habe.

Dresden, den 9. April 2010

Anita Schilling

Kurzfassung

In dieser Arbeit wurde die Entwicklung eines Verfahrens zur automatischen relativen Orientierung eines

Fotos zu einer Laserscannerpunktwolke, die durch ein Intensitätsbild repräsentiert wird, angestrebt. Die

Möglichkeiten zur Darstellung der Punktwolke als Bild mit den Intensitätswertenwurde untersucht. Die

benötigten Punktkorrespondenzen werden durch automatische Merkmalsextraktion und -zuordnung er-

stellt. Experimente zeigten, dass ein Anteil von ca. 18% richtiger Korrespondenzen an den automatisch

mit SIFT bestimmten Zuordnungsmengen von RANSAC gefunden wird. Die relative Orientierung wur-

de über eine Kleinste-Quadrate-Ausgleichung unter Verwendung von Näherungswerten berechnet, die

mit der Direkten Linearen Transformation bestimmt wurden. Für die automatischerstellten Punktkorre-

spondenzen konnte keine Orientierung aufgrund unzureichender Punktverteilung berechnet werden. Die

Orientierung von Fotos mit manuell erstellten Korrespondenzen zeigte, dass sich der verwendete Ansatz

für die Generierung visuell ansprechend texturierter Objektmodelle eignet.

1

Inhaltsverzeichnis

1 Einleitung 3

2 Terrestrisches Laserscanning 5

2.1 Prinzipien der Entfernungsmessung . . . . . . . . . . . . . . . . . . . . . . .. . . . . 5

2.2 Abbildung der Punktwolke auf Bildkoordinaten . . . . . . . . . . . . . . . . .. . . . . 10

2.3 Zentralperspektivische Abbildung der Punktwolke . . . . . . . . . . . . .. . . . . . . . 13

2.4 Verbesserung des Intensitätsbildes . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 15

3 Relative Orientierung eines Bildes 19

3.1 Parameter der relativen Orientierung . . . . . . . . . . . . . . . . . . . . . . .. . . . . 19

3.2 Direkte Lineare Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 21

3.3 Kleinste-Quadrate-Ausgleichung . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 23

3.4 Ergebnisse der Orientierung und Texturierung . . . . . . . . . . . . . . .. . . . . . . . 25

4 Detektion und Zuordnung von Merkmalen 31

4.1 Eigenschaften merkmalsbasierter Detektion und Zuordnung . . . . . . . .. . . . . . . . 31

4.2 Anforderungen an den Merkmalsdetektor . . . . . . . . . . . . . . . . . . .. . . . . . 33

4.3 Scale Invariant Feature Transform (SIFT) . . . . . . . . . . . . . . . .. . . . . . . . . 34

5 Zuordnung von Intensitätsbildern und Fotos mit SIFT 41

5.1 Verwendete Datensätze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 41

5.2 Berechnung der SIFT-Merkmalspunkte . . . . . . . . . . . . . . . . . . . .. . . . . . . 43

5.3 Evaluation der SIFT-Zuordnung . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 44

5.4 Automatische Bestimmung der Homographie mit RANSAC . . . . . . . . . . . . . . . 47

5.5 Diskussion der Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 56

6 Zusammenfassung 61

Literaturverzeichnis 65

2

3

1 Einleitung

Die Erstellung detaillierter texturierter Objektmodelle ist eine Voraussetzung, um dreidimensionale Stadt-

modelle generieren oder Kulturschätze digital dokumentieren zu können. Die dreidimensionale Objekt-

geometrie lässt sich effizient und präzise mit einem terrestrischen Laserscanner erfassen. Das Ergebnis

einer Aufnahme mit dem Laserscanner ist eine Punktwolke, die das Objektrepräsentiert jedoch keine

Farbinformationen enthält. Um ein Foto desselben Objektes als Quelle für Farbinformationen zum Tex-

turieren der Punktwolke zu verwenden, muss die Aufnahmesituation des Fotos rekonstruiert werden.

Dies kann durch Berechnung von Parametern erreicht werden, die dierelative Orientierung des Fotos zur

Laserscannerpunktwolke beschreiben. Dafür sind Punktkorrespondenzen zwischen dem zweidimensio-

nalen Foto und der dreidimensionalen Punktwolke notwendig.

Für jeden vom Laserscanner gemessenen Punkt wird der Bruchteil des Laserstrahls aufgezeichnet, der

von der Umgebung reflektiert wurde. Die Interpretation dieser Intensitätswerte als Grauwerte ermög-

licht die Darstellung der Punktwolke als Bild, indem die 3D-Punkte auf eine virtuelle Ebene abgebildet

werden. Die Intensitätswerte des Laserscanners werden bisher nur selten genutzt und dienen meist zum

ersatzweisen Einfärben der Punktwolke. Das Ziel dieser Arbeit ist die Bestimmung der Orientierungspa-

rameter über Punktkorrespondenzen, die zwischen dem Intensitätsbild und dem Foto hergestellt werden.

Durch das Intensitätsbild sind damit automatisch die korrespondierenden 3D-Koordinaten für die ausge-

wählten Punkte im Foto bekannt. Die Verwendung von Bildverarbeitungsmethoden zur Herstellung der

Punktkorrespondenzen zwischen Bildern stellt einen wesentlichen Vorteil dar, da so der mögliche Such-

raum für identische Punkte viel stärker einschränkt wird als bei einer Suche nach ähnlichen Punkten in

3D-Punktwolke und 2D-Bild.

Im folgenden Kapitel wird zunächst das Prinzip des Laserscannings erläutert. Danach werden die Mög-

lichkeiten analysiert mit denen die Punktwolke als Intensitätsbild dargestellt werden kann. Die Berech-

nung der relativen Orientierung über gegebene Punktkorrespondenzen wird im dritten Kapitel erklärt.

Anschließend wird im darauf folgenden Abschnitt dargestellt, wie Punktkorrespondenzen über die Ex-

traktion und Zuordnung von Merkmalspunkten etabliert werden können.Außerdem wird in diesem Ab-

schnitt ein Merkmalsdetektor für diese Anwendung vorgestellt. Im Anschlusskapitel wird das Vorgehen

bei den Experimenten zur automatischen Merkmalsextraktion und -zuordnung beschrieben. Außerdem

4 1. EINLEITUNG

werden die Ergebnisse diskutiert. Im letzten Kapitel werden die Ergebnisse der Arbeit abschließend zu-

sammengefasst.

Auf der DVD, die der Arbeit beiliegt, befindet sich die PDF-Version dieser Arbeit. Sie enthält außerdem

die Datensätze, mit denen die Experimente ausgeführt wurden, und alle Matlab-Skripte. Des Weiteren

befinden sich auf der DVD die C++-Implementierung der im zweiten Kapitel beschriebenen Vorgehens-

weisen zur Generierung des Intensitätsbilds und ein Visualisierungswerkzeug zur Texturierung einer

Laserscannerpunktwolke mit einem Foto, das unter Verwendung des CGVFrameworks entstanden ist.

5

2 Terrestrisches Laserscanning

LiDAR (light detection and ranging) ist der Überbegriff für Techniken,die elektromagnetische Strahlung

zur Messung von Distanzen einsetzen und kommt ursprünglich aus der Fernerkundung. Das Laserscan-

ning gehört zu dieser Klasse, da ein laserbasierter Entfernungsmesser eingesetzt wird. Der Laser (Light

amplification by stimulated emission of radiation) arbeitet meist im Nahinfrarotbereich, wobei die kon-

krete Wellenlänge sowie sämtliche technischen Details zwischen den Herstellern unterschiedlich sein

können. Für die Entfernungsmessung gibt es zwei generelle Ansätze:die Laufzeitmessung und das Pha-

senvergleichsverfahren.

2.1 Prinzipien der Entfernungsmessung

Laufzeitmessung

Der schematische Aufbau eines Laserscanners mit Laufzeitmessung (TOF, Time-Of-Flight) ist in Abbil-

dung 2.1 gegeben. Ein Laserimpuls wird über eine kurze Zeitspanne hinweg ausgesendet, dabei wird ein

Teil des Strahls, der aus dem Laser kommt, durch einen Spiegel auf eine Photodiode abgelenkt. Das Auf-

treffen des Laserstrahls auf die Photodiode startet die Zeitmessung im Laserscanner. Der ausgesendete

Laserimpuls wird an einem Objekt reflektiert und kommt mit einem Bruchteil derursprünglichen Stärke

zum Scanner zurück. Die eintreffende Reflektion wird über Spiegel konzentriert und ebenfalls auf eine

Photodiode gelenkt. Überschreitet die in der Photodiode registrierte Stärke des reflektierten Laserimpul-

ses einen bestimmten Grenzwert, wird die Zeitmessung gestoppt. Da die Lichtgeschwindigkeitc bekannt

ist, lässt sich auf Basis des gemessenen Zeitintervallst die Distanzd einfach mit

d =1

2· c · t (2.1)

berechnen. Die Genauigkeit der Entfernungsmessung ist damit direkt abhängig von der Präzision bzw.

Stabilität des internen Oszillators, der für die Zeitmessung genutzt wird ([ST09], S. 17). Die Laufzeit-

messsung wird in den meisten Laserscannern eingesetzt und ermöglicht je nach Energie des verwendeten

Lasers Messungen von bis zu 1000m ([HL09], S. 90).

6 2. TERRESTRISCHES LASERSCANNING

Abbildung 2.1: Aufbau eines Laserscanners mit Laufzeitmessung

Phasenvergleichsverfahren

Beim Phasenvergleichsverfahren wird im Gegensatz zur Laufzeitmessung der Laserstrahl kontinuierlich

gesendet. Die Trägerwelle des Laserstrahl wird durch Amplitudenmodulation mit einer weiteren Welle

meistens in Form einer Sinuswelle zum Zwecke der Entfernungsmessung überlagert. Diese Messwelle

wird mittels eines stabilen Frequenzoszillators auf einem konstanten Wert gehalten. Für die Bestimmung

der Entfernung wird die Phase des ausgesendeten modulierten Laserstrahls mit der Phase des ankom-

menden Signals verglichen und die Phasendifferenz (Phasenwinkelφ) festgestellt. Der Phasenwinkel

repräsentiert einen Bruchteil der Gesamtdistanz, da die Anzahl der vollen WellenlängenM , die dazwi-

schen liegt, nicht mit nur einer Welle bestimmt werden kann. Um diese Mehrdeutigkeiten aufzulösen

werden meistenn Messungenφi in schneller Folge mit unterschiedlichen Wellenlängenλi gemacht. Die

Lösung des sich daraus ergebenden Gleichungssystems

d = M1 ·λ1

2+

φ1

2π

λ1

2(2.2)

d = M2 ·λ2

2+

φ2

2π

λ2

2(2.3)

. . . (2.4)

d = Mn · λn

2+

φn

2π

λn

2(2.5)

für d erhält man die zu bestimmende Entfernung ([ST09], S. 4). Die maximal messbare Entfernung

ist dabei abhängig von der Wellenlänge der längsten Trägerwelle. Dieses Verfahren wird bei mittleren

Entfernungsmessungen bis ungefähr 100m eingesetzt.

Bei einem Scan befindet sich der Laserscanner im Ursprung des Aufnahmekoordinatensystems. Lasers-

canner für terrestrische Anwendungen zeichnen sich dadurch aus,dass sie fest positioniert werden. Um

die Umgebung erfassen zu können, muss der Laserscanner gedrehtoder der Laser durch Spiegel, deren

Ausrichtung vom Scanner gesteuert wird, abgelenkt werden. Die Werte für die Ausrichtung des Laser-

strahls in horizontaler und vertikaler Richtung(φ, θ) werden zu jeder Distanzmessung aufgezeichnet und

2.1. PRINZIPIEN DER ENTFERNUNGSMESSUNG 7

Abbildung 2.2: Polarkoordinatensystem des Scanners

ergeben so ein Aufnahmeraster in Polarkoordinaten um den Scanner, wie in Abbildung 2.2 skizziert. Die

Schrittweiten(∆φ,∆θ) in horizontaler und vertikaler Richtung können meist vom Nutzer passend zum

Scan gewählt werden und bestimmen die Anzahl der Messungen. Das Ergebnis eines Scanvorgangs ist

eine Punktwolke, die die gescannte Umgebung repräsentiert. Über

x = sin pφ · d (2.6)

y = cos pφ · d (2.7)

z = sin pθ · d (2.8)

werden die Punktep der Punktwolke anschließend in kartesische Koordinaten transformiert.

Die Stärke des reflektierten Laserstrahls ist abhängig von den Reflektionseigenschaften der Objektober-

fläche. Wird der Laserimpuls komplett in eine andere Richtung abgelenkt (Abbildung 2.3(b)), gelangt

kein Teil des Stahls mehr zum Scanner zurück und es wird kein Punkt aufgezeichnet. Bei totaler Re-

flektion wird dagegen praktisch der gesamte einfallende Impuls wieder reflektiert (Abbildung 2.3(a)).

Dies ist beispielsweise bei retroreflektierenden Zielmarken der Fall, die für die Verknüpfung mehrerer

Scans genutzt werden und die aufgrund der Stärke des reflektierten Strahls meist gut in den Messungen

identifiziert werden können. Für gewöhnlich wird ein Laserstrahl allerdings in alle Richtungen gestreut

(Abbildung 2.3(c)) und nur eine schwache Reflektion findet zum Laserscanner zurück.

Helle Materialien reflektieren mehr als dunkle Oberflächen. Bei farbigen Materialien ist die Reflektion

abhängig von den spektralen Charakteristiken des Laserstrahls ([HL09], S. 92). Die Reflektionseigen-

schaften hängen auch von der konkreten Wellenlänge des Lasers ab.Wasser absorbiert Nahinfrarotstrah-

lung und es entstehen an diesen Stellen Datenlöcher. Glasoberflächen können mit einem Laser im Na-

hinfrarotbereich genausowenig erfasst werden, da Glas diese Strahlung ungehindert durchlässt ([HL09],

S. 33). In Tabelle 2.1 ist eine Aufstellung der Reflektionsstärke für ausgewählte Materialien bei einer

Wellenlänge von 900nm gegeben. Zusätzlich wirken meteorologische Einflüsse auf den Laserstrahl ein,

so dass sich die Reichweite deutlich reduzieren kann.


(a) Totalreflektion (b) Komplette Ablenkung (c) Streuung

Abbildung 2.3: Reflektionsarten

Material Reflektivität Material Reflektivität

Weißes Paper bis zu 100% Bauholz (Kiefer, sauber, trocken) 94%

Schnee 80-90% Bierschaum 88%

Weißes Mauerwerk 85% Kalkstein, Lehm bis zu > 75%

Zeitung mit Text 69% Papiertuch (2-lagig) 60%

Laubbaum typ. 60% Nadelbaum typ. 30%

Strandsand typ. 50% rauhe Holzpalette (sauber) 25%

Beton, glatt 24% Asphalt mit Kieselsteinen 17 %

Lava 8% Schwarzes Neoprene 5%

Reflektionsfolie 3M2000X 1250% Weiße Plaste, opak1 110%

Schwarze Plaste, opak1 17% Klare Plaste1 50%

1 Maximales Antwortsignal bei orthogonalem Einstrahlwinkel zur Oberfläche

Tabelle 2.1: Reflektionswerte nach [Rie08]

Obwohl der Laser aufgrund seiner Kohärenzcharakteristik ein hochgebündelter Strahl ist, ist er den-

noch von einer Strahldivergenz betroffen. Das bedeutet, das der Durchmesser bzw. der Footprint des

Strahls mit der Entfernung größer wird. Eine Strahldivergenz von 0,25mrad am Laser entspricht einer

Vergrößerung des Durchmessers von 2,5cm auf 100m Entfernung. Damit wird der Laserstrahl nicht von

einem idealen geometrischen Punkt am Objekt reflektiert, sondern von einem OberflächenbereichAo.

Die eigentliche Reflektionsstärke ist folglich abhängig von den Eigenschaften der Materialien in diesem

Bereich. Wenn der Laserstrahl auf eine Kante trifft, wird für diese Ausrichtung des Lasersstrahls, d.h.

die Polarkoordinaten(pφ, pθ) nur ein Distanzwert gemessen, welcher allerdings in der Punktwolke den

gesamten OberflächenbereichAo repräsentiert. Durch diese Unterabtastung repräsentiert die resultieren-

de Punktwolke nur eine Approximation der Umgebung. Die reflektierte Energie des Lasers lässt sich

2.1. PRINZIPIEN DER ENTFERNUNGSMESSUNG 9

Meßreichweite

für natürliche Ziele,ρ ≥ 80% bis zu 1000m

für natürliche Ziele,ρ ≥ 10% bis zu 350m

minimale Reichweite 2m

Genauigkeit1 10mm

Wiederholbarkeit 8mm (Einzelpunkt), 4mm (durchschnittlich)

Meßrate bis zu 12000 Pt/s (langsame Scanrate, oszillierender Spiegel)

bis zu 8000 Pt/s (hohe Scanrate, rotierender Spiegel)

Wellenlänge 1550nm

Strahldivergenz 0,25mrad

vertikale Scanlinie horizontale Scanlinie

Öffnungswinkel 0◦ bis 80◦ 0◦ bis 360◦

Scanmechanismus rotierender/ oszillierender Spiegel rotierender optischer Kopf

Scanrate 1 bis 20 Scans/s 0,01◦/s bis 15◦/s

bei 80◦ Öffnungswinkel

Schrittweite zwischen 0,004◦ ≤ ∆ϑ ≤0,2◦ 0,004◦≤ ∆ϕ ≤ 0,75◦

aufeinanderfolgenden Scans

Winkelauflösung 0,002◦ 0,0025◦

Tabelle 2.2: Spezifika des Laserscanner Riegl LMS-Z420i ([Rie06])

zusammenfassend ausdrücken durch

Pr = ρM2 · Ao

πd2Pt (2.9)

mit der Objektreflektanzρ, der ausgesendeten PulsenergiePt, der atmosphärischen TransmissionM und

der Entfernung zum Objektd ([HL09], S. 31).

Datensätze, die für die Arbeit zur Verfügung standen, sind mit dem Laserscanner Riegl LMS-Z420i

aufgenommen wurden. Dieses Modell kann durch Drehung des Scannerkopfes einen horizontalen Öff-

nungswinkel von 360◦ und durch rotierende Spiegel einen vertikalen Bereich von 80◦ erfassen. Der Laser

arbeitet mit einer Wellenlänge von 1550nm ([Kra07]). Dieser relativ starke Laser gilt trotz seiner Strah-

lung im kurzwelligen Infrarotbereich als augensicher, da diese Wellenlänge durch den Wassergehalt im

Auge absorbiert wird ([ST09], S. 21). In Tabelle 2.2 sind die Spezifikadieses Laserscanners aufgelistet.


2.2 Abbildung der Punktwolke auf Bildkoordinaten

Der Intensitätswert einer Distanzmessung ist der Bruchteil der Energie des ursprünglich ausgesendeten

Laserimpulses, die vom Objekt reflektiert wird und wieder im Laserscanner registriert wurde. Die In-

tensität bewegt sich im Intervall[0..1] und wird für die gemessenen Punkte mit den Polarkoordinaten

aufgezeichnet. Da die Schrittweiten∆φ und∆θ des Scans bekannt sind, können die Polarkoordinaten

(pφ, pθ) jedes Punktesp auf kartesische Bildkoordinaten(pu, pv) abgebildet werden.

pu = ⌊(pφ − φmin)/∆φ⌋ (2.10)

pv = ⌊(pθ − θmin)/∆θ⌋ (2.11)

Indem die Intensitätpi jedes Punktes als Grauwert eingesetzt wird, kann ein Intensitätsbild wie in Abbil-

dung 2.4(a) generiert werden. Durch die Verwendung der gemessenen Entfernungswerte als Grauwert,

kann auf dieselbe Weise ein Tiefenbild des Scans erzeugt werden. Einedirekte Darstellung des Tie-

fenbilds ist allerdings nicht sinnvoll, da das Intervall der Entfernungswerte die Anzahl an möglichen

Graustufen weit übersteigt.

Der Vorteil dieser Abbildung ist, dass jedem gemessenen Punkt ein Pixel zugewiesen wird und es somit

einen Überblick über den gesamten Scan gibt. Dabei wird aus Abbildung 2.4(a) ebenfalls deutlich, das

der Laserscanner die vorgegebenen Schrittweite nicht immer korrekt einhält und dadurch linienförmige

Lücken im Bild zu sehen sind. Gleichzeitig werden diese zu groß gewählten Abstände vom Scanner selbst

damit kompensiert, dass die Schrittweite zum nächsten Punkt reduziert wird. Diese Lücken sind für die

weitere Auswertung und Anschaulichkeit ungünstig. Eine einfache Möglichkeit die Lücken zu eliminie-

ren, ist die leichte Erhöhung der Schrittweiten∆φ und∆θ, die zur Bildgenerierung verwendet werden.

Jedoch werden dann vielen Pixel mehrere Punkte zugeordnet, wodurch sich außerdem die Auflösung

verringert. Eine andere Möglichkeit ist die Schließung der Lücken durch morphologische Operationen,

wie sie in Algorithmus 2.1 zusammengefasst sind. Die Lücken werden dabei geschlossen, indem das je-

weilige leere Pixel mit dem Mittelwert der Grauwerte der umliegenden Datenpunktnachbarschaft gefüllt

wird. Der Nachteil ist dabei wiederum, dass auch kleine Lücken, die keine Fehler darstellen sondern

z.B. durch Ornamente an Gittern herrühren, in Abhängigkeit von der Größe des verwendeten Struktur-

elements geschlossen werden.

Da dieses Bild die Punktwolke in Polarkoordinaten direkt auf Pixelkoordinaten abbildet, erscheinen Li-

nien, die vom Laserscanner wegführen, gekrümmt wie in Abbildung 2.4. Für einen direkten Vergleich

mit einem Foto desselben Objekts ist dies ungünstig, da die Grauwertnachbarschaft eines Pixels sich

dann nicht aufgrund der verschiedenen Beleuchtung sondern wegen der unterschiedlichen Geometrien

der Bilder vom Foto unterscheidet. Da Fotos für gewöhnlich in Zentralperspektive aufgenommen sind,

2.2. ABBILDUNG DER PUNKTWOLKE AUF BILDKOORDINATEN 11

(a) Polarkoordinaten abgebildet auf Bildkoordinaten

(b) Scanlücken durch morphologische Operationen geschlossen

Abbildung 2.4: Intensitätsbild des Palais vom Standpunkt 3 mit Bildverbesserung (siehe Abschnitt 2.4).


Voraussetzung: Bildmaskem(x, y) derselben Größe wie das Intensitätsbildi(x, y)

Ziel: Interpolation des Grauwerts für die Scanlücken durch die PixelnachbarschaftP

Algorithmus:

• Maskem(x, y) = 0 ∀ x, y ∈ [0..xmax], [0..ymax]

• ∀ p ∈ Punktwolke

m(⌊(pφ − φmin)/∆φ⌋ , ⌊(pθ − θmin)/∆θ⌋) = 1

• Opening-Operation mit einem 3×3-Strukturelements (Symbolnotation nach ([GW02], S. 528))

n′ = (¬m ⊖ s) ⊕ s)

• Logische Und-Verknüpfung der Negation der Maskenn′ undm

n = ¬n′ ∧ ¬m

• In der Masken sind nur die Scanlücken des Bildesi(x, y) mit 1 markiert

∀ n(x, y) = 0 mit der 8-PixelnachbarschaftP = {(px, py)}

– AnzahlN der benachbarten Pixel vonn(x, y), die einen 3D-Punkt repräsentieren

N =∑8

i=1 m(pix, pi

y)

– Interpolation des Grauwerts an der Stellei(x, y) durch den Mittelwert der Pixelnachbarschaft

i(x, y) =1

N·

8∑

i=1

m(pix, pi

y) · i(pix, pi

y)

Algorithmus 2.1: Lücken füllen mit morphologischen Operationen

2.3. ZENTRALPERSPEKTIVISCHE ABBILDUNG DER PUNKTWOLKE 13

wäre es wünschenswert auch die Punktwolke auf diese Art abzubilden, um ein Bild zu generieren, das

von der Aufnahmeart den Fotos entspricht und vorhandene Ähnlichkeiten maximal ausnutzen zu können.

2.3 Zentralperspektivische Abbildung der Punktwolke

Für jeden Punktp der Punktwolke sind die 3D-Koordinaten(px, py, pz), die Polarkoordinaten der Auf-

nahme(pφ, pθ, d) und die Intensitätpi gegeben. Um die Punkte zentralperspektivisch auf eine virtuelle

Bildebene zu projizieren, muss zunächst eine Viewing-TransformationV, d.h. eine Matrix, die die 3D-

Koordinaten der Punkte in das Kamerakoordinatensystem überführt, festgelegt werden. Die Blickrich-

tung~k

~k =~p min

φ∥

∥

∥~p min

φ

∥

∥

∥

+~p max

φ∥

∥

∥~p max

φ

∥

∥

∥

(2.12)

wird durch Addition der beiden normalisierten Vektoren zu den Punkten~p maxφ und ~p min

φ mit der ma-

ximalen und minimalenφ-Koordinate bestimmt. Dadurch zeigt~k in die Mitte der Punktwolke. Da die

Oben-Richtung eines Bildes dery-Achse entspricht, ergibt sich das Kamerakoordinatensystem, welches

im übergeordneten Koordinatensystem von den Vektoren~i,~j und~k

kz = 0 ~k =~k

∥

∥

∥

~k∥

∥

∥

(2.13)

~i = (0 1 0)T × ~k ~i =~i

∥

∥

∥

~i∥

∥

∥

(2.14)

~j = ~k ×~i ~j =~j

∥

∥

∥

~j∥

∥

∥

(2.15)

aufgespannt wird ([Com06], S. 257). Mit der Viewing-TransformationV

V =

~i ~j ~k ~0

0 0 0 0

T

(2.16)

und der Matrix für die perspektivische ProjektionP

P =

1 0 0 0

0 1 0 0

0 0 1 0

0 0 1/f 0

(2.17)

mit f als der Distanz zwischen Projektionszentrum und virtueller Bildebene, können allen Punkte der

Punktwolke in homogenen Koordinatenp = (px py pz pw = 1)T auf die Bildebene projiziert werden


([Com06], S. 274).

p = PVp =

1 0 0 0

0 1 0 0

0 0 1 0

0 0 1/f 0

·

ix iy iz 0

jx jy jz 0

kx ky kz 0

0 0 0 1

·

px

py

pz

pw

(2.18)

Die Koordinaten der Punktep′ auf der Bildebene erhält man durch Normalisierung der projizierten

Punktkoordinatenp mit pw

p′ =(

px py pz pw

)T· 1

pw=

(

p′x p′y1f 1

)T. (2.19)

Die Größe der virtuellen Bildebene wird durch die maximalen bzw. minimalen Koordinaten inx undy

der projizierten Punkte bestimmt

Bildbreite = ⌈(xmax − xmin)/∆p⌉ (2.20)

Bildhöhe = ⌈(ymax − ymin)/∆p⌉ (2.21)

mit

xmin = minx

p xmax = maxx

p (2.22)

ymin = miny

p ymax = maxy

p, (2.23)

wobei die Pixelgröße∆p oder die Bildgröße vorher festgelegt werden muss ([Com06], S. 276).Anschlie-

ßend können dann für die projizierten Punktwolke mit

xp =⌈

(p′x − xmin)/∆p

⌉

yp =⌈

(p′y − ymin)/∆p

⌉

(2.24)

Pixelkoordinaten berechnet werden. Da die Punktwolke in Polarkoordinaten aufgenommen wurde, führt

eine zentralperspektivische Projektion auf eine Bildebene, die parallel zur z-Achse des Aufnahmekoordi-

natensystems verläuft, zu einer inhomogenen Verteilung der projizierten Punkte. Abbildung 2.5 verdeut-

licht, dass im Zentrum der Bildebene ein Bereich mit hoher Punktdichte entsteht. Je größer der Winkel

zwischen der Blickachse und dem Vektor zu einem beliebigen Punktp wird, desto größer wird auch der

Abstand zwischenp zu seinem nächstgelegenen Punkt. Das heißt, der Abstand zwischen denPunkten

wird vom Zentrum ausgehend zu den Rändern immer größer. Die Darstellung und Weiterverarbeitung

als Bild macht eine diskrete Unterteilung der Projektionsebene in Pixel notwendig. Dafür muss eine Pi-

xelgröße gewählt werden. Wenn die Pixelgröße zu klein gewählt wird, ergibt sich zwar ein Bereich mit

hoher Auflösung im Zentrum, jedoch entstehen viele Lücken vom Zentrum zum Rand hin dort, wo der

Punktabstand die vorgegebene Pixelgröße übersteigt (Abbildung 2.5).Die Interpolation dieser Lücken

2.4. VERBESSERUNG DES INTENSITÄTSBILDES 15

Abbildung 2.5: Durch die Aufnahme der Punkte in Polarkoordinaten vom Laserscanner aus ist der Ab-

stand der projizierten Punkte auf der Bildebene nicht konstant.

ist allerdings ungünstig, da weit weniger Datenpunkte in diesen Bereichenvorhanden sind als leere Pixel

entstehen und es somit eine Verfälschung des Bildinhalts zur Folge hätte. Wird die Pixelgröße zu groß

festgelegt, entstehen folglich keine Lücken, aber ein Großteil der Punktinformation im höher aufgelösten

Bereich geht verloren, da jedes Pixel nur mit der Intensität eines Punktes als Grauwert eingefärbt wird.

Die Auflösung des entstehenden Bildes wird durch die maximale Auflösung, die am Rande möglich ist,

bestimmt. Wie groß die Abstände zwischen Punkten auf der Projektionsebenewerden, hängt direkt vom

Winkel α zwischen den Punkten mit der minimalen und maximalen Winkelnpφ ab. Wenn der Winkelα

klein ist, decken die Punkte auf der Projektionsebene einen kleinen Bereich ab, wodurch sich die Auflö-

sung im Zentrum durch die Wahl einer geeignet kleinen Pixelgröße teilweise erhalten lässt. Der maximal

mögliche Winkel für eine Projektion ist folglich 180◦. Der Laserscanner Riegl LMS-Z420i ist zu einem

Öffnungswinkel von bis zu 360◦ bei einem Scan in der Lage. Daher ist es sinnvoll, die resultieren-

de Punktwolke abschnittsweise zu projizieren. Man erhält mehrere Teilbilder mit einem vorgegebenem

Öffnungswinkel von z.B. 45◦, die folglich eine höhere Auflösung ermöglichen als die Projektion der

gesamten Punktwolke in ein Bild.

2.4 Verbesserung des Intensitätsbildes

Das entstandene Intensitätsbild ist aufgrund der schwachen Laserreflektion, die von den meisten Ober-

flächen zurück kommt, sehr dunkel und weist nur geringe Kontraste auf(vgl. Abbildung 5.1 in Abschnitt


(a) Abbildung der Polarkoordinaten (b) Zentralperspektivische Projektion

Abbildung 2.6: Vergleich der zwei Abbildungsmöglichkeiten

5.1). Für die weitere Verwendung wäre eine Verbesserung des Bildes mitBildverarbeitungsmethoden

daher wünschenswert. In der folgenden Tabelle 2.3 sind die Verbesserungsoperationen aufgelistet, die

sukzessive auf das Intensitätsbild angewendet wurden, um es visuellzu verbessern. Die Grauwerte des

Eingangsbildes müssen so abgebildet werden, dass die Gradientenbeträge verstärkt werden, aber die Ori-

entierung möglichst erhalten bleibt. Dafür müssen die Parameter der Funktionen entsprechend gewählt

werden. Da die Intensität den Grauwert für jedes Pixel darstellt, sind dieWerte schon auf das Intervall

[0..1] normiert.

2.4. VERBESSERUNG DES INTENSITÄTSBILDES 17

Helligkeitsänderung1 mit h ∈ [−1..0..1] Kontraständerung1 mit c ∈ [−1..0..1]

i(x, y) =

i(x, y) · (1 + h) h < 0

i(x, y) + (1 − i(x, y)) · h h ≥ 0i(x, y) = (i(x, y) − 0, 5) · tan ((c + 1) · π

4) + 0, 5

0 0.2 0.4 0.6 0.8 10

0.2

0.4

0.6

0.8

1

h = 0

Eingangsgrauwerte

Aus

gang

sgra

uwer

te

h = 0,3

h = −0,5

0 0.2 0.4 0.6 0.8 10

0.2

0.4

0.6

0.8

1

Eingangsgrauwerte

Aus

gang

sgra

uwer

te

c = 0,5

c = 0

c = −0,5

Gammakorrektur Histogrammdehung

mit γ > 0 mit gweiss, gschwarz ∈ [0..1]

i(x, y) = i(x, y)γ i(x, y) =i(x, y) − gschwarz

gweiss − gschwarz

0 0.2 0.4 0.6 0.8 10

0.2

0.4

0.6

0.8

1

Eingangsgrauwerte

Aus

gang

sgra

uwer

te

γ = 0,3

γ = 3,5

γ = 1

0 0.2 0.4 0.6 0.8 10

0.2

0.4

0.6

0.8

1

Eingangsgrauwerte

Aus

gang

sgra

uwer

te

gschwarz

= 0,0g

weiß = 0,6

gschwarz

= 0,0g

weiß = 1,0

gschwarz

= 0,4g

weiß = 1,0

Tabelle 2.3: Verbesserungsoperationen für das Intensitätsbildi(x, y).

1 Die Formeln für die Helligkeits- und Kontraständerung wurden aus [Gim] entnommen.


19

3 Relative Orientierung eines Bildes

Die Texturierung einer Laserscannerpunktwolke mit Farbinformationen eines Fotos erfordert die Kennt-

nis der relativen Orientierung des Fotos im Koordinatensystem der Punktwolke. Die relative Orientierung

bezeichnet Parameter eines geeigneten Abbildungsmodells mit dem die ursprüngliche Aufnahmesitua-

tion wiederhergestellt werden kann. In diesem Kapitel werden die Parameter, die die relative Orientie-

rung ausmachen, erläutert und auf ihre Berechnung mit der Direkten Linearen Transformation und der

Kleinste-Quadrate-Ausgleichung eingegangen. Schließlich werden die Ergebnisse der Orientierung von

Fotos des Palais im Großen Garten und die anschließende Texturierung der zugehörigen Laserscanner-

punktwolke diskutiert.

3.1 Parameter der relativen Orientierung

Das Abbildungsmodell gewöhnlicher Fotos ist die Zentralperspektive. DieBeziehung zwischen einem

3D-PunktP und den entsprechenden Bildkoordinatenp kann dabei durch die Kollinearitätsgleichungen

px = x0 − ckr11(Px − X0) + r21(Py − Y0) + r31(Pz − Z0)

r13(Px − X0) + r23(Py − Y0) + r33(Pz − Z0)(3.1)

py = y0 − ckr12(Px − X0) + r22(Py − Y0) + r32(Pz − Z0)

r13(Px − X0) + r23(Py − Y0) + r33(Pz − Z0)(3.2)

beschrieben werden [Luh00]260. Die Parameter der Kollinearitätsgleichung werden in Parameter der

äußeren und inneren Orientierung unterschieden. Die äußere Orientierung umfasst die Parameter, die

die räumliche Lage und Position des Kamerakoordinatensystems im übergeordneten Koordinatensystem

angeben, in welchem auch die 3D-Punkte gegeben sind. Dazu gehörendie Koordinaten des Projektions-

zentrumsO = (X0, Y0, Z0), das den Ursprung des Kamerakoordinatensystems bildet. Die Drehung des

Kamerakoordinatensystems wird durch die RotationsmatrixR bzw. den Drehwinkeln(φ, κ, ω) angege-

ben.

R =

r11 r12 r13

r21 r22 r23

r31 r32 r33

(3.3)

Die innere Orientierung, bestehend aus der Kamerakonstanteck und dem BildhauptpunktH = (x0, y0),

bestimmt die Lage der Bildebene im Kamerakoordinatensystem. Der Bildhauptpunkt H ist der Durch-

20 3. RELATIVE ORIENTIERUNG EINES BILDES

Abbildung 3.1: Parameter der inneren und äußeren Orientierung

stoßpunkt der negativen z-Achse durch die orthogonal dazu stehende Bildebene. Die Kamerakonstante

ck gibt den Abstand zwischen dem Projektionszentrum und dem Bildhauptpunkt an. In Abbildung 3.1

werden die Orientierungsparameter schematisch verdeutlicht.

In der praktischen Anwendung reichen die Kollinearitätsgleichungen jedoch nicht aus, um die Abbil-

dungsbeziehung zwischen 3D-Punkt und Bildkoordinaten vollständig zubeschreiben. Ein Kameraob-

jektiv besteht aus einem beweglichen Linsensystem, das verschiedene Vergrößerungen ermöglicht. Wenn

die optischen Achsen nicht präzise zusammenfallen, bewirkt dies eine Abweichung vom idealen Modell,

so dass ein Bildpunktp um ∆r von seinen eigentlichen Koordinaten versetzt wird ([Luh00], S. 113).

Diese Abweichung wird als radial-symmetrische Verzeichnung∆xrad

p′x = px − x0 (3.4)

p′y = py − y0 (3.5)

r =√

p′2x + p′2

y (3.6)

r0 =2

3·√

(0, 5 · Bildbreite)2 + (0, 5 · Bildhöhe)2 (3.7)

∆xrad = A1 · r(r2 − r20) + A2 · r(r4 − r4

0) + A3 · r(r6 − r60) (3.8)

bezeichnet und kann durch eine Korrekturfunktion, die dem Abbildungsmodell hinzugefügt wird, wei-

testgehend kompensiert werden. Die möglicherweise leicht dezentrale Anordnung der Linsen im Objek-

tiv verursacht eine radial-asymmetrische und tangentiale Verzeichnung∆xtan und∆ytan

∆xtan = B1 · (r2 + 2p′2x ) + 2B2 · p′x · p′y (3.9)

∆ytan = B2 · (r2 + 2p′2y ) + 2B1 · p′x · p′y. (3.10)

3.2. DIREKTE LINEARE TRANSFORMATION 21

Sind die Bildachsen nicht orthogonal zueinander ausgerichtet und weisen unterschiedliche Maßstäbe auf,

so lässt sich dies als∆xaff bzw.∆yaff

∆xaff = C1 · p′x + C2 · p′y (3.11)

∆yaff = 0 (3.12)

ebenfalls repräsentieren. Die Gesamtkorrektur dieser nicht-linearen Abweichungen wird schließlich durch

Summierung der Teilkorrekturen

px = p′x + p′x · ∆xrad

r+ ∆xtan + ∆xaff (3.13)

py = p′y + p′y ·∆xrad

r+ ∆ytan + ∆yaff (3.14)

an den Bildkoordinaten angebracht. Die Korrekturfunktionen der Abweichungen sind Teil der inneren

Orientierung, die zusammen mit der äußeren Orientierung die relative Orientierung des Fotos im über-

geordneten Koordinatensystem beschreibt.

Die Voraussetzung um die Parameter der relativen Orientierung bestimmen zukönnen, sind bekannte

Korrespondenzen zwischen 3D-Punkten und deren Bildkoordinaten imFoto. Mit einer Kleinste-Quadrate-

Ausgleichung kann eine hohe Genauigkeit bei der Bestimmung der Parameter erreicht werden, sofern die

Koordinaten exakt gemessen wurden und Näherungswerte für die zu bestimmenden unbekannten Para-

meter gegeben sind. Das heißt, es müssen zunächst Näherungswerte beschafft werden, deren Qualität das

Ergebnis der Ausgleichung signifikant beeinflusst. Um Näherungswerte zu bestimmen, wird die Direkte

Lineare Transformation (DLT) verwendet. Anschließend wird auf die Kleinste-Quadrate-Ausgleichung

eingegangen.

3.2 Direkte Lineare Transformation

Die Direkte Lineare Transformation (DLT) modelliert einen linearen Zusammenhang der 3D- und Bild-

koordinaten und ist aus diesem Grund für die alleinige Bestimmung der Orientierungsparameter zu un-

genau. Allerdings bietet sie eine Möglichkeit, Näherungswerte für die unbekannten Parameter aus den

Punktkorrespondenzen zu bestimmen.

Die Kollinearitätsgleichungen (3.1) werden dafür um eine Affintransformation der Bildkoordinaten er-

weitert ([AW09], S. 209) und umgeschrieben

px =L1Px + L2Py + L3Pz + L4

L9Px + L10Py + L11Pz + 1(3.15)

py =L5Px + L6Py + L7Pz + L8

L9Px + L10Py + L11Pz + 1, (3.16)


wobei die unbekannten Parameter zusammengefasst und durchLi ersetzt werden. Durch Umstellung

dieser Gleichung erhält man für jede Punktkorrespondenz folgende lineare Beziehung

− L1Px − L2PY − L3Pz − L4 + pxL9Px + pxL10Py + pxL11Pz + px = 0 (3.17)

−L5Px − L6PY − L7Pz − L4 + pyL9Px + pyL10Py + pyL11Pz + py = 0. (3.18)

Die Stapelung dieser Gleichungen für allen Punktkorrespondenzen und Darstellung in Matrizenschreib-

weise

Al =

−PT 0T pxPT

0T −PT pyPT

·

L1

...

L11

= 0 (3.19)

ergibt eine2n × 9-Matrix A und einen12 × 1-Vektor l, der die ParameterLi umfasst. Für eine exak-

te Lösung vonl sind mindestens 6 Punktkorrespondenzen notwendig. Werden mehr als 6 verwendet,

ist die Lösung überbestimmt. Der Lösungsvektorl kann durch eine Singulärwertzerlegung vonA be-

stimmt werden. Dabei entsprichtl dem Rechtssingulärvektor vonA (vgl. [BSMM01], S. 295), der zum

kleinsten Singulärwert gehört ([HZ03], S. 91). Das heißt, bei einer Zerlegung inA = UDVT , wobei

D eine Diagonalmatrix mit positiven, absteigend geordneten Elementen ist, erhältmanl als den letzten

Spaltenvektor vonV. Die Werte der gesuchten Parameter der inneren und äußeren Orientierung können

anschließend aus denLi berechnet werden. Die Koordinaten für den BildhauptpunktH = (x0, y0) erhält

man mit

x0 = L2 · (L1 · L9 + L2 · L10 + L3 · L11) (3.20)

y0 = L2 · (L5 · L9 + L6 · L10 + L7 · L11), (3.21)

wobeiL =−1

√

L29 + L2

10 + L211

ist. Die Kamerakonstante nachx- und y-Richtung skaliert, ergibt sich

aus

ckx =√

L2 · (L21 + L2

2 + L23) − x2

0 (3.22)

cky =√

L2 · (L25 + L2

6 + L27) − y2

0. (3.23)

Die Koordinaten des ProjektionszentrumsO kann man über

O =

X0

Y0

Z0

= −

L1 L2 L3

L5 L6 L7

L9 L10 L11

−1

·

L4

L8

1

(3.24)

3.3. KLEINSTE-QUADRATE-AUSGLEICHUNG 23

bestimmen. Außerdem sind die Elemente der RotationsmatrixR

r11 =L · (x0 · L9 − L1)

ckxr12 =

L · (y0 · L9 − L5)

ckyr13 = L (3.25)

r21 =L · (x0 · L10 − L2)

ckxr22 =

L · (y0 · L10 − L6)

ckyr23 = L (3.26)

r31 =L · (x0 · L11 − L3)

ckxr32 =

L · (y0 · L11 − L7)

ckyr33 = L (3.27)

gegeben.

3.3 Kleinste-Quadrate-Ausgleichung

Die Werte, die mit der Direkten Linearen Transformation für die unbekannten Parameter bestimmt wur-

den, werden nun iterativ im Rahmen einer Kleinste-Quadrate-Ausgleichung durch die gegebenen Punkt-

korrespondenzen optimiert. Die Kleinste-Quadrate-Ausgleichung stellt einen Algorithmus zur Lösung

von Problemen mit Überbestimmung dar. Das Ergebnis erfüllt dabei bestimmte Optimalitätskriterien und

lässt außerdem eine qualitative Bewertung zu ([Nie08], S. 112). Die Ausgleichung kann nach ([Luh00],

S. 53ff,260ff) wie folgt ausgeführt werden.

Die unbekannten Parameter der relativen Orientierung, für die genaue Werte bestimmt werden sollen und

man zunächst die vorher bestimmten Näherungswerte einsetzt, werden zumParametervektorX

X = (X0 Y0 Z0 e1 e2 e3 x0 y0 ck A1 A2 A3 B1 B2 C1 C2)T (3.28)

Die Parametere1, e2, e3 sind Quaternionelemente, die die RotationsmatrixR in kompakter Form dar-

stellen. Da ein Rotationsquaternion die Einheitsnorm erfüllen muss [Wei], kann das vierte Quaternion-

elemente0 aus den übrigen bestimmt werden

e0 =√

1 − e21 − e2

2 − e23. (3.29)

Die Elemente der RotationsmatrixR ergeben sich aus dem Quaternion mit folgenden Formeln

R =

r11 r12 r13

r21 r22 r23

r31 r32 r33

=

e20 + e2

1 − e22 − e2

3 2(e1e2 − e0e3) 2(e1e3 + e0e2)

2(e1e2 + e0e3) e20 − e2

1 + e22 − e2

3 2(e2e3 − e0e3)

2(e1e3 − e0e2) 2(e2e3 + e0e3) e20 − e2

1 − e22 + e2

3

. (3.30)

Der sogennante BeobachtungsvektorL enthält die Bildkoordinatenpi für allen Punktkorrespondenzen

L = (px1 py

1 px2 py

2 . . . pxn py

n)T

, (3.31)

wobei jede Koordinate ein Vektorelement ausmacht. Die FunktionΦxi (X) bzw.Φy

i (X) erhält den Para-

metervektorX als Argument und bestimmt mittels der erweiterten Kollinearitätsgleichungen (3.13)für


den 3D-PunktPi die zugehörige Bildkoordinatep′x bzw.p′y. Die Zusammenfassung allerϕxi undϕy

i als

Funktionenvektor der unbekannten Parameter

ϕ(X) = [ϕx1(X) ϕy

1(X) ϕx2(X) ϕy

2(X) . . . ϕxn(X) ϕy

n(X)]T (3.32)

ergibt das funktionale Modellϕ(X). Das funktionale Modellϕ berechnet die BildkoordinatenL der

3D-PunktePi

L = ϕ(X) (3.33)

mit den gegebenen Werten des ParametervektorsX. Mit den Näherungswerten für die unbekannten Pa-

rameter inX0 erhält man zunächst den BeobachtungsvektorL0

L0 = ϕ(X0), (3.34)

welcher von dem Vektor der gegebenen Beobachtungen abgezogen wird. Es ergibt sich der Differenz-

vektorl

l = L − L0. (3.35)

Die gesuchten, wahren ParameterwerteX

X = X0 + x (3.36)

werden als NäherungswerteX0, zu denen nur noch kleine Beträgex hinzugefügt werden müssen, ange-

nommen. Gleichermaßen ergeben sich die wahren BeobachtungenL

L = L + v (3.37)

aus den gegebenen BeobachtungenL und kleinen Verbesserungenv. Die Verbesserungenv können an

den Näherungswerten durch eine Reihenentwicklung nach Taylor

L + v = φ(

X0)

+

(

∂φ(X)

∂X

)

0

·(

X − X0)

= L0 +

(

∂φ(X)

∂X

)

0

· x (3.38)

bestimmt werden, die nach den linearen Termen abgebrochen wird. DurchUmformung erhält man

L − L0 + v =

(

∂φ(X)

∂X

)

0

· x (3.39)

l + v = Ax (3.40)

wobei die2n × u-Matrix A mit den Ableitungen des funktionalen Modells nach allenu Parametern für

jede der2n Bildkoordinaten inL aufgestellt wird.

A =

(

∂ϕ(X)

∂X

)

0

=

(

∂ϕx

1(X)

∂X1

)

0

(

∂ϕx

1(X)

∂X2

)

0. . .

(

∂ϕx

1(X)

∂Xn

)

0(

∂ϕy

1(X)

∂X1

)

0

(

∂ϕy

1(X)

∂X2

)

0. . .

(

∂ϕy

1(X)

∂Xn

)

0...

. . ....

(

∂ϕxn(X)

∂X1

)

0

(

∂ϕxn(X)

∂X2

)

0. . .

(

∂ϕxn(X)

∂Xn

)

0(

∂ϕy

n(X)∂X1

)

0

(

∂ϕy

n(X)∂X2

)

0. . .

(

∂ϕy

n(X)∂Xn

)

0

(3.41)

3.4. ERGEBNISSE DER ORIENTIERUNG UND TEXTURIERUNG 25

Indem der Differenzvektorl in Gleichung (3.40) auf die rechte Seite gestellt und die Verbesserungen zu

Null gesetzt werden

0 = Ax − l, (3.42)

erhält man ein lineares Gleichungssystem. Sofern das MatrixproduktATA invertierbar ist, lässt sich die

Lösung für die Parameterzuschlägex durch Umformung über die Pseudoinverse vonATA

0 = ATAx − ATl (3.43)

x = (ATA)−1ATl (3.44)

ermitteln. Durch Addition des Vektorx zum ParametervektorX0 erhält man nach (3.36) die korrigierten

Parameterwerte. Anschließend lassen sich die Verbesserungen bzw. Residuen der Bildkoordinaten mit

v = Ax − l (3.45)

bestimmen. Ein wichtiges Kriterium für die Bewertung des Ergebnisses ist die Standardabweichungσ0

a posteriori

σ0 =

√

vTv

n − u. (3.46)

Sie gibt den verbleibenden Gesamtfehler der Berechnung und damit die erzielte Genauigkeit der Lösung

relativ zu den gegebenen Eingabedaten an.

Da das funktionale Modellϕ eine nicht-lineare Aufgabe darstellt und das Gleichungssystem umr =

n − u Zeilen überbestimmt ist, werden weitere Iterationen benötigt um die Parameterwerte ausreichend

zu verbessern. Dafür werden die korrigierten Parameterwerte als neue Näherungswerte verwendet. Die

Berechnung terminiert, wenn die Summe der Zuschlägex oder der größte Wert vonx einen festgelegten

Grenzwert unterschreitet. Ein weiteres Abbruchkriterium besteht in dermaximal zulässigen Anzahl an

Iterationen, das in dem Fall relevant ist, wenn die Berechnung nicht konvergiert. Das Konvergenzverhal-

ten der Kleinsten-Quadrate-Ausgleichung ist wesentlich von den Eingabewerten abhängig. Abgesehen

von guten Näherungswerten, müssen auch die Punktkorrespondenzen gewissen Bedingungen, wie einer

ausreichenden Messgenauigkeit und günstiger Verteilung, genügen.Ausreißer in den Bildkoordinaten

bzw. den 3D-Punkten können durch markant große Werte im Verbesserungsvektorv erkannt werden.

Die Konvergenz der Berechnung ist jedoch auch bei ausreichend guten Eingabedaten nicht mit Sicher-

heit gegeben.

3.4 Ergebnisse der Orientierung und Texturierung

Die relative Orientierung der Fotos des Palaisdatensatzes wurde mit der Kleinsten-Quadrate-Ausgleichung

berechnet. Dafür wurden manuell Bildkoordinaten von markanten Punkten in den Fotos gemessen. Die


σ0 x0 y0 ck A1 A2

0,000326 0,1825 0,04771 28,8696 -0,0000859 0,000000154

A3 B1 B2 C1 C2

0,0 9,13033e-6 1,61852e-6 -0,00688217 8,36519e-5

Tabelle 3.1: Kalibrierungsdaten der Nikon D100 mitr0 = 8, 85 für die Fotos des Palais

3D-Koordinaten dieser Punkte wurden bestimmt, indem entsprechende 3D-Punkte in der Laserscanner-

punktwolke ausgewählt wurden.

Da die Kamerakonstante ohnehin näherungsweise von dem verwendetenObjektiv bekannt war, wurde

der Näherungswert direkt mit 28mm vorgegeben. Die Berechnung eines Näherungswertes über die in

Abschnitt 3.2 erläuterte DLT wäre aber genauso möglich gewesen. Die Fotos zu Standpunkt 3 und 4

des Palaisdatensatzes konnten erst nach Transformation der 3D-Punkte in das Laserscannerkoordina-

tensystem von Standpunkt 2 erfolgreich orientiert werden. In Tabelle 3.2 sind die Ergebnisse der Ori-

entierungsberechnung der Fotos angegeben. Zum Vergleich sind die Kalibrierungsdaten der Kamera in

Tabelle 3.1 aufgeführt.

Die Standardabweichungσ0 a posteriori ist für alle Fotos wesentlich schlechter als das Ergebnis der

Kalibrierung. Der Wert, der für die Kamerakonstante bestimmt wurde, weicht bis zu 1mm vom Kali-

brierungswert ab. Dementsprechend weisen auch die anderen Parameterwerte große Differenzen zu den

Vergleichswerten der Kalibrierung auf.

Die größten Fehlerquellen, die das Ergebnis der Orientierung beeinflussen, sind die manuelle Messung

der Bildkoordinaten und die Auswahl der 3D-Punkte. Wie stark sich die Laserscannergenauigkeit aus-

wirkt, konnte allerdings nicht festgestellt werden, da keine Passpunktinformationen für das Palais zur

Verfügung standen. Die Orientierung der Fotos des Schillergartens undder Kommode, für die Passpunk-

te vorhanden waren, schlug allerdings fehl, da die Ausgleichung nicht konvergierte.

Anhand der bestimmten Orientierungsparameter wurde die Punktwolke anschließend mit den Fotos tex-

turiert. Dafür wurde innerhalb des CGVFrameworks ein Werkzeug in C++implementiert, das die Punkt-

wolke farbig visualisiert. In Abbildung 3.2 sind einige Beispiele dargestellt, diemit dem Visualisierungs-

werkzeug entstanden sind. Die Punkte der Laserscannerpunkwolke wurden mit den Formeln (3.1), (3.2)

und (3.13), (3.14) in das Foto projiziert und mit dem Farbwert koloriert, der sich an dieser Pixelposi-

tion befand. Die Punkte, die außerhalb des Fotobereichs projiziert wurden, sind farblos bzw. schwarz

dargestellt, wie zum Beispiel in Abbildung 3.2(a) und 3.2(d).


Foto σ0 x0 y0 ck A1 A2

DSC_0019 0,0172 0,2060 0,1897 28,8706 -0,000136 0,000001

DSC_0020 0,0165 0,2052 0,2529 28,8703 -0,000129 0,000000

DSC_0021 0,0181 -0,0254 -0,0205 28,5757 -0,000162 0,000001

DSC_0080 0,0194 0,2902 0,0867 28,8419 -0,000043 0,000000

DSC_0082 0,0189 0,0263 -0,0018 28,7507 -0,000091 0,000000

DSC_0086 0,0260 -0,2245 -0,2420 28,2957 -0,000236 0,000001

DSC_0162 0,0152 0,2958 0,0905 28,8891 -0,000170 0,000001

DSC_0027 0,0287 0,5863 0,2518 28,9580 -0,000090 0,000000

DSC_0030 0,0253 0,1550 0,7810 28,5360 -0,000192 0,000001

DSC_0031 0,0211 -0,0791 0,4473 28,4070 -0,000175 0,000001

DSC_0096 0,0251 -0,0439 0,4006 28,4180 -0,000061 0,000000

DSC_0097 0,0234 0,8722 1,1510 29,9240 -0,000233 0,000001

DSC_0104 0,0253 0,4462 0,7217 28,8050 -0,000123 0,000001

DSC_0039 0,0212 -0,1186 0,1698 29,2150 -0,000089 0,000000

DSC_0040 0,0171 -0,2993 0,3811 29,3560 -0,000115 0,000000

DSC_0112 0,0225 -0,1890 0,1372 29,1860 -0,000092 0,000000

DSC_0114 0,0218 -0,3322 0,3134 29,2940 -0,000137 0,000001

DSC_0188 0,0213 0,0023 0,1594 29,0500 -0,000070 0,000000

Tabelle 3.2: Ergebnisse der Orientierungsberechnung für den Palaisdatensatz mitr0 = 9, 4669


In Anbetracht des relativ schlechten Ergebnisses der Orientierungsberechnung, ergibt sich damit den-

noch eine gute Texturierung der Punktwolke. Die bestimmten Orientierungsparameter reichen aus, um

ein ansprechendes visuelles Ergebnis zu erzielen. Für eine Texturierung zur Visualisierung eines Gebäu-

demodells würde eine Orientierung auf Basis der Laserscannerdaten folglich genügen.


(a) 2. Standpunkt mit DSC_0082

(b) 2. Standpunkt mit DSC_0020

(c) 3. Standpunkt mit DSC_0030

(d) 4. Standpunkt mit DSC_0114

Abbildung 3.2: Texturierung der Punktwolke des Palais mit orientierten Fotos


31

4 Detektion und Zuordnung von Merkmalen

Für die relative Orientierung von Bildern zu einem übergeordneten Koordinatensystem sind bekannte

Korrespondenzen zwischen 3D-Punkten im Koordinatensystem und deren Bildkoordinaten eine notwen-

dige Voraussetzung. Allerdings ist die Zuordnung von 3D- zu 2D-Merkmalen wesentlich aufwendiger

als eine 2D-2D-Zuordnung, da der Suchraum um eine Dimension größerist. Die Aufstellung von Kor-

respondenzen zwischen einem Foto und einer Punktwolke über die Bestimmung von 2D-Zuordnungen

zwischen dem Foto und dem Intensitätsbild, für das die 3D-Koordinaten aus der Punktwolke zu jedem

Pixel bekannt sind, wäre daher wünschenswert.

In diesem Kapitel werden die Detektion und Zuordnung von Merkmalspunkten vorgestellt, sowie die An-

forderungen an einen geeigneten Merkmalsdetektor diskutiert. Anschließend wird die Merkmalsextrak-

tion mittels SIFT (Scale Invariant Feature Transform) erläutert, die für die Merkmalsextraktion gewählt

wurde.

4.1 Eigenschaften merkmalsbasierter Detektion und Zuordnung

Die Ansätze zur Merkmalsextraktion werden in merkmals- und flächenbasierte Detektoren unterschie-

den. Bei flächenbasierten Detektoren wird in einem Schritt detektiert undzugeordnet. Die Kreuzkorrela-

tion ist der bekannteste Vertreter dieser Kategorie. Dabei wird in beiden Bildern ein Fenster bestimmter

Größe betrachtet, wobei es in einem Bild fest positioniert ist und im anderen über alle möglichen Po-

sitionen geschoben wird. Das feste Fenster gibt über die enthaltene Grauwertverteilung das zu suchen-

de Bildmuster an. Es wird versucht mit dem beweglichen Fenster eine Positionzu finden, die diesem

Grauwertmuster entspricht. Der direkte Vergleich der Grauwerte zwischen den Bildern reduziert die An-

wendung der flächenbasierten Merkmalsdetektoren allerdings auf Translationen und kleine Rotationen

der Bildszene [ZF03]. Komplexere Transformationen und Skalierungsunterschiede können mit diesem

Ansatz nicht bewältigt werden. Außerdem arbeiten sie direkt auf den Grauwerten, weshalb sie für den

Vergleich von Bilder mit großen Beleuchtungsunterschieden nicht geeignet sind.

Aus diesem Grund wird im Folgenden nur die vielseitigere Detektion und Zuordnung von Merkmal-

spunkten betrachtet. Um Punktkorrespondenzen zwischen dem BildA undB zu erstellen, müssen zu-

32 4. DETEKTION UND ZUORDNUNG VON MERKMALEN

nächst die Merkmalspunkte separat in jedem Bild detektiert werden. Ein Merkmal ist nach [TM07] ein

lokales Bildmuster, welches sich von seiner direkten Nachbarschaft unterscheidet. Die gefundenen Merk-

male stellen dabei nicht unbedingt einen bedeutungsvollen Objektteil dar. Die direkte Interpretierbarkeit

der Merkmale wäre zwar wünschenswert, würde aber im Allgemeinen eine umfangreiche semantische

Interpretation der Bildszene erfordern. So ergibt sich für die beiden Bilder jeweils eine meist unterschied-

lich große Menge an Merkmalspunkten. Um die einzelnen Merkmalspunkte der Bilder zuzuordnen, wird

eine Metrik benötigt, mit der die Ähnlichkeit zweier Merkmalspunkte bestimmt werden kann. Zu diesem

Zweck werden die Merkmalspunkte durch Deskriptoren repräsentiert. Damit erhält man für die Bilder

A undB die zwei DeskriptormengenDA undDB. Meist kann mit dem Euklidischen Abstand oder der

Mahalonobis-Distanz die Ähnlichkeit zwischen zwei Deskriptoren bestimmt werden. Dementsprechend

werden die Punktkorrespondenzen zwischenA undB hergestellt, indem die Deskriptorpaare(dA,dB)

mit den geringsten Abständen aus den DeskriptormengenDA undDB gesucht werden. Das heißt, die

korrespondierenden Merkmalspunkte ausDA undDB sind nach der verwendeten Metrik nächste Nach-

barn im Deskriptorraum.

Ein idealer Detektor sollte nach [TM07] folgende Charakteristiken aufweisen: Die wichtigste Fähigkeit

des Detektors ist, ob er in der Lage ist dieselben Punkte in Bildern wiederzufinden, die dieselbe Szene

darstellen, aber unter verschiedenen Aufnahmesituationen entstanden sind. Dies setzt voraus, das der De-

tektor entweder invariant gegenüber bestimmten Bildtransformationen konzipiert oder unempfindlicher

dagegen gestaltet wird. Je robuster der Detektor ist, desto weniger genau können allerdings die Merk-

malspunkte lokalisiert werden. Gleichzeitig soll der Detektor natürlich an solchen Bildstellen Punkte

extrahieren, wo das unterliegende Bildmuster besonders charakteristisch und abwechslungsreich ist. Je

differenzierter ein Merkmalspunkt im Vergleich zu seiner Umgebung ist, desto höher ist die Wahrschein-

lichkeit, dass er auch in einem anderen Bild derselben Szene wieder detektiert wird.

Die Merkmale sollten exakt positioniert sein, aber nur eine begrenzte lokaleAusdehnung haben, um

die Verdeckungswahrscheinlichkeit zu reduzieren. Dadurch sind auch Approximationen der geo- und

photometrischen Deformationen durch einfache Modelle besser möglich. Bei genauer Lokalisation des

Merkmals wird die Umgebung allerdings sehr klein und damit die Bildinformation, die das Merkmal

charakterisiert ebenfalls weniger. Das erschwert wiederum die Zuordnung, da die Merkmale aufgrund

der kleinen Umgebung auch weniger differenziert beschrieben werden können.

Die Dichte der Merkmalspunkte sollte den Informationsgehalt des Bildes reflektieren und eine kom-

pakte Bildrepräsentation ermöglichen. Idealerweise sollte die Menge an Merkmalspunkten über einen

Grenzwert reguliert werden können, so dass sich die Anzahl an detektierten Merkmalspunkten je nach

Anwendung einstellen lässt. Und schließlich sollte die Detektion von Merkmalen ineinem Bild effi-

4.2. ANFORDERUNGEN AN DEN MERKMALSDETEKTOR 33

zient gehalten sein, um eine möglichst vielseitige Anwendung zu gewährleisten. Natürlich können die

gewünschten Eigenschaften nicht alle in gleichem Maße von einem einzigenDetektor erfüllt werden.

Ähnliche Anforderungen müssen auch für den Deskriptor gelten. Er sollte die charakteristischen Eigen-

schaften des Merkmalspunktes bzw. seiner Umgebung akkurat wiedergeben und gleichzeitig Beleuchtungs-

und Orientierungsänderungen tolerieren können. Zusätzlich sollte das Distanzmaß ebenfalls effizient zu

berechnen sein.

4.2 Anforderungen an den Merkmalsdetektor

Die Menge an Merkmalsdetektoren ist genauso vielfältig wie die der möglichen Deskriptoren, mit denen

man die Merkmalspunkte repräsentieren kann. Ein ausführlicher Überblick wird in [TM07] gegeben.

Die Detektoren lassen sich z.B. nach der extrahierten Form des Merkmals weiter in Punkt-, Regionen-,

Blob- und Liniendetektoren unterteilen. Eine allgemeine Theorie, nach der immer die besten Merkmale

aus den gegebenen Bildern für eine Anwendung extrahiert werden können, gibt es allerdings bisher nicht

[TM07]. Für eine konkrete Anwendung muss sowohl der Detektor als auch der Deskriptor passend zu

gegebenen Bilddaten gewählt werden.

Der größte Unterschied zwischen den hier betrachteten den Fotos und Intensitätsbildern besteht in der

Auflösung. Die Intensitätsbilder haben maximal die halbe Größe der Fotos. Eine notwendige Vorausset-

zung für die erfolgreiche Zuordnung ist demnach ein skaleninvarianterDetektor. Dieser zeichnet sich

dadurch aus, dass über verschiedene Auflösungsstufen desselben Bildes Merkmale gesucht werden, um

sie in ihrer charakteristischen Größe detektieren zu können. Dadurch ist die Wahrscheinlichkeit groß,

dass dasselbe Merkmal in einem anderen Bild derselben Szene in einer der Auflösungsstufen ebenfalls

detektiert wird.

Die Beleuchtungsunterschiede zwischen den beiden Bildklassen stellen ebenfalls wichtige Anforderun-

gen an den Merkmalsdetektor. Da die Fotos mit einem passiven Verfahrenim sichtbaren Bereich des

Lichts aufgenommen wurden, während das Intensitätsbild durch aktive Messung im Nahinfrarotbereich

entstanden ist, ergeben sich deutliche visuelle Unterschiede zwischen denBildern. Das Intensitätsbild

hat mit den als Graustufen interpretierten Intensitätswerten nur einen Kanal, in dem Merkmale extrahiert

werden können. Das Foto muss in Graustufen konvertiert werden, weildie Merkmalsdetektoren norma-

lerweise nur auf einem Kanal arbeiten. Verglichen mit den anderen Farbkanälen kommt der Rotkanal

des Fotos der Wellenlänge des Lasers am nächsten. Aus diesem Grund liegt es nahe, nur diesen Kanal

zur Merkmalsdetektion zu verwenden. Die verbleibenden Beleuchtungsunterschiede müssen durch die

Unempfindlichkeit des Detektors kompensiert werden.


Des Weiteren müssen auch kleinere Translationen und Rotationen der Bildszene durch eine robuste Ge-

staltung des Merkmalsdetektors toleriert werden. Zwischen den Intensitätsbilder und den zugehörigen

Fotos ändert sich der Blickwinkel allerdings nicht stark, so dass der Detektor nicht affininvariant sein

muss. Affininvariante Detektoren sind die Erweiterung der skaleninvarianten Detektoren auf ungleich-

mäßige Skalierungen und Affinität der Bildszene [TM07]. Ein Detektor sollteallerdings nur die wirklich

notwendigen Anforderungen erfüllen, damit das Ergebnis nicht durchInvarianz oder Robustheit gegen-

über Bildtransformationen beeinträchtigt wird, die nicht tatsächlich in der Anwendung auftreten.

Die erfolgreiche Zuordnung der entsprechenden Merkmale hängt entscheidend von der Leistungsfähig-

keit des Deskriptors ab. Die Merkmale müssen so repräsentiert werden,dass eine richtige Zuordnung

trotz verschiedener Beleuchtung möglich ist. In [MS05] wurde eine Mengevon Deskriptoren für die Zu-

ordnung von Merkmalen evaluiert. Der SIFT-Deskriptor stellte sich dabeials überlegen gegenüber den

anderen Deskriptoren heraus. Eine noch bessere Leistung wies nur GLOH auf, der eine Erweiterung des

SIFT-Detektors darstellt.

In [BB07] und [BH07] wurde SIFT verwendet, um Merkmale in Intensitätsbildern1 eines grünen La-

sers und Fotos zu detektierten und zuzuordnen. Für die Merkmalsdetektion wurde der Grünkanal des

Fotos verwendet. In [BB07] wurde ein Anteil von ca. 20% an richtigen Korrespondenzen in der Menge

der von SIFT bestimmten Zuordnungen mit RANSAC ermittelt. Durch verschiedene Maßnahmen zur

Verbesserung des Ergebnisses, betrugt dieser Anteil in [BH07] 22%.

SIFT ist ein skalen- und beleuchtungsinvarianter Blobdetektor. Ein Vorteil von Blobdetektoren ist, dass

sie Merkmale besser lokalisieren als Corner-Detektoren [TM07]. Da SIFT die Anforderungen erfüllt

und eine effiziente Merkmalsdetektion und -zuordnung ermöglicht, wurde er für die Arbeit verwendet.

Im Folgenden wird die Merkmalsextraktion mit SIFT genauer erläutert.

4.3 Scale Invariant Feature Transform (SIFT)

SIFT beinhaltet sowohl einen Merkmalsdetektor als auch einen -deskriptor. In diesem Abschnitt wird

zunächst nach [Low04] und [VF08a] die Funktionsweise der Merkmalsdetektion und anschließend die

Berechnung des Deskriptors erläutert.

1In dem Fall meint das Intensitätsbild eine Abbildung der Polarkoordinaten auf kartesische Bildkoordinaten (vgl. Abschnitt

2.2).

4.3. SCALE INVARIANT FEATURE TRANSFORM (SIFT) 35

SIFT-Detektor

In einem Bild sind meist sowohl sehr feine als auch größere, gröbere Strukturen vorhanden. Wird ein lo-

kaler Merkmalsdetektor darauf angewendet, der jeweils nur eine kleine Pixelnachbarschaft eines Punktes

betrachtet, können die groben Strukturen nicht erfasst werden. Ausdiesem Grund muss auch in geglät-

teten Versionen des Bildes gesucht werden, in denen die feinen Strukturen unterdrückt werden, um alle

relevanten Merkmale zu extrahieren. Dafür wird ein Skalenraum des Bildes angelegt. Der Skalenraum

ist eine Folge vonS + 3 unterschiedlich stark geglätteten Versionen des AusgangsbildesI(x, y). Die

erste EbeneL(x, y, s) stellt dabei das AusgangsbildI(x, y) selbst dar, welches zusätzlich mitσ = 1, 6

geglättet wird. Die weiterenS + 2 Ebenen werden durch sukzessive Faltung mitG(x, y, σ)

L(x, y, s + 1) = L(x, y, s) ∗ G(x, y, σ) (4.1)

generiert, wobeiσ = 21/S ein konstanter Faktor ist, der die Ebenen separiert. Der Gaußsche Faltungskern

G(x, y, σ) =1

2πσ2exp

(−(x2 + y2)

2σ2

)

(4.2)

ist der einzige Filter, der sich für die Erzeugung eines Skalenraums eignet ([Jäh02], S. 139). Er erfüllt

die Bedingung, dass die Bildinformation mit zunehmender Glättung abnehmen muss, d.h. dass lokale

Extrempunkte nicht verstärkt werden dürfen und keine neuen mit zunehmender Glättung entstehen. Au-

ßerdem weist er eine Halbgruppeneigenschaft auf: Die sukzessiveGlättung mit demselben Parameter

hat dasselbe Ergebnis wie die einmalige Glättung mit einem entsprechend gewählten anderen Parameter.

Der Gaußsche Faltungskern ist zusätzlich dazu isotrop und homogen ([Jäh02], S. 139).

Da I(x, y) kein ideales Bild unendlicher Auflösung ist, wird davon ausgegangen, dass das eigentliche

AusgangbildIσn(x, y) schon eine Glättung mitσn = 0, 5 aufweist, um die finite Auflösung zu berück-

sichtigen [VF08b].

Der Skalenraum wird bei SIFT als Oktaveo bezeichnet. Wenn der Skalenraum des Ausgangsbildes, also

die erste Oktaveo = 0 vollständig bearbeitet wurde, wird die nächste Oktaveo + 1 untersucht. Das erste

Bild für die nächste Oktaveo + 1 ist das Bild der Oktaveo, das zweifach mitσ geglättet wurde. Dieses

wird um die Hälfte der Bildgröße reduziert, bevor die nächste Oktaveo + 1 damit aufgebaut wird. So

werden maximalomax

omax = ⌊log2 (min (Bildbreite, Bildhöhe))⌋ − omin − 3 (4.3)

Oktaven von der VLFeat-Bibliothek erzeugt, die insgesamt eine Multiskalenrepräsentation des Aus-

gangsbildes ergeben.

Ein Pixel wird nun zusätzlich zu seinen Bildkoordinaten(px, py) durch den Skalenparameterps in der

Oktaveo identifiziert. Die zunehmende Glättung des Bildes im Skalenraum reduziert neben feinen Struk-


(a) (b) (c)

(d) (e)

Abbildung 4.1: Veranschaulichung des Skalenraums. 4.1(a), 4.1(b) und 4.1(c) stellen die Ebenen

L(x, y, s) dar, 4.1(d) und 4.1(e) die Differenzbilder von zwei benachbarten Ebenen

turen auch Rauschen, das maßgeblich zur Invarianz des Detektors beiträgt. Durch Subtraktion von zwei

aufeinanderfolgenden Ebenen einer Oktave

D(x, y, s) = L(x, y, s + 1) − L(x, y, s) (4.4)

erhält man die DifferenzfunktionD(x, y, s) der gaußgeglätteten Bilder, die eine nahe Approximation

der skalennormalisierten Laplace-Funktion der Gaußfunktionσ2∇2G darstellt [Low04]. Von denS + 3

Ebenen einer Oktave erhält manS +2 Differenzbilder, wie in Abbildung 4.1 dargestellt. Die mittlerenS

Differenzbilder werden nun auf Extrema überprüft. Ein Pixel ist dann ein Extrempunkt, wenn alle Grau-

werte der Pixel seiner Nachbarschaft einen größeren oder kleineren Wert aufweisen. Als Nachbarschaft

eines Pixels sind die 8 umgebenden Pixel auf derselben Ebene und die jeweils 9 Pixel auf der Ebene

darüber und darunter gemeint.

Der gefundene Extrempunktp = (px, py, ps) in der aktuellen Oktave wird anschließend auf Stabili-

tätskriterien geprüft. Punkte, die nur schwachen Kontrast aufweisen und deshalb empfindlich gegenüber

Rauschen sind, können daraufhin eliminiert werden [Low04]. Um den Punkt genauer zu lokalisieren,

wird am Extrempunkt im DifferenzbildD(px, py, ps) eine Taylorreihe mitx = (x, y, s)T entwickelt

D(x) = D +∂DT

∂x+

1

2xT ∂2D

∂x2x, (4.5)

die nach den quadratischen Termen abgebrochen wird. Setzt man die erste Ableitung dieser Funktion


nachx zu Null

x = −∂2D−1

∂x2

∂D

∂x, (4.6)

ergibt sich ein lineares Gleichungssystem. Die Lösungx ist der Versatz des tatsächlichen Extrempunkts

dieser Funktion vom gefundenen Extrempunktp. Die Berechung wird mit den Pixeldifferenzen vorge-

nommen. Sofern die Werte inx nicht größer als 0,5 sind, wird der Vektorx zum gefundenen Extrem-

punktp addiert. Anderenfalls wird die Berechnung um den nachx versetzten Punkt erneut ausgeführt.

Extremstellen, bei denen die Bedingung

|D(x)| =

∣

∣

∣

∣

D +1

2

∂DT

∂xx

∣

∣

∣

∣

≤ t (4.7)

erfüllt ist mit t als festgelegtem Schwellwert (peakThreshold), werden als instabile Punkte eliminiert.

Nachdem so die Position des Merkmalspunktes interpoliert wurde, wird überprüft, ob sich der Punkt

ungünstig auf einer Kante befindet. Dafür wird die Hesse-MatrixH

H =

Dxx Dxy

Dxy Dyy

(4.8)

berechnet, wobei sich die AbleitungenDxx, Dxy und Dyy aus den Pixeldifferenzen ergeben. Die Ei-

genwerteλ1, λ2 (λ1 > λ2) von H sind proportional zur Hauptkrümmung vonD am interpolierten

Extrempunkt, jedoch ist nur das Verhältnis der Werte von Interesse. Über die Determinantedet(H)

det(H) = DxxDyy − D2xy = λ1λ2 (4.9)

und die Spur der Matrixsp(H)

sp(H) = Dxx + Dxy = λ1 + λ2 (4.10)

kann das Verhältnis berechnet werden

sp(H)

det(H)=

(λ1 + λ2)2

λ1λ2=

(rλ2 + λ2)2

rλ22

=(r + 1)2

r. (4.11)

Wenn die Eigenwerteλ1 undλ2 gleichgroß sind, nimmt(r + 1)2

rden minimalen Wert an und wächst

ansonsten mitr. Um zu testen, ob die Hauptkrümmung eines Punktes kleiner als ein festgelegter Schwell-

wert r (edgeThreshold) ist, musssp(H)

det(H)<

(r + 1)2

r(4.12)

geprüft werden. Abschließend wird für jeden gefundenen Extrempunkt p eine Orientierung bestimmt.

Innerhalb einer Oktave werden die Gradientenstärkenm(x, y)

m(x, y) =√

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


und Gradientenorientierungenθ(x, y)

θ(x, y) = arctanL(x, y + 1, s) − L(x, y − 1, s)

L(x + 1, y, s) − L(x − 1, y, s)(4.14)

vorberechnet. Für den Extrempunktp wird ein Histogramm aus den Gradientenorientierungen der umlie-

genden Punkte erstellt, ähnlich wie in Abbildung 4.3 für den Deskriptor dargestellt. Das Orientierungs-

histogramm teilt die 360◦ in 36 Klassen. Außerdem wird am Extrempunktp ein GaußfilterG(x, y, σ =

1, 5ps) angesetzt, mit dem die Gradientenorientierungen der Punkte der kreisförmigen Region um den

Extrempunkt, die dem Histogramm hinzugefügt werden, gewichtet werden. Zusätzlich werden die Orien-

tierung des Punktes auch noch mit der Stärke seines Gradienten multipliziert. Die Histogrammklasse mit

dem größten Werten gibt folglich die dominante Orientierung für diesen Extrempunkt an [Low04]. Für

alle Histogrammklassen deren Wert mehr als 80% des Histogrammmaximums beträgt, wird ein Merk-

malspunkt angelegt. Daher es kann für jeden Extrempunkt mehr als einen Merkmalspunkt geben, die

aber jeweils verschieden orientiert sind. Die genaue Orientierung für jeden Merkmalspunkt wird inter-

poliert, indem eine Parabel an den entsprechenden Wert der Klasse und die zwei benachbarten Klassen

angepasst wird.

Für das AusgangsbildI(x, y) erhält man somit eine Menge an Merkmalspunktenpi, die jeweils durch

ihre Bildkoordinaten(px, py), die Orientierungpθ und den Skalenparameterps definiert werden.

SIFT-Deskriptor

Ein Merkmalsdeskriptor soll den Merkmalspunkt möglichst unverwechselbar repräsentieren und gleich-

zeitig invariant gegenüber verschiedenen Transformationen, wie Beleuchtungs- und Orientierungssän-

derung sein. Um den SIFT-Deskriptor für einen Merkmalspunkt, der nicht notwendigerweise mit dem

SIFT-Detektor identifiziert worden sein muss, zu erstellen, wird zunächst ein lokales Koordinatensy-

stem mit dem Merkmalspunkt als Ursprung angelegt. Diex-Achse des Deskriptorkoordinatensystems

bildet mit derx-Achse des Bildkoordinatensystems den Orientierungswinkelpθ, wie in Abbildung 4.2

angegeben. Das lokale Koordinatensystem ist also relativ zum Bildkoordinatensystem um den Orientie-

rungswinkelpθ gedreht.

Es werden nun die Gradienten in einem quadratischen Fenster festgelegter Größewf im Deskriptor-

koordinatensystem betrachtet. Die Gradienten darin werden mit einem Gaußfilter G(x, y, σ = 1, 5wf )

geglättet um den Einfluss von Gradienten, die weiter vom Merkmalspunkt entfernt sind, abzuschwächen.

Ähnlich wie in Abbildung 4.3 wird das Fenster wird in 4×4 Unterfenster aufgeteilt und für jedes ein Ori-

entierungshistogramm mit 8 Klassen aus den Gradienten erstellt. Durch trilineare Interpolation werden

die Grauwerte auch anteilig den Histogrammen zugewiesen.


Abbildung 4.2: Lokales Deskriptorkoordinatensystem umpθ zum Bildkoordinatensystem gedreht

Abbildung 4.3: Herstellung der Orientierungshistogramme mit den Bildgradienten [Low04]. Zuvor wer-

den die Gradienten mit einem Gaußfilter geglättet, angedeutet durch den Kreis.


Die jeweils 8 Werte der 4×4 Orientierungshistogramme werden aneinander gereiht und bilden den De-

skriptorvektor mit 128 Elementen, der auf Einheitslänge normiert wird. Die Vektorelemente werden ge-

gebenenfalls auf 0,2 reduziert, sofern sie größer als dieser Wert sind. Abschließend wird der Deskriptor

nochmals normiert.

Für jeden der detektierten Merkmalspunkte wird so ein Deskriptor erstellt, der den Merkmalspunkt im

128-dimensionalen Merkmalsraum darstellt. Die DeskriptorenDA eines Bildes werden den Deskriptoren

DB eines anderen Bildes zugeordnet, indem der nächste NachbardB ∈ DB zu dA ∈ DA im 128-

dimensionalen Merkmalsraum gesucht wird. Der Abstandd zwischen zwei Deskiptoren wird mit dem

Euklidischen Abstand

d(dA,dB) =

√

√

√

√

128∑

i=1

(diA − di

B)2 (4.15)

gemessen. In Algorithmus 4.1 wird die Zuordnung der Deskriptoren zusammengefasst.

Voraussetzung:dA ∈ DA Deskriptoren aus dem BildA unddB ∈ DB Deskriptoren aus dem BildB

Ziel: Bestimmung einer Menge von KorrespondenzenMAB = {(mA,mB) : mA ∈ DA,mB ∈DB, d(mA,mB) = min}

Algorithmus:

MAB = { }∀dA

i ∈ DA, i = 1 . . .m

q = argminj

d(dAi ,dB

j ) mit dBj ∈ DB

r = argminj

d(dAi ,dB

j ) mit dBj ∈ DB\dB

q

if (t · d(dAi ,dB

q )≤ d(dAi ,dB

r ))

MAB = M ∩ (dAi ,dB

r )

endif

Algorithmus 4.1: Zuordnung der SIFT-Deskriptoren über Nächste-Nachbar-Suche

41

5 Zuordnung von Intensitätsbildern und Fotos mit SIFT

In diesem Kapitel werden die Datensätze, die für die Arbeit zur Verfügung standen, kurz vorgestellt.

Anschließend wird das Vorgehen bei der Herstellung und Bewertung von Punktkorrespondenzen mit

SIFT erläutert. Am Schluß steht eine Diskussion der Ergebnisse.

5.1 Verwendete Datensätze

Für die Experimente standen drei Datensätze zur Verfügung: das Palaisim Großen Garten, der Schiller-

garten und die Alte Bibliothek in Berlin. Alle Punktwolken wurden mit dem Laserscanner Riegl LMS-

Z420i (siehe Tabelle 2.2 im Abschnitt 2.1) aufgenommen. Für den Datensatzdes Palais im Großen

Garten, welches mit sechs Standpunkten erfasst wurde, wurden Fotosmit der Kamera Nikon D100 ge-

macht. Nur drei der sechs Standpunkte wurden verwendet, da die Palaisfassaden sich sehr ähneln. Der

Schillergarten wurde von einem Standpunkt aus neu aufgenommen. Außerdem wurden dazu Fotos mit

der Kamera Nikon D300 gemacht. Ein Datensatz der Alten Bibliothek („Kommode“) in Berlin stand

ebenfalls samt Fotos zur Verfügung. Die Fotos stammen von einer Fuji FinePix S2 Pro-Kamera und ihr

ursprünglicher Zweck war die Erfassung der Passpunkte an der Fassade für eine Bündelblockausglei-

chung. Aus diesem Grund sind diese Aufnahmen Frontalansichten von Fassadenteilen und stellen nicht

das Objekt im Ganzen dar, wie es bei den anderen Fotos hauptsächlich der Fall ist. Vom Datensatz der

Kommode wurde nur der zweite Standpunkt gewählt, der einen großen Teildes Gebäudes in relativ hoher

Auflösung darstellt.

Von den ausgewählten Standpunkten wurden die zentralperspektivischen Intensitätsbilder, wie in Ab-

schnitt 2.2 erläutert, mit einer empirisch ermittelten Pixelgröße∆p von 0,00089mm generiert. Für die

Punktwolken des Palais und des Schillergartens ergibt sich damit jeweils ein Intensitätsbild pro Stand-

punkt. Der Öffnungswinkel des Laserscanners bei der Aufnahme des zweiten Kommodestandpunktes

war relativ groß, weshalb eine Darstellung in einem Bild unpraktikabel ist (vgl. Abschnitt 2.2). Deshalb

wurden 4 Teilbilder von der Punktwolke erzeugt.

Die Intensitätsbilder wurden jeweils nach den im Abschnitt 2.4 erläuterten Punktoperationen mit den

Parameternh = 0, 6 (Helligkeitsänderung),c = 0, 1 (Kontraständerung),γ = 0, 3 (Gammakorrektur),

42 5. ZUORDNUNG VON INTENSITÄTSBILDERN UND FOTOS MIT SIFT

(a) Intensitätsbild ohne Bildverbesserung (b) Intensitätsbild mit Bildverbesserung

Abbildung 5.1: Intensitätsbild der Kommode (Teilbild 3) ohne und mit Verbesserung

Intensitätsbild zugehörige Fotos

Schillergarten DSC_0325, DSC_0327, DSC_0328, DSC_0329,

DSC_0334,DSC_0339,DSC_0340, DSC_0342,DSC_0344

Palais

Standpunkt 2 DSC_0019, DSC_0020,DSC_0080, DSC_0082,DSC_0086,DSC_0162

Standpunkt 3 DSC_0030, DSC_0031,DSC_0096,DSC_0097,DSC_0104

Standpunkt 4 DSC_039, DSC_0040, DSC_0111, DSC_0188

Kommode

Teilbild 1 DSCF0797, DSCF0798


Teilbild 3 DSCF0789, DSCF0784, DSCF0785, DSCF0787, DSCF0788


Tabelle 5.1: Zuteilung der Fotos zu den Intensitätsbildern

k = 0 undw = 0, 6 (Histogrammdehnung) verbessert. Zum Vergleich ist in Abbildung 5.1 das Intensi-

tätsbild der Kommode mit und ohne den Verbesserungsoperationen dargestellt.

Eine automatische Zuordnung der Foto zu den passenden Intensitätsbilderist selbst ebenfalls eine kom-

plizierte Aufgabe, denn schon die Standpunkte von den gegenüberliegenden Palaisfassaden sehen sich

zum Verwechseln ähnlich. Die Bearbeitung dieser Problematik war allerdings nicht das Ziel der Arbeit.

Aus diesem Grund wurden für die Experimente die Fotos des Palais den entsprechenden Intensitätsbil-

dern der Standpunkte manuell zugeordnet. Die Zuteilung der Teilintensitätsbilder des Kommodedaten-

satzes zu den Fotos erfolgte ebenfalls manuell. In Tabelle 5.1 sind die Zuteilungen aufgeführt.

Im Folgenden bezeichnetDatensatzimmer die ausgewählten Standpunkte und dazugehörigen Fotos.

5.2. BERECHNUNG DER SIFT-MERKMALSPUNKTE 43

5.2 Berechnung der SIFT-Merkmalspunkte

Für die Merkmalsdetektion wurde die SIFT-Implementation aus der VLFeat-Bibliothek [VF08a] verwen-

det. Sie bietet eine Schnittstelle für Matlab, die benutzt wurde, um in allen Bildern SIFT-Merkmalspunkte

zu detektiertieren und Deskriptoren zu berechnen. Bevor die Deskriptoren aus der VLFeat-Matlabfunktion

zurückgegeben werden, wird der einheitsnormierte Deskriptor mit 512 multipliziert und anschließend auf

den maximalen Elementbetrag von 255 beschränkt. Die Matlabschnittstelle wurdefür die Experimente

so modifiziert, dass direkt der einheitsnormierte Deskriptor zurückgebenwird.

Für die Einstellung des Detektorergebnisses sind vor allem die ParameterpeakThreshold, edgeThreshold

undfirstOctaveentscheidend. Wie bereits in Abschnitt 4.3 erwähnt, regeltpeakThresholdwie stark ein

Extrempunkt bei der Detektion sein muss um als Merkmalspunkt akzeptiert zu werden. Vorgegeben ist

peakThreshold= 0 und reduziert mit steigendem Wert die Anzahl an gefundenen Merkmalspunkten. Mit

edgeThresholdwerden die Punkte während des Detektionsschritts eliminiert, deren Krümmungzu klein

ist und die deshalb eher schlecht lokalisiert sind [VF08a]. Der Ausgangswert istedgeThreshold= 10.

Eine Verringerung des Werts reduziert ebenfalls die Anzahl an Merkmalspunkten. Mit dem Parameter

firstOctavekann die Oktave angegeben werden, in der mit der Extrempunktdetektion begonnen werden

soll. Normalerweise wird in der ersten Oktave mit der Detektion angefangen,d.h.firstOctave= 0.

Durch Einstellung der Parameter wurde versucht die Anzahl der SIFT-Punkte gering zu halten und

gleichzeitig eine ausreichende Abdeckung der Bildszene zu erreichen.Da mit zunehmender Anzahl an

Merkmalspunkten auch die Anzahl an falschen Zuordnungen steigt, beeinflusst eine zu hohe Anzahl an

Merkmalspunkten die Zuordnung der Deskriptoren negativ [TM07]. Inden Abbildungen 5.2 und 5.3(b)

sind die Mengen der SIFT-Punkte für die Datensätze als Balkendiagramme dargestellt. Die Parameter

wurden für die Intensitätsbilder eigentlich auf den voreingestellten Werten belassen. Nur bei dem Intensi-

tätsbild des Schillergartens wurde deredgeThresholdauf 3 reduziert, wobei die Anzahl an SIFT-Punkten

trotzdem fast die höchste der Intensitätsbilder ist. Eine Änderung despeakThresholdresultierte bei allen

Intensitätsbildern darin, dass keine SIFT-Punkte mehr gefunden wurden. Das bedeutet, das die Merk-

malspunkte der Intensitätsbilder eher schwach ausgeprägt sind, was sich auf die trotz Bildverbesserung

schwachen Kontraste zurückführen lässt.

Von den Fotos wurde der Rot- und der Grünkanal zur Detektion von Merkmalspunkten verwendet. Der

Rotkanal wurde unter der Annahme gewählt, dass er der Nahinfrarotstrahlung des Lasers näher kommt

und deshalb mehr Ähnlichkeiten zum Intenstitäsbild aufweist. Der Grünkanal wurde zusätzlich verwen-

det um vergleichen zu können, wie die Farbkanalwahl das Ergebnis beeinflusst.edgeThresholdwurde

sehr niedrig auf 3 bzw. 2,5 eingestellt undpeakThresholdauf 1,5 angehoben. DerfirstOctave-Parameter


wurde auf 1 bzw. 2 gesetzt. Die Detektion von Merkmalspunkten in der ersten Oktave, d.h. infirstOc-

tave= 0, ist überflüssig, da das Intensitätsbild den Detailreichtum des Fotos ohnehin nicht aufweist.

Eine Zuordnung von SIFT-Punkten aus der ersten Oktave würde somit zwangsläufig fehlschlagen. Um

die großen Auflösungsunterschiede zwischen Intensitätsbild und Foto besser zu kompensieren wird des-

halb die Extrempunktdetektion erst in der zweiten bzw. dritten Oktave begonnen. Die Einstellung der

Anfangsoktave reduziert folglich ebenfalls die Anzahl an gefundenen Merkmalspunkten. Für alle Daten-

sätze ist die Anzahl der SIFT-Punkten sehr ähnlich und liegt zwischen 1400 und 3500 Punkten, wenn

firstOctave= 1 und zwischen 600 und 1100 Punkten, wennfirstOctave= 2.

5.3 Evaluation der SIFT-Zuordnung

Die SIFT-Deskriptoren der Bildpaare wurden mit der Matlabfunktionvl_ubcmatch der VLFeat-

Bibliothek zugeordnet. Der Zuordnungsalgorithmus, den die Funktion verwendet, wurde bereits in Ab-

schnitt 4.3 erläutert. Standardmäßig verwendetvl_ubcmatch einen Schwellwert vont = 1, 5 um

ausreichend differenzierte Zuordnungen zu finden. In den Abbildungen 5.4, 5.5 und 5.6 sind die Zuord-

nungsmengen der Bildpaare jeweils durch die Gesamthöhe des Balkens dargestellt. Für den Schillergarten-

und den Palaisdatensatz werden in den Deskriptormengen der Bilder zwischen 135 und 244 Zuordnungen

zum Intensitätsbild gefunden, während es bei der Kommode nur zwischen8 und maximal 121 sind.

Zur Abschätzung der Anzahl an tatsächlich richtigen Korrespondenzen aus der Menge an gefundenen

DeskriptorpaarenMAB = {(mA,mB) : mA ∈ DA,mB ∈ DB}, wurde eine Homographie berechnet,

die die Bildkoordinaten des einen Bildes in das andere projiziert. Dafür wardie Bestimmung von manu-

ellen Punktkorrespondenzen in den Bildpaaren erforderlich. Die 3D-Koordinaten der Passpunkte, die der

Kommodedatensatz enthält, waren bekannt. Die Bildkoordinaten der Passpunkte wurden in den Fotos

gemessen. Für die anderen Datensätze erfolgte die Bestimmung von Bildkoordinaten über die Messung

von markante Punkten in den Fotos. Die zugehörigen 3D-Koordinaten wurden durch Auswahl geeigne-

ter Punkte aus der Laserscannerpunktwolke bestimmt. Die 3D-Koordinatenwurden bei der Generierung

des Intensitätsbildes mit den anderen Punkten auf die Bildebene projiziert, um die entsprechenden Bild-

koordinaten zu erhalten. Durch die manuelle Messung und Auswahl der Punkte und der beschränkten

Meßgenauigkeit des Laserscanners weisen die manuell erstellten Korrespondenzen einen hohen Anteil

an Rauschen auf.

Mit diesen Korrespondenzen wurde anschließend die HomographiematrixH berechnet. In Algorith-

mus 5.1 ist die Berechnung der HomographieH angegeben, wobei deutlich wird, dass es eine 2D-DLT

darstellt (vgl. Abschnitt 3.2). Für die Homographiebestimmung müssen die PunktmengenxA undxB

5.3. EVALUATION DER SIFT-ZUORDNUNG 45

0325 0327 0328 0329 0334 0039 0340 0342 03440

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

Schillergarten−Bilder (DSC_∗ )

SIF

T−

Pun

kte

Rotkanal, firstOctave = 1Rotkanal, firstOctave = 2Grünkanal, firstOctave = 1

SIFT−Parameter: edgeThreshold = 2,5; peakThreshold = 1,5

(a) Anzahl SIFT-Punkte der Schillergartenfotos

0019 0020 0080 0082 0086 0162 0030 0031 0096 0097 0104 0039 0040 0111 01880

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

Palais−Bilder (DSC_∗ )

SIF

T−

Pun

kte


SIFT−Parameter: edgeThreshold = 3; peakThreshold = 1,5

(b) Anzahl SIFT-Punkte der Palaisfotos

Abbildung 5.2: SIFT-Punkte für die Fotos der Datensätze


0797 0798 0789 0784 0785 0787 0788 0779 07800

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

Kommode−Bilder (DSCF∗ )

SIF

T−

Pun

kte


SIFT−Parameter: edgeThreshold = 2,5; peakThreshold = 1,5

(a) Anzahl SIFT-Punkte der Kommodefotos

(2) (3) (4) {1} {2} {3} {4}0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

SIF

T−

Pun

kte

SIFT−Parameter: peakThreshold = 0; firstOctave = 0edgeThreshold = 3 edgeThreshold = 10

Schiller−garten Kommode {Teilbild}Palais (Standpunkt)

(b) Anzahl SIFT-Punkte der Intensitätsbilder

Abbildung 5.3: SIFT-Punkte für den Kommodedatensatz und die Intensitätsbilder der Datensätze

5.4. AUTOMATISCHE BESTIMMUNG DER HOMOGRAPHIE MIT RANSAC 47

zunächst normalisiert werden. Laut ([HZ03], S. 108) ist das ein essentieller Schritt, der nicht vernach-

lässigt werden darf, da die Berechnung nicht invariant zum gewähltenKoordinatensystem ist. Um die

HomographiematrixH zu erhalten, muss am Schluß die bestimmte Matrix wieder denormalisiert wer-

den.

Die HomographieH wird genutzt um den aufgerundeten, mittleren Abstandtn

tn =

⌈

1

n

n∑

i=0

√

(xB − x′A)2

⌉

(5.7)

der BildkoordinatenxB zu den projizierten Koordinatenx′A

x′A = HxA (5.8)

x′A = x

′A/x′Aw (5.9)

zu bestimmen. Dieser Wert wird verwendet um die Anzahl an richtigen Korrespondenzen zu ermitteln.

Die SIFT-PunktemA ∈ MAB des Intensitätsbildes werden mitH in das Foto projiziert. Die Paare

(mA,mB) der ZuordnungsmengeMAB, bei denen der Abstandd die Bedingung

d(mB,HmA) ≤ tn (5.10)

erfüllt, werden als richtige Zuordungen betrachtet. Die Balkendiagramme 5.4, 5.5 und 5.6 geben die

Anteile der so ermittelten richtigen Korrespondenzen (orange eingefärbt)an. Für jedes Bildpaar ist der

Schwellwerttn über dem Balken in Pixeln angegeben, mit dem dieser Anteil ermittelt wurde. Die Menge

aller Zuordnungen für ein Bildpaar ergibt sich durch die Gesamthöhe desBalkens. Daraus ist ersichtlich,

dass aus den Zuordnungen des Palais- und Schillergartendatensatzeszwischen 8 und 62 Zuordnungen

als richtig erkannt wurden. Für den Kommodedatensatz konnten maximal 4 in einer Zuordnungsmenge

gefunden werden. Zum größten Teil wurden für diesen Datensatz jedoch keine richtigen Zuordnungen

identifiziert. Diese Anzahl an richtigen Korrespondenzen stellt nur einenOrientierungswert dar. Wenn

die HomographieH mit anderen Korrespondenzen bestimmt wird, kann es sein, dass sich die Anzahl

der SIFT-Punktpaare, die das Kriterium (5.10) erfüllen, ändert.

5.4 Automatische Bestimmung der Homographie mit RANSAC

Da die Mengen der Zuordnungen des Palais und des Schillergartens zwischen 5% und 38% richtige

Korrespondenzen aufweisen, wurde RANSAC angewendet um sie automatisch in der Zuordnungsmenge

MAB zu idenfizieren. Die Bestimmung einer Homographie mit einer minimalen Stichprobe von 4 Punkt-

korrespondenzen ausMAB dient dabei als Modell. Zunächst wurde eine einfache Version des RANSAC-

Algorithmus nach ([HZ03], S. 122) in Matlab umgesetzt, wobei für jede Stichprobe Bedingung überprüft


Voraussetzung:n ≥ 4 2D zu 2D-PunktkorrespondenzenxAi ↔ xB

i

Ziel: Bestimmung einer 2D-HomographiematrixH, so dassxAi = HxB

i

Algorithmus:

• Normalisierung der PunktexAi mit einer MatrixTA, so dass ihr Schwerpunkt im Ursprung liegt

und der mittlere Abstand jedes Punktes vom Ursprung√

2 beträgt.

T =

√2/σx 0 −

√2/σx · µx

0√

2/σy −√

2/σy · µy

0 0 1

(5.1)

xA = TAxA (5.2)

σ ist die Standardabweichung undµ der Mittelwert vonx .

• Normalisierung der PunktexB mit der MatrixTB, die dieselben Bedingungen fürxB erfüllt.

xB = TBxB (5.3)

• Aufstellen der2n × 9-Matrix A

A =

0T −xBT1 yA

1 xBT1

xBT1 0T −xA

1 xBT1

. . .

0T −xBTn yA

n xBTn

xBTn 0T −xA

nxBTn

(5.4)

mit den gegebenenn Punktkorrespondenzen.

• Lösen vonAh = 0 mit einer Singulärwertzerlegung vonA = UDVT . H entspricht dem letzten

Spaltenvektor der9 × 9-Matrix V als Matrix arrangiert

H =

V19 V29 V39

V49 V59 V69

V79 V89 V99

. (5.5)

• Denormalisierung vonH mit

H = T−1A HTB (5.6)

um die HomographiematrixH zu erhalten.

Algorithmus 5.1: Berechnung einer Homographie nach ([HZ03], S. 103,91)


0019 0020 0080 0082 0086 0162 0030 0031 0096 0097 0104 0039 0040 0111 01880

50

100

150

200

250

300

Foto (DSC_∗ ) und Intensitätsbild

SIF

T−

Zuo

rdnu

ngen

ZuordnungenAnteil an richtigenZuordnungen

17px18%

8px21% 20px

7%

8px8%

25px8%

9px9% 20px

5%

9px4%

5px20%

8px18%

8px19%

28px33%

20px38% 43px

35%

5px20%

(a) SIFT-Parameter:edgeThreshold= 3, peakThreshold= 1, 5,firstOctave= 1, Rotkanal

0019 0020 0080 0082 0086 0162 0030 0031 0096 0097 0104 0039 0040 0111 01880

50

100

150

200

250

300


SIF

T−

Zuo

rdnu

ngen

17px13%

8px14%

20px5% 8px

7%

25px6% 9px

9%

20px3% 9px

4%

5px12% 8px

9%

8px15%

28px25%

20px25%

43px30% 5px

17%

(b) SIFT-Parameter:edgeThreshold= 3, peakThreshold= 1, 5,firstOctave= 2, Rotkanal

0019 0020 0080 0082 0086 0162 0030 0031 0096 0097 0104 0039 0040 0111 01880

50

100

150

200

250

300


SIF

T−

Zuo

rdnu

ngen

17px18%

8px14% 20px

5%8px11%

25px9%

9px7%

20px2% 9px

4%

5px14% 8px

14%

8px19%

28px25%

20px39%

43px27%

5px17%

(c) SIFT-Parameter:edgeThreshold= 3, peakThreshold= 1, 5,firstOctave= 1, Grünkanal

Abbildung 5.4: Zuordnungen des Palaisdatensatzes. Der obere Wert über dem Balken gibt den Schwell-

wert tn an, der Wert darunter gibt den Anteil der richtigen Korrespondenzenan den

gefundenen Zuordnungen in Prozent wieder.


0325 0327 0328 0329 0334 0339 0340 0342 03440

50

100

150

200

250

300


SIF

T−

Zuo

rndu

ngen

ZuordnungenAnteil an richtigen Zuordnungen

22px16%

31px13%

32px13% 19px

16%

29px12% 27px

16%

28px16%

29px11%

35px12%

(a) SIFT-Parameter:edgeThreshold= 2, 5, peakThreshold= 1, 5,firstOctave= 1, Rotkanal

0325 0327 0328 0329 0334 0339 0340 0342 03440

50

100

150

200

250

300


SIF

T−

Zuo

rdnu

ngen

22px15%

31px14%

32px14% 19px

15%

29px11%

27px15% 28px

18%

29px10%

35px13%

(b) SIFT-Parameter:edgeThreshold= 2, 5, peakThreshold= 1, 5,firstOctave= 2, Rotkanal

0325 0327 0328 0329 0334 0339 0340 0342 03440

50

100

150

200

250

300


SIF

T−

Zuo

rdnu

ngen

22px12% 31px

13%

32px14%

19px16%

29px12% 27px

14%

28px18% 29px

10%35px12%

(c) SIFT-Parameter:edgeThreshold= 2, 5, peakThreshold= 1, 5,firstOctave= 1, Grünkanal

Abbildung 5.5: Zuordnungen des Schillergartendatensatzes. Der obere Wert über dem Balken gibt den

Schwellwerttn an, der Wert darunter gibt den Anteil der richtigen Korrespondenzenan

den gefundenen Zuordnungen in Prozent wieder.


0797 0798 0797 0789 0789 0784 0785 0787 0788 0779 07800

50

100

150

200

250

300

Foto (DSCF∗ ) und Intensitätsbild

SIF

T−

Zuo

rdnu

ngen

ZuordnungenAnteil an richtigen Zuordnungen

40px0%39px

0%

62px0%

40px0%

47px0%

12px0%

16px0%

45px0%

58px2%

31px1%

38px3%

(a) SIFT-Parameter:edgeThreshold= 2, 5, peakThreshold= 1, 5,firstOctave= 1, Rotkanal

0797 0798 0797 0789 0789 0784 0785 0787 0788 0779 07800

50

100

150

200

250

300


SIF

T−

Zuo

rdnu

ngen

39px0%

40px0%

62px0%

40px0% 16px

0%12px0%

45px2%

58px2%

31px3%

38px7%

47px4%

(b) SIFT-Parameter:edgeThreshold= 2, 5, peakThreshold= 1, 5,firstOctave= 2, Rotkanal

0797 0798 0797 0789 0789 0784 0785 0787 0788 0779 07800

50

100

150

200

250

300


SIF

T−

Zuo

rdnu

ngen

39px0%

40px0%

62px0%

40px0%

45px0%

16px0%

12px0%

58px1%

31px1%

38px3% 47px

0%

(c) SIFT-Parameter:edgeThreshold= 2, 5, peakThreshold= 1, 5,firstOctave= 1, Grünkanal

Abbildung 5.6: Zuordnungen des Kommodedatensatzes. Der obere Wertüber dem Balken gibt den

Schwellwerttn an, der Wert darunter gibt den Anteil der richtigen Korrespondenzen

an den gefundenen Zuordnungen in Prozent wieder.


wurde, das die Punkte nicht kollinear sein dürfen. Jedoch schlug die Bestimmung der richtigen Korre-

spondenzen damit fehlt. Aus diesem Grund wurde schließlich die RANSAC Toolbox für Matlab [Zul08]

verwendet, die gleichzeitig die Homographieberechnung nach ([HZ03],S. 103, 91) bereitstellt. In Algo-

rithmus 5.2 ist das konkrete RANSAC-Verfahren, welches von der Toolbox angewendet wird, mit den

verwendeten Parametern zusammengefasst. Daraus ist ersichtlich, dassdie Stichprobe zusätzlich noch

die Bedingung erfüllen muss, das die Punktkonstellationen in beiden Bildern ähnlich sein müssen, sonst

wird die Stichprobe nicht weiter in Betracht gezogen. Sowohl dieses Kriterium als auch die andere Art

der Berechnung der notwendigen Iterationen tragen offenbar dazu bei, dass die richtigen Korresponden-

zen gefunden werden.

Die Ergebnisse der automatischen Bestimmung der richtigen Korrespondenzen aus der Menge der Zu-

ordnungen des Palais- und Schillergartendatensatzes sind Abbildung 5.4, 5.5 und 5.6 angegeben. Die

Anzahl an richtigen Korrespondenzen, die mit RANSAC bestimmt wurden, liegt praktisch für alle Bilder

des Palaisdatensatzes über den geschätzten Werten. Es werden zwischen 10% und 37% aller Punktkorre-

spondenzen der Zuordnungsmenge als richtig ermittelt. Abbildung 5.7(a) zeigt das Foto DSC_0040, das

zum 4. Palaistandpunkt gehört. In diesem Bildpaar wurden die meisten Korrespondenzen mit RANSAC

gefunden, die in der Abbildung entsprechend markiert sind. Beim Schillergartendatensatz liegt die An-

zahl der von RANSAC gefundenen richtigen Korrespondenzen meist etwas unter den vorher bestimmten

Werten. Der Anteil der richtigen Zuordnungen macht beim Schillergartendatensatz zwischen 8% und

13% aus. Abbildung 5.7(b) zeigt das Foto DSC_0340 bei dem die meisten Korrespondenzen gefunden

wurden. Die Positionen der SIFT-Punkte, die von RANSAC als richtige Zuordnungen gefunden wurden,

sind für ein Intensitätsbild jeweils sehr ähnlich.

Bei den Fotos DSC_0030 und DSC_0031 musste die RANSAC-Berechnung aufgrund des hohen Zeitauf-

wandes (> 3 Stunden) abgebrochen werden. Die vorher geschätzte Anzahl an richtigen Korrespondenzen

ist bei diesen Bildern sehr niedrig, was im Prinzip eine enorm große Zahlan Iterationen von RANSAC

erfordert und sehr zeitintensiv ist. Da die geschätzten Zahlen für den Kommodedatensatz ebenfalls sehr

niedrig bzw. 0 trotz des hohen Grenzwertstn sind, wurde RANSAC nicht auf dem Datensatz angewen-

det, da mit keiner ausreichenden Menge an Inliern gerechnet werden konnte.

Die RANSAC-Berechnung wurde in Matlab R2009a auf einem Rechner (Intel i5-750 2,67GHz, 6GB

RAM) ausgeführt und dauerte normalerweise zwischen ca. 0,01 und 6 Minuten.


Voraussetzung:n PunktkorrespondenzenxAi ↔ xB

i , die über die Zuordnung der SIFT-DeskriptorenDA

undDB des Bildpaares(A, B) bestimmt wurden (siehe Algorithmus 4.1)

Ziel: Bestimmung der richtigen Korrespondenzen indem eine 2D-Homographiematrix bestimmt wird

Algorithmus:

• Festlegung der Wahrscheinlichkeit für mindestens eine fehlerfreie Stichprobep = 0, 99

• Bestimmung des Fehlerschwellwertest2n mit der kumulativenχ2-Verteilung ([HZ03], S. 118,119)

t2n = F−1χ2

4

(p) (5.11)

• Anzahl an durchgelaufenen Iterationenc = 0 und maximale Anzahl an IterationenT = 100

• Wiederhole solangec < T

– Bestimmung eine zufällige Stichprobes vonn Punktkorrespondenzen mit‖s‖ = 4

– Überprüfung, dass (a) die Punkte nicht kollinear sind und (b) die Punktkonfigurationen in

beiden Bildern ähnlich sind, d.h. wenn eine gerichtete Linie zwischen zwei Punkten gezogen

wird, muss sich ein dritter Punkt dazu in beiden Bildern auf derselben Seite der Linie befinden

– Berechnung der HomographieH mit der Stichprobes nach Algorithmus 5.1

– Berechnung der mitH projizierten Bildkoordinatenx′A

x′A = HxA (5.12)

x′A = x

′A/x′Aw (5.13)

und analogx′B

– Berechnung des symmetrischen TransferfehlerE für allen Korrespondenzen

E =n

∑

i=0

√

(xA − x′B)2 +

n∑

i=0

√

(xB − x′A)2 (5.14)

– Bestimmung der InliermengeI als diejenigen Korrespondenzen, dieEi < t2n erfüllen.

– Wenn‖I‖ > ‖I∗‖, dannI∗ = I undH∗ = H

– Bestimmung der Wahrscheinlichkeitq =k−1∏

i=0

‖I‖ − i

n − iund Aktualisierung der Anzahl an

maximalen IterationenT

T =

⌈

log ǫ

log (1 − q)

⌉

, (5.15)

wobeiǫ = 1 − p ist.

• Bestimmung der HomographieH∗ mit der gesamten Menge an InlierI∗ neu.

Algorithmus 5.2: Automatische Bestimmung der richtigen Korrespondenzen mit RANSAC [Zul08]


(a) Korrespondenzen des Palaisdatensatz zwischen DSC_0040 und dem Intensitätsbild von Standpunkt 4

(b) Korrespondenzen des Schillergartendatensatz zwischen DSC_0340 und dem Intensitätsbild

Abbildung 5.7: Von RANSAC gefundene Korrespondenzen. Die SIFT-Punkte des Intensitätsbildes wur-

den mit der Homographie in das Foto projiziert (grün markiert) und werden von den

zugehörigen SIFT-Punkte des Fotos (rot markiert) überlagert.


0019 0020 0080 0082 0086 0162 0096 0097 0104 0039 0040 0111 01880

50

100

150

200

250

Foto (DSC_∗ ) und Intensitätsbild des Palaisdatensatzes

SIF

T−

Zuo

rdnu

ngen

20%22%

16%

12%

10% 10%

31% 23% 25%

37%

26%36%33%

(a) Palaisdatensatz

0325 0327 0328 0329 0334 0339 0340 0342 03440

50

100

150

200

250

Foto (DSC_∗ ) und Intensitätsbild des Schillergartendatensatzes

SIF

T−

Zuo

rdnu

ngen

12%13%

12%

13%

8%

13%

11% 8% 10%

(b) Schillergartendatensatz

Abbildung 5.8: Ergebnisse der Bestimmung der richtigen Zuordnungen mit RANSAC


5.5 Diskussion der Ergebnisse

Die richtigen Zuordnungen konnten mit RANSAC und der Homographieberechnung als Modell erfolg-

reich aus der von SIFT ermittelten Menge von Korrespondenzen bestimmt werden.

In [BB07] und [BH07] wurde mit SIFT das Intensitätsbild eines Laserscanners mit grünem Laser und

ein Foto zugeordnet, wobei der Grünkanal des Fotos verwendet wurde. In beiden Artikeln wurde dabei

die Abbildung der Polarkoordinaten auf kartesische Bildkoordinaten als Intensitätsbild verwendet. In

[BB07] wird der Anteil der von RANSAC gefundenen richtigen Korrespondenzen mit ca. 20% und in

[BH07] mit 22% angegeben.

Dieses Ergebnis kann teilweise mit den Experimenten in dieser Arbeit bestätigt werden. Der Anteil der

richtigen Korrespondenzen weicht etwas ab und liegt durchschnittlich bei ca. 18%. Im Unterschied zu

den benannten Artikeln wurden die Datensätze mit einem Laserscanner im Nahinfrarotbereich aufge-

nommen. Der Beleuchtungsunterschied der Intensitätsbilder zu den Fotos ist daher wesentlich größer.

Damit sich die Umgebung eines SIFT-Punktes im Intensitätsbild zu der entsprechenden im Foto aber

nicht noch zusätzlich geometrisch unterscheidet, wurde das zentralperspektivische Intensitätsbild in den

Experimenten verwendet, was die Merkmalszuordnung zu begünstigen scheint.

Nur bei zwei der Palaisbilder konnte mit RANSAC kein Ergebnis innerhalb eines angemessenen Zeitrah-

mens berechnet werden. Daraus lässt sich ableiten, dass die Bestimung mitRANSAC zu zeitaufwändig

wird, wenn der Anteil der richtigen Korrespondenzen weniger als ca. 6% beträgt. In diesem Fall ist eine

extrem große Anzahl an Iterationen notwendig um die Inlier zu bestimmen.

Die Parametereinstellung des SIFT-Detektors scheint eine gute Balance zwischen Anzahl und Verteilung

der Merkmalspunkte zu ergeben, da die Korrespondenzen in verschiedenen Bildbereichen gefunden wer-

den. Der Beginn der Merkmalsdetektion in der zweiten Oktave, d.h. beifirstOctave= 1, bestimmt das

Ergebnis maßgeblich, da sonst die Menge an Merkmalspunkten mindestens doppelt so groß wäre und

die Anzahl an richtigen Korrespondenzen sich verringern würde. Der Beginn in der dritten Oktave, bei

firstOctave= 2, verringert die Anzahl der SIFT-Punkte im Vergleich zur zweiten Oktave wesentlich.

Die Wahl des Farbkanals des Fotos, der zur Detektion der Merkmalspunkte verwendet wird, hat keinen

großen Einfluss auf das Ergebnis. Die geschätzte Anzahl der richtigenKorrespondenzen verringert sich

meist etwas, jedoch ist kein genereller Trend erkennbar. Die richtig zugeordneten Merkmalspunkte des

Grün- und des Rotkanals befinden sich für ein Foto meist an denselben Stellen und weichen nur in we-

nigen Punkten ab. Diese Ergebnisse sind unter dem Vorbehalt zu betrachten, dass für eine automatische

Orientierungsberechnung auch die SIFT-Parameter vollautomatisch eingestellt werden müssten. Die hier

manuell vorgegebenen Parameter unterscheiden sich zwar kaum voneinander, allerdings weisen auch die

5.5. DISKUSSION DER ERGEBNISSE 57

Fotos ähnliche Eigenschaften auf. Für eine allgemeine Anwendung wäre eine dahingehende Auswer-

tung der Bildeigenschaften notwendig um geeignete SIFT-Parameter zu bestimmen. Eine ausführliche

Betrachtung dieser Problematik war nicht in dem gegebenem Zeitraum möglich,da dafür auch nicht

ausreichend Daten zur Verfügung standen.

Die besten Ergebnisse wurden mit dem Palaisdatensatz erzielt. Die inhomogene Struktur der Fassade

durch die verschieden hellen Steine sind sowohl für den Detektor als auch den Deskriptor vorteilhaft,

da sie in beiden Bildern recht gut zu erkennen sind und damit eine charakteristische Konstellation auf-

weisen. Außerdem wurden Punkte am Übergang vom Gebäude zum Himmelgefunden, also dort, wo

ohnehin starke Gradienten zu erwarten sind. Da der Blickwinkel sich zwischen den Fotos und den In-

tensitätsbildern nur wenig unterscheidet, stellt dies eigentlich keine besondere Herausforderung an den

Merkmalsdetektor. Warum so wenig richtige Zuordnungen bei den Fotos DSC_0030 und DSC_0031

etabliert wurden, bleibt allerdings unklar.

Der Schillergartendatensatz stellt dagegen etwas höhere Anforderungen, da das Gebäude nicht insge-

samt, sondern nur in Ausschnitten auf den Fotos abgebildet. Das Intensitätsbild zeigt jedoch das gesamte

Gebäude. Das heißt, die Unterschiede zwischen den Blickwinkeln der Bilder sind größer. Der Schiller-

garten hat zwar ebenfalls eine charakteristische Textur, die gut im Intensitätsbild zu erkennen ist, jedoch

ist sie lokal nicht so charakteristisch wie die des Palais, weshalb die Deskriptoren vermutlich weniger

differenziert sind und so die Zuordnung erschwert wird.

Beim Datensatz der Kommode konnte praktisch kein Ergebnis erzielt werden. Zum einen sind die Blick-

winkel vollkommen anders. Die Fotos geben Teile der Fassade sehr hochaufgelöst wieder. Dagegen ist

der entsprechende Teilbereich im Intensitätsbild nur sehr klein. Obwohl das Intensitätsbild den Bereich

enthält, wird natürlich nur ein Bruchteil der Merkmalspunkte in diesem Bereich detektiert. Das dieser

kleine Teil der gesamten SIFT-Punktmenge des Intensitätsbildes nicht erfolgreich mit der großen Anzahl

an Punkten vom Foto, die ausschließlich diesen Bereich abdecken, zugeordnet werden kann, ist nicht

überraschend. An der gesamten Fassade ist nur wenig Textur vorhanden, allerdings weist sie viel Selb-

stähnlichkeit auf, d.h. die vorhandenen Muster am Gebäude wiederholen sich, so das eigentlich keine

eindeutige Zuordnung möglich ist.

Die erfolgreiche Ermittlung von Punktkorrespondenzen mit SIFT ist also möglich, sofern sich der Blick-

winkel zwischen Intensitätsbild und Foto nicht zu stark ändert und ausreichend Textur in der Bildszene

vorhanden ist. Da es sich bei den Experimenten im Foto um Gebäude handelt, ist die Gefahr, dass die

Mekrmalsextraktion durch Verdeckung beeinträchtigt wird, nicht relevant.

Da das Intensitätsbild durch aktive Beleuchtung aufgenommen wird, kann auch der Objektbereich, der

im Foto eventuell durch Schatten verdeckt wird, uneingeschränkt erfasst werden, sofern er vom Scanner


aus sichtbar ist. Die Fotos, die für die Experimente verwendet wurden, weisen keine Schatten auf. Es ist

zu vermuten, dass Schattenbereiche im Foto die Merkmalsextraktion und Zuordnung durch große Gra-

dienten, die am Übergang von hellen Fassadebereichen zu dunklen Schatten entstehen würden, negativ

beeinflusst.

Die Ergebnisse, die für die relative Orientierung der Fotos über manuell bestimmte Korrespondenzen

zwischen dem Foto und der Laserscannerpunktwolke in Abschnitt 3.4 erzielt wurden, sind für eine vi-

suell ansprechende Texturierung der Punktwolke ausreichend. Durch die Verwendung von automatisch

festgelegten Zuordnungen könnte der Fehler, der durch die manuelle Messung und Auswahl der Punkte

entstanden ist, eliminiert werden und somit das Orientierungsergebnis, repräsentiert durch die Standard-

abweichungσ0 a posteriori, verbessern.

Mit den 2D-2D-Punktkorrespondenzen, die mit SIFT hergestellt wurden, sind durch das Intensitätsbild

sofort die entsprechenden 2D-3D-Korrespondenzen verfügbar. Die relative Orientierung der Fotos konn-

te jedoch nicht mit diesen Punktkorrespondenzen berechnet werden.Die Punkte weisen keine ausrei-

chende Verteilung im Bild auf. Außerdem ist die Anzahl der Punkte in den meisten Fällen zu gering.

Punktkorrespondenzen, die sich in den Bildern am Himmel befinden, können nicht in die Ausgleichungs-

rechnung zur Bestimmung der relativen Orientierung einbezogen werden, da dafür logischerweise keine

3D-Koordinaten gegeben sind.

Die Menge der Punktkorrespondenzen muss für eine automatische Berechnung der relativen Orientie-

rung also noch erhöht werden. Für gewöhnlich werden bei der Merkmalsextraktion mehrere Detektoren

eingesetzt um möglichst verschiedene Merkmale zu extrahieren und eine bessere Verteilung der Punkte

zu erzielen [TM07]. In [MS04] wird angegeben, das der Harris-Laplace-Detektor, der eine adaptierte

und skaleninvariante Version des Harris-Detektors darstellt, komplementäre Merkmale zu SIFT findet.

Der Einsatz dieses Detektors würde sich daher anbieten um noch weitere Merkmalspunkte zu finden.

Die Zuordnung könnte dann ebenfalls über SIFT-Deskriptoren der Merkmalspunkte erfolgen oder unter

Verwendung der Homographie, die mit den bereits hergestellten Punktkorrespondenzen berechnet wird.

Mit letzterer Möglichkeit könnten natürlich ebenfalls noch weitere SIFT-Punkte zugeordnet werden, die

zwar keine nächsten Nachbarn im Deskriptorraum sind, aber dennochan denselben Stellen in den Bildern

gefunden wurden.

Der Fehler, der sich einerseits durch die Messungenauigkeit der Entfernungsmessung und andererseits

durch die Footprintausdehnung des Laserscanners in die Punktwolkenrepräsentation kommt, wirkt sich

natürlich auch auf das Intensitätsbild aus und überträgt sich vor allem mit in die Orientierungsberech-

nung, solang die Laserscannerpunkte direkt als 3D-Koordinatenentsprechungen der 2D-Merkmalspunkte

des Intensitätsbildes verwendet werden. Durch Einpassung von Ebenen oder anderer geometrischer

5.5. DISKUSSION DER ERGEBNISSE 59

Primitive an Teile der Punktwolke kann die Genauigkeit der 3D-Koordinatenerhöht werden, wie in

([Kra07], S. 480) erläutert wird. Bei Gebäuden sollte dies für einen Teil der Punktwolke auch ohne große

Probleme möglich sein, sofern die entsprechenden geometrischen Voraussetzungen erfüllt sind. Das wäre

eine Variante das Intensitätsbild zu verbessern, indem die Intensitätswerteder 3D-Punkte auf der einge-

passten Ebene interpoliert werden. Anschließend könnte das Intensitätsbild von der Punktwolke bzw. der

Ebene generiert werden. Dies könnte die mögliche Auflösung des Intensitätsbildes erhöhen und gleich-

zeitig das Rauschen, das durch die diskrete Aufteilung der Punkte auf diePixel entstanden ist, reduzieren

und sich somit positiv auf die Merkmalsextraktion auswirken. Vor allem aberwäre das eine Möglichkeit,

die 3D-Koordinaten der Merkmalspunkte im Intensitätsbild exakter zu bestimmen. Der Schnittpunkt der

Raumgeraden, definiert durch Projektionszentrum und Merkmalspunktdes Intensitätsbildes, mit der in

die Punktwolke eingepassten Ebene würde genauere 3D-Koordinaten für den Merkmalspunkt ergeben

als ein direkt gescannter 3D-Punkt der Punkwolke.

Mit der Berechnung der relativen Orientierung des Fotos auf Basis derLaserscannerdaten könnte zwar

ein visuell ansprechendes Ergebnis berechnet werden, die Genauigkeit dieses Ansatzes konnte nicht

bestimmt werden, da keine ausreichenden Passpunktinformationen zur Verfügung standen.


61

6 Zusammenfassung

In dieser Arbeit wurde die Entwicklung eines Verfahrens zur automatischen relativen Orientierung von

Laserscannerpunktwolken und Bilddaten auf Basis von Intensitätsdatenangestrebt. Die so bestimmte

Orientierung sollte außerdem durch die Texturierung der Punktwolke mit den Farbinformationen aus

dem Bild visualisiert werden.

Als Erstes wurden dafür das Prinzip des Laserscannings und die Möglichkeit zur Darstellung der Punkt-

wolke als Bild untersucht. Aufgrund der beabsichtigten Weiterverarbeitung zusammen mit zentralper-

spektivisch aufgenommenen Fotos wurde eine ebenfalls zentralperspektivische Projektion der Punkt-

wolke gewählt. Im Anschluß daran wurde ein Werkzeug in C++ implementiert, das aus einer Laserscan-

nerpunktwolke auf diese Weise ein Intensitätsbild generiert.

Im Verlauf der Arbeit wurden Fotos für den verfügbaren Datensatz des Palais im Großen Garten ge-

macht. Außerdem wurde der Schillergarten sowohl mit einem Laserscanner als auch einer Kamera neu

aufgenommen. Ein Laserscannerdatensatz mit Fotos von der Alten Bibliothek(„Kommode“) in Berlin

stand zusätzlich zur Verfügung.

Zur Visualisierung der Orientierung des Fotos relativ zur Laserscannerpunktwolke wurde ein Werkzeug

in C++ innerhalb des CGVFrameworks implementiert. Damit können Punktwolkeneingelesen und mit

einem ausgewählten Foto texturiert werden, sofern die Orientierungsparameter des Fotos vorliegen. Um

das Visualisierungswerkzeug zu testen, wurden manuell Punktkorrespondenzen zwischen den Fotos und

der Punkwolke des Palaisdatensatzes erstellt. Die Parameter der relative Orientierung wurden über eine

Kleinste-Quadrate-Ausgleichung berechnet. Mit der Direkten LinearenTransformation wurden vorher

Näherungswerte für die Ausgleichung bestimmt. Das Ergebnis der mit diesenPunktkorrespondenzen

durchgeführten Orientierungsberechnung ist verglichen mit den bekannten Kalibrierungsdaten der Ka-

mera ungenügend. Eine Referenzorientierung konnte nicht berechnet werden, da für diesen Datensatz

keine Passpunktinformationen zur Verfügung standen. Ungeachtet dessen ist die aus diesen Orientie-

rungsparametern resultierende Texturierung der Punktwolke durch das Foto visuell zufriedenstellend.

Durch korrekte automatisch festgelegte Punktkorrespondenzen sollte dieGenauigkeit der Orientierungs-

berechnung und damit die Qualität der Texturierung folglich gesteigert werden können.

Für die automatische Festlegung von Punktkorrespondenzen wurde eineExtraktion und Zuordnung von

62 6. ZUSAMMENFASSUNG

geeigneten Merkmalen angestrebt. SIFT erfüllt die Anforderungen, diedie verwendeten Bilddaten an

die Merkmalsextraktion stellen und zeigte bei ähnlichen Aufgabenstellungenbereits positive Ergebnisse

[BB07], [BH07]. Deshalb wurde SIFT zur Merkmalsextraktion bei denanschließenden Experimenten

eingesetzt.

Zwischenzeitlich wurde die Auswertung von Linienmerkmalen in Betracht gezogen, da die Extrakti-

on von Merkmalspunkten zunächst keine zufriedenstellenden Ergebnise brachte. Experimente in die-

sem Zusammenhang ergaben allerdings, dass sich das Intensitätsbild im Gegensatz zum Tiefenbild der

Punktwolke nicht für die Auswertung von Linien eignet. Aus diesem Grundwurde dieser Ansatz wieder

verworfen und die Arbeit auf die Extraktion von Merkmalen mit SIFT konzentriert.

Die Merkmalsextraktion und -zuordnung mit SIFT wurde mit der VLFeat-Bibliothek [VF08a] in Mat-

lab durchgeführt. Anschließend wurde der Anteil an richtigen Korrespondenzen in den von SIFT be-

stimmten Zuordnungen ermittelt. Dazu wurden manuell Punktkorrespondenzen zwischen dem Fotos und

dem Intensitätsbildern über die Punktwolken hergestellt. Mit diesen Korrespondenzen wurde eine Hom-

mographie berechnet, mit der die SIFT-Punkte des Intensitätsbildes in das Foto projiziert wurden. Die

Punktpaare aus der Menge der von SIFT bestimmten Zuordnungen, bei denen der Abstand zwischen

SIFT-Punkt des Fotos und projiziertem Punkt des Intensitätsbildes einenfestgelegten Schwellwert unter-

schritt, wurden als richtige Zuordnungen klassifiziert. Diese Untersuchung der SIFT-Zuordnungen ergab,

dass in den Datensätzen von Palais und Schillergarten zwischen 4% und 38% der SIFT-Zuordnungen kor-

rekt waren. Für den Kommodedatensatz wurden jedoch praktisch keine richtigen Zuordnungen ermittelt.

Anschließend wurden deshalb Experimente mit RANSAC gemacht, um die richtigen Punktkorrespon-

denzen automatisch aus den SIFT-Zuorndungen zu ermitteln. Eine einfache Implementierung des RANSAC-

Algorithmus als Matlab-Skript mit einer Homographiebestimmung als Modell ergababer keine erfolg-

reichen Ergebnisse. Aus diesem Grund wurde dann die RANSAC Toolbox für Matlab verwendet, die

auch eine Homographiebestimmung bereitstellt. Damit konnte ein Anteil von ca. 18% richtigen Korre-

spondenzen an den SIFT-Zuordnungen für den Palais- und Schillergartendatensatz automatisch gefunden

werden. Die Experimente haben außerdem gezeigt, dass eine Bestimmung mit RANSAC nur dann in an-

gemessener Zeit möglich ist, wenn der Anteil der richtigen Korrespondenzen an den SIFT-Zuordnungen

mehr als 5% beträgt.

Die Orientierung der Fotos mit den auf diese Weise bestimmten Punktkorrespondenzen war allerdings

nicht erfolgreich. Für Bestimmung der Näherungswerte mit der Direkten Linearen Transformation und

der anschließenden Kleinste-Quadrate-Ausgleichung sind die automatischhergestellten Korresponden-

zen nicht ausreichend gleichmäßig über das Objekt verteilt. Außerdem istdie Punktmenge in vielen

Fällen zu gering.

63

Ein Verfahren für die automatische relative Orientierung konnte nicht vollständig entwickelt werden. Die

Anforderungen, die die Orientierungsberechnung an die Punktkorrespondenzen stellen, kann von dem

vorhergehenden Teilschritt, nämlich der Aufstellung von Korrespondenzen mit SIFT über RANSAC,

nicht sichergestellt werden. Hierzu wäre ein weiterer Zwischenschritt erforderlich, der die notwendigen

Bedingungen an die Punktkorrespondenzen für den Orientierungsschritt garantiert. Außerdem ist das

konzipierte Verfahren noch auf manuelle Parametereinstellungen für die Merkmalsextraktion in Abhän-

gigkeit von den bearbeiteten Daten angewiesen, ebenso wie die Vorgabeeines entsprechenden Paares

aus Foto und Intensitätsbild. Der nächste Schritt zu einem vollautomatischen Verfahren wäre folglich die

Ergänzung dieser Funktionalität und die Optimierung der Teilschritte.

Abschließend lässt sich festhalten, dass die Ergebnisse der durchgeführten Experimente zeigen, dass

dieser Ansatz vielversprechend ist. Das Resultat der Orientierungsberechnung über die manuell her-

gestellten Punktkorrespondenzen für das Visualisierungswerkzeug demonstriert, dass dieses Verfahren

geeignet wäre um ansprechend texturierte Objektmodelle automatisch zu erstellen.

64 6. ZUSAMMENFASSUNG

65

Literaturverzeichnis

[AW09] A LBERTZ, Jörg ; WIGGENHAGEN, Manfred: Taschenbuch zur Photogrammetrie und Fer-

nerkundung. 2. Edition. Wichmann Verlag, 2009

[BB07] BÖHM, Jan ; BECKER, Susanne: Automatic marker-free registration of terrestrial laser scans

using reflectance features. In:8th Conference on Optical 3D Measurement Techniques,

2007, S. 338–344

[BH07] BECKER, Susanne ; HAALA , Norbert: Combined Feature Extraction for Facade Recon-

struction. In:ISPRS Workshop on Laser Scanning 2007 and SilviLaser 200736 (2007), S.

44 – 49

[BSMM01] BRONSTEIN, I.N. ; SEMENDJAJEW, K.A. ; M USIOL, G. ; MÜHLIG, H.: Taschenbuch der

Mathematik. Verlag Harri Deutsch, 2001

[Com06] COMNINOS, Peter: Mathematical and Computer Programming Techniques for Computer

Graphics. Springer-Verlag, 2006

[Gim] GNU GIMP Quellcode V.2.6.8. – ftp://ftp.gimp.org/pub/gimp/v2.6/gimp-2.6.8.tar.bz2, lut-

funcs.c Zeile 53-59, Abgerufen am 08.04.2010

[GW02] GONZALEZ, Rafael C. ; WOODS, Richard E.:Digital Image Processing. 2. Edition. Prentice

Hall, 2002

[HL09] HERITAGE, George L. (Hrsg.) ; LARGE, Andrew R. (Hrsg.):Laser Scanning for the Envi-

ronmental Sciences. Wiley-Blackwell, 2009

[HZ03] HARTLEY, Richard ; ZISSERMAN, Andrew: Multiple View Geometry in computer vision.

2. Edition. Cambridge University Press, 2003

[Jäh02] JÄHNE, Bernd:Digitale Bildverarbeitung. Springer-Verlag, 2002

[Kra07] KRAUS, Karl: Photogrammetry - Geometry from Images and Laser Scans. 2. Edition.

Walter de Gruyter, 2007

[Low04] LOWE, David G.: Distinctive Image Features from Scale-Invariant Keypoints. In: Interna-

tional Journal of Computer Vision60 (2004), Nr. 2, S. 91–110

66 Literaturverzeichnis

[Luh00] LUHMANN , Thomas:Nahbereichsphotogrammetrie. Wichmann Verlag, 2000

[MS04] MIKOLAJCZYK , K. ; SCHMID, C.: Scale & Affine Invariant Interest Point Detectors. In:

International Journal of Computer Vision60 (2004), Nr. 1, S. 63–86

[MS05] MIKOLAJCZYK , Krystian ; SCHMID, Cordelia: A Performance Evaluation of Local Des-

criptors. In:IEEE Transactions on Pattern Analysis and Machine Intelligence27 (2005),

Nr. 10, S. 1615–1630

[Nie08] NIEMEIER, Wolfgang:Ausgleichungsrechnung - Statistische Auswertemethoden. 2. Edition.

Walter de Gruyter, 2008

[Rie06] Riegl Measurement Systems:Datenblatt LMS-Z420i. 2006. – Erhalten vom Institut für

Photogrammetrie und Fernerkundung

[Rie08] Riegl Laser Measurement Systems: Application Note AN-GI002. 2008.

– http://w3.riegl.com/uploads/tx_pxpriegldownloads/General-Information-

Distancemeter.pdf , Abgerufen am 15.03.2010

[ST09] SHAN, Jie (Hrsg.) ; TOTH, Charles K. (Hrsg.):Topographic laser ranging and scanning:

principles and processing. CRC Press, Taylor & Francis Group, 2009

[TM07] TUYTELAARS, Tinne ; MIKOLAJCZYK , Krystian: Local Invariant Feature Detectors: A

Survey. In:Foundations and Trends in Computer Graphics and Vision3 (2007), Nr. 3, S.

177–280

[VF08a] VEDALDI , A. ; FULKERSON, B.: VLFeat: An Open and Portable Library of Computer

Vision Algorithms. 2008. – http://www.vlfeat.org/, Abgerufen am 27.11.2009

[VF08b] VEDALDI , A. ; FULKERSON, B.: VLFeat: Dokumentation der C API. 2008. –

http://www.vlfeat.org/api/sift_8h.html, Abgerufen am 07.04.2010

[Wei] WEISSTEIN, Eric W.: Euler Parameters. Von MathWorld–A Wolfram Web Resource. –

http://mathworld.wolfram.com/EulerParameters.html, Abgerufen am 07.04.2010

[ZF03] ZITOVA , Barbara ; FLUSSER, Jan: Image registration methods: a survey. In:Image and

Vision Computing21 (2003), S. 977–1000

[Zul08] ZULIANI , M.: RANSAC toolbox for Matlab. 2008. –

http://vision.ece.ucsb.edu/˜zuliani/Research/RANSAC/RANSAC.shtml, Abgerufen am

27.3.2010

Documents

Diplomarbeit - TU Dresden · Diplomarbeit zur Erlangung des akademischen Grades Diplom-Informatikerin Entwicklung eines Verfahrens zur automatischen relativen Orientierung zwischen