Empreinte digitale de l'Image pour comparer la similarité de nombreuses images

Normal hachage ou le calcul de CRC algorithmes ne fonctionnent pas bien avec les données de l'image. La nature dimensionnelle de l'information doit être prise en compte.

si vous avez besoin d'empreintes extrêmement robustes, de sorte que les transformations affine (échelle, rotation, traduction, retournement) sont prises en compte, vous pouvez utiliser une transformation de Radon sur la source d'image pour produire une cartographie normative des données d'image-stockez ceci avec chaque image et puis comparez juste les empreintes. C'est un algorithme complexe et pas pour les faibles de cœur.

quelques solutions simples sont possibles:

1. créer un histogramme de luminosité pour l'image en tant qu'empreinte digitale
2. créer des versions réduites de chaque image comme une empreinte digitale
3. combiner la technique (1) et (2) dans une approche hybride pour améliorer la qualité de comparaison

A l'histogramme de luminosité (en particulier un qui est séparé en composants RVB) est une empreinte digitale raisonnable pour une image - et peut être mis en œuvre très efficacement. La soustraction d'un histogramme à un autre produira un nouveau historgram que vous pouvez traiter pour décider comment deux images sont similaires. Les histogrammes, parce que le seul évaluer la distribution et l'occurrence de la luminosité/information de couleur gérer affine transformations assez bien. Si vous quantifiez l'information de luminosité de chaque composante de couleur jusqu'à une valeur de 8-bit, 768 bytes 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 l'information sur la couleur d'une image est manipulée. Si vous appliquez des transformations comme le contraste/luminosité, postérize, changement de couleur, l'information de luminosité change. Les faux positifs sont également possibles avec certains types d'images ... comme les paysages et les images où une seule couleur domine les autres.

utiliser des images à échelle réduite est une autre façon de réduire la densité d'information de l'image à un niveau qui est plus facile à comparer. Les réductions inférieures à 10% de la taille de l'image originale perdent généralement trop d'information pour être utile - de sorte qu'une image de 800x800 pixels peut être réduite à 80x80 et fournir encore assez d'information pour effectuer des empreintes décentes. Contrairement aux données d'histogrammes, vous devez effectuer une mise à l'échelle anisotrope des données d'image lorsque les résolutions sources ont un aspect variable. ratio. En d'autres termes, la réduction d'une image 300x800 en une vignette 80x80 provoque une déformation de l'image, telle que comparée à une image 300x500 (qui est très similaire) causera de faux négatifs. Les empreintes digitales des vignettes produisent aussi souvent de faux négatifs lorsque des transformations affines sont impliquées. Si vous faites pivoter une image, sa vignette sera très différente de l'image originale et peut donner un faux positif.

combiner les deux techniques est une manière raisonnable pour couvrir vos paris et réduire l'occurrence de faux positifs et de faux négatifs.

il y a une approche beaucoup moins ad hoc que les variantes d'image réduites 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.

Prendre ondelettes de Haar de l'image. Fondamentalement, la ondelette Haar est la succession des 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 que vous êtes dans l '"arbre" de mipmaps. Le calcul est simple. Ensuite, une fois que vous avez la vague Haar correctement pesé, jeter tous sauf les coefficients k plus grands (en termes de valeur absolue), normaliser le vecteur et enregistrer.

Si vous prenez le produit scalaire de deux vecteurs normés il vous donne une mesure de similarité avec 1 étant presque identiques. J'ai posté plus d'informations sur ici .

vous devriez certainement jeter un oeil à phash .

pour la comparaison d'image il y a ce php projet : https://github.com/kennethrapp/phasher

et mon petit javascript clone: https://redaktorcms.com/dev/phasher/demo_js/index.html

malheureusement, c'est basé sur"bitcount" mais will reconnaître les images tournées. Une autre approche dans le javascript était de construire un histogramme luminosité de l'image à l'aide de la toile. Vous pouvez visualiser un histogramme polygonal sur la toile et comparer ce polygone dans votre base de données (par exemple mySQL spatial ...)

il s'agit d'une démo pour les histogrammes vidéo: https://redaktorcms.com/dev/globetrottr/testHashVideo.php

il y a longtemps, j'ai travaillé sur un système qui avait des caractéristiques similaires, et c'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, donc nous avons utilisé 12 zones. Cela enlève la résolution des images source de l'image.
2. Pour chaque zone, calculer une couleur globale - la moyenne de tous les pixels dans la zone
3. pour l'image entière, calculer une couleur globale - la moyenne de toutes les zones

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

pour les comparaisons, vous devez également regarder chaque canal de couleur individuellement.

1. pour l'image globale, comparez les canaux de couleurs pour l'ensemble des couleurs pour voir si elles sont dans un certains seuils-disons 10 %151960920"
2. si les images sont à l'intérieur du seuil, comparez ensuite chaque zone. Si toutes les zones sont également à l'intérieur du seuil, les images sont une correspondance assez forte que vous pouvez au moins les signaler pour une comparaison plus poussée.

cela vous permet de rejeter rapidement les images qui ne correspondent pas; vous pouvez également utiliser plus de zones et/ou appliquer l'algorithme de façon récursive pour obtenir une plus grande confiance en match.

semblable à la réponse D'Ic - vous pourriez essayer de comparer les images à plusieurs résolutions. Ainsi chaque image est enregistrée en 1x1, 2x2, 4x4 .. 800x800. Si le plus faible résolution ne correspond pas (sous réserve d'un seuil), vous pouvez rejeter immédiatement. Si elle correspond, Vous pouvez les comparer à la prochaine résolution supérieure, et ainsi de suite..

aussi-si les images partagent une structure similaire, comme des images médicales, vous pourriez être en mesure d'extraire cette structure dans une description qui est plus facile/rapide à comparer.

donc vous voulez faire" correspondance d'empreintes digitales "qui est assez différent de"correspondance d'image". L'analyse des empreintes digitales a été étudiée en profondeur 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 FAR et FRR mesures - faux taux D'acceptation et faux taux de rejet ).

je vous suggère pour mieux regarder à LFA (Local Feature Analysis) classe de techniques de détection, principalement construit sur l'inspection minutiae. Les Minutiae sont des caractéristiques spécifiques de toute empreinte digitale et ont été classées en plusieurs classes. Cartographier une image matricielle sur une carte des minutiae est ce que font en fait la plupart des autorités publiques pour classer les criminels ou les terroristes.

voir ici pour plus de références

pour comparaison d'image iPhone et développement de similarité d'image vérifier: http://sites.google.com/site/imagecomparison/

pour le voir en action, regardez eyeBuy Visual Search sur l'AppStore iTunes.

une façon de faire cela est de redimensionner l'image et de laisser tomber la résolution de manière significative (à 200x200 peut-être?), stockant une version plus petite (moyenne en 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 est juste un algorithme O (n) à comparer (vous n'avez qu'à la comparer à chaque image précédemment insérée). Il finira par se décomposer cependant que la liste des images à comparer devient plus grande, mais je pense que vous êtes en sécurité pendant un certain temps.

après 400 jours de course, vous aurez 500 000 images, ce qui signifie (en faisant abstraction du temps de redimensionner l'image) 200(H)*200(W)*500,000(images)*3(RGB) = 60,000,000 comparaisons. Si chaque image correspond exactement, vous allez prendre du retard, mais ce ne sera probablement pas le cas, n'est-ce pas? N'oubliez pas, vous pouvez escompte image comme une correspondance dès qu'une seule comparaison tombe en dehors de votre seuil.

voulez-vous littéralement comparer chaque image avec les autres? Quelle est la demande? Peut-être que vous avez juste besoin d'une sorte d'indexation et de récupération d'images basées sur certains descripteurs? Ensuite, par exemple, vous pouvez regarder la norme MPEG-7 pour L'Interface de Description de contenu multimédia. Vous pourrez alors comparer les différents descripteurs d'image, qui ne seront pas aussi précis, mais beaucoup plus rapides.

à partir de 2015 (retour vers le futur... sur cette question de 2009 qui est maintenant Haut Classé dans Google) la similitude d'image peut être calculé en utilisant des techniques D'apprentissage en profondeur. La famille d'algorithmes connue sous le nom D'encodeurs automatiques peut créer une représentation vectorielle qui peut être recherchée pour la similarité. Il y a une démo ici .

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

cherchez-vous des images byte-identiques plutôt que de chercher des images qui sont dérivées de la même source mais peuvent être un format ou une résolution différente (ce qui me frappe comme un problème assez difficile).