Algorithme pour comparer deux images

ce sont simplement des idées que j'ai eu en pensant au problème, jamais essayé mais j'aime penser à des problèmes comme celui-ci!

avant de commencer

envisager de normaliser les images, si l'une est une résolution plus élevée que l'autre, envisager l'option que l'un d'entre eux est une version compressée de l'autre, donc réduire la résolution pourrait fournir des résultats plus précis.

considérer balayage de diverses zones prospectives de l'image qui pourraient représenter des portions agrandies de l'image et diverses positions et rotations. Il commence à devenir délicat si une des images est une version biaisée d'une autre, ce sont le genre de limitations que vous devriez identifier et de compromis sur.

Matlab est un excellent outil pour tester et évaluer les images.

test des algorithmes

vous devez tester (au minimum) un grand ensemble de données d'essai analysées chez l'humain où les correspondances sont connues à l'avance. Si par exemple dans vos données de test vous avez 1.000 images où 5% d'entre elles correspondent, vous avez maintenant un benchmark raisonnablement fiable. Un algorithme qui trouve 10% de résultats positifs n'est pas aussi bon qu'un algorithme qui trouve 4% de résultats positifs dans nos données d'essai. Cependant, un algorithme peut trouver toutes les correspondances, mais aussi avoir un taux important de faux positifs de 20%, donc il y a plusieurs façons d'évaluer votre algorithme.

les données d'essai doivent être conçues pour couvrir le plus grand nombre possible de types de dynamique que l'on peut s'attendre à trouver dans le monde réel.

il est important de noter que chaque algorithme pour être utile doit effectuer mieux que la supposition aléatoire, sinon il est inutile pour nous!

vous pouvez alors appliquer votre logiciel dans le monde réel d'une manière contrôlée et commencer à analyser les résultats qu'il produit. C'est le sorte de projet de logiciel qui peut aller de l'avant pour infinitum, Il ya toujours des modifications et des améliorations que vous pouvez faire, il est important de garder cela à l'esprit lors de la conception, car il est facile de tomber dans le piège du projet sans fin.

Seaux De Couleur

avec deux images, numérisez chaque pixel et comptez les couleurs. Par exemple, vous pouvez avoir les 'seaux':

white
red
blue
green
black

(évidemment vous auriez un la plus haute résolution de compteurs). Chaque fois que vous trouvez un pixel "rouge", vous incrémentez le compteur rouge. Chaque godet peut être représentatif du spectre de couleurs, la plus haute résolution est la plus précise, mais vous devriez expérimenter avec un taux de différence acceptable.

une fois que vous avez vos totaux, comparez-les aux totaux pour une deuxième image. Vous pourriez trouver que chaque image a une empreinte assez unique, assez pour identifier les correspondances.

Edge détection

Que Diriez-vous d'utiliser Edge Detection . alt text http://upload.wikimedia.org/wikipedia/en/thumb/8/8e/EdgeDetectionMathematica.png/500px-EdgeDetectionMathematica.png

avec deux images similaires de détection de bord devrait vous fournir une empreinte unique utilisable et assez fiable.

prendre les deux photos, et appliquer la détection de bord. Peut-être mesurer la l'épaisseur moyenne des bords et ensuite calculer la probabilité que l'image pourrait être scalée, et rééchelonner si nécessaire. Ci-dessous un exemple d'un Gabor Filter (un type de détection de bord) appliqué dans diverses rotations.

comparez les images pixel pour pixel, comptez les correspondances et les non correspondances. S'ils sont dans un certain seuil d'erreur, vous avez une correspondance. Sinon, vous pourriez essayer réduire la résolution jusqu'à un certain point et voir si la probabilité d'une correspondance s'améliore.

régions D'intérêt

certaines images peuvent présenter des segments/régions d'intérêt distincts. Ces régions probablement contraste fortement avec le reste de l'image, et sont un bon point pour rechercher dans vos autres images pour trouver des correspondances. Prenez cette image par exemple:

alt texte http://meetthegimp.org/wp-content/uploads/2009/04/97.jpg

le travailleur de la construction en bleu est une région d'intérêt et peut être utilisé comme un objet de recherche. Il y a probablement plusieurs façons d'extraire des propriétés/données de cette région d'intérêt et de les utiliser pour rechercher votre ensemble de données.

Si vous avez plus de 2 régions d'intérêt, vous pouvez mesurer les distances entre eux. Prenez cet exemple simplifié:

alt texte http://www.per2000.eu/assets/images/3_dots_black_03.jpg

nous avons 3 régions claires d'intérêt. La distance entre la Région 1 et 2 peut être de 200 pixels, entre 1 et 3 400 pixels, et 2 et 3 200 pixels.

rechercher d'autres images pour des régions similaires d'intérêt, normaliser les valeurs de distance et voir si vous avez des correspondances potentielles. Cette technique pourrait bien fonctionner pour les images tournées et à l'échelle. Le plus de régions de l'intérêt que vous avez, la probabilité d'une correspondance augmente que chaque mesure de distance correspond.

il est important de penser au contexte de votre ensemble de données. Si, par exemple, votre ensemble de données est de l'art moderne, alors les régions d'intérêt fonctionneraient très bien, puisque les régions d'intérêt étaient probablement conçues pour être une partie fondamentale de l'image finale. Toutefois, si vous travaillez avec des images de chantiers de construction, les régions d'intérêt peuvent être interprétées par le copieur illégal est laid et peut être recadré/édité libéralement. Gardez à l'esprit les caractéristiques communes de votre ensemble de données et tentez d'exploiter ces connaissances.

Morphing

Morphing les deux images est le processus de transformation d'une image à l'autre à travers un ensemble d'étapes:

Note, c'est différent de dégrader une image en de l'autre!

il existe de nombreux progiciels qui peuvent transformer des images. Il est traditionnellement utilisé comme un effet de transition, deux images ne se métamorphosent pas en quelque chose à mi-chemin habituellement, un extrême se transforme en l'autre extrême comme le résultat final.

Pourquoi cela pourrait-il être utile? Selon l'algorithme de morphing que vous utilisez, il peut y avoir une relation entre la similarité des images et certains paramètres de l'algorithme de morphing.

dans un grossièrement sur exemple simplifié, un algorithme pourrait exécuter plus rapidement quand il y a moins de changements à faire. Nous savons alors qu'il y a une plus grande probabilité que ces deux images partagent des propriétés l'une avec l'autre.

Cette technique pourrait bien travailler pour la rotation, faussée, biaisée, gros plan, tous les types d'images copiées. Encore une fois, c'est juste une idée que j'ai eue, elle n'est pas basée sur des recherches universitaires autant que je suis au courant (je n'ai pas cherché à fond cependant), donc il peut être beaucoup de travail pour vous avec peu/pas de résultats.

Fermeture À Glissière

la réponse D'Ow à cette question est excellente, je me souviens avoir lu sur ces techniques d'étude de L'IA. Il est très efficace pour comparer les lexiques du corpus.

une optimisation intéressante lors de la comparaison de corps est que vous pouvez supprimer les mots considérés comme trop communs, par exemple "le", "A", " et " etc. Ces mots diluent notre résultat, nous voulons travailler sur la façon dont les deux corpus sont différents afin qu'ils puissent être enlevés avant le traitement. Peut-être y a-t-il des signaux communs similaires dans les images qui pourraient être supprimés avant la compression? Il pourrait être intéressant de regarder dans.

taux de Compression est un moyen très rapide et raisonnablement efficace de déterminer comment deux ensembles de données similaires sont. La lecture de comment compression vous donnera une bonne idée de pourquoi cela pourrait être efficace. Pour un rapide communiqué de l'algorithme ce serait probablement un bon point de départ.

transparence

encore une fois, je ne sais pas comment les données de transparence est stocké pour certains types d'image, gif png etc, mais ce sera extractible et servirait de découpage simplifié efficace pour comparer avec vos ensembles de données transparence.

Signaux Inverseurs

An l'image n'est qu'un signal. Si vous jouez un bruit d'un haut-parleur, et vous jouez le bruit opposé dans un autre haut-parleur en parfaite synchronisation au même volume exact, ils annulent l'un l'autre.

alt texte http://www.themotorreport.com.au/wp-content/uploads/2008/07/noise-cancellation.gif

inversez les images et ajoutez-les à votre autre image. Mettez à l'échelle les positions it/loop de façon répétitive jusqu'à ce que vous trouviez une image résultante où suffisamment de pixels sont blancs ou noir? Je vais l'appeler une toile neutre) pour vous fournir une correspondance positive,ou partielle.

cependant, considérez deux images qui sont égales, sauf que l'une d'elles a un effet lumineux appliqué à elle:

de l'Inversion de l'un d'eux, puis l'ajouter à l'autre ne sera pas neutre toile, qui est ce que nous visons. Cependant, lorsque l'on compare les pixels à partir des deux images originales, nous pouvons certainement voir une relation claire entre les deux.

Je n'ai pas étudié la couleur depuis quelques années maintenant, et je ne suis pas sûr si le spectre de couleur est sur une échelle linéaire, mais si vous avez déterminé le facteur moyen de différence de couleur entre les deux images, vous pouvez utiliser cette valeur pour normaliser les données avant de traiter avec cette technique.

l'Arbre de structures de Données

à d'abord, elles ne semblent pas adaptées au problème, mais je pense qu'elles pourraient fonctionner.

vous pourriez penser à extraire certaines propriétés d'une image (par exemple des boîtes de couleur) et générer un arbre huffman ou une structure de données similaire. Vous pourriez être en mesure de comparer deux arbres pour la similitude. Cela ne fonctionnerait pas bien pour les données photographiques, par exemple avec un large spectre de couleurs, mais des dessins animés ou d'autres images en couleurs réduites cela pourrait fonctionner.

ça ne marcherait probablement pas, mais c'est une idée. La structure de données de trie est excellente pour stocker des lexiques, par exemple une dictionarty. C'est un préfixe de l'arbre. Peut-être est-il possible de construire un équivalent image d'un lexique, (encore une fois, je ne pense qu'aux couleurs) pour construire un tri. Si vous réduisez par exemple une image 300x300 en carrés de 5x5, puis décomposez chaque carré de 5x5 en une séquence de couleurs, vous pourriez construire un trie à partir des données résultantes. Si un 2x2 square contient:

FFFFFF|000000|FDFD44|FFFFFF

nous avons un code de tri assez unique qui étend 24 niveaux, augmentant/diminuant les niveaux (c'est-à-dire réduisant/augmentant la taille de notre sous-carré) peut produire des résultats plus précis.

comparer les arbres de tries devrait être raisonnablement facile, et pourrait fournir des résultats efficaces.

plus d'idées

j'ai trébuché sur un papier intéressant breif à propos de classification des images satellitaires , il précise:

Les mesures de Texture

sont les suivantes: matrices de cooccurrence, différences de niveaux de gris, analyse texture-ton, caractéristiques dérivées du spectre de Fourier et filtres Gabor. Certaines caractéristiques de Fourier et certains filtres Gabor se sont avérés être de bons choix, en particulier lorsqu'une seule bande de fréquences était utilisée pour la classification.

il peut être il vaut la peine d'examiner ces mesures plus en détail, bien que certaines d'entre elles ne soient pas pertinentes pour votre ensemble de données.

autres éléments à prendre en considération

il y a probablement beaucoup de papiers sur ce genre de choses, donc la lecture de certains d'entre eux devrait aider bien qu'ils puissent être très technique. Il s'agit d'un domaine extrêmement difficile en informatique, avec de nombreuses heures de travail infructueuses passées par de nombreuses personnes qui tentent de faire des choses similaires. Keeping la meilleure façon de procéder serait de s'appuyer sur ces idées. Il doit être assez difficile de créer un algorithme de mieux qu'au hasard, et pour commencer à améliorer sur qui n'a vraiment commencer à devenir très difficile à atteindre.

chaque méthode devrait probablement être testé et modifié à fond, si vous avez des informations sur le type d'image que vous allez vérifier aussi, ce serait utile. Par exemple, des publicités, beaucoup de ils auraient du texte dans eux, donc faire la reconnaissance de texte serait un moyen facile et probablement très fiable de trouver des correspondances en particulier lorsqu'il est combiné avec d'autres solutions. Comme mentionné précédemment, tentative d'exploiter les propriétés communes de votre ensemble de données.

combiner des mesures et des techniques alternatives Chaque qui peut avoir un vote pondéré (dépendant de leur efficacité) serait une façon de créer un système qui génère des résultats plus précis.

si vous utilisez plusieurs algorithmes, comme mentionné au début de cette réponse, on peut trouver tous les positifs mais avoir un taux de faux positifs de 20%, Il serait intéressant d'étudier les propriétés/forces/faiblesses d'autres algorithmes car un autre algorithme peut être efficace pour éliminer les faux positifs retournés d'un autre.

attention de ne pas tomber dans la tentative de compléter le projet sans fin, bonne chance!

lire le papier: Porikli, Fatih, Oncel Tuzel, et Peter Meer. "La Covariance De Suivi En Utilisant Le Modèle Mis À Jour En Fonction sur Moyens sur Riemannienne Collecteurs". (2006) de l'IEEE de la Vision par Ordinateur et Reconnaissance de formes.

j'ai réussi à détecter des régions se chevauchant dans des images capturées à partir de webcams adjacents en utilisant la technique présentée dans cet article. Ma matrice de covariance était composée de Sobel, canny et SUSAN. sorties de détection d'aspect/bord, ainsi que les pixels à l'échelle de gris d'origine.

Une idée:

1. utilisez des détecteurs de points de saisie pour trouver des descripteurs invariants d'échelle et de transformation de certains points de l'image (par exemple SIFT, SURF, GLOH ou LESH).
2. essayer d'aligner les points de touches avec des descripteurs similaires des deux images (comme dans la couture panorama), prévoir quelques transformations d'image si nécessaire (par exemple échelle & rotation, ou étirement élastique).
3. si beaucoup de points de touches s'alignent bien (existe une telle transformation, que erreur d'alignement du point de saisie est faible; ou "énergie" de transformation est faible,etc.), vous avez probablement des images similaires.

L'Étape 2 n'est pas anodine. En particulier, vous pouvez avoir besoin d'utiliser un algorithme intelligent pour trouver les plus similaires tazoult sur l'autre image. Les descripteurs de points sont habituellement très dimensionnels (comme une centaine de paramètres), et il y a de nombreux points à examiner. KD-arbres peut être utile ici, les recherches de hachage ne fonctionnent pas bien.

variantes:

• détecter les arêtes ou autres caractéristiques au lieu de points.

c'est en effet beaucoup moins simple qu'il n'y paraît :-) la suggestion de Nick est bonne.

pour commencer, gardez à l'esprit que toute méthode de comparaison valable fonctionnera essentiellement en convertissant les images dans une forme différente -- une forme qui rend plus facile de choisir des caractéristiques similaires. D'habitude, ces trucs ne sont pas très faciles à lire ...





Un des exemples les plus simples que je puisse penser, c'est tout simplement en utilisant l'espace de couleur de chaque image. Si deux images très similaires distributions de couleur, alors vous pouvez être raisonnablement sûr qu'ils montrent la même chose. Au moins, vous pouvez avoir assez de certitude pour le signaler, ou faire plus de tests. Comparer des images dans l'espace de couleur résistera également à des choses telles que la rotation, l'échelle, et certains recadrage. Il ne résistera pas, bien sûr, à une modification lourde de l'image ou à une recoloration lourde (et même un simple changement de teinte sera quelque peu délicat).

http://en.wikipedia.org/wiki/RGB_color_space

http://upvector.com/index.php?section=tutorials&subsection=tutorials/colorspace

un autre exemple concerne quelque chose appelé la transformation de Hough. Cette transformation se décompose essentiellement une image en un ensemble de lignes. Vous pouvez alors prendre de l' les lignes 'strongest' dans chaque image et voir si elles s'alignent. Vous pouvez faire un peu de travail supplémentaire pour essayer de compenser la rotation et la mise à l'échelle aussi -- et dans ce cas, puisque comparer quelques lignes est beaucoup moins de travail de calcul que de faire la même chose pour des images entières -- ce ne sera pas si mal.

http://homepages.inf.ed.ac.uk/amos/hough.html

http://rkb.home.cern.ch/rkb/AN16pp/node122.html

http://en.wikipedia.org/wiki/Hough_transform

Vous aurez besoin d'utiliser un filigrane régime d'intégrer un code dans l'image. Pour prendre un peu de recul, contrairement à certaines approches de bas niveau (détection de bord, etc.) suggérées par certains, une méthode de filigrane est supérieure parce que:

il est résistant aux attaques de traitement de Signal ► Amélioration du Signal-affûtage, contraste, etc. ► Filtrage-médiane, passe basse, passe haute, etc. ► Bruit additif-gaussien, uniforme, etc. ► Compression avec perte-JPEG, MPEG, etc.

il résiste aux attaques géométriques ► Affine se transforme ► Réduction des données-culture, découpage, etc. ► Distorsions locales aléatoires ► Gauchissement 151910920"

faites quelques recherches sur les algorithmes de filigrane et vous serez sur la bonne voie pour résoudre votre problème. ( Note: vous pouvez comparer votre méthode en utilisant l'ensemble de données STIRMARK . C'est une norme acceptée pour ce type d'application.

c'est juste une suggestion, ça ne marchera peut-être pas et je suis prêt à être appelé là-dessus.

cela générera des faux positifs, mais avec un peu de chance pas de faux négatifs.

1. redimensionnez les deux images de façon à ce qu'elles aient la même taille (je suppose que les rapports largeur / longueur sont les mêmes dans les deux images).

2. compresser une image bitmap des deux images avec une compression sans perte algorithme (par exemple gzip).

3. trouver des paires de fichiers qui ont des tailles similaires. Par exemple, vous pourriez juste trier chaque paire de fichiers que vous avez par la façon dont les tailles de fichier sont similaires et de récupérer le haut X.

comme je l'ai dit, cela générera certainement des faux positifs, mais j'espère pas de faux négatifs. Vous pouvez mettre en œuvre cela en cinq minutes, alors que le Porikil et. Al. nécessiterait probablement de travail considérable.

je crois que si vous êtes prêt à appliquer l'approche à toutes les orientations possibles et aux versions négatives, un bon début à la reconnaissance d'image (avec une bonne fiabilité) est d'utiliser des eigenfaces: http://en.wikipedia.org/wiki/Eigenface

une Autre idée serait de transformer les images en vecteurs de leurs composants. Une bonne façon de le faire est de créer un vecteur qui fonctionne en x*y (x étant la largeur de votre image et y étant les hauteur), la valeur de chaque dimension s'appliquant à la valeur du pixel (x,y). Ensuite, exécutez une variante de K-voisins les plus proches avec deux catégories: match et no match. Si elle est suffisamment proche de l'image originale, elle s'insérera dans la catégorie match, sinon elle ne s'insérera pas.

K voisins les plus proches (KNN) peut être trouvé ici, Il ya d'autres bonnes explications de celui-ci sur le web aussi: http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

les avantages de KNN est que plus vous comparez de variantes à l'image originale, plus l'algorithme devient précis. L'inconvénient est que vous avez besoin d'un catalogue d'images pour former le système d'abord.

si vous êtes prêt à envisager une approche totalement différente pour détecter les copies illégales de vos images, vous pourriez envisager filigrane . (de 1.4)

...insère les informations de copyright dans l'objet numérique sans perte de qualité. Chaque fois que l'auteur d'un objet numérique qui est en question, cette information est extraite d'identifier le propriétaire légitime. Il est également possible de coder l'identité de l'original acheteur ainsi que l'identité du détenteur du droit d'auteur, ce qui permet de retracer toute copie non autorisée.

bien qu'il s'agisse également d'un champ complexe, il existe des techniques qui permettent à l'information en filigrane de persister grâce à une altération grossière de l'image: (de 1.9)

... toute transformation de signal d'une puissance raisonnable ne peut enlever le filigrane. Par conséquent, un pirate prêt à supprimer le filigrane ne réussira pas à moins qu'ils ne document trop d'être d'intérêt commercial.

bien sûr, la faq appelle la mise en œuvre de cette approche: "...très difficile", mais si vous réussissez, vous obtenez un niveau de confiance élevé si l'image est une copie ou pas, plutôt qu'un pourcentage de probabilité.

si vous utilisez Linux, je suggère deux outils:

align_image_stack from package hugin-tools - est un programme en ligne de commande qui peut corriger automatiquement la rotation, la mise à l'échelle, et d'autres distorsions (il est principalement destiné à compositing HDR photographie, mais fonctionne pour les cadres vidéo et d'autres documents aussi). Plus d'informations: http://hugin.sourceforge.net/docs/manual/Align_image_stack.html

comparez à partir du paquet imagemagick - un programme qui peut trouver et compter la quantité de pixels différents dans deux images. Voici un joli tutoriel: http://www.imagemagick.org/Usage/compare/ uising l'-fuzz N% vous pouvez augmenter la tolérance à l'erreur. Plus le N est élevé, plus la tolérance d'erreur est élevée.

align_image_stack devrait corriger tout décalage de sorte que la commande compare vraiment avoir une chance de détecter les mêmes pixels.