Empreinte digitale d'image pour comparer la similarité de plusieurs images

Question

J'ai besoin de créer des empreintes digitales d'un grand nombre d'images (environ 100 000 existantes, 1000 nouvelles par jour, RGB, JPEG, taille maximale 800x800) pour comparer chaque image à toutes les autres très rapidement. 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 des conseils sur les algorithmes existants m'aideraient beaucoup.

Answer 1

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

Si vous avez besoin d'extrêmement robuste empreintes digitales, telles que les transformations affines (mise à l'échelle, rotation, translation, retournement) sont pris en compte, vous pouvez utiliser une transformation de Radon sur la source de l'image pour produire un ensemble de normes de cartographie des données d'image - magasin de cela avec chaque image, puis de comparer simplement les empreintes digitales. C'est un algorithme complexe et pas pour les faibles de cœur.

quelques solutions simples sont possibles:

1. Créer un histogramme luminosité de l'image comme une 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 l'amélioration de la comparaison de la qualité

Avec une luminosité de l'histogramme (en particulier celle qui est séparé en composantes RVB) est raisonnable d'empreintes digitales pour une image - et peut être mis en œuvre assez efficacement. En soustrayant un histogramme à partir d'un autre va produire une nouvelle historgram qui vous pouvez décider comment similaires de deux images. Histogrammes, parce que la seule évaluer la distribution et la survenue de luminosité/couleur de l'information gérer les transformations affines assez bien. Si vous quantification de chaque composant de la couleur de la luminosité de l'information vers le bas pour une valeur de 8 bits, 768 octets de stockage sont suffisantes pour que l'empreinte digitale d'une image de presque n'importe quelle taille raisonnable. Luminosité histogrammes de produire des faux négatifs lorsque les informations de couleur dans une image est manipulé. Si vous appliquer des transformations comme la luminosité et du contraste, postérisation, le changement de couleur, la luminosité de modification de l'information. Les faux positifs sont également possible avec certains types d'images ... comme les paysages et les images, où une seule couleur qui domine les autres.

À l'aide de l'échelle des images est une autre façon de réduire la densité d'informations de l'image à un niveau qui est plus facile à comparer. Réductions en dessous de 10% de la taille originale de l'image en général trop perdre de l'information pour être utile - si un 800x800 pixels de l'image peut être réduite à 80x80 et toujours fournir suffisamment d'informations pour effectuer décent empreintes digitales. À la différence de l'histogramme des données, vous devez effectuer la mise à l'échelle anisotrope des données d'image lorsque la source de résolutions ayant différents rapports d'aspect. En d'autres termes, la réduction d'un 300x800 image dans un 80x80 vignette provoque une déformation de l'image, de telle sorte que, en comparaison avec un 300x500 de l'image (qui est très similaire) va entraîner des faux négatifs. Miniature empreintes digitales souvent aussi produire des faux négatifs lors de transformations affines sont impliqués. Si vous flip ou de faire pivoter une image, de sa vignette sera assez différent de l'original et peut provoquer un faux positif.

En combinant les deux techniques est une façon raisonnable de couvrir vos paris et de réduire le risque de survenue de faux positifs et de faux négatifs.

Answer 2

Il existe une approche beaucoup moins ad hoc que les variantes d'images réduites qui ont été proposées ici, qui conserve leur caractère général, mais qui donne une base mathématique beaucoup plus rigoureuse à ce qui se passe.

Prenez un ondelette de Haar de l'image. En fait, l'ondelette de Haar est la succession des différences entre les images de basse résolution et chaque image de haute résolution, mais pondérée par la profondeur de l'arbre des mipmaps. Le calcul est simple. Une fois que vous avez pondéré l'ondelette de Haar de manière appropriée, éliminez 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, vous obtenez une mesure de la similarité, 1 étant presque identique. J'ai posté plus d'informations sur ici .

Answer 3

Vous devriez certainement jeter un coup d'œil à phash .

Pour comparer les images, il y a celle-ci php projet : https://github.com/kennethrapp/phasher

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

Malheureusement, cette méthode est basée sur le "nombre de bits", mais elle reconnaît les images tournées. Une autre approche en javascript était de construire un histogramme de luminosité à partir de l'image à l'aide de canvas. Vous pouvez visualiser un histogramme polygonal sur le canevas et comparer ce polygone dans votre base de données (par exemple mySQL spatial ...).

Answer 4

Il y a longtemps, j'ai travaillé sur un système qui présentait des caractéristiques similaires, et voici 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. Cette opération permet d'éliminer la résolution des images sources de l'image.
2. Pour chaque zone, calculez une couleur globale - la moyenne de tous les pixels de la zone.
3. Pour l'ensemble de l'image, 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 examiner chaque canal de couleur individuellement.

1. Pour l'image globale, comparez les canaux de couleur pour les couleurs globales afin de voir si elles se situent dans un certain seuil - disons, 10 %.
2. Si les images sont dans le seuil, comparez ensuite chaque zone. Si toutes les zones se situent également dans la limite du seuil, la correspondance des images est suffisamment forte pour que vous puissiez au moins les signaler pour une comparaison ultérieure.

Cela vous permet d'écarter rapidement les images qui ne correspondent pas ; vous pouvez également utiliser davantage de zones et/ou appliquer l'algorithme de manière récursive pour obtenir une plus grande confiance dans les correspondances.

Answer 5

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

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