Étant donné deux fichiers image différents (quel que soit le format que je choisis), je dois écrire un programme pour prédire le risque que l'un soit la copie illégale d'un autre. L'auteur de la copie peut faire des choses comme la rotation, la création de négatifs ou l'ajout de détails triviaux (ainsi que la modification de la dimension de l'image).
Connaissez-vous un algorithme pour faire ce genre de travail?
algorithm
image
image-processing
image-recognition
Salvador Dali
la source
la source
Réponses:
Ce sont simplement des idées que j'ai eues en pensant au problème, je ne l'ai jamais essayé mais j'aime penser à des problèmes comme celui-ci!
Avant que tu commences
Envisagez de normaliser les images, si l'une est une résolution plus élevée que l'autre, envisagez l'option selon laquelle l'une d'elles est une version compressée de l'autre, par conséquent, la réduction de la résolution peut fournir des résultats plus précis.
Envisagez de numériser diverses zones prospectives de l'image qui pourraient représenter des parties agrandies de l'image et diverses positions et rotations. Cela commence à devenir délicat si l'une des images est une version biaisée d'une autre, ce sont le genre de limitations que vous devez identifier et faire des compromis.
Matlab est un excellent outil pour tester et évaluer les images.
Tester les algorithmes
Vous devez tester (au minimum) un grand ensemble de données de test analysées par l'homme où les correspondances sont connues à l'avance. Si, par exemple, dans vos données de test, vous avez 1 000 images dont 5% correspondent, vous disposez désormais d'un benchmark raisonnablement fiable. Un algorithme qui trouve 10% de positifs n'est pas aussi bon qu'un qui trouve 4% de positifs dans nos données de test. Cependant, un algorithme peut trouver toutes les correspondances, mais aussi avoir un taux de faux positifs élevé de 20%, il existe donc plusieurs façons d'évaluer vos algorithmes.
Les données de test doivent essayer d'être conçues pour couvrir autant de types de dynamiques que possible que vous vous attendez à trouver dans le monde réel.
Il est important de noter que chaque algorithme pour être utile doit être plus performant que les devinettes aléatoires, sinon cela nous est inutile!
Vous pouvez ensuite appliquer votre logiciel dans le monde réel de manière contrôlée et commencer à analyser les résultats qu'il produit. C'est le genre de projet logiciel qui peut durer à l'infini, il y a toujours des ajustements et des améliorations que vous pouvez apporter, il est important de garder cela à l'esprit lors de sa conception car il est facile de tomber dans le piège du projet sans fin.
Seaux de couleur
Avec deux images, scannez chaque pixel et comptez les couleurs. Par exemple, vous pourriez avoir les 'buckets':
(Évidemment, vous auriez une résolution de compteurs plus élevée). Chaque fois que vous trouvez un pixel «rouge», vous incrémentez le compteur rouge. Chaque seau peut être représentatif du spectre de couleurs, plus la résolution est élevée, plus elle est précise, mais vous devez expérimenter avec un taux de différence acceptable.
Une fois que vous avez vos totaux, comparez-les aux totaux d'une deuxième image. Vous constaterez peut-être que chaque image a une empreinte assez unique, suffisante pour identifier les correspondances.
Détection des bords
Que diriez-vous d'utiliser la détection de bord . (source: wikimedia.org )
Avec deux images similaires, la détection des contours devrait vous fournir une empreinte unique utilisable et assez fiable.
Prenez les deux photos et appliquez la détection des contours. Peut-être mesurer l'épaisseur moyenne des bords, puis calculer la probabilité que l'image puisse être mise à l'échelle, et redimensionner si nécessaire. Vous trouverez ci-dessous un exemple de filtre Gabor appliqué (un type de détection de bord) dans diverses rotations.
Comparez les images pixel par pixel, comptez les correspondances et les non correspondances. S'ils se trouvent dans un certain seuil d'erreur, vous avez une correspondance. Sinon, vous pouvez essayer de 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 avoir des segments / régions d'intérêt distinctifs. Ces régions contrastent probablement fortement avec le reste de l'image et constituent un bon élément à rechercher dans vos autres images pour trouver des correspondances. Prenons cette image par exemple:
(source: meetthegimp.org )
Le travailleur de la construction en bleu est une région d'intérêt et peut être utilisé comme objet de recherche. Il existe 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 elles. Prenons cet exemple simplifié:
(source: per2000.eu )
Nous avons 3 régions d'intérêt claires. La distance entre les régions 1 et 2 peut être de 200 pixels, entre 1 et 3 400 pixels, et 2 et 3 200 pixels.
Recherchez d'autres images pour des régions d'intérêt similaires, normalisez les valeurs de distance et voyez si vous avez des correspondances potentielles. Cette technique pourrait bien fonctionner pour les images pivotées et mises à l'échelle. Plus vous avez de régions d'intérêt, plus la probabilité d'une correspondance augmente à mesure que chaque mesure de distance correspond.
Il est important de réfléchir 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, car les régions d'intérêt ont probablement été conçues pour être une partie fondamentale de l'image finale. Si toutefois vous avez affaire à des images de chantiers de construction, les régions d'intérêt peuvent être interprétées par le copieur illégal comme laides et peuvent être rognées / éditées généreusement. Gardez à l'esprit les caractéristiques communes de votre ensemble de données et essayez d'exploiter ces connaissances.
Morphing
Le morphing de deux images consiste à transformer une image en une autre en un ensemble d'étapes:
Notez que c'est différent de fondre une image dans une autre!
Il existe de nombreux logiciels capables de transformer des images. Il est traditionnellement utilisé comme effet de transition, deux images ne se transforment généralement pas en quelque chose à mi-chemin, l'une extrême se transforme en l'autre extrême comme résultat final.
Pourquoi cela pourrait-il être utile? En fonction de l'algorithme de morphing que vous utilisez, il peut y avoir une relation entre la similitude des images et certains paramètres de l'algorithme de morphing.
Dans un exemple grossièrement simplifié, un algorithme peut s'exécuter plus rapidement lorsqu'il y a moins de modifications à apporter. On sait alors qu'il y a une probabilité plus élevée que ces deux images partagent des propriétés l'une avec l'autre.
Cette technique pourrait bien fonctionner pour tous les types d'images copiées, tournées, déformées, biaisées, agrandies. Encore une fois, c'est juste une idée que j'ai eue, elle n'est basée sur aucune recherche universitaire pour autant que je sache (je n'ai pas regardé sérieusement), donc cela peut être beaucoup de travail pour vous avec des résultats limités / pas.
Zipping
La réponse d'Ow à cette question est excellente, je me souviens avoir lu ce genre de techniques d'étude de l'IA. Il est assez efficace pour comparer les lexiques de corpus.
Une optimisation intéressante lors de la comparaison des corpus est que vous pouvez supprimer des mots considérés comme trop courants, par exemple «Le», «A», «Et» etc. Ces mots diluent notre résultat, nous voulons déterminer à quel point les deux corpus sont différents afin qu'ils puissent être supprimé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? Cela pourrait valoir la peine d'être examiné.
Le taux de compression est un moyen très rapide et raisonnablement efficace de déterminer à quel point deux ensembles de données sont similaires. Lire comment fonctionne la compression vous donnera une bonne idée de pourquoi cela pourrait être si efficace. Pour un algorithme à diffusion rapide, ce serait probablement un bon point de départ.
Transparence
Encore une fois, je ne suis pas sûr de la façon dont les données de transparence sont stockées pour certains types d'images, gif png, etc., mais cela sera extractible et servirait de découpe simplifiée efficace pour comparer la transparence de vos ensembles de données.
Inversion des signaux
Une image n'est qu'un signal. Si vous diffusez un bruit d'un haut-parleur et que vous jouez le bruit opposé dans un autre haut-parleur en parfaite synchronisation au même volume exact, ils s'annulent.
(source: themotorreport.com.au )
Inversez les images et ajoutez-les à votre autre image. Mettez-le à l'échelle / positionnez en boucle de manière répétitive jusqu'à ce que vous trouviez une image résultante où suffisamment de pixels sont blancs (ou noirs? Je l'appellerai un canevas neutre) pour vous fournir une correspondance positive ou partielle.
Cependant, considérez deux images égales, sauf que l'une d'elles a un effet d'éclat qui lui est appliqué:
(source: mcburrz.com )
Inverser l'un d'eux, puis l'ajouter à l'autre ne donnera pas une toile neutre, ce que nous visons. Cependant, en comparant les pixels des deux images originales, nous pouvons clairement voir une relation claire entre les deux.
Je n'ai pas étudié la couleur depuis quelques années maintenant, et je ne sais pas si le spectre de couleurs 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.
Structures de données arborescentes
Au début, 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 bacs de couleurs) et générer un arbre de Huffman ou une structure de données similaire. Vous pourrez peut-être 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 à jeu de couleurs réduit cela pourrait fonctionner.
Cela ne fonctionnerait probablement pas, mais c'est une idée. La structure de données trie est excellente pour stocker des lexiques, par exemple une dictionarty. C'est un arbre de préfixes. Peut-être est-il possible de construire une image équivalente à un lexique, (encore une fois, je ne peux penser qu'aux couleurs) pour construire un trie. Si vous réduisez par exemple une image 300x300 en carrés 5x5, puis décomposez chaque carré 5x5 en une séquence de couleurs, vous pouvez construire un trie à partir des données résultantes. Si un carré 2x2 contient:
Nous avons un code trie assez unique qui étend 24 niveaux, augmentant / diminuant les niveaux (IE réduisant / augmentant la taille de notre sous-carré) peut donner des résultats plus précis.
La comparaison des trois arbres devrait être raisonnablement facile et pourrait éventuellement donner des résultats efficaces.
Plus d'idées
Je suis tombé sur un article intéressant sur la classification de l'imagerie satellite , il décrit:
Il peut être utile d'étudier ces mesures plus en détail, même si certaines d'entre elles peuvent ne pas être pertinentes pour votre ensemble de données.
Autres choses à considérer
Il y a probablement beaucoup d'articles sur ce genre de choses, donc la lecture de certains d'entre eux devrait aider bien qu'ils puissent être très techniques. C'est 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. Rester simple et s'appuyer sur ces idées serait la meilleure façon de procéder. Ce devrait être un défi raisonnablement difficile de créer un algorithme avec un taux de correspondance meilleur que aléatoire, et commencer à améliorer cela commence vraiment à devenir assez difficile à réaliser.
Chaque méthode devra probablement être testée et peaufinée à fond, si vous avez des informations sur le type d'image que vous vérifierez également, cela serait utile. Par exemple, les publicités, beaucoup d'entre elles contiendraient du texte, de sorte que la reconnaissance de texte serait un moyen facile et probablement très fiable de trouver des correspondances, en particulier lorsqu'elle est combinée avec d'autres solutions. Comme mentionné précédemment, essayez d'exploiter les propriétés communes de votre ensemble de données.
La combinaison de mesures et de techniques alternatives, chacune pouvant avoir un vote pondéré (en fonction 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 employez 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 comme un autre algorithme peut être efficace pour éliminer les faux positifs renvoyés par un autre.
Veillez à ne pas tomber dans la tentative de terminer le projet sans fin, bonne chance!
la source
Lisez l'article: Porikli, Fatih, Oncel Tuzel et Peter Meer. «Suivi de la covariance à l'aide de la mise à jour du modèle basée sur les moyennes sur les manifolds riemanniens». (2006) IEEE Computer Vision and Pattern Recognition.
J'ai réussi à détecter des régions qui se chevauchent dans des images capturées à partir de webcams adjacentes en utilisant la technique présentée dans cet article. Ma matrice de covariance était composée de sorties de détection d'aspect / de bord Sobel, canny et SUSAN, ainsi que des pixels d'origine en niveaux de gris.
la source
Une idée:
L'étape 2 n'est pas anodine. En particulier, vous devrez peut-être utiliser un algorithme intelligent pour trouver le point-clé le plus similaire sur l'autre image. Les descripteurs de points sont généralement de très grande dimension (comme une centaine de paramètres), et il y a de nombreux points à parcourir. Les kd-tree peuvent être utiles ici, les recherches de hachage ne fonctionnent pas bien.
Variantes:
la source
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 sous une forme différente - une forme qui facilite la sélection de fonctionnalités similaires. Habituellement, ce truc ne permet pas une lecture très légère ...
L'un des exemples les plus simples auxquels je puisse penser est simplement d'utiliser l'espace colorimétrique de chaque image. Si deux images ont des distributions de couleurs très similaires, vous pouvez être raisonnablement sûr qu'elles montrent la même chose. Au moins, vous pouvez avoir suffisamment de certitude pour le signaler ou faire plus de tests. La comparaison d'images dans l'espace colorimétrique résiste également à des choses telles que la rotation, la mise à l'échelle et certains recadrages. Il ne résistera bien sûr pas à une modification importante 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 implique quelque chose appelé la transformation de Hough. Cette transformation décompose essentiellement une image en un ensemble de lignes. Vous pouvez ensuite prendre certaines des lignes les plus «fortes» de chaque image et voir si elles s'alignent. Vous pouvez également faire un peu de travail supplémentaire pour essayer de compenser la rotation et la mise à l'échelle - et dans ce cas, puisque comparer quelques lignes est BEAUCOUP moins de travail de calcul que de faire de même avec 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
la source
Dans la forme que vous avez décrite, le problème est difficile. Envisagez-vous de copier, coller une partie de l'image dans une autre image plus grande comme copie? etc.
Si vous prenez du recul, cela est plus facile à résoudre si vous filigrane les images principales. Vous devrez utiliser un schéma de filigrane pour incorporer un code dans l'image. Pour prendre du recul, contrairement à certaines des approches de bas niveau (détection des contours, etc.) suggérées par certaines personnes, une méthode de tatouage est supérieure car:
Il résiste aux attaques du traitement du signal ► Amélioration du signal - accentuation, contraste, etc. ► Filtrage - médian, passe-bas, passe-haut, etc. ► Bruit additif - gaussien, uniforme, etc. ► Compression avec perte - JPEG, MPEG, etc.
Il résiste aux attaques géométriques ► Transformées affines ► Réduction des données - rognage, écrêtage, etc. ► Distorsions locales aléatoires ► Warping
Faites des recherches sur les algorithmes de filigrane et vous serez sur la bonne voie pour résoudre votre problème. (Remarque: vous pouvez comparer votre méthode à l'aide du jeu de données STIRMARK . Il s'agit d'une norme acceptée pour ce type d'application.
la source
Ce n'est qu'une suggestion, cela pourrait ne pas fonctionner et je suis prêt à être appelé à ce sujet.
Cela générera de faux positifs, mais, espérons-le, pas de faux négatifs.
Redimensionnez les deux images afin qu'elles aient la même taille (je suppose que les rapports largeur / longueur sont les mêmes dans les deux images).
Compressez une image bitmap des deux images avec un algorithme de compression sans perte (par exemple gzip).
Recherchez des paires de fichiers ayant des tailles de fichier similaires. Par exemple, vous pouvez simplement trier chaque paire de fichiers que vous avez en fonction de la similitude des tailles de fichier et récupérer le X supérieur.
Comme je l'ai dit, cela générera certainement de faux positifs, mais, espérons-le, pas de faux négatifs. Vous pouvez l'implémenter en cinq minutes, alors que le Porikil et. Al. exigerait probablement un travail considérable.
la source
Je crois que si vous êtes prêt à appliquer l'approche à toutes les orientations possibles et aux versions négatives, un bon début pour la reconnaissance d'image (avec une bonne fiabilité) est d'utiliser des faces propres: http://en.wikipedia.org/wiki/Eigenface
Une autre idée serait de transformer les deux images en vecteurs de leurs composants. Une bonne façon de faire est de créer un vecteur qui fonctionne dans les dimensions x * y (x étant la largeur de votre image et y étant la hauteur), la valeur de chaque dimension s'appliquant à la valeur de pixel (x, y). Exécutez ensuite une variante de K-Nearest Neighbours avec deux catégories: match et no match. S'il est suffisamment proche de l'image d'origine, il rentrera dans la catégorie de correspondance, sinon ce ne sera pas le cas.
K Nearest Neighbours (KNN) peut être trouvé ici, il y a aussi d'autres bonnes explications à ce sujet sur le Web: http://en.wikipedia.org/wiki/K-nearest_nequart_algorithm
L'avantage de KNN est que plus vous comparez de variantes à l'image d'origine, plus l'algorithme devient précis. L'inconvénient est que vous avez besoin d'un catalogue d'images pour former le système en premier.
la source
Si vous êtes prêt à envisager une approche totalement différente pour détecter les copies illégales de vos images, vous pouvez envisager de créer un filigrane . (à partir de 1,4)
Bien qu'il s'agisse également d'un domaine complexe, il existe des techniques qui permettent aux informations de filigrane de persister lors d'une altération grossière de l'image: (à partir de 1.9)
bien sûr, la FAQ appelle la mise en œuvre de cette approche: "... très difficile" mais si vous réussissez, vous obtenez une grande confiance quant à savoir si l'image est une copie ou non, plutôt qu'un pourcentage de probabilité.
la source
Si vous utilisez Linux, je suggérerais deux outils:
align_image_stack du 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é à la composition de photographies HDR, mais fonctionne également pour les images vidéo et autres documents). Plus d'informations: http://hugin.sourceforge.net/docs/manual/Align_image_stack.html
comparer à partir du package imagemagick - un programme qui peut trouver et compter la quantité de pixels différents dans deux images. Voici un tutoriel soigné: http://www.imagemagick.org/Usage/compare/ uising the -fuzz N%, vous pouvez augmenter la tolérance d'erreur. Plus le N est élevé, plus la tolérance d'erreur est élevée pour toujours compter deux pixels comme étant identiques.
align_image_stack devrait corriger tout décalage afin que la commande de comparaison ait réellement une chance de détecter les mêmes pixels.
la source