Perzeptueller Hash: Suche nach ähnlichen Bildern

# Perceptual Hash: Wie Algorithmen ähnliche Bilder finden

Perceptual Hashing ermöglicht die Erkennung visueller Ähnlichkeiten zwischen Bildern, auch wenn sie in Größe, Farbe oder Kompressionsstufe unterschiedlich sind. Im Gegensatz zu kryptographischen Hashes wie SHA1 bewahren Perceptual Hashes Informationen über die Bildstruktur und sind robust gegenüber kleineren Modifikationen. Das macht sie unverzichtbar in Systemen zur Duplikatsuche, Inhaltserkennung und digitalen Forensik.

Grundlagen des Perceptual Hashing

Kryptographische Hash-Funktionen sind dafür ausgelegt, exakte Datenübereinstimmungen zu überprüfen: Schon die geringste Änderung in der Eingabedatei führt zu einem vollständig anderen Hash. Perceptual Hashes lösen ein anderes Problem – sie bleiben ähnlich bei visuell unbedeutenden Änderungen am Bild. Dieser Ansatz basiert darauf, dass die menschliche Wahrnehmung feine Details ignoriert und sich auf die Gesamtstruktur konzentriert.

Perceptual-Hashing-Algorithmen sind typischerweise:

• Robust gegenüber Änderungen in Größe und Seitenverhältnis;
• Invariant gegenüber Anpassungen von Helligkeit und Kontrast;
• Erhalten Ähnlichkeit bei leichter Kompression oder Rauschen;
• Schnell und skalierbar.

Um zwei Bilder zu vergleichen, werden ihre Hashes berechnet und dann die Hamming-Distanz gemessen – die Anzahl der unterschiedlichen Bits. Je kleiner die Distanz, desto größer die visuelle Ähnlichkeit.

Einfachste Methode: Average Hash

Einer der zugänglichsten Perceptual-Hashing-Algorithmen basiert auf Pixel-Mittelung. Er umfasst folgende Schritte:

• Resize auf 8×8 Pixel – das reduziert den Einfluss hochfrequenter Details drastisch.
• Umwandlung in Graustufen – beseitigt die Abhängigkeit von Farbkanälen.
• Berechnung der durchschnittlichen Helligkeit aller 64 Pixel.
• Binarisierung: Jedes Pixel wird durch 1 ersetzt, wenn seine Helligkeit über dem Durchschnitt liegt, und durch 0, wenn darunter.
• Erstellung eines 64-Bit-Hashs durch Aneinanderreihung der Bits (meist von links nach rechts, oben nach unten).

Diese Methode ist extrem schnell und wirksam zur Suche nach exakten oder nahezu exakten Duplikaten. Allerdings ist sie empfindlich gegenüber nichtlinearen Transformationen wie Gamma-Korrektur oder Histogrammänderungen, da sich der Durchschnitt verschiebt und viele Bits umkippen.

Verbesserter Ansatz: pHash auf DCT-Basis

Der pHash (perceptual hash) Algorithmus nutzt die diskrete Kosinustransformation (DCT), um sich auf die niederfrequency-Komponenten des Bildes zu konzentrieren – diese definieren die Gesamtstruktur. Die Schritte von pHash:

• Resize auf 32×32 Pixel – ausreichend für eine ordnungsgemäße DCT-Anwendung.
• Umwandlung in Graustufen.
• Anwendung der DCT auf das gesamte Bild (im Gegensatz zu JPEG, wo DCT auf 8×8-Blöcke angewendet wird).
• Extraktion des oberen linken 8×8-Blocks aus der resultierenden Frequenzmatrix – er enthält die niedrigsten Frequenzen.
• Berechnung des Durchschnitts dieser 64 Koeffizienten, wobei der erste (DC-Komponente) ausgeschlossen wird, um Abhängigkeit von der Gesamthelligkeit zu vermeiden.
• Binarisierung der Koeffizienten relativ zu diesem Durchschnitt.
• Erstellung eines 64-Bit-Hashs.

Dieser Ansatz ist deutlich robuster gegenüber Farb- und Helligkeitsverzerrungen. Selbst nach Gamma-Korrektur oder lokalen Änderungen (z. B. Hinzufügen eines Wasserzeichens auf einem kleinen Bildbereich) bleibt der Hash dem Original ähnlich nah.

Praktische Anwendungen und Einschränkungen

In realen Systemen wie TinEye oder internen digitalen Forensik-Tools werden oft mehrere Methoden kombiniert:

• Vorgefertigte Hashes für das gesamte Archiv;
• Schneller Average Hash für die erste Filterung;
• pHash oder andere fortschrittliche Algorithmen zur Verfeinerung;
• Zusätzliche Merkmale: Farbverteilung, Objektpositionen, Vorhandensein von Gesichtern.

Beispielsweise können in einem Gesichtserkennungssystem separate Hashes nur für Gesichtsbereiche berechnet werden, um die Genauigkeit in Porträt-Sammlungen zu verbessern.

Allerdings garantiert kein Perceptual Hash 100%ige Genauigkeit. Wesentliche Änderungen – wie das Ersetzen des Hintergrunds, Drehen um einen großen Winkel oder Tauschen zentraler Objekte – können Bilder visuell unterschiedlich wirken lassen, wobei Hashes dennoch nah beieinanderliegen oder umgekehrt.

Wichtige Punkte

• Perceptual Hash misst visuelle, keine bitweise Ähnlichkeit.
• Hamming-Distanz zwischen Hashes ist die primäre Methode zur Bewertung der Ähnlichkeit.
• Average Hash ist schnell, aber anfällig für nichtlineare Transformationen.
• DCT-basierter pHash bietet bessere Robustheit gegenüber Modifikationen.
• Industrielle Systeme nutzen Kombinationen von Methoden und Vor-Indexierung.

Methodenvergleich

| Kriterium | Average Hash | pHash (DCT) |

|------------------------|--------------|-----------------|

| Geschwindigkeit | Sehr hoch | Mittel |

| Rauschrobustheit | Mittel | Hoch |

| Gamma-Robustheit | Niedrig | Hoch |

| Speicherbedarf | Minimal | Mittel |

| Geeignet für Massensuche | Ja | Ja (mit Indexierung) |

Die Wahl der Methode hängt von der Aufgabe ab: Average Hash für exakte Kopien, pHash für modifizierte Bilder.

— Editorial Team