Rechercher des images similaires, analyser un seul algorithme

J'ai récemment dû résoudre le problème de l'optimisation de la recherche d'images en double.

La solution existante fonctionne sur une bibliothèque Python assez connue, Image Match , basée sur UNE SIGNATURE D'IMAGE POUR TOUT TYPE D'IMAGE, rédigée par H. Chi Wong, Marshall Bern et David Goldberg.

Pour un certain nombre de raisons, il a été décidé de tout réécrire sur Kotlin, tout en abandonnant le stockage et la recherche dans ElasticSearch, ce qui nécessite beaucoup plus de ressources, à la fois ironiques et humaines, pour le support et l'administration, en faveur de la recherche dans le cache local en mémoire.

Pour comprendre comment cela fonctionne, j'ai dû me plonger dans le code Python «référence», car le travail original n'est parfois pas tout à fait évident, et à quelques endroits il me fait penser «comment dessiner un hibou». En fait, je veux partager les résultats de cette étude, en même temps parler de certaines optimisations, à la fois en termes de volume de données et de vitesse de recherche. Peut-être que quelqu'un vous sera utile.

Avertissement: Il est possible que je me suis trompé quelque part, que je l'ai mal fait ou pas de manière optimale. Eh bien, je serai heureux de toute critique et commentaire. :)

Comment ça marche:

1. L'image est convertie au format noir et blanc 8 bits (un point est un octet dans la valeur 0-255)
2. L'image est rognée de manière à éliminer 5% de la différence accumulée (plus ci-dessous) de chacun des quatre côtés. Par exemple, un cadre noir autour de l'image.
3. Une grille de travail est sélectionnée (9x9 par défaut), dont les nœuds serviront de points de référence à la signature d'image.
4. Pour chaque point de référence, sur la base d'une certaine zone autour de lui, sa luminosité est calculée.
5. Pour chaque point de référence, il est calculé combien il est plus clair / plus sombre que ses huit voisins. Cinq gradations sont utilisées, de -2 (beaucoup plus sombre) à 2 (beaucoup plus clair).
6. Toute cette «joie» se déroule dans un tableau unidimensionnel (vecteur) et est appelée par la signature d'image.

La similitude des deux images est vérifiée comme suit:



Plus le d est bas, mieux c'est. En fait, d <0,3 est presque une garantie d'identité.

Maintenant plus en détail.

Première étape

Je pense que parler de la conversion en niveaux de gris n'a pas de sens.

Deuxième étape

Disons que nous avons une image comme celle-ci:


On voit qu'il y a un cadre noir de 3 pixels à droite et à gauche et 2 pixels en haut et en bas, dont nous n'avons pas du tout besoin en comparaison

La frontière de coupure est déterminée par l'algorithme suivant:

1. Pour chaque colonne, nous calculons la somme des différences absolues des éléments voisins.
   
2. On recadre à gauche et à droite le nombre de pixels dont la contribution à la différence cumulée totale est inférieure à 5%.

Nous faisons de même pour les colonnes.

Une précision importante: si les dimensions de l'image résultante sont insuffisantes pour l'étape 4, alors on ne recadre pas!

Étape trois

Eh bien, tout est assez simple ici, nous divisons l'image en parties égales et sélectionnons les points nodaux.

Quatrième étape

La luminosité du point d'ancrage est calculée comme la luminosité moyenne de tous les points de la zone carrée qui l'entoure. Dans l'œuvre originale, la formule suivante est utilisée pour calculer les côtés de ce carré:

Cinquième étape

Pour chaque point de référence, la différence de sa luminosité avec la luminosité de ses huit voisins est calculée. Pour les points pour lesquels il n'y a pas de voisins (lignes supérieure et inférieure, colonnes gauche et droite), la différence est prise à 0.

De plus, ces différences sont réduites à cinq gradations:


Il s'avère quelque chose comme cette matrice:

Sixième étape

Je pense qu'aucune explication n'est nécessaire.

Et maintenant sur l'optimisation

Dans l'œuvre originale, il est à juste titre souligné qu'à partir de la signature résultante, il est possible d'effacer complètement les valeurs nulles le long des bords de la matrice, car elles seront identiques pour toutes les images.


Cependant, si vous regardez attentivement, vous pouvez voir que pour deux voisins, leurs gradations mutuelles seront égales en valeur absolue. Par conséquent, en fait, vous pouvez supprimer en toute sécurité quatre valeurs en double pour chaque point de référence, ce qui réduit de moitié la taille de la signature (à l'exclusion des zéros latéraux).


Évidemment, lors du calcul de la somme des carrés, pour chaque x il y aura certainement un modulo égal x ' et la formule de calcul de la norme peut être écrite quelque chose comme ça (sans plonger dans la réindexation):


Cela est vrai à la fois pour le numérateur et pour les deux termes du dénominateur.

Plus loin dans le travail original, il est à noter que trois bits suffisent pour stocker chaque gradation. C'est-à-dire, par exemple, dans le long non signé s'adaptera à 21 gradations. Il s'agit d'une économie de taille assez importante, mais, d'un autre côté, cela ajoute de la complexité lors du calcul de la somme des carrés de la différence entre les deux signatures. Je dois dire que cette idée m’a vraiment accroché à quelque chose et ne l’a pas lâché pendant quelques jours, jusqu’à ce qu’un soir, il commence à comprendre comment manger un poisson , un endroit pour économiser et simplifier le calcul. Regardez vos mains.

Nous utilisons un tel schéma de stockage, 4 bits par gradation:

Oui, seulement 16 gradations s'inscriront dans un long non signé, contre 21, mais alors le tableau de la différence des deux signatures sera calculé avec un xor et 15 décalages vers la droite avec le calcul du nombre de bits défini pour chaque itération du décalage. C'est-à-dire


Le signe n'a pas d'importance pour nous, car toutes les valeurs seront au carré.

De plus, si la valeur seuil de la distance est déterminée à l'avance, dont les valeurs ne nous intéressent plus, alors après avoir dansé un peu autour de la formule de calcul, vous pouvez dériver une condition de filtrage plutôt légère pour un simple nombre de bits défini.

Plus de détails sur l'optimisation de cet algorithme, avec des exemples de code, peuvent être trouvés dans l' article précédent . Je recommande séparément de lire les commentaires à ce sujet - le masyaman résident de Khabrovsk a proposé plusieurs méthodes de calcul plutôt intéressantes, y compris l'emballage des gradations en trois bits, en utilisant la magie des bits.

En fait, c'est tout. Merci de votre attention. :)