Scale-Invariant Feature Transform (SIFT)

Die skalierungsinvariante Merkmalstransformation (SIFT) ist ein klassischer Algorithmus der Computer Vision, der markante lokale Schlüsselpunkte in einem Bild findet und jeden davon mit einem Vektor aus 128 Zahlen beschreibt, der sich bei Skalierung oder Drehung des Bildes weitgehend nicht verändert. Der Abgleich dieser Deskriptoren ermöglicht es Software, zwei Fotos derselben Szene miteinander zu verknüpfen, die aus unterschiedlichen Entfernungen und Blickwinkeln aufgenommen wurden. So werden überlappende Fotos zu einem Panorama zusammengefügt. SIFT ist ein von Hand entwickeltes Verfahren zur Merkmalsextraktion, im Gegensatz zu den erlernten Merkmalskarten eines Faltungsnetzes.

Ursprung und Grundidee#

David Lowe von der University of British Columbia stellte SIFT 1999 in der ICCV-Arbeit Objekterkennung anhand lokaler skalierungsinvarianter Merkmale vor und beschrieb das Verfahren ausführlich in „Markante Bildmerkmale anhand skalierungsinvarianter Schlüsselpunkte“ im International Journal of Computer Vision von 2004. SIFT-Merkmale sind invariant gegenüber Skalierung und Drehung und lassen sich auch bei erheblichen affinen Verzerrungen, Änderungen des 3D-Blickwinkels, Rauschen und Beleuchtungsänderungen zuverlässig abgleichen. Das Verfahren war patentiert; das Patent lief 2020 aus. OpenCV überführte SIFT mit Version 4.4.0 aus seinem Contrib-Repository in die Hauptbibliothek.

Objekte haben auf Fotos keine feste Größe, daher muss ein Detektor Strukturen in jeder Größe erkennen. SIFT erstellt einen Skalenraum, indem wiederholt Gaußsche Weichzeichnung mit zunehmender Stärke angewendet und das Bild in Gruppen, sogenannten Oktaven, verkleinert wird.

So funktioniert SIFT#

Der Algorithmus durchläuft vier Stufen:

1. Erkennung von Extrema im Skalenraum: Unterschiede zwischen benachbarten Weichzeichnungsstufen (Differenz der Gauß-Funktionen) dienen als Näherung für einen Blob-Detektor. Ein Pixel gilt als Kandidat, wenn es unter den 26 Nachbarn in Raum und Skala das Maximum oder Minimum ist.
2. Lokalisierung von Schlüsselpunkten: Die Kandidaten werden auf Subpixelgenauigkeit verfeinert. Punkte mit geringem Kontrast und Punkte entlang von Kanten werden verworfen, da sie instabil sind.
3. Ausrichtung: Ein Histogramm der lokalen Gradientenrichtungen um jeden Schlüsselpunkt bestimmt eine Hauptrichtung, auf die alle folgenden Messungen bezogen werden. Dadurch ist das Verfahren rotationsinvariant.
4. Erstellung des Deskriptors: Die Nachbarschaft wird in ein 4 x 4-Raster unterteilt, und jede Zelle enthält ein Gradientenhistogramm mit 8 Klassen. Das ergibt 4 x 4 x 8 = 128 Werte, die normalisiert werden, um die Empfindlichkeit gegenüber Beleuchtungsänderungen zu verringern.

Beim Abgleich werden Deskriptoren anhand des euklidischen Abstands verglichen. Lowes Verhältnis-Test behält einen Treffer nur dann bei, wenn der beste Nachbar deutlich näher liegt als der zweitbeste. Eine Suche nach den k nächsten Nachbarn mit k = 2 liefert beide Abstände.

import cv2
from ultralytics.utils import ASSETS

# Load a sample image in grayscale and a half-size copy
img = cv2.imread(str(ASSETS / "bus.jpg"), cv2.IMREAD_GRAYSCALE)
small = cv2.resize(img, None, fx=0.5, fy=0.5)

# Detect keypoints and compute 128-dimensional descriptors
sift = cv2.SIFT_create()
kp1, des1 = sift.detectAndCompute(img, None)
kp2, des2 = sift.detectAndCompute(small, None)

# Match half-size descriptors to full-size ones, then apply Lowe's ratio test
pairs = cv2.BFMatcher().knnMatch(des2, des1, k=2)
good = [m for m, n in pairs if m.distance < 0.8 * n.distance]
print(f"{len(good)} of {len(kp2)} half-size keypoints matched at full size")

Die ausgegebene Anzahl zeigt, wie viele Schlüsselpunkte, die bei halber Bildgröße gefunden wurden, im Bild voller Größe wiedererkannt werden – ein Beispiel für Skalierungsinvarianz.

Anwendungen#

SIFT wurde zum Standardverfahren für lokale Merkmale bei geometrischen Sehaufgaben:

• Zusammenfügen von Panoramen: Beim automatischen Zusammenfügen von Panoramen durch Brown und Lowe (IJCV 2007) werden SIFT-Merkmale zwischen überlappenden Fotos abgeglichen und eine Homografie berechnet, um die Fotos auszurichten. Dieser Ausrichtungsschritt wird Bildregistrierung genannt.
• 3D-Rekonstruktion: Photo Tourism (Snavely, Seitz und Szeliski, 2006) gleicht SIFT-Merkmale in Touristenfotos ab und verwendet Epipolargeometrie, um Kamerapositionen und eine dünn besetzte 3D-Struktur zu rekonstruieren.
• Roboterlokalisierung: Se, Lowe und Little (2001) verwendeten SIFT-Landmarken zur Lokalisierung und Kartierung mobiler Roboter – ein Vorläufer des modernen visuellen SLAM.
• Instanzerkennung: In seiner Arbeit von 2004 erkennt Lowe in einer unübersichtlichen, teilweise verdeckten Szene eine Spielzeugeisenbahn und einen Frosch anhand von nur drei übereinstimmenden Merkmalen.

Beim Objekt-Tracking mit Ultralytics YOLO gleicht BoT-SORT Kamerabewegungen zwischen Frames aus. Wenn du gmc_method: sift in der Tracker-Konfiguration festlegst, verwendet das Verfahren für diese Schätzung SIFT-Abgleiche anstelle des standardmäßig eingesetzten dünn besetzten optischen Flusses.

SIFT im Vergleich zu verwandten Verfahren#

SIFT gleicht dieselben physischen Punkte in verschiedenen Ansichten ab und eignet sich daher für Korrespondenz und Geometrie. Bei der Objekterkennung werden stattdessen Kategorie und Position von Objekten vorhergesagt. Beim Vorlagenabgleich wird ein festes Bildfeld über das Bild geschoben; bei Änderungen der Skalierung oder Drehung versagt das Verfahren.

SIFT ist langsamer als ORB, ein binärer Deskriptor, den Rublee und Kollegen 2011 als Alternative zu SIFT und SURF eingeführt haben. Außerdem hat SIFT Schwierigkeiten bei texturlosen Oberflächen und sehr großen Änderungen des Blickwinkels. Für die Erkennung auf Kategorieebene wurde SIFT weitgehend durch erlernte Modelle ersetzt.

In Lowes Tests von 2004 führte das Verwerfen von Abgleichen mit einem Abstandsverhältnis über 0,8 dazu, dass 90 % der falschen Abgleiche entfernt wurden, während weniger als 5 % der korrekten Abgleiche verloren gingen. Die Tests verwendeten Bilder mit zufälligen Skalierungs- und Drehungsänderungen, einer Tiefendrehung um 30 Grad und 2 % Rauschen und glichen sie mit 40.000 Schlüsselpunkten ab.