Supprimer les images en double [fermé]

Question

Nous avons une collection d’images de la taille de quelques centaines de concerts. Un grand nombre de photos sont des doublons visuels, mais avec des tailles de fichiers, une résolution, une compression différentes, etc.

Est-il possible d'utiliser des méthodes de traitement d'images spécifiques pour rechercher et supprimer ces images en double?

Answer 1

Je voulais récemment accomplir cette tâche pour une galerie d'images PHP. Je voulais être capable de générer un & "; Flou &"; empreinte digitale pour une image téléchargée, recherchez dans une base de données les images portant la même empreinte digitale, en indiquant qu'elles étaient similaires, puis comparez-les plus étroitement pour déterminer leur similitude.

Je l’ai accompli en redimensionnant l’image téléchargée sur une largeur de 150 pixels, en la réduisant au niveau de gris, en arrondissant la valeur de chaque couleur au multiple de 16 le plus proche (donnant 17 niveaux de gris possibles compris entre 0 et 255), en les normalisant et stockez-les dans un tableau, créant ainsi un & "; flou &"; histogramme de couleur, puis créer un md5sum de l'histogramme que je pourrais ensuite rechercher dans ma base de données. Cela a été extrêmement efficace pour réduire les images très similaires au fichier téléchargé.

Ensuite, pour comparer le fichier téléchargé à chaque " similaire " image dans la base de données, j’ai pris les deux images, les ai redimensionnées au format 16x16, puis les ai analysées pixel par pixel et ai extrait la valeur RVB de chaque pixel de la valeur du pixel correspondant dans l’autre image, en additionnant toutes les valeurs et en divisant par le nombre de pixels me donnant un écart de couleur moyen. Toute valeur inférieure à une valeur spécifique est considérée comme un doublon.

Le tout est écrit en PHP en utilisant le module GD, et une comparaison avec des milliers d'images ne prend que quelques centaines de millisecondes par fichier téléchargé.

Mon code et ma méthodologie sont ici: http://www.catpa.ws / php-duplicate-image-finder /

Answer 2

Essayez PerceptualDiff pour comparer 2 images de mêmes dimensions. Permet de définir visuellement des seuils, tels que celui de considérer des images avec seulement X nombre de pixels différents.

Si les doublons visuels peuvent avoir des dimensions différentes en raison de la mise à l'échelle, ou des types de fichiers différents, vous voudrez peut-être créer un format standard pour les comparaisons. Par exemple, je pourrais utiliser ImageMagick pour redimensionner toutes les images à 100 x 100 et les enregistrer au format PNG.

Answer 3

Une approche très simple est la suivante:

• Convertissez l'image en niveaux de gris en mémoire afin que chaque pixel ne représente qu'un nombre compris entre 0 (noir) et 255 (blanc).

• Échelle l'image à une taille fixe. Trouver la bonne taille est important, vous devriez jouer avec différentes tailles. Par exemple. vous pouvez redimensionner chaque image à 64 x 64 pixels, mais vous pouvez obtenir des résultats meilleurs ou moins bons avec des images plus petites ou plus grandes.

• Une fois que vous avez fait cela pour toutes les images (oui, cela prendra un peu de temps), chargez toujours deux images en mémoire et soustrayez-les l'une de l'autre. C'est-à-dire soustraire la valeur de pixel (0,0) dans l'image A ob la valeur de pixel (0,0) dans l'image B, faites maintenant la même chose pour (0,1) dans les deux et ainsi de suite. La valeur obtenue peut être positive ou négative, vous devez toujours stocker la valeur absolue (donc 5 résultats sur 5, -8 mais 8 sur 8).

• Vous avez maintenant une troisième image qui est la " image de différence " (image delta) de l'image A et B. Si elles étaient identiques, l'image delta est entièrement noire (toutes les valeurs seront soustraites à zéro). Le & "Moins noir &"; c’est moins les images sont identiques. Vous devez trouver un bon seuil, car même si les images sont identiques (à vos yeux), en redimensionnant, en modifiant la luminosité, etc., l'image delta ne sera pas totalement noire, elle n'aura cependant que des tons de gris très sombres. Il vous faut donc un seuil indiquant & "; Si l'erreur moyenne (luminosité de l'image delta) est inférieure à une certaine valeur, il est fort probable qu'elles soient identiques, mais si elle est supérieure à cette valeur, elles ne le sont probablement pas. . Trouver le bon seuil est aussi difficile que de trouver la bonne taille de mise à l'échelle. Vous aurez toujours des faux positifs (des images réputées identiques, bien qu'ils ne le soient pas du tout) et des faux négatifs (des images réputées non identiques, bien qu'ils le soient).

Cet algorithme est ultra lent. En réalité, créer des images en niveaux de gris prend des tonnes de temps. Ensuite, vous devez comparer chaque image GS les unes aux autres, encore une fois, des tonnes de temps. Le stockage de toutes les images GS nécessite également beaucoup d’espace disque. Donc, cet algorithme est très mauvais, mais les résultats ne sont pas si mauvais, même si c'est aussi simple que cela. Bien que les résultats ne soient pas étonnants, ils sont meilleurs que ce que je pensais initialement.

Le seul moyen d’obtenir des résultats encore meilleurs est d’utiliser un traitement d’image avancé, qui devient très compliqué. Cela implique beaucoup de maths (beaucoup de choses); Il existe de bonnes applications (détecteurs de dupes) pour de nombreux systèmes qui les implémentent. Par conséquent, si vous ne devez pas le programmer vous-même, il est probablement préférable d'utiliser l'une de ces solutions. J'ai lu beaucoup d'articles sur ce sujet, mais je crains que cela ne dépasse mon horizon. Même les algorithmes que je pourrais être capable de mettre en œuvre conformément à ces articles vont au-delà; cela signifie que je comprends ce qui doit être fait, mais je ne sais pas pourquoi cela fonctionne ni comment cela fonctionne réellement, c'est simplement magique ;-)

Answer 4

J'ai en fait écrit une application qui fait exactement cela.

J'ai commencé avec une application précédente qui utilisait un algorithme de base Distance de Levenshtein pour calculer la similarité des images, mais cette méthode n'est pas souhaitable pour un certain nombre de raisons. L’algorithme le plus rapide que vous puissiez trouver pour déterminer la similarité des images est sans doute la erreur quadratique moyenne ou erreur absolue moyenne (les deux ont une durée d'exécution de O (n), où n est le nombre de pixels dans l’image, et il serait également trivial d’enfiler une implémentation de l’un ou l’autre algorithme de différentes façons). Le message de Mecki n’est en réalité qu’une implémentation Mean Absolute Error, que mon application peut exécuter (le code est également disponible pour votre plus grand plaisir de navigation, si vous le souhaitez).

Dans tous les cas, dans notre application, nous sous-échantillonnons tout d'abord les images (par exemple, tout est mis à l'échelle, par exemple, 32 * 32 pixels), puis nous les convertissons en échelle de gris, puis nous exécutons les images obtenues à l'aide de nos algorithmes de comparaison. Nous travaillons également sur des algorithmes de prétraitement plus avancés pour normaliser davantage les images, mais ... pas tout à fait là.

Il existe certainement de meilleurs algorithmes que MSE / MAE (en fait, les problèmes posés par ces deux algorithmes appliqués à l'information visuelle ont été bien documentés), comme SSIM , mais cela a un coût. D'autres personnes tentent de comparer d'autres qualités visuelles dans l'image, telles que la luminance, le contraste, les histogrammes de couleur, etc., mais cela coûte cher par rapport à la simple mesure du signal d'erreur.

Mon application peut fonctionner, en fonction du nombre d'images contenues dans ces dossiers. Il est multithread (je l'ai vu charger complètement huit cœurs de processeur en effectuant des comparaisons), mais je n'ai jamais testé sur une base de données d'images supérieure à quelques centaines d'images. Quelques centaines de concerts d'images sont d'une taille prohibitive. (Il suffit de les lire à partir du disque, de procéder à un sous-échantillonnage, de les convertir en niveaux de gris et de les stocker en mémoire, en supposant que vous disposiez de suffisamment de mémoire pour tout, ce que vous n’avez probablement pas, cela peut prendre quelques heures.)

.

Answer 5

C’est toujours un domaine de recherche, je crois. Si vous avez du temps entre vos mains, voici quelques mots clés pertinents:

• Détection de copie d'image
• Récupération d'images basée sur le contenu
• Indexation d'images
• Suppression des doublons d'image

En principe, chaque image est traitée (indexée) pour produire une & "signature d'image &"; Des images similaires ont des signatures similaires. Si vos images viennent juste d'être redimensionnées, leur signature est probablement presque identique, alors elles se regroupent bien. Certaines signatures populaires sont les descripteurs MPEG-7. Pour regrouper, je pense que K-Means ou l'une de ses variantes peut être suffisant. Cependant, vous devez probablement traiter des millions d’images, cela peut poser problème.

Voici un lien vers l'entrée principale de Wikipedia:
http://fr.wikipedia.org/wiki/CBIR

J'espère que cela vous aidera.

Answer 6

La similarité d’image est probablement un sous-domaine du traitement d’image / AI.

Soyez prêt à mettre en œuvre des algorithmes / formules à partir de papiers si vous recherchez une excellente solution (performante et évolutive).

Si vous voulez quelque chose de rapide, cherchez sur Google pour Similarité d'image

Voici une application de ressemblance d'image C # qui pourrait faire quoi tu veux.

Tous les algorithmes extraient et comparent les fonctionnalités. Comment ils définissent & Quot; feature & Quot; dépend du modèle mathématique sur lequel ils sont basés.

Answer 7

Pour cela, il suffit d’écrire un programme qui calcule la valeur du pixel moyen dans chaque image, en niveaux de gris, trie en fonction de cette valeur, puis les compare visuellement. Des images très similaires doivent apparaître les unes à côté des autres dans l'ordre de tri.

Answer 8

Vous aurez besoin d'un outil de ligne de commande pour gérer autant de données.

La comparaison de chaque paire d'images possible ne sera pas adaptée à un aussi grand nombre d'images. Vous devez trier l'ensemble des images en fonction d'une métrique afin que les comparaisons ne sont nécessaires que sur les images voisines.

Un exemple de métrique simple est la valeur moyenne de tous les pixels d'une image, exprimée en tant que valeur unique en niveaux de gris. Cela ne devrait fonctionner que si les doublons n'ont subi aucune altération visuelle. L'utilisation d'un format de fichier avec perte peut également entraîner des modifications visuelles.

Answer 9

En dehors des sentiers battus, vous pourrez peut-être utiliser des métadonnées d'image pour affiner votre ensemble de données. Par exemple, vos images peuvent comporter des champs indiquant la date et l'heure de la prise de vue, à la seconde près. Les doublons sont susceptibles d'avoir des valeurs identiques. Un outil tel que exiv2 pourrait être utilisé pour afficher ces données dans un format texte plus pratique et pouvant être trié (avec un peu de connaissance des scripts batch / shell).

Même des champs tels que le fabricant et le modèle d'appareil photo pourraient être utilisés pour réduire un ensemble de 1 000 000 d'images 100 séries de 10 000 images, une amélioration significative.

Answer 10

Le programme gqview a une option pour rechercher les doublons, vous pouvez donc essayer de chercher là-bas. Cependant, ce n’est pas infaillible, il ne conviendrait donc que comme heuristique de présenter des copies à un humain, pour confirmation manuelle.

Answer 11

La partie la plus importante est de rendre les fichiers comparables.

Une solution générique pourrait consister à redimensionner toutes les images à une taille et à une échelle de gris fixes. Enregistrez ensuite les images résultantes dans un répertoire distinct portant le même nom pour référence ultérieure. Il serait alors possible de trier par taille de fichier et de comparer visuellement les entrées voisines.

Les images résultantes peuvent être quantifiées de certaines manières pour détecter par programmation les similarités (calcul de la moyenne des blocs, des lignes, etc.).

Answer 12

J'imagine que la méthode la plus évolutive serait de stocker une empreinte digitale avec chaque image. Ensuite, lorsqu’une nouvelle image est ajoutée, il suffit de SELECT id FROM photos where id='uploaded_image_id' vérifier les doublons (ou de prendre l’empreinte de toutes les images, puis de rechercher les doublons

Évidemment, un simple hachage de fichier ne fonctionnerait pas car le contenu actuel diffère.

Empreinte acoustique / cet article peut être un bon début pour le concept, car il existe de nombreuses implémentations de celui-ci. Voici un document sur les empreintes digitales.

Cela dit, vous pourrez peut-être vous en tirer avec quelque chose de plus simple. Quelque chose d'aussi fondamental que de redimensionner l'image en largeur ou en hauteur, en soustrayant image_a de image_b, et en sommant la différence. Si la différence totale est inférieure à un seuil, l’image est un doublon.

Le problème, c’est que vous devez comparer chaque image à une autre. Le temps requis augmentera de manière exponentielle.

Answer 13

Si vous pouvez trouver un moyen de comparer des images qui obéit à l’inégalité du triangle (par exemple, si d (a, b) est la différence entre les images a et b, alors d (a, b) < d (a, c) + d (b, c) pour tous les a, b, c), puis un BK-Tree serait un moyen efficace d’indexer les images afin que vous puissiez trouver des correspondances en temps O (log n) au lieu de temps O (n) pour chaque image.

Si vos correspondances sont restreintes à la même image après différentes variations de compression / redimensionnement / etc, la conversion en une taille / balance des couleurs canonique / etc et une simple addition des carrés de différences de chaque pixel peuvent constituer une bonne métrique. , et cela obéit à l’inégalité du triangle, vous pouvez donc utiliser un arbre BK pour un accès efficace.

Answer 14

Si vous avez un peu d'argent à dépenser, et peut-être qu'une fois que vous effectuez une première passe pour déterminer quelles images correspondent à peut-être , vous pouvez écrire un test pour Mechanical Turk d'Amazon.

https://www.mturk.com/mturk/welcome

Essentiellement, vous créeriez un petit widget que l'AMT montrerait à de vrais utilisateurs humains qui n'auraient alors plus qu'à répondre à la question & "Ces deux images sont-elles identiques? &"; Vous pouvez également leur montrer une grille d'images de format 5x5 et leur demander & "Laquelle de ces images correspond? &"; Vous collecteriez ensuite les données.

Une autre approche consisterait à utiliser les principes de calcul humain qui ont été adoptés de la manière la plus célèbre par Luis Von Ahn ( http://www.cs.cmu.edu/~biglou/ ) avec reCaptcha, qui utilise les réponses Captcha pour déterminer les mots illisibles qui ont été traités à l'aide de la reconnaissance optique de caractères, aidant ainsi à numériser des livres. Vous pouvez créer un captcha qui demande aux utilisateurs d’aider à affiner les images.

Answer 15

Cela ressemble à un problème de procédure plutôt qu’à un problème de programmation. Qui télécharge les photos? Vous ou les clients? Si vous téléchargez la photo, normalisez les dimensions sur une échelle et un format de fichier fixes. De cette façon, les comparaisons seront plus faciles. Cependant, dans l'état actuel des choses, à moins que vous n'ayez des jours, voire des semaines, de temps libre, je vous suggère plutôt de supprimer manuellement les images en double, que ce soit par vous ou par votre équipe, en comparant visuellement les images.

Vous devriez peut-être regrouper les images par lieu, car il s'agit d'images touristiques.