Nous avons une collection de photos de quelques centaines de gigaoctets. Un grand nombre de ces photos sont visuellement des doublons, mais avec des tailles de fichiers, des résolutions, des compressions, etc. différentes.
Est-il possible d'utiliser des méthodes de traitement d'image spécifiques pour rechercher et supprimer ces images en double ?
J'ai récemment voulu accomplir cette tâche pour une galerie d'images PHP. Je voulais pouvoir générer une empreinte digitale "floue" pour une image téléchargée, et vérifier dans une base de données toutes les images qui avaient la même empreinte digitale, indiquant qu'elles étaient similaires, puis les comparer de plus près pour déterminer leur degré de similarité.
Pour ce faire, j'ai redimensionné l'image téléchargée à 150 pixels de large, je l'ai réduite en niveaux de gris, j'ai arrondi la valeur de chaque couleur au multiple de 16 le plus proche (ce qui donne 17 nuances de gris possibles entre 0 et 255), je les ai normalisées et stockées dans un tableau, créant ainsi un histogramme de couleur "flou", puis j'ai créé une somme md5 de l'histogramme que je pouvais ensuite rechercher dans ma base de données. Cette méthode s'est avérée extrêmement efficace pour réduire le nombre d'images qui étaient visuellement très similaires au fichier téléchargé.
Ensuite, pour comparer le fichier téléchargé à chaque image "similaire" de la base de données, j'ai pris les deux images, les ai redimensionnées en 16x16, et les ai analysées pixel par pixel. J'ai pris la valeur RVB de chaque pixel par rapport à la valeur du pixel correspondant dans l'autre image, j'ai additionné toutes les valeurs et divisé par le nombre de pixels, ce qui m'a donné un écart de couleur moyen. Tout ce qui était inférieur à une valeur spécifique était considéré comme un doublon.
Le tout est écrit en PHP à l'aide du 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/
Essayez PerceptualDiff pour comparer 2 images de mêmes dimensions. Permet des seuils tels que considérer comme visuellement indiscernables des images ayant seulement un nombre X 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 pouvez vouloir créer un format standard pour les comparaisons. Par exemple, je peux utiliser ImageMagick pour mettre toutes les images à l'échelle 100x100 et les enregistrer au format PNG.
J'ai en fait écrit un application qui fait cette même chose.
J'ai commencé par une application précédente qui utilisait une base Distance de Levenshtein pour calculer la similarité des images, mais cette méthode n'est pas souhaitable pour un certain nombre de raisons. Sans aucun doute, l'algorithme le plus rapide que vous trouverez pour déterminer la similarité des images est soit erreur quadratique moyenne ou erreur absolue moyenne (les deux ont un temps 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 plusieurs façons différentes). L'article de Mecki n'est en fait qu'une mise en œuvre de l'erreur absolue moyenne, que mon application peut exécuter (le code est également disponible pour votre plaisir de navigation, si vous le souhaitez).
Quoi qu'il en soit, dans notre application, nous commençons par sous-échantillonner les images (par exemple, tout est mis à l'échelle, disons, de 32*32 pixels), puis nous convertissons en échelle de gris, et enfin nous soumettons les images résultantes à nos algorithmes de comparaison. Nous travaillons également sur des algorithmes de prétraitement plus avancés pour normaliser davantage les images, mais... nous n'en sommes pas encore là.
Il existe sans aucun doute 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), par exemple SSIM mais cela a un coût. D'autres personnes tentent de comparer d'autres qualités visuelles de l'image, comme la luminance, le contraste, les histogrammes de couleur, etc., mais tout cela est coûteux par rapport à la simple mesure du signal d'erreur.
Ma candidature pourrait travail, en fonction de combien de sont dans ces dossiers. Il est multithread (j'ai vu qu'il chargeait pleinement huit cœurs de processeur en effectuant des comparaisons), mais je ne l'ai jamais testé avec une base de données d'images supérieure à quelques centaines d'images. Quelques centaines de gigaoctets d'images semblent prohibitifs. (La simple lecture des images depuis le disque, le sous-échantillonnage, la conversion en échelle de gris et le stockage en mémoire - en supposant que vous ayez assez de mémoire pour tout contenir, ce qui n'est probablement pas le cas - pourrait prendre quelques heures).
Une approche très simple est la suivante :
Convertir l'image en échelle de gris en mémoire, de sorte que chaque pixel ne soit qu'un nombre compris entre 0 (noir) et 255 (blanc).
Mettre à l'échelle l'image à une taille fixe. Il est important de trouver la bonne taille, vous devriez jouer avec différentes tailles. Par exemple, vous pouvez redimensionner chaque image à 64x64 pixels, mais vous pouvez obtenir de meilleurs ou de moins bons résultats avec des images plus petites ou plus grandes.
Une fois que vous avez fait cela pour toutes les images (oui, cela prendra un certain temps), chargez toujours deux images en mémoire et soustrayez-les l'une de l'autre. C'est-à-dire soustrayez la valeur du pixel (0,0) de l'image A de la valeur du pixel (0,0) de l'image B, puis faites de même pour (0,1) dans les deux images et ainsi de suite. La valeur résultante peut être positive ou négative, vous devez toujours enregistrer la valeur absolue (ainsi, 5 donne 5, -8 donne 8).
Vous avez maintenant une troisième image qui est l'"image de différence" (image delta) des images A et B. Si elles étaient identiques, l'image delta serait entièrement noire (toutes les valeurs se réduiraient à zéro). Moins elle est noire, moins les images sont identiques. Vous devez trouver un bon seuil, car même si les images sont en fait identiques (à vos yeux), en mettant à l'échelle, en modifiant la luminosité et ainsi de suite, l'image delta ne sera pas totalement noire, elle n'aura cependant que des tons gris très foncés. Vous avez donc besoin d'un seuil qui dise : "Si l'erreur moyenne (luminosité de l'image delta) est inférieure à une certaine valeur, il y a encore de bonnes chances 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 d'échelle. Vous aurez toujours des faux positifs (des images considérées comme identiques, alors qu'elles ne le sont pas du tout) et des faux négatifs (des images considérées comme non identiques, alors qu'elles le sont).
Cet algorithme est ultra lent. En fait, la seule création des images en niveaux de gris prend des tonnes de temps. Ensuite, vous devez comparer chaque image GS à une autre, encore une fois, des tonnes de temps. De plus, le stockage de toutes les images GS prend beaucoup d'espace disque. Cet algorithme est donc très mauvais, mais les résultats ne sont pas si mauvais, même si c'est si simple. Bien que les résultats ne soient pas extraordinaires, ils sont meilleurs que ce que je pensais au départ.
Le seul moyen d'obtenir des résultats encore meilleurs est d'utiliser un traitement d'image avancé, et c'est là que ça commence à devenir vraiment compliqué. Cela implique beaucoup de mathématiques (vraiment beaucoup) ; il existe de bonnes applications (détecteurs de doublons) pour de nombreux systèmes qui les ont implémentées, donc à moins que vous ne deviez les programmer vous-même, il est probablement préférable d'utiliser une de ces solutions. J'ai lu beaucoup d'articles sur ce sujet mais j'ai peur que la plupart d'entre eux dépassent mon horizon. Même les algorithmes que je pourrais mettre en œuvre selon ces articles sont au-delà de mon horizon ; cela signifie que je comprends ce qui doit être fait, mais je n'ai aucune idée de la raison pour laquelle cela fonctionne ou comment cela fonctionne réellement, c'est juste de la magie ;-)
Il s'agit encore d'un domaine de recherche, je crois. Si vous avez un peu de temps devant vous, voici quelques mots-clés pertinents :
Fondamentalement, chaque image est traitée (indexée) pour produire une "signature d'image". Les images similaires ont des signatures similaires. Si vos images sont simplement redimensionnées, il est probable que leur signature soit presque identique et qu'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 suffire. Cependant, vous devez probablement traiter des millions d'images, ce qui peut être un problème.
Voici un lien vers l'entrée principale de Wikipedia :
http://en.wikipedia.org/wiki/CBIR
J'espère que cela vous aidera.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
