Testen verschiedener Bild Hashfunktionen
Für die Image-ID-Komponente des ISCC – also die Content-ID von Bilddateien – brauchen wir eine Hashfunktion, die bei kleinen Änderungen einen gleichen, beziehungsweise möglichst ähnlichen Hash erzeugt, dabei jedoch wenig ungewollte Kollisionen verursacht.
Anforderungen
Im Sinne einer generischen Einsatzfähigkeit des ISCC legen wir Wert darauf, einen Algorithmus zu finden, der eine geringe Laufzeit zur Berechnung des Hashes aufweist und einfach zu implementieren ist. Bei Bildern kann die Laufzeit schnell aus dem Ruder laufen. Ein Bild der Größe 1920×1080 hat beispielsweise 2.073.600 Pixel, die alle verarbeitet werden müssen. Um die Auswahl an geeigneten Hashfunktionen weiter einzugrenzen haben wir festgelegt, gegen welche Bildänderungen unser Hash idealerweiser robust sein soll:
Sollte robust sein gegen:
- Änderung der Helligkeit (5% – 20%)
- Änderung des Kontrasts (5% – 20%)
- Gammakorrektur
- Wasserzeichen
- JPEG Kompression (5% – 20%)
- Skalierung (50% – 300%)
- Graustufen
Sollte teilweise robust sein gegen:
- Salt and Pepper
- Multiplicative noise
- Zuschneiden (1% – 5%)
- Gauß-Glättung (5% – 20%)
- Farbanpassungen
Muss nicht robust sein gegen:
- Rotation
- Verzerrung
Mögliche Hashfunktionen
Abgesehen vom Block Hash sind alle Hashfunktionen von uns implementiert worden, und wir benutzen abgesehen von PIL keine fremden Bibliotheken. PIL benutzen wir zum einen, um die Bilder in Graustufenbilder zu konvertieren; PIL verwendet nach eigenen Angaben hierfür die ITU-R 601-2 luma Transformation. Zum anderen verwenden wir PIL zum Skalieren der Bilder, welches hier beschrieben wird; wir nutzen zum Resamplen die bikubische Interpolation, welche hier beschrieben wird.
Das in diesem Dokument verwendete Beispielbild stammt von Morguefile.com.
Average Hash
Der Average Hash berechnet zuerst aus dem Eingabebild ein Graustufenbild und verkleinert es daraufhin. Da wir einen 64 Bit Hash erzeugen wollen, wird das Bild in unserem Fall auf ein 8×8 Bild verkleinert.
Dann wird der Durchschnitt aller Grauwerte des Bildes berechnet und die Pixel werden reihenweise von links nach rechts betrachtet; ist der Grauwert größer als der Durchschnitt wird eine 1, andernfalls eine 0 zum Hash hinzugefügt.
Hash: 0000000000010000000000000010000001000010100001101111111111111110
Blockhash
Der Blockhash teilt das Bild in Blöcke und berechnet zu jedem Block einen Wert, entweder 1 oder 0. Diese werden reihenweise von links nach rechts zu einem Hash zusammengefügt. Da wir einen 64 Bit Hash brauchen, teilen wir das Bild in 64 Blöcke ein.
Da der Blockhash das Bild weder in ein Graustufenbild umwandelt noch das Bild verkleinert, war er anfangs, vor allem bei größeren Bildern, recht langsam. Dieses Problem konnten wir jedoch beheben, indem wir das Eingabebild auf ein Bild der Größe 256×256 skaliert haben. Dadurch hat jeder Block noch immer 16 Pixel, aber die Laufzeit wurde erheblich verbessert. Zudem haben wir erst aus jedem Bild ein Grauwertbild berechnet.
Hash: 0011100010011100000011100110001101000011100001110100001011100110
Difference Hash
Der Difference Hash berechnet ähnlich wie der Average Hash zunächst aus dem Eingabebild ein Graustufenbild und verkleinert dieses dann, in unserem Fall in ein Bild der Größe 9×8. Von jeder Reihe werden die ersten 8 Pixel reihenweise von links nach rechts betrachtet und mit ihrem rechten Nachbarn verglichen, woraus sich analog zum Average Hash ein 64 Bit Hash ergibt.
Hash: 1111000000110000101110001100111010000110010011001000111010001110
Median Hash
Der Median Hash funktioniert ähnlich wie der Average Hash, nur, dass nicht mit dem Durchschnitt sondern mit dem Median verglichen wird.
Hash: 0000000010011100000011000110001101000010100001111111111111111111
Perceptual Hash
Auch der Perceptual Hash berechnet zuerst das Grauwertbild und verkleinert dieses dann. In unserem Fall wollten wir einen Faktor von 4, weswegen wir auf ein 8*4×8*4 also ein 32×32 Bild verkleinert haben.
Auf diesem Bild führen wir nun die Diskrete Kosinustransformation durch, erst reihenweise, dann spaltenweise.
Diskrete Kosinustransformation: 
Die Pixel mit hohen Frequenzen liegen nun oben links, weswegen wir das Bild auf die oberen linken 8×8 Pixel zuschneiden. Dann berechnen wir den Median der Grauwerte in diesem Bild und bilden analog zum Median Hash einen Hashwert aus dem Bild.
Hash: 1010010010101101100110011011001101100010100100000111011010101110
Wavelet Hash
Der Wavelet Hash berechnet ebenfalls aus dem Eingabebild analog zum Average Hash ein Grauwertbild der Größe 8×8. Dann wird auf dem Bild eine zweidimensionale Wavelet Transformation ausgeführt. Unsere Tests haben ergeben, dass die Ergebnisse besser werden wenn wir 3 mal die oberste Reihe auf 0, also schwarz, setzen und die Wavelet Transformation erneut ausführen; diese Idee haben wir aus einer der Imagehash Bibliothek imagehash.
Dann wird analog zum Perceptual Hash jeder Pixel mit dem Median verglichen und der Hash wird berechnet.
Hash: 0000010110111001111110011111101111111010000000000000011100000101
Den Blockhash haben wir aus der Bibliothek blockhash-python, Average Hash, Difference Hash, Perceptual Hash und Wavelet Hash haben wir in Anlehnung an die Bibliothek imagehash implementiert und den Median Hash haben wir selbst entwickelt.
Unsere Tests
Wir haben die Hashfunktionen gegeneinander getestet mit der Bilddatenbank Caltech101, welche 9143 Bilder enthält. Zu jedem Bild haben wir jeweils 10 Testbilder mit leichten, randomisierten Änderungen erstellt.
Wir haben:
- Die Helligkeit erhöht und verringert
- Den Kontrast erhöht und verringert
- Ein Wasserzeichen eingebaut
- Es in ein Graustufenbild umgerechnet
- Es kleiner skaliert
- Den Rand abgeschnitten
- Es mit einer Gauß-Glättung versehen
- Eine JPEG-Kompression durchgeführt
Dadurch haben wir 100.584 Testbilder erhalten. Dann wurden zu jedem Bild die verschiedenen Hashes berechnet und zusammen mit der Bildnummer und der Fehlerart auf einem ElasticSearch Index gespeichert.
Wir haben zu jedem Hash drei verschiedene Tests durchgeführt:
- Nach Bild gruppiert und gezählt, zu wie viele Bilder ein anderer Hash als das Originalbild berechnet wurde.
- Nach Bild gruppiert und die durchschnittliche Hamming Distanz vom Hash eines veränderten Bildes zum Originalbild berechnet.
- Nach Hash gruppiert und gezählt wie viele Kollisionen es gab, also wie viele Bilder den gleichen Hash zugeordnet bekamen, obwohl sie nicht zum gleichen Originalbild gehören.
Ergebnisse
Anderer Hash als das Originalbild
| Fehlerart | aHash | bHash | dHash | mHash | pHash | wHash |
| Gauß-Glättung | 1828 (20,0%) | 1241 (13,6%) | 3807 (41,6%) | 2122 (23,2%) | 786 (8,6%) | 971 (10,6%) |
| Graustufen | 0 (0%) | 0 (0%) | 0 (0%) | 0 (0%) | 0 (0%) | 0 (0%) |
| Helligkeit erhöht | 3874 (42,4%) | 3206 (35,1%) | 5357 (58,6%) | 3451 (37,7%) | 3986 (43,6%) | 2844 (31,1%) |
| Helligkeit verringert | 1717 (18,8%) | 809 (8,8%) | 4935 (54,0%) | 2115 (37,7%) | 1030 (11,3%) | 1420 (15,5%) |
| JPEG Kompression | 455 (5,0%) | 598 (6,5%) | 1616 (17,7%) | 658 (7,2%) | 546 (6,0%) | 514 (5,6%) |
| Kontrast erhöht | 2559 (28,0%) | 2062 (22,6%) | 4568 (50,0%) | 2474 (27,1%) | 2460 (26,9%) | 2197 (24.0%) |
| Kontrast verringert | 2056 (22,5%) | 766 (8,4%) | 5223 (51,1%) | 2154 (23,6%) | 1063 (11,6%) | 2026 (22,2%) |
| Skaliert | 554 (6,1%) | 1297 (14,2%) | 2091 (22,9%) | 851 (9,3%) | 664 (7,3%) | 614 (6,7%) |
| Wasserzeichen | 3600 (39,4%) | 5046 (55,2%) | 7167 (78,4%) | 4029 (44,1%) | 4242 (46,4%) | 2896 (31,7%) |
| Zugeschnitten | 8543 (93,4%) | 8750 (95,7%) | 9075 (99,2%) | 8514 (93,1%) | 9088 (99,4%) | 7840 (85,7%) |
| Gesamt | 25.186 (25,0%) | 23.775 (23,6%) | 43.839 (43,6%) | 26.368 (26,2%) | 23.865 (23,7%) | 21.322 (21,2%) |
Durchschnittliche Hamming Distanz
| Fehlerart | aHash | bHash | dHash | mHash | pHash | wHash |
| Gauß-Glättung | 0,24 | 0,31 | 0,61 | 0,31 | 0,17 | 0,20 |
| Graustufen | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 | 0,00 |
| Helligkeit erhöht | 0,81 | 1,22 | 1,28 | 0,94 | 1,14 | 0,68 |
| Helligkeit verringert | 0,24 | 0,20 | 1,15 | 0,48 | 0,23 | 0,31 |
| JPEG Kompression | 0,06 | 0,13 | 0,21 | 0,10 | 0,12 | 0,10 |
| Kontrast erhöht | 0,38 | 0,60 | 0,84 | 0,43 | 0,58 | 0,52 |
| Kontrast verringert | 0,29 | 0,59 | 0,84 | 0,48 | 0,23 | 0,52 |
| Skaliert | 0,07 | 0,34 | 0,28 | 0,12 | 0,15 | 0,12 |
| Wasserzeichen | 0,64 | 2,46 | 2,51 | 1,30 | 1,06 | 0,67 |
| Zugeschnitten | 4,11 | 6,02 | 6,23 | 4,69 | 7,47 | 2,98 |
| Gesamt | 0,68 | 1,14 | 1,44 | 0,88 | 1,12 | 0,61 |
Kollisionen
| Hash | Kollisionen |
| aHash | 4438 |
| bHash | 711 |
| dHash | 421 |
| mHash | 4432 |
| pHash | 483 |
| wHash | 7866 |
Wir haben auch versucht, die Hashes mit AND, OR, XOR oder einem Similarity Hash zu verbinden, die Ergebnisse waren jedoch maximal so gut wie die des Besten der verbunden Hashes.
Laufzeiten
| Hash | Durchschnittliche Laufzeit pro Bild |
| aHash | 2,25 ms |
| bHash | 112,70 ms |
| dHash | 0,33 ms |
| mHash | 0,33 ms |
| pHash | 60,05 ms |
| wHash | 0.91 ms |
Da der Perceptual Hash bei den Gesamtabweichungen und der durchschnittlichen Hamming-Distanz gute Ergebnisse hatte, dabei wenig ungewollte Kollisionen erzeugt hat und doppelt so schnell war wie der Block Hash haben wir uns für den Perceptual Hash entschieden.
