wake-up-neo.net

Bildfingerabdruck zum Vergleich der Ähnlichkeit vieler Bilder

Ich muss Fingerabdrücke von vielen Bildern erstellen (ca. 100.000 vorhandene, 1000 neue pro Tag, RGB, JPEG, maximale Größe 800x800), um jedes Bild sehr schnell mit jedem anderen Bild zu vergleichen. Ich kann keine binären Vergleichsmethoden verwenden, da auch nahezu ähnliche Bilder erkannt werden sollten.

Am besten wäre eine vorhandene Bibliothek, aber auch einige Hinweise auf vorhandene Algorithmen würden mir sehr helfen.

91
Philip Dreyer

Normale Hashing- oder CRC-Berechnungsalgorithmen funktionieren mit Bilddaten nicht gut. Die Dimension der Information muss berücksichtigt werden.

Wenn Sie extrem robuste Fingerabdrücke benötigen, sodass affine Transformationen (Skalierung, Rotation, Translation, Spiegeln) berücksichtigt werden, können Sie eine normative Abbildung der Bilddaten mit Radontransformation auf der Bildquelle erstellen - Speichern Sie dies mit jedem Bild und vergleichen Sie dann nur die Fingerabdrücke. Dies ist ein komplexer Algorithmus und nichts für schwache Nerven.

einige einfache Lösungen sind möglich:

  1. Erstellen Sie ein Helligkeitshistogramm für das Bild als Fingerabdruck
  2. Erstellen Sie verkleinerte Versionen jedes Bildes als Fingerabdruck
  3. Kombinieren Sie die Techniken (1) und (2) zu einem Hybridansatz, um die Vergleichsqualität zu verbessern

Ein Leuchtkrafthistogramm (insbesondere eines, das in RGB-Komponenten unterteilt ist) ist ein vernünftiger Fingerabdruck für ein Bild - und kann sehr effizient implementiert werden. Wenn Sie ein Histogramm von einem anderen subtrahieren, wird ein neues Verlaufsprogramm erstellt, das Sie verarbeiten können, um zu bestimmen, wie ähnlich zwei Bilder sind. Histogramme, weil sie nur die Verteilung und das Auftreten von Leuchtkraft-/Farbinformationen auswerten, handhaben affine Transformationen recht gut. Wenn Sie die Luminanzinformationen jeder Farbkomponente auf einen 8-Bit-Wert reduzieren, reichen 768 Byte Speicherplatz für den Fingerabdruck eines Bilds mit nahezu jeder vernünftigen Größe aus. Leuchtkrafthistogramme erzeugen falsche Negative, wenn die Farbinformationen in einem Bild manipuliert werden. Wenn Sie Transformationen wie Kontrast/Helligkeit, Postergröße, Farbverschiebung und Helligkeitsinformationen anwenden, werden diese geändert. Bei bestimmten Bildtypen sind auch Fehlalarme möglich, z. B. Landschaften und Bilder, bei denen eine einzige Farbe die anderen dominiert.

Die Verwendung von skalierten Bildern ist eine weitere Möglichkeit, die Informationsdichte des Bildes auf ein Niveau zu reduzieren, das einfacher zu vergleichen ist. Bei Verkleinerungen unter 10% der ursprünglichen Bildgröße gehen im Allgemeinen zu viele Informationen verloren, als dass sie verwendet werden könnten. Daher kann ein 800 x 800 Pixel großes Bild auf 80 x 80 verkleinert werden, und es werden immer noch genügend Informationen bereitgestellt, um einen angemessenen Fingerabdruck durchzuführen. Im Gegensatz zu Histogrammdaten müssen Sie die Bilddaten anisotrop skalieren, wenn die Quellauflösungen unterschiedliche Seitenverhältnisse aufweisen. Mit anderen Worten, das Verkleinern eines 300x800-Bildes in ein 80x80-Miniaturbild führt zu einer Verformung des Bildes, sodass im Vergleich zu einem 300x500-Bild (das sehr ähnlich ist) falsche Negative auftreten. Miniaturbild-Fingerabdrücke erzeugen häufig auch falsche Negative, wenn affine Transformationen beteiligt sind. Wenn Sie ein Bild spiegeln oder drehen, unterscheidet sich die Miniaturansicht erheblich vom Original und kann zu einem falschen Positiv führen.

Die Kombination beider Techniken ist ein vernünftiger Weg, um Ihre Einsätze abzusichern und das Auftreten von falschen Positiven und falschen Negativen zu reduzieren.

55
LBushkin

Es gibt viel weniger Ad-hoc-Ansätze als die hier vorgeschlagenen verkleinerten Bildvarianten, die ihren allgemeinen Charakter behalten, aber eine wesentlich strengere mathematische Grundlage für das bieten, was vor sich geht.

Nehmen Sie ein Haar Wavelet des Bildes. Grundsätzlich ist das Haar-Wavelet die Folge von Unterschieden zwischen den Bildern mit niedrigerer Auflösung und jedem Bild mit höherer Auflösung, jedoch gewichtet nach der Tiefe, in der Sie sich im "Baum" der Mipmaps befinden. Die Berechnung ist unkompliziert. Sobald Sie das Haar-Wavelet richtig gewichtet haben, werfen Sie alle bis auf die k größten Koeffizienten (in Bezug auf den Absolutwert) weg, normalisieren Sie den Vektor und speichern Sie ihn.

Wenn Sie das Skalarprodukt von zwei dieser normalisierten Vektoren nehmen, erhalten Sie ein Ähnlichkeitsmaß, wobei 1 nahezu identisch ist. Ich habe mehr Informationen über hier gepostet.

33
Edward KMETT

Sie sollten sich unbedingt phash ansehen.

Zum Bildvergleich gibt es dieses php Projekt: https://github.com/kennethrapp/phasher

Und mein kleiner Javascript Klon: https://redaktorcms.com/dev/phasher/demo_js/index.html

Leider ist dies "bitcount" -basiert, erkennt aber gedrehte Bilder. Ein anderer Ansatz in Javascript war es, mit Hilfe der Leinwand ein Histogramm der Leuchtkraft aus dem Bild zu erstellen. Sie können ein Polygon-Histogramm auf der Zeichenfläche visualisieren und dieses Polygon in Ihrer Datenbank vergleichen (z. B. mySQL Spatial ...).

Dies ist eine Demo für Video-Histogramme: https://redaktorcms.com/dev/globetrottr/testHashVideo.php

19
sebilasse

Vor langer Zeit habe ich an einem System mit ähnlichen Eigenschaften gearbeitet, und dies ist eine Annäherung an den Algorithmus, dem wir gefolgt sind:

  1. Teilen Sie das Bild in Zonen. In unserem Fall handelte es sich um ein Video mit einer Auflösung von 4: 3, also verwendeten wir 12 Zonen. Dadurch wird die Auflösung der Quellbilder aus dem Bild entfernt.
  2. Berechnen Sie für jede Zone eine Gesamtfarbe - den Durchschnitt aller Pixel in der Zone
  3. Berechnen Sie für das gesamte Bild eine Gesamtfarbe - den Durchschnitt aller Zonen

Sie speichern also für jedes Bild n + 1 Integer-Werte, wobei n die Anzahl der Zonen ist, die Sie verfolgen.

Für Vergleiche müssen Sie auch jeden Farbkanal einzeln betrachten.

  1. Vergleichen Sie für das Gesamtbild die Farbkanäle für die Gesamtfarben, um festzustellen, ob sie innerhalb eines bestimmten Schwellenwerts liegen - z. B. 10%.
  2. Wenn die Bilder innerhalb des Schwellenwerts liegen, vergleichen Sie als nächstes jede Zone. Wenn sich auch alle Zonen innerhalb des Schwellenwerts befinden, stimmen die Bilder so gut überein, dass Sie sie zumindest für einen weiteren Vergleich kennzeichnen können.

Auf diese Weise können Sie Bilder, die nicht übereinstimmen, schnell verwerfen. Sie können auch mehr Zonen verwenden und/oder den Algorithmus rekursiv anwenden, um ein besseres Übereinstimmungsvertrauen zu erzielen.

11
GalacticCowboy

Ähnlich wie bei der Antwort von Ic können Sie versuchen, die Bilder mit mehreren Auflösungen zu vergleichen. So wird jedes Bild als 1x1, 2x2, 4x4 .. 800x800 gespeichert. Wenn die niedrigste Auflösung nicht übereinstimmt (vorbehaltlich eines Schwellenwerts), können Sie sie sofort ablehnen. Wenn dies zutrifft, können Sie sie mit der nächsthöheren Auflösung vergleichen und so weiter.

Auch - wenn die Bilder eine ähnliche Struktur aufweisen, z. B. medizinische Bilder, können Sie diese Struktur möglicherweise in eine Beschreibung extrahieren, die einfacher/schneller zu vergleichen ist.

6
allclaws

Sie möchten also einen "Fingerabdruckabgleich" durchführen, der sich von "Bildabgleich" deutlich unterscheidet. Die Analyse von Fingerabdrücken wurde in den letzten 20 Jahren eingehend untersucht und es wurden mehrere interessante Algorithmen entwickelt, um die richtige Erkennungsrate (in Bezug auf [~ # ~] weit [~ # ~] zu gewährleisten. und [~ # ~] frr [~ # ~] Maßnahmen - Falsche Akzeptanzrate und Falsche Ablehnungsrate ).

Ich schlage vor, dass Sie sich die Klasse der LFA-Erkennungstechniken (Local Feature Analysis) genauer ansehen, die hauptsächlich auf der Prüfung von Details aufbauen. Minutien sind spezifische Merkmale eines Fingerabdrucks und wurden in mehrere Klassen eingeteilt. Das Mappen eines Rasterbilds auf eine Minutienkarte ist das, was die meisten Behörden tatsächlich tun, um Kriminelle oder Terroristen zu registrieren.

Siehe hier für weitere Referenzen

3
ZZambia

Informationen zum Vergleich von iPhone-Bildern und zur Entwicklung von Bildähnlichkeiten finden Sie unter: http://sites.google.com/site/imagecomparison/

Schauen Sie sich eyeBuy Visual Search im iTunes AppStore an, um es in Aktion zu sehen.

3
Brett

Ab 2015 (zurück in die Zukunft ... auf dieser 2009 in Google hochrangigen Frage) kann die Bildähnlichkeit mithilfe von Deep-Learning-Techniken berechnet werden. Die als Auto Encoder bekannte Algorithmenfamilie kann eine Vektordarstellung erstellen, die nach Ähnlichkeit durchsucht werden kann. Es gibt eine Demo hier .

2
Alex R

Eine Möglichkeit besteht darin, die Größe des Bilds zu ändern und die Auflösung erheblich zu verringern (auf 200x200?), Wobei für den Vergleich eine kleinere (pixelgemittelte) Version gespeichert wird. Definieren Sie dann eine Toleranzschwelle und vergleichen Sie jedes Pixel. Wenn die RGB-Werte aller Pixel innerhalb der Toleranz liegen, haben Sie eine Übereinstimmung.

Ihr erster Durchlauf ist O (n ^ 2), aber wenn Sie alle Übereinstimmungen katalogisieren, ist jedes neue Bild nur ein O(n)-Algorithmus zum Vergleichen (Sie müssen es nur mit jedem zuvor eingefügten Bild vergleichen). . Es wird jedoch irgendwann zusammenbrechen, wenn die Liste der zu vergleichenden Bilder größer wird, aber ich denke, Sie sind für eine Weile in Sicherheit.

Nach 400 Tagen haben Sie 500.000 Bilder, dh (abzüglich der Zeit zum Verkleinern des Bildes) 200(H)*200(W)*500,000(images)*3(RGB) = 60.000.000.000 Vergleiche. Wenn jedes Bild genau übereinstimmt, werden Sie ins Hintertreffen geraten, aber das wird wahrscheinlich nicht der Fall sein, oder? Denken Sie daran, dass Sie ein Bild als Treffer ausschließen können, sobald ein einzelner Vergleich außerhalb Ihres Schwellenwerts liegt.

2
lc.

Möchten Sie buchstäblich jedes Bild mit den anderen vergleichen? Was ist die Anwendung? Vielleicht brauchen Sie nur eine Art Indizierung und Abruf von Bildern, die auf bestimmten Deskriptoren basieren? Dann können Sie sich beispielsweise den MPEG-7-Standard für die Schnittstelle zur Beschreibung von Multimedia-Inhalten ansehen. Dann könnten Sie die verschiedenen Bilddeskriptoren vergleichen, die zwar nicht so genau, dafür aber viel schneller sind.

2
Anonymous

Es scheint, dass spezialisierte Bild-Hashing-Algorithmen ein Bereich aktiver Forschung sind, aber vielleicht würde eine normale Hash-Berechnung der Bildbytes den Trick tun.

Suchen Sie nach byte-identischen Bildern, anstatt nach Bildern zu suchen, die aus derselben Quelle stammen, aber möglicherweise ein anderes Format oder eine andere Auflösung haben (was für mich ein ziemlich schweres Problem darstellt).

0
Ian Hopkinson