Quel algorithme pourrait être utilisé pour identifier si les images sont «identiques» ou similaires, quelle que soit leur taille?
https://stackoverflow.com/questions/1005115
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
TinEye , le "moteur de recherche d'images inversées", vous permet de transférer un lien vers une image. capable de rechercher parmi le milliard d’images qu’il a explorées et il renverra des liens vers des images trouvées identiques.
Cependant, ce n'est pas une somme de contrôle naïve ou quoi que ce soit lié à cela. Il est souvent capable de trouver à la fois des images de résolution supérieure, de résolution inférieure et de taille plus grande et plus petite que l'image d'origine fournie. C’est une bonne utilisation du service, car je trouve souvent une image et souhaite en obtenir la version la plus haute résolution possible.
Non seulement cela, mais je l’ai eu à chercher des images du même ensemble d’images, où les personnes dans l’image sont dans une position différente mais où l’arrière-plan reste en grande partie le même.
Quel type d'algorithme pourrait utiliser TinEye lui permettant de comparer une image avec d'autres de tailles et de compressions variées ratios et pourtant toujours avec précision qu'ils sont les "mêmes" que image ou ensemble?
La solution
Ces algorithmes sont généralement basés sur les empreintes digitales. L'empreinte digitale est une structure de données assez petite, un peu comme un long code de hachage. Cependant, les objectifs de la fonction d'empreinte digitale sont opposés à ceux de la fonction de hachage. Une bonne fonction de hachage devrait générer des codes très différents pour des objets très similaires (mais pas égaux). La fonction d'empreinte digitale devrait au contraire générer la même empreinte digitale pour des images similaires.
Juste pour vous donner un exemple, il s’agit d’une fonction (pas particulièrement bonne) d’empreintes digitales: redimensionnez l’image en 32x32 carrés, normalisez et quantifiez les couleurs, en réduisant le nombre de couleurs à 256. Ensuite, vous avez 1024 -byte d'empreinte digitale pour l'image. Il suffit de garder une table d'empreintes digitales = > [liste des URL de l'image]. Lorsque vous devez rechercher des images similaires à une image donnée, calculez simplement sa valeur d'empreinte digitale et recherchez la liste d'images correspondante. Facile.
Ce qui n’est pas facile - pour être utile dans la pratique, la fonction d’empreinte digitale doit être robuste contre les cultures, les transformations affines, les changements de contraste, etc. La construction de bonnes fonctions d’empreinte digitale est un sujet de recherche distinct. Bien souvent, ils sont réglés manuellement et utilisent de nombreuses méthodes heuristiques (par exemple, utiliser les connaissances relatives au contenu photo typique, au format d'image / aux données supplémentaires dans EXIF, etc.)
Une autre variante consiste à utiliser plus d’une fonction d’empreinte digitale, à appliquer chacune d’elles et à combiner les résultats. En fait, c'est similaire à la recherche de textes similaires. Juste au lieu de "sac de mots" La recherche de similarité d’image utilise un "sac d’empreintes digitales". et trouve combien d'éléments d'un sac sont identiques à ceux d'un autre sac. Comment rendre cette recherche efficace est un autre sujet.
Maintenant, en ce qui concerne les articles / papiers. Je ne pouvais pas trouver un bon article qui donnerait un aperçu des différentes méthodes. La plupart des articles publics que je connais traitent d'améliorations spécifiques apportées à des méthodes spécifiques. Je pourrais recommander de vérifier ces:
" Empreinte digitale du contenu en utilisant des ondelettes " . Cet article traite des empreintes audio au moyen d’ondelettes, mais la même méthode peut être adaptée pour les empreintes d’images.
GROUPEMENT DE PERMUTATIONS: CONCEPTION INTELLIGENTE DE FONCTION DE HASH POUR AUDIO & amp; RETRAIT D'IMAGE . Informations sur les hachages sensibles à la localisation.
Association de fonctionnalités pour la recherche d'images Web à grande échelle et en partie dupliquées . Un très bon article parle de SIFT et des fonctionnalités de groupement pour plus d’efficacité. Il a également une belle bibliographie à la fin
Autres conseils
Cela est probablement basé sur des améliorations des algorithmes d'extraction de fonctionnalités, tirant parti des fonctionnalités invariantes à l'échelle.
Jetez un coup d'œil à
ou, si cela vous intéresse VRAIMENT, vous pouvez débourser environ 70 dollars (ou au moins consulter l'aperçu Google) pour
Le créateur du site FotoForensics a publié ce blog sur ce sujet, il m’a été très utile et m'a montré des algorithmes qui pourraient vous suffire et qui nécessitent beaucoup moins de travail que les ondelettes et l'extraction de fonctionnalités.
http: // www .hackerfactor.com / blog / index.php? /archives/529-Kind-of-Like-That.html
aHash (également appelé hachage moyen ou hachage moyen). Cette approche écrase l’image en une image 8 x 8 en niveaux de gris et active les 64 bits. le hachage basé sur si la valeur du pixel est supérieure à la couleur moyenne de l'image.
pHash (également appelé "hachage perceptif"). Cet algorithme est similaire à aHash mais utilise une transformée en cosinus discrète (DCT) et compare les sur les fréquences plutôt que sur les valeurs de couleur.
dHash Comme aHash et pHash, dHash est assez simple à mettre en œuvre et est beaucoup plus précis qu'il n'a le droit de l'être. En tant que implémentation, dHash est presque identique à aHash mais il fonctionne beaucoup mieux. AHash se concentre sur les valeurs moyennes et pHash évalue modèles de fréquence, dHash suit les gradients.
La transformation de Hough est un très ancien algorithme d'extraction de fonctionnalités, qui vous dérange beaucoup. Je doute que ce soit ce que tinyeye utilise, mais c’est un bon et simple point de départ pour l’apprentissage de l’extraction des fonctionnalités.
Il existe également des diapositives pour une conversation soignée de la part de membres de l’Université de Toronto au sujet de leur travail à l’adresse astrometry.net . Ils ont développé un algorithme pour faire correspondre les images télescopiques du ciel nocturne aux emplacements des catalogues d'étoiles afin d'identifier les caractéristiques de l'image. C'est un problème plus spécifique que ce que tinyeye tente de résoudre, mais je m'attendrais à ce que nombre des idées de base dont ils parlent soient applicables au problème plus général.
Sur cette base, La réponse d'Igor Krivokon semble être sur la marque.
Ils font peut-être une transformation de Fourier pour caractériser la complexité de l’image, ainsi qu’un histogramme pour caractériser la distribution chromatique, couplés à un algorithme de catégorisation de région pour garantir que des images aussi complexes et colorées ne soient pas faussement jumelées. . Je ne sais pas si c'est ce qu'ils utilisent, mais il semble que cela ferait l'affaire.
Découvrez cet article de blog (pas le mien) pour une description très compréhensible d’un algorithme très compréhensible qui semble donner de bons résultats pour sa simplicité. Il partitionne fondamentalement les images respectives en une grille très grossière, trie la grille selon des ratios rouge: bleu et vert: bleu et vérifie si les tris sont identiques. Cela ne fonctionne naturellement que pour les images couleur.
Les professionnels obtiennent probablement de meilleurs résultats en utilisant des algorithmes beaucoup plus avancés. Comme mentionné dans les commentaires sur ce blog, une approche dominante semble être les ondelettes.
Qu'en est-il du redimensionnement des images à une petite taille standard et de la vérification des valeurs de PSIM ou SSIM ou luma-only? c'est ce que je ferais.
