Doublettenerkennung bei Bildern

Forum for developers

Doublettenerkennung bei Bildern

Beitragvon Low012 » Sa Jan 29, 2011 6:19 pm

Bei mir ist es in der letzten Zeit öfter vorgekommen, dass ich bei der Bildersuche Doubletten in den Ergebnissen hatte, insbesondere wenn viele Ergebnisse von Wikipedia kamen. Ich habe daher mal einen einfachen, aber recht zuverlässigen Algorithmus entworfen und implementiert, um doppelte Bilder identifizieren zu können. Dabei soll es natürlich egal sein, wenn die Bildgröße geändert wurde, die Bilder unterschiedliche Kompressionsartefakte zeigen oder ähnliche, nicht besonders signifikante Unterschiede aufweisen.

Ich habe ein kleines Demoprogramm angehängt, das man auf ein Verzeichnis mit Bildern loslassen kann. Ich bin nicht sicher, welche Formate verarbeitet werden könne. JPEG und PNG funktionieren auf jeden Fall, TIFF nicht.

Das Programm wird gestartet mit:

java -jar DoubleDetect.zip /pfad/zu/bildern/

Der Pfad kann weggelassen werden. Es wird dann versucht, die Dateien im aktuellen Verzeichnis zu untersuchen. Die Ausgabe sieht dann z.B. so aus:
Code: Alles auswählen
[low012@localhost dist]$ java -jar DoubleDetect.zip /home/low012/Desktop/JAFFE/tmp/
/home/low012/Desktop/JAFFE/tmp/1294788595172s.jpg
/home/low012/Desktop/JAFFE/tmp/1294788595172.jpg

/home/low012/Desktop/JAFFE/tmp/KR.DI1.86.png

/home/low012/Desktop/JAFFE/tmp/clinton1.jpg
/home/low012/Desktop/JAFFE/tmp/clinton3.jpg
/home/low012/Desktop/JAFFE/tmp/clinton2.jpg

/home/low012/Desktop/JAFFE/tmp/KR.DI3.88.png

/home/low012/Desktop/JAFFE/tmp/KR.DI2.87.png

Wenn zwischen zwei Dateinamen keine Leerzeile steht, sind die Bilder gleich, sonst nicht.

Um den Algorithmus in YaCy nutzen zu können, wäre es wahrscheinlich gut, wenn man einen charakteristischen Wert für ein Bild im Index hinterlegen könnte. Zur Zeit bilde ich ein Byte-Array mit 192 Elementen. Es gibt zwei Möglichkeiten, mit weniger Elementen auszukommen, die ich aber beide noch nicht vollständig implementiert habe. Die eine kommt mit 128 Byte aus, die andere (ein bisschen aufwändiger) benötigt 104 Byte.

Bevor ich mehr Arbeit in das Ganze stecke, würde ich gerne eine Einschätzung haben, ob 128 oder 104 Byte zusätzlich pro Bild zu viel sind oder ob das vertretbar ist. Wenn man das Byte-Array benutzt, um gleiche Bilder erkennen zu können, könnte das auch weitere (positive) Folgen für die Bildersuche haben. Wenn ich weiß, dass Bild1 und Bild2 identisch sind und Bild1 mit WortA und Bild2 mit WortB verknüpft ist, dass müsste ja Bild1 auch was mit WortB und Bild2 was mit WortA zu tun haben.

Außerdem würde ich gerne hören, wie die Ergebnisse bei euch sind, wenn ihr einen Ordner mit Bildern und Doubletten anlegt. Ist die Erkennungsrate halbwegs OK? Ich habe nicht mit besonders vielen Bildern getestet.

Den Quellcode kann ich auch entweder ins SVN einchecken (wo passt sowas rein? oder neues Package aufmachen?) oder anderweitig zur Verfügung stellen.
Dateianhänge
DoubleDetect.zip
Umbenannte JAR-Datei.
(6.08 KiB) 145-mal heruntergeladen
Low012
 
Beiträge: 2214
Registriert: Mi Jun 27, 2007 12:11 pm

Re: Doublettenerkennung bei Bildern

Beitragvon Orbiter » Di Feb 01, 2011 2:46 am

Hallo Marc,

das ist eine tolle Sache. Sorry ich hatte bislang noch nicht die Zeit das auszuprobieren aber ich bin sicher wir sollten eine Bilderdoublettenerkennung in eine YaCy 2.0-Plaung einbauen. Ich hatte ja andererorts schon eine Skizze dazu gemacht und da nehme ich mir ja das Theme Dokumentensemantik vor. Dazu gehört dann wohl auch ein Ähnlichkeitsmaß.

Kann man denn die Ähnlichkeit der Bilder skalierend ausdrücken? Wie fehleranfällig ist das denn wenn es die Übereinstimmung der Bilder ausdrückt?

Bytegröße: im Prinzip denke ich dass irgendwo wieder ein 12-byte hash hin sollte. Den könnte man ja aus den 128 oder 104 byte berechnen, da ist es aber nicht so wichtig ob das nun 128 oder 104 byte sind. Wenn es geht lieber genauer. Das hier wären Daten die in die neue Metadatenstruktur rein kommen sollen, und das werden RDF Tripel in BLOBs sein. Also ist es nicht so wild wenn es ein paar bytes mehr werden.

Einchecken: momentan gibts möglicherweise noch keinen Ort wo man sagen könnte das es dort hin gehört. Das hier gehört m.E. nach in die Semantikkomponente des neuen Parsers nach YaCy 1.0 im Kontext von RDF und Jena.
Orbiter
 
Beiträge: 5796
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main

Re: Doublettenerkennung bei Bildern

Beitragvon Low012 » Di Feb 01, 2011 10:51 am

Also im Moment skaliere ich die Bilder auf 64 x 64 Pixel, wandle es in Graustufen um, mache eine Spreizung der Graustufen, so dass der volle Wertebereich von 256 Stufen abgedeckt wird und lege am Ende noch einen Weichzeichner drüber. Dann zerlege ich das Bild in 8 x 8 Pixel-Blöcke und berechne jeweils den minimalen, den maximalen und den Durchschnittswert, den ich dann noch durch 8 Teile (Wertebereich für Graustufen reicht dann nur noch von 0 bis 31).

Bei der Überprüfung auf Ähnlichkeit von zwei oder mehr Bildern vergleiche ich diese Werte und wenn da mehr als 1% der Werte eine Abweichung von über 1 haben, habe ich (nach ein bisschen Rumprobieren) festgelegt, dass die Bilder nicht gleich sein sollen.

Das ist eine sehr einfache Methode, aber sie funktioniert überraschend gut. Ich habe es u.a. mit Gesichts-Bildern von http://www.kasrl.org/jaffe.html getestet (erst in PNG umgewandelt), aber noch nicht systematisch. Ich müsste mal schauen, wie anfällig das Ganze wird, wenn man die Bilder z.B. stark komprimiert.

Blöd ist nur, dass ich die 3 Werte (min, max, Durchschnitt) für alle 64 Blöcke benötige, um die Ähnlichkeit zu überprüfen. Das sind eigentlich 192 Werte, wobei aber 3 Werte aber in 2 Byte passen. Da aber das Minimum immer kleiner ist als das Maximum und der Durchschnitt immer zwischen Minimum und Maximum liegt, gibt es nur eine begrenzte Anzahl von Kombinationen, die man durchnummerieren kann und dann nur noch 5 Bit für die 3 Werte benötigt. Vielleicht ist es ja möglich, die Genauigkeit für Minimum, Maximum und Durchschnitt noch weiter zu verringern und trotzdem brauchbare Ergebnisse zu bekommen. Vielleicht kann man dann auch nützliche 12-Byte-Hashs bilden.

Ich kann ja mal im Subversion einfach mal ein neues Verzeichnis neben "trunk" anlegen, in das solche Experimente rein können. Oder wird das dann zu unübersichtlich?

Ich würde auch noch gerne probieren, z.B. Gesichter auf Bildern zu erkennen oder sonst irgendwie Bilder automatisch in Kategorien einzuteilen.

Aber erstmal YaCy 1.0 abwarten... Da habe ich auch noch ein paar Dinge gefunden, die noch gefixt werden müssten. ;)
Low012
 
Beiträge: 2214
Registriert: Mi Jun 27, 2007 12:11 pm

Re: Doublettenerkennung bei Bildern

Beitragvon Low012 » Di Feb 01, 2011 3:02 pm

Ich habe eben mal kurz mit verschiedenen Versionen des Wikipedia-Logos getestet und dabei festgestellt, dass der Algorithmus dafür zur Zeit zu streng eingestellt ist. Vielleicht wäre es auch nützlich, große, einfarbige Flächen zu entfernen. Da werde ich noch ein bisschen testen müssen. Eventuell schreibe ich mir dafür mal einen automatischen Test, der unterschiedliche Einstellungen systematisch abarbeitet...
Low012
 
Beiträge: 2214
Registriert: Mi Jun 27, 2007 12:11 pm


Zurück zu YaCy Coding & Architecture

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron