Bildvergleich - schneller Algorithmus

StackOverflow https://stackoverflow.com/questions/843972

Frage

Ich suche eine Basistabelle von Bildern zu erstellen und vergleichen dann alle neuen Bilder vor, dass, um zu bestimmen, ob das neue Bild eine exakte (oder schließen) ist Duplikat der Basis.

Zum Beispiel: Wenn Sie die Speicherung der gleichen Bild 100 von Zeiten reduzieren wollen, können Sie eine Kopie davon speichern kann und Referenz Links zu ihr geben. Wenn ein neues Bild eingegeben Sie auf ein vorhandenes Bild vergleichen wollen Ideen, um sicherzustellen, es ist kein Duplikat ...?

Eine Idee von mir war zu einer kleinen Miniatur zu reduzieren und dann 100 Pixelort zufällig auszuwählen und zu vergleichen.

War es hilfreich?

Lösung

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

  • Der erste ist ein Standardansatz in Computer Vision, keypoint Matching. Dies kann einige Hintergrundwissen benötigen zu implementieren und kann langsam sein.

  • Die zweite Methode verwendet nur elementare Bildverarbeitung und ist potentiell schneller als der erste Ansatz und ist einfach zu implementieren. Doch was es in Verständlichkeits gewinnt, fehlt es in Robustheit - Matching nicht auf skaliert, gedreht oder verfärbte Bilder

    • .

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

Keypoint Matching

Besser als Kommissionierung 100 zufällige Punkte Kommissionierung 100 wichtig Punkte. Bestimmte Teile eines Bildes haben mehr Informationen als andere (insbesondere an Kanten und Ecken), und diese sind diejenigen, die Sie für intelligente Bildanpassung verwenden möchten. Google " keypoint Extraktion " und " keypoint passende " und Sie werden schon einige wissenschaftliche Arbeiten zu diesem Thema finden. In diesen Tagen, keypoints SIFT wohl sind die beliebtesten, da sie Bilder unter verschiedenen Maßstäben entsprechen können , Rotationen und Beleuchtung. Einige SIFT Implementierungen können hier .

Ein Nachteil keypoint Anpassung ist die Laufzeit einer naiven Umsetzung: O (n ^ 2 m), wobei n die Anzahl von Schlüsselpunkten in jedem Bild ist, und m ist die Anzahl der Bilder in der Datenbank. Einige cleveren Algorithmen könnten am nächsten kommt schneller finden, wie Quadtrees oder binäre Raumaufteilung.

Alternative Lösung: Histogramm-Methode

Eine andere, weniger robust, aber potenziell schnellere Lösung ist Feature-Histogramme für jedes Bild zu bauen, und wählen Sie das Bild mit dem Histogramm am nächsten das Histogramm des Eingangsbildes. Ich implementiert dies als under, und wir haben 3 Farben Histogramme (rot, grün und blau) und zwei Textur-Histogramme, die Richtung und Maßstab. Ich werde die Details unten geben, aber ich sollte beachten, dass dies nur gut funktioniert Bilder sehr ähnlich wie die Datenbank Bilder zur Anpassung. Re-skaliert, gedreht oder verfärbte Bilder können mit dieser Methode nicht, aber kleine Änderungen wie Zuschneiden wird der Algorithmus nicht brechen

Die Berechnung der Farbhistogramme ist einfach - wählen Sie einfach den Bereich für Ihr Histogramm Eimer, und für jeden Bereich, die Anzahl der Pixel mit einer Farbe in diesem Bereich übereinstimmen. Betrachten wir zum Beispiel das „grüne“ Histogramm, und nehmen wir wählen, 4 Eimer für unser Histogramm: 0-63, 64-127, 128-191 und 192-255. Dann gilt für jedes Pixel, schauen wir auf den grünen Wert, und eine Strichliste an den entsprechenden Eimer hinzuzufügen. Wenn wir fertig sind Auszählung, teilen wir jeden Eimer Summe durch die Anzahl der Pixel im gesamten Bild ein normalisiertes Histogramm für die grünen Kanal zu erhalten.

Für die Texturrichtung Histogramm, haben wir begonnen, indem Kantenerkennung auf das Bild. Jeder Randpunkt hat einen Normalvektor zeigt in die Richtung, die senkrecht zu der Kante. Wir quantisiert den Winkel des Normalenvektors in eine von 6 Eimern zwischen 0 und PI (da Kanten 180-Grad-Symmetrie haben wir umgewandelt Winkel zwischen 0 -PI und zwischen 0 und PI sein). Nach der Auszählung der Anzahl der Kantenpunkte in jede Richtung nach oben, haben wir ein nicht-normalisierten Histogramm Texturrichtung darstellt, die wir durch Dividieren jeden Eimer durch die Gesamtzahl von Kantenpunkten in dem Bild normalisierten.

die Textur Skala Histogramm zu berechnen, für jeden Randpunkt, gemessen wir den Abstand zum nächsten am nächsten Kantenpunkt mit der gleichen Richtung. Foder Wenn beispielsweise Kantenpunkt A um eine Richtung von 45 Grad hat, geht der Algorithmus in dieser Richtung, bis er eine anderen Kantenpunkt mit einer Richtung von 45 Grad (oder in angemessener Abweichung) findet. Nach der Berechnung Punkt dieser Abstand für jede Kante, entleeren wir diese Werte in ein Histogramm und normalisieren sie durch die Gesamtzahl von Kantenpunkten durch Dividieren.

Sie haben nun 5 Histogramme für jedes Bild. So vergleichen Sie zwei Bilder, nehmen Sie den absoluten Wert der Differenz zwischen jedem Histogramm Eimer, und dann diese Werte summieren. Zum Beispiel Bilder A und B zu vergleichen, wir würden berechnen 

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

für jeden Eimer im grünen Histogramm, und wiederholen Sie für die anderen Histogramme und dann alle Ergebnisse zusammenfassen. Je kleiner das Ergebnis, desto besser ist das Spiel. Wiederholen Sie dies für alle Bilder in der Datenbank, und das Spiel mit dem kleinsten Ergebnis gewinnt. Sie würden vermutlich eine Schwelle haben wollen, über den der Algorithmus kommt zu dem Schluss, dass keine Übereinstimmung gefunden wurde.

Dritte Wahl - keypoints + Decision Trees

Ein dritte Ansatz, der wahrscheinlich viel schneller als die anderen zwei ist, ist mit semantischem Texton Wäldern (PDF). Dies beinhaltet einfache keypoints Extrahieren und eine Sammlung Entscheidungsbäume unter Verwendung des Bildes zu klassifizieren. Dies ist schneller als einfach SIFT keypoint Matching, weil es vermeidet den aufwendigen Matching-Prozess, und keypoints sind viel einfacher als SIFT, so keypoint Extraktion ist viel schneller. Aber es bewahrt die Invarianz der SIFT Verfahren zur Rotation, Skalierung und Beleuchtung, ein wichtiges Merkmal, das das Histogramm Methode fehlte.

Aktualisieren :

Mein Fehler - das Semantic Texton Wald Papier ist nicht speziell zur Bildanpassung, sondern Region Kennzeichnung. Das ursprüngliche Papier, das passende tut, ist diese: Keypoint Erkennung mit Hilfe der Randomized Trees . Auch weiterhin die Papiere unten, um die Ideen zu entwickeln und den Stand der Technik dar (c 2010.):

Andere Tipps

Die beste Methode, die ich kenne, ist ein Perceptual Hash zu verwenden. Es scheint eine gute Open-Source-Implementierung eines solchen Hash zu sein unter:

http://phash.org/

Die Hauptidee ist, dass jedes Bild mit einem kleinen Hashcode reduziert gefahren wird oder ‚Fingerabdruck‘ von herausragenden Eigenschaften in der Originalbilddatei zu identifizieren und eine kompakte Darstellung dieser Merkmale Hashing (eher als Hashing die Bilddaten direkt). Dies bedeutet, dass die falsch-positive Rate viel über einen simplen Ansatz reduziert wird, wie Bilder bis zu einer winzigen Daumenabdruck Größe Bild zu reduzieren und den Vergleich thumbprints.

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

Dieser Beitrag ist der Ausgangspunkt meiner Lösung war, viele gute Ideen, die hier so, obwohl ich würde ich meine Ergebnisse teilen. Die Haupt Erkenntnis ist, dass ich einen Weg gefunden habe, durch Ausnutzen die Geschwindigkeit von phash um die Langsamkeit der keypoint basierte Bildanpassung zu erhalten.

Für die allgemeine Lösung, dann ist es am besten, verschiedene Strategien zu beschäftigen. Jeder Algorithmus eignet sich am besten für bestimmte Arten von Bildtransformationen und profitieren Sie davon nehmen.

An der Spitze, die schnellsten Algorithmen; an der Unterseite der langsamste (obwohl genauer). Sie könnten die langsamen überspringen, wenn ein gutes Spiel auf dem schnelleren Niveau gefunden wird.

  • Datei-Hash-basierte (MD5, SHA1, usw.) für die exakte Duplikate
  • Wahrnehmungs Hashing (phash) für umskalierten Bilder
  • merkmalsbasierte (SIFT) für modifizierte Bilder

Ich habe sehr gute Ergebnisse mit phash. Die Genauigkeit ist gut für umskalierten Bilder. Es ist nicht gut für (wahrnehmungs) modifizierten Bilder (beschnitten, gedreht, gespiegelt, etc). Um mit der Hashing-Geschwindigkeit umgehen müssen wir eine Platten-Cache / Datenbank verwenden, um die Hash-Werte für die Heuhaufen zu halten.

Das wirklich Schöne an phash ist, dass, sobald Sie Ihre Hash-Datenbank aufbauen (für mich, die etwa 1000 Bilder / s sind), kann die Suche sehr, sehr schnell, insbesondere wenn Sie die gesamte Hash-Datenbank im Speicher halten können . Das ist ziemlich praktisch, da ein Hash ist nur 8 Byte.

Zum Beispiel, wenn Sie eine Million Bilder habe es eine Reihe von 1 Million 64-Bit-Hash-Werten (8 MB) erforderlich. Bei einigen CPUs paßt dies in dem L2 / L3-Cache! In der praktischen Anwendung habe ich ein COREi7 bei über 1 Giga-hamm / sec vergleichen zu sehen ist, ist es nur eine Frage der Speicherbandbreite in die CPU. A 1 Milliarde-Bilddatenbank ist praktisch auf einem 64-Bit-CPU (8 GB RAM benötigt) und sucht nicht mehr als 1 Sekunde!

Für modifizierte / beschnittene Bilder würde es scheinen, eine Transformation invariantes Merkmal / keypoint Detektor wie SIFT ist der Weg zu gehen. SIFT wird gut keypoints produzieren, die Ernte / drehen / Spiegel usw. erkennen jedoch die Beschreiber vergleichen ist sehr langsam im Vergleich zu Hamming-Distanz von phash verwendet. Dies ist eine große Einschränkung. Es gibt eine Menge zu tun, vergleicht, da es maximal IxJxK Deskriptor vergleicht ein Bild zum Nachschlagen (I = num Heuhaufen Bilder, J = Ziel keypoints pro Heuhaufen Bild, K = Ziel keypoints pro Nadel Bild).

Um die Geschwindigkeit Problem zu bekommen, habe ich versucht, mit phash um jeden gefundenen charakteristischen Punkt, mit der Strukturgröße / Radius das Unter Rechteck zu bestimmen. Der Trick macht diese Arbeit gut, ist den Radius zu wachsen / schrumpfen verschiedene Unter rect Ebene zu erzeugen (auf dem Nadel-Bild). Typischerweise wird die erste Stufe (unskaliert) jedoch oft passen es ein paar mehr nimmt. Ich bin nicht 100% sicher, warum dies funktioniert, aber ich kann mir vorstellen, es ermöglicht Funktionen, die zu klein sind für phash zu arbeiten (phash skaliert Bilder bis auf 32x32).

Ein weiteres Problem ist, dass SIFT wird die keypoints nicht optimal verteilen. Wenn es einen Bereich des Bildes mit vielen Kanten ist die keypoints dort Cluster und Sie werden nicht in einen anderen Bereich bekommen. Ich bin mit dem GridAdaptedFeatureDetector in OpenCV die Verteilung zu verbessern. Nicht sicher, welche Rastergröße ist am besten, ich bin mit einem kleinen Gitter (1x3 oder 3x1 je nach Bildformat).

Sie wollen wahrscheinlich alle Heuhaufen Bilder (und Nadel) auf eine kleinere Größe skalieren, bevor eine Erkennung verfügen (I 210px entlang maximale Dimension verwenden). Dies wird das Rauschen im Bild reduzieren (immer ein Problem für Computer Vision Algorithmen), auch Detektor auf prominenteren Funktionen konzentrieren.

Für Bilder von Menschen, könnten Sie die Gesichtserkennung versuchen und es verwenden, um die Bildgröße zu bestimmen, und die Rastergröße zu skalieren (zB größte Gesicht skaliert 100px zu sein). Der Merkmalsdetektor mehr Maßstabsebene (mit Pyramiden) macht, aber es ist eine Beschränkung, wie viele Ebene wird es verwenden (dies ist abstimmbaren natürlich).

Der keypoint Detektor wahrscheinlich am besten funktioniert, wenn es wieder weniger als ter Reihe von Funktionen, die Sie wollten. wenn Sie für 400 fragen zum Beispiel, und 300 zurück, das ist gut. Wenn Sie 400 jedes Mal wieder, wahrscheinlich einige gute Eigenschaften hatten weggelassen werden.

Die Nadel Bild kann weniger keypoints haben als die Heuhaufen Bilder und immer noch gute Ergebnisse zu erzielen. nicht mehr das Hinzufügen nicht notwendigerweise Sie riesige Gewinne erhalten, zum Beispiel mit J = 400 und K = 40 meiner Trefferquote beträgt etwa 92%. Mit J = 400 und K = 400 der Trefferquote geht nur bis zu 96%.

Wir können die Vorteile der extremen Geschwindigkeit der Hamming-Funktion übernehmen Skalierung zu lösen, Drehen, Spiegeln usw. Eine Mehrfachpass Technik verwendet werden kann. Bei jeder Iteration verwandelt die Unterrechtecke, Re-Hash, und wiederholen Sie die Suchfunktion.

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

Ein Ausgangspunkt für die Suche nach der Nähe Bilder könnte hier . Dies ist ein Werkzeug von CG Unternehmen genutzt, um zu überprüfen, ob neu gestaltete Bilder sind immer noch im Wesentlichen die gleiche Szene zeigen.

Ich habe eine Idee, die arbeiten kann und es sehr wahrscheinlich sehr schnell sein. Sie können ein Bild Teilprobe 80x60 Auflösung oder vergleichbar zu sagen, und wandelt es in Graustufen (nach Subsampling wird es schneller sein). Verarbeiten beide Bilder, die Sie vergleichen möchten. Dann laufen normalisierte Summe der quadrierten Unterschiede zwischen zwei Bildern (die Abfragebild und jeweils aus der db), oder noch besser normalisierte Kreuzkorrelation, die Antwort näher an 1 gibt, wenn beide Bilder sind ähnlich. Dann, wenn Bilder ähnlich sind, können Sie zu anspruchsvollere Techniken gehen um sicherzustellen, dass es die gleichen Bilder. Offensichtlich dieser Algorithmus ist linear in Bezug auf die Anzahl der Bilder in der Datenbank so dass, obwohl es sehr schnell sein wird bis zu 10.000 Bilder pro Sekunde auf der modernen Hardware. Wenn Sie Invarianz der Drehung benötigen, dann kann ein dominant Gradient berechnet werden für dieses kleine Bild, und dann die ganze Koordinatensystem kann auf kanonische gedreht werden Orientierung, dies wird allerdings sein, langsamer. Und nein, es gibt keine Invarianz hier maßstäblich.

Wenn Sie etwas allgemeinere oder mit großen Datenbanken (Millionen von Bildern), dann Sie müssen Image Retrieval Theorie aussehen in (Lasten der Papiere in den letzten 5 Jahren erschienen). Es gibt einige Hinweise in anderen Antworten. Aber es könnte sein Overkill, und das Histogramm Ansatz vorschlagen, wird die Arbeit machen. Obwohl ich würde denken Kombination vieler verschiedener schnell Ansätze noch besser sein wird.

Ich glaube, dass die Größe des Bildes bis zu einer fast Symbolgröße fallen, 48x48 sagen, dann in Graustufen umzuwandeln, dann die Differenz zwischen den Pixeln einnehmen oder Delta, sollte gut funktionieren. Weil wir die Änderung der Pixelfarbe sind zu vergleichen, eher als die tatsächliche Pixelfarbe, wird es keine Rolle, ob das Bild etwas heller oder dunkler ist. Große Veränderungen werden seit Pixel Rolle zu hell / dunkel wird, gehen verloren. Sie können dies viele über eine Zeile oder als anwenden, wie Sie die Genauigkeit erhöhen möchte. Allenfalls würden Sie 47x47 = 2209 Subtraktionen müssen machen, um einen vergleichbaren Schlüssel zu bilden.

Picking 100 zufällige Punkte könnte bedeuten, dass ähnliche (oder gelegentlich sogar unähnlich) Bilder als das gleiche markiert werden würden, was ich davon ausgehen, ist nicht das, was Sie wollen. MD5-Hashes nicht funktionieren würde, wenn die Bilder verschiedene Formate sind (PNG, JPEG, usw.), hatten unterschiedliche Größen oder hatten verschiedene Metadaten. Reduzieren Sie alle Bilder auf eine kleinere Größe ist eine gute Wette, einen Pixel-für- Pixel-Vergleich tun soll lange nicht nehmen, solange man eine gute Bild Bibliothek / Fast Sprache verwenden, und die Größe ist klein genug.

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

Wenn Sie eine große Anzahl von Bildern haben, schauen Sie in einem Bloom Filter , die verwendet mehrere Hashes für ein probablistic aber effizientes Ergebnis. Wenn die Anzahl der Bilder nicht sehr groß ist, dann ist ein kryptographischer Hash wie md5 sollte ausreichend sein.

Meine Firma hat über 24million Bilder kommen von Herstellern jeden Monat. Ich war auf der Suche nach einer schnellen Lösung, um sicherzustellen, dass die Bilder, die wir in unseren Katalog laden sind neue Bilder.

Ich möchte sagen, dass ich das Internet gesucht haben weit und breit zu versuchen, eine ideale Lösung zu finden. Ich habe sogar meinen eigenen Kantenerkennungsalgorithmus entwickelt.
Ich habe die Geschwindigkeit und Genauigkeit von mehreren Modellen bewertet. Meine Bilder, die weißen Hintergründe haben, arbeiten sehr gut mit phashing. Wie redcalx sagte, empfehle ich phash oder einHash. NICHT verwenden MD5-Hashing oder anyother kryptographischen Hashes. Es sei denn, dass Sie nur wollen EXACT Bild Streichhölzer. Größenänderungen oder Manipulation, die zwischen den Bildern auftritt, wird eine andere Hash ergeben.

Für phash / einHash, Check this out: imagehash

Ich wollte * redcalx '* s Beitrag erweitern, indem meinen Code und meine Genauigkeit zu veröffentlichen.

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  totalaccuracy
desk1  desk2       3
desk2  phone1     22
chair1 desk1      17
phone1 chair1     34

, wo das Element das eigentliche Thema des Bildes darstellt und die Zahl steht für das Ausmaß der Orientierung.

Hope, das hilft!

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top