Retrouver deux fois la même image

Demandez à une bibliothèque de 200 000 photographies si elle contient déjà l’image que vous avez sous les yeux : la réponse dépend de ce qu’on appelle « la même image ». Le fichier peut avoir été réencodé, redimensionné, étalonné ou recadré, si bien que ses octets ne correspondent plus, alors qu’une personne reconnaîtrait la photographie d’origine.

Cet article est le deuxième d’une série sur la recherche d’images. Le premier traitait du chemin textuel : construire un document interrogeable, fusionner BM25 et pgvector, gérer les plafonds de candidats. Celui-ci écarte le texte du problème et s’appuie sur un autre index, dans la même instance PostgreSQL, avec une autre définition de ce qui est correct.

L’algorithme de base fonctionne bien sur des photographies ordinaires, mais un style de catalogue courant met au jour une hypothèse qui compte en production.

Définir ce qu’est « la même image »

Avant tout algorithme, il faut une règle. Voici six choses qui arrivent à une image dans une organisation, et aucune technique ne les traite toutes.

Une coche signifie que la technique reconnaît encore la paire. La dernière ligne est une paire qui ne doit PAS correspondre, et c’est là que les méthodes perceptuelles sont les plus faibles.

Quelles lignes comptent n’est pas une question technique. Dans un DAM (digital asset management, une photothèque centralisée), le même moteur répond à trois besoins, avec trois définitions différentes de « correct ».

« Avons-nous déjà importé ce média ? » s’exécute automatiquement à l’ingestion. Un faux positif interrompt l’import : ce chemin est donc volontairement prudent et ne couvre que les lignes 1 à 3.

« Retrouver le reste de cette séance photo. » vient d’une personne devant son clavier, qui veut du rappel et écartera elle-même le bruit. Lignes 1 à 5, sans restriction.

« Avons-nous déjà acheté une licence pour cette image ? » est le cas coûteux. Quelqu’un s’apprête à payer une image de banque d’images, et la copie déjà présente dans la bibliothèque a peut-être été recadrée, rééquilibrée en couleur et réexportée jusqu’à devenir méconnaissable. Un oubli coûte ici de l’argent : il faut un rappel maximal et une étape de confirmation humaine.

Les trois besoins peuvent partager un index et un moteur de requête, mais ils demandent des seuils différents.

Le tableau suggère aussi deux distinctions utiles.

Un hash d’octets répond à une autre question. MD5 dit s’il s’agit du même fichier, ce qui sert à l’import mais ne couvre pas les copies transformées.

Les embeddings seuls conviennent mal à la déduplication. Un embedding de vision est entraîné à rapprocher les images sémantiquement proches : « la même photographie, réencodée » et « une autre photographie du même sujet » peuvent donc toutes deux sembler de bonnes correspondances. Cette généralisation aide la recherche ordinaire, mais crée des faux positifs entre des références différentes photographiées sur le même fond.

Nous utilisons donc une méthode structurelle peu coûteuse, en grande partie insensible au sens, pour générer les candidats, et nous n’employons l’information sémantique que dans la vérification.

Un hash qui survit au réencodage

Le hash perceptuel résout les lignes 1 à 3 du tableau avec une idée issue de la compression d’images : jeter tout ce qu’un encodeur JPEG jetterait aussi, et hacher ce qui reste.

Le sous-échantillonnage à 32 × 32 détruit les artefacts de compression. Ne garder que les coefficients DCT basse fréquence détruit les détails fins. Ce qui reste est la structure grossière qu’un humain reconnaît.

Nous utilisons une DCT parce que les deux hashes perceptuels plus simples sont moins robustes pour cet usage. Un hash moyen (average hash) compare les pixels à la luminosité moyenne, si bien que les ajustements de contraste l’affectent facilement. Un hash de différence (difference hash) compare des pixels voisins : il gère mieux la luminosité mais peine sur les dégradés. La DCT demande plus de calcul, mais sépare explicitement la structure grossière du détail fin, ce qui permet de choisir les coefficients à garder.

Le résultat est un entier de 63 bits où des images semblables donnent des entiers semblables, et « semblable » a un sens précis : la distance de Hamming, le nombre de positions de bits où deux hashes diffèrent. Un réencodage la déplace d’un ou deux bits. Un redimensionnement, de quelques-uns. Un recadrage la déplace énormément, ce qui est le problème suivant.

Hacher des régions, pas seulement l’image entière

Retirez 20 % d’une image et tous les coefficients de sa DCT changent, parce que les pixels qui les alimentent ont tous bougé. Le hash devient méconnaissable, alors que quatre cinquièmes de l’image sont identiques.

La solution est de cesser de traiter une image comme un tout. freedam hache six régions indépendamment : l’image entière recadrée en carré au centre, les 70 % centraux et les quatre quadrants à 60 % chacun.

Six hashes coûtent six lignes par média et transforment une comparaison fragile sur l’image entière en un vote. La tuile qui a correspondu est une information de diagnostic, pas un sous-produit.

Chercher dans un espace sans index

Étant donné un hash de requête et six lignes par média, il faut trouver chaque ligne à une distance de Hamming donnée, par exemple 12 bits. Un B-tree ne peut pas répondre directement, parce que l’ordre numérique n’a aucun lien utile avec la distance de Hamming : WHERE hamming(phash, $1) <= 12 impose donc un parcours séquentiel de toutes les tuiles.

Le multi-index hashing ramène cela à des recherches d’égalité indexées. Découpez chaque hash de 64 bits en quatre blocs de 16 bits stockés dans des colonnes indexées. Si deux hashes diffèrent d’au plus trois bits, ces différences ne peuvent pas toucher les quatre blocs : au moins un bloc est donc identique. La garantie s’arrête au-delà de cette distance, ce qui explique pourquoi la méthode reste une seule source de candidats parmi d’autres.

Le multi-index hashing ne donne une garantie exacte que tant que le rayon est inférieur au nombre de blocs ; au-delà, c’est une heuristique de génération de candidats.

Trois détails d’implémentation ont compté en pratique.

Calculez la distance dans la base, une seule fois. Une petite fonction SQL garde l’arithmétique à côté des données : bit_count((a # b)::bit(64)), déclarée IMMUTABLE STRICT PARALLEL SAFE, afin que le planificateur puisse la paralléliser et l’intégrer à un filtre plutôt que de matérialiser des lignes dans votre application.

Éclatez sur les tuiles avec UNION ALL, puis regroupez par média. Six tuiles donnent six recherches par bloc ; les résultats sont réunis, les distances calculées, puis regroupés en une ligne par média avec MIN(hd) et la tuile qui l’a produit. Un média qui correspond sur quatre tuiles doit donner un résultat fort, pas quatre faibles.

Comprenez ce que coûte réellement une recherche par bloc. Seize bits donnent 65 536 valeurs possibles par colonne de bloc. Sur une bibliothèque de hashes aléatoires uniformes, une recherche d’égalité sur un bloc renvoie environ une ligne sur 65 536, et c’est pourquoi la méthode fonctionne. Les hashes réels ne sont pas uniformes. Un corpus qui contient beaucoup de régions plates ou quasi identiques produit des valeurs de bloc qui se répètent des milliers de fois, et une requête qui tombe sur l’une d’elles paie chaque ligne renvoyée avant même qu’une seule distance soit calculée. C’est le même problème de forme du corpus que dans la section suivante, qui arrive par une autre porte : le modèle de coût de l’algorithme suppose une distribution que votre bibliothèque n’a peut-être pas. Si les recherches sont lentes, mesurez la distribution des valeurs de c0 à c3 avant de toucher à quoi que ce soit d’autre.

Consignez le plafond de candidats. L’étape A s’arrête à 2 000 candidats triés par distance exacte. L’étape de vérification ne fait que réduire cet ensemble, mais le plafond a quand même un coût en rappel et doit figurer dans le rapport d’exhaustivité, comme décrit dans le premier article.

Là où la photographie de catalogue met l’hypothèse en défaut

Le hash perceptuel suppose que les images contiennent assez de structure pour être comparées. La photographie de catalogue sur fond blanc uni affaiblit cette hypothèse, parce que la majeure partie de chaque image est uniforme. La DCT d’une image « presque entièrement blanche avec un petit objet au milieu » est dominée par des coefficients proches de zéro : le seuil à la médiane peut alors séparer du bruit plutôt qu’une structure utile, et placer des produits différents à quelques bits les uns des autres.

Cela ne produit aucune exception. Cela se voit comme un catalogue qui signale de mauvaises suggestions de doublons, alors que les autres bibliothèques et les tests se comportent normalement. La distance est calculée correctement ; la distribution des images a simplement violé une hypothèse sous-jacente à la métrique. Les tests doivent donc contenir des exemples des styles photographiques présents dans le corpus réel, pas seulement des photographies génériques.

Abaisser le seuil global réduirait le rappel sur les photographies ordinaires : nous classons donc cette forme d’image et ne resserrons les seuils que pour elle.

freedam mesure deux statistiques peu coûteuses sur la vignette 16 par 16 en niveaux de gris, avant de la normaliser : la variance des valeurs de pixels et la densité de contours, tirée de l’amplitude du gradient.

Le coefficient s’applique à chaque image de requête, à partir de statistiques calculées une fois à l’ingestion. Il ne coûte rien à la recherche et fait la différence entre utilisable et inutile sur une bibliothèque e-commerce.

Plus généralement, un seuil de similarité dépend de la paire d’images et du corpus. Quand une bibliothèque a un style photographique dominant, une seule constante globale a peu de chances de donner la même précision sur tous les médias. Mesurer la variance et la densité de contours à l’ingestion offre un moyen peu coûteux de corriger selon ce style.

Trois sources de candidats, un seul résultat

Comme la garantie du principe des tiroirs s’arrête au rayon 3, et comme les recadrages mettent la structure complètement en échec, le hash seul laisse des trous. freedam exécute trois générateurs de candidats en parallèle, et chacun existe à cause d’un défaut précis et identifié des autres.

Trois sources, ce n’est pas de la redondance. Chacune couvre un défaut que les deux autres ont à coup sûr, et c’est l’union qui rend les recadrages et les changements de format détectables.

Trois détails méritent d’être explicités.

Le vecteur de vignette contraint l’embedding de vision. La source C est la seule qui survive à un recadrage serré, mais elle peut aussi renvoyer une autre photographie du même sujet. Un candidat doit donc passer à la fois un seuil sémantique de cosinus et un seuil structurel de distance de vignette. Un vrai recadrage reste en général proche structurellement, alors qu’une nouvelle photographie ne l’est souvent pas.

Gardez la limite visible pour le parcours ANN. La requête de vision utilise ORDER BY clip_vector <=> $1 LIMIT 50, le filtre de distance étant appliqué ensuite. Ajouter AND distance <= x semble plus strict mais empêche le parcours de l’index HNSW dans cette forme de requête. Comme pour la borne de lignes BM25 du premier article, l’exécuteur doit voir la limite pour utiliser efficacement l’index approximatif.

Consignez les comparaisons qui ont été exécutées. Une correspondance vectorielle seule porte une distance de Hamming sentinelle de -1 et une correspondance de vision seule porte -2, plutôt qu’une valeur plausible. La confiance peut alors utiliser une formule adaptée aux preuves disponibles, et le débogage ultérieur peut distinguer une comparaison sautée d’une distance mesurée.

La tolérance dépend du cas d’usage

Le même moteur de détection sert des besoins aux profils de risque différents. À l’ingestion, un faux positif interrompt un import : le système ne doit donc signaler que les copies quasi exactes. En recherche interactive, les utilisateurs peuvent inspecter eux-mêmes des résultats bruités, et le seuil peut donc favoriser le rappel. Un seul seuil ne peut pas bien servir les deux cas.

Il y a donc une seule tolérance sur une échelle de 0 à 50, dont tout le reste est dérivé. Cinq familles de seuils évoluent ensemble le long d’une courbe linéaire par morceaux, avec des ancres à 0, 10 et 50.

Cinq nombres qui doivent évoluer ensemble, exposés comme un seul. Le coude à 10 est un point d’ancrage de compatibilité, pas un artefact d’ajustement de courbe.

Le coude à 10 préserve exactement les anciennes constantes d’ingestion. Quand on remplace des valeurs codées en dur par une courbe réglable, une ancre sur les anciennes valeurs par défaut donne un point de compatibilité connu et facilite l’évaluation des changements ailleurs sur l’échelle.

Coût et limites actuelles

L’essentiel du coût est payé à l’ingestion. ImageMagick ouvre l’image, crée six tuiles de 256 pixels, les convertit en entrées de 32 par 32 en niveaux de gris pour les DCT, et produit une vignette 16 par 16 pour le vecteur et les statistiques d’image. Le travail est limité par le CPU et s’exécute dans une file, pas dans la requête d’import. Ce qui est stocké reste relativement petit : six lignes de huit entiers, un vecteur de 256 dimensions et un vecteur optionnel de 768 dimensions.

Faire plus de travail une seule fois à l’ingestion limite les requêtes à quatre recherches d’égalité indexées, deux parcours de plus proches voisins approximatifs et quelques milliers d’appels à bit_count. Cela rend « est-ce déjà dans la bibliothèque ? » praticable comme requête synchrone sur une bibliothèque de 200 000 médias.

Les limites :

La rotation et le miroir la mettent en échec. Le hash DCT d’une image retournée n’a aucun rapport avec l’original. Les petites rotations d’un degré ou deux passent ; 90 degrés non, ni le retournement horizontal. Les systèmes qui en ont besoin hachent aussi les variantes transformées, pour un multiple du coût d’indexation. Nous ne le faisons pas, car dans une bibliothèque de marque, un média en miroir est généralement un média volontairement différent.

Les compositions lourdes sont hors périmètre. Une photographie source placée dans une mise en page travaillée, avec du texte par-dessus et un traitement colorimétrique, n’est un quasi-doublon de la photographie selon aucune de ces mesures. La retrouver demande une correspondance par région, qui est une architecture différente et bien plus coûteuse.

Elle travaille par image, pas par région. Les tuiles forment une grille fixe, pas un détecteur. Elles approchent bien la tolérance au recadrage, et pas du tout la correspondance au niveau de l’objet.

La vidéo est traitée par substitut, pas directement. On peut hacher des images extraites, mais la forme de la question change, parce que « la même vidéo » fait intervenir le temps.

Chaque limite peut être traitée avec plus d’indexation et de calcul, mais le système actuel ne déclare que les transformations qu’il est conçu pour couvrir, afin que les utilisateurs ne prêtent pas à la détection de doublons plus de force qu’elle n’en a.

Ce que nous dirions à quiconque construit cela

Décidez ce que « la même image » signifie avant de choisir un algorithme. Écrivez le tableau des transformations. La ligne qui ne doit pas correspondre est celle qui détermine l’architecture.
N’utilisez pas les embeddings seuls pour la déduplication. Ils sont entraînés à généraliser, précisément sur la distinction que vous cherchez à faire. Servez-vous-en pour vérifier ou pour récupérer des recadrages, encadrés par un contrôle structurel.
Hachez des régions, pas des images. Les tuiles transforment une comparaison fragile, tout ou rien, en un vote, et la tuile qui a correspondu indique comment les deux images sont liées.
Sachez où s’arrête votre garantie du principe des tiroirs. Le multi-index hashing est exact en dessous du rayon m et heuristique au-dessus. Si vos seuils sont au-dessus, dites-le et ajoutez une deuxième source plutôt que de faire semblant.
Un seuil est une propriété du corpus. Deux statistiques par image à l’ingestion valent mieux qu’une constante globale réglée sur un échantillon qui ne contenait pas le catalogue de votre client.
Laissez l’index garder sa forme. Un parcours ANN a besoin d’une limite visible ; un filtre qui ressemble à un resserrement peut être un parcours complet déguisé.
N’inventez jamais une distance que vous n’avez pas mesurée. Les sentinelles et un score adapté aux preuves gardent un jeu de résultats déboguable.
Exposez un seul réglage, dérivez le reste. Les utilisateurs ont une seule question (« quel degré d’exigence ? »), et chaque étape du pipeline a besoin d’un nombre différent pour y répondre.

Où cela se trouve dans le produit

La détection de quasi-doublons s’exécute à l’ingestion, où elle signale les copies probables avant leur entrée dans la bibliothèque, et à la demande sous forme de recherche par similarité visuelle et de détection de doublons. Tout ce qui précède s’exécute dans la même instance PostgreSQL que celle qui stocke les médias, sur pgvector et quatre index B-tree ordinaires, ce qui contribue à rendre freedam praticable en auto-hébergement.

Prochain article de la série : comment la recherche gère vingt langues, y compris pourquoi le nom d’index, le prédicat de langue et la configuration de texte doivent se replier ensemble.

Si vous préférez voir plutôt que lire, essayez la démo et importez une copie recadrée et réenregistrée d’une image déjà présente dans la bibliothèque.