Wie kann ich die Ähnlichkeit zwischen zwei Bildern messen? [geschlossen]

Ich möchte einen Screenshot einer Anwendung (möglicherweise eine Webseite) mit einem zuvor aufgenommenen Screenshot vergleichen, um festzustellen, ob die Anwendung sich selbst korrekt anzeigt. Ich möchte keinen genauen Übereinstimmungsvergleich, da der Aspekt leicht unterschiedlich sein kann (im Fall einer Web-App kann sich je nach Browser ein Element an einem etwas anderen Ort befinden). Es sollte ein Maß dafür geben, wie ähnlich die Screenshots sind.

Gibt es eine Bibliothek / ein Tool, das / das das schon macht? Wie würden Sie es implementieren?

Dies hängt ganz davon ab, wie intelligent der Algorithmus sein soll.

Hier sind zum Beispiel einige Probleme:

• zugeschnittene Bilder im Vergleich zu einem nicht zugeschnittenen Bild
• Bilder mit einem hinzugefügten Text gegen einen anderen ohne
• gespiegelte Bilder

Der einfachste und einfachste Algorithmus, den ich dafür gesehen habe, besteht darin, die folgenden Schritte für jedes Bild auszuführen:

1. Skalieren Sie auf etwas Kleines, wie 64x64 oder 32x32, ignorieren Sie das Seitenverhältnis, verwenden Sie einen kombinierten Skalierungsalgorithmus anstelle des nächsten Pixels
2. Skalieren Sie die Farbbereiche so, dass der dunkelste schwarz und der hellste weiß ist
3. Drehen und drehen Sie das Bild so, dass die hellste Farbe oben links und dann oben rechts als nächstes dunkler und unten links als nächstes dunkler ist (so weit wie möglich natürlich).

Bearbeiten Ein kombinierter Skalierungsalgorithmus ist ein Algorithmus , der beim Skalieren von 10 Pixeln auf eins eine Funktion verwendet, die die Farbe all dieser 10 Pixel übernimmt und sie zu einem kombiniert. Kann mit Algorithmen wie Mittelwertbildung, Mittelwert oder komplexeren Algorithmen wie bikubischen Splines durchgeführt werden.

Berechnen Sie dann den mittleren Abstand Pixel für Pixel zwischen den beiden Bildern.

Um eine mögliche Übereinstimmung in einer Datenbank nachzuschlagen, speichern Sie die Pixelfarben als einzelne Spalten in der Datenbank, indizieren Sie eine Reihe von Spalten (aber nicht alle, es sei denn, Sie verwenden ein sehr kleines Bild) und führen Sie eine Abfrage durch, die jeweils einen Bereich verwendet Pixelwert, dh. Jedes Bild, bei dem das Pixel im kleinen Bild zwischen -5 und +5 des Bildes liegt, das Sie nachschlagen möchten.

Dies ist einfach zu implementieren und relativ schnell auszuführen, wird aber natürlich die meisten fortgeschrittenen Unterschiede nicht bewältigen. Dafür benötigen Sie viel fortgeschrittenere Algorithmen.

Die "klassische" Methode, dies zu messen, besteht darin, das Bild in eine kanonische Anzahl von Abschnitten (z. B. ein 10x10-Raster) aufzuteilen und dann ein Histogramm der RGB-Werte in jeder Zelle zu berechnen und die entsprechenden Histogramme zu vergleichen. Diese Art von Algorithmus wird sowohl wegen seiner Einfachheit als auch wegen seiner Invarianz gegenüber Skalierung und (kleiner!) Übersetzung bevorzugt.

Verwenden Sie ein normalisiertes Farbhistogramm. (Lesen Sie den Abschnitt über Anwendungen hier ), sie werden häufig in Bildabruf- / Abgleichsystemen verwendet und sind eine Standardmethode zum Abgleichen von Bildern, die sehr zuverlässig, relativ schnell und sehr einfach zu implementieren ist.

Im Wesentlichen erfasst ein Farbhistogramm die Farbverteilung des Bildes. Dies kann dann mit einem anderen Bild verglichen werden, um festzustellen, ob die Farbverteilungen übereinstimmen.

Diese Art der Anpassung ist ziemlich widerstandsfähig gegen Skalierung (sobald das Histogramm normalisiert ist) und Rotation / Verschiebung / Bewegung usw.

Vermeiden Sie pixelweise Vergleiche, da das Bild, wenn es leicht gedreht / verschoben wird, zu einem großen Unterschied führen kann.

Es wäre einfach, Histogramme selbst zu erstellen (vorausgesetzt, Sie können auf Pixelwerte zugreifen), aber wenn Sie keine Lust dazu haben, ist die OpenCV- Bibliothek eine großartige Ressource für solche Aufgaben. Hier ist eine PowerPoint-Präsentation, die Ihnen zeigt, wie Sie mit OpenCV ein Histogramm erstellen.

Berechnen Videokodierungsalgorithmen wie MPEG nicht den Unterschied zwischen den einzelnen Bildern eines Videos, damit sie nur das Delta codieren können? Sie könnten untersuchen, wie Videokodierungsalgorithmen diese Bildunterschiede berechnen.

Schauen Sie sich diese Open-Source-Bildsuchanwendung http://www.semanticmetadata.net/lire/ an . Es werden verschiedene Bildähnlichkeitsalgorithmen beschrieben, von denen drei aus dem MPEG-7-Standard stammen: ScalableColor, ColorLayout, EdgeHistogram und Auto Color Correlogram.

Sie könnten einen rein mathematischen Ansatz von verwenden O(n^2), aber er ist nur dann nützlich, wenn Sie sicher sind, dass es keinen Offset oder ähnliches gibt. (Wenn Sie jedoch einige Objekte mit homogener Farbgebung haben, funktioniert dies immer noch recht gut.)

Die Idee ist jedenfalls, das normalisierte Punktprodukt der beiden Matrizen zu berechnen. C = sum(Pij*Qij)^2/(sum(Pij^2)*sum(Qij^2)).

Diese Formel ist eigentlich der "Kosinus" des Winkels zwischen den Matrizen (seltsam). Je größer die Ähnlichkeit ist (sagen wir mal Pij=Qij), C ist 1, und wenn sie völlig unterschiedlich sind, sagen wir für jede i,j Qij = 1(Vermeidung der Nullteilung) Pij = 255, dann sind wir für die Größe umso näher an Null nxn, je größer nsie ist bekommen. (Durch grobe Berechnung :) C=1/n^2.

Dafür benötigen Sie eine Mustererkennung . Um kleine Unterschiede zwischen zwei Bildern festzustellen, funktionieren Hopfield-Netze recht gut und sind recht einfach zu implementieren. Ich kenne jedoch keine verfügbaren Implementierungen.

Eine Rubinlösung finden Sie hier

Aus der Readme:

Phashion ist ein Ruby-Wrapper um die pHash-Bibliothek "Perceptual Hash", der doppelte und nahezu doppelte Multimediadateien erkennt

Wie Sie die Ähnlichkeit zwischen zwei Bildern messen, hängt ganz davon ab, was Sie messen möchten, zum Beispiel: Kontrast, Helligkeit, Modalität, Rauschen ... und dann das für Sie am besten geeignete Ähnlichkeitsmaß auswählen. Sie können zwischen MAD (mittlere absolute Differenz) und MSD (mittlere quadratische Differenz) wählen , die sich gut zur Messung der Helligkeit eignen. Es gibt auch CR (Korrelationskoeffizient), der die Korrelation zwischen zwei Bildern gut darstellt. Sie können auch zwischen histogrammbasierten Ähnlichkeitsmaßen wie SDH (Standardabweichung des Differenzbildhistogramms) oder multimodalen Ähnlichkeitsmaßen wie MI (gegenseitige Information) oder NMI (normalisierte gegenseitige Information) wählen .

Da diese Ähnlichkeitsmaße viel Zeit kosten, wird empfohlen, Bilder zu verkleinern, bevor diese Maße auf sie angewendet werden.

Ich frage mich (und ich werfe wirklich nur die Idee raus, abgeschossen zu werden), ob etwas abgeleitet werden könnte, indem man ein Bild vom anderen subtrahiert und dann das resultierende Bild als JPEG von GIF komprimiert und die Dateigröße als nimmt ein Maß für Ähnlichkeit.

Wenn Sie zwei identische Bilder hätten, würden Sie eine weiße Box erhalten, die sich sehr gut komprimieren lässt. Je mehr sich die Bilder unterschieden, desto komplexer wäre die Darstellung und desto weniger komprimierbar.

Wahrscheinlich kein idealer Test und wahrscheinlich viel langsamer als nötig, aber es könnte als schnelle und schmutzige Implementierung funktionieren.

Sie können sich den Code für das Open-Source-Tool findimagedupes ansehen , obwohl er anscheinend in Perl geschrieben wurde. Daher kann ich nicht sagen, wie einfach das Parsen sein wird ...

Wenn ich die Seite findimagedupes lese, die mir gefallen hat, sehe ich, dass es eine C ++ - Implementierung desselben Algorithmus gibt . Vermutlich wird dies leichter zu verstehen sein.

Und anscheinend können Sie auch gqview verwenden .

Nun, um Ihre Frage nicht direkt zu beantworten, aber ich habe gesehen, dass dies passiert ist. Microsoft hat kürzlich ein Tool namens PhotoSynth auf den Markt gebracht, mit dem sich überlappende Bereiche in einer großen Anzahl von Bildern (die unterschiedliche Seitenverhältnisse aufweisen können) sehr ähnlich bestimmen können.

Ich frage mich, ob sie in ihrem Blog Bibliotheken oder Codefragmente zur Verfügung haben.

Um Vaibhavs Anmerkung zu erweitern, ist hugin ein Open-Source-Autostitcher, der einen Einblick in das Problem haben sollte.

Es gibt eine Software zum inhaltsbasierten Abrufen von Bildern, die (teilweise) das tut, was Sie benötigen. Alle Referenzen und Erklärungen sind von der Projektseite verlinkt und es gibt auch ein kurzes Lehrbuch (Kindle): LIRE

Sie können Siamese Network verwenden, um zu sehen, ob die beiden Bilder nach diesem Tutorial ähnlich oder unähnlich sind . In diesem Lernprogramm werden ähnliche Bilder zusammengefasst, während Sie mithilfe der L2Entfernung die Ähnlichkeit zweier Bilder messen können.

Wenn Sie dies gelegentlich tun und keine Automatisierung benötigen, können Sie dies in einem Bildeditor tun, der Ebenen wie Photoshop oder Paint Shop Pro unterstützt (wahrscheinlich auch GIMP oder Paint.Net, aber ich ' Ich bin mir da nicht sicher. Öffnen Sie beide Screenshots und legen Sie einen als Ebene übereinander. Ändern Sie den Ebenenüberblendungsmodus in "Differenz", und alles, was zwischen den beiden gleich ist, wird schwarz. Sie können die oberste Ebene verschieben, um Ausrichtungsunterschiede zu minimieren.

Beyond Compare bietet einen pixelweisen Vergleich für Bilder, z.

Nun, eine wirklich einfache Methode könnte jede Pixelfarbe durchgehen und sie mit der entsprechenden Pixelfarbe auf dem zweiten Bild vergleichen - aber das ist wahrscheinlich eine sehr, sehr langsame Lösung.