Empreinte digitale d'image pour comparer la similitude de nombreuses images

J'ai besoin de créer des empreintes digitales de nombreuses images (environ 100.000 existantes, 1000 nouvelles par jour, RVB, JPEG, taille maximale 800x800) pour comparer très rapidement chaque image à toutes les autres images. Je ne peux pas utiliser de méthodes de comparaison binaire car les images qui sont presque similaires doivent également être reconnues.

Le mieux serait une bibliothèque existante, mais aussi quelques conseils sur les algorithmes existants m'aideraient beaucoup.

Les algorithmes de hachage ou de calcul CRC normaux ne fonctionnent pas bien avec les données d'image. La nature dimensionnelle des informations doit être prise en compte.

Si vous avez besoin d'une empreinte digitale extrêmement robuste, de sorte que les transformations affines (mise à l'échelle, rotation, translation, retournement) soient prises en compte, vous pouvez utiliser une transformation Radon sur la source d'image pour produire une cartographie normative des données d'image - stockez-la avec chaque image et puis comparez uniquement les empreintes digitales. C'est un algorithme complexe et pas pour les âmes sensibles.

quelques solutions simples sont possibles:

1. Créer un histogramme de luminosité pour l'image sous forme d'empreinte digitale
2. Créez des versions réduites de chaque image sous forme d'empreinte digitale
3. Combinez les techniques (1) et (2) dans une approche hybride pour une meilleure qualité de comparaison

Un histogramme de luminosité (en particulier celui qui est séparé en composants RVB) est une empreinte digitale raisonnable pour une image - et peut être implémenté assez efficacement. La soustraction d'un histogramme d'un autre produira un nouvel historgramme que vous pourrez traiter pour décider de la similitude de deux images. Les histogrammes, car les seuls évaluent la distribution et l'occurrence des informations de luminosité / couleur gèrent assez bien les transformations affines. Si vous quantifiez les informations de luminosité de chaque composant de couleur jusqu'à une valeur de 8 bits, 768 octets de stockage sont suffisants pour l'empreinte digitale d'une image de presque n'importe quelle taille raisonnable. Les histogrammes de luminosité produisent de faux négatifs lorsque les informations de couleur d'une image sont manipulées. Si vous appliquez des transformations comme le contraste / la luminosité, la postérisation, le changement de couleur, les informations de luminosité changent.

L'utilisation d'images mises à l'échelle est un autre moyen de réduire la densité d'informations de l'image à un niveau plus facile à comparer. Les réductions inférieures à 10% de la taille de l'image d'origine perdent généralement trop d'informations pour être utiles - une image de 800x800 pixels peut donc être réduite à 80x80 tout en fournissant suffisamment d'informations pour effectuer une empreinte digitale décente. Contrairement aux données d'histogramme, vous devez effectuer une mise à l'échelle anisotrope des données d'image lorsque les résolutions source ont des proportions variables. En d'autres termes, la réduction d'une image 300x800 en une vignette 80x80 entraîne une déformation de l'image, de sorte que comparée à une image 300x500 (c'est très similaire), elle provoquera de faux négatifs. Les empreintes digitales miniatures produisent souvent de faux négatifs lorsque des transformations affines sont impliquées. Si vous retournez ou faites pivoter une image,

La combinaison des deux techniques est un moyen raisonnable de couvrir vos paris et de réduire l'apparition de faux positifs et de faux négatifs.

Il existe une approche beaucoup moins ad hoc que les variantes d'image à échelle réduite qui ont été proposées ici qui conserve leur saveur générale, mais qui donne une base mathématique beaucoup plus rigoureuse pour ce qui se passe.

Prenez une ondelette de Haar de de l'image. Fondamentalement, l'ondelette de Haar est la succession de différences entre les images de résolution inférieure et chaque image de résolution supérieure, mais pondérée par la profondeur de votre `` arbre '' des mipmaps. Le calcul est simple. Ensuite, une fois que vous avez correctement pondéré l'ondelette de Haar, jetez tous les coefficients sauf les k plus grands (en termes de valeur absolue), normalisez le vecteur et enregistrez-le.

Si vous prenez le produit scalaire de deux de ces vecteurs normalisés, cela vous donne une mesure de similitude, 1 étant presque identique. J'ai posté plus d'informations ici .

Vous devriez certainement jeter un oeil à phash .

Pour la comparaison d'images, il y a ce projet php : https://github.com/kennethrapp/phasher

Et mon petit clone javascript : https://redaktor.me/phasher/demo_js/index.html

Malheureusement, ceci est basé sur le "nombre de bits" mais reconnaîtra les images pivotées. Une autre approche en javascript consistait à créer un histogramme de luminosité à partir de l'image à l'aide d'une toile. Vous pouvez visualiser un histogramme de polygone sur le canevas et comparer ce polygone dans votre base de données (par exemple mySQL spatial ...)

Il y a longtemps, j'ai travaillé sur un système qui avait des caractéristiques similaires, et ceci est une approximation de l'algorithme que nous avons suivi:

1. Divisez l'image en zones. Dans notre cas, nous avions affaire à une vidéo de résolution 4: 3, nous avons donc utilisé 12 zones. Cela supprime la résolution des images source de l'image.
2. Pour chaque zone, calculez une couleur globale - la moyenne de tous les pixels de la zone
3. Pour l'image entière, calculez une couleur globale - la moyenne de toutes les zones

Donc, pour chaque image, vous stockez n + 1des valeurs entières, où nest le nombre de zones que vous suivez.

Pour les comparaisons, vous devez également examiner chaque canal de couleur individuellement.

1. Pour l'image globale, comparez les canaux de couleur pour les couleurs globales pour voir si elles se situent dans un certain seuil - par exemple, 10%
2. Si les images sont dans le seuil, comparez ensuite chaque zone. Si toutes les zones sont également comprises dans le seuil, les images correspondent suffisamment pour que vous puissiez au moins les marquer pour une comparaison ultérieure.

Cela vous permet de supprimer rapidement les images qui ne correspondent pas; vous pouvez également utiliser plus de zones et / ou appliquer l'algorithme de manière récursive pour obtenir une meilleure confiance de correspondance.

Similaire à la réponse d'Ic - vous pouvez essayer de comparer les images à plusieurs résolutions. Ainsi, chaque image est enregistrée au format 1x1, 2x2, 4x4 .. 800x800. Si la résolution la plus basse ne correspond pas (sous réserve d'un seuil), vous pouvez la rejeter immédiatement. Si cela correspond, vous pouvez les comparer à la résolution immédiatement supérieure, et ainsi de suite.

De plus, si les images partagent une structure similaire, telle que des images médicales, vous pourrez peut-être extraire cette structure dans une description plus facile / plus rapide à comparer.

Donc, vous voulez faire une «correspondance d'empreintes digitales» qui est assez différente de la «correspondance d'image». L'analyse des empreintes digitales a été profondément étudiée au cours des 20 dernières années, et plusieurs algorithmes intéressants ont été développés pour assurer le bon taux de détection (en ce qui concerne les mesures FAR et FRR - taux de fausse acceptation et taux de faux rejet ).

Je vous suggère de mieux vous pencher sur la classe de techniques de détection LFA (Local Feature Analysis) , principalement basée sur l'inspection des minuties. Les minuties sont des caractéristiques spécifiques de toute empreinte digitale et ont été classées en plusieurs classes. Mapper une image raster sur une carte minutieuse est ce que la plupart des autorités publiques font pour classer les criminels ou les terroristes.

Voir ici pour plus de références

Pour la comparaison d'images iPhone et le développement de similitudes d'images, consultez: http://sites.google.com/site/imagecomparison/

Pour le voir en action, consultez eyeBuy Visual Search sur iTunes AppStore.

À partir de 2015 (retour vers le futur ... sur cette question de 2009 désormais bien classée dans Google), la similitude des images peut être calculée à l'aide de techniques de Deep Learning. La famille d'algorithmes connus sous le nom de codeurs automatiques peut créer une représentation vectorielle qui peut faire l'objet d'une recherche de similitude. Il y a une démo ici .

Une façon de le faire est de redimensionner l'image et de réduire considérablement la résolution (à 200x200 peut-être?), En stockant une version plus petite (moyenne des pixels) pour effectuer la comparaison. Définissez ensuite un seuil de tolérance et comparez chaque pixel. Si le RVB de tous les pixels est dans la tolérance, vous avez une correspondance.

Votre parcours initial est O (n ^ 2) mais si vous cataloguez toutes les correspondances, chaque nouvelle image n'est qu'un algorithme O (n) à comparer (il vous suffit de le comparer à chaque image précédemment insérée). Cela finira par s'effondrer au fur et à mesure que la liste des images à comparer s'agrandit, mais je pense que vous êtes en sécurité pendant un certain temps.

Après 400 jours de fonctionnement, vous aurez 500 000 images, ce qui signifie (en réduisant le temps de redimensionnement de l'image) 200(H)*200(W)*500,000(images)*3(RGB)= 60 000 000 000 de comparaisons. Si chaque image correspond exactement, vous allez prendre du retard, mais ce ne sera probablement pas le cas, non? N'oubliez pas que vous pouvez réduire une image en tant que correspondance dès qu'une seule comparaison tombe en dehors de votre seuil.

Voulez-vous littéralement comparer chaque image aux autres? Quelle est l'application? Peut-être avez-vous juste besoin d'une sorte d'indexation et de récupération d'images basées sur certains descripteurs? Ensuite, par exemple, vous pouvez consulter la norme MPEG-7 pour l'interface de description de contenu multimédia. Ensuite, vous pouvez comparer les différents descripteurs d'image, qui ne seront pas aussi précis mais beaucoup plus rapides.

Il semble que les algorithmes de hachage d'images spécialisés soient un domaine de recherche active, mais peut-être qu'un calcul de hachage normal des octets d'image ferait l'affaire.

Cherchez-vous des images identiques en octets plutôt que de rechercher des images qui sont dérivées de la même source mais qui peuvent être d'un format ou d'une résolution différent (ce qui me semble être un problème assez difficile).