Bildvergleich - schneller Algorithmus

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

Beispiel: Wenn Sie die Speicherung desselben Bildes hundertmal reduzieren möchten, können Sie eine Kopie davon speichern und Referenzlinks dazu bereitstellen. Wenn ein neues Bild eingegeben wird, möchten Sie es mit einem vorhandenen Bild vergleichen, um sicherzustellen, dass es sich nicht um ein Duplikat handelt ... Ideen?

Eine Idee von mir war es, auf ein kleines Miniaturbild zu reduzieren und dann zufällig 100 Pixelpositionen auszuwählen und zu vergleichen.

Im Folgenden finden Sie drei Ansätze zur Lösung dieses Problems (und es gibt viele andere).

• Der erste ist ein Standardansatz für Computer Vision, Keypoint Matching. Die Implementierung erfordert möglicherweise Hintergrundwissen und kann langsam sein.

• Die zweite Methode verwendet nur eine elementare Bildverarbeitung und ist möglicherweise schneller als die erste Methode und einfach zu implementieren. Was jedoch an Verständlichkeit gewinnt, mangelt es an Robustheit - die Anpassung schlägt bei skalierten, gedrehten oder verfärbten Bildern fehl.

• Die dritte Methode ist schnell und robust, aber möglicherweise am schwierigsten zu implementieren.

Schlüsselpunktabgleich

Besser als 100 zufällige Punkte auszuwählen, ist es, 100 wichtige Punkte auszuwählen . Bestimmte Teile eines Bildes enthalten mehr Informationen als andere (insbesondere an Kanten und Ecken). Diese Teile möchten Sie für die intelligente Bildanpassung verwenden. Google " Keypoint Extraction " und " Keypoint Matching " und Sie finden einige wissenschaftliche Artikel zu diesem Thema. In diesen Tagen, SIFT keypoints sind wohl die beliebtesten, da sie Bilder unter verschiedenen Skalen, Rotationen bieten kann, und Beleuchtung. Einige SIFT-Implementierungen finden Sie hier .

Ein Nachteil der Schlüsselpunktübereinstimmung ist die Laufzeit einer naiven Implementierung: O (n ^ 2m), wobei n die Anzahl der Schlüsselpunkte in jedem Bild und m die Anzahl der Bilder in der Datenbank ist. Einige clevere Algorithmen finden möglicherweise die engste Übereinstimmung schneller, z. B. Quadtrees oder binäre Raumpartitionierung.

Alternative Lösung: Histogrammmethode

Eine andere weniger robuste, aber möglicherweise schnellere Lösung besteht darin, Feature-Histogramme für jedes Bild zu erstellen und das Bild mit dem Histogramm auszuwählen, das dem Histogramm des Eingabebilds am nächsten liegt. Ich habe dies als Undergrad implementiert und wir haben 3 Farbhistogramme (rot, grün und blau) und zwei Texturhistogramme (Richtung und Maßstab) verwendet. Ich werde die Details unten angeben, aber ich sollte beachten, dass dies nur gut für übereinstimmende Bilder funktioniert hat, die den Datenbankbildern SEHR ähnlich sind. Neu skalierte, gedrehte oder verfärbte Bilder können mit dieser Methode fehlschlagen, aber kleine Änderungen wie das Zuschneiden werden den Algorithmus nicht beschädigen

Das Berechnen der Farbhistogramme ist unkompliziert. Wählen Sie einfach den Bereich für Ihre Histogramm-Buckets aus und zählen Sie für jeden Bereich die Anzahl der Pixel mit einer Farbe in diesem Bereich. Betrachten Sie beispielsweise das "grüne" Histogramm und nehmen Sie an, wir wählen 4 Buckets für unser Histogramm: 0-63, 64-127, 128-191 und 192-255. Dann schauen wir uns für jedes Pixel den grünen Wert an und fügen dem entsprechenden Bucket eine Liste hinzu. Wenn wir mit dem Zählen fertig sind, teilen wir jede Bucket-Summe durch die Anzahl der Pixel im gesamten Bild, um ein normalisiertes Histogramm für den grünen Kanal zu erhalten.

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

Um das Textur-Skalen-Histogramm zu berechnen, haben wir für jeden Kantenpunkt den Abstand zum nächstgelegenen Kantenpunkt mit derselben Richtung gemessen. Wenn beispielsweise der 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 wir diesen Abstand für jeden Kantenpunkt berechnet haben, speichern wir diese Werte in einem Histogramm und normalisieren es, indem wir durch die Gesamtzahl der Kantenpunkte dividieren.

Jetzt haben Sie 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 beispielsweise die Bilder A und B zu vergleichen, würden wir berechnen

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

für jeden Bucket im grünen Histogramm und wiederholen Sie dies für die anderen Histogramme und fassen Sie dann alle Ergebnisse zusammen. Je kleiner das Ergebnis, desto besser die Übereinstimmung. Wiederholen Sie diesen Vorgang für alle Bilder in der Datenbank, und die Übereinstimmung mit dem kleinsten Ergebnis gewinnt. Sie möchten wahrscheinlich einen Schwellenwert haben, über dem der Algorithmus zu dem Schluss kommt, dass keine Übereinstimmung gefunden wurde.

Dritte Wahl - Schlüsselpunkte + Entscheidungsbäume

Ein dritter Ansatz, der wahrscheinlich viel schneller ist als die beiden anderen, ist die Verwendung semantischer Textonwälder (PDF). Dies beinhaltet das Extrahieren einfacher Schlüsselpunkte und das Verwenden von Sammlungsentscheidungsbäumen zum Klassifizieren des Bildes. Dies ist schneller als ein einfacher SIFT-Schlüsselpunktabgleich, da der kostspielige Abgleichprozess vermieden wird und Schlüsselpunkte viel einfacher als SIFT sind, sodass die Schlüsselpunktextraktion viel schneller ist. Die Invarianz der SIFT-Methode in Bezug auf Rotation, Skalierung und Beleuchtung bleibt jedoch erhalten, ein wichtiges Merkmal, das der Histogrammmethode fehlte.

Update :

Mein Fehler - beim Papier Semantic Texton Forests geht es nicht speziell um Bildanpassung, sondern um die Beschriftung von Regionen. Das Originalpapier, das übereinstimmt, ist das folgende: Schlüsselpunkterkennung mit randomisierten Bäumen . Die folgenden Artikel entwickeln die Ideen weiter und repräsentieren den Stand der Technik (ca. 2010):

• Schnelle Schlüsselpunkterkennung mit zufälligen Farnen - schneller und skalierbarer als Lepetit 06
• KURZDARSTELLUNG: Binär robuste, unabhängige Elementarfunktionen - weniger robust, aber sehr schnell - Ich denke, das Ziel hier ist die Echtzeitanpassung auf Smartphones und anderen Handhelds

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

http://phash.org/

Die Hauptidee ist, dass jedes Bild auf einen kleinen Hash-Code oder "Fingerabdruck" reduziert wird, indem hervorstechende Merkmale in der Originalbilddatei identifiziert und eine kompakte Darstellung dieser Merkmale gehasht werden (anstatt die Bilddaten direkt zu hashen). Dies bedeutet, dass die Falsch-Positiv-Rate gegenüber einem vereinfachten Ansatz wie dem Reduzieren von Bildern auf ein winziges Bild mit Fingerabdruckgröße und dem Vergleichen von Fingerabdrücken erheblich reduziert wird.

Phash bietet verschiedene Arten von Hash und kann für Bilder, Audio oder Video verwendet werden.

Dieser Beitrag war der Ausgangspunkt meiner Lösung, viele gute Ideen hier, damit ich meine Ergebnisse teilen kann. Die wichtigste Erkenntnis ist, dass ich einen Weg gefunden habe, um die Langsamkeit der auf Schlüsselpunkten basierenden Bildanpassung zu umgehen, indem ich die Geschwindigkeit von Phash ausnutzte.

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

An der Spitze die schnellsten Algorithmen; unten am langsamsten (wenn auch genauer). Sie können die langsamen überspringen, wenn auf der schnelleren Ebene eine gute Übereinstimmung gefunden wird.

• Datei-Hash-basiert (md5, sha1 usw.) für genaue Duplikate
• Perceptual Hashing (Phash) für neu skalierte Bilder
• Feature-basiert (SIFT) für geänderte Bilder

Ich habe sehr gute Ergebnisse mit Phash. Die Genauigkeit ist gut für neu skalierte Bilder. Es ist nicht gut für (wahrnehmungsmäßig) modifizierte Bilder (zugeschnitten, gedreht, gespiegelt usw.). Um mit der Hashing-Geschwindigkeit fertig zu werden, müssen wir einen Festplatten-Cache / eine Festplatten-Datenbank verwenden, um die Hashes für den Heuhaufen zu verwalten.

Das wirklich Schöne an Phash ist, dass die Suche nach dem Erstellen Ihrer Hash-Datenbank (für mich ungefähr 1000 Bilder / Sek.) Sehr, sehr schnell sein kann, insbesondere wenn Sie die gesamte Hash-Datenbank im Speicher halten können. Dies ist ziemlich praktisch, da ein Hash nur 8 Bytes umfasst.

Wenn Sie beispielsweise 1 Million Bilder haben, ist ein Array von 1 Million 64-Bit-Hashwerten (8 MB) erforderlich. Bei einigen CPUs passt dies in den L2 / L3-Cache! Im praktischen Gebrauch habe ich einen Corei7-Vergleich mit über 1 Giga-Hamm / Sek. Gesehen, es ist nur eine Frage der Speicherbandbreite zur CPU. Eine 1-Milliarden-Bilddatenbank ist auf einer 64-Bit-CPU (8 GB RAM erforderlich) praktisch und die Suche wird 1 Sekunde nicht überschreiten!

Für modifizierte / zugeschnittene Bilder scheint ein transformationsinvarianter Feature- / Keypoint-Detektor wie SIFT der richtige Weg zu sein. SIFT erzeugt gute Schlüsselpunkte, die Ernten / Drehen / Spiegeln usw. erkennen. Der Deskriptorvergleich ist jedoch im Vergleich zu der von Phash verwendeten Hamming-Distanz sehr langsam. Dies ist eine wesentliche Einschränkung. Es gibt viele Vergleiche zu tun, da es maximale IxJxK-Deskriptor-Vergleiche gibt, um ein Bild nachzuschlagen (I = Anzahl Heuhaufenbilder, J = Zielschlüsselpunkte pro Heuhaufenbild, K = Zielschlüsselpunkte pro Nadelbild).

Um das Geschwindigkeitsproblem zu umgehen, habe ich versucht, um jeden gefundenen Schlüsselpunkt einen Phash zu verwenden und das Subrechteck anhand der Feature-Größe / des Radius zu bestimmen. Der Trick, um dies gut zu machen, besteht darin, den Radius zu vergrößern / verkleinern, um verschiedene sub-rect-Pegel zu erzeugen (auf dem Nadelbild). Normalerweise stimmt die erste Ebene (nicht skaliert) überein, jedoch dauert es oft einige weitere. Ich bin nicht 100% sicher, warum dies funktioniert, aber ich kann mir vorstellen, dass es Funktionen ermöglicht, die zu klein sind, als dass Phash funktionieren könnte (Phash skaliert Bilder auf 32x32).

Ein weiteres Problem ist, dass SIFT die Schlüsselpunkte nicht optimal verteilt. Wenn es einen Abschnitt des Bildes mit vielen Kanten gibt, werden die Schlüsselpunkte dort gruppiert und Sie erhalten keine in einem anderen Bereich. 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).

Sie möchten wahrscheinlich alle Heuhaufenbilder (und Nadeln) vor der Feature-Erkennung auf eine kleinere Größe skalieren (ich verwende 210 Pixel entlang der maximalen Abmessung). Dies reduziert das Bildrauschen (immer ein Problem für Computer-Vision-Algorithmen) und fokussiert den Detektor auch auf wichtigere Merkmale.

Bei Bildern von Personen können Sie die Gesichtserkennung ausprobieren und damit die zu skalierende Bildgröße und die Rastergröße bestimmen (z. B. das größte Gesicht, das auf 100 Pixel skaliert ist). Der Feature-Detektor berücksichtigt mehrere Skalierungsstufen (mithilfe von Pyramiden), es gibt jedoch eine Beschränkung für die Anzahl der verwendeten Ebenen (dies ist natürlich einstellbar).

Der Schlüsselpunktdetektor funktioniert wahrscheinlich am besten, wenn er weniger als die gewünschte Anzahl von Funktionen zurückgibt. Wenn Sie zum Beispiel nach 400 fragen und 300 zurückbekommen, ist das gut. Wenn Sie jedes Mal 400 zurückbekommen, mussten wahrscheinlich einige gute Funktionen weggelassen werden.

Das Nadelbild kann weniger Schlüsselpunkte als die Heuhaufenbilder haben und dennoch gute Ergebnisse erzielen. Wenn Sie mehr hinzufügen, erhalten Sie nicht unbedingt enorme Gewinne. Bei J = 400 und K = 40 liegt meine Trefferquote beispielsweise bei 92%. Mit J = 400 und K = 400 steigt die Trefferquote nur auf 96%.

Wir können die extreme Geschwindigkeit der Hamming-Funktion nutzen, um Skalierung, Rotation, Spiegelung usw. zu lösen. Eine Mehrfachdurchlauf-Technik kann verwendet werden. Transformieren Sie bei jeder Iteration die Unterrechtecke, führen Sie einen erneuten Hash durch und führen Sie die Suchfunktion erneut aus.

Wie Cartman betonte, können Sie jede Art von Hash-Wert verwenden, um genaue Duplikate zu finden.

Ein Ausgangspunkt für die Suche nach Nahbildern könnte hier sein . Dies ist ein Tool, mit dem CG-Unternehmen prüfen, ob überarbeitete Bilder im Wesentlichen dieselbe Szene zeigen.

Ich habe eine Idee, die funktionieren kann und höchstwahrscheinlich sehr schnell ist. Sie können ein Bild mit einer Auflösung von 80 x 60 oder einer vergleichbaren Auflösung unterabtasten und in Graustufen konvertieren (nach der Unterabtastung ist es schneller). Verarbeiten Sie beide Bilder, die Sie vergleichen möchten. Führen Sie dann eine normalisierte Summe der quadratischen Differenzen zwischen zwei Bildern (das Abfragebild und jedes aus der Datenbank) oder eine noch besser normalisierte Kreuzkorrelation aus, die eine Antwort näher an 1 ergibt, wenn beide Bilder ähnlich sind. Wenn die Bilder ähnlich sind, können Sie mit komplexeren Techniken fortfahren, um zu überprüfen, ob es sich um dieselben Bilder handelt. Offensichtlich ist dieser Algorithmus in Bezug auf die Anzahl der Bilder in Ihrer Datenbank linear, obwohl er auf der modernen Hardware bis zu 10000 Bilder pro Sekunde sehr schnell sein wird. Wenn Sie eine Invarianz zur Rotation benötigen, kann für dieses kleine Bild ein dominanter Gradient berechnet werden. und dann kann das gesamte Koordinatensystem in kanonische Ausrichtung gedreht werden, dies ist jedoch langsamer. Und nein, hier gibt es keine maßstabsgetreue Invarianz.

Wenn Sie etwas allgemeineres möchten oder große Datenbanken (Millionen von Bildern) verwenden möchten, müssen Sie sich mit der Bildwiederherstellungstheorie befassen (in den letzten 5 Jahren sind zahlreiche Artikel erschienen). Es gibt einige Hinweise in anderen Antworten. Aber es könnte übertrieben sein, und der vorgeschlagene Histogramm-Ansatz wird den Job erledigen. Obwohl ich denke, dass die Kombination vieler verschiedener schneller Ansätze noch besser sein wird.

In meinem Unternehmen kommen jeden Monat etwa 24 Millionen Bilder von Herstellern. Ich suchte nach einer schnellen Lösung, um sicherzustellen, dass die Bilder, die wir in unseren Katalog hochladen, neue Bilder sind.

Ich möchte sagen, dass ich weit und breit im Internet gesucht habe, um eine ideale Lösung zu finden. Ich habe sogar meinen eigenen Kantenerkennungsalgorithmus entwickelt.
Ich habe die Geschwindigkeit und Genauigkeit mehrerer Modelle bewertet. Meine Bilder mit weißem Hintergrund eignen sich hervorragend für Phashing. Wie Redcalx sagte, empfehle ich Phash oder Ahash. Verwenden Sie KEIN MD5 Hashing oder andere kryptografische Hashes. Es sei denn, Sie möchten nur GENAUE Bildübereinstimmungen. Jede Größenänderung oder Manipulation zwischen Bildern führt zu einem anderen Hash.

Für Phash / Ahash, überprüfen Sie dies: imagehash

Ich wollte den Beitrag von * redcalx * erweitern, indem ich meinen Code und meine Genauigkeit veröffentlichte.

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

Hoffe das hilft!

Ich bin der Meinung, dass es gut funktionieren sollte, die Bildgröße auf eine Symbolgröße von beispielsweise 48 x 48 zu reduzieren, dann in Graustufen zu konvertieren und dann den Unterschied zwischen Pixeln oder Delta zu ermitteln. Da wir die Änderung der Pixelfarbe und nicht die tatsächliche Pixelfarbe vergleichen, spielt es keine Rolle, ob das Bild etwas heller oder dunkler ist. Große Änderungen sind wichtig, da zu hell / dunkel werdende Pixel verloren gehen. Sie können dies auf eine oder mehrere Zeilen anwenden, um die Genauigkeit zu erhöhen. Sie müssten höchstens 47x47 = 2.209 Subtraktionen vornehmen, um einen vergleichbaren Schlüssel zu bilden.

Das Auswählen von 100 zufälligen Punkten könnte bedeuten, dass ähnliche (oder gelegentlich sogar unähnliche) Bilder als gleich markiert werden, was meiner Meinung nach nicht das ist, was Sie wollen. MD5-Hashes würden nicht funktionieren, wenn die Bilder unterschiedliche Formate (PNG, JPEG usw.), unterschiedliche Größen oder unterschiedliche Metadaten hätten. Das Reduzieren aller Bilder auf eine kleinere Größe ist eine gute Wahl. Ein Pixel-für-Pixel-Vergleich sollte nicht zu lange dauern, solange Sie eine gute Bildbibliothek / schnelle Sprache verwenden und die Größe klein genug ist.

Sie könnten versuchen, sie winzig zu machen, und wenn sie gleich sind, führen Sie einen weiteren Vergleich mit einer größeren Größe durch - könnte eine gute Kombination aus Geschwindigkeit und Genauigkeit sein ...

Wenn Sie eine große Anzahl von Bildern haben, schauen Sie in einen Bloom-Filter , der mehrere Hashes verwendet, um ein wahrscheinliches, aber effizientes Ergebnis zu erzielen. Wenn die Anzahl der Bilder nicht groß ist, sollte ein kryptografischer Hash wie md5 ausreichen.