Nahezu doppelte Bilderkennung [geschlossen]

Was ist ein schneller Weg, um einen bestimmten Satz von Bildern nach ihrer Ähnlichkeit zu sortieren?

Im Moment habe ich ein System, das Histogrammanalysen zwischen zwei Bildern durchführt, aber dies ist eine sehr teure Operation und scheint zu übertrieben.

Optimalerweise suche ich nach einem Algorithmus, der jedem Bild eine Bewertung gibt (zum Beispiel eine ganzzahlige Bewertung, wie z. B. den RGB-Durchschnitt), und ich kann einfach nach dieser Bewertung sortieren. Identische Scores oder Scores nebeneinander sind mögliche Duplikate.

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994 

RGB-Durchschnitt pro Bild ist zum Kotzen, gibt es etwas Ähnliches?

Es wurde viel über Bildsuche und Ähnlichkeitsmaße geforscht. Es ist kein einfaches Problem. Im Allgemeinen reicht eine einzelne intnicht aus, um festzustellen, ob Bilder sehr ähnlich sind. Sie haben eine hohe Falsch-Positiv-Rate.

Da jedoch viel recherchiert wurde, können Sie sich einige davon ansehen. In diesem Dokument (PDF) finden Sie beispielsweise einen kompakten Algorithmus für den Fingerabdruck von Bildern, mit dem Sie doppelte Bilder schnell und ohne Speicherung vieler Daten finden können. Es scheint, dass dies der richtige Ansatz ist, wenn Sie etwas Robustes wollen.

Wenn Sie nach etwas Einfacherem suchen, aber definitiv mehr Ad-hoc, hat diese SO-Frage ein paar anständige Ideen.

Ich würde empfehlen, nicht nur ein RGB-Histogramm zu verwenden.

Eine bessere Übersicht über Ihr Bild erhalten Sie, wenn Sie ein 2D-Haar-Wavelet des Bildes aufnehmen (es ist viel einfacher als es sich anhört, es ist nur eine Menge Mittelwertbildung und einige Quadratwurzeln, die zum Gewichten Ihrer Koeffizienten verwendet werden) und nur das k größte beibehalten gewichtete Koeffizienten im Wavelet als spärlicher Vektor, normalisieren Sie ihn und speichern Sie ihn, um seine Größe zu verringern. Sie sollten RG und B mindestens vorher mit Wahrnehmungsgewichten neu skalieren, oder ich würde empfehlen, zu YIQ (oder YCoCg, um Quantisierungsrauschen zu vermeiden) zu wechseln, damit Sie Chrominanzinformationen mit reduzierter Wichtigkeit abtasten können.

Sie können jetzt das Punktprodukt von zwei dieser spärlich normalisierten Vektoren als Maß für die Ähnlichkeit verwenden. Die Bildpaare mit den größten Punktprodukten werden in ihrer Struktur sehr ähnlich sein. Dies hat den Vorteil, dass es leicht widerstandsfähig gegen Größenänderung, Farbtonverschiebung und Wasserzeichen ist und sehr einfach zu implementieren und zu kompaktieren ist.

Sie können Speicher und Genauigkeit gegeneinander abwägen, indem Sie k erhöhen oder verringern.

Das Sortieren nach einer einzelnen numerischen Bewertung ist für diese Art von Klassifizierungsproblem nicht möglich. Wenn Sie darüber nachdenken, müssten Bilder nur entlang einer Achse "geändert" werden, aber nicht. Aus diesem Grund benötigen Sie einen Merkmalsvektor. Im Haar-Wavelet-Fall treten ungefähr dort die schärfsten Diskontinuitäten im Bild auf. Sie können einen Abstand zwischen Bildern paarweise berechnen. Da Sie jedoch nur eine Abstandsmetrik haben, kann eine lineare Reihenfolge kein Dreieck aus 3 Bildern ausdrücken, die alle gleich weit entfernt sind. (Denken Sie also an ein Bild, das ganz grün ist, ein Bild, das ganz rot ist und ein Bild, das ganz blau ist.)

Das bedeutet, dass jede echte Lösung für Ihr Problem O (n ^ 2) -Operationen in der Anzahl der Bilder benötigt, die Sie haben. Wenn es möglich gewesen wäre, das Maß zu linearisieren, könnten Sie nur O (n log n) oder O (n) benötigen, wenn das Maß beispielsweise für eine Radix-Sortierung geeignet wäre. Das heißt, Sie müssen kein O (n ^ 2) ausgeben, da Sie in der Praxis nicht den gesamten Satz durchsehen müssen, sondern nur das Zeug finden müssen, das näher als eine Schwelle liegt. Wenn Sie also eine von mehreren Techniken anwenden, um Ihren spärlichen Vektorraum zu partitionieren, können Sie viel schnellere Asymptotiken für das Problem "Finden von Bildern, die einem bestimmten Schwellenwert ähnlicher sind" erhalten, als jedes Bild naiv mit jedem Bild zu vergleichen und Ihnen was zu geben Sie brauchen wahrscheinlich ... wenn nicht genau das, wonach Sie gefragt haben.

Auf jeden Fall habe ich dies vor einigen Jahren persönlich genutzt, um die Anzahl der verschiedenen Texturen, die ich gespeichert habe, zu minimieren, aber es gab auch viel Forschungsrauschen in diesem Bereich, das seine Wirksamkeit zeigt (und in diesem Fall vergleicht) es zu einer komplexeren Form der Histogrammklassifizierung):

http://www.cs.princeton.edu/cass/papers/spam_ceas07.pdf

Wenn Sie eine bessere Erkennungsgenauigkeit benötigen, können die Algorithmen minHash und tf-idf mit dem Haar-Wavelet (oder dem Histogramm) verwendet werden, um Änderungen robuster zu verarbeiten:

http://cmp.felk.cvut.cz/~chum/papers/chum_bmvc08.pdf

Schließlich hat Stanford eine Bildsuche, die auf einer exotischeren Variante dieses Ansatzes basiert und auf einer stärkeren Merkmalsextraktion aus den Wavelets basiert, um gedrehte oder skalierte Bildabschnitte usw. zu finden. Dies geht jedoch wahrscheinlich weit über den Arbeitsaufwand hinaus würde tun wollen.

http://wang14.ist.psu.edu/cgi-bin/zwang/regionsearch_show.cgi

Ich habe dafür einen sehr zuverlässigen Algorithmus namens Fast Multiresolution Image Querying implementiert . Mein (alter, nicht gepflegter) Code dafür ist hier .

Bei der schnellen Abfrage von Bildern mit mehreren Auflösungen wird das Bild basierend auf dem YIQ-Farbraum in drei Teile aufgeteilt (besser für die Anpassung von Unterschieden als für RGB). Dann wird das Bild im Wesentlichen unter Verwendung eines Wavelet-Algorithmus komprimiert, bis nur die hervorstechendsten Merkmale aus jedem Farbraum verfügbar sind. Diese Punkte werden in einer Datenstruktur gespeichert. Abfragebilder durchlaufen denselben Prozess, und die herausragenden Merkmale im Abfragebild werden mit denen in der gespeicherten Datenbank abgeglichen. Je mehr Übereinstimmungen, desto wahrscheinlicher sind die Bilder ähnlich.

Der Algorithmus wird häufig für die Funktion "Abfrage nach Skizze" verwendet. Meine Software erlaubte nur die Eingabe von Abfragebildern über eine URL, daher gab es keine Benutzeroberfläche. Ich fand jedoch, dass es außergewöhnlich gut funktioniert, um Miniaturansichten an die große Version dieses Bildes anzupassen.

Viel beeindruckender als meine Software ist Retrievr, mit dem Sie den FMIQ-Algorithmus mit Flickr-Bildern als Quelle ausprobieren können. Sehr cool! Probieren Sie es per Skizze oder mit einem Quellbild aus und Sie können sehen, wie gut es funktioniert.

Ein Bild hat viele Funktionen. Wenn Sie sich also nicht auf eine wie die durchschnittliche Helligkeit beschränken, haben Sie es mit einem n-dimensionalen Problemraum zu tun.

Wenn ich Sie bitten würde, den Städten der Welt eine einzige Ganzzahl zuzuweisen, damit ich erkennen kann, welche nahe beieinander liegen, wären die Ergebnisse nicht großartig. Sie können beispielsweise die Zeitzone als einzelne Ganzzahl auswählen und mit bestimmten Städten gute Ergebnisse erzielen. Eine Stadt in der Nähe des Nordpols und eine andere Stadt in der Nähe des Südpols können sich jedoch ebenfalls in derselben Zeitzone befinden, obwohl sie sich an entgegengesetzten Enden des Planeten befinden. Wenn ich Sie zwei ganze Zahlen verwenden lasse, können Sie mit Breiten- und Längengraden sehr gute Ergebnisse erzielen. Das Problem ist das gleiche für die Bildähnlichkeit.

Alles in allem gibt es Algorithmen, die versuchen, ähnliche Bilder zu gruppieren, was genau das ist, wonach Sie fragen. Dies passiert, wenn Sie mit Picasa eine Gesichtserkennung durchführen. Noch bevor Sie Gesichter identifizieren, werden ähnliche Gesichter zusammengefasst, sodass Sie problemlos eine Reihe ähnlicher Gesichter durchgehen und den meisten den gleichen Namen geben können.

Es gibt auch eine Technik namens Prinzipielle Komponentenanalyse, mit der Sie n-dimensionale Daten auf eine kleinere Anzahl von Dimensionen reduzieren können. Ein Bild mit n Merkmalen könnte also auf ein Merkmal reduziert werden. Dies ist jedoch immer noch nicht der beste Ansatz zum Vergleichen von Bildern.

Es gibt eine C-Bibliothek ("libphash" - http://phash.org/ ), die einen "Wahrnehmungs-Hash" eines Bildes berechnet und es Ihnen ermöglicht, ähnliche Bilder durch Vergleichen von Hashes zu erkennen (damit Sie nicht jedes Bild vergleichen müssen) direkt gegen jedes andere Bild), aber leider schien es nicht sehr genau zu sein, als ich es versuchte.

Sie müssen entscheiden, was "ähnlich" ist. Kontrast? Farbton?

Ist ein Bild dem gleichen Bild verkehrt herum "ähnlich"?

Ich wette, Sie können viele "enge Anrufe" finden, indem Sie Bilder in 4x4-Teile zerlegen und für jede Gitterzelle eine durchschnittliche Farbe erhalten. Sie hätten 16 Punkte pro Bild. Um die Ähnlichkeit zu beurteilen, würden Sie einfach eine Summe von Quadraten mit Unterschieden zwischen Bildern erstellen.

Ich denke nicht, dass ein einzelner Hash Sinn macht, es sei denn, er widerspricht einem einzelnen Konzept wie Farbton, Helligkeit oder Kontrast.

Hier ist deine Idee:

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994

Zunächst gehe ich davon aus, dass es sich um Dezimalzahlen handelt, die R * (2 ^ 16) + G * (2 ^ 8) + B sind, oder so ähnlich. Offensichtlich ist das nicht gut, weil Rot übermäßig gewichtet wird.

Ein Umzug in den HSV-Raum wäre besser. Sie könnten die HSV-Teile in den Hash verteilen , oder Sie könnten einfach H oder S oder V einzeln festlegen oder Sie könnten drei Hashes pro Bild haben.

Eine Sache noch. Wenn Sie R, G und B gewichten. Gewicht am höchsten grün, dann rot, dann blau, um der visuellen Empfindlichkeit des Menschen zu entsprechen.

Im Zeitalter der Webdienste können Sie http://tineye.com ausprobieren

Die Frage Gute Möglichkeit, ähnliche Bilder zu identifizieren? scheint eine Lösung für Ihre Frage zu bieten.

Ich nahm an, dass eine andere Software zur Suche nach doppelten Bildern eine FFT für die Bilder ausführt und die Werte der verschiedenen Frequenzen als Vektoren speichert:

Image1 = (u1, u2, u3, ..., un)
Image2 = (v1, v2, v3, ..., vn)

und dann können Sie zwei Bilder auf Gleichheit vergleichen, indem Sie den Abstand zwischen den Gewichtsvektoren zweier Bilder berechnen :

distance = Sqrt(
     (u1-v1)^2 +
     (u2-v2)^2 +
     (u2-v3)^2 +
     ...
     (un-vn)^2);

Eine Lösung besteht darin, einen RMS / RSS- Vergleich für jedes Bildpaar durchzuführen, das für eine Blasensortierung erforderlich ist. Zweitens könnten Sie eine FFT für jedes Bild durchführen und eine Achsenmittelung durchführen, um eine einzelne Ganzzahl für jedes Bild abzurufen, nach der Sie als Index sortieren würden. Sie können einen Vergleich mit einer verkleinerten Version (25%, 10%) des Originals in Betracht ziehen, je nachdem, wie gering der Unterschied ist, den Sie ignorieren, und wie viel Beschleunigung Sie benötigen. Lassen Sie mich wissen, ob diese Lösungen interessant sind, und wir können diskutieren oder ich kann Beispielcode bereitstellen.

Die meisten modernen Ansätze zur Erkennung von nahezu doppelten Bildern verwenden eine interessante Punkterkennung und Deskriptoren, die den Bereich um solche Punkte beschreiben. Oft wird SIFT verwendet. Anschließend können Sie Deskriptoren quatisieren und Cluster als visuelles Wortvokabular verwenden.

Wenn wir also das Verhältnis der gemeinsamen visuellen Wörter zweier Bilder zu allen visuellen Wörtern dieser Bilder sehen, schätzen Sie die Ähnlichkeit zwischen den Bildern. Es gibt viele interessante Artikel. Eine davon ist die nahezu doppelte Bilderkennung: minHash- und tf-idf-Gewichtung

Mit der IMMI-Erweiterung und IMMI können Sie beispielsweise viele verschiedene Methoden untersuchen, um die Ähnlichkeit zwischen Bildern zu messen: http://spl.utko.feec.vutbr.cz/en/component/content/article/46-image-processing-extension- for-rapidminer-5

Durch Definieren eines Schwellenwerts und Auswählen einer Methode können Sie die Ähnlichkeit messen.