Oder so ähnlich
Maschinelles „Sehen“ ist ein Forschungsgebiet mit vielen Anwendungen – von der Gesichtserkennung bis hin zu autonomen Fahrzeugen. Für Aufgaben wie das Vergleichen von Bildern muss man jedoch gar nicht tief in die mathematisch-algorithmische Trickkiste greifen.
- Michael Riepe
Den Aufmacher hatten wir schon mal,“ sagt die Kollegin. Kurze Zeit später fördert sie den alten Artikel zutage. Tatsächlich ähneln sich die Bilder frappierend: Motiv und Komposition sind identisch, lediglich die Farbgebung unterscheidet sich.
Was der Kollegin leichtfällt, ist für den Computer ungleich schwerer – aber nicht unmöglich. Der Bildbetrachter geeqie etwa kann ähnliche Bilder auf der Festplatte aufspüren und anzeigen (siehe Onlinequellen [a]). TinEye findet Bilder im Internet [b]. Google bietet die Funktion ebenfalls, wenn auch etwas versteckt: Klickt man in der Bildsuche auf das Kamerasymbol im Suchfeld, kann man ein Bild hochladen und bekommt als Resultat Webseiten angezeigt, die das Bild enthalten, sowie eine Auswahl ähnlicher Bilder.
Ähnlichkeit ist relativ
Wer das mit seinem eigenen Konterfei probiert, wird allerdings enttäuscht: Zwar findet Google ähnlich aufgebaute Porträts, doch in der Regel keine ähnlichen Gesichter. Der verwendete Algorithmus vergleicht die Bildstruktur, nicht die Details.
Dahinter steckt eine Technik, die sich Perceptual Hashing nennt. Sie reduziert das Bild auf wesentliche (optische) Merkmale und berechnet daraus einen digitalen Fingerabdruck (Hash). Anders als bei kryptografischen Hash-Funktionen, wo kleine Änderungen an den Daten zu völlig anderen Hash-Werten führen, haben leichte Modifikationen beim Perceptual Hashing keine oder nur geringe Auswirkungen auf den Hash-Wert; man spricht daher auch von Robust Hashing. Bilder mit ähnlichen Merkmalen besitzen ähnliche oder sogar identische Fingerabdrücke.
Das klingt kompliziert, doch im Grunde kann es sehr einfach sein, wie Neal Krawetz in seinem Blog „The Hacker Factor“ erklärt [c]: Man skaliert das Bild auf 8 x 8 Pixel, konvertiert es in Graustufen-Darstellung und vergleicht die Helligkeit der einzelnen Pixel mit der des Gesamtbildes. Hellere Pixel bekommen eine Eins, dunklere eine Null – fertig. Als Maß für die Ähnlichkeit zweier Bilder eignet sich die Hamming-Distanz [d] ihrer Fingerabdrücke, die sich leicht durch eine xor-Verknüpfung der Fingerabdrücke und Zählen der Einsen berechnen lässt.
Bereits dieses einfache Verfahren hätte vermutlich die Ähnlichkeit der beiden Aufmacher festgestellt. Schwieriger wird das, wenn jemand eins der beiden Bilder leicht modifiziert hat, etwa die Ränder abgeschnitten und das Bild aufgehellt. Die Bibliothek libpuzzle verwendet einen etwas komplexeren Algorithmus, der in solchen Fällen bessere Resultate liefert [e]. Er legt ein Gitternetz über das Bild und vergleicht quadratische Bereiche um die Kreuzungspunkte herum mit ihren acht Nachbarn. Wer ein wenig Mathematik nicht scheut, findet eine genaue Beschreibung des Verfahrens im Netz [f].
Mehr mathematischen Aufwand treiben die in pHash umgesetzten drei Algorithmen [g]. ph_dct_imagehash verwendet die Helligkeitsinformationen nicht direkt, sondern unterzieht das Bild zunächst einer Diskreten Kosinustransformation (Discrete Cosine Transformation, DCT) und erzeugt daraus den 64 Bit langen Fingerabdruck. Als Maß für die Ähnlichkeit dient die Hamming-Distanz, die sich mit ph_hamming_distance berechnen lässt.
Statt der DCT verwendet ph_mh_imagehash eine Wavelet-Transformation mit dem Marr-Wavelet [h], die die Kanten unterschiedlich heller Bereiche extrahiert. Die resultierenden Fingerabdrücke sind 576 Bit lang und lassen sich mit ph_hammingdistance2 vergleichen. Allerdings ist der Algorithmus nur gut halb so schnell wie der DCT-basierte. Der gehört ebenfalls nicht zu den flottesten: libpuzzle benötigt nur rund ein Drittel der Zeit.
Fast so schnell wie libpuzzle arbeitet ph_image_digest. Der Algorithmus legt 180 Linien in unterschiedlichen Winkeln durch den Bildmittelpunkt und extrahiert dessen geometrische Merkmale mit einer Radon-Transformation [i]. Anschließend unterzieht es das Ergebnis – den Feature-Vektor – einer DCT und errechnet daraus den 320 Bit langen Fingerabdruck. Die zugehörige Vergleichsfunktion ph_crosscorr ist allerdings deutlich komplexer als die übrigen: Sie berechnet die Kreuzkorrelationsfunktion beider Hashes [j]. Deren Maximalwert zeigt an, wie ähnlich sich die beiden Bilder sind.
Alle Links: www.ix.de/ix1301163 (mr)
