Journal Dans lequel il est question de la recherche d'images par similarité visuelle

Posté par  (site web personnel) .
Étiquettes :
23
29
mar.
2010
Chers lecteurs bonjour,

Situons d'abord un peu le contexte : Les totoz, ce sont ces petites images beaucoup utilisées sur certains forums comme ceux de hardware.fr pour illustrer les discussions, mais aussi sur les tribunes, y compris la tribune de DLFP (ou sa version AJAX). Le serveur de totoz historique, celui de hardware.fr, étant quelque peu restrictif (un seul totoz par utilisateur, d'où le besoin de créer un compte pour chaque nouveau totoz, taille très réduite, modération des images), un serveur alternatif, totoz.eu, fut mis en place par LLG<.

Vers la fin de l'année dernière, suite à une mise à jour de Ruby le totoz.eu d'origine a arrêté de fonctionner et comme personne n'était capable de le mettre à jour (bravo la maintenabilité du ruby !) j'ai monté une nouvelle version en PHP avec Drupal.


Ce week-end, j'ai pensé à deux nouvelles features et je les ai mises en place, c'est de cela que je voudrais vous parler aujourd'hui.

Une pratique relativement courante sur hardware.fr est de réutiliser un totoz existant tel quel, par exemple les totoz [:aloy] et [:sugoy].

Une autre pratique est de prendre un totoz existant et de le modifier un peu pour en faire un nouveau, par exemple [:totoz] et [:infocore], ou encore [:garghahamail] et [:lefebvre haha]. Vous remarquerez les subtiles différences.


Ce que je voulais, donc, c'était pour chaque totoz, proposer une liste des totoz identiques et une liste de totoz différents mais « similaires ». Pour les totoz identiques pas de problème, il suffit de comparer le md5, mais pour la similarité... c'est une autre paire de manches !

J'ai d'abord cherché du côté d'une API chez TinEye, un moteur de recherches d'images bien connu des participants à What The Movie. Mais à 300 $ les cinq mille recherches, avec ma base de onze mille totoz, non merci. En cherchant des alternatives libres ou tout au moins gratuites, je suis tombé sur CoPhIR qui est « available to the research community » mais pas tout le monde, apparemment.

De nombreux autres papiers de recherche, projets en « preview » depuis 2002, sites payants, plus tard, j'ai trouvé findimagedupes, un petit outil libre et simple en perl, datant de 2002 mais réécrit plus tard et plus ou moins maintenu pour Debian (voir ici).

Sur mon serveur, findimagedupes analyse les 11000 totoz en à peu près une minute, pas mal. Mais je n'en étais pas tout à fait content, d'abord à cause du format sous lequel sont présentés les résultats : tous les fichiers similaires sur une seule ligne, séparés par des espaces, mais certains fichiers contiennent déjà des espaces, pas facile à parser donc, et le fait que tous les fichiers sans aucun fichier similaire soient considérés comme tous similaires, un peu bizarre.

J'ai donc continué ma quête et j'ai découvert ImgSeek et surtout isk-daemon. Un serveur en python, qui indexe les images (il a bien pris une trentaine de minutes pour indexer tous les totoz) puis retourne des résultats de recherche très rapidement (ça se mesure en centièmes de seconde). L'index toujours pour 11000 totoz fait 12 Mo, et le serveur prend une quarantaine de mégaoctets en RAM, ce qui est raisonnable.

Voilà donc un exemple des résultats pour le totoz [:totoz] : http://totoz.eu/totoz/totoz/similar
pour [:aloy] : http://totoz.eu/totoz/aloy/similar
ou un petit totoz tout simple, [:mpk] : http://totoz.eu/totoz/mpk/similar

Les résultats pour d'autres totoz, en particulier les visages, sont un peu différents, voir par exemple [:big menes] : http://totoz.eu/totoz/big%20menes/similar mais ils me semblent plutôt pertinents après tout.


J'en ai profité pour publier un petit script en ligne de commande pour rechercher des totoz : http://ssz.fr/brdl/totoz.sh (je vous suggère de le renommer en "ttz", c'est plus rapide à utiliser), il utilise les nombreuses API mises à disposition par totoz.eu, tout comme olcc pour sa recherche de totoz (j'espère d'ailleurs que chrisix< trouvera des applications à la recherche de totoz par similarité !).


Voilà, je souhaitais partager mes recherches et mes découvertes avec vous. D'ailleurs si vous avez vous-mêmes de l'expérience à ce sujet, d'autres pistes à me suggérer pour la recherche d'images par similarité visuelle, ou bien d'autres fonctionnalités intéressantes pour totoz.eu, n'hésitez pas à laisser un commentaire.

  • # Gloire au totoz

    Posté par  . Évalué à 4.

    Une spécialité française que les grands pays nous envient.

    En même temps c'est une façon ludique de découvrir le monde, comme par exemple ces types qui se bastonnent à grand coups de néons.

    http://totoz.eu/gif/Neon6.gif
    http://totoz.eu/gif/Neon4.gif
    http://totoz.eu/gif/Neon3.gif

    The capacity of the human mind for swallowing nonsense and spewing it forth in violent and repressive action has never yet been plumbed. -- Robert A. Heinlein

    • [^] # Re: Gloire au totoz

      Posté par  . Évalué à 6.

      Ben oui, c'est violent, mais c'est tiré du film de Nuc Besson.

      Article Quarante-Deux : Toute personne dépassant un kilomètre de haut doit quitter le Tribunal. -- Le Roi de Cœur

  • # Nostalgie

    Posté par  (site web personnel) . Évalué à -9.

    Haaa les totoz, HFR et ses bon vieux splits [:zoutte]

    Mais depuis j'ai grandi, j'essaie de faire des choses utiles, gagner ma vie, faire une famille …

    Nostalgie du temps de l'insouciance …
    Sincères salutations aux copains qui y sont restés [:spamafote]

    [:zjk]

    • [^] # Re: Nostalgie

      Posté par  (site web personnel) . Évalué à 10.

      Je trouve toujours ça un peu triste, ces gens qui font ces réflexions et qui mettent en opposition activité sur internet et réussite dans la vie réelle. Tu sais, je vis en couple et je gagne ma vie avec un emploi qui me plaît, pour reprendre tes points. Et ne me dis pas que tu ne vois pas l'utilité de la recherche d'image par similarité visuelle en général, je ne te croirais pas.

      J'ai plutôt l'impression en fait que ces arguments sont sortis - à tort ou à raison - en tant qu'excuses pour ne pas contribuer, ou pour se retirer d'une communauté. Dans tous les cas, ils n'ont pas lieu d'être : non seulement ils partent d'une supposition fausse (activité au sein d'une communauté sur internet => pas de vie réelle) mais au-delà de ça ce ton condescendant est tout à fait détestable et déplorable. La condescendance et l'élitisme sont deux choses que j'exècre.

      • [^] # Re: Nostalgie

        Posté par  . Évalué à 3.

        Vous devriez proposer pour l'an prochain un GSoC pour améliorer la gestion et l'affichage des totoz dans les navigateurs, si les vilains râleurs de linuxfr ne voient pas l'intérêt de ce formidable outil de communication [:goat_see], peut-être google le verra-t-il !

        Only wimps use tape backup: real men just upload their important stuff on megaupload, and let the rest of the world ~~mirror~~ link to it

      • [^] # Re: Nostalgie

        Posté par  (site web personnel) . Évalué à 8.

        Oulala, désolé si tu as perçu un ton condescendant.
        Oui, ces arguments sont sortis pour expliquer *ma* situation qui m'ont fait quitter cette communauté. En relisant mon message, je pense vraiment qu'il a été mal interprété et que je n'ai porté aucun jugement sur qui que ce soit.
        D'ailleurs mon titre « Nostalgie » annonçait bien un sentiment « personnel ».
        C'est peut-être le « des choses plus utiles » qui a laissé un flou malheureux, j'aurait dû précisé « à mon existence ».

        Sinon, oui, ton projet est sensationnel :-)

  • # Je vais poser une question sérieuse, mais...

    Posté par  . Évalué à 4.

    ... c'est l'occasion ou jamais : pourquoi le totoz de base c'est Shinobu ? Y'a une raison à ça ? Et ça veut dire quoi, totoz ?

    Article Quarante-Deux : Toute personne dépassant un kilomètre de haut doit quitter le Tribunal. -- Le Roi de Cœur

  • # "mais certains fichiers contiennent déjà des espaces"

    Posté par  . Évalué à 7.

    ça t'apprendra.

  • # Bundling Features for Large Scale Partial-Duplicate Web Image Search

    Posté par  . Évalué à 2.

    J'ai récemment lu un papier interessant de Microsoft (^.^) dans le thème, ils utilisent des caractéristiques SIFT et MSER pour retrouver dans de grandes bases de données des images partiellement dupliquées.

    http://research.microsoft.com/en-us/um/people/jiansun/papers(...)

    Vous n'avez plus qu'à implémenter l'algorithme =)

  • # ASCII vaincra \o/

    Posté par  . Évalué à 4.

    C'est tout de même affligeant, tout ce temps, toute cette énergie dépensée, pour des images n'ayant la plupart du temps pas grand intérêt, et à la signification souvent absconse.
    Un simple :-) de 3 octets, au moins tout le monde comprend, et ça ne gaspille pas la bande passante ! Pensez à la planète, bande de pollueurs !
    Oui à la taxe carbone sur les smilaids ;-)

  • # Tentative de troll ?

    Posté par  . Évalué à 5.

    Vers la fin de l'année dernière, suite à une mise à jour de Ruby le totoz.eu d'origine a arrêté de fonctionner et comme personne n'était capable de le mettre à jour (bravo la maintenabilité du ruby !) j'ai monté une nouvelle version en PHP avec Drupal.
    Pis pas de bol, lors de la prochaine migration PHP, tu ne seras plus la, ça ne fonctionnera plus, et un spécialiste Python voudra reprendre le flambeau pour porter le truc et il dira la même chose : personne n'était capable de le mettre à jour. Bravo la maintenabilité dePHP !

    Quand tu connais le langage, Ruby n'est pas plus difficilement maintenable que PHP (je drais même "au contraire", mais je ne serais pas objectif : ça fait pres de 10 ans que je n'ai plus fait de PHP). D'aileurs c'est à peu près valable pour tous les langages (sauf Perl, et C/c++ qui permettent d'écrire facilement du code obscur).

    • [^] # Re: Tentative de troll ?

      Posté par  . Évalué à 4.

      ToBybuR< ne serait pas ton avis.

      « Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche

    • [^] # Re: Tentative de troll ?

      Posté par  (site web personnel) . Évalué à 5.

      Alors là je t'avoue que je ne connais pas Ruby moi-même, mais le fait que le propre auteur d'une application ait des difficultés à porter son application sur une nouvelle version mineure de Ruby en dit quand même long.

      PHP, jusque là mes applications écrites pour PHP 4 tournent encore avec des adaptations mineures alors qu'on en est à PHP 5.3. Dans l'autre sens, Drupal vient tout juste de sortir sa première version cassant la compatibilité PHP 4... je rappelle que PHP 4 date de 2000 !

      Et comme le dit claudex< ci-dessus, l'auteur de ToBybuR, encore une application Ruby, voit lui aussi souvent l'application casser lors d'une mise à jour de Ruby.

      Tu parles de PHP, Perl, C et C++, et ces langages font justement de gros efforts pour garder une compatibilité ascendante : à quelques exceptions près, n'importe quelle application écrite dans un de ces langages il y a des années, tourne encore avec une version récente, et tournera probablement pendant encore un bon nombre de versions.

      À l'évidence il n'en est pas de même pour Ruby.

      • [^] # Re: Tentative de troll ?

        Posté par  . Évalué à 2.

        Je suis d'accord avec toi mais d'un autre coté ruby 1.8 date de 2003 et je crois me souvenir que Yukihiro «Matz» Matsumoto avait dit (manque de référence :) qu'il préférait casser la compatibilité ascendante entre 2 versions plutôt que de trainer de vieilles casseroles toutes pourries (et cela au moins jusqu'à la version 2). Et franchement il n'y a qu'à voir les monstruosités qu'on peut écrire en Perl, Python et PHP pour voir que c'est peut-être pas un mal de forcer de temps en temps les développeurs à faire un coup de ménage dans leurs codes pour respecter une nouvelle API ... quitte à laisser au bord de la route des milliers de petits projets.

        Bon je dis ça, mais ça m'avait bien gonfler de porter mon code Ruby en 1.9, mais avec quelques liens c'est vite fait [http://boga.wordpress.com/2008/04/15/ruby-19-porting-notes/]

        Par contre c'est vrai que j'ai pu constater des problèmes de compatibilité dans des versions correctives d'une même branche (surtout en 1.6) ... ça c'est pas cool mais il semble que ça s'améliore (pas eu de problème depuis un petit bout de temps).

        Donc effectivement le problème de compatibilité ascendante est une évidence, comme le fait que Ruby est plus lent à s'exécuter (cela aussi n'était pas une priorité pour Matz) mais je trouve que ça vaut largement le coup afin d'avoir un langage de scripting 100% objet avec une API cohérente.

        En tout cas bravo pour le travail sur sur totoz.eu

  • # pHash

    Posté par  . Évalué à 4.

    Hiers, en regardant freshmeat, je suis tombé la dessus sur pHash en GPL3 qui calcul un hash perceptuel d'images et de sons (mp3, ogg, flac)
    http://freshmeat.net/projects/phash

    Sur le site du projet il y a le code source en C
    Et il y a une démo en ligne içi : http://www.phash.org/demo/

  • # Identi.calf

    Posté par  (site web personnel) . Évalué à 1.

    >> Pour les totoz identiques pas de problème, il suffit de comparer le md5

    Ah ouais…
    Autant comparer la taille et la couleur de 10 pixels aléatoires, à mon avis, c'est bien plus rapide et aussi efficace…
    Car le md5, il ne survit pas à un bmp -> png-sans-perte, ni même à un gif n&b -> gif couleurs indexées (la taille non plus, d'ailleurs, mais on gagne du temps quand même).

    • [^] # Re: Identi.calf

      Posté par  (site web personnel) . Évalué à 2.

      « comparer la taille et la couleur de 10 pixels aléatoires » ça n'aide en rien : c'est plus compliqué qu'un md5 (qui de toute façon est calculé à l'upload de chaque image, la requête revient à un SELECT id FROM totoz WHERE md5 = '...'), ça n'aide pas à trouver les totoz similaires mais différents (à moins bien sûr que par hasard tes dix pixels tombent sur des endroits identiques) et ça ne tient pas non plus le coup si on passe d'un jpg à du gif indexé... je ne relève même pas le fait que la taille changera de toute façon pour n'importe quelle conversion : même [http://totoz.eu/aloy.gif] et [http://totoz.eu/jibidi.gif], une conversion directe JPG -> GIF, ne passerait pas ton test.

      À la rigueur, en ignorant la taille et en redimensionnant au préalable chaque image en 16x16 puis en la convertissant en noir et blanc et en comparant les valeurs, on arrive à un algorithme proche de celui de findimagedupes, qui marche pas mal.

      • [^] # Re: Identi.calf

        Posté par  (site web personnel) . Évalué à 3.

        Je parlais de comparer la taille des images (les dimensions), et si elle est pareille, la couleur. Évidemment, la taille du pixel, c'est pas terrible (vu ta citation, ma phrase avait été mal parsée).

        >> (qui de toute façon est calculé à l'upload de chaque image, la requête revient à un SELECT id FROM totoz WHERE md5 = '...'),

        Tu ne l'as pas dit dans ton journal que tu avais cette info !

        >> (à moins bien sûr que par hasard tes dix pixels tombent sur des endroits identiques)

        Et bien, justement, ça me parait un bon algorithme randomisé, pour trouver des images identiques, si tu as d'autres informations (déjà la taille). Suffisant, pas sur 10 pixels, mais c'est déjà un critère. Je te rappelle qu'avec MD5, tu as des collisions. Donc même hash ne signifie pas même image (alors que même pixels, oui !)
        Ensuite, si ton JPEG fait 256 couleurs ou moins, ça peut très bien survivre au GIF indexé !

        Bref, je pense que ça peut être plus rentable qu'une conversion en 16² n&b (c'est en fait un échantillonnage terrible de l'image, alors que le côté probabiliste évite les cas pathologiques sur l'image grandeur nature). Puis 16x16, c'est juste 65535 images. Tu es déjà sûr et certain d'avoir des collisions d'images pas du tout liées à cause du paradoxe des anniversaires.

        Enfin, de toute façon, les meilleurs algos sont plus chers : ni ton algo (ni le mien ci-dessus) ne passent dans le cas général une rotation quelconque.

        C'est pour ça qu'on peut (doit ?) utiliser des algos conservatifs pour dégrossir avant d'aller dans des techniques plus chères.
        Le md5, lui, n'est pas conservatif, car il ne préserve ni ne teste aucune information (au sens « Shannonnien » du terme) de l'image.

  • # SIFT et FLANN

    Posté par  (site web personnel) . Évalué à 3.

    Salut,

    tu peux générer des éléments caractéristiques pour tes images (features) avec SIFT
    (http://en.wikipedia.org/wiki/Scale-invariant_feature_transfo(...) puis appliquer un algorithme des plus proches voisins, voir FLANN (http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN).

    FLANN est aussi disponible à partir de l'API OpenCV.

    bon courage!

  • # LibPuzzle

    Posté par  (site web personnel, Mastodon) . Évalué à 2.

    Je sais pas si tu connaît déjà, je l'utilise pas pour le moment mais c'est fait par un super dév, LibPuzzle : http://libpuzzle.pureftpd.org/project/libpuzzle

    Ça a l'air assez cool :)

    « Je vois bien à quels excès peut conduire une démocratie d'opinion débridée, je le vis tous les jours. » (Nicolas Sarkozy)

  • # Geeqie / GQView

    Posté par  . Évalué à 1.

    Ce projet propose aussi une comparaison des images pour trouver les images identiques, avec plusieurs façons de le faire d'ailleurs.
    Et il ajoute même un pourcentage de similarité si besoin (par exemple si le poids de l'image est différent mais que l'image est visuellement identique [=meilleure/moindre définition], il baisse un peu le pourcentage)

    Je l'ai trouvé toujours très efficace avec quelques faux positifs mais rien d'alarmant ou d'handicapant.
    A tester ?

    • [^] # Re: Geeqie / GQView

      Posté par  (site web personnel) . Évalué à 2.

      Le problème de GQView (et de Geeqie aussi je suppose), c'est que ce sont des applications graphiques. Pour moi, il faut que ça tourne sur un serveur [:aloy]

      • [^] # Re: Geeqie / GQView

        Posté par  . Évalué à 2.

        J'ai dû mal m'exprimer alors, sorry
        je pensais te faire aller jeter un œil à leur code source pour étudier/copier leurs méthodes et algos pour comparer les images, puisque les applications graphiques sont justement très efficaces (à mon goût) ;)

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.