Articles

Einführung in SIFT( Scale Invariant Feature Transform)

Deepanshu Tyagi

Folgen Sie

16. März 2019 · 7 min Lesezeit

SIFT steht für Scale-Invariant Feature Transform und wurde erstmals 2004 von D.Lowe, University of British Columbia, vorgestellt. SIFT ist Invarianz zur Bildskalierung und -drehung. Dieser Algorithmus ist patentiert, daher ist dieser Algorithmus im unfreien Modul in OpenCV enthalten.

lokalität: Merkmale sind lokal, so robust gegen Okklusion und Unordnung (keine vorherige Segmentierung)

  • Unterscheidungskraft: Einzelne Merkmale können mit einer großen Datenbank von Objekten abgeglichen werden
  • Menge: Viele Merkmale können auch für kleine Objekte generiert werden
  • Effizienz: nahezu echtzeitfähige Leistung
  • Erweiterbarkeit: Kann problemlos auf eine Vielzahl verschiedener Feature-Typen erweitert werden, wobei jeder Robustheit hinzufügt
  • Dies ist Teil einer Feature-Erkennung und -Anpassung der 7-Serie. Weitere Artikel enthalten

    • Einführung in die Merkmalserkennung und -anpassung
    • Einführung in den Harris Corner Detector
    • Einführung in SURF (beschleunigte robuste Funktionen)
    • Einführung in FAST (Funktionen aus dem beschleunigten Segmenttest)
    • Einführung in BRIEF (binäre robuste unabhängige Elementarfunktionen)
    • Einführung in ORB (Orientierte SCHNELLE und gedrehte KURZE Funktionen)

    SIFT ist ein ziemlich komplizierter Algorithmus. Der SIFT-Algorithmus besteht hauptsächlich aus vier Schritten. Wir werden sie eins nach dem anderen sehen.

    • Skala-Raum peak Auswahl: Potenzieller Ort zum Auffinden von Funktionen.
    • Keypoint Localization: Genaue Lokalisierung der Feature-Keypoints.
    • Orientation Assignment: Zuweisen der Ausrichtung zu Schlüsselpunkten.
    • Keypoint descriptor: Beschreibung der Keypoints als hochdimensionaler Vektor.
    • Keypoint Matching

    Scale-space Peak Selection

    Objekte der realen Welt sind nur in einem bestimmten Maßstab sinnvoll. Sie könnten einen Zuckerwürfel perfekt auf einem Tisch sehen. Aber wenn man die gesamte Milchstraße betrachtet, dann existiert sie einfach nicht. Diese mehrstufige Natur von Objekten ist in der Natur durchaus üblich. Und a scale space versucht, dieses Konzept auf digitalen Bildern zu replizieren.

    Der Skalierungsraum eines Bildes ist eine Funktion L (x, y, σ), das aus der Faltung eines Gaußschen Kernels (Unschärfe) in verschiedenen Maßstäben mit dem Eingabebild erzeugt wird. Maßstab – Der Raum ist in Oktaven unterteilt, und die Anzahl der Oktaven und der Maßstab hängen von der Größe des Originalbilds ab. Wir erzeugen also mehrere Oktaven des Originalbildes. Die Bildgröße jeder Oktave ist halb so groß wie die vorherige.

    Unschärfe

    Innerhalb einer Oktave werden Bilder mit dem Gaußschen Unschärfeoperator zunehmend unscharf. Mathematisch wird „Unschärfe“ als Faltung des Gaußschen Operators und des Bildes bezeichnet. Gaußsche Unschärfe hat einen bestimmten Ausdruck oder „Operator“, der auf jedes Pixel angewendet wird. Das Ergebnis ist das unscharfe Bild.

    Unscharfes Bild

    G ist der Gaußsche Unschärfeoperator und I ist ein Bild. Während x, y die Standortkoordinaten sind und σ der Parameter „Skalierung“ ist. Betrachten Sie es als die Menge an Unschärfe. Je größer der Wert, desto größer die Unschärfe.

    Gaußscher Unschärfeoperator

    DOG(Difference of Gaussian kernel)

    Jetzt verwenden wir diese unscharfen Bilder, um einen weiteren Satz von Bildern zu erzeugen, den Unterschied von Gauß (DoG). Diese Hundebilder eignen sich hervorragend, um interessante Schlüsselpunkte im Bild herauszufinden. Die Gaußsche Differenz ergibt sich als Differenz der Gaußschen Unschärfe eines Bildes mit zwei verschiedenen σ, sei es σ und kσ. Dieser Vorgang wird für verschiedene Oktaven des Bildes in der Gaußschen Pyramide durchgeführt. Es ist im folgenden Bild dargestellt:

    Schlüsselpunkte finden

    Bisher haben wir einen Skalenraum generiert und den Skalenraum verwendet, um die Differenz von Gauß zu berechnen. Diese werden dann verwendet, um Laplace von Gaußschen Näherungen zu berechnen, die skaleninvariant sind.

    Ein Pixel in einem Bild wird mit seinem 8 Nachbarn sowie 9 Pixel im nächsten Maßstab und 9 Pixel im vorherigen Maßstab. Auf diese Weise werden insgesamt 26 Kontrollen durchgeführt. Wenn es sich um ein lokales Extrema handelt, ist es ein potenzieller Schlüsselpunkt. Grundsätzlich bedeutet dies, dass der Schlüsselpunkt in dieser Skala am besten dargestellt wird.

    Keypoint Localization

    Key0points, die im vorherigen Schritt generiert wurden, erzeugen viele keypoints. Einige von ihnen liegen an einer Kante, oder sie haben nicht genug Kontrast. In beiden Fällen sind sie nicht so nützlich wie Funktionen. Also werden wir sie los. Der Ansatz ähnelt dem im Harris Corner Detector zum Entfernen von Kantenmerkmalen verwendeten. Bei kontrastarmen Merkmalen überprüfen wir einfach deren Intensitäten.

    Sie verwendeten die Erweiterung des Skalenraums in der Taylor-Serie, um eine genauere Position von Extrema zu erhalten, und wenn die Intensität an diesem Extrema kleiner als ein Schwellenwert ist (0,03 gemäß dem Papier), wird sie abgelehnt. Hund hat eine höhere Reaktion für Kanten, daher müssen auch Kanten entfernt werden. Sie verwendeten eine 2×2 hessische Matrix (H), um die Hauptkrümmung zu berechnen.

    Jetzt haben wir legitime Schlüsselpunkte. Sie wurden getestet, um stabil zu sein. Wir kennen bereits den Maßstab, in dem der Schlüsselpunkt erkannt wurde (er entspricht dem Maßstab des unscharfen Bildes). Wir haben also eine Skaleninvarianz. Als nächstes müssen Sie jedem Schlüsselpunkt eine Ausrichtung zuweisen, um ihn zur Rotationsinvarianz zu machen.

    uf der Skala, und die Gradientengröße und -richtung wird in dieser Region berechnet. Es wird ein Orientierungshistogramm mit 36 Bins erstellt, die 360 Grad abdecken. Angenommen, die Gradientenrichtung an einem bestimmten Punkt (im „Orientierungssammlungsbereich“) beträgt 18,759 Grad, dann wird sie in den 10-19-Grad-Behälter gelangen. Und die „Menge“, die dem Behälter hinzugefügt wird, ist proportional zur Größe des Gradienten an diesem Punkt. Sobald Sie dies für alle Pixel um den Schlüsselpunkt herum getan haben, hat das Histogramm irgendwann einen Peak.

    Der höchste Peak im Histogramm wird und jeder Peak über 80% davon wird auch berücksichtigt, um die Orientierung zu berechnen. Es werden Schlüsselpunkte mit derselben Position und Skalierung, aber unterschiedlichen Richtungen erstellt. Es trägt zur Stabilität des Matchings bei.

    Schlüsselpunktdeskriptor

    An diesem Punkt hat jeder Schlüsselpunkt eine Position, Skalierung und Ausrichtung. Als nächstes wird ein Deskriptor für den lokalen Bildbereich für jeden Schlüsselpunkt berechnet, der für Variationen wie Änderungen des Standpunkts und der Beleuchtung so unverwechselbar und invariant wie möglich ist.

    Dazu wird ein 16×16-Fenster um den Schlüsselpunkt genommen. Es ist in 16 Unterblöcke von 4×4 Größe unterteilt.

    For each sub-block, 8 bin orientation histogram is created.

    So 4 X 4 descriptors over 16 X 16 sample array were used in practice. 4 X 4 X 8 directions give 128 bin values. It is represented as a feature vector to form keypoint descriptor. Dieser Funktionsvektor führt zu einigen Komplikationen. Wir müssen sie loswerden, bevor wir den Fingerabdruck finalisieren.

    1. Rotationsabhängigkeit Der Merkmalsvektor verwendet Gradientenorientierungen. Wenn Sie das Bild drehen, ändert sich alles. Alle Gradientenausrichtungen ändern sich ebenfalls. Um eine Rotationsunabhängigkeit zu erreichen, wird die Drehung des Schlüsselpunkts von jeder Ausrichtung subtrahiert. Somit ist jede Gradientenorientierung relativ zur Ausrichtung des Schlüsselpunkts.
    2. Beleuchtungsabhängigkeit Wenn wir große Zahlen haben, können wir Beleuchtungsunabhängigkeit erreichen. Also wird jede Zahl (der 128) größer als 0,2 in 0,2 geändert. Dieser resultierende Merkmalsvektor wird wieder normalisiert. Und jetzt haben Sie einen beleuchtungsunabhängigen Merkmalsvektor!

    Schlüsselpunktübereinstimmung

    Schlüsselpunkte zwischen zwei Bildern werden durch die Identifizierung ihrer nächsten Nachbarn abgeglichen. Aber in einigen Fällen, Das zweitnächste Spiel kann dem ersten sehr nahe sein. Dies kann durch Lärm oder andere Gründe geschehen. In diesem Fall wird das Verhältnis von nächstgelegener Entfernung zur zweitnächsten Entfernung genommen. Wenn es größer als 0,8 ist, werden sie abgelehnt. Es beseitigt etwa 90% der falschen Übereinstimmungen, während nur 5% der richtigen Übereinstimmungen gemäß dem Papier verworfen werden.

    Implementierung

    Ich konnte sift mit OpenCV(3.4) implementieren. So habe ich es gemacht:

    Github-Link für den Code: https://github.com/deepanshut041/feature-detection/tree/master/sift

    Schreibe einen Kommentar

    Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.