Bildvergleich - schneller Algorithmus

Question

Ich möchte eine Basistabelle mit Bildern erstellen und dann alle neuen Bilder damit vergleichen, um festzustellen, ob das neue Bild ein exaktes (oder nahes) Duplikat der Basistabelle ist.

Wenn Sie z.B. die Speicherung desselben Bildes über 100 Mal reduzieren wollen, können Sie eine Kopie davon speichern und Verweise darauf bereitstellen. Wenn ein neues Bild eingegeben wird, möchten Sie es mit einem vorhandenen Bild vergleichen, um sicherzustellen, dass es kein Duplikat ist... Ideen?

Eine meiner Ideen war, die Bilder auf ein kleines Vorschaubild zu reduzieren und dann zufällig 100 Pixel auszuwählen und zu vergleichen.

Answer 1

Im Folgenden werden drei Ansätze zur Lösung dieses Problems vorgestellt (und es gibt noch viele weitere).

• Die erste ist ein Standardansatz in der Computer Vision, das Keypoint Matching. Die Umsetzung dieses Ansatzes erfordert unter Umständen etwas Hintergrundwissen und kann langsam sein.

• Die zweite Methode verwendet nur elementare Bildverarbeitung und ist potenziell schneller als der erste Ansatz und ist einfach zu implementieren. Was sie jedoch an Verständlichkeit gewinnt, fehlt ihr an Robustheit - der Abgleich schlägt bei skalierten, gedrehten oder verfärbten Bildern fehl.

• Die dritte Methode ist sowohl schnell als auch robust, aber potenziell am schwierigsten zu implementieren.

Keypoint-Matching

Besser als 100 zufällige Punkte zu wählen, ist die Wahl von 100 wichtig Punkte. Bestimmte Teile eines Bildes enthalten mehr Informationen als andere (insbesondere an den Rändern und Ecken), und genau diese sollten Sie für den intelligenten Bildabgleich verwenden. Google " Schlüsselpunkt-Extraktion " und " Keypoint-Matching " und Sie finden eine ganze Reihe von wissenschaftlichen Abhandlungen zu diesem Thema. Heutzutage, SIFT-Schlüsselpunkte sind wohl die beliebtesten, da sie Bilder in verschiedenen Maßstäben, Drehungen und bei unterschiedlicher Beleuchtung abgleichen können. Einige SIFT-Implementierungen können gefunden werden aquí .

Ein Nachteil des Keypoint Matching ist die Laufzeit einer naiven Implementierung: O(n^2m), wobei n die Anzahl der Keypoints in jedem Bild und m die Anzahl der Bilder in der Datenbank ist. Einige clevere Algorithmen können die nächstgelegene Übereinstimmung schneller finden, wie z. B. Quadtrees oder binäre Raumaufteilung.

---

Alternative Lösung: Histogramm-Methode

Eine andere, weniger robuste, aber möglicherweise schnellere Lösung ist die Erstellung von Merkmalshistogrammen für jedes Bild und die Auswahl des Bildes mit dem Histogramm, das dem Histogramm des Eingabebildes am nächsten kommt. Ich habe dies im Rahmen meines Studiums implementiert, und wir verwendeten 3 Farbhistogramme (rot, grün und blau) und zwei Texturhistogramme, Richtung und Skala. Ich werde die Details weiter unten erläutern, aber ich sollte anmerken, dass dies nur bei Bildern gut funktionierte, die den Datenbankbildern SEHR ähnlich waren. Neu skalierte, gedrehte oder verfärbte Bilder können mit dieser Methode scheitern, aber kleine Änderungen wie das Beschneiden werden den Algorithmus nicht zerstören.

Die Berechnung der Farbhistogramme ist einfach: Wählen Sie den Bereich für Ihre Histogrammbereiche aus, und zählen Sie für jeden Bereich die Anzahl der Pixel mit einer Farbe in diesem Bereich. Betrachten wir zum Beispiel das "grüne" Histogramm und nehmen wir an, wir wählen 4 Bereiche für unser Histogramm: 0-63, 64-127, 128-191, und 192-255. Dann betrachten wir für jedes Pixel den Grünwert und fügen dem entsprechenden Bereich eine Zahl hinzu. Wenn wir mit der Zählung fertig sind, teilen wir die Summe jedes Bereichs durch die Anzahl der Pixel im gesamten Bild, um ein normalisiertes Histogramm für den grünen Kanal zu erhalten.

Für das Texturrichtungshistogramm wurde zunächst eine Kantenerkennung auf dem Bild durchgeführt. Jeder Kantenpunkt hat einen Normalenvektor, der in die Richtung zeigt, die senkrecht zur Kante steht. Wir haben den Winkel des Normalenvektors in einen von 6 Bereichen zwischen 0 und PI quantisiert (da Kanten eine 180-Grad-Symmetrie aufweisen, haben wir Winkel zwischen -PI und 0 in einen Bereich zwischen 0 und PI umgewandelt). Nachdem wir die Anzahl der Kantenpunkte in jeder Richtung zusammengezählt haben, haben wir ein nicht normalisiertes Histogramm, das die Texturrichtung darstellt, das wir normalisiert haben, indem wir jeden Bereich durch die Gesamtzahl der Kantenpunkte im Bild geteilt haben.

Zur Berechnung des Texturskalenhistogramms wurde für jeden Kantenpunkt der Abstand zum nächstgelegenen Kantenpunkt mit der gleichen Richtung gemessen. Wenn beispielsweise Kantenpunkt A eine Richtung von 45 Grad hat, geht der Algorithmus in diese Richtung, bis er einen anderen Kantenpunkt mit einer Richtung von 45 Grad (oder innerhalb einer angemessenen Abweichung) findet. Nachdem dieser Abstand für jeden Kantenpunkt berechnet wurde, werden diese Werte in ein Histogramm eingetragen und durch die Gesamtzahl der Kantenpunkte geteilt.

Sie haben nun 5 Histogramme für jedes Bild. Um zwei Bilder zu vergleichen, nehmen Sie den absoluten Wert der Differenz zwischen den einzelnen Histogrammbereichen und addieren diese Werte. Um zum Beispiel die Bilder A und B zu vergleichen, würden wir Folgendes berechnen

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1| 

für jeden Bereich im grünen Histogramm und wiederholen Sie den Vorgang für die anderen Histogramme, und addieren Sie dann alle Ergebnisse. Je kleiner das Ergebnis ist, desto besser ist die Übereinstimmung. Wiederholen Sie den Vorgang für alle Bilder in der Datenbank, und die Übereinstimmung mit dem kleinsten Ergebnis gewinnt. Wahrscheinlich sollten Sie einen Schwellenwert festlegen, bei dessen Überschreitung der Algorithmus zu dem Schluss kommt, dass keine Übereinstimmung gefunden wurde.

---

Dritte Wahl - Keypoints + Entscheidungsbäume

Ein dritter Ansatz, der wahrscheinlich viel schneller ist als die beiden anderen, ist die Verwendung von semantischer Text über Wälder (PDF). Dabei werden einfache Keypoints extrahiert und eine Sammlung von Entscheidungsbäumen verwendet, um das Bild zu klassifizieren. Dies ist schneller als der einfache SIFT-Keypoint-Abgleich, da der kostspielige Abgleich vermieden wird und die Keypoints viel einfacher sind als SIFT, so dass die Keypoint-Extraktion viel schneller geht. Allerdings bleibt die Invarianz der SIFT-Methode in Bezug auf Drehung, Skalierung und Beleuchtung erhalten, eine wichtige Eigenschaft, die der Histogramm-Methode fehlte.

Update :

Mein Fehler - die Semantic Texton Forests Arbeit ist nicht speziell über Bild-Matching, sondern eher Region Labeling. Das Originalpapier, das den Abgleich vornimmt, ist dieses: Erkennung von Schlüsselpunkten mit zufälligen Bäumen . Auch die folgenden Beiträge entwickeln die Ideen weiter und stellen den aktuellen Stand der Technik dar (Stand 2010):

• Schnelle Erkennung von Schlüsselpunkten mit Zufallsfarnen - schneller und besser skalierbar als Lepetit 06
• BRIEF: Binäre robuste unabhängige elementare Merkmale - weniger robust, aber sehr schnell - ich denke, das Ziel ist hier der Echtzeitabgleich auf Smartphones und anderen Handhelds

Answer 2

Die beste Methode, die ich kenne, ist die Verwendung eines Perceptual Hash. Es scheint eine gute Open-Source-Implementierung eines solchen Hashes zu geben:

http://phash.org/

Die Grundidee besteht darin, dass jedes Bild auf einen kleinen Hash-Code oder "Fingerabdruck" reduziert wird, indem auffällige Merkmale in der ursprünglichen Bilddatei identifiziert und eine kompakte Darstellung dieser Merkmale gehasht wird (anstatt die Bilddaten direkt zu hashen). Dies bedeutet, dass die Rate der Fehlalarme deutlich geringer ist als bei einem einfachen Ansatz, bei dem Bilder auf ein winziges Bild in der Größe eines Daumenabdrucks reduziert werden und die Daumenabdrücke verglichen werden.

phash bietet mehrere Hash-Typen und kann für Bilder, Audio oder Video verwendet werden.

Answer 3

Dieser Beitrag war der Ausgangspunkt für meine Lösung, viele gute Ideen hier, so dass ich dachte, ich würde meine Ergebnisse teilen. Die wichtigste Erkenntnis ist, dass ich einen Weg gefunden habe, um die Langsamkeit des Keypoint-basierten Bildabgleichs durch Ausnutzung der Geschwindigkeit von phash zu umgehen.

Für die allgemeine Lösung ist es am besten, mehrere Strategien anzuwenden. Jeder Algorithmus ist für bestimmte Arten von Bildtransformationen am besten geeignet, und das können Sie sich zunutze machen.

Ganz oben stehen die schnellsten Algorithmen, ganz unten die langsamsten (aber genaueren). Sie können die langsamen Algorithmen auslassen, wenn Sie auf der schnelleren Ebene eine gute Übereinstimmung finden.

• Datei-Hash-basiert (md5, sha1, etc.) für exakte Duplikate
• perceptual hashing (phash) für neu skalierte Bilder
• Merkmalsbasiert (SIFT) für modifizierte Bilder

Ich habe sehr gute Ergebnisse mit phash. Die Genauigkeit ist bei neu skalierten Bildern gut. Bei (wahrnehmungsmäßig) veränderten Bildern (beschnitten, gedreht, gespiegelt usw.) ist sie nicht gut. Um die Hash-Geschwindigkeit zu erreichen, müssen wir einen Festplatten-Cache/eine Datenbank verwenden, um die Hashes für den Heuhaufen zu speichern.

Das Schöne an phash ist, dass die Suchvorgänge sehr, sehr schnell sein können, sobald man seine Hash-Datenbank aufgebaut hat (bei mir sind das etwa 1000 Bilder pro Sekunde), insbesondere wenn man die gesamte Hash-Datenbank im Speicher halten kann. Das ist ziemlich praktisch, da ein Hash nur 8 Bytes groß ist.

Wenn Sie beispielsweise 1 Million Bilder haben, würde dies ein Array von 1 Million 64-Bit-Hash-Werten (8 MB) erfordern. Bei einigen CPUs passt dies in den L2/L3-Cache! In der Praxis habe ich eine Corei7 mit über 1 Giga-hamm/sec gesehen, es ist nur eine Frage der Speicherbandbreite zur CPU. Eine Datenbank mit 1 Milliarde Bildern ist auf einer 64-Bit-CPU praktikabel (8 GB RAM erforderlich), und die Suchvorgänge werden nicht länger als 1 Sekunde dauern!

Für veränderte/beschnittene Bilder scheint ein transformationsinvarianter Merkmals-/Schlüsselpunktdetektor wie SIFT der richtige Weg zu sein. SIFT erzeugt gute Keypoints, die Beschnitt/Drehung/Spiegelung usw. erkennen. Allerdings ist der Deskriptorvergleich im Vergleich zu der von phash verwendeten Hamming-Distanz sehr langsam. Dies ist eine große Einschränkung. Es müssen sehr viele Vergleiche durchgeführt werden, da es maximal IxJxK Deskriptorvergleiche gibt, um ein Bild zu durchsuchen (I=Anzahl Heuhaufenbilder, J=Zielkeypunkte pro Heuhaufenbild, K=Zielkeypunkte pro Nadelbild).

Um das Geschwindigkeitsproblem zu umgehen, habe ich versucht, Phash um jeden gefundenen Keypoint herum zu verwenden, wobei ich die Größe/den Radius des Merkmals zur Bestimmung des Sub-Rechtecks verwendet habe. Der Trick dabei ist, den Radius zu vergrößern/verkleinern, um verschiedene Unterrechtebenen (auf dem Nadelbild) zu erzeugen. Normalerweise passt die erste Ebene (nicht skaliert), aber oft braucht es ein paar mehr. Ich bin mir nicht 100%ig sicher, warum das funktioniert, aber ich kann mir vorstellen, dass es Funktionen ermöglicht, die für Phash zu klein sind (Phash skaliert Bilder bis auf 32x32).

Ein weiteres Problem ist, dass SIFT die Keypoints nicht optimal verteilt. Wenn es einen Bildabschnitt mit vielen Kanten gibt, häufen sich die Keypoints dort und in einem anderen Bereich gibt es keine. Ich verwende den GridAdaptedFeatureDetector in OpenCV, um die Verteilung zu verbessern. Ich bin mir nicht sicher, welche Rastergröße am besten ist, ich verwende ein kleines Raster (1x3 oder 3x1, je nach Bildausrichtung).

Wahrscheinlich sollten Sie alle Heuhaufenbilder (und die Nadel) vor der Merkmalserkennung auf eine kleinere Größe skalieren (ich verwende 210 Pixel entlang der maximalen Abmessung). Dadurch wird das Rauschen im Bild reduziert (immer ein Problem für Computer-Vision-Algorithmen), und der Detektor konzentriert sich auf markantere Merkmale.

Bei Bildern von Menschen können Sie die Gesichtserkennung verwenden, um die Bildgröße und die Rastergröße zu bestimmen (z. B. das größte Gesicht wird auf 100 Pixel skaliert). Der Merkmalsdetektor berücksichtigt mehrere Skalierungsstufen (unter Verwendung von Pyramiden), aber es gibt eine Begrenzung, wie viele Stufen er verwendet (dies ist natürlich einstellbar).

Der Keypoint-Detektor funktioniert wahrscheinlich am besten, wenn er weniger als die von Ihnen gewünschte Anzahl von Merkmalen liefert. Wenn Sie z. B. nach 400 Merkmalen fragen und 300 zurückbekommen, ist das gut. Wenn Sie jedes Mal 400 zurückbekommen, mussten wahrscheinlich einige gute Merkmale ausgelassen werden.

Das Nadelbild kann weniger Keypoints haben als die Heuhaufenbilder und trotzdem gute Ergebnisse erzielen. Wenn man mehr Keypoints hinzufügt, erhält man nicht unbedingt einen enormen Zuwachs, z. B. liegt meine Trefferquote bei J=400 und K=40 bei 92 %. Mit J=400 und K=400 steigt die Trefferquote nur noch auf 96 %.

Wir können die extreme Geschwindigkeit der Hamming-Funktion nutzen, um Skalierung, Drehung, Spiegelung usw. zu lösen. Es kann eine Technik mit mehreren Durchläufen verwendet werden. Bei jeder Iteration werden die Teilrechtecke transformiert, neu gehasht und die Suchfunktion erneut ausgeführt.

Answer 4

Mein Unternehmen hat etwa 24Millionen Jeden Monat kommen Bilder von den Herstellern herein. Ich war auf der Suche nach einer schnellen Lösung, um sicherzustellen, dass die Bilder, die wir in unseren Katalog hochladen neu Bilder.

Ich möchte sagen, dass ich das Internet weit und breit durchsucht habe, um eine ideale Lösung zu finden. Ich habe sogar meinen eigenen Algorithmus zur Kantenerkennung entwickelt.
Ich habe Geschwindigkeit und Genauigkeit mehrerer Modelle bewertet. Meine Bilder, die einen weißen Hintergrund haben, funktionieren sehr gut mit Phashing. Wie redcalx sagte, empfehle ich phash oder ahash. NICHT MD5-Hashing oder andere kryptografische Hashes verwenden. Es sei denn, Sie wollen nur EXAKTE Bildübereinstimmungen. Jede Größenänderung oder Manipulation zwischen Bildern führt zu einem anderen Hashwert.

Für phash/ahash, Sehen Sie sich das an: imagehash

Ich wollte *redcalx'*s Beitrag durch die Veröffentlichung meines Codes und meiner Genauigkeit erweitern.

Was ich mache:

from PIL import Image
from PIL import ImageFilter
import imagehash

img1=Image.open(r"C:\yourlocation")
img2=Image.open(r"C:\yourlocation")
if img1.width<img2.width:
    img2=img2.resize((img1.width,img1.height))
else:
    img1=img1.resize((img2.width,img2.height))
img1=img1.filter(ImageFilter.BoxBlur(radius=3))
img2=img2.filter(ImageFilter.BoxBlur(radius=3))
phashvalue=imagehash.phash(img1)-imagehash.phash(img2)
ahashvalue=imagehash.average_hash(img1)-imagehash.average_hash(img2)
totalaccuracy=phashvalue+ahashvalue

Hier sind einige meiner Ergebnisse:

item1  item2  totalsimilarity
desk1  desk1       3
desk1  phone1     22
chair1 desk1      17
phone1 chair1     34

Ich hoffe, das hilft!

Answer 5

Wie cartman schon sagte, können Sie jede Art von Hash-Wert verwenden, um exakte Duplikate zu finden.

Ein Ausgangspunkt für die Suche nach nahen Bildern könnte sein aquí . Dies ist ein Werkzeug, das von CG-Firmen verwendet wird, um zu überprüfen, ob überarbeitete Bilder immer noch im Wesentlichen die gleiche Szene zeigen.