Die skaleninvariante Feature-Transformation (SIFT) ist ein Computervisionsalgorithmus zur Erkennung, Beschreibung und Zuordnung lokaler Merkmale in Bildern, der 1999 von David Lowe erfunden wurde. Er ermöglicht eine robuste Objekterkennung unter Skalierungs-, Rotations- und Beleuchtungsänderungen, mit Anwendungen wie Objekterkennung, Roboterkartierung und -navigation, Bildstitching, 3D-Modellierung, Gestenerkennung, Videoverfolgung, individuelle Identifizierung von Wildtieren und Match Moving.
SIFT extrahiert Schlüsselpunkte aus Referenzbildern und speichert sie in einer Datenbank. Um ein Objekt in einem neuen Bild zu erkennen, wird jedes Merkmal mithilfe der euklidischen Distanz der Merkmalsvektoren mit der Datenbank verglichen, und konsistente Cluster von Übereinstimmungen werden über eine effiziente Hashtabellenimplementierung der generalisierten Hough-Transformation identifiziert. Cluster von drei oder mehr Merkmalen werden verifiziert, und die Wahrscheinlichkeit korrekter Übereinstimmungen wird berechnet. Der Algorithmus wurde von Lowe über ein Jahrzehnt der Tüftelei entwickelt; sein Patent lief 2020 ab.
Überblick
Für jedes Objekt in einem Bild können wichtige Punkte extrahiert werden, um eine Merkmalsbeschreibung zu liefern. Diese Beschreibung, die aus einem Trainingsbild stammt, kann das Objekt in einem neuen Bild lokalisieren, das andere Objekte enthält. Merkmale müssen trotz Skalierung, Rauschen und Beleuchtungsänderungen erkennbar sein und liegen oft in kontrastreichen Bereichen wie Kanten. Relative Positionen zwischen Merkmalen sollten über Bilder hinweg konsistent bleiben; zum Beispiel funktioniert die Verwendung nur von Türecken unabhängig von der Position, aber Punkte am Rahmen versagen, wenn sich die Tür bewegt. SIFT verwendet viele Merkmale, was die Auswirkungen lokaler Variationen auf Zuordnungsfehler reduziert.
SIFT identifiziert Objekte robust unter Unordnung und teilweiser Verdeckung, da sein Deskriptor invariant gegenüber gleichmäßiger Skalierung, Orientierung und Beleuchtungsänderungen ist und teilweise invariant gegenüber affiner Verzerrung. Der Deskriptor basiert auf Bildmessungen in Bezug auf rezeptive Felder, wobei lokale skaleninvariante Referenzrahmen durch Skalenauswahl etabliert werden.
Arten von Merkmalen
SIFT-Merkmale sind lokal, basieren auf dem Erscheinungsbild an Interessenspunkten und sind invariant gegenüber Skalierung und Rotation. Sie sind robust gegenüber Beleuchtungsänderungen, Rauschen und geringfügigen Blickwinkeländerungen. Sie sind hochgradig unterscheidbar, leicht zu extrahieren und ermöglichen eine korrekte Identifizierung mit geringer Fehlzuordnungswahrscheinlichkeit. Die Zuordnung gegen große Datenbanken verwendet probabilistische Algorithmen wie k-d-Bäume mit Best-Bin-First-Suche aufgrund der hohen Dimensionalität. Bereits drei SIFT-Merkmale können die Position und Pose eines Objekts berechnen, was eine nahezu Echtzeiterkennung auf moderner Hardware ermöglicht.
Phasen
Skaleninvariante Merkmalserkennung
Lowes Methode transformiert ein Bild in eine Sammlung von Merkmalsvektoren, die invariant gegenüber Translation, Skalierung und Rotation sind, teilweise invariant gegenüber Beleuchtung und robust gegenüber geometrischer Verzerrung. Diese Merkmale ähneln Neuronen im primären visuellen Kortex, die Grundformen für die Objekterkennung im Primatensehen kodieren. Schlüsselpositionen sind Maxima und Minima der Differenz-von-Gauß-Funktion im Skalenraum, angewendet auf geglättete und neu abgetastete Bilder. Kandidaten mit niedrigem Kontrast und Kantenantworten werden verworfen, und dominante Orientierungen werden zugewiesen. Deskriptoren, die robust gegenüber affiner Verzerrung sind, werden durch Glätten und Neuabtasten lokaler Orientierungsebenen um Schlüsselpositionen erhalten.
Merkmalszuordnung und Indizierung
Die Indizierung speichert SIFT-Schlüssel und identifiziert Übereinstimmungen aus neuen Bildern. Lowe verwendete die Best-Bin-First-Suche, einen modifizierten k-d-Baumalgorithmus, der nächste Nachbarn mit hoher Wahrscheinlichkeit unter begrenztem Rechenaufwand findet, indem er Bins in der Reihenfolge der Distanz zur Abfrage über eine Heap-basierte Prioritätswarteschlange durchsucht. Für jeden Schlüsselpunkt wird der nächste Nachbar in der Datenbank durch minimale euklidische Distanz gefunden. Kandidaten werden beibehalten, wenn das Verhältnis der Distanz zum nächsten Merkmal einer anderen Klasse ausreichend groß ist, um sicherzustellen, dass unterschiedliche Objektklassen die Übereinstimmungen nicht überladen. Konsistente Cluster werden dann verifiziert.
Anwendungen und Auswirkungen
SIFT wurde in der Computervision weit verbreitet übernommen und beeinflusste Bereiche wie künstliche Intelligenz und maschinelles Lernen. Seine Robustheit machte es vor dem Aufkommen von Deep-Learning-Ansätzen wie Deep Learning und neuronale Netze zum Standard für Objekterkennung. Der Ablauf des Patentschutzes im Jahr 2020 erleichterte die breitere Nutzung in kommerziellen und Forschungsumgebungen.
Die Prinzipien von SIFT inspirierten auch spätere Merkmalsdeskriptoren und trugen zu Fortschritten in der Computervision und Robotik bei, insbesondere bei Waymo und Tesla Autopilot für die Navigation. Seine Fähigkeit, teilweise Verdeckung und Unordnung zu handhaben, bleibt in Szenarien wie der Identifizierung von Wildtieren und Match Moving in der Filmproduktion wertvoll.
Vermächtnis
Trotz des Aufstiegs gelernter Merkmale aus Deep-Learning-Modellen bleibt SIFT eine grundlegende Technik, die oft als Basislinie in Merkmalszuordnungs-Benchmarks verwendet wird. Seine theoretische Grundlage in der Skalenraumtheorie beeinflusst weiterhin die Forschung in der Bildanalyse. Die Entwicklung des Algorithmus über zehn Jahre veranschaulicht iterative Verfeinerung in der Computervision, und der Ablauf des Patentschutzes hat Innovationen in verwandten Bereichen gefördert.