Optimierung von Merkmalsvektoren
Optimierung von
Merkmalen für die
Bildsuche
Vertieferpraktikum Photogrammetrie SS 2004
Frank Klughardt
Optimierung von Merkmalsvektoren
Frank Klughardt
Übersicht
I.
Einführung in SIFT Features von Lowe
1)
2)
II.
Optimierung von SIFT Featurevektoren
1)
2)
3)
III.
Eigenschaften
Aufbau
Wiederholte Muster
Ähnliche Featuredeskriptoren
Entfernen ähnlicher Features
Analyse-Tool
1)
2)
3)
4)
Fundamental Matrix
Korrelationsverfahren
Anwendung
Erweiterung
IV.
Weitere Optimierungsmöglichkeiten
V.
Quellen
VI.
Softwaredemonstration
Vertieferpraktikum Photogrammetrie SS 2004
2
Optimierung von Merkmalsvektoren
Frank Klughardt
Eigenschaften der SIFT Features



Invariant gegen
•
Skalierung
•
Rotation
Robust gegenüber
•
Affine Verzerrung
•
Änderung des Blickpunkts
•
Verrauschen
•
Änderung der Beleuchtung
•
Verdeckung (bei Objekterkennung)
Trotzdem unterscheidbar
Hohe Wahrscheinlichkeit für korrektes Matching
Vertieferpraktikum Photogrammetrie SS 2004
3
Optimierung von Merkmalsvektoren
Frank Klughardt
Aufbau eines Features

Koordinaten im Bild (x,y)
(im folgenden als Keypoint
bezeichnet)

Maßstab (Extremum im Skalenraum)

Orientierung

128 dimensionaler geordneter
Deskriptionsvektor
(im folgenden als Keypointvektor
bezeichnet)

Auswahl von Keypoints:
Finde Extrema im Skalenraum durch
Aufbau einer “Difference of Gaussian“Bildpyramide
Approximation der maßstabsinvarianten
“Laplace of Gaussian“-Funktion
Gradientenstärke und -orientierung berechnen
Für genauere Information
siehe (3)
Gewichtung mit
kreisförmigen
Gaußkern
Vertieferpraktikum Photogrammetrie SS 2004
4
Optimierung von Merkmalsvektoren
Frank Klughardt
II. Optimierung von SIFT Features
Motivation:
1. Optimierung (Reduktion) der Datenbankgröße
2. Verbesserung der Matching-Eigenschaften der Keypointvektoren
(unter “Weitere Optimierungsmöglichkeiten“)
Methode:
Entfernen von Features mit folgenden Eigenschaften
•
Schlecht geeignet zum Matchen innerhalb eines Bildes
•
Schlecht geeignet zur Zuordnung (Wiederfinden) von
Bildern in der Datenbank
Vertieferpraktikum Photogrammetrie SS 2004
5
Optimierung von Merkmalsvektoren
Frank Klughardt
Wiederholte Muster
Idee:
Ersetzung von Keypointvektoren, die wiederholte Muster beschreiben, durch
einen Repräsentanten (Mittelung).
Problem:
• Aufgrund der Individualität der Keypointvektoren
existieren solch “Wiederholte Muster“-Features
nicht, bzw. sind schwer als solche zu
identifizieren.
• Mittelung zur späteren Zuordnung von Features
in der Datenbank nicht sinnvoll, da
ausschließlich die Features in der Datenbank
gespeichert werden.
Vertieferpraktikum Photogrammetrie SS 2004
6
Optimierung von Merkmalsvektoren
Frank Klughardt
Ähnliche Keypointvektoren
Idee:
Ähnliche Keypointvektoren sicherlich schlecht zum Matching geeignet
(liefern oft falsche oder mehrdeutige Zuordnung)
Entfernen von Keypointvektoren, die:
• Zu geringen Abstand haben (Schwellwert ?)
• Clustering Verfahren, z.B. K-Means
(Problem: Anzahl der Cluster im vornherein
nicht bekannt)
• Hier: Euklidische Distanz als Abstandsmaß
(Brute Force)
• Andere Abstandsmaße ebenfalls möglich
(z.B. Mahalanobis Distanz), jedoch nicht
erfolgsversprechend [siehe (3)]
Vertieferpraktikum Photogrammetrie SS 2004
7
Optimierung von Merkmalsvektoren
Frank Klughardt
Entfernen ähnlicher Features
Untersuchung zur Legitimation:
• Euklidische Distanz zwischen gematchten Keypointvektoren
• Verhältnis des Besten zu zweitbestem Match
(Nächstes zu zweitnächstem Match)
• Mit steigendem Verhältnis
• Zahl der falschen Matches steigt
• Anzahl der Matches nimmt ab
einem Verhältnis von 0.7 ab
Vertieferpraktikum Photogrammetrie SS 2004
8
Optimierung von Merkmalsvektoren
Frank Klughardt
III. Analyse Tool
Motivation:
Es wird ein Bewertungmaß für die Optimierung benötigt.
Optimierung soll richtige Matches erhalten und falsche Matches entfernen.
Anwendung des Tools:
 Qualität des Matchings
• Anteil der richtigen Matches
• Anzahl der richtigen Matches (absoluter Wert)
 Schwellwert für Parameter
• z.B. Wert für Maximalabstand zum Entfernen von Matchings
Vertieferpraktikum Photogrammetrie SS 2004
9
Optimierung von Merkmalsvektoren
Frank Klughardt
Fundamental Matrix
 Robustes Verfahren benötigt, da hohe Anzahl falsche Matches möglich
RANSAC Verfahren
 “Um nicht das Rad neu zu erfinden“
Benutzung der “Open Computer Vision“ (OpenCV) Library von Intel
• Verfahren bereits implementiert und optimiert
• Interface für diverse Bilddateitypen implementiert
• (Beschränktes) GUI nutzbar
• Auch andere Verfahren zum Bestimmen der Fundamental Matrix nutzbar
- 7 Punkte Verfahren
- 8 Punkte Verfahren
- Least Squares Verfahren
- Probleme:
- schlechte Dokumentation (insbes. der relativ neuen Funktionen)
- Merkwürdige dynamische Speicherverwaltung
Viel Trial and Error
Hoher Zeitaufwand
Vertieferpraktikum Photogrammetrie SS 2004
10
Optimierung von Merkmalsvektoren
Frank Klughardt
Fundamental Matrix
 “Fundamental Matrix“-Bedingung erfüllende Matches als richtig kennzeichnen
 Rest der Matches als falsch kennzeichnen
 Problem:
• Zu einem Keypoint in Bild A erfüllen alle Punkte auf Epipolarlinie in Bild B
die “F. Matrix“-Bedingung
• Aufgrund der Geometrie von Hausfassadenaufnahmen
- wenig Rotation
- Translation nur in X, Z-Richtung
Epipolarlinien verlaufen parallel zu Strukturen (Fenster, Türen,
Außenverkleidung, …) der Hausfassade
Vertieferpraktikum Photogrammetrie SS 2004
11
Optimierung von Merkmalsvektoren
Frank Klughardt
Beispiel
Match erfüllt “F. Matrix“-Bedingung
Vertieferpraktikum Photogrammetrie SS 2004
12
Optimierung von Merkmalsvektoren
Frank Klughardt
Korrelationsverfahren
 Vergleich der 2 Profillinien zwischen 2 “richtigen“ Matches in beiden Bildern
 Funktioniert nur
• Bei Punkten auf Ebene = Hausfassade (Vorteil: Vordergrund wird gefiltert)
• wenn Verdeckung durch Vordergrund nicht zu groß ist
• wenn perspektivische Änderung nicht zu große Abschattung hervorruft
• Mittelung über mehrere Profillinien (da auch Punkte im Vordergrund als
Kandidaten ausgewählt werden)
• Probleme:
- Profillinie muss diskret “gesamplet“ werden
- Äquidistantes “Sampling“ in Bild A ist in Bild B nicht direkt
rekonstruierbar
- Samplingpunkte genähert berechenbar durch Epipolargeometrie
- Falsche Punkte (im Vordergrund) liefern schlechte Profillinien
Mittelung über mehrere Random Keypoints
Vertieferpraktikum Photogrammetrie SS 2004
13
Optimierung von Merkmalsvektoren
Frank Klughardt
Problem: Samplingpunkte
1) Suche zu jedem Match ein anderes “richtiges“ Match
2) Werte Profillinie in Bild A an Samplingpunkten aus
3) Werte Profillinie in Bild B an “zugehörigen“ Samplingpunkten aus?
4) Berechne Korrelation beider Grauwert-“Funktionen“


Problem:
•
Bestimmung der “zugehörigen“ Samplingpunkte
•
Äquidistantes Sampling in Bild B würde falsche Samplingpunkte liefern
Lösung:
•
Fundamental Matrix und damit Abbildung zwischen Bildern bekannt
•
Berechne damit 1-D projektive Abbildung zwischen den Profillinien
•
Zu jedem Samplingpunkt in Bild A ist Epipolarlinie in Bild B bekannt
•
Schnitt von Epipolarlinie und Profillinie liefert korrekten “zugehörigen“
Samplingpunkt
Problem: Epipolarlinie und Profillinie parallel ? (siehe Falsche Matches)
Vertieferpraktikum Photogrammetrie SS 2004
14
Optimierung von Merkmalsvektoren
Frank Klughardt
Problem: Samplingpunkte
Vertieferpraktikum Photogrammetrie SS 2004
15
Optimierung von Merkmalsvektoren
Frank Klughardt
Beispiel: Samplingpunkte
Vertieferpraktikum Photogrammetrie SS 2004
16
Optimierung von Merkmalsvektoren
Frank Klughardt
Vorteile und Probleme
Vordergrundfilterung
Vertieferpraktikum Photogrammetrie SS 2004
Fehlerbehaftetes Verfahren
17
Optimierung von Merkmalsvektoren
Frank Klughardt
Problem: Falsche Matches
Vertieferpraktikum Photogrammetrie SS 2004
18
Optimierung von Merkmalsvektoren
Frank Klughardt
Problem: Falsche Matches
1) Suche zu jedem Match ein anderes “richtiges“ Match
2) Werte Profillinie in Bild A äquidistant aus
3) Werte Profillinie in Bild B an Schnittpunkten aus
4) Berechne Korrelation beider Grauwert-“Funktionen“
Liegt Korrelationswert unter Schwellwert
Kennzeichne Match als falsch

Problem:
• (anderes) “richtiges“ Match erfüllt nur “F. Matrix“-Bedingung
•
•

Kann auch falsches Match sein
(Fall tritt hier sehr häufig auf: siehe Aufnahmegeometrie)
Profillinienkorrelation liefert (wahrscheinlich) unkorreliert
Lösung:
• Wiederhole Vorgang mit mehreren zufällig ausgewählten Matches
• Mittelung über Korrelationen liefert robustes Ergebnis
• Liefert für falsche Matches auch bei richtigem Match als Partner
(wahrscheinlich): unkorreliert
• Falls Epipolarlinie und Profillinie parallel
wähle anderes Match
Vertieferpraktikum Photogrammetrie SS 2004
19
Optimierung von Merkmalsvektoren
Frank Klughardt
Beispiel:Random Points
Vertieferpraktikum Photogrammetrie SS 2004
20
Optimierung von Merkmalsvektoren
Frank Klughardt
Anwendung

Anwendung 1. Verfahren: Bestimmen der Fundamental Matrix


Parameter (OpenCV):
•
Erlaubte Pixelabweichung von Epipolarlinie
(empirisch: 5 Pixel = 0.5% der Bildbreite)
•
Zuverlässigkeit RANSAC (99%)
Iteratives Anwenden von 2. Verfahren: Korrelationsverfahren

Parameter:
•
Anzahl der zufälligen Matches (Anzahl Profillinien)
“Random Points“
(empirisch: 10 bis 20)
•
Anzahl der Samplingpunkte (Stützstellen auf Profillinie)
(empirisch: 30 bis 40)
•
Schwellwert für Korrelationswert in jeder Iteration erhöhen
Nach jeder Iteration fließen nur verbleibende “richtige“ Matches ein
(empirisch: Startwert: 0.2 in 0.1-Schritten mit 3 bis 5 Iterationen)
Vertieferpraktikum Photogrammetrie SS 2004
21
Optimierung von Merkmalsvektoren
Frank Klughardt
Anwendung in der Projektpipeline

Filter für Matchingverfahren

Um Relative Orientierung zu berechnen reicht ein kleiner Teil der, aus
der KD-Tree Suche, gelieferten Matches

Parameter können entsprechend scharf gewählt werden

Hohe Wahrscheinlichkeit für Korrektheit der gefilterten Matches
Vertieferpraktikum Photogrammetrie SS 2004
22
Optimierung von Merkmalsvektoren
Frank Klughardt
Erweiterung

“Fundamental Matrix“-Verfahren
•

Filterung des Vordergrunds
Korrelationsverfahren
•
Farbbilder (separate Korrelation auf Farbkanälen bei RGB)
•
HSV-Farbmodell
•
Statt Vergleich “Grauwert“-Funktionen über Korrelation
- Berechnung der 2D projektiven Abbildung (zwischen Hausfassaden)
- Histogrammvergleich
•
Gewichtung der Profillinien über Differenz der Grauwerte, da
homogene Regionen immer hohe Korrelation liefern
•
Problem: Mehrere Hausfassaden in einem Bild
Graphen
- Knoten = Matches
- Kanten = Profillinien zwischen Matches mit hoher Korrelation
-
Farbkanal ist unkorreliert gegen Helligkeitsänderung
Untersuchung auf Cliquen oder Zusammenhangskomponenten
liefert dann Punktwolken, die auf Fassaden verteilt sind
Vertieferpraktikum Photogrammetrie SS 2004
23
Optimierung von Merkmalsvektoren
Frank Klughardt
IV. Weitere Optimierungsmöglichkeiten

Nutzung anderer Features [siehe (5)]

Einbindung Kantendetektoren und Segmentierung

Erweiterung der SIFT Featurevektoren
•
Farbinformation
•
Elliptisches Gradientenfenster
Vertieferpraktikum Photogrammetrie SS 2004
24
Optimierung von Merkmalsvektoren
Frank Klughardt
V. Quellen
(1)
‘Ausarbeitung Praktikum SS 2004 ‘Optimierung von SIFT Features zum Wiederfinden von
Hausfassaden‘, Andreas Wedel, 18. Juli 2004
(2)
‘Object recognition from local scale-invariant features‘, D. G. Lowe
http://www.cs.ubc.ca/spider/lowe/papers/iccv99.pdf
(3)
‘Distinctive Image Feature from Scale-Invariant Keypoints‘, David G. Lowe, 2004
http://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf
(4)
‘Improving SIFT Features / Finding Planes in Hallways‘, C. Gustavsson, A. Hui and M. Turitzin
(5)
‘A performance evaluation of local descriptors‘, K. Mikolajczek, C. Schmid, 2003
http://www.inrialpes.fr/movi/people/ Schmid/publi/mikolajczyk_cvpr2003.pdf
(6)
‘An affine invariant interest point detector‘, K. Mikolajczek, C. Schmid
http://www.inrialpes.fr/movi/publi/Publications/2002/MS02/mikolajc_ECCV2002.ps.gz
(7)
‘Invariant Feature from Interest Point Groups‘, Matthew Brown and David Lowe
http://www.bmva.ac.uk/bmvc/2002/papers/92/full_92.pdf
Vertieferpraktikum Photogrammetrie SS 2004
25
Optimierung von Merkmalsvektoren
Frank Klughardt
NOCH FRAGEN ???
VI. Softwaredemonstration
Vertieferpraktikum Photogrammetrie SS 2004
26

Optimierung von Bildmerkmalen