JPEG vergleichen auf identische Übereinstimmung, oder Ähnlichkeit

#1
Hi Folks,
ich habe momentan ein ziemliches Problem mit diversen Images (>15000) und eventuellen dazugehörigen redundaten Images, welche hier in dem JPG Format vorliegen.
Bei näherer Betrachtung dachte ich mir hier eine eigene Lösung anzustreben, welche mir zum ersten einmal 100% identische Bilder herausfiltert und anzeigt - quasi Pixel für Pixel - und im nächsten Schritt mir die Bilder aufzeigt, welche zum Original eine Ähnlichkeit aufweisen und auch nur alles mit einer Ähnlichkeit von größer 75% betrachtet.

Degrees, in Form von 90Grad | 180Grad | 270Grad Drehungen lasse ich komplett aus der Berechnung, ebenso wie die Betrachtung von Teilausschnitten.

An dieser Stelle sei gesagt dass ich mir bewusst bin nicht die Größe von Google zu haben, um solch eine komplexe Thematik zu lösen. Das Verständnis der Problematik, sowie eine angestrebte Lösung hierzu, sollte aber doch zu schaffen sein. Zurückgreifen möchte ich auf PHP, da ich mich hier zuhause fühle und die Sprache ebenfalls dafür geeignet ist.

Wie stelle ich mir das vor ...

Zuallererst möchte ich jedes Bild für sich analysieren und Metadaten hierzu in einer Datenbank erfassen.

Das bedeutet ich erstelle zu erst ein Histogramm aus dem Orginalen Bild und komprimiere das Bild im Anschluss auf 32x32 Pixel und erstelle hier ebenfalls ein Histogramm. Die Komprimierung auf 32 Pixel sorgt zum einen für eine schneller Verarbeitung und zum Zweiten werden dadurch kleinere Unterschiede "weg komprimiert". Die Zahlenfolgen, der jeweiligen Histogramme kommen in die DB.

Um einen Abgleich der Bilder durchführen zu können setze ich nun den Graufilter ein und erhalte hier eine Abstufung der jeweiligen Farbinformation.

Jetzt berechne ich mir den Schwellwert des Bildes über die Graustufen, in der Annahme das eine Graustufe immer die gleiche Farbinformation von RGB->r == RGB->g == RGB->b hat. Beispiel ==> RGB(234,234,234) oder RGB(245,245,245)

Unter dieser Betrachtung wird dann jeder einzelne Farbwert der Grafik miteinander addiert und durch die Gesamtpixelanzahl geteilt.(siehe Beispiel1).
Beispiel 1:
Code:
  // Schwellwert ermitteln
  for ($i = 0; $i < $imgw; $i ++) {
    for ($j = 0; $j < $imgh; $j ++) {
        $rgb = imagecolorat($im, $i, $j);
        $r = ($rgb >> 16) & 0xFF;
        $g = ($rgb >> 8) & 0xFF;
        $b = $rgb & 0xFF; 
        $schwellwert += (int)round(($r + $g + $b) / 3);
        $V = (int)round(($r + $g + $b) / 3);
        $histo[$V] += $V / $n;
    }
}
$schwellwert = $schwellwert / ( $imgw * $imgh );
Im zweiten Durchlauf betrachte ich dann jeden Pixel für sich und erstelle mir aus der gewonnen Information den binären String

Code:
...
if ((($r+$g+$b)/3) > $schwellwert)
      {
          $binaer[] = 1;
      }
      else
      {
          $binaer[] = 0;
      }
...
Um das Ganze hier später übergreifend Binär abgleichen zu können schreibe ich diesen Binärstring ebenfalss in die DB. Bei einem direkten Vergleich von BIT für BIT (Grafik zu Grafik) kann ich mir über den Fehlerwert eine prozentuale Übereinstimmung ausrechnen und hier alles was einen Wert von über 75% hat als ähnlich markieren.

Liege ich bis hierher absolut daneben oder wäre das ein kleiner plausibler Ansatz?

Im nächsten Durchlauf möchte ich mir den DCT (diskrete Kosinustransformation) Wert der JPG Datei ermitteln und hier ebenfalls eine Abgleich zu tätigen, ich weis bisher nur noch nicht ob das zum gewünschtenErfolg führt, da ich den Ansatz für einen Vergleich noch nicht verstehe, habe aber ein gutes Beispiel im Netz gefunden und konnte mir hierzu die jeweiligen 8x8 Werte errechnen...

Was kann ich mir noch für eine Vergleich heranziehen, bzw. welche Informationen sind wichtig/hilfreich?

Über Anregungen, bzw. Hilfestellung wäre ich dankbar
 

Chakky

Member of Honour
#2
Hallo bytesurfer,
ich nehme an du bist diesen kleinen Code ausflug gefolgt:
http://www.powerdev.de/?p=202

Ich hab das Problem noch nicht so ganz verstanden. Willst du jetzt die Bilder als Datei vergleichen. Also ist 1.jpg gleich 2.jpg? Wenn ja: Dann nehme eine beliebige Hashfunktion und wenn das gleiche Ergebnis raus kommt, sind es zwei identische Dateien.

Oder willst du den Inhalt des Bildes vergleichen? Dann ist mMn dein Ansatz richtig, das Pixelweise zu vergleichen. Warum du da ein Histogramm nutzt bin ich mir aber unsicher? Wenn du eh jeden einzelnen Pixel miteinander vergleichst kannst du ja direkt abbrechen sobald der Schwellwert (+ Toleranz) überschritten ist.....


Ein ganz anderer Ansatz wenn du mit php Unterwegs ist, vielleicht gibt es auf den Webserver direkt Linuxboardmittel die du nutzen kannst und per "bösen" system()-Befehl ansprichst. Ich denke da so an: https://wiki.ubuntuusers.de/ImageMagick/ oder auf Datei ebene: https://wiki.ubuntuusers.de/diff/
 
#3
Hallo bytesurfer,
ich nehme an du bist diesen kleinen Code ausflug gefolgt:
http://www.powerdev.de/?p=202
Den Beitrag kenne und habe diesen inhaltlich von der Idee und vom Ansatz mit verarbeitet, habe mir aber aus der gesamtheit des Netzes einen kompletten Überblick geschaffen.
Ich hab das Problem noch nicht so ganz verstanden. Willst du jetzt die Bilder als Datei vergleichen. Also ist 1.jpg gleich 2.jpg? Wenn ja: Dann nehme eine beliebige Hashfunktion und wenn das gleiche Ergebnis raus kommt, sind es zwei identische Dateien.
wenn ein direkter vergleich stimmt, also 1.jpg === 2.jpg fallen alle anderen Prüfung aus. Sollte der direkte Vergleich nicht passen möchte ich in die Ähnlichkeitsprüfung gehen. Den ein Bild was überbelichtet ist, ist nicht identisch aber zu 98% ähnlich.

Warum du da ein Histogramm nutzt bin ich mir aber unsicher?
Meine Idee ist, je mehr Prüfungen ich habe, umso genauer ist die Aussagekraft des Ergebnisses für den prozentualen Wert der Ähnlichkeit.
Beispiel:
55%+74%+66% = 65% Ähnlichkeit
10%+74%+66% = 49% Ähnlichkeit

Am Beispiel Histogramm kann ich mir den Faktor (Über-/Unterbelichtung) ermitteln und ins Verhältnis zu den Bildern setzen. Der Kurvenverlauf sollte, wenn beide bilder in "GREYSCALE" sind, annähernd identisch sein, zumindestens in meiner Theorie und in den bisherigen Versuchen. Mit dem Delta und einer eingerechneten Toleranz kann ich einen prozentwert errechnen und eine Aussage zu einer Ähnlichkeit treffen.

Ich bin mir im klaren, das zu guter letzt immer noch ein menschliches Auge einen Blick riskieren muss einen genauen Treffer zu landen. Wenn mir das System aber z.B.: 40 anbietet kann ich hier einen ausschluss treffen- so der Plan.

Auf externe Libraries möchte ich im Moment nicht zugreifen, sondern das Thema als solches erst einmal im Kopf verstehen und selber an einer kleinen Lösung stricken ...
 
Oben