Bildfingerabdruck zum Vergleich der Ähnlichkeit vieler Bilder

94

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

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

Philip Dreyer
quelle
1
Sprache, für die die Bibliothek sein sollte?
Ben S

Antworten:

57

Normale Hashing- oder CRC-Berechnungsalgorithmen funktionieren mit Bilddaten nicht gut. Die dimensionale Natur der Informationen muss berücksichtigt werden.

Wenn Sie einen äußerst robusten Fingerabdruck benötigen, bei dem affine Transformationen (Skalierung, Drehung, Translation, Spiegeln) berücksichtigt werden, können Sie eine Radon-Transformation für die Bildquelle verwenden , um eine normative Abbildung der Bilddaten zu erstellen. Speichern Sie diese 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 Leuchtkrafthistogramm 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 für eine verbesserte Vergleichsqualität

Ein Helligkeitshistogramm (insbesondere eines, das in RGB-Komponenten unterteilt ist) ist ein angemessener Fingerabdruck für ein Bild - und kann sehr effizient implementiert werden. Wenn Sie ein Histogramm von einem anderen subtrahieren, wird ein neues Histogramm erstellt, mit dem Sie entscheiden können, wie ähnlich zwei Bilder sind. Histogramme, da nur die Verteilung und das Auftreten von Leuchtkraft- / Farbinformationen die affinen Transformationen recht gut handhaben. Wenn Sie die Leuchtkraftinformationen jeder Farbkomponente auf einen 8-Bit-Wert quantisieren, reichen 768 Byte Speicherplatz für den Fingerabdruck eines Bildes mit nahezu jeder vernünftigen Größe aus. Helligkeitshistogramme erzeugen falsch negative Ergebnisse, wenn die Farbinformationen in einem Bild bearbeitet werden. Wenn Sie Transformationen wie Kontrast / Helligkeit, Posterisierung, Farbverschiebung und Änderung der Helligkeitsinformationen anwenden.

Die Verwendung skalierter Bilder ist eine weitere Möglichkeit, die Informationsdichte des Bildes auf ein Niveau zu reduzieren, das einfacher zu vergleichen ist. Bei einer Reduzierung unter 10% der ursprünglichen Bildgröße gehen im Allgemeinen zu viele Informationen verloren, um verwendet zu werden. Daher kann ein Bild mit 800 x 800 Pixel auf 80 x 80 verkleinert werden und bietet dennoch genügend Informationen, um einen anständigen Fingerabdruck durchzuführen. Im Gegensatz zu Histogrammdaten müssen Sie eine anisotrope Skalierung der Bilddaten durchführen, wenn die Quellauflösungen unterschiedliche Seitenverhältnisse aufweisen. Mit anderen Worten, das Reduzieren eines 300 x 800-Bilds in ein 80 x 80-Miniaturbild führt zu einer Verformung des Bildes, sodass im Vergleich zu einem 300 x 500-Bild (das sehr ähnlich ist) falsch negative Ergebnisse erzielt werden. Thumbnail-Fingerabdrücke führen auch häufig zu falsch negativen Ergebnissen, wenn affine Transformationen beteiligt sind. Wenn Sie ein Bild spiegeln oder drehen,

Die Kombination beider Techniken ist ein vernünftiger Weg, um Ihre Wetten abzusichern und das Auftreten von falsch positiven und falsch negativen Ergebnissen zu reduzieren.

LBushkin
quelle
In Bezug auf CRC vereinbart. Wenn man es jedoch verwenden möchte, ist es besser, MD5-Hash als CRC32 zu verwenden
Mloskot
5
Sie möchten MD5 nicht verwenden, da es sich um einen kryptografischen Einweg-Hash handelt. Sie müssen eine Hash-Methode verwenden, die ein ähnliches Ergebnis für eine ähnliche Eingabe liefert, damit Sie die Unterschiede zwischen den Hashes direkt vergleichen können.
AJ Quick
34

Es gibt einen viel weniger ad-hoc-Ansatz als die hier vorgeschlagenen verkleinerten Bildvarianten, der seinen allgemeinen Geschmack beibehält, aber eine viel strengere mathematische Grundlage für das Geschehen bietet.

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

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

Edward KMETT
quelle
20

Sie sollten sich auf jeden Fall Phash ansehen .

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

Und mein kleiner Javascript- Klon: https://redaktor.me/phasher/demo_js/index.html

Leider basiert dies auf "Bitcount", erkennt jedoch gedrehte Bilder. Ein anderer Ansatz in Javascript bestand darin, aus dem Bild mithilfe der Leinwand ein Helligkeitshistogramm zu erstellen. Sie können ein Polygonhistogramm auf der Leinwand visualisieren und dieses Polygon in Ihrer Datenbank vergleichen (z. B. mySQL räumlich ...).

Sebilasse
quelle
ist das auf npm? Ich suche nach einer Möglichkeit, die Ähnlichkeit zwischen zwei Bildern mit Javascript zu vergleichen
chovy
Hm, ich dachte es ist "zu billig für npm". Es war wirklich nur eine Demo, die schnell von Grund auf neu geschrieben wurde. Sie können jedoch jederzeit mit der Quelle tun, was Sie möchten. Wenn ich es schaffen kann, werde ich es später untersuchen und es an github github.com/redaktor senden ...
sebilasse
@SebastianLasse Ich habe gerade Ihren JS-Port überprüft und es ist fantastisch! Ich möchte nur, dass Sie einen Bild-URI an die Compare()Funktion übergeben können, anstatt das Bild zuerst herunterladen zu müssen. Nach meinen Tests sollte der Schwellenwert für "ein sehr ähnliches Bild"> 90% und nicht> 98% sein.
Dooan
12

Vor langer Zeit habe ich an einem System gearbeitet, das einige ähnliche Eigenschaften aufweist, 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 Videos mit einer Auflösung von 4: 3, sodass wir 12 Zonen verwendeten. 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

Für jedes Bild speichern Sie also n + 1ganzzahlige Werte, wobei ndie Anzahl der Zonen angegeben 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 - beispielsweise 10%
  2. Wenn sich die Bilder innerhalb des Schwellenwerts befinden, vergleichen Sie als nächstes jede Zone. Wenn sich auch alle Zonen innerhalb des Schwellenwerts befinden, stimmen die Bilder so stark überein, dass Sie sie zumindest zum weiteren Vergleich markieren 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 höheres Übereinstimmungsvertrauen zu erzielen.

GalacticCowboy
quelle
6

Ähnlich wie bei Ics Antwort 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 es übereinstimmt, können Sie sie mit der nächsthöheren Auflösung vergleichen und so weiter.

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.

Allklauen
quelle
Dies ist eine Art Baumsuche, denke ich. Es ist interessant.
André Laszlo
3

Sie möchten also einen "Fingerabdruck-Abgleich" durchführen, der sich deutlich von dem "Bild-Abgleich" 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 sicherzustellen (in Bezug auf FAR- und FRR- Messungen - Falsche Akzeptanzrate und Falsche Ablehnungsrate ).

Ich schlage vor, dass Sie sich die LFA- Klasse (Local Feature Analysis) der Erkennungstechniken genauer ansehen , die hauptsächlich auf Minutieninspektionen basieren. Minutien sind spezifische Merkmale eines Fingerabdrucks und wurden in mehrere Klassen eingeteilt. Das Zuordnen eines Rasterbilds zu einer Minutienkarte ist das, was die meisten Behörden tatsächlich tun, um Kriminelle oder Terroristen einzureichen.

Sehen Sie hier für weitere Referenzen

Sambia
quelle
Wissen Sie, wie Sie die Rate der falschen Akzeptanz berechnen, wenn Sie eine Gaußsche Verteilung der Bewertungen für ein bestimmtes biometrisches System haben?
GobiasKoffi
OP möchte "Fingerabdrücke vieler Bilder erstellen". Vergleichen Sie keine Bilder von menschlichen Fingerabdrücken.
Navin
3

Ab 2015 (zurück in die Zukunft ... zu dieser Frage von 2009, die jetzt bei Google einen hohen Stellenwert hat) kann die Bildähnlichkeit mithilfe von Deep-Learning-Techniken berechnet werden. Die als Auto Encoder bekannte Familie von Algorithmen kann eine Vektordarstellung erstellen, die nach Ähnlichkeit durchsucht werden kann. Es gibt eine Demo hier .

Alex R.
quelle
Ist es möglich, aus Binärdaten ein Fingerabdruckbild zu erzeugen?
SwR
Sicher, es gibt ANNs für diese Aufgabe, aber Ihre Antwort scheint eigentlich nichts zu beantworten. Die Frage ist: Wie geht das? Die verlinkte Seite enthält keine Informationen und der Begriff "Auto Encoder" hilft auch nicht.
Simon Steinberger
In der ursprünglichen Frage steht nicht "Wie wird das gemacht?", sondern "Einige Hinweise auf vorhandene Algorithmen würden mir sehr helfen", was ich angegeben habe.
Alex R
Sie haben keinen "Hinweis" mit einem Algorithmus verknüpft, tatsächlich heißt es auf der verlinkten Seite: "Es funktioniert, aber niemand weiß warum. Bitte erwarten Sie nicht zu viel über das Ergebnis" ...
odyth
Dieses deeplearning4j.org/deepautoencoder#use-cases bietet mehr Klarheit darüber, wie Auto Encoder zum Erstellen eines Fingerabdrucks verwendet werden können und wie Sie diesen Fingerabdruck verwenden können, um Ähnlichkeiten in anderen Bildern basierend auf der Ähnlichkeit der Scheitelpunkte zu finden.
odyth
2

Eine Möglichkeit, dies zu tun, besteht darin, die Bildgröße zu ändern und die Auflösung erheblich zu verringern (möglicherweise auf 200 x 200?). Dabei wird eine kleinere (pixelgemittelte) Version für den Vergleich gespeichert. Definieren Sie dann eine Toleranzschwelle und vergleichen Sie jedes Pixel. Wenn das RGB aller Pixel innerhalb der Toleranz liegt, 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, was bedeutet (abzüglich der Zeit zum Ändern der Bildgröße) 200(H)*200(W)*500,000(images)*3(RGB)= 60.000.000.000 Vergleiche. Wenn jedes Bild genau übereinstimmt, werden Sie zurückfallen, aber das wird wahrscheinlich nicht der Fall sein, oder? Denken Sie daran, dass Sie ein Bild als Übereinstimmung rabattieren können, sobald ein einzelner Vergleich Ihren Schwellenwert überschreitet.

lc.
quelle
2

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 basierend auf bestimmten Deskriptoren? Dann können Sie sich beispielsweise den MPEG-7-Standard für die Multimedia-Inhaltsbeschreibungsoberfläche ansehen. Dann könnten Sie die verschiedenen Bilddeskriptoren vergleichen, die nicht so genau, aber viel schneller sind.

Anonym
quelle
Vielleicht eine Wahl zwischen erschöpfend und begrenzt
Johnny
0

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 byteidentischen Bildern, anstatt nach Bildern zu suchen, die von derselben Quelle stammen, aber möglicherweise ein anderes Format oder eine andere Auflösung haben (was mir als ziemlich schwieriges Problem erscheint).

Ian Hopkinson
quelle