Ich habe ungefähr 150.000 Bilder und einige davon sind Duplikate. Ich habe herausgefunden, dass der SSIM-Algorithmus eine gute Wahl ist, um zwei Bilder zu vergleichen und zu sehen, ob es sich um Duplikate handelt. Wenn ich jedoch auf diese Weise Dubletten finden möchte, muss ich 150.000 * 149.999 Bilder vergleichen, die ewig dauern würden.
Was ich jetzt suche, ist ein schneller und effektiver Algorithmus, um einen Durchschnittswert für jedes Bild zu erstellen und dann nur Bilder zu vergleichen, die ihrem Durchschnittswert nahe kommen.
Kurz gesagt: Ich suche nach einer effektiven Art, Bilder zu kategorisieren!
Ich plane, die C ++ - CImg-Bibliothek für diese Aufgabe zu verwenden, weil sie schnell ist.
Danke!
Ich würde versuchen, einen Hash / Fingerabdruck Ansatz:
Generierung eines Fingerabdrucks für jedes Bild, der auch relevante Bildattribute wie Größe und Anzahl der Komponenten für eine Metadatei oder eine Datenbank enthält. Der Fingerabdruck könnte aus dem gemeinsamen Unterbild berechnet werden, dies könnte ein verlustbehaftetes komprimiertes Spektrogramm sein, ein einfacher Vektor, der die Häufigkeitsbins einer FFT enthält, ein Histogramm oder eine andere Technik (ich habe keine wirkliche Ahnung, was besser passt, das ist am meisten) wahrscheinlich sehr inhaltsabhängig).
Wie bereits erwähnt, wird die Gruppierung mit Bildattributen wie Größe und Anzahl der Farbkomponenten die Anzahl der (binären) Vergleiche stark reduzieren, was (n*(n-1))/2 für jede Gruppe bedeuten würde.
Vergleich der Fingerabdrücke mit angemessener Toleranz für weitere Untergruppen (achten Sie darauf, Fälle abzudecken, in denen ein Bild Übereinstimmungen in mehreren Gruppen aufweist).
OpenCV könnte das letzte Match machen:
Verwandte Fragen zum Bildvergleich mit OpenCV:
Es gibt Bilder, die in der Höhe variieren, aber im Grunde sind sie das gleiche Bild, das nur eine nicht verwandte Box auf der Unterseite hat, die die Höhe ändert.
Wenn der obere Teil des Bildes für zwei Duplikate immer gleich ist, könnten Sie versuchen, einen Hashwert basierend auf N Pixelzeilen im Bild zu berechnen, die ziemlich sicher sein sollen (dh Ihre Box im unteren Bereich hat Ich bin in diesen Zeilen).
Sobald Sie alle Ihre Dateien hashed haben, können Sie die Hashwerte sortieren und nur Bilder mit demselben Hashwert genauer vergleichen.
Jede Form von Hashing ist hier sinnlos, da selbst nahezu identische Bilder sehr unterschiedliche Hashwerte ergeben. Wie in den Kommentaren gezeigt wurde, können zwei "Duplikatbilder" am geringsten unterschiedlich sein (denke zum Beispiel an die Effekte, die durch die JPEG-Komprimierung verursacht werden), so dass Interesse daran besteht, nahezu duplizierte Bilder zu erkennen. Wie bereits in den Kommentaren gezeigt wurde, ist die Berücksichtigung nur von Bildern gleicher Breite ein erster Schritt, um Ihre quadratische Anzahl von Vergleichen zu reduzieren. Wenn alle Bilder die gleiche Breite haben, gibt es keine Verbesserung.
Das erste Problem, das Sie lösen müssen, ist das Verwerfen der untersten Box von nahezu identischen Bildern mit unterschiedlichen Höhen. Warum ist diese Box da? Ist es eine einheitliche Hintergrundfarbe? Preprocess Ihre Bilder, um solche unteren Kästen zu entfernen, wenn es problematisch ist, dies zu erklären, warum. Ich denke, dass diese Boxen von nun an entfernt wurden.
Die SSIM (Structural SIMilarity) ist zwar ein guter Ansatz, um Ihre Fast-Duplikate zu erkennen, aber sie ist nicht schneller als ein einfacherer Algorithmus wie der unter Vergleichen von Bild in URL zu Bild im Dateisystem in Python . Eine Möglichkeit, den Prozess zu beschleunigen (obwohl er in der Natur quadratisch bleibt), besteht darin, zuerst ein gegebenes Bild in Graustufen zu konvertieren und nur ein kleines zentrales Fenster von ihm zu betrachten, wie 50x50. Wenden Sie einen Gaußschen Filter auf dieses zentrale Fenster an, so dass kleinere Strukturen (z. B. Rauschen) größtenteils unterdrückt werden. Da Sie ziemlich viele Bilder zum Vergleich haben, würde ich in diesem geglätteten zentralen Fenster eine grobe Binarisierung anwenden in der Form: Wenn ein Wert v größer ist als die Hälfte des maximal möglichen Wertes, dann wandle es andernfalls weiß mach es schwarz. Jetzt haben Sie 2500 Bits für jedes Bild. Der nächste Schritt könnte folgender sein: Berechnen Sie die Hamming-Distanz von diesen 2500 Bits zu einem gemeinsamen Bitmuster, 2500 Bits 1 würden hier funktionieren. Wiederholen Sie diesen Vorgang für alle Ihre Bilder. Für jedes Bild haben Sie eine Hamming-Distanz.
Lasst uns nun die fast identischen Bilder finden. Berücksichtigen Sie zuerst das Binning der gefundenen Hamming-Abstände in k distinct slots. Daher werden alle Bilder, die in den gleichen Behälter fallen, zum Vergleich weiter betrachtet. Wenn ein Bild a im Bin k_i landet und image b im Bin k_j , i != j landet, wird% ce_de% als a zurückgewiesen. Wenn sich zu viele Bilder in derselben Bin befinden, muss der oben beschriebene Prozess verfeinert werden und / oder das Intervall für jeden Bin muss reduziert werden. Um den Prozess weiter zu beschleunigen, sollten Sie zuerst die NRMSE zwischen allen Bildern in demselben Bin anwenden, und nur diejenigen, die einen hohen Wert ergeben, werden schließlich von SSIM verglichen.
MarvinLabs haben bereits auf die Idee hingewiesen, die ersten N Zeilen zu hashen.
Wenn Sie einen guten Hash (wie MD5) über die ersten N (etwa 20) Zeilen verwenden, können Sie ziemlich sicher sein, dass Hash-Kollisionen identische Bilder identifizieren. Setzen Sie den Hash zusammen mit dem anderen eindeutigen Bildbezeichner (Dateiname?) in eine std :: multimap. Diese Multimap kostet Sie abhängig von der Pfadlänge ca. 10MB bis 100MB und kann leicht im Speicher gehalten werden. Sie können Ihre Berichte nach dem Hashing erstellen. Wenn Sie paranoid sind, machen Sie einen weiteren Bildvergleich für die Kollisionen. Wenn nicht alle Bilder von derselben CCTV-Kamera stammen, ist die Wahrscheinlichkeit eines falschen Positivs kleiner als ein Lesefehler von der Festplatte.