PHP Ähnlichkeit von Bildern

Hallo zusammen,

gibts denn einen guten (und evtl. schnellen) Algorithmus, mit dem man den Bildinhalt hashen und aufbewahren kann, ähnlich MD5, SHA, ...? Ziel ist es doppelte Bilder (und Videos, aber die Vorschauen davon generier ich mir durch Movie Thumbnailer/ffmpeg) zu finden, ohne Bild für Bild vorgehen zu müssen. Die Hashes sollen dabei in eine DB, worauf ich mich dann jederzeit referenzieren kann.

Ne kurze Recherche hat bereits Perceptual Hash (bzw. pHash) zu Tage gebracht, was eigentlich auch bereits ganz i.O. ist, allerdings mit ner 32er Size bereits ein wenig dauert. Gibts da was Schnelleres/Besseres? Ne dicke Library oder ein Framework will ich nicht einbinden, am besten nur ne kleine Klasse dafür besitzen. Ggf. kann es auch irgend ein Binary in einer anderen Sprache sein, Windows (Host) oder Linux (VM) ist dabei egal.



LG

Hey Yuuri, leider habe ich überhaupt keine Ahnung von der ganzen Materie und stecke da nicht drin. Aber das einzige was mir spontan dazu einfiel war Base64 Codierung von Bildern, oder bringt dir das in diesem Fall gar nichts?

pHash klingt schon ganz gut, hast Du mal mit dessen verschiedenen Algorithmen rumgespielt? Das Haar-Wavelet dürfte eigentlich recht fix gehen.
(alternativ könntest Du natürlich versuchen, die zugrunde liegenden Algorithmen zu parallelisieren. Das müsste über eine GPU nämlich eigentlich nochmal deutlich schneller gehen.)

Du kannst Imagemagik verwenden

dort gibts a feature "Perceptual hash:"
und hier hast die erklärung wie das funktinoiert
http://www.fmwconcepts.com/misc_tests/perceptual_hash_test_results_510/index.html

vermutlich ist das eh der selbe Algorithmus, nur Imagemagick ist ein binary, wird also schneller sein als dein PHP code
(auserdem kannst das leicht verwenden)

Ich würde auch zu ImageMagick raten. Wenn man schon mit Bildern hantiert, ist es nicht unwahrscheinlich, dass man auch Metadaten auslesen oder Formate konvertieren oder resizen möchte.

Kanibal schrieb:

pHash klingt schon ganz gut, hast Du mal mit dessen verschiedenen Algorithmen rumgespielt?

Zum Vergrößern anklicken....

Nein, ehrlich gesagt hab ich nur versucht, mir mal nen Überblick zu verschaffen, kurz ne PHP-Klasse dafür gefunden und herumgespielt und wollte jetzt mal noch andere Meinungen einholen. Vielleicht gibts ja noch bessere Ansätze. Ich hab noch einiges von Wavelet-Transformationen gelesen, allerdings natürlich noch keinen Schimmer davon. So tief will ich eigentlich auch nicht einsteigen, ich will ja nur ne kleine Lib, die mir alle Arbeit abnimmt.

Auf das Perceptual Hashing bin ich dadurch gestoßen: http://bertolami.com/index.php?engine=blog&content=posts&detail=perceptual-hashing Sah sehr vielversprechend aus, nur leider ist dessen Lib (noch) nicht offen. Dadurch bin ich dann auf pHash gestoßen. Die gefundene kleine PHP-Klasse hat mir dann wie gewünscht mit dessen Methode einen Hash erzeugt.

Die Methode überzeugt an sich schon, allerdings hab ich beim Original plus die 50% Verkleinerung nur eine Übereinstimmung von 70 % (in der PHP-Klasse). Vielleicht sollte ich einfach mal das Tool von phash selbst verwenden und ein paar Tests fahren... Vielleicht auch selbst was draus stricken, allerdings sind meine C/C++-Skills ein wenig eingerostet.

@ the_nobs: Jap, von ImageMagick hab ich beim Überfliegen auch was gelesen. Allerdings gibt mir das wohl keinen Hash zurück (den müsste ich dann wohl selbst erstellen), welchen ich gern hätte, damit ich einfaches Bulk-Processing in einer DB machen könnte, ohne direkten Zugriff auf die Bilder zu haben bzw. ohne alles erneut zu vergleichen.

the_nobs schrieb:

vermutlich ist das eh der selbe Algorithmus, nur Imagemagick ist ein binary, wird also schneller sein als dein PHP code

Zum Vergrößern anklicken....

pHash ist auch eine C++ Binary (sogar zusätzlich mit C-Bindings zu bsp. PHP).

Kanibal schrieb:

pHash ist auch eine C++ Binary (sogar zusätzlich mit C-Bindings zu bsp. PHP).

Zum Vergrößern anklicken....

Hiermit nehme ich alles zurück und behaupte das gegenteil :-)

@Yuuri: kannst du auch in Imagemagick, must halt mit den input/output des consolen programms arbeiten
es gibt afaik auch PHP bindings für Imagemagick damit du entsprechende aufrufe direkt machen kannst.

Nach dem was ich gesehen habe gibt es kein PHP:Imagick für die PHash-Schnittstelle. Imagick kann eh nicht alles, was Konsolen-ImageMagick kann.

ähhh
direkt im PHP Manual
http://php.net/manual/de/book.imagick.php

Soweit ich das verstanden habe, ist Imagick eine alternative zur GD funktionalität von PHP und hat mit Imagemagick nur ursprünglich was zu tun.

the_nobs schrieb:

Soweit ich das verstanden habe, ist Imagick eine alternative zur GD funktionalität von PHP und hat mit Imagemagick nur ursprünglich was zu tun.

Zum Vergrößern anklicken....

Wenn du schon verlinkst, dann lies auch...
Imagick is a native php extension to create and modify images using the ImageMagick API.

NATÜRLICH ist es eine Alternative zu GD. Beide Bibliotheken bearbeiten Bilder. Imagick hat nur eben den deutlich größeren Funktionsumfang. Aber, wie ich schon sagte, kann PHP::Imagick nicht alles, was das Shell-Command kann. Manches geht hingegen zwar, ist aber krüppelig-umständlich.

@Daaron: hiermit nehme ich alles zurück und behaupte das Gegenteil :-)

Google und Co. verwenden da einen Algorithmus von Microsoft zum Vergleich von Bildern mit bekannten KiPo-Bildern, so wurde vor ein paar Woche auch der Pädophile mit seinem Gmail-Konto mit KiPo-Bildern erkannt.

Ich kann nur gerade keine größere Suche durchführen (bin unterwegs), das wäre vllt aber noch ein möglicher weiterer Algorithmus der ja auch in der Praxis eingesetzt wird - also nicht zu langsam sein kann.

Guter Einwand, allerdings hab ich jetzt nur (durchaus treffende) Schätzungen gefunden. Wobei Google auch eher weniger einen Algorithmus nutzt, sondern je nach Option bzw. auch gleich mehrere.

http://googleblog.blogspot.de/2009/10/similar-images-graduates-from-google.html
http://www.quora.com/What-is-the-algorithm-used-by-Google-Search-by-Image-1
http://en.wikipedia.org/wiki/Scale-invariant_feature_transform
http://en.wikipedia.org/wiki/Content-based_image_retrieval



Aber mal ne andere Frage: Mir wird gerade ne Exception um die Ohren gehauen beim Löschen des Speichers.

In der Lib heißt es (N ist fix auf 72 gesetzt)
Und auf ein malloc(), muss ich ja mit einem free() antworten. Zur besseren Handhabung, stopf ich mir das Array einfach in einen std::vector.
Beim free() krachts hier allerdings. Überseh ich irgendwas? In C hab ich bisher kaum Erfahrung... Lass ich das free() weg, funktionierts natürlich, aber ich hab n Speicherleck...

Gibt es für die Google Bildersuche keine API? Würd mich wundern :O

Geht es dir darum binär identische Bilder zu vermeiden? Dann wäre etwas schnelles wie md5 doch super.
Allerdings schreibst du:

Die Methode überzeugt an sich schon, allerdings hab ich beim Original plus die 50% Verkleinerung nur eine Übereinstimmung von 70 % (in der PHP-Klasse)

Zum Vergrößern anklicken....

Das klingt so also soll das ganze unabhängig vom gewählten Kompressions-Algorithmus, von dessen parametern und evtl auch noch von der Bildgröße arbeiten.
Das ist wirklich beliebig kompliziert. Du wirst hier immer nur mit einer gewissen Wahrscheinlichkeit antworten können und dich trotzdem oft täuschen mit false-positive und false-negative.

Eines der schnellsten und auch noch sehr DB freundlichen Bild-Vergleichs-Verfahren sind (Hu-)Momente auf Graustufenbildern:
http://de.wikipedia.org/wiki/Moment_(Bildverarbeitung)
OpenCV liefert auch direkt eine C(++) Implementation:
http://docs.opencv.org/doc/tutorials/imgproc/shapedescriptors/moments/moments.html
http://docs.opencv.org/modules/imgp...pe_descriptors.html?highlight=moments#moments

Der Vorteil hier wäre, dass du zu allen bekannten Bildern nur die Momente (8 Zahlen) speicherst und beim aktuell neuen daher nur mittels des Ähnlichkeitsmaßes über alle bekannten Bilder iterieren musst und nicht bzgl. der Bildinhalte.

Aber auch hier tut sich ein extrem kompliziertes Problem auf, was auch bei allen anderen Feature-Basierten Verfahren existiert:
Wenn du eine gigantisch große Datenbank hast und daher aus Zeitgründen nicht immer zu allen Bildern die Distanz berechnen kannst, musst du an deine Datenbank eine Art Fuzzy-Anfrage stellen können.
Also zB kennt deine DB die Bilder mit den Momenten
1: 1,1,1,1,1
2: 5,6,7,8,9
3: 8,7,6,5,4
und ein neues hat nun 2,1,1,1,1.
Die Distanz wird sicherlich zu Bild1 gering genug sein um es als "Duplikat" zu entlarven aber woher weißt du, dass dieser "ähnliche" Eintrag in deiner DB vorhanden ist, ohne alles durchsuchen zu müssen?
Jedes Moment ist quasi eine Dimension und die DB ist eine Punktwolke. Du willst jetzt bei einem beliebigen Punkt im Raum wissen, ob ein Punkt der Wolke "nah genug" ist, ohne zu jedem Punkt der Wolke zu messen.
Wenn du deine DB Dimensionsweise sortiert vorhalten kannst, könnte man die Dimensionen nacheinander abfragen:
m1=2 wird gesucht, dh wir suchen nur Einträge mit m1 1 bis 3.
m2=1 wird gesucht, dh wir suchen nur Einträge mit m2 0 bis 2.
..
Davon dann die Schnittmenge

edit: normalerweise guck ich ja in