zwei Bilder miteinander vergleichen

[beachdiddi]

Hallo,

ich möchte zwei Bilder miteinander vergleichen. Jetzt habe ich gelesen, dass man aus den Bildern Pixel-Arrays macht und diese dann miteinander vergleicht. Ich will diese Bilder nirgends anzeigen lassen oder sonst was mit ihnen machen. Ich will nur prüfen ob sie identisch sind.

Ich habe dazu schon ein paar Beiträge gelesen und auch schon gegoogelt. Leider komme ich immer noch nicht auf eine ordentliche Lösung.
Vielleicht hat jemand die Geduld es mir noch einmal zu erklären wie ich da vorgehen muss.

Ich beschreibe mal meinen bisherigen Weg.

             File f = new File("/pfad/zu/meinem/Bild/xy.jpg");
             BufferedImage img = ImageIO.read(f);
             int[] pix = new int[img.getWidth()*img.getHeight()]; // int[] mit der Größe "breite * höhe", um alle Pixel unterzubringen

Jetzt hab ich gelesen, dass ich irgendwie die Klasse PixelGrabber ins Spiel bringen muss.
Aber da hängts irgendwie...
Vielleicht bin ich ja auch mit obigen Vorgehen schon auf dem Holzweg.
Ich bitte also um Rat.

mfg, beachdiddi

 

[Ariol]

http://www.dpunkt.de/java/Referenz/Das_Paket_java.awt.image/38.html


Das hier suchst du vermutlich:
public synchronized Object getPixels() [1.1]
Liefert die kopierten Pixel in einem int-Array, falls ein RGB-Farbmodell benutzt wurde, ansonsten in einem byte-Array.

 

[Wildcard]

Ich würde erstmal eine Vorauswahl anhand der Dateigröße oder des Hashwerts treffen bevor ich mich auf einen teuren Pixelvergleich einlasse.

 

[beachdiddi]

Das hier suchst du vermutlich:
public synchronized Object getPixels() [1.1]
Liefert die kopierten Pixel in einem int-Array, falls ein RGB-Farbmodell benutzt wurde, ansonsten in einem byte-Array.

Ok, so hab ich es hinbekommen.
Danke Ariol!

public class Grab {
	
       void grab(Image img, int pix[], int width, int height) {
	        PixelGrabber grabber =  new PixelGrabber(img, 0, 0, width, height, pix, 0, width);
	      try {
	        grabber.grabPixels();
	      }
	      catch (InterruptedException e) {
	        e.printStackTrace();
	      }
	    }
	
	public static void main(String[] args) {
		try{
 		File f = new File("/pfad/zu/dem/Bild/xy.jpg");
		BufferedImage img = ImageIO.read(f);
		int w = img.getWidth();
		int h = img.getHeight();
		int[] pix = new int[w*h];
		Grab y = new Grab();
		y.grab(img, pix, w, h);

		}catch (IOException e){
			
		}
}

@Wildcard:
Gibts da irgendwie eine bestimmte Reihenfolge, die Du bevorzugen würdest?
Z.B.:
1. Das Verhältnis von w*h
// dann, falls das Verhältnis gleich ist
2. Die Dateigröße
//falls gleich, dann
3. Hashwertvergleich
// und zuletzt
4. Pixelvergleich

Kann man da eine solche Reihenfolge wählen?
Oder gibts noch andere Möglichkeiten zur Überprüfung?
Macht es Sinn sich aus dem Bild ein Stück rauszuschneiden (also z.B. 16x16 Pixel), bei dem anderen Bild natürlich auch an der gleichen Stelle auch ein 16x16 Stück ausschneiden und diese kleineren Byte-Arrays miteinander zu vergleichen? Und nur falls die beiden Arrays übereinstimmen folgt ein kompletter Pixelvergleich. Spart ja bestimmt einiges an Zeit, oder? Oder ist die Zeitersparnis vernachlässigbar?

 

[Wildcard]

Ich sag mal so, wenn der Hashwert identisch ist (nicht der Java Hash sondern MD5, SHA oder so) ist die Wahrscheinlichkeit das beide Bilder gleich sind schon sehr hoch.

 

[Ariol]

1. ergibt keinen sinn, denn bei 400*300 und auch bei 800*600 das Größenverhältnis gleich ist, aber du die beiden nicht vergleichen kannst.

also zuerst mal auf dateigröße testen, dann auf höhe und auf breite.

ob hashwert sinn macht weiss ich nicht, aber zumindest den vergleich kannst du abbrechen lassen, wenn nur ein pixel falsch ist.

Zur verbesserung der Laufzeit könntest du das überprüfen in mehrere Threads auslagern mit geteiltem String natürlich, dann findest du schneller raus, wenn das ganze ungleich ist.

Was ich nicht weiss, ob vielleicht auch equal das ganze abkürzen kann (glaubs aber nicht)

 

[beachdiddi]

Ok, also dann über den Hashwert.

Bin ich dann bei dem Paket "java.security.MessageDigest" richtig?
Damit werd ich mich mal auseinander setzen.

Danke für Deine Hilfe!!!

 

[Wildcard]

Was ich nicht weiss, ob vielleicht auch equal das ganze abkürzen kann (glaubs aber nicht)

Dann glaubst du richtig.

 

[Ariol]

Ich sag mal so, wenn der Hashwert identisch ist (nicht der Java Hash sondern MD5, SHA oder so) ist die Wahrscheinlichkeit das beide Bilder gleich sind schon sehr hoch.

sehr hoch, aber nicht gleich.

aber mir fällt gerade ein, das die Größe auch nix über die Gleichheit sagen muss (gleiches Bild einmal als gif und einmal als jpeg)

dann stimmt der hashwert natürlich nicht überein.


Insofern fallen diese beiden Überprüfungen zum Abbruch eigentlich flach

 

[Wildcard]

Ein gif und ein jpg können praktisch gar nicht gleich sein, da (fast alle) jpegs verlustbehaftet komprimiert werden.

 

[beachdiddi]

Jetzt waren wir drei fast gleichzeitig fertig

Zur verbesserung der Laufzeit könntest du das überprüfen in mehrere Threads auslagern mit geteiltem String natürlich, dann findest du schneller raus, wenn das ganze ungleich ist.

Du meinst den String in X Teile aufteilen und alle X Teile von jeweils einem Thread überprüfen lassen?

 

[Wildcard]

Da fällt mir ein:
Geht es dir eigentlich um identische Bilder oder identische Dateien?
Denn wenn es dir um echt identische Bilder (von den Pixeln) geht dann kannst du den Hash nicht verwenden.
Bilder enthalten zum Beispiel auch Meta-Daten (Autor,...) die den Hash-Wert selbst wenn das Bild das gleiche ist.

 

[Ariol]

muss j nicht unbedingt jpeg sein, was ist denn mit tiff??

@beachdiddi:

ja, das Array (wieso String) aufteilen und dann von mehren Threads testen lassen, sobald dann einer einer Fehler findet abbrechen.

Das Verbessert die Laufzeit zumindest, wenn der Unterschied zwischen den Bildern irgendwo mitten im Bild ist, weil du sonst da erst recht spät hinkommst.

Wenn beide Bilder gleich sind wirst du allerdings kaum eine Verbesserung merken, weil die Laufzeit dann trotzdem O(n) ist.

 

[beachdiddi]

Ich denke aus oben genannten Gründen, ist eine sinnvolle und durchdachte Reihenfolge an Überprüfungen von Nöten.

Geht es dir eigentlich um identische Bilder oder identische Dateien?

Mir geht es um identische Bilder. Es geht um einen Vergleich von Bildern auf einer Homepage, die ich mit denen in einem Ordner vergleiche. Mein Ziel ist es "geklaute" Bilder auf fremden Hp's zu entdecken.

 

[Ariol]

Mir geht es um identische Bilder. Es geht um einen Vergleich von Bildern auf einer Homepage, die ich mit denen in einem Ordner vergleiche. Mein Ziel ist es "geklaute" Bilder auf fremden Hp's zu entdecken.

Das wird allerdings schwierig mit dem Programm, wenn, wie Wildcard schon angemerkt hat, die geklauten Bilder komprimiert wurden. Dann wirst du immer eine Meldung bekommen, das die Bilder nicht gleich sind!

 

[Wildcard]

Das wird allerdings schwierig mit dem Programm, wenn, wie Wildcard schon angemerkt hat, die geklauten Bilder komprimiert wurden. Dann wirst du immer eine Meldung bekommen, das die Bilder nicht gleich sind!

Dann hilft nur noch eine Self Organizing Map um den Ähnlichkeitsgrad der Bilder zu berechnen.
http://de.wikipedia.org/wiki/Selbstorganisierende_Karte

 

[beachdiddi]

Oh!
Das ist harter Stoff für 23 Uhr 50...
Das muss ich mir morgen mal mit einer Tasse Kaffee anschauen.

Habt ihr selbst Erfahrung mit einer Selbstorganisierenden Karte?

 

[Wildcard]

Habt ihr selbst Erfahrung mit einer Selbstorganisierenden Karte?

Nein, das ist harter Stoff :wink:

 

[beachdiddi]

Gut, dass es nicht nur mir so geht :wink:

Noch ein Versuch das Ganze zusammenzufassen bevor ich offline gehe:
Es gibt zwei Möglichkeiten:
1. Bilder direkt vergleichen
- Dateigröße
- Breite und Höhe
- Hashwert
- Pixelvergleich
was natürlich alles für die Katz is, falls die Bilder komprimiert werden...

2. der harte Stoff :bahnhof: : Selbstorganisierende Karte

Seh ich das so richtig, oder?

 

[Wildcard]

Ja, würde ich soweit zustimmen.

 

[beachdiddi]

Ok, danke für die super schnellen Antworten!!!
Ihr habt mir sehr geholfen. :toll:

Falls ihr noch andere Ideen habt, lasst es mich einfach wissen.

Gute Nacht,
beachdiddi

 

[schalentier]

Was mir noch spontan einfallen wuerde:

Du rechnest beide Bilder auf die gleiche, kleine Groesse (zb 50x50 Pixel) runter. So dass, wenn zb das Ursprungsbild 100x100 gross ist, immer aus 2x2 Bloecken ein Pixel mit dem Durchschnitt der 4 Pixel wird. Dann nimmst du die Differenz der beiden (nun gleich grossen) Bilder, errechnest die Summe der Pixel-Differenzen und ab einem Grenzwert vergleichst du (oder jemand anderes ;-) ) die beiden Originalbilder.

Nur so als Idee...

 

[Gast]

Du könntest auch die Arrays komplett durchlaufen und dir in einem weiteren Array die Differenzen speichern.

Diese Werte dann positiv noch um die Toleranz verringern (auf negative werte achten)

wenn du dann noch mehr als x Differenzen über 0 hast, wird das Bild wohl ein anderes sein.

Dann gibt es aber auch noch die Möglichkeit die Differenzen mitteinander zu vergleichen um herauszufinden, ob das bild nur anders eingefärbt wurde...


Die Selbstorganisierende Karte würde vermutlich die besten ergebnisse zurückgeben.

 

[byte]

Du kannst auch heuristisch an das Problem herangehen, z.b. mit Hilfe von Entscheidungsbäumen (Decision Trees). Das Prinzip ist folgendes: Du definierst Dir verschiedene Metriken zum Vergleich der beiden Bilder, z.b. wie Gast gerade beschrieben hat eine Berechnung der Differenz der RGB Werte der Pixel. Dann kannst Du mit Hilfe der richtigen Algorithmen auf Basis eines Testdatensatzes einen Entscheidungsbaum aufbauen. Mit den richtigen Metriken kann man je nach Problem auf verblüffend gute Ergebnisse kommen.

Klingt sehr theoretisch, ist es auch, aber dank der Weka-Bibliothek mit Java recht easy zumzusetzen: http://www.cs.waikato.ac.nz/ml/weka/

 

[beachdiddi]

Was mir noch spontan einfallen wuerde:

Du rechnest beide Bilder auf die gleiche, kleine Groesse (zb 50x50 Pixel) runter. So dass, wenn zb das Ursprungsbild 100x100 gross ist, immer aus 2x2 Bloecken ein Pixel mit dem Durchschnitt der 4 Pixel wird. Dann nimmst du die Differenz der beiden (nun gleich grossen) Bilder, errechnest die Summe der Pixel-Differenzen und ab einem Grenzwert vergleichst du (oder jemand anderes ;-) ) die beiden Originalbilder.

Nur so als Idee...

Mal ne blöde Frage: Wie bildest Du den Durchschnitt bei 4 Pixeln. Da steht doch in jedem Feld immer 0 oder 1 drin, oder?
Zählst Du einfach die 1er und teilst sie durch 4?
Das finde ich eine gute Idee. Wie performant ist das resizen eines Bildes?
Und den Vergleich der "Durchschnittspixel" könnte ich ja dann wieder mit verschiedenen Threads machen.

Du könntest auch die Arrays komplett durchlaufen und dir in einem weiteren Array die Differenzen speichern.

Da stehe ich ja wieder vor dem wie 'wildcard' sagt, teuren Pixelvergleich, oder?

Klingt sehr theoretisch, ist es auch, aber dank der Weka-Bibliothek mit Java recht easy zumzusetzen: http://www.cs.waikato.ac.nz/ml/weka/

Klingt wirklich sehr theoretisch. ???:L
Ich habe zwar schon mal was von Entscheidungsbäumen gehört, aber nur in Verbindung mit Ausprägungen wie: kalt, warm, heiß und sehr heiß
Kannst Du die Idee noch ein bisschen genauer beschreiben?
Dienen die verschiedenen Methoden sozusagen als Entscheidungspunkte in meinem Entscheidungsbaum?
Und wie würden meine Trainingsdaten dann zum Beispiel aussehen? Viele Bilder?

 

[byte]

Ich habe zwar schon mal was von Entscheidungsbäumen gehört, aber nur in Verbindung mit Ausprägungen wie: kalt, warm, heiß und sehr heiß
Kannst Du die Idee noch ein bisschen genauer beschreiben?
Dienen die verschiedenen Methoden sozusagen als Entscheidungspunkte in meinem Entscheidungsbaum?
Und wie würden meine Trainingsdaten dann zum Beispiel aussehen? Viele Bilder?

Das stimmt schon, aber selbst bei einfachen Ja/Nein Entscheidungen (in Deinem Fall Bilder gleich oder nicht) kann man damit oft gute Ergebnisse erzielen. In Deinem Fall könntest Du als Metrik halt ne Methode schreiben, die prüft um welchen RGB Wert die einzelnen Pixel auseinander liegen. Als Testdatensatz nimmst du dann verschiedene Bilder (identische Bilder, gleiche Bilder aber anderes Format/ Komprimierung, unterschiedliche Bilder). Du gibst dem Algorithmus für diese Testdaten die Ergebnisklassifikation vor. Daraus generiert der Algorithmus (zig Classifier sind in Weka schon implementiert) dann den Entscheidungsbaum, der (je nach Güte der Testdaten und Metriken) allgemeingültig ist. Du musst in diesem Fall also keine Schwellwerte für die RGB-Differenzen festlegen.

Richtig interessant ist dieser Lösungsansatz allerdings erst, wenn man viele verschiedene Metriken (also Entscheidungsknoten) hat. Musst Du mal gucken, ob das bei Deiner Entscheidung sinnvoll ist. Die Umsetzung ist mit Weka zumindest nicht sonderlich schwierig.