Bei zwei verschiedenen Bilddateien (in welchem Format auch immer) muss ich ein Programm schreiben, um die Wahrscheinlichkeit vorherzusagen, ob eine die illegale Kopie einer anderen ist. Der Autor der Kopie kann Dinge wie Drehen, Negativ machen oder triviale Details hinzufügen (sowie die Größe des Bildes ändern).
Kennen Sie einen Algorithmus für diese Art von Arbeit?
algorithm
image
image-processing
image-recognition
Salvador Dali
quelle
quelle
Antworten:
Dies sind einfach Ideen, über die ich nachgedacht habe, die ich nie ausprobiert habe, aber ich denke gerne über solche Probleme nach!
Bevor Sie beginnen
Erwägen Sie, die Bilder zu normalisieren. Wenn eines eine höhere Auflösung als das andere hat, ziehen Sie die Option in Betracht, dass eines davon eine komprimierte Version des anderen ist. Daher kann eine Verkleinerung der Auflösung zu genaueren Ergebnissen führen.
Überlegen Sie, ob Sie verschiedene potenzielle Bereiche des Bildes scannen möchten, die gezoomte Teile des Bildes sowie verschiedene Positionen und Rotationen darstellen können. Es wird schwierig, wenn eines der Bilder eine verzerrte Version eines anderen ist. Dies sind die Einschränkungen, die Sie identifizieren und bei denen Sie Kompromisse eingehen sollten.
Matlab ist ein hervorragendes Werkzeug zum Testen und Auswerten von Bildern.
Testen der Algorithmen
Sie sollten (mindestens) einen großen, von Menschen analysierten Satz von Testdaten testen, bei denen Übereinstimmungen im Voraus bekannt sind. Wenn Sie beispielsweise in Ihren Testdaten 1.000 Bilder haben, von denen 5% übereinstimmen, haben Sie jetzt einen einigermaßen zuverlässigen Benchmark. Ein Algorithmus, der 10% Positive findet, ist nicht so gut wie einer, der 4% Positive in unseren Testdaten findet. Ein Algorithmus kann jedoch alle Übereinstimmungen finden, weist jedoch auch eine hohe Falsch-Positiv-Rate von 20% auf. Daher gibt es verschiedene Möglichkeiten, Ihre Algorithmen zu bewerten.
Die Testdaten sollten so gestaltet sein, dass sie so viele Arten von Dynamik wie möglich abdecken, die Sie in der realen Welt erwarten würden.
Es ist wichtig zu beachten, dass jeder Algorithmus, um nützlich zu sein, eine bessere Leistung als zufälliges Raten erbringen muss, sonst ist er für uns nutzlos!
Anschließend können Sie Ihre Software kontrolliert auf die reale Welt anwenden und mit der Analyse der daraus resultierenden Ergebnisse beginnen. Dies ist die Art von Softwareprojekt, die unendlich lange dauern kann. Es gibt immer Verbesserungen und Verbesserungen, die Sie vornehmen können. Es ist wichtig, dies beim Entwerfen zu berücksichtigen, da es leicht ist, in die Falle des nie endenden Projekts zu geraten.
Farbeimer
Scannen Sie mit zwei Bildern jedes Pixel und zählen Sie die Farben. Zum Beispiel könnten Sie die "Eimer" haben:
(Offensichtlich hätten Sie eine höhere Auflösung der Zähler). Jedes Mal, wenn Sie ein "rotes" Pixel finden, erhöhen Sie den roten Zähler. Jeder Eimer kann für das Farbspektrum repräsentativ sein. Je höher die Auflösung, desto genauer. Sie sollten jedoch mit einer akzeptablen Differenzrate experimentieren.
Wenn Sie Ihre Summen haben, vergleichen Sie sie mit den Summen für ein zweites Bild. Möglicherweise hat jedes Bild einen ziemlich einzigartigen Fußabdruck, der ausreicht, um Übereinstimmungen zu identifizieren.
Kantenerkennung
Wie wäre es mit Kantenerkennung . (Quelle: wikimedia.org )
Mit zwei ähnlichen Bildern sollte die Kantenerkennung Ihnen einen brauchbaren und ziemlich zuverlässigen, einzigartigen Platzbedarf bieten.
Nehmen Sie beide Bilder auf und wenden Sie die Kantenerkennung an. Messen Sie möglicherweise die durchschnittliche Dicke der Kanten und berechnen Sie dann die Wahrscheinlichkeit, mit der das Bild skaliert werden kann, und skalieren Sie sie gegebenenfalls neu. Unten finden Sie ein Beispiel für einen angewendeten Gabor-Filter (eine Art Kantenerkennung) in verschiedenen Umdrehungen.
Vergleichen Sie die Bilder Pixel für Pixel, zählen Sie die Übereinstimmungen und die Nichtübereinstimmungen. Wenn sie innerhalb einer bestimmten Fehlerschwelle liegen, haben Sie eine Übereinstimmung. Andernfalls können Sie versuchen, die Auflösung bis zu einem bestimmten Punkt zu reduzieren und festzustellen, ob sich die Wahrscheinlichkeit einer Übereinstimmung verbessert.
Regionen von Interesse
Einige Bilder können unterschiedliche Segmente / Regionen von Interesse aufweisen. Diese Regionen stehen wahrscheinlich in starkem Kontrast zum Rest des Bildes und sind ein gutes Element, nach dem Sie in Ihren anderen Bildern suchen müssen, um Übereinstimmungen zu finden. Nehmen Sie dieses Bild zum Beispiel:
(Quelle: meetthegimp.org )
Der Bauarbeiter in Blau ist eine Region von Interesse und kann als Suchobjekt verwendet werden. Es gibt wahrscheinlich mehrere Möglichkeiten, wie Sie Eigenschaften / Daten aus dieser Region von Interesse extrahieren und sie zum Durchsuchen Ihres Datensatzes verwenden können.
Wenn Sie mehr als 2 interessierende Regionen haben, können Sie die Abstände zwischen ihnen messen. Nehmen Sie dieses vereinfachte Beispiel:
(Quelle: per2000.eu )
Wir haben 3 klare Regionen von Interesse. Der Abstand zwischen Bereich 1 und 2 kann 200 Pixel, zwischen 1 und 3 400 Pixel und 2 und 3 200 Pixel betragen.
Durchsuchen Sie andere Bilder nach ähnlichen Regionen von Interesse, normalisieren Sie die Entfernungswerte und prüfen Sie, ob Sie potenzielle Übereinstimmungen haben. Diese Technik könnte für gedrehte und skalierte Bilder gut funktionieren. Je mehr Regionen von Interesse Sie haben, desto höher ist die Wahrscheinlichkeit einer Übereinstimmung, wenn jede Entfernungsmessung übereinstimmt.
Es ist wichtig, über den Kontext Ihres Datensatzes nachzudenken. Wenn zum Beispiel Ihres Datensatz moderne Kunst ist, würden dann Regionen von Interesse arbeiten recht gut, wie Regionen von Interesse wahrscheinlich wurden entworfen , ein wesentlicher Bestandteil des endgültigen Bildes zu sein. Wenn es sich jedoch um Bilder von Baustellen handelt, können interessierende Regionen vom illegalen Kopierer als hässlich interpretiert und großzügig ausgeschnitten / bearbeitet werden. Beachten Sie die allgemeinen Merkmale Ihres Datasets und versuchen Sie, dieses Wissen zu nutzen.
Morphing
Beim Morphing von zwei Bildern wird ein Bild in mehreren Schritten in das andere umgewandelt:
Beachten Sie, dass dies anders ist als das Einblenden eines Bildes in ein anderes!
Es gibt viele Softwarepakete, die Bilder verwandeln können. Es wird traditionell als Übergangseffekt verwendet. Zwei Bilder verwandeln sich normalerweise nicht in die Hälfte, ein Extrem verwandelt sich als Endergebnis in das andere Extrem.
Warum könnte das nützlich sein? Abhängig vom verwendeten Morphing-Algorithmus besteht möglicherweise eine Beziehung zwischen der Ähnlichkeit von Bildern und einigen Parametern des Morphing-Algorithmus.
In einem stark vereinfachten Beispiel kann ein Algorithmus schneller ausgeführt werden, wenn weniger Änderungen vorgenommen werden müssen. Wir wissen dann, dass es eine höhere Wahrscheinlichkeit gibt, dass diese beiden Bilder Eigenschaften miteinander teilen.
Diese Technik eignet sich gut für gedrehte, verzerrte, verzerrte, gezoomte Bilder aller Arten von kopierten Bildern. Auch dies ist nur eine Idee, die ich hatte. Soweit mir bekannt ist, basiert sie nicht auf einer recherchierten Wissenschaft (ich habe jedoch nicht genau hingeschaut), daher kann es eine Menge Arbeit für Sie sein, mit begrenzten / keinen Ergebnissen.
Reißverschluss
Ous Antwort auf diese Frage ist ausgezeichnet. Ich erinnere mich, dass ich über diese Art von Techniken gelesen habe, mit denen ich KI studiert habe. Es ist sehr effektiv beim Vergleich von Korpuslexika.
Eine interessante Optimierung beim Vergleich von Korpussen besteht darin, dass Sie Wörter entfernen können, die als zu häufig angesehen werden, z. B. 'The', 'A', 'And' usw. Diese Wörter verwässern unser Ergebnis. Wir möchten herausfinden, wie unterschiedlich die beiden Korpusse sind so können diese vor der Verarbeitung entfernt werden. Vielleicht gibt es ähnliche häufige Signale in Bildern, die vor der Komprimierung entfernt werden könnten? Es könnte sich lohnen, einen Blick darauf zu werfen.
Das Komprimierungsverhältnis ist eine sehr schnelle und relativ effektive Methode, um festzustellen, wie ähnlich zwei Datensätze sind. Wenn Sie sich über die Funktionsweise der Komprimierung informieren, erhalten Sie eine gute Vorstellung davon, warum dies so effektiv sein kann. Für einen schnell freizugebenden Algorithmus wäre dies wahrscheinlich ein guter Ausgangspunkt.
Transparenz
Auch hier bin ich mir nicht sicher, wie Transparenzdaten für bestimmte Bildtypen, GIF-Png usw. gespeichert werden, aber dies ist extrahierbar und würde als effektiver vereinfachter Ausschnitt dienen, um die Transparenz Ihrer Datensätze zu vergleichen.
Signale invertieren
Ein Bild ist nur ein Signal. Wenn Sie ein Geräusch von einem Lautsprecher abspielen und das entgegengesetzte Geräusch in einem anderen Lautsprecher perfekt synchron mit genau derselben Lautstärke wiedergeben, heben sie sich gegenseitig auf.
(Quelle: themotorreport.com.au )
Invertieren Sie eines der Bilder und fügen Sie es Ihrem anderen Bild hinzu. Skalieren Sie die Positionen wiederholt, bis Sie ein resultierendes Bild finden, in dem genügend Pixel weiß (oder schwarz? Ich werde es als neutrale Leinwand bezeichnen), um eine positive oder teilweise Übereinstimmung zu erzielen.
Betrachten Sie jedoch zwei Bilder, die gleich sind, außer dass eines von ihnen einen Aufhellungseffekt hat:
(Quelle: mcburrz.com )
Wenn Sie einen von ihnen invertieren und dann zum anderen hinzufügen, entsteht keine neutrale Leinwand, die wir anstreben. Wenn wir jedoch die Pixel beider Originalbilder vergleichen, können wir definitiv eine klare Beziehung zwischen den beiden erkennen.
Ich habe seit einigen Jahren keine Farbe mehr studiert und bin mir nicht sicher, ob das Farbspektrum linear ist. Wenn Sie jedoch den durchschnittlichen Faktor der Farbdifferenz zwischen beiden Bildern ermittelt haben, können Sie diesen Wert verwenden, um die Daten vor der Verarbeitung mit zu normalisieren diese Technik.
Baumdatenstrukturen
Zunächst scheinen diese nicht für das Problem zu passen, aber ich denke, sie könnten funktionieren.
Sie könnten darüber nachdenken, bestimmte Eigenschaften eines Bildes (z. B. Farbfächer) zu extrahieren und einen Huffman-Baum oder eine ähnliche Datenstruktur zu generieren . Möglicherweise können Sie zwei Bäume auf Ähnlichkeit vergleichen. Dies würde für fotografische Daten, beispielsweise mit einem großen Farbspektrum, nicht gut funktionieren, aber Cartoons oder andere Bilder mit reduzierten Farbsätzen könnten funktionieren.
Das würde wahrscheinlich nicht funktionieren, aber es ist eine Idee. Die Trie-Datenstruktur eignet sich hervorragend zum Speichern von Lexika, z. B. einer Wörterbucharty. Es ist ein Präfixbaum. Vielleicht ist es möglich, ein Bildäquivalent eines Lexikons zu erstellen (wieder kann ich nur an Farben denken), um einen Versuch zu konstruieren. Wenn Sie beispielsweise ein 300 x 300-Bild in 5 x 5 Quadrate verkleinert haben, zerlegen Sie jedes 5 x 5-Quadrat in eine Folge von Farben, aus denen Sie aus den resultierenden Daten einen Versuch erstellen können. Wenn ein 2x2-Quadrat enthält:
Wir haben einen ziemlich einzigartigen Trie-Code, der 24 Ebenen erweitert. Durch Erhöhen / Verringern der Ebenen (dh Verringern / Erhöhen der Größe unseres Unterquadrats) können genauere Ergebnisse erzielt werden.
Der Vergleich von Trie-Bäumen sollte relativ einfach sein und könnte möglicherweise zu effektiven Ergebnissen führen.
Weitere Ideen
Ich stolperte über ein interessantes Papier-Breif über die Klassifizierung von Satellitenbildern , das Folgendes beschreibt:
Es kann sinnvoll sein, diese Messungen genauer zu untersuchen, obwohl einige davon möglicherweise nicht für Ihren Datensatz relevant sind.
Andere Dinge zu beachten
Es gibt wahrscheinlich viele Artikel über diese Art von Dingen, daher sollte es hilfreich sein, einige davon zu lesen, obwohl sie sehr technisch sein können. Es ist ein äußerst schwieriger Bereich im Computerbereich, in dem viele Menschen erfolglos arbeiten und versuchen, ähnliche Dinge zu tun. Es wäre der beste Weg, es einfach zu halten und auf diesen Ideen aufzubauen. Es sollte eine ziemlich schwierige Herausforderung sein, einen Algorithmus mit einer besser als zufälligen Übereinstimmungsrate zu erstellen, und eine Verbesserung dieser zu erreichen, wird wirklich ziemlich schwer zu erreichen.
Jede Methode müsste wahrscheinlich gründlich getestet und optimiert werden. Wenn Sie Informationen über den Bildtyp haben, den Sie ebenfalls überprüfen möchten, ist dies hilfreich. Zum Beispiel würden viele von ihnen Text enthalten, sodass die Texterkennung eine einfache und wahrscheinlich sehr zuverlässige Möglichkeit wäre, Übereinstimmungen zu finden, insbesondere in Kombination mit anderen Lösungen. Versuchen Sie, wie bereits erwähnt, die allgemeinen Eigenschaften Ihres Datensatzes auszunutzen.
Die Kombination alternativer Messungen und Techniken, die jeweils eine gewichtete Abstimmung haben können (abhängig von ihrer Wirksamkeit), wäre eine Möglichkeit, ein System zu erstellen, das genauere Ergebnisse generiert.
Wenn mehrere Algorithmen verwendet werden, wie zu Beginn dieser Antwort erwähnt, kann man alle positiven Ergebnisse finden, aber eine falsch positive Rate von 20% haben. Es wäre von Interesse, die Eigenschaften / Stärken / Schwächen anderer Algorithmen wie bei einem anderen Algorithmus zu untersuchen wirksam sein, um falsch positive Ergebnisse zu eliminieren, die von einem anderen zurückgegeben wurden.
Achten Sie darauf, dass Sie nicht versuchen, das nie endende Projekt abzuschließen. Viel Glück!
quelle
Lesen Sie die Zeitung: Porikli, Fatih, Oncel Tuzel und Peter Meer. "Kovarianzverfolgung unter Verwendung einer Modellaktualisierung basierend auf Mitteln auf Riemannschen Mannigfaltigkeiten". (2006) IEEE Computer Vision und Mustererkennung.
Mit der in diesem Artikel vorgestellten Technik konnte ich erfolgreich überlappende Bereiche in Bildern erkennen, die von benachbarten Webcams aufgenommen wurden. Meine Kovarianzmatrix bestand aus Sobel-, Canny- und SUSAN-Aspekt- / Kantenerkennungsausgaben sowie den ursprünglichen Graustufenpixeln.
quelle
Eine Idee:
Schritt 2 ist nicht trivial. Insbesondere müssen Sie möglicherweise einen intelligenten Algorithmus verwenden, um den ähnlichsten Schlüsselpunkt auf dem anderen Bild zu finden. Punktdeskriptoren sind normalerweise sehr hochdimensional (wie hundert Parameter), und es gibt viele Punkte, durch die man schauen muss. kd-Bäume können hier nützlich sein, Hash-Lookups funktionieren nicht gut.
Varianten:
quelle
Es ist in der Tat viel weniger einfach als es scheint :-) Nicks Vorschlag ist gut.
Denken Sie zunächst daran, dass jede sinnvolle Vergleichsmethode im Wesentlichen funktioniert, indem Sie die Bilder in eine andere Form konvertieren - eine Form, die es einfacher macht, ähnliche Funktionen auszuwählen. Normalerweise ist dieses Zeug nicht sehr leicht zu lesen ...
Eines der einfachsten Beispiele, die ich mir vorstellen kann, ist die einfache Verwendung des Farbraums jedes Bildes. Wenn zwei Bilder sehr ähnliche Farbverteilungen aufweisen, können Sie ziemlich sicher sein, dass sie dasselbe zeigen. Zumindest können Sie genug Sicherheit haben, um es zu kennzeichnen oder mehr Tests durchzuführen. Das Vergleichen von Bildern im Farbraum widersteht auch Dingen wie Drehung, Skalierung und etwas Zuschneiden. Es wird natürlich einer starken Modifikation des Bildes oder einer starken Neufärbung nicht widerstehen (und selbst eine einfache Farbtonverschiebung wird etwas schwierig sein).
http://en.wikipedia.org/wiki/RGB_color_space
http://upvector.com/index.php?section=tutorials&subsection=tutorials/colorspace
Ein anderes Beispiel betrifft die sogenannte Hough-Transformation. Diese Transformation zerlegt ein Bild im Wesentlichen in eine Reihe von Linien. Sie können dann einige der "stärksten" Linien in jedem Bild nehmen und sehen, ob sie ausgerichtet sind. Sie können zusätzliche Arbeit leisten, um Rotation und Skalierung zu kompensieren. In diesem Fall ist das Vergleichen einiger Zeilen VIEL weniger Rechenaufwand als das Gleiche mit ganzen Bildern. Es wird nicht so schlimm sein.
http://homepages.inf.ed.ac.uk/amos/hough.html
http://rkb.home.cern.ch/rkb/AN16pp/node122.html
http://en.wikipedia.org/wiki/ Hough_transform
quelle
In der von Ihnen beschriebenen Form ist das Problem schwierig. Betrachten Sie das Kopieren und Einfügen eines Teils des Bildes in ein anderes größeres Bild als Kopie? etc.
Wenn Sie einen Schritt zurücktreten, ist dies einfacher zu lösen, wenn Sie die Master-Bilder mit einem Wasserzeichen versehen. Sie müssen ein Wasserzeichenschema verwenden, um einen Code in das Bild einzubetten. Um einen Schritt zurückzutreten, ist eine Wasserzeichenmethode im Gegensatz zu einigen von einigen Leuten vorgeschlagenen Low-Level-Ansätzen (Kantenerkennung usw.) überlegen, weil:
Es ist resistent gegen Signalverarbeitungsangriffe. ► Signalverbesserung - Schärfen, Kontrast usw. ► Filtern - Median, Tiefpass, Hochpass usw. ► Additives Rauschen - Gauß, Uniform usw. ► Verlustbehaftete Komprimierung - JPEG, MPEG usw.
Es ist resistent gegen geometrische Angriffe. ► Affine Transformationen. ► Datenreduktion - Zuschneiden, Abschneiden usw. ► Zufällige lokale Verzerrungen. ► Verziehen
Wenn Sie nach Wasserzeichenalgorithmen suchen, sind Sie auf dem richtigen Weg, um Ihr Problem zu lösen. (Hinweis: Sie können Ihre Methode mit dem STIRMARK- Dataset vergleichen. Dies ist ein akzeptierter Standard für diese Art von Anwendung.
quelle
Dies ist nur ein Vorschlag, es könnte nicht funktionieren und ich bin bereit, darauf angesprochen zu werden.
Dies erzeugt falsch positive, aber hoffentlich keine falsch negativen Ergebnisse.
Ändern Sie die Größe beider Bilder so, dass sie dieselbe Größe haben (ich gehe davon aus, dass die Verhältnisse von Breite zu Länge in beiden Bildern gleich sind).
Komprimieren Sie eine Bitmap beider Bilder mit einem verlustfreien Komprimierungsalgorithmus (z. B. gzip).
Suchen Sie nach Dateipaaren mit ähnlichen Dateigrößen. Zum Beispiel könnten Sie einfach jedes Dateipaar, das Sie haben, nach der Größe der Dateigrößen sortieren und das oberste X abrufen.
Wie gesagt, dies wird definitiv zu falsch positiven, aber hoffentlich nicht zu falsch negativen Ergebnissen führen. Sie können dies in fünf Minuten umsetzen, während Porikil et. al. würde wahrscheinlich umfangreiche Arbeit erfordern.
quelle
Ich glaube, wenn Sie bereit sind, den Ansatz auf jede mögliche Ausrichtung und auf negative Versionen anzuwenden, ist ein guter Anfang für die Bilderkennung (mit guter Zuverlässigkeit) die Verwendung von Eigengesichtern: http://en.wikipedia.org/wiki/Eigenface
Eine andere Idee wäre, beide Bilder in Vektoren ihrer Komponenten umzuwandeln. Eine gute Möglichkeit, dies zu tun, besteht darin, einen Vektor zu erstellen, der in x * y-Dimensionen arbeitet (x ist die Breite Ihres Bildes und y ist die Höhe), wobei der Wert für jede Dimension auf den (x, y) -Pixelwert angewendet wird. Führen Sie dann eine Variante von K-Nearest Neighbors mit zwei Kategorien aus: Match und No Match. Wenn es dem Originalbild ausreichend nahe kommt, passt es in die Übereinstimmungskategorie, wenn nicht, wird es nicht.
K Nearest Neighbors (KNN) finden Sie hier. Weitere gute Erklärungen finden Sie auch im Internet: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm
Der Vorteil von KNN besteht darin, dass der Algorithmus umso genauer wird, je mehr Varianten Sie mit dem Originalbild vergleichen. Der Nachteil ist, dass Sie einen Katalog mit Bildern benötigen, um das System zuerst zu trainieren.
quelle
Wenn Sie bereit sind, einen anderen Ansatz zur Erkennung illegaler Kopien Ihrer Bilder in Betracht zu ziehen, können Sie Wasserzeichen in Betracht ziehen . (ab 1.4)
Obwohl es sich auch um ein komplexes Feld handelt, gibt es Techniken, mit denen die Wasserzeicheninformationen durch grobe Bildänderungen erhalten bleiben können: (ab 1.9)
Natürlich heißt es in der FAQ, diesen Ansatz zu implementieren: "... sehr herausfordernd", aber wenn Sie damit erfolgreich sind, erhalten Sie ein hohes Vertrauen, ob das Bild eine Kopie ist oder nicht, und nicht eine prozentuale Wahrscheinlichkeit.
quelle
Wenn Sie Linux verwenden, würde ich zwei Tools vorschlagen:
align_image_stack von package hugin-tools - ist ein Befehlszeilenprogramm, das Rotation, Skalierung und andere Verzerrungen automatisch korrigieren kann (es ist hauptsächlich zum Zusammenstellen von HDR-Fotografie gedacht, funktioniert aber auch für Videobilder und andere Dokumente). Weitere Informationen: http://hugin.sourceforge.net/docs/manual/Align_image_stack.html
Vergleichen Sie mit dem Paket imagemagick - einem Programm, das die Anzahl verschiedener Pixel in zwei Bildern finden und zählen kann. Hier ist ein ordentliches Tutorial: http://www.imagemagick.org/Usage/compare/ Mit dem -fuzz N% können Sie die Fehlertoleranz erhöhen. Je höher das N, desto höher ist die Fehlertoleranz, um immer noch zwei Pixel als gleich zu zählen.
align_image_stack sollte jeden Versatz korrigieren, damit der Vergleichsbefehl tatsächlich die Chance hat, dieselben Pixel zu erkennen.
quelle