Bildmerkmale werden genutzt, um qualitative Aussagen über Bildausschnitte treffen zu können. Ziel dabei sind repräsentative Merkmale zu erkennen. Mit dem Wissen können ähnliche Bildausschnitte auf anderen Bildern wieder gefunden, aufeinander gelegt oder zusammengeführt werden.

Allgemein kann das Problem in drei Schritte benannt werden:

  1. Detektionsschritt
  2. Markante Regionen in Bilddaten finden
  3. Deskriptor bilden
  4. Eigenschaften dieser Regionen in kompakter Form beschreiben
  5. Matching 

Anhand dieser Eigenschaften Übereinstimmungen zwischen verschiedenen Bildern des selben Objektes bestimmen

 

Grundlagen

Difference of Gaussian

Der Difference of Gaussian auch mit DoG abgekürzt ist ein Differenzbild, das aus unterschiedlichen Glättungsstufen hervorgeht. Es wird somit ein unscharfes Bild von einem anderen unscharfen Bild subtrahiert.Das Ziel vom DoG ist, dass die Kanten bei der Differenz hervorgehboen werden.

Auf das urpsrüngliche Bild wird der Gaußfilter mit dem Paraemter Sigma angwendet. Sigma gibt die Größe von dem Gaußfilter an. Durch Sigma ensteht ein Bild mit einer unterschiedlich starken Glättung bzw. bekommt einen Skalenraum. Dieser Schritt wird wiederholt, so dass zwei Bilder mit unterschiedlichen Glättung vorliegt. Diese beiden Bildern werden voneinandere abezogen. Das Ergebnis ist eine approximation der zweiten Ableitung. Die zweite Ableitung hat eine ähnlichkeit mit dem Mexican Hat Filter, ist es aber nicht. Das sogenannten DoG Bild kann für die Kantenerkennung verwendet werden.

 Diskreptor

Für einen Diskreptor gibt es in der Bildverarbeitung viele Synonyme wie beispielswiese Featurevektor und so weiter. Ein Diskreptor beschreibt mit einem Vektor möglichst genau einen Keypoint, der dann später auf einem anderen Bild dadurch identifiziert werden kann.

 

Blob Detection

 Laut Definition sind BLOBS (= Binary Large Objects) große binäre Datenobjekte. BLOBs sind analysierte Bildbereiche in dem benachbarte Pixel gleiche oder ähnliche Grauwerte aufweisen quasi die Extraktion von Merkmalen aus verbunden Pixeln. Für die Blobs muss eine geeignet Größe verwendet werden. Wenn beispielsweise die Größe des BloBs zu klein gewählt wird gehen zu viele details verloren und umgekehrt. Vergleicht man die verschiedenen Größen der BloBs von einem Objekt kann in der zweiten Ableitung die unterschiede erkannt werden, ob Informationen verloren gegangen oder zusammen gefügt worden sind.

 

 

  Integralbild

 

Hesse Matrix

Mit der Hesse-Matrix kann die Krümmung von differenziberan Funktionen bestimmt werden. Damit kann geprüft werden, ob ein Maximum bzw. Minimum vorliegt. Es werde alle Funktionen der zweiten partiellen Ableitung zusammengefasst. Zuerst werden in der ersten Zeile alle Ableitungen nach der ersten Variable abgeleitet, dann nach der zweiten Variable und so weiter. In der Abbildung XY ist Aussage mathematisch verallgemeinert worden.

 In der Regel spielt die Reihenfolge der Ableitung keine Rolle und ist mit diesem Artikel begründet worden.

 

KLT

Tomasi und Kanade entwickelte im Jahre 1991 einen Alogrithmus zur Detektion von Punktekorresponden, um Schlüsselpaare in Bildfolden erkennen zu können. Die Erkennung der Merkmale wird mit der Berechnung des optischen Flusses realsiert. Der optische Fluss eines Bildes ist ein Geschwindkeitsfeld in einem Bild (Vektorfeld), der ein Bild aus einer Sequenz in das daraufolgende überführt. Der Methodenname Kanade-Lucas-Tomasi feature tracker lässt sich mit den Namen der begründer erklären. Der Ansatz lässt sich in drei Abschnitte unterteilen:

  1. Extraktion guter Merkmalspunkte
    Initial wird der Algorithmus mit einem Bild initialisert. Aus dem Bild werden zunächst die Schlüsselpunkte anhang der Gradientenberechnung in die x- und y- Richtung berechnet. Die Schlüsselpunkte müssen einen gewissen mindesabstand einhalten damit die Features von dem ganzen Bild gut abgedeckt sind. Der beschriebene Schritt wird für jedes Bild angwendet.
  2. Findung von Punktekorrespondenzen
    Der Tracker wird mit zwei aufeinanderfolgenden Bilder und den Schlüsselpunken aus dem ersten Bild initialisiert. Für die Schätzung der Bewegung wird das translatorische Bewegunsmodell und die Newton-Rapshon-Methode verwendet. Das translatorische Bewegungsmodell geht davon aus, dass das Bild in zwei Handlungen unterteilt ist. Zum einem in Vordergrund und Hintergrund. Das Modell geht davon aus, dass sich auf dem festen Hintergrund Objekte bewegen, die sich auch verdecken können. Die Newton-Rapshon-Methode ist ein mathematisches Verfahren, um nichtlineare Gleichung zu lösen. Der KLT-Alogrithmus vergleicht den Schlüsselpunkt eines Bildauschnitts von dem ersten Bild mit dem vom zweiten Bild. Mit jedem weiteren Durchlauf wird der Bildauschnitt verkleinert.
  3. Verwerfung und Neufindung von Merkmalspunkten
    Die Bildmerkmale können wertlos werden indem sie verdeckt werden oder nicht mehr in einem Berreich vorhanden sind. Bei diesem besonderen Fall werden die Schlüsselpaare verworfen. Unterschreiteten jedoch die Schlüsselpaare eine bestimmte mindestanzahl von Merkmalen müssen weitere Merkmale extrahiert und in der Liste der zu verwendeten Punkte aufgenommen werden.

In der Abbildung XY wird durch ein Flow chart der iterative Ablauf des KLT-Verfahrens visuell gezeigt.

Leider weißt dieses Verfahren Schwächen auf, um eindeutige Merkmale beispielsweise in der Gesichtserkennung detektieren zu können.

 

SIFT

Das Verfahren ist von D. Lowe 1999 erstmal vorgestellt worden und steht für scale-invariant feature transform. Das Merkmal von SIFT ist, dass als Methode zur Auffindung von Punktkorrespondenzen in Bildfolgen die Eindeutigkeit eines Keypoints in seiner Umgebung extrahiert wird. Die Bildmerkamle sind invariant gegen Skalierung, Translation und Rotation. Neben der Lage werden mit den Keypoint Größe und Breite erfasst.

Lowe hat im Jahre 2004 seine Algorithmus verbessert und dieser lässt sich in vier Schritte aufteilen:

  1. Ermittlung potentieller Keypoints
    Zuerst werden die potentiellen Keypoints ermittelt. Dafür wird DoG oder eine DoG-Prymaide aufgebaut, um potenzielle interessante Punkte zu identifizieren, indem in ihr nach Maxima oder Minima gesucht wird.
  2. Filterung und Subpixellokalisierung
    Anschließend werden diese Punkte nach gewissen Kriterien gefiltert. Für dieverbleibenden Keypoints wird eine subpixel-genaue Position berechnet.
  3. Berechnung der Keypoint-Orientierung
    Für jeden Keypoint wird eine Orientierung ermittelt. Falls ein Punkt mehr al seine dominante Richtung besitzt, werden weitere Keypoints an dieser Positionmit unterschiedlichen Orientierungen angelegt
  4. Berechnung der Deskriptoren
    Als letztes wird für jeden verbliebenen Keypoint ein einzigartiger,  charakteristischerFeature-Vektor berechnet. Dieser Feature-Vektor muss invariant gegenber verschiedenen Änderungen sein.

Vorgehen

  1. Blobkandidaten finden
    • Skalenraum aufbauen
      • Glättung mit Gaußfiltern mit steigendem Sigma (=steigender Breite)
      • Differenz zum Original bilden
        • DOG
        • Approximation der 2. Ableitung
    • Optimale Skala bzw. Position für jeden Blob finden
      • Lokales Maximum des DoG bzg. Raum und Skala
      • Verbesserung der Genauigkeit mit Taylorreiehen-Entwicklung
    • Zu Null setzten, heraus kommt die Inverse der Hesse-Matrix inkl. Gradienten bezogen auf DoGs lokal an Optima-Positionen
    • Nun haben wir die Keypoints (xDach, yDach, SigmaDach)
  2. Reduktion der Kandidaten (Keypoints eliminieren)
    • Schwelle auf die DoG-Punkte anwenden
    • Kandidaten an Kanten eliminieren. Hier haben wir aber sehr unterschiedliche Hauptkrümmungen. Wir können sie mit Hilfe einer Hesse-Matrix unterscheiden
    • Hesse-Matrix für alle Kandidaten bzw. der DoGs bilden
    • Trick: Wir nutzen die Spur und die Dterminante der Hesse-Matrix und erhalten das Verhältnis der Eigenwerte der Matrix
  3. Merkmale zur Beschreibung des Kandidaten bestimmten
    • Für jeden Kandidaten (=Blob) möchte man rotationsunabhängige die Hauptorienteirung des Blobs finden
    • Gradienten auf Originalbild berechnen
    • Lokales Orientierungshistogramm
      (Eine Schwelle auf dem Histogramm zeigt die Hauptrichtung des Kandidaten an (wenn Werte diese Schwelle übersteigen)
      • Mit Gewichtung 1 (Gradientenlänge)
      • Mit Gewichtung 2 (Gaußkern)
    • Am Ende erhält man einen 4x4x8 = 128-dimensionalen Vektor, der dann in den Klassifikator gesteckt wird.

 SURF

Surf ist die abkürzung für Speeded Up Robust Features und bedeutet auf deutsch beschleunigt, robuste Merkmale. SURF ist stark an SIFT angelehnt, jedoch unterscheiden sie sich in der noch radikaleren Approximierung durch den Ansatz der Verwendung von der Fast-Hessian Detector, dass eine approximation von der Hesse-Matrix für einen gegeben Bildpunkt ist. Dadurch, dass die Hesse-Matrix Box-Filter und Integralbilder erlaubt kann SURF mit einer besseren Performance überzeugen.

Der SURF- kann wie der Sift-Alogrithmus in drei Teilbereichen unterteilt werden:

  • Merkmalsdetektion
  • Deskriptor bestimmen
  • Matching der Deskriptoren

Die Unterscheid zu SIFT ist, dass bei der (Merkmals-)detektion zur schnelleren Berechnung Integralbilder verwendet werden. Zudem verwendet der Detektor für das auffinden von Interessenpunkten die Hesse-Matrix und mit einem Box-Filter approximiert und keinen Mittelwertsfilter wie bei SIFT. Damit ist die Rechenzeit erheblich reduziert worden. Sobald die Prozesse auf der GPU ausgelagert worden sind, kann noch mehr Rechenzeit eingespart werden. Zudem hat ist Länge 64 des Vektors vom Deskriptor, aber es kann auf eine Länge von 128 erweitert werden. Im Gegensatz ist die Länge von 128 bei SIFT nicht veränderbar.

 

Gegenüberstellung der Implementierung von SIFT und SURF

Im Paper Comparing several implemantations of two recently published feature detecors von Bauer, Sunderhauf und Protzel stellen sie einige implementierungen von SIFT und SURF gegenüber.
Folgende Implrementierungen sind verwendet worden:

  • SIFT
    • Orignal imprlemantation by David Lowe
    • SIFT++
    • LTI-lib SIFT
  • SURF
    • SURF
    • SURF -d

Als Resultat hat sich heraus gestellt, dass SIFT und SIFT++ eine höhere Anzahl von Keypoints ermittelt hat, aber im Gesamten die Qualität ähnlich zu SURF ist. Jedoch ist aufgefallen, dass die LTI-lib für SIFT fehlerhaft ist bzw. nicht den orginalen Algorithmus von Lowe folgt und somit ein schlechtes Verhältnis von korrekt erkannten übereinstimmungen mit sich zieht. Im Weitern ist die Rotation der Algorithmen getestet worden, die alle in etwa gleich gut abgeschnitten haben. Bei der Skalierung von dem Bild hat der SIFT Algorithmus leicht schwächen. Denn wenn die Größe der Skalierung verändert wird, fallen die korrekten Übereinstimmungen. Sobald das Bildrauschen erhöht wird, zeigen alle Algorithmen bei der Detektion von den Keypoints schwächen auf. Bis zu einem gewissen Ausmaß können alle Algorithmen mit der Beleuchtung umgehen. Andernfalls können nicht genügend Keypoints gefunden werden. Wird beispielsweise der Winkel von den Bildern verändet haben alle Algorithmen bereits ab 10 Crad schwächen und die Anzahl der Keypoints sinkt signifikant.

Zusammenfassen hat Bauer, Sunderhauf und Protzel festgestellt, dass SIFT nach Lowe und SIFT++ die Beste Peformanz in der er übereinstimmenden Treffer der Keypoints und von dem Verhältnis haben. Im Gegensatz ist die Geschwindigkeit von dem Algorithmus von SURF schneller. Schlussfolgernd ist das Ergebnis vom Paper, dass SURF tatsächlich überlegender als SIFT ist, weil die Geschwindigkeit schneller ist. Es werden zwar nicht alle Keypoints gefunden, aber es werden dennoch genügend und gute Keypoints gefunden, weswegen dieses Argument vernachlässigt werden kann.

 

 


Quellen:

[1] https://www.informatik.hu-berlin.de/de/forschung/gebiete/viscom/teaching/media/cphoto10/cphoto10_04.pdf

[2] http://www1.inf.tu-dresden.de/~ds24/lehre/bvme_ss_2012/bv_bmerk.pdf

[3] Color texture classification by integrative Co-occurrence matrices, Christoph Palm, August 2013

[4] Vorlesung von Prof. Dr. Christoph Palm, Bildanalyse und Machien Learning, WiSe 2017, OTH Regensburg

[5] Implmentierung und Evaluierung von SIFT auf der GPU, Sven-René von der Heidt, Juli 2007, Universität Koblenz

[6] Detection and Tracking of Point Features, Carlo Tomasi and Takeo Kanade, April 1991

[7] Kanade-Lucas-Tomasi (KLT) Feature Tracker, Jae Kyu Suhr, 2009, Yonsel University

[8] Difference of Gaussian (DoG), Ruye Wang, 2016

[9] Skript zur Vorlesung Technische Bildverarbeitung, Dipl.-Ing. Dirk Mohr, 2010, Hochschule Bochum

[10] Keypoint-Detektion und Deskriptoren-Berechnung auf der Grafikkarte, Fabian Zimmermann, Februar 2007, Technische Universität Kaiserslautern

[11] Distinctive Image Features form Scale-Invariant Keypoints, David G. Lowe, January 2004, University of British Columbia Vancouver

[12] Speeded-Up Robust Features (SURF), Herbert Bay, Andreas Ess, Tinne Tuytelaars, and Luc Van Gool, 2006, ETH Zurich

[13] Image-based Tracking, Jens Maiero, September 2009, Hochschule Bonn-Rhein-Sieg

[14] Erweiterung von Fast Retina Keypoints um Farbinformation, Anselm Brachmann, Oktober 2013, Freie Universität Berlin

[15] Digitale Bildverarbeitung für die automatisierte Auswertung in der Architekturphotogrammetrie, Dipl.-Ing. Frank Henze, Oktober 2015, nversität Cottbus-Senftenberg

Suche

Kategorien

Wir nutzen Cookies auf unserer Website. Einige von ihnen sind essenziell für den Betrieb der Seite, während andere uns helfen, diese Website und die Nutzererfahrung zu verbessern (Tracking Cookies). Sie können selbst entscheiden, ob Sie die Cookies zulassen möchten. Bitte beachten Sie, dass bei einer Ablehnung womöglich nicht mehr alle Funktionalitäten der Seite zur Verfügung stehen.