Détection de quasi-doublons Image

Question

Quel est un moyen rapide pour trier un ensemble d'images par leur similitude avec les uns des autres.

Pour le moment j'ai un système qui ne les analyse de l'histogramme entre les deux images, mais c'est une opération très coûteuse et semble trop exagéré.

Idéalement, je suis à la recherche d'un algorithme qui permettrait de donner à chaque image une note (par exemple un entier partition, comme le RVB Moyenne) et je viens de trier par ce score. Scores identiques ou des notes à côté de l'autre sont possibles doublons.

0299393
0599483
0499994 <- possible dupe
0499999 <- possible dupe
1002039
4995994
6004994

RVB Moyenne par image suce, est-il quelque chose de similaire?

Answer 1

Il y a eu beaucoup de recherches sur l'image de la recherche et des mesures de similarité. Ce n'est pas un problème facile. En général, un seul int ne sera pas suffisant pour déterminer si les images sont très similaires. Vous aurez un taux élevé de faux positifs.

Cependant, puisqu'il y a beaucoup de recherche à faire, vous pourriez jeter un oeil à certains de. Par exemple, ce document (PDF) donne une image compacte empreintes algorithme qui est approprié pour trouver des images rapidement et sans stocker beaucoup de données. Il semble que c'est le droit de l'approche si vous voulez quelque chose de solide.

Si vous êtes à la recherche de quelque chose de simple, mais certainement plus ad-hoc, ce DONC, la question est un peu décente idées.

Answer 2

Je vous recommandons d'envisager de déménager loin de simplement à l'aide d'un histogramme RVB.

Mieux digérer de votre image peut être obtenu que si vous prenez un 2d Haar en ondelettes de l'image (c'est beaucoup plus facile que cela puisse paraître, c'est juste un lot de calcul de la moyenne et des racines carrés utilisés pour le poids de votre coefficients) et il suffit de conserver les k plus grand pondérée des coefficients en ondelettes comme un sparse vecteur, normaliser, et de les enregistrer afin de réduire sa taille. Vous devez redimensionner, R, G et B à l'aide de perception des poids à l'avance au moins j'aurais recommandons de passer à l'espace YIQ (ou YCoCg, pour éviter le bruit de quantification) de sorte que vous pouvez échantillon de chrominance de l'information avec une baisse de l'importance.

Vous pouvez maintenant utiliser le produit scalaire de deux de ces éparses vecteurs normés comme une mesure de similarité. Les paires d'images avec le plus grand point des produits sont très similaires dans leur structure. Ceci a pour avantage d'être peu résistant pour le redimensionnement, la teinte, le décalage et le filigrane, et d'être vraiment facile à mettre en œuvre et compact.

Vous pouvez en échange de stockage et de précision en augmentant ou en diminuant k.

Le tri par un seul score va être intraitable pour ce genre de problème de classement. Si vous pensez cela, il aurait besoin d'images pour seulement être en mesure de "modifier" le long d'un axe, mais ils ne le font pas. C'est pourquoi vous avez besoin d'un vecteur de caractéristiques. Dans les ondelettes de Haar cas sa approximativement à l'endroit où les plus fortes discontinuités dans l'image se produire. Vous pouvez calculer une distance entre les images par paires, mais depuis tout ce que vous avez est une distance métrique linéaire, la commande n'a aucun moyen d'exprimer un triangle de 3 images qui sont tous à distance égale. (c'est à dire penser à une image qui est tout vert, une image qui est tout rouge et une image qui est tout bleu.)

Ce qui signifie que toute véritable solution à votre problème aurez besoin de O(n^2) opérations dans le nombre d'images que vous avez. Alors que si cela avait été possible de linéariser la mesure, vous pourriez avoir besoin de seulement O(n log n), O(n) si la mesure a été adapté pour, disons, un tri radix. Cela dit, vous n'avez pas besoin de dépenser O(n^2) étant donné que, dans la pratique, vous n'avez pas besoin de passer au crible l'ensemble, vous avez juste besoin de trouver le truc c'est plus proche que d'un certain seuil. Donc en appliquant l'une des techniques de partition de votre éparses espace vectoriel, vous pouvez obtenir beaucoup plus rapide asymptotique pour le 'me trouver k des images qui sont de plus en plus semblables-delà d'un certain seuil de" problème de la naïveté de la comparaison de chaque image par rapport à chaque image, vous donnant ce que vous avez probablement besoin... si ce n'est précisément ce que vous avez demandé.

En tout cas, j'ai utilisé il y a quelques années de bon effet, personnellement, en essayant de minimiser le nombre de textures différentes, j'ai été le stockage, mais il y a aussi beaucoup de recherche sur le bruit dans cet espace, la preuve de son efficacité (et dans ce cas, la comparant à une forme plus subtile de l'histogramme de classement):

http://www.cs.princeton.edu/cass/papers/spam_ceas07.pdf

Si vous avez besoin de plus de précision dans la détection, la minHash et tf-idf algorithmes peuvent être utilisés avec les ondelettes de Haar (ou de l'histogramme) pour faire face à des modifications plus robuste:

http://cmp.felk.cvut.cz/~chum/documents/chum_bmvc08.pdf

Enfin, Stanford a une recherche d'images basée sur une plus exotiques variante de ce type d'approche, basée sur le fait de faire plus d'extraction de caractéristiques de la ondelettes pour trouver pivoter ou mettez à l'échelle des sections d'images, etc, mais cela va bien au delà de la quantité de travail que vous aimeriez faire.

http://wang14.ist.psu.edu/cgi-bin/zwang/regionsearch_show.cgi

Answer 3

J'ai mis en place une très bonne algorithme pour cela appelé Fast Multirésolution de l'Image de l'Interrogation. Mon (ancien, plus maintenu) code pour qui est ici.

Ce Rapide Multirésolution de l'Image de l'Interrogation n'est séparer l'image en 3 morceaux basés sur l'espace YIQ palette (mieux pour la mise en correspondance de différences que de RVB). L'image est alors essentiellement compressé à l'aide d'ondelettes d'un algorithme jusqu'à ce que seulement les caractéristiques les plus importantes de chaque couleur sont disponibles. Ces points sont stockés dans une structure de données. Requête images passent par le même processus, et l'une des principales caractéristiques de l'image de la requête sont en correspondance avec ceux de la base de données stockée. Le plus de matchs, plus il est probable que les images sont similaires.

L'algorithme est souvent utilisé pour la requête "par l'esquisse" de la fonctionnalité. Mon seul logiciel a permis la saisie de la requête images via l'URL, donc il n'y a pas d'interface utilisateur. Cependant, je trouve qu'il ont très bien travaillé pour la mise en correspondance des vignettes à la grand version de cette image.

Beaucoup plus impressionnant que mon logiciel est retrievr qui vous permet d'essayer le FMIQ algorithme en utilisant des images Flickr comme la source. Très cool! Essayer via l'esquisse ou à l'aide d'une source d'image, et vous pouvez voir comment cela fonctionne bien.

Answer 4

Une image possède de nombreuses fonctionnalités, de sorte que si vous limitez-vous à un, comme la luminosité moyenne, vous avez affaire à un n-dimensions problème de l'espace.

Si je vous demande d'attribuer un nombre entier unique pour les villes du monde, afin que je puisse dire à ceux qui sont à proximité, les résultats ne serait pas la grande. Vous pourriez, par exemple, choisir le fuseau horaire que votre unique entier et d'obtenir de bons résultats avec certaines villes. Toutefois, une ville près du pôle nord et une autre ville près du pôle sud peut aussi être dans le même fuseau horaire, même s'ils sont à des extrémités opposées de la planète. Si je vous laisse utilisation de deux entiers, vous pouvez obtenir de très bons résultats avec la latitude et la longitude. Le problème est le même pour l'image de la similitude.

Tout cela étant dit, il existe des algorithmes qui tentent de cluster images similaires ensemble, ce qui est effectivement ce que vous me demandez. C'est ce qui arrive quand vous ne détection de visage avec Picasa. Avant même de vous identifier toutes les faces, de groupements similaires au ensemble, de sorte qu'il est facile de passer à travers une série de visages semblables et de donner à la plupart d'entre eux le même nom.

Answer 5

Il existe une bibliothèque C ("libphash" - http://phash.org/ ) qui calcule le "hachage perceptuel" d’une image et vous permet de détecter des images similaires en comparant les hachages directement contre toutes les autres images) mais malheureusement cela ne semblait pas très précis quand je l’ai essayé.