Hachages perceptuels ou comment rechercher dans les images (Part 1: Généralités)
Introduction
Empreintes digitales, reconnaissance faciale, scanner rétinien. Ces dernières années ont vu l’émergence de technologies biométriques dans les systèmes de sécurité informatique. Et aussi dans les entreprises dans le but par exemple de vérifier la ponctualité des employés. Face ID est sûrement la grande star de l’époque dans le domaine de la biométrie. En effet, Apple a mis la barre très haut avec son système de reconnaissance faciale ultra-fiable et déployé à l’échelle du milliard d’utilisateurs. Dans cette série d’articles, nous nous bornerons à présenter les hachages perceptuels, ainsi qu’une application de ces derniers pour des tâches telles que la reconnaissance faciale.
C’est quoi un hachage perceptuel ?
Les fonctions de hachage en informatique permettent de transformer un lot de données hétérogènes vers un type plus compact et de taille fixe : les hash. En général, une bonne fonction de hachage doit limiter au maximum les collisions. On en trouve souvent, mais c’est extrêmement difficile (probabilité quasi-nulle) surtout pour les fonctions de hachage cryptographique de dernière génération comme le SHA-512. En effet, pour un hachage cryptographique, deux valeurs initiales extrêmement proches doivent produire des hachages complètement différents et très peu similaires ; pour qu’un pirate informatique ne puisse pas deviner la valeur encodée juste en étudiant sa structure.
Ce type de hachage est très utilisé en sécurité informatique. Mais il existe des fonctions de hachage où le comportement inverse est souhaité. C’est à dire que, pour deux valeurs de départ très proches, on souhaite obtenir des valeurs hachées très proches. Ce type de fonctions font en fait partie d’une famille de fonctions en mathématiques appelées fonctions de hachages sensibles à la localisation : la famille de fonctions LSH (Locality Sensitive Hashing). Une fonction est dite LSH lorsque pour deux éléments de départ très proches (similaires), les valeurs hachées produites sont également très similaires vis à vis de l’espace de départ ; inversement, des valeurs très éloignées dans l’espace de départ doivent également produire des hachages éloignés dans l’espace considéré.
La famille des fonctions LSH est très nombreuse. Nous produirons sûrement un article pour les définir de manière plus formelle et décortiquer quelques fonctions particulières de cet ensemble. Pour cet article, nous nous bornons à une présentation non formelle des hachages perceptuels. Vous l’aurez compris, les hachages perceptuels font parti de cette famille d’algorithmes. Ils permettent d’encoder des données de manière à sauvegarder leur aspect tel que perçu par nos sens. En effet, les hachage de deux images similaires par cette méthode produira deux codes très proches conformément à l’espace métrique de la fonction (la distance dans l’espace des deux hash sera quasi-nulle).
Pourquoi avons-nous besoin des hachages perceptuels ?
Prenons deux images et essayons de les comparer afin d’en définir la similitude. Nous souhaitons par exemple détecter les doublons dans un dossier de photos afin de libérer de l’espace. Une comparaison pixel par pixel fonctionnerait dans le cas d’images parfaitement similaires. Mais qu’adviendra-t-il si les deux images sont prises sous un angle différent ? Et si deux images étaient similaires mais n’avaient pas la même dimension ? De plus, dans une grande base de données et avec des images de très haute résolution, on risque ne jamais en finir à cause l’explosion combinatoire due à la très haute dimensionnalité de l’espace de travail. Bref, vous l’aurez compris, nous avons d’une méthode efficace. C’est là qu’entrent en jeu nos amis de la famille LSH. Ils vont nous permettre de créer des versions compactes et résistantes au bruit (luminosité, compression, rotations etc. dans le cas des images) de nos images et de faire des recherches et comparaisons plus rapides.
Conclusion
J’espère que cet article vous a plu et qu’il vous a permis de comprendre empiriquement la notion de hachages perceptuels. Si c’est le cas, n’hésitez pas à le recommander. Dans la partie 2, nous verrons différents types d’algorithmes ainsi que des implémentations en langage python. D’ici là, portez vous bien. Merci de m’avoir lu.
