Hi,

ich arbeite derzeit an einem Projekt (privat) welches Bilder von Webseiten
runterlädt.
Um doppelte Bilder zu vermeiden habe ich, folgendes, einfaches System eingebaut:
1. Beide der zu vergleichenden Bilder in Graustufen umwandeln.
2. Beide auf 32² Pixel skalieren.
3. Die durchschnittliche Helligkeitsdifferenz der beiden Bilder errechnen.

Das ganze funktioniert dank der Skalierung auch ziemlich gut.
Allerdings hat das ganze bei Schwarzweißbildern starke Probleme.
Verschiedene Comics beispielsweise werden als 95% gleich erkannt.

Deshalb hier die Frage(n):
- Gibt es relativ einfache Algorithmen zur Bilderkennung?
- Welche kennt ihr?
- Wie könnte ich meinen einfachen Algorithmus verbessern?

Guck dir mal einen auf 32x32px runtergerechneten Comic an. Ich glaube das da oft was gleich aussieht sollte dich ned wundern. Warum wandelst du es in Graustufen um anstatt einfach jeweils die einzelnen RGB Kanäle zu betrachten?

Nun ist deine Zeit gekommen sprach der Tod, stolperte und brach sich das Genick. :o

hier duerften sich einige algos finden, http://scholar.google.com/scholar?hl=en&as_sdt=2000&q=detecting+duplicate+images

Ich wandle es in Graustufen um, um die Dateigröße meiner Datenbank zu reduzieren.

Außerdem wüsste ich nicht was das betrachten der einzelnen Kanäle für einen Vorteil hätte, ob ich zuerst Graustufen draus mache und dann die
Durchschnittsdifferenz berechne, oder selbe aus den 3 verschiedenen Kanälen
zusammenrechne kommt denke ich aufs gleiche raus.

Oder habe ich deine Vorgehensweise vielleicht falsch verstanden?

@dp: Danke, sieht gut aus, werde ich mich durchwühlen.

Du sollst ja eben nicht die 3 Kanäle zusammenrechnen.

Nun ist deine Zeit gekommen sprach der Tod, stolperte und brach sich das Genick. :o

Naja, angenommen ich hab die Differenz von den 3 Kanälen, dann
bringt mich das auch nicht weiter, denn ich muss ja diese 3 Werte addieren und
dann durch 3 teilen um den Durchschnitt zu erhalten.

Meine Funktion übernimmt ja 2 Bilder und errechnet den Prozentwert zu dem
sie sich gleichen. Ob ich da jetzt beide zu grau mache, oder RGB-Differenz berechne und dann den Durchschnitt bilde, kommt doch aufsgleiche raus...
Wenn ich die 3 Kanäle wie du sagst nicht zusammen rechne, dann hätte ich ja 3 Rückgabewerte, welche ich früher oder später ja auch irgenwie zusammenrechnen muss.

Natürlich musst du für deine Auswertung am Ende alles durch eine Funktion jagen, die dann sämtliche Information auf einen Prozentwert oder gleich einen BOOLschen Wert abbildet, um den Vergleich zu bewerkstelligen. Aber bis dahin solltest du versuchen ein gesundes Maß an Informationen zu erhalten anstatt sie zu vernichten. (Die feste Skalierung auf 32² vernichtet bspw. umso mehr Information je größer das Ursprungsbild war)

Zu RGB vs Grayscale am Beispiel:
Bei dir ist RGB(100,0,200) das selbe wie RGB(200,100,0) nämlich Gray(100) (unter der Annahme, dass du gleiche Gewichte für jeden Farbkanal bei der Durchschnittsbildung benutzt).
Wobei hier aber eine Differenz von RGB(-100,-100,200) besteht und daraus kannst du jetzt nicht einfach Gray(0) machen, weil nun einmal Lila nicht gleich Orange ist.

The C language combines all the power of assembly language with all the ease-of-use of assembly language.
"humorig is n blödwort :>" by -CarniGGeLjumpR-

Zitat:

Felheart postete
Ob ich da jetzt beide zu grau mache, oder RGB-Differenz berechne und dann den Durchschnitt bilde, kommt doch aufsgleiche raus...

Du siehst, die Graustufen sind exakt gleich!

Ok, dann werde ich die Bilder auf 64² skalieren lassen.

Das mit den Farben ist mir ja auch klar, dass eben Grau nicht gut ist (nur einfacher zu rechnen), aber wie schlagt ihr vor das ich dann weiterverfahre?

Angenommen ich habe das "DifferenzBild" von Rot, Blau und Grün.
Wie soll ich aus den drei Differenzbildern nun einen Prozentwert machen?
Wenn ich alle 3 Differenzbilder zusammenrechnen würde und durch 3 teilen würde,
hätte ich mir den Aufwand mit den seperaten Channels nicht machen müssen,
sondern gleich bei Graustufen bleiben können.

Folglich darf ich aus den 3 Channels keinen Durchschnitt bilden.
Aber was soll ich sonst machen?

@Bluthund: Ich hab folgende Formel für Color->Gray benutzt:
0.299*R + 0.588*G + 0.111*B
Diese hab ich aus dem Internet, ob das jetzt einen so grossen unterschied zu:
(R+G+B)/3
macht weis ich nicht...

@CPoly:
Du sagst in deinem Satz über dem Bild "Eben nicht".
Aber in deinem Satz unter dem Bild stimmst du meinem Quote zu.
Ich sagte doch, "kommt doch aufs gleiche raus"
und du sagst "Du siehst, die Graustufen sind exakt gleich!"
Versteh ich nicht ganz.

Das ich die Farben irgenwie in meine Berechnung einbeziehen sollte ist mir schon
klar, aber wie genau ich das (ausser
einer Durchschnittsrechnung, das ist ja was hier bemängelt wird) bewerkstelligen
soll ist mir nicht klar.

Zitat:

Felheart postete

@Bluthund: Ich hab folgende Formel für Color->Gray benutzt:
0.299*R + 0.588*G + 0.111*B
Diese hab ich aus dem Internet, ob das jetzt einen so grossen unterschied zu:
(R+G+B)/3
macht weis ich nicht...

aus den 3 differenzbildern einen prozentwert? 3 prozentwerte mitteln zb? oder den maximalen wert nehmen (pro pixel)?

caedes

Deutschland rückt nach Einschätzung der Sicherheitsbehörden im Superwahljahr verstärkt ins Visier von Terroristen.

Zitat:

aus den 3 differenzbildern einen Prozentwert? 3 Prozentwerte mitteln zb? oder den maximalen wert nehmen (pro Pixel)?

@caedes: Einen Unterschied macht es schon das ich eine andere Formel für die
Grauberechnung verwende, das ist mir klar.
Das ich sagte: "ob das jetzt einen so grossen unterschied macht",
damit meinte ich ja das ich nicht genau weis wie stark wohl der Unterschied der Zuverlässigkeit des Algorithmus sein wird.
Klar macht es einen fürs Bild, aber im Hinblick auf die Zuverlässigkeit fällt dieser wohl eher klein aus.

Du hast meinen Post falsch gedeutet, ich dachte das Bild würde alles sagen.

Auf dem Bild sind links zwei offensichtlich verschiedene Bilder. Wenn du die beiden aber in Graustufe umwandelst, ergibt sich nach deinem Algorithmus eine Ähnlichkeit von 100%. Wenn du hingegen aus den Ähnlichkeiten der drei Kanäle einen Mittelwert bildest, kommt nicht 100% raus!

Edit: Da du nicht alle Kanäle gleich stark gewichtest, sind es natürlich keine 100% mehr, aber das spielt ja keine Rollte in meiner Argumentation.

Zitat:

Bluthund postete
BOOLschen Wert

\o tanz den naziprau! o/

And more than ever, I hope to never fall,
Where enough is not the same it was before

@CPoly: Ahh stimmt, ja habs jetzt verstanden, danke.
Ich werds mal so probieren

Ich denke mal, dass du Bilder jetzt nicht unter Einbezug von z.B. affinen Transformationen (Rotation, Skalierung, Verschiebung) noch als gleich erkennen möchtest, sondern dass du davon ausgehst, dass zwei gleiche Bilder auch wirklich gleich sind. Hier mit höheren Modellen der Mustererkennung heranzugehen wär mit Kanonen auf Spatzen geschossen.

Trotz allem musst du Invarianten finden, was dann aber natürlich einfacher ist, weil du schlicht keine Freiheitsgrade für Transformationen berücksichtigen musst. Eine Skalierung auf 32x32 Pixel würde dir also die Möglichkeit geben, Bilder in einem Vektor mit 1024 Elementen (jeweils im Wertebereich von 0..255) darzustellen. Du kannst Vektoren solcher Bilder elementweise vergleichen, bei 1024 Elementen geht das ja noch recht schnell. Du könntest aber auch nen Monte-Carlo Ansatz nehmen und beliebige Punkte aus deiner Bildmatrix greifen (z.B. 30 Stück), sie in ihrer 4er-Nachbarschaft identifizieren und mit dem zu vergleichenden Bild abgleichen. Damit hättest du noch 150 Schritte für einen Vergleich von zwei Matrizen, der dir schon erstaunlich gute Ergebnisse liefern kann.
Summen über solche Elemente oder über Grauwertbilder zu machen ist denkbar schlecht, du hast ja schon selbst festgestellt, dass das bei verschiedenen Bildtypen dann schnell mal zu "false positives" führt.

Zitat:

Ich denke mal, dass du Bilder jetzt nicht unter Einbezug von z.B. affinen Transformationen (Rotation, Skalierung, Verschiebung) noch als gleich erkennen möchtest, sondern dass du davon ausgehst, dass zwei gleiche Bilder auch wirklich gleich sind. Hier mit höheren Modellen der Mustererkennung heranzugehen wär mit Kanonen auf Spatzen geschossen.

Zitat:

Du kannst Vektoren solcher Bilder elementweise vergleichen, bei 1024 Elementen geht das ja noch recht schnell.

Zitat:

sie in ihrer 4er-Nachbarschaft identifizieren und mit dem zu vergleichenden Bild abgleichen.

Zitat:

Damit hättest du noch 150 Schritte für einen Vergleich von zwei Matrizen, der dir schon erstaunlich gute Ergebnisse liefern kann.

Also Kurzum würdest du alle 34Pixel ein Pixel und seine Nachbarn mit dem anderen Bild vergleichen oder wie?

Ja, die 4er-Nachbarschaft besteht aus 5 Pixeln: Dem Referenzpixel selbst und den 4 direkten Nachbarn: Nord, Ost, Süd, West.
Aber der Vergleich ist anders gemeint. Du vergleichst direkt die Grauwerte von jeder Nachbarschaft. Dabei würde ich an deiner Stelle das Referenzpixel stärker gewichten als die 4 drumherum, aber der Einfluss der Nachbarschaft ist entscheidend. Und Monte-Carlo heisst, dass du beliebige Pixel aus deinem Bild greifst, keine Regelmäßigkeit wie "alle 34 Pixel".

Als Beispiel: Du hast den Pixel (10, 15) zufällig herausgegriffen. Als Charakteristik lässt sich der Pixel mit seiner Nachbarschaft vektoriell als (G_r, G_n, G_o, G_s, G_w)^T darstellen. Dabei ist G der Grauwert und r, n, o, s, w sind Indizes, die für referenz, nord, ost, süd, west stehen. Ganz konkret setzt sich der Vektor für unser Beispielpixel (10, 15) so zusammen:
G_r = (10, 15)
G_n = (10, 14)
G_o = (11, 15)
G_s = (10, 16)
G_w = (9, 15)

Dann nimmst du den Vektor aus deinem einen Vergleichsbild und den passenden Vektor zu Pixel (10, 15) aus deinem Bild der Datenbank und vergleichst die Vektoren komponentenweise. Du kannst sie auch entsprechend einer gewünschten Gewichtung der Komponenten noch normieren, die Funktion dafür kannst du dir im Grunde selbst aussuchen, du kannst sie aber auch erstmal ganz weg lassen.

Es gibt noch andere Ansätze (z.B. über C-Transformationen der Bilder) mit denen du auf Gleichheit (nicht wirklich auf Ähnlichkeit) prüfen kannst. Hab grad nicht die Zeit, mehr darüber zu schreiben, aber vllt hol ich das heute abend oder morgen mal nach... (Vorab schonmal das hier bzw. allgemein das hier)

Auch auf die Gefahr hin, mich mit meinem Betrag zu disqualifizieren, aber wie sähe es mit folgender Methode aus:

Man nimmt beide Graubilder, invertiert eines davon und addiert diese miteinander. Wenn die Summe "weiß" ist folgt daraus, dass die Bilder gleich sind.

Edit: oder ist das genau das, was du mit der "Helligkeitsdifferenz" meintest?

Heute schon gegoogelt?
spezi|Clan
TheWall.de - wo jeder alles sein kann.

Zitat:

speziFanta postete
Edit: oder ist das genau das, was du mit der "Helligkeitsdifferenz" meintest?

@Felheart:
Auch für den gewichteten Durchschnitt der Kanäle bleibt o.g. Problem bestehen. Die Gewichte, die du da nimmst, sind iirc nur auf das Helligkeitsempfinden des menschlichen Auges auf verschiedene Farben abgestimmt. Für die Maschine macht das jetzt nicht unbedingt Sinn, außer du möchtest, dass wie bereits erwähnt z.B. ein Unterschied im Grünkanal stärker ins Gewicht fällt.

Was mir gestern noch eingefallen ist:
Was sind denn eigentlich die konkreten Kriterien für Gleichheit in deinem Fall?
Was sind es für Bilder?
Nur gleiche Motive mit unterschiedlichen Dimensionen oder auch Tolerierung von unterschiedlich starken Kompressionsartefakten?

Gerade durch die Skalierung auf Briefmarkengröße, könnten wenn es sich um viele ähnliche Motive (bspw. Landschaften) handelt sehr schnell viele False-Positives ergeben.

@td:
Das ist natürlich korrekt.

The C language combines all the power of assembly language with all the ease-of-use of assembly language.
"humorig is n blödwort :>" by -CarniGGeLjumpR-

@LeJean:
Wenn ich die zu vergleichenden Bildpixel nach einem Zufallsprinzip auswähle,
dann erhalte ich aber doch jedes mal einen (wenn auch minimal) anderen
Prozentwert für die "Gleichheit" der Bilder. Ist das nicht schlecht?
Oder macht die Ersparnis des Rechenaufwandes das locker wieder wett?
Was spricht gegen eine Normalverteilung ala alle 34px ?

Diese C-Transformation aus dem PDF sieht übrigens sehr vielversprechend aus!

@speziFanta:
Ja, genau das mache ich derzeit schon mehr oder weniger erfolgreich.

@Bluthund:

Zitat:

Auch für den gewichteten Durchschnitt der Kanäle bleibt o.g. Problem bestehen. Die Gewichte, die du da nimmst, sind iirc nur auf das Helligkeitsempfinden des menschlichen Auges auf verschiedene Farben abgestimmt. Für die Maschine macht das jetzt nicht unbedingt Sinn, außer du möchtest, dass wie bereits erwähnt z.B. ein Unterschied im Grünkanal stärker ins Gewicht fällt.

Zitat:

Was sind es für Bilder?
Nur gleiche Motive mit unterschiedlichen Dimensionen oder auch Tolerierung von unterschiedlich starken Kompressionsartefakten?

Hier besteht natürlich eine extreme Gefahr das jemand irgendwas quotet oder auf irgendeine Art und Weise nochmal postet.
Solche Duplikate sollen verhindert werden.
Bei Reposts ist es natürlich auch nicht gewährleistet das keine neuen Kompressionsartefakte hinzugekommen sind, die Bilder sind aber trotz Artefakten
ja noch die selben...

Sehr interessantes Thema...

Bzgl Kompressionsartefakte:
Vielleicht würde es etwas helfen, wenn du statt einzelner Pixel die Frequenzkomponenten nach einer Fouriertransformation vergleichst... Da Kompressionsartefakte ja meiner Erfahrung nach sich eher in den hohen Frenquenzen niederschlagen, könntest du sie so gut ausfiltern.

Es gibt 2 Möglichkeiten, eine Kristallkugel zu benutzen:
a) um damit Spekulationen über ein Problem eines Users zu machen und
b) um sie einem besonders unkooperativen User über den Schädel zu ziehen.
- bloggt jetzt auch selbst auf Sclavia.de

Das Problem mit den Kompressionsartefakten sollte sich doch durch das verkleinern von selbst lösen. Falls es nicht schon gesagt wurde, würde ich in jedem Fall die Hashes der Bilder speichern und damit abgleichen ob das Bild schon vorhanden ist.

Nun ist deine Zeit gekommen sprach der Tod, stolperte und brach sich das Genick. :o

Huch, lang nicht mehr reingeschaut...

Ganz kurz zu deiner "Normal"-Verteilung (du meinst sicher ne gleichmäßige Verteilung :D ) -- dann könntest du die Bilder auch direkt verkleinern und Pixelweise vergleichen. Bei der von mir vorgeschlagenen Methode geht's ja darum, nicht zu viele Informationen durch Reduktion der Auflösung zu verlieren. Den Vergleich auf Zufallspixeln kannst du dann im Nachhinein immernoch "verstellen" indem du mehr oder weniger Pixel wählst, ohne dass du wieder alle Bilder in höherer Auflösung brauchst.

Zu dem vom Hellmapper:
Wenn man eine FFT auf ein Bild berechnet, dann bekommt man die Repräsentation des Bildes natürlich im Frequenzraum. Wenn du dann Frequenzen wegschneidest, stehst du zuerst mal vor der Frage: Welche? Beschneidest du einfach die Frequenzen ab einem gewissen Grad, dann verwäscht dein Bild und du verlierst Information, wenngleich auch der Vergleich dann sicher schneller geht. Vergleichst du dagegen alle Komponenten der Frequenzen miteinander, dürfte der Aufwand einem direkten Pixelvergleich recht nahe kommen.

Kompressionsartefakte schlagen sich übrigens gerade nicht in hohen Frequenzen nieder, sondern sie sind Resultat von fehlenden hohen Frequenzen. Wenn du ein JPEG mit hohem Grad komprimierst, dann werden die hohen Frequenzen nämlich weggeschnitten und es kommt zu Kanteneffekten entlang der Gradienten im Bild. Naja, solang du keine Rücktransformation machst um das Bild wieder zu speichern, sondern nur die FFT nutzt um dann Frequenzen in einem bestimmten Bereich zu vergleichen, könnte dir das trotzdem Erfolg bringen.

Klar, wenn man alle Frequenzen vergleicht, hat man nix gewonnen. Aber da bei jpgs ja die hohen Frequenzen rausgeschnitten werden, braucht man sie wohl auch nicht vergleichen.

Bei anderen Formaten mit anderen Kompressionsmethoden hat man hingegen tatsächlich wieder Informationsverlust, aber um den wird man, wenn es schneller gehen soll, nicht drumherum kommen. - oder man denkt sich noch ne andere Methode aus.

Zumidest glaube ich, würde mein Vorschlag die Anzahl an Falsepositives bei Comics gegenüber der Einzelpixelmethode reduzieren.

Es gibt 2 Möglichkeiten, eine Kristallkugel zu benutzen:
a) um damit Spekulationen über ein Problem eines Users zu machen und
b) um sie einem besonders unkooperativen User über den Schädel zu ziehen.
- bloggt jetzt auch selbst auf Sclavia.de

Mich wunderts das noch keiner SSIM in den Raum geworfen hat. Damit müsste sich das Problem der Bildähnlichkeit doch eigentlich sehr einfach (gibt ja schon fertige Implementationen) aus dem Weg räumen lassen. Die beiden Bilder müsste man zwar vorher auf eine Größe skalieren, aber das dürfte recht wenig ausmachen.

"[...] you're going to burn in a very special level of Hell. A level they reserve for child molesters and people who talk at the theater." - Book