Comparaison d'images, - un algorithme rapide

je cherche à créer une table de base d'images et puis comparer toutes les nouvelles images par rapport à cela 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 100's de fois, vous pouvez stocker une copie de celui-ci et fournir des liens de référence à elle. Lorsqu'une nouvelle image est enregistrée, vous voulez comparer à une image existante pour s'assurer qu'il n'est pas un doublon ... des idées?

One l'idée de la mienne était de réduire à une petite vignette et puis choisir au hasard 100 emplacements pixels et comparer.

353
demandé sur Chuck Savage 2009-05-10 00:18:18

8 réponses

ci-dessous sont trois approches pour résoudre ce problème (et il ya beaucoup d'autres).

  • la première est une approche standard de la vision par ordinateur, l'appariement des touches. Cela peut exiger des connaissances de base pour la mise en œuvre, et peut être lent.

  • la deuxième méthode n'utilise que le traitement d'image élémentaire, et est potentiellement plus rapide que la première approche, et est simple à mettre en œuvre. Cependant, ce qu'il gagne en intelligibilité, il manque de Robustesse -- l'appariement échoue sur des images graduées, tournées ou décolorées.

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

Point-Clé D'Appariement

mieux que de choisir 100 points au hasard est de choisir 100 important points. Certaines parties d'une image ont plus d'information que d'autres (particulièrement aux bords et aux coins), et ce sont celles que vous voudrez utiliser pour faire des correspondances d'image intelligentes. Google " extraction de point de clé " et " correspondance point de clé " et vous trouverez un bon nombre de documents universitaires sur le sujet. Ces jours-ci, SIFT keypoints sont sans doute les plus populaires, car ils peuvent correspondre images sous différentes échelles, rotations, et l'éclairage. Certaines implémentations de SIFT peuvent être trouvées ici .

Un inconvénient à tazoult correspondant est le temps d'exécution d'une implémentation naïve: O(n^2 m), où n est le nombre de keypoints 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 quadtrees ou partitionnement de l'espace binaire.


solution Alternative: histogramme méthode

une autre solution moins robuste mais potentiellement plus rapide consiste à construire des histogrammes caractéristiques pour chaque image, et de choisir l'image avec l'histogramme le plus proche de l'histogramme de l'image d'entrée. J'ai mis en œuvre ceci comme un undergrad, et nous avons utilisé 3 histogrammes de couleur (rouge, vert et bleu), et deux histogrammes de texture, la direction et l'échelle. Je vais donner les détails ci-dessous, mais je dois noter que cela n'a bien fonctionné que pour apparier des images très similaires aux images de la base de données. Re-mise à l'échelle, rotation, ou décolorée, les images peuvent échouer avec cette méthode, mais de petits changements, comme le cadrage de ne pas casser l'algorithme

le calcul des histogrammes de couleur est simple -- il suffit de choisir la plage pour vos seaux d'histogrammes, et pour chaque plage, compter le nombre de pixels avec une couleur dans cette plage. Par exemple, considérons l'histogramme "vert", et supposons que nous choisissions 4 seaux pour notre histogramme: 0-63, 64-127, 128-191, et 192-255. Puis pour chaque pixel, on regarde la valeur verte, et ajouter un compte approprié seau. Quand nous avons fini de compter, 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 direction de 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 en l'un des 6 seaux entre 0 et PI (puisque les bords ont une symétrie à 180 degrés, nous avons converti les angles entre-PI et 0 pour être entre 0 et PI). Après avoir additionné 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ée en divisant chaque seau par le nombre total de points de bord dans l'image.

pour calculer l'histogramme de l'échelle de texture, pour chaque point de bordure, nous avons mesuré la distance au point de bordure le plus proche avec le 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 une déviation raisonnable). Après avoir calculé cette distance pour chaque point de bord, nous plaçons ces valeurs dans un histogramme et nous les normalisons en les divisant par le nombre total de points de bord.

Maintenant vous avez 5 histogrammes pour chaque image. Pour comparer deux images, on prend la valeur absolue de la différence entre chaque série d'histogrammes, puis additionner ces valeurs. Par exemple, pour comparer les images A et B, on calculerait

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

pour chaque seau dans l'histogramme vert, et répéter pour les autres histogrammes, puis résumer tous les résultats. Le plus petit, le résultat, le meilleur le match. Répéter pour toutes les images dans la base de données, et le match avec le plus petit résultat gagne. Vous voulez probablement avoir un seuil, au-dessus duquel l'algorithme conclut que non la correspondance 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 est d'utiliser les forêts de texton sémantiques (PDF). Il s'agit d'extraire des points de saisie simples et d'utiliser un arbre de décision pour classer l'image. Ceci est plus rapide que la simple correspondance de point de clé SIFT, parce qu'il évite la correspondance coûteuse processus, et les points de frappe sont beaucoup plus simples que SIFT, de sorte que l'extraction de point de frappe 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 que la méthode histogram a manqué.

mise à Jour :

mon erreur -- le papier sémantique Texton Forests n'est pas spécifiquement sur l'appariement d'image, mais plutôt sur l'étiquetage de la région. Le papier original qui fait correspondre est celui-ci: point-clé de la Reconnaissance à l'aide de Randomisée Arbres . En outre, les documents ci-dessous continuent de développer les idées et de représenter l'état de la technique (C. 2010):

411
répondu Kyle Simek 2016-07-21 11:44:15

la meilleure méthode que je connaisse est d'utiliser un hachage perceptuel. Il semble y avoir une bonne mise en œuvre open source d'un tel hachage disponible à:

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 traits saillants dans le fichier image original et en hachant une représentation compacte de ces traits (plutôt que de hachage des données d'image directement). Cela signifie que le taux de faux positifs est considérablement réduit par une approche simpliste telle que la réduction des images à une image minuscule de la taille d'une empreinte du pouce et la comparaison des empreintes du pouce.

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

70
répondu redcalx 2011-11-09 22:17:32

ce post a été le point de départ de ma solution, beaucoup de bonnes idées ici donc je pensais que je partagerais mes résultats. L'idée principale est que j'ai trouvé un moyen de contourner la lenteur de la correspondance d'image basée sur les points de frappe 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, les plus lents (bien que plus précis). Vous pouvez ignorer les lentes si une correspondance est trouvée au plus vite.

  • fichier-hachage basé (md5, sha1, etc) pour les doublons exacts
  • perceptuel de hachage (phash) pour le redimensionnement des images
  • fonction (EIPD) pour des images modifiées

je suis d'avoir un très bon résultats avec phash. La précision est bonne pour les images rééchelonnées. Il n'est pas bon pour les images modifiées (perceptuellement) (recadré, tourné, miroir, etc.). Pour gérer la vitesse de hachage, nous devons employer un cache de disque/base de données pour maintenir les hachures pour la meule de foin.

ce qui est vraiment bien à propos de phash, c'est qu'une fois que vous avez créé votre base de données de hachage (qui pour moi est d'environ 1000 images/seconde), les recherches peuvent être très, très rapides, en particulier lorsque vous pouvez tenir l'ensemble de la base de données de hachage dans mémoire. C'est assez pratique car un hachage n'est que de 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 CPU, cela correspond au cache L2/L3! Dans la pratique, j'ai vu un corei7 comparer à plus de 1 Giga-hamm/sec, c'est seulement une question de bande passante de mémoire au CPU. Une base de données d'un milliard d'images est pratique sur un CPU 64 bits (8 Go de RAM nécessaire) et les recherches ne dépasseront pas 1 seconde!

pour les images modifiées / recadrées, il semblerait qu'une fonction invariante de transformation/un détecteur de point de touche comme SIFT soit la voie à suivre. SIFT produira de bons points de frappe qui détecteront crop / rotate/mirror etc. Cependant, le descripteur Comparer est très lent par rapport à la distance de martelage utilisé par phash. C'est une limitation majeure. Il y a beaucoup de comparaisons à faire, car il y a un descripteur ixjxk maximum qui se compare à une image de recherche (I = num haystack images, J= target keypoints per haystack image, K = target points de frappe par image d'aiguille).

pour contourner le problème de vitesse, j'ai essayé d'utiliser phash autour de chaque point de touche trouvé, en utilisant la taille Caractéristique/rayon pour déterminer le sous-rectangle. L'astuce pour que cela fonctionne bien, est de pousser/rétrécir le rayon pour générer différents niveaux de sous-rect (sur l'image de l'aiguille). Généralement le premier niveau (non ajustée) correspondent cependant, souvent, il prend un peu plus. Je ne suis pas sûr à 100% pourquoi cela fonctionne, mais je peux imaginer qu'il permet des fonctionnalités qui sont trop petites pour que phash fonctionne (phash réduit les images à 32x32).

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

You il est probable que vous voulez réduire la taille de toutes les images de meule 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 permettra de réduire le bruit dans l'image (toujours un problème pour les algorithmes de vision d'ordinateur), sera également focalisé détecteur sur les caractéristiques plus proéminentes.

pour les images de personnes, vous pouvez essayer la détection de visage et de l'utiliser pour déterminer la taille de l'image à l'échelle et la taille de la grille (par exemple la plus grande face à l'échelle d'être 100px). Caractéristique le détecteur 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 point de frappe fonctionne probablement mieux lorsqu'il renvoie moins de fonctions que le nombre que vous vouliez. Par exemple, si vous demandez 400 et obtenez 300 de retour, c'est bien. Si vous obtenez 400 de retour à chaque fois, probablement quelques bonnes fonctionnalités ont dû être laissées de côté.

l'image de l'aiguille peut avoir moins de points les images de meule de foin et encore obtenir de bons résultats. Ajouter plus ne vous procure pas nécessairement 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 succès ne monte qu'à 96%.

nous pouvons profiter de la vitesse extrême de la fonction de martelage pour résoudre l'échelle, la rotation, le miroir, etc. Une technique de passes multiples peut être utilisée. À chaque itération, transformez les sous-rectangles, ré-hachez et relancez la fonction de recherche.

24
répondu wally 2013-12-01 20:21:32

j'ai une idée, qui peut travailler et elle est plus susceptible d'être très rapide. Vous pouvez sous-échantillonner une image pour dire 80x60 résolution ou comparable, et la convertir en niveau de gris (après le sous-échantillonnage, il sera plus rapide). Traitez les deux images que vous voulez comparer. Ensuite, exécutez la somme normalisée des différences carrées entre deux images (l'image de requête et chacune de la base de données).), ou encore, une corrélation croisée normalisée, qui donne une réponse plus proche de 1, si les deux images sont similaires. Alors si les images sont similaires vous pouvez passer à des techniques plus sophistiquées pour vérifier que c'est la même image. Évidemment, cet algorithme est linéaire en termes de nombre d'images dans votre base de données donc, même si elle va être très rapide jusqu'à 10 000 images par seconde sur du matériel moderne. Si vous avez besoin d'invariance à la rotation, alors un gradient dominant peut être calculé pour cette petite image, et puis tout le système de coordonnées peut être tourné à canonique orientation, cependant, sera plus lent. Et non, il n'est pas l'invariance à l'échelle ici.

si vous voulez quelque chose de plus général ou en utilisant de grandes bases de données (millions d'images), puis vous devez examiner la théorie de récupération d'image (charges de documents sont apparus dans les 5 dernières années). Il y a quelques conseils dans d'autres réponses. Mais c'est peut-être exagéré, et l'approche suggérée par l'histogramme fera l'affaire. Bien que je pense combinaison de beaucoup de différents approche rapide sera encore mieux.

6
répondu Denis C 2009-06-11 21:22:11

comme cartman l'a fait remarquer, vous pouvez utiliser n'importe quelle valeur de hachage pour trouver des doublons exacts.

un point de départ pour trouver des images rapprochées pourrait être ici . C'est un outil utilisé par les CG entreprises pour vérifier si remanié images montrent toujours essentiellement la même scène.

5
répondu Tobiesque 2009-05-09 20:47:03

je crois que le fait de ramener la taille de l'image à une taille presque icône, disons 48x48, puis de passer à l'échelle de gris, puis de prendre la différence entre les pixels, ou Delta, devrait bien fonctionner. Parce que nous comparons le changement de la couleur du pixel, plutôt que la couleur réelle du pixel, cela n'a pas d'importance si l'image est légèrement plus claire ou plus foncée. Les grands changements seront importants car les pixels qui deviennent trop clairs / sombres seront perdus. Vous pouvez appliquer ceci sur une rangée, ou autant que vous voulez augmenter exactitude. Tout au plus 47 x 47=2 209 soustractions à effectuer pour former une clé comparable.

4
répondu Tanoshimi 2011-11-05 13:04:01

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

vous pourriez essayer de les rendre minuscules, puis si elles sont la même effectuer une autre comparaison sur une plus grande taille - pourrait être une bonne combinaison de la vitesse et de la précision...

3
répondu HarryM 2009-05-09 20:31:03

si vous avez un grand nombre d'images, regardez dans un filtre de fleur , qui utilise des hachures multiples pour un résultat probabliste mais efficace. Si le nombre d'images n'est pas énorme, puis un hachage cryptographique comme md5 devrait être suffisant.

2
répondu jdigital 2009-05-09 20:26:42