Comparaison d'images - algorithme rapide

Question

Je cherche à créer un tableau d'images de base, puis à comparer toute nouvelle image à ce tableau pour déterminer si la nouvelle image est une copie exacte (ou proche) de la base.

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

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

Answer 1

Vous trouverez ci-dessous trois approches pour résoudre ce problème (et il en existe bien d'autres).

• La première est une approche standard en vision par ordinateur, la mise en correspondance des points clés. Sa mise en œuvre peut nécessiter quelques connaissances de base et peut être lente.

• La seconde méthode n'utilise qu'un traitement d'image élémentaire, elle est potentiellement plus rapide que la première approche et est simple à mettre en œuvre. Cependant, si elle est plus facile à comprendre, elle n'est pas aussi robuste : 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 des points clés

Mieux que de choisir 100 points au hasard, c'est de choisir 100 important points. Certaines parties d'une image contiennent plus d'informations que d'autres (notamment les bords et les coins), et ce sont ces parties que vous voudrez utiliser pour une correspondance intelligente des images. Google " extraction de points clés " et " correspondance des points clés "et vous trouverez de nombreux articles universitaires sur le sujet. De nos jours, Points clés SIFT sont sans doute les plus populaires, car ils peuvent faire correspondre des images à différentes échelles, rotations et lumières. Quelques implémentations de SIFT peuvent être trouvées aquí .

L'un des inconvénients de la correspondance des points clés est le temps d'exécution d'une mise en œuvre 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 pourraient trouver la correspondance la plus proche plus rapidement, comme les quadtrees ou le partitionnement de l'espace binaire.

---

Solution alternative : Méthode de l'histogramme

Une autre solution moins robuste mais potentiellement plus rapide consiste à construire des histogrammes de caractéristiques pour chaque image, et à choisir l'image dont l'histogramme est le plus proche de celui de l'image d'entrée. J'ai implémenté cette méthode en tant qu'étudiant, et nous avons utilisé 3 histogrammes de couleur (rouge, vert et bleu), et deux histogrammes de texture, direction et échelle. Je vais donner les détails ci-dessous, mais je dois noter que cela n'a bien fonctionné que pour la correspondance d'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 casseront pas l'algorithme.

Le calcul des histogrammes de couleur est simple : il suffit de choisir l'intervalle de votre histogramme et, pour chaque intervalle, de compter le nombre de pixels dont la couleur se situe dans cet intervalle. Par exemple, considérons l'histogramme "vert", et supposons que nous choisissions 4 intervalles pour notre histogramme : 0-63, 64-127, 128-191, et 192-255. Ensuite, pour chaque pixel, nous examinons la valeur du vert et ajoutons un pointage à la case appropriée. Lorsque nous avons terminé, nous divisons le total de chaque case par le nombre de pixels de l'image entière pour obtenir un histogramme normalisé pour le canal vert.

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

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

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

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

pour chaque case de l'histogramme vert, et répétez l'opération pour les autres histogrammes, puis additionnez tous les résultats. Plus le résultat est petit, plus la correspondance est bonne. 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 souhaiterez probablement définir un seuil au-delà duquel l'algorithme conclura qu'aucune correspondance n'a été trouvée.

---

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

Une troisième approche qui est probablement beaucoup plus rapide que les deux autres consiste à utiliser Texte sémantique sur les forêts (PDF). Il s'agit d'extraire des points clés simples et d'utiliser une collection d'arbres de décision pour classer l'image. Cette méthode est plus rapide que la simple correspondance des points clés SIFT, car elle évite le coûteux processus de correspondance, et les points clés sont beaucoup plus simples que la méthode SIFT, de sorte que l'extraction des points clés est beaucoup plus rapide. Cependant, elle préserve l'invariance de la méthode SIFT à la rotation, à l'échelle et à l'éclairage, une caractéristique importante que la méthode de l'histogramme n'avait pas.

Mise à jour :

Je me suis trompé : l'article sur les forêts sémantiques de textures ne traite pas spécifiquement de la correspondance d'images, mais plutôt de l'étiquetage de régions. L'article original qui traite de la correspondance est celui-ci : Reconnaissance de points clés à l'aide d'arbres aléatoires . En outre, les articles ci-dessous continuent de développer les idées et représentent l'état de l'art (c. 2010) :

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

Answer 2

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 à l'adresse suivante :

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 du fichier image original et en hachant une représentation compacte de ces caractéristiques (plutôt que de hacher directement les données de l'image). Cela signifie que le taux de faux positifs est beaucoup plus faible qu'avec une approche simpliste telle que la réduction des images à une image de la taille d'une empreinte de pouce et la comparaison des empreintes de pouce.

phash offre plusieurs types de hachage et peut être utilisé pour les images, l'audio ou la vidéo.

Answer 3

Ce post a été le point de départ de ma solution, beaucoup de bonnes idées ici, alors j'ai pensé que je pourrais 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 les 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 mieux adapté à certains types de transformations d'images et vous pouvez en tirer parti.

En haut, les algorithmes les plus rapides ; en bas, les plus lents (mais plus précis). Vous pouvez ignorer les algorithmes lents si vous trouvez une bonne correspondance au niveau le plus rapide.

• basé sur le hachage des fichiers (md5, sha1, etc.) pour les doublons exacts
• hachage perceptuel (phash) pour les images remises à l'échelle
• basé sur les caractéristiques (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. Elle n'est pas bonne pour les images modifiées (perceptuellement) (recadrées, tournées, reflétées, etc.). Pour gérer la vitesse de hachage, nous devons utiliser un cache disque/base de données pour maintenir les hachages de la meule de foin.

Ce qui est vraiment bien avec phash, c'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 tenir toute la base de données de hachage en mémoire. C'est assez pratique puisqu'un hash ne fait que 8 octets.

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

Pour les images modifiées/cadrées, il semblerait qu'un détecteur de caractéristiques/de points clés invariant par transformation comme SIFT soit la solution. SIFT produira de bons points clés qui permettront de détecter les recadrages, les rotations, les miroirs, etc. Cependant, la comparaison des descripteurs est très lente par rapport à la distance de Hamming utilisée par Phash. C'est une limitation majeure. Il y a beaucoup de comparaisons à faire, puisqu'il y a un maximum de IxJxK comparaisons de descripteurs pour rechercher une image (I=nombre d'images de botte de foin, J=points clés cibles par image de botte de foin, K=points clés cibles par image d'aiguille).

Pour contourner le problème de vitesse, j'ai essayé d'utiliser le phash autour de chaque point clé trouvé, en utilisant la taille/rayon de l'élément pour déterminer le sous-rectangle. L'astuce pour que cela fonctionne bien, est d'augmenter/réduire le rayon pour générer différents niveaux de sous-rectangle (sur l'image de l'aiguille). En général, le premier niveau (non mis à l'échelle) correspond, mais il en faut souvent plusieurs. Je ne suis pas sûr à 100% de la raison pour laquelle cela fonctionne, mais j'imagine que cela permet d'obtenir des caractéristiques trop petites pour que phash puisse fonctionner (phash met à l'échelle les images jusqu'à 32x32).

Un autre problème est que SIFT ne distribue pas les points clés de manière optimale. Si une section de l'image comporte beaucoup de bords, les points clés s'y regrouperont et vous n'en aurez 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 mettre à l'échelle toutes les images de la botte de foin (et de l'aiguille) à une taille plus petite avant la détection des caractéristiques (j'utilise 210px 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 permettra également de concentrer le détecteur sur les caractéristiques les plus saillantes.

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 100px). Le détecteur de visage prend en compte plusieurs niveaux d'échelle (en utilisant des pyramides) mais il y a une limite au nombre de niveaux qu'il utilisera (ceci est réglable bien sûr).

Le détecteur de points clés fonctionne probablement mieux lorsqu'il renvoie moins que le nombre de caractéristiques souhaitées. Par exemple, si vous demandez 400 et obtenez 300, c'est bien. Si vous obtenez 400 à chaque fois, il est probable que de bonnes caractéristiques ont dû être écartées.

L'image de l'aiguille peut avoir moins de points clés que les images de la botte de foin et obtenir quand même de bons résultats. L'ajout de points clés ne permet pas nécessairement d'obtenir des gains énormes. 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 qu'à 96%.

Nous pouvons tirer parti de l'extrême rapidité de la fonction de Hamming pour résoudre les problèmes de mise à l'échelle, de rotation, de mise en miroir, etc. Une technique à passages multiples peut être utilisée. À chaque itération, on transforme les sous-rectangles, on les remet en mémoire et on exécute à nouveau la fonction de recherche.

Answer 4

C'est un beau problème que de chercher le openCV bibliothèque...

Je pense que pour détecter des images similaires mais non égales, vous devriez essayer une combinaison d'algorithmes d'analyse d'image (histogrammes et autres).

Answer 5

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

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