Grafiken mittels Hashing vergleichen. aber wie?

[-Hades-]

Hi Leute,

ich habe 2 Grafiken als BufferedImage vorliegen und möchte prüfen ob sie gleich sind (also alle Pixel denselben Farbwert haben).
Bis jetzt hab ich es so gemacht das ich alle Pixel durchgegangen bin und wenn ein Pixel gefunden wurde der sich von dem der anderen Datei an derselben Position unterschied wusste ich das sie nicht gleich sind. Da ich dazu immer "umständlich" zwei Arrays durchlaufen muss möchte ich das jetzt gerne mit Hashing machen.

Also mit
if (File1.hashcode() != File2.hashcode()) {return false;}
geht es nicht da der hashwert in dem Fall nicht nur aus dem Inhalt der Grafiken berechnet wird (anscheinend).

Falls jemand eine Lösung hat wäre ich sehr dankbar!

Gruß Dominik

 

[Wildcard]

pixel für pixel. anders kriegst du's nicht hin.
Sinnvoll ist's aber erstmal die Bildgröße auf Gleichheit zu testen.

 

[-Hades-]

wow, eine so schnelle Antwort :toll:

nur leider genau die die ich nicht hören wollte

Hmm also ich weiß das es in VB.net ohne Probleme geht, irgendjemand meinte mal das man dazu irgendein System.security oder so benutzen muss und das normale hashing für datenstrukturen nicht funktioniert (diese Aussage ist mit Vorsicht zu genießen da sie nur sehr bruchstückhaft in meinem Kopf rumschwirrt aber das es klappt weiß ich ziemlich sicher).

Also wenn es wirklich nicht gehen sollte, könnte mir das noch jemand bestätigen, dann kann ich aufhören danach zu suchen aber ich bin noch nicht ganz davon überzeugt, bis jetzt.

Also an alle Experten, wenn es eine Lösung gibt bitte posten.

Falls jemand das das Thema hier nicht reinpasst bitte ich um Entschuldigung aber ich wusste es nicht besser, es handelt sich ja auch um Grafiken deren Inhal ich vergleichen möchte

Gruß Dominik

Asooo, noch was am Rande, die Bildgröße is eh immer gleich bei den Vergleichen.

 

[Wildcard]

Sofern du gewisse Annahmen für die Bilder treffen kannst gibt es effizientere Verfahren.
Sag mal ein paar Worte dazu was du genau vor hast.

 

[Wildcard]

In der Zwischenzeit schonmal was zum verdeutlichen warum man hier nicht einfach hashCode nehmen kann.
Etwas anderer Kontext, aber trotzdem:
http://www.java-forum.org/de/viewtopic.php?t=28251

 

[-Hades-]

Hmm okay, ich hätte es vielleicht gleich etwas präzisieren sollen.

Ich habe kleine gif-Dateien (50x50 Pixel) vorliegen und lasse von meinem Programm in gewissen Abständen einen Screenshot machen um zu gucken ob ein bestimmter Fall (den ich durch Bildvergleich ermitteln möchte) eingetreten ist. Die vorliegende Grafikdatei lasse ich als BufferedImage einlesen und lese auch den (frisch) gemachten Screenshot als BufferedImage ein. Die beiden gleichgroßen BufferedImages möchte ich dann wie gesagt auf Gleichheit vergleichen.

Es müssen also zwingend alle Pixel exakt gleich sein damit ich genaue Aussagen machen kann.

Das sollte zu den Rahmenbedingungen genügen denke ich.

 

[Wildcard]

Da bei einem Hashwert grundsätzlich Kollisionen auftreten können müssteste du bei identischen Hashwerten trotzdem alle Pixel vergleichen, ein Hashwert würde also nur der Vorsortierung dienen.
Das Problem ist aber das ein Hashwert natürlich auch den gesamten Inhalt der Daten anfassen muss, daher stellt sich die Frage in wie weit das überhaupt schneller als ein Pixelvergleich ist.
Falls du die Dateien eh rauspeichern musst würde sich zum Beispiel ein Vergleich der Dateigröße als Vorauswahl eignen.

 

[-Hades-]

Hmm verdammt das macht alles schon ziemlich Sinn was du sagst!
Das mit den Kollisionen und das zwei unterschiedliche Objekte auf denselben Hashwert abgebildet werden können is wohl das Hauptproblem. Das das ganze nicht wirklich schneller sein (ich denke mein Code is recht optimiert) is auch klar... wahrscheinlich wollte ich nur ne Lösung mit der ich die 5 Zeilen Code mit den Arrays durch nur eine mit dem Hashing ersetzen kann :roll:

Aber du scheinst zu wissen das es doch geht und auch wie, wenn du Lust hast könntest du das bitte trotzdem posten? Jetzt interessierts mich doch, auch wenn ich meine Implementierung wohl bestehen lasse.

Gruß Dominik

 

[Wildcard]

Naja, wenn ich's jetzt machen müsste und kein Array benutzen dürfte würde ich mir wohl von beiden BufferdImages das ColorModel geben lassen und dann nachsehen ob in der konkreten Implementierung equals sinnvoll überschrieben ist... ???:L

 

[-Hades-]

Hmm okay, das is für mich noch zu hoch, bin noch nicht lange bei der Programmierung mit Java, ich habe equals() gar nicht überschrieben da ich mich damit nicht auskenne. Auf jeden Danke für deine schnellen Antworten Wildcard!!

 

[Wildcard]

Nein, du musst gar nichts überschrieben.
Lass dir nur mal von deinem BufferedImage das ColorModel geben und schau dir an welche konkrete Instanz verwendet wird.
Sobald das geklärt ist kann man im Source dieser Klasse nachsehen ob dort equals überschrieben ist, und wenn ja, wie.

 

[-Hades-]

Ok, also ColorModel() ist in der Klasse Java.awt.image.BufferedImage zu finden. Ich hab aber irgendwie die Befürchtung das es nicht das ist was du hören willst, wie finde ich heraus welche konkrete Instanz benutzt wird?

 

[Wildcard]

Es gibt verschiedene ColorModels. Welches konkret verwendet wird kann man am einfachsten zur Laufzeit rausfinden.

System.println(bufferedImage.getColorModel().getClass().getName());

 

[-Hades-]

java.awt.image.IndexColorModel


so sieht die Ausgabe bei mir aus.

 

[Wildcard]

Läuft wohl auf das Gleiche raus:

  public boolean equals(Object obj) {
        if (!(obj instanceof ColorModel)) {
            return false;
        }
        ColorModel cm = (ColorModel) obj;
        
        if (this == cm) {
            return true;
        }
        if (supportsAlpha != cm.hasAlpha() ||
            isAlphaPremultiplied != cm.isAlphaPremultiplied() ||
            pixel_bits != cm.getPixelSize() ||
            transparency != cm.getTransparency() ||
            numComponents != cm.getNumComponents())
        {
            return false;
        }

        int[] nb = cm.getComponentSize();

        if ((nBits != null) && (nb != null)) {
            for (int i = 0; i < numComponents; i++) {
                if (nBits[i] != nb[i]) {
                    return false;
                }
            }
        } else {
            return ((nBits == null) && (nb == null));
        }

        return true;
    }

Die Methode ist allerdings von ColorModel, da sie in IndexColorModel nicht neu überschrieben wird.
Ich würde das einfach so benutzen, dann hast du's zumindest aus deinem Code raus.

 

[-Hades-]

Hmm was heißt das jetzt genau? Kann ich jetzt einfach die beiden ColorModels mit equals vergleichen?

 

[Wildcard]

Hmm was heißt das jetzt genau? Kann ich jetzt einfach die beiden ColorModels mit equals vergleichen?

Ja. müsste eigentlich funktionieren. Hab's aber nicht versucht, daher keine Garantie...

 

[-Hades-]

Ok, danke ich werds ma versuchen, jetzt geh ich aber erstmal pennen, ich schreib morgen obs geklappt hat

 

[HaBaLeS]

Gu solltest aber auch testen, ob die Gif´s die du als Referenz einliest die gleiche Instanz des Color Models benutzen.

Deine Ursprüngliche Idee die Bilder Mittels Hash zu überprüfen, könntest du mal mit einem MD5 Hasch probieren, aber ich bezweifle ein bisschen, das du damit erfolg haben wirst, da die Headerdaten der Bilder wahrscheinlich nicht gleich sind. Bei RAW Images könnte es klappen.

Generell ist hierfür gerade ein GIF als quelle eher ungeeignet, da es mit Paletten arbeitet. Wenn du einen Screenshot machst kann es gut sein, das du eine ganz andere Palette hast als im Originalbild und das macht das vergleichen sehr schwer. Versuch´s doch mal mit BMP´s

Grüße

 

[-Hades-]

Ok, ich kann gerne mit bmp´s arbeiten aber ich denke das die Bilder im Aufbau gleich sind, da ich die schon vorliegenden Grafiken, die als Referenz dienen mit demselben Programm erzeugt habe.

Wie läuft das denn genau mit dem MD5 hash?

 

[HaBaLeS]

MD5 erzeugt eine 128Bit Prüfsumme über deine Daten. Wenn diese übereinstimmen, ist es sehr wahrscheinlich (nicht garantiert!!), das diese übereinstimmen.

de.wikipedia.org/wiki/Message_Digest_Algorithm_5

Implementierungen für MD5 in Java solltest du bei Google viele finden. Die JRE kann es zwar von sich aus auch, aber dann musst du noch einen Wrapper schreiben, damit du es auf Dateien anwenden kannst. Message Digest bei Gallileo Computing