Les fonctions de hachage sont fort pratiques pour comparer des fichiers : à partir de données fournies en entrée, elle génère une empreinte de taille fixe. La plupart des fonctions de hachage sont conçues pour varier complètement au moindre changement. Si les signatures diffèrent, les documents seront différents. Fort pratique pour certifier que le contenu d'un fichier n'a pas bougé, mais il est parfois plus pertinent de s'intéresser à ce que l'on perçoit du document, et pas uniquement de la suite de bits qui le compose. Les outils de compression destructifs, comme le JPEG pour les images, ou le MP3 pour le son, promettent à réglage similaire, un résultat perçu comme similaire. Par contre, au niveau des octets du fichier, rien n'est garanti. Le même souci apparait pour un même média enregistré dans différents formats de fichiers.
Prenons le cas des images, qui est, euh, plus visuel.
Une photo peut être redimensionnée, ses couleurs corrigées (les balances des blancs, le contraste par exemple), l'horizon remis d'aplomb. Les possibilités sont variées, et en ajoutant les histoires de formats et de compression, on est sûr de ne pouvoir comparer les octets des fichiers. Plutôt que de jouer au Memory avec des millions d'images, il est possible d'utiliser une fonction de hachage spécifique, se basant sur la perception, et qui changent peu si la différence entre deux images est faible.
Le Dr Neal Krawetz a fait des recherches intéressantes dans ce domaine : http://www.hackerfactor.com/blog/?/archives/529-Kind-of-Like-That.html. Il teste différentes approches, pour finalement constater qu'il existe une méthode simple et efficace : la variation de luminance.
Son algorithme nommé dHash est simple à comprendre et à mettre en oeuvre, un parfait exemple pour découvrir Numpy.
L'image, en niveau de gris, est redimensionnée à une taille de 8 * 9 pixels, on compare chaque pixel avec son voisin de droite, s'il est plus clair, on obtient un 1, sinon, c'est un 0. La première colonne servant à amorcer, on obtient un mot de 64 bits, taille plus que raisonnable. Pour comparer deux images, on se contente de compter le nombre de bits différents : la distance de Hamming. Une distance de 0 indique deux images similaires, à partir de 10, c'est complètement différent. Une distance de 2 est une valeur raisonnable, en fait.
Numpy travaille avec des vecteurs
Pour comprendre le code, voici une présentation express de la vectorisation de Numpy.
numpy est aliasé en np, c'est une tradition.
In [1]: import numpy as np
Une suite de 0 à 7.
In [2]: np.arange(8)
In [3]: a
Out[4]: array([0, 1, 2, 3, 4, 5, 6, 7])
8 entiers, de 0 à 5.
In [5]: b = np.random.random_integers(0, 5, 8)
In [6]: b
Out[6]: array([4, 4, 5, 1, 5, 0, 1, 1])
Il est possible d'effectuer une opération entre un vecteur et un objet.
In [7]: b > 3
Out[7]: array([ True, True, True, False, True, False, False, False], dtype=bool)
Comparaison un à un, des éléments des deux listes.
In [8]: c = a > b
In [9]: c
Out[9]: array([False, False, False, True, False, True, True, True], dtype=bool)
On peut utiliser un vecteur de booléen pour piocher dans un autre vecteur
In [10]: d = np.array([128, 64, 32, 16, 8, 4, 2, 1, 0])[c]
In [11]: d
Out[11]: array([16, 4, 2, 1])
In [12]: d.sum()
Out[12]: 23
Implémenter dhash avec Numpy
Skimage propose tout ce qu'il faut pour manipuler des images. Les besoins techniques de cet exemple sont très simples : conversion d'une image en niveau de gris et redimensionnement.
import numpy as np
from skimage.transform import resize
from skimage.color import rgb2grey
Chaque ligne de 8 pixels est représentée par 8 bits, représentés par un uint8. Il y a 8 lignes, soit 64 bits: un uint64.
TWOS = np.array([2 ** n for n in range(7, -1, -1)])
BIGS = np.array([256 ** n for n in range(7, -1, -1)], dtype=np.uint64)
def dhash(picture):
"Compute dhash as uint64."
img = rgb2grey(resize(picture, (9, 8))) # a small grey picture
h = np.zeros([8], dtype=np.uint8)
for a in range(8):
h[a] = TWOS[img[a] > img[a + 1]].sum()
return (BIGS * h).sum()
Calcul par lot de la cardinalité avec des opérations de type bit offset et booléene.
def ncardinality(array):
"Cardinality of an array of any kind of int"
c = np.zeros([len(array)], dtype=int)
for n in range(array.dtype.itemsize * 8):
c += array >> n & 1
return c
Toujours l'approche par lot. Les hashs de l'ensemble des images sont modélisés par une array de uint64. Il faut prévoir une boucle pour gérer une demi-matrice, pour comparer les images entre elles.
def compare(all, reference, thresold=4):
"""
Compare reference picture with all others.
Return ranks of similar hash, and its scores.
"""
diff = all ^ reference # XOR
c = ncardinality(diff)
small = c <= thresold # Less differences than thresold.
rank = np.arange(len(all)) # Enumerate hashes
if small.any():
return rank[small], c[small]
En préparant la liste des hashs, et en les stockant sur disque, la comparaison de 5600 images prend 20s, sur une machine peu agressive. Un gros 15 millions de comparaisons, soit 1.3 µs par comparaison.
L'algorithme fonctionne bien, il est simple et rapide, mais il est conçu pour des photos. Sur des illustrations avec de gros aplats, comme un objet au milieu d'un fond uni, il génère beaucoup de faux positifs.
Avant de changer d'approche radicalement, il est possible de tuner, en diminuant le seuil de comparaison, en augmentant la résolution (8 pixels de côté, c'est quand même petit).
La variante à deux dimensions, 64 bits pour les variations verticales, 64 bits pour les variations horizontales (une passe, tourner l'image de 90°, une autre passe), doit améliorer sensiblement la pertinence pour les photos, mais ne doit pas résoudre grand-chose aux problèmes des aplats.
Pour ne pas trop brimer les performances, il est possible de commencer par un tri à base de dhash, puis de vérifier les résultats avec un autre algo plus complexe.
