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 ...
 
#4
Den ein Bild was überbelichtet ist, ist nicht identisch aber zu 98% ähnlich.
So wie ich das herauslese, möchtest du erkennen, ob zwei Bilder - bis auf eine unterschiedliche Belichtungszeit - dasselbe Objekt zeigen. Ist das korrekt?
Im einfachsten Fall, müsste der Zusammenhang zwischen zwei Bildern mit unterschiedlicher Belichtungszeit linear sein.
Bild_A = c * Bild_B
Wenn die Überbelichtung zu krass ist, kommt es natürlich zu Clipping. Bei krasser Unterbelichtung, wird das Bildrauschen der Kamera das Bild stark beeinflussen. Das wären dann nichtlineare bzw. stochastische Einflüsse, aber ich gehe mal davon aus, dass wir diese hier ignorieren können.

Dein Ansatz auf Basis des normierten Histogrammvergleichs klingt erst mal naheliegend. Hast du das schon getestet? Vielleicht reicht das ja schon aus. Mir ist noch nicht ganz klar, warum du das Bild auf 32x32 komprimieren möchtest. Ich würde mir das folgendermaßen vorstellen:
1) Berechnung des normierten Helligkeitshistogramms. Bei einer Farbtiefe von 8 Bit wäre das ein diskretes Signal mit 2^8=256 Stützstellen.
2) Das normierte Histogramm könnte man jetzt noch komprimieren, um Platz in der DB zu sparen. Dazu gibt es unterschiedliche Ansätze. Du könntest z.B. das Signal mit DCT in den Frequenzbereich überführen und nur die Koeffizienten für die niedrigen Frequenzen speichern.
3) Bei einem neuen Bild führst du Schritt 1 und Schritt 2 erneut durch. Anschließend kannst du die Histogramme im Frequenzbereich vergleichen.

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
Wenn du die diskrete Fourier-Transformation (DFT) verstanden hast, ist das eigentlich relativ easy. Wenn du die diskrete Fourier-Transformation nicht kennst, lies es am besten mal nach. Dazu gibt es unzählige Materialien im Internet (Youtube, Wikipedia, etc.). Ist sehr praktisch.

Nehmen wir mal an, wir verwenden die DFT zur Kompression. Das würde dann so aussehen:
1) Signal (das kann z.B. ein Audiosignal (1d), oder auch ein Bild (2d) sein) wird in den Frequenzbereich transformiert.
2) Zur Kompression werden im Frequenzsprektrum hohe Frequenzen abgeschnitten. Man speichert die Frequenzkoeffizienten der niedrigen Frequenzen. Dadurch wird das Signal zwar verändert, aber das menschliche Sinnessystem stört es nicht sonderlich.
3) Zur Rekonstruktion wird das (verlustbehaftet komprimierte) Frequenzspektrum wieder rücktransformiert.

Die DCT ähnelt der DFT sehr stark, allerdings ist es aufgrund einer anderen Randbereichsfortsetzung besser zur Kompression geeignet. Man kann den letztgenannten Algorithmus damit also auch durchführen.
 
#5
@Night@ ist das nicht ein Problem mit der DFT wenn das Bild z.B. mit einem anderen Winkel aufgenommen wurde, oder vergroessert oder verkleinert ist.
Dann duerfte die Repraesentation doch anders ausfallen.

Fuer mich hoert sich das eher nach einem Problem an was man mit ML loesen koennte.
Fange damit aber selbst gerade erst an, und kann d.h. noch nicht so wirklich Hilfestellungen geben.

https://course.fast.ai/videos/?lesson=1

Cheers

Fluffy
 
#6
Zuallererst einmal danke für die Unterstützung,

kleine Randinformation:
Wir verwenden fast nur technische Zeichnungen, Explosionszeichnungen und soweiter - mit ein paar kleinen Ausnahmen

@Night@
Warum 32x32 Pixel - lediglich um Störfaktoren zu entfernen. Ist aber komplett aus meiner Betrachtung!

@Night@
Ehrlich gesagt vernachlässige ich die DCF Methode momentan, da sich mir diese nicht völlig erschließt und es für mich dadurch ein Brainfuck ist einen Vergleich durchzuführen (--Quasi etwas zu programmieren --).

mein bisher erster Ansatz:
1. Bild einlesen
2. in ein Graubild wandeln
3. Schwellwert der Grautöne ermitteln
4. Bit "0" oder "1" setzen, je nachdem, ob die RGB-Angaben über oder unter dem Schwellwert

Da Weiß keine Spektralfarbe ist und mir Weiß als solches, bei einer digitalen Betrachtung, keine wichtigen Informationen liefert werte ich nur die Schwarzanteile aus. Sprich, nur die gesetzten Bit's und führe einen direkte Vergleich durch.
Wenn eine 100 prozentige Übereinstimmung vorliegt abbruch und fertig, wenn nicht dann wird Bild1 gegen Bild2 verglichen und der prozentuale Antiel der Übereinstimmungen von Bild1 zu Bild2 ermittelt (Pixel by Pixel ). Wie bereits erwähnt nur die gesetzten Bit's. Im Umkehrschluss wird das gleiche von Bild 2 zu Bild1 ermittelt.
( ( %(Bild1) + %(Bild2) ) / 2 ) = %(Ähnlichkeit)

Mein erster Ansatz funtkioniert soweit schon einmal ziemlich gut und schränkt das ganze schon ziemlich gut ein...

mein zweiter Ansatz:
Das Bild aufbrechen in Objekte. Die Zusammenhängenden gesetzten Bit's ermitteln und durchlaufen. Also Bit by Bit -- Child by Child.
Wenn der Nachbar des gerade zu betrachtenden Bit's ein gesetztes Bit hat wird dieser weiter verfolgt und durchlaufen und das zusammenhängende "Objekt" kann somit separiert werden.

Somit erhalte ich eine Anzahl X an Objekte.

Warum?
Sollte das Bild z.B. in der horizontale Achse um 8 Pixel, sowie in der vertikalen Achse um -9Px verschoben sein kann ich hierüber die einzelnen, gefundenen Objekte im direkten Vergleich prüfen und hier ebenfalls prozentual ermitteln wieviel Übereinstimmungen hier vorliegen.

Wenn ich das jeweilige Objekt über den außerst linken, rechten, höchsten und tiefsten X/Y-Wert ermittelt habe, kann ich das Objekt als separates Bild ausschneiden. Nun gilt es nur noch zu prüfen, ob ich dieses generierte Bild an irgendeiner Stelle im anderen Bild finde und ermittel entsprechend , wenn eine Position gefunden wurde, die Übereinstimmungen der jeweiligen Anteile.

Im Endeffekt eine große Rekursion... Funktioniert wunderlicher Weise gut und relativ schnell.

Hier teste ich das Ganze aber noch auf die Zuverlässigkeit/Aussagekraft.

Gegebenenfalls werte ich dann noch, wei angesprochen, das Histogramm sowie die DCT/DFT Geschichte mit einbeziehen. Auch wenn es vielleicht nur dem eigenem Ego dient ... 8)
 

end4win

Member of Honour
#7
kleine Randinformation:
Wir verwenden fast nur technische Zeichnungen, Explosionszeichnungen und soweiter - mit ein paar kleinen Ausnahmen
Sind die nicht in der Regel beschriftet? Geräte-, Bauabschnitts- und Bauteilname oder sonstige Bezeichnungen; Datum und Seitenzahlen, wäre es da nicht einfacher und sicherer mit einer OCR Software nach Übereinstimmungen zu suchen?

Gruß
 
#8
Das Vielleicht schon, aber das funktioniert auch so ziemlich gut. Noch dazu sind die inhaltlichen Werte aus dem Bild, wie das Auswerten der Zeichen/Buchstaben auf Textbasis, für mich nicht von Bedeutung.

kleines Dummy Beispiel im Anhang ( es ist wirklich sehr klein und primitiv)

-die einzelnen Objekt sind farblich gestaltet
-die Rechtecke zeigen die gefundenen Bereiche (Objekte)
 

Anhänge

#9
@Night@ ist das nicht ein Problem mit der DFT wenn das Bild z.B. mit einem anderen Winkel aufgenommen wurde, oder vergroessert oder verkleinert ist.
Dann duerfte die Repraesentation doch anders ausfallen.
Stimmt genau. Allerdings bin ich davon ausgegangen, dass ByteSurfer nur Bilder mit unterschiedlicher Belichtungszeit trennen möchte. Also Winkel und Skalierung bleiben gleich.

Offenbar sollen Bilder nicht in eine Datenbank aufgenommen werden, wenn es in dieser nicht schon Ähnliche gibt.
Das ist aber im Allgemeinen ein sehr anspruchsvolles Problem. Bei beliebiger Skalierung, Orientierung, anderen Farben, usw. ist es sehr schwer algorithmisch die Ähnlichkeit von Bildern zu beurteilen. Wenn man das Problem durch Annahmen jedoch vereinfachen kann, könnte man eventuell eine zuverlässige Lösung finden, wenn auch nur für diesen Spezialfall.

Wenn deine Lösung jetzt aber schon ausreichend gut funktioniert, ist das Problem ja eigentlich abgehakt. Gut zu wissen, dass das Kleinskalieren zum Vergleich der einzelnen Pixel bei keiner Rotation passende Ergebnisse liefert.
 
#10
Offenbar sollen Bilder nicht in eine Datenbank aufgenommen werden, wenn es in dieser nicht schon Ähnliche gibt.
Das ist aber im Allgemeinen ein sehr anspruchsvolles Problem. Bei beliebiger Skalierung, Orientierung, anderen Farben, usw. ist es sehr schwer algorithmisch die Ähnlichkeit von Bildern zu beurteilen. Wenn man das Problem durch Annahmen jedoch vereinfachen kann, könnte man eventuell eine zuverlässige Lösung finden, wenn auch nur für diesen Spezialfall.
Genau - ein Suche hilft mir nur, wenn ich ein vernünftiges Ergebnis in einem annehmbaren Zeitfenster bekomme. Wenn die Maschine für 100 Bilder 12 Stunden benötigt, klicke ich mich manuell schneller durch und finde selber das Ergebniss schneller. Somit möchte ich keine Bilder physikalisch in der Datenbank abspeichern, sonder lediglich Muster / Kombinationen auf die ich eine Abfrage starten kann ablegen.

Die Skalierung ist ein Problem, das stimmt ... Die Farben (Rot, Grün , Blau und Weiß) ignoriere ich komplett und werte hier nur die schwarzen Anteile aus, denn diese sind für mich ausschließlich von interesse. Alles andere ist Binär "0".

Nehmen wir das Beispiel Auto als technische Zeichnung. Mein Programm durchläuft die schwarzen Pixel und sortiert die einzelnen, zusammenhängenden Objekte aus und speichert mir diese primitiv als Binäern String ab. Nun könnte ich mir doch theoretisch diesen String zur Hilfe nehmen und mir nur die Treffer anzeigen lassen welche eine Übereinstimmung größer 75% haben. Den gleichen Reifen könnte man unter Umständen auch in anderen Bildern verwenden.

Das Objekt Binär abgebildet und über X-NOR verküpft:
110101000100011101001010010001 (Vergleichstring aus der DB)
110101000100011101001010000000 (zu findender String)
________________________________________
111111111111111111111111101110 = ~93% Übereinstimmung

Das sollte doch funktionieren? Somit benötige ich das Bild nicht als Blob und kann dieses auf Fileebene abspeichern und darauf referenzieren. Ein Vorteil - nur theoretisch betrachtet - wäre hier auch einzelnen Objekte in Form von Ausschnitten finden zu können. Ich schneide einen Ausschnitt aus einem Bild aus und füge diesen in ein anderes hinein.

Als Beispiel, mein Programm sortiert mir ein Objekt (z.B. ein hydraulisches Ventil) heraus, welches irgendwann einmal ausgeschnitten und in ein anderes Bild kopiert wurde, heraus. Nun sollte dieses doch gefunden werden können, wenn in dem zu vergleichenden Bild die Skalierung nicht geändert wurde und es auch damals im Vorfeld als Objekt klassifiziert wurde und somit in der DB ein binärer String zum vergleichen vorliegt.

Ich bin aber noch am testen und versuche eine annehmbare Skalierung zu integrieren und für einen Vergleich zu berücksichtigen...

Gut zu wissen, dass das Kleinskalieren zum Vergleich der einzelnen Pixel bei keiner Rotation passende Ergebnisse liefert.
Dazu kann ich dir, wenn ich mehr Testdaten haben, später genaueres sagen
 
Zuletzt bearbeitet:
Oben