Comparaison d'images - algorithme rapide

Je cherche à créer une table de base d'images, puis à comparer toute nouvelle image à celle-ci pour déterminer si la nouvelle image est un doublon exact (ou proche) de la base.

Par exemple: si vous souhaitez réduire le stockage de la même image des centaines de fois, vous pouvez en stocker une copie et lui fournir des liens de référence. Lorsqu'une nouvelle image est entrée, vous souhaitez la comparer à une image existante pour vous assurer qu'il ne s'agit pas d'un doublon ... d'idées?

Une de mes idées était de réduire à une petite vignette, puis de choisir au hasard des emplacements de 100 pixels et de les comparer.

Voici trois approches pour résoudre ce problème (et il y en a beaucoup d'autres).

• La première est une approche standard en vision par ordinateur, la correspondance des points clés. Cela peut nécessiter des connaissances de base pour être implémenté et peut être lent.

• La seconde méthode utilise uniquement un traitement d'image élémentaire, est potentiellement plus rapide que la première approche et est simple à mettre en œuvre. Cependant, ce qu'il gagne en compréhensibilité, il manque de robustesse - la correspondance échoue sur les images mises à l'échelle, pivotées ou décolorées.

• La troisième méthode est à la fois rapide et robuste, mais elle est potentiellement la plus difficile à mettre en œuvre.

Correspondance de points clés

Mieux que de choisir 100 points aléatoires, c'est de choisir 100 points importants . Certaines parties d'une image contiennent plus d'informations que d'autres (en particulier sur les bords et les coins), et ce sont celles que vous voudrez utiliser pour une correspondance d'image intelligente. Google " extraction de points clés " et " correspondance de points clés " et vous trouverez pas mal d'articles académiques sur le sujet. De nos jours, les points clés SIFT sont sans doute les plus populaires, car ils peuvent faire correspondre les images sous différentes échelles, rotations et éclairages. Certaines implémentations SIFT peuvent être trouvées ici .

Un inconvénient de la correspondance des points clés est le temps d'exécution d'une implémentation naïve: O (n ^ 2m), où n est le nombre de points clés dans chaque image et m est le nombre d'images dans la base de données. Certains algorithmes intelligents peuvent trouver la correspondance la plus proche plus rapidement, comme les arbres quadruples ou le partitionnement d'espace binaire.

Solution alternative: méthode histogramme

Une autre solution moins robuste mais potentiellement plus rapide consiste à créer des histogrammes de fonction pour chaque image et à choisir l'image avec l'histogramme le plus proche de l'histogramme de l'image d'entrée. J'ai implémenté cela en tant que premier cycle, et nous avons utilisé 3 histogrammes de couleurs (rouge, vert et bleu), et deux histogrammes de texture, direction et échelle. Je donnerai les détails ci-dessous, mais je dois noter que cela ne fonctionnait bien que pour faire correspondre des images TRÈS similaires aux images de la base de données. Les images redimensionnées, pivotées ou décolorées peuvent échouer avec cette méthode, mais de petits changements comme le recadrage ne briseront pas l'algorithme

Le calcul des histogrammes de couleur est simple - il vous suffit de choisir la plage de vos compartiments d'histogramme et, pour chaque plage, de compter le nombre de pixels avec une couleur dans cette plage. Par exemple, considérons l'histogramme "vert" et supposons que nous choisissions 4 compartiments pour notre histogramme: 0-63, 64-127, 128-191 et 192-255. Ensuite, pour chaque pixel, nous examinons la valeur verte et ajoutons un décompte au compartiment approprié. Lorsque nous avons terminé le décompte, nous divisons chaque total de seau par le nombre de pixels dans l'image entière pour obtenir un histogramme normalisé pour le canal vert.

Pour l'histogramme de la direction de la texture, nous avons commencé par effectuer une détection de bord sur l'image. Chaque point de bord a un vecteur normal pointant dans la direction perpendiculaire au bord. Nous avons quantifié l'angle du vecteur normal dans l'un des 6 compartiments entre 0 et PI (puisque les arêtes ont une symétrie de 180 degrés, nous avons converti les angles entre -PI et 0 entre 0 et PI). Après avoir compté le nombre de points de bord dans chaque direction, nous avons un histogramme non normalisé représentant la direction de la texture, que nous avons normalisé en divisant chaque compartiment par le nombre total de points de bord dans l'image.

Pour calculer l'histogramme de l'échelle de texture, pour chaque point de bord, nous avons mesuré la distance jusqu'au point de bord le plus proche avec la même direction. Par exemple, si le point de bord A a une direction de 45 degrés, l'algorithme marche dans cette direction jusqu'à ce qu'il trouve un autre point de bord avec une direction de 45 degrés (ou dans un écart raisonnable). Après avoir calculé cette distance pour chaque point de bord, nous transférons ces valeurs dans un histogramme et le normalisons en divisant par le nombre total de points de bord.

Vous avez maintenant 5 histogrammes pour chaque image. Pour comparer deux images, vous prenez la valeur absolue de la différence entre chaque compartiment d'histogramme, puis additionnez ces valeurs. Par exemple, pour comparer les images A et B, nous calculerions

|A.green_histogram.bucket_1 - B.green_histogram.bucket_1| 

pour chaque seau dans l'histogramme vert, et répétez pour les autres histogrammes, puis résumez tous les résultats. Plus le résultat est petit, meilleure est la correspondance. Répétez l'opération pour toutes les images de la base de données et la correspondance avec le plus petit résultat l'emporte. Vous voudriez probablement avoir un seuil, au-dessus duquel l'algorithme conclut qu'aucune correspondance n'a été trouvée.

Troisième choix - Points clés + arbres de décision

Une troisième approche, probablement beaucoup plus rapide que les deux autres, utilise les forêts sémantiques de texton (PDF). Cela implique l'extraction de points clés simples et l'utilisation d'une collection d'arbres de décision pour classer l'image. C'est plus rapide que la simple correspondance de points clés SIFT, car cela évite le processus de correspondance coûteux, et les points clés sont beaucoup plus simples que SIFT, donc l'extraction de points clés est beaucoup plus rapide. Cependant, il préserve l'invariance de la méthode SIFT à la rotation, à l'échelle et à l'éclairage, une caractéristique importante qui manquait à la méthode de l'histogramme.

Mise à jour :

Mon erreur - le document Semantic Texton Forests ne traite pas spécifiquement de la correspondance d'images, mais plutôt de l'étiquetage des régions. Le papier original qui fait la correspondance est celui-ci: Reconnaissance des points clés à l'aide d'arbres randomisés . De plus, les articles ci-dessous continuent de développer les idées et représentent l'état de l'art (c. 2010):

• Reconnaissance rapide des points clés à l'aide de fougères aléatoires - plus rapide et plus évolutive que Lepetit 06
• BREF: Fonctionnalités élémentaires indépendantes robustes binaires - moins robustes mais très rapides - je pense que l'objectif ici est la correspondance en temps réel sur les téléphones intelligents et autres ordinateurs de poche

La meilleure méthode que je connaisse est d'utiliser un hachage perceptuel. Il semble y avoir une bonne implémentation open source d'un tel hachage disponible sur:

http://phash.org/

L'idée principale est que chaque image est réduite à un petit code de hachage ou `` empreinte digitale '' en identifiant les caractéristiques saillantes dans le fichier image d'origine et en hachant une représentation compacte de ces caractéristiques (plutôt que de hacher directement les données d'image). Cela signifie que le taux de faux positifs est considérablement réduit par rapport à une approche simpliste telle que la réduction des images jusqu'à une image de taille minuscule et la comparaison des empreintes.

phash propose plusieurs types de hachage et peut être utilisé pour des images, audio ou vidéo.

Ce message était le point de départ de ma solution, beaucoup de bonnes idées ici, donc je pensais partager mes résultats. L'idée principale est que j'ai trouvé un moyen de contourner la lenteur de la correspondance d'images basée sur des points clés en exploitant la vitesse de phash.

Pour la solution générale, il est préférable d'employer plusieurs stratégies. Chaque algorithme est le mieux adapté à certains types de transformations d'image et vous pouvez en profiter.

En haut, les algorithmes les plus rapides; en bas le plus lent (bien que plus précis). Vous pouvez sauter les plus lents si une bonne correspondance est trouvée au niveau le plus rapide.

• fichier basé sur le hachage (md5, sha1, etc.) pour les doublons exacts
• hachage perceptuel (phash) pour les images redimensionnées
• basé sur les fonctionnalités (SIFT) pour les images modifiées

J'ai de très bons résultats avec phash. La précision est bonne pour les images redimensionnées. Ce n'est pas bon pour les images modifiées (perceptuellement) (recadrées, tournées, inversées, etc.). Pour gérer la vitesse de hachage, nous devons utiliser un cache disque / base de données pour maintenir les hachages pour la botte de foin.

La chose vraiment agréable à propos de phash est qu'une fois que vous avez construit votre base de données de hachage (qui pour moi est d'environ 1000 images / sec), les recherches peuvent être très, très rapides, en particulier lorsque vous pouvez conserver la base de données de hachage entière en mémoire. C'est assez pratique car un hachage ne fait que 8 octets.

Par exemple, si vous avez 1 million d'images, il faudrait un tableau de 1 million de valeurs de hachage 64 bits (8 Mo). Sur certains processeurs, cela tient dans le cache L2 / L3! Dans la pratique, j'ai vu un corei7 comparer à plus de 1 Giga-hamm / sec, ce n'est qu'une question de bande passante mémoire pour le CPU. Une base de données à 1 milliard d'images est pratique sur un processeur 64 bits (8 Go de RAM nécessaires) et les recherches ne dépasseront pas 1 seconde!

Pour les images modifiées / recadrées, il semblerait qu'une fonctionnalité invariante par transformation / détecteur de point clé comme SIFT soit la voie à suivre. SIFT produira de bons points clés qui détecteront le recadrage / rotation / miroir, etc. Cependant, la comparaison des descripteurs est très lente par rapport à la distance de brouillage utilisée par phash. Il s'agit d'une limitation majeure. Il y a beaucoup de comparaisons à faire, car il y a un descripteur IxJxK maximal à comparer pour rechercher une image (I = num images de meule de foin, J = points de clé cible par image de meule de foin, K = points de clé cible par image d'aiguille).

Pour contourner le problème de vitesse, j'ai essayé d'utiliser phash autour de chaque point clé trouvé, en utilisant la taille / le rayon de l'entité pour déterminer le sous-rectangle. L'astuce pour bien faire fonctionner est d'augmenter / rétrécir le rayon pour générer différents niveaux sub-rect (sur l'image de l'aiguille). Généralement, le premier niveau (non mis à l'échelle) correspondra, mais il en faut souvent un peu plus. Je ne suis pas sûr à 100% de la raison pour laquelle cela fonctionne, mais je peux imaginer que cela permet des fonctionnalités trop petites pour que phash fonctionne (phash réduit les images à 32x32).

Un autre problème est que SIFT ne distribuera pas les points clés de manière optimale. S'il y a une section de l'image avec beaucoup de bords, les points clés s'y regrouperont et vous n'en obtiendrez pas dans une autre zone. J'utilise le GridAdaptedFeatureDetector dans OpenCV pour améliorer la distribution. Je ne sais pas quelle taille de grille est la meilleure, j'utilise une petite grille (1x3 ou 3x1 selon l'orientation de l'image).

Vous voudrez probablement redimensionner toutes les images de la botte de foin (et l'aiguille) à une taille plus petite avant la détection des fonctionnalités (j'utilise 210 px le long de la dimension maximale). Cela réduira le bruit dans l'image (toujours un problème pour les algorithmes de vision par ordinateur) et concentrera également le détecteur sur des caractéristiques plus importantes.

Pour les images de personnes, vous pouvez essayer la détection des visages et l'utiliser pour déterminer la taille de l'image à mettre à l'échelle et la taille de la grille (par exemple, le plus grand visage mis à l'échelle pour être de 100 pixels). Le détecteur de caractéristiques prend en compte plusieurs niveaux d'échelle (en utilisant des pyramides) mais il y a une limite au nombre de niveaux qu'il utilisera (cela peut être ajusté bien sûr).

Le détecteur de points clés fonctionne probablement mieux lorsqu'il renvoie moins que le nombre de fonctionnalités que vous vouliez. Par exemple, si vous demandez 400 et récupérez 300, c'est bien. Si vous en récupérez 400 à chaque fois, quelques bonnes fonctionnalités ont probablement dû être omises.

L'image de l'aiguille peut avoir moins de points clés que les images de la botte de foin et toujours obtenir de bons résultats. L'ajout de plus n'obtient pas nécessairement d'énormes gains, par exemple avec J = 400 et K = 40, mon taux de réussite est d'environ 92%. Avec J = 400 et K = 400, le taux de réussite ne monte que jusqu'à 96%.

Nous pouvons profiter de la vitesse extrême de la fonction de hamming pour résoudre l'échelle, la rotation, la mise en miroir, etc. Une technique à passes multiples peut être utilisée. À chaque itération, transformez les sous-rectangles, re-hachez et réexécutez la fonction de recherche.

Comme l'a souligné cartman, vous pouvez utiliser n'importe quel type de valeur de hachage pour trouver des doublons exacts.

Un point de départ pour trouver des images proches pourrait être ici . Il s'agit d'un outil utilisé par les sociétés CG pour vérifier si les images remaniées montrent toujours essentiellement la même scène.

J'ai une idée, qui peut fonctionner et qui sera très probablement très rapide. Vous pouvez sous-échantillonner une image pour dire une résolution de 80x60 ou comparable, et la convertir en niveaux de gris (après le sous-échantillonnage, ce sera plus rapide). Traitez les deux images que vous souhaitez comparer. Ensuite, exécutez la somme normalisée des différences au carré entre deux images (l'image de requête et chacune de la base de données), ou mieux encore la corrélation croisée normalisée, qui donne une réponse plus proche de 1, si les deux images sont similaires. Ensuite, si les images sont similaires, vous pouvez procéder à des techniques plus sophistiquées pour vérifier qu'il s'agit des mêmes images. Évidemment, cet algorithme est linéaire en termes de nombre d'images dans votre base de données, même s'il va être très rapide jusqu'à 10000 images par seconde sur le matériel moderne. Si vous avez besoin d'une invariance par rapport à la rotation, un gradient dominant peut être calculé pour cette petite image, puis l'ensemble du système de coordonnées peut être tourné en orientation canonique, mais cela sera plus lent. Et non, il n'y a pas d'invariance à l'échelle ici.

Si vous voulez quelque chose de plus général ou d'utiliser de grandes bases de données (millions d'images), alors vous devez vous pencher sur la théorie de la récupération d'images (de nombreux articles sont apparus au cours des 5 dernières années). Il y a quelques pointeurs dans d'autres réponses. Mais cela pourrait être exagéré, et l'approche d'histogramme suggérée fera l'affaire. Bien que je pense que la combinaison de nombreuses approches rapides différentes sera encore meilleure.

Ma société compte environ 24 millions d' images provenant de fabricants chaque mois. Je cherchais une solution rapide pour faire en sorte que les images que nous téléchargeons dans notre catalogue soient de nouvelles images.

Je tiens à dire que j'ai cherché sur Internet très largement pour tenter de trouver une solution idéale. J'ai même développé mon propre algorithme de détection de bord.
J'ai évalué la vitesse et la précision de plusieurs modèles. Mes images, qui ont un fond blanc, fonctionnent très bien avec le phasage. Comme le redcalx dit , je recommande phash ou ahash. N'UTILISEZ PAS le hachage MD5 ou tout autre hachage cryptographique. À moins que vous ne souhaitiez que des correspondances d'images EXACTES. Tout redimensionnement ou manipulation qui se produit entre les images donnera un hachage différent.

Pour phash / ahash, vérifiez ceci: imagehash

Je voulais étendre la publication de * redcalx * en publiant mon code et ma précision.

Ce que je fais:

from PIL import Image
from PIL import ImageFilter
import imagehash

img1=Image.open(r"C:\yourlocation")
img2=Image.open(r"C:\yourlocation")
if img1.width<img2.width:
    img2=img2.resize((img1.width,img1.height))
else:
    img1=img1.resize((img2.width,img2.height))
img1=img1.filter(ImageFilter.BoxBlur(radius=3))
img2=img2.filter(ImageFilter.BoxBlur(radius=3))
phashvalue=imagehash.phash(img1)-imagehash.phash(img2)
ahashvalue=imagehash.average_hash(img1)-imagehash.average_hash(img2)
totalaccuracy=phashvalue+ahashvalue

Voici certains de mes résultats:

item1  item2  totalsimilarity
desk1  desk1       3
desk1  phone1     22
chair1 desk1      17
phone1 chair1     34

J'espère que cela t'aides!

Je pense que la réduction de la taille de l'image à une taille presque icône, disons 48x48, puis la conversion en niveaux de gris, puis la différence entre les pixels ou Delta, devraient bien fonctionner. Parce que nous comparons le changement de couleur des pixels, plutôt que la couleur réelle des pixels, peu importe si l'image est légèrement plus claire ou plus sombre. Les changements importants seront importants car les pixels devenant trop clairs / sombres seront perdus. Vous pouvez l'appliquer sur une ligne ou autant que vous le souhaitez pour augmenter la précision. Au maximum, vous auriez 47x47 = 2 209 soustractions à faire pour former une clé comparable.

Choisir 100 points aléatoires pourrait signifier que des images similaires (ou parfois même différentes) seraient marquées comme identiques, ce qui, je suppose, n'est pas ce que vous voulez. Les hachages MD5 ne fonctionneraient pas si les images étaient de formats différents (png, jpeg, etc.), avaient des tailles différentes ou avaient des métadonnées différentes. Réduire toutes les images à une taille plus petite est un bon pari, faire une comparaison pixel par pixel ne devrait pas prendre trop de temps tant que vous utilisez une bonne bibliothèque d'images / un langage rapide et que la taille est suffisamment petite.

Vous pouvez essayer de les faire minuscules, puis si elles sont les mêmes, effectuez une autre comparaison sur une plus grande taille - pourrait être une bonne combinaison de vitesse et de précision ...

Si vous avez un grand nombre d'images, examinez un filtre Bloom , qui utilise plusieurs hachages pour un résultat probabliste mais efficace. Si le nombre d'images n'est pas énorme, un hachage cryptographique comme md5 devrait suffire.