Journal Distance entre deux images...

Posté par  .
Étiquettes : aucune
0
24
fév.
2005
Bonjours tout le monde...

Le journal du jour porte sur une question simple...

Existe-t-il un outil sous linux qui me donnerait la distance entre deux images...

Je m'explique...

Si je prends une capture d'écran de la page d'accueil de linuxfr aujourd'hui, et une autre demain, elle vont se ressembler beaucoup. Des images avec les mêmes nuances de couleurs aux mêmes endroits, des boites avec a peu prêt la même taille aux mêmes endroits, etc.

En revanche si je compare la page d'accueil la page de google, la ça n'a rien a voir...

Si je compare la page d'accueil de linuxfr avec la page des forums de linuxfr, je vais être plus proche que dans le cas de google, mais plus loin que dans le cas de 2 pages d'accueils de jours différents...

J'ai pensé à plusieurs solutions pour ça. Par exemple, calculer la couleur moyenne de la page et vérifier ça variation entre 2 pages... Ou alors comme dans les JPG, essayer e pixelliser l'image un maximum pour la transformer en un ensembles de gros carrés de couleurs plus facilement comparables?

Bref, de nombreuse solutions, mais aucune ne me semble vraiment bonne. D'ou l'idée de rechercher un outils déjà existant faisant cela. Dans mogrify par exemple? Ou dans gimp? Je n'ai rien trouvé qui ressemble a cela, malheureusement.

Fait que, j'suis ouvert a tout idée qui pourrait m'avancer sur le sujet, et pourquoi pas un algo a implémenter pour essayer... A moins que des amis chercheurs traînent dans le coins et ai des théories sur le sujet?

Merci pour vos avis.

JMS
  • # Une façon simple et efficace

    Posté par  . Évalué à 7.

    Serait de faire une transformée de fourrier des deux immages.
    Avec la FFTW par exemple. Tu aura ainsi une analyse spectrale pour pas trop cher. Après pour affiner c'est tout un bazard. Ci le but est d'être capable de reconnaitre un paysage de nuit par rapport à un paysage de jour ça ne marche pas du tout.
    • [^] # Re: Une façon simple et efficace

      Posté par  . Évalué à 3.

      Non, le but c'est de comparer 2 images représentant des pages web, dont par exemple l'une serait décalée de un pixel avec un mot différent par rapport a l'autre, mais les meme images et les les memes informations, en gros.

      Afin de pouvoir bien différencier celle qui pointe a la meme place et celle qui n'y pointe pas... Donc pour moi, le paysage de jour et celui de nuit sont TRES eloignés, donc ca pourrai fonctionner...

      Je vais essayer de regarder de ce coté la... Est-ce qu'un outil en ligne de commande pourrai me renvoyer ce genre de truc? Mogrify ne permet pas d'obtenir des infos; juste de modifier... Yaura pas un truc pour renvoyer une chaine style 00001235799874230015687 qui représenterai la courbe du spectre?
  • # Distance entre deux images...

    Posté par  . Évalué à 7.

    C'est tout simplement du "traitement du signal".

    Tu veux en fait mesurer la "corrélation" (la ressemblance) entre 2 "signaux" qui sont des images, des signaux à 2 dimensions.

    Il y a pas mal de chose sur le net, en cherchant sur google (par exemple). Mais pour faire le tri, c'est autre chose.

    Il y aura bien quelqu'un connaissant des algorithmes précis qui passera ici.
    • [^] # Re: Distance entre deux images...

      Posté par  . Évalué à 5.

      Wouaou, grace a ton vocabulaire j'ai pu trouver ca :

      http://www.greyc.ensicaen.fr/~regis/Pandore/programmes/operatorsP0/(...)

      Qui en fait vient de la http://www.greyc.ensicaen.fr/~regis/Pandore/(...) et qui semble faire EXACTEMENT ce dont j'ai besion!!!

      J'suis impressioné la... Le seul hic c'est que j'y connais rien au C :(

      Bon, il semble qu'il y ai des executables en ligne de commande. PAs tout compris. Je crois qu'il va falloir que je telecharge ca et que je te le test... Merci encore!

      JMS
    • [^] # Re: Distance entre deux images...

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

      les mots cles que tu recherche sont simples:
      - cros-correlation ( on passes souvent par la cross-correlation de transformees de l image, comme une DFT [Discrete FT], ou FFT )
      - autosimilarite ( compression fractale).

      Dans les deux cas, avant de pondre un code efficace, il te faudra etudier les maths pendant plusieur mois ... parce que les deux requierrent des bases en beton arme.

      Je travailles sur une OCR: je vais coder une cross-correlation la semaine prochaine. Rappelle moi de tenter une fractale dans la foulee ...

      Enfin passer par des screen shots est idiot ... tu peut directement appliquer la crosscorrelation sur le flux XML ( RSS) de la page ... ca evite tous les problemes dus aux CSS.

      Parce que tu prends deux sites tournant sous DaCode, avec un peu de chance, deux pages d acueil auront plus de ressemblance graphique que l acueil et le forum du meme site.

      Avant tout traitement du signal, tu dois appliquer un filtre passe bas, pour eleminer le bruit HF, et eventuellement une ou deux constantes, et si te as le temps, d autres filtres sympas pour retirer d autres types de bruit. Travailler en brut sur les images n as aucun interret d un point de vue traitement du signal.

      Bref, de nombreuse solutions, mais aucune ne me semble vraiment bonne.

      achete un bon bouquin, va dans une bibliotheque scientifique, ou inscrit toi a des cours universitaires ... bref, commence par prendre les cours de base sur le traitement du signal.
  • # Une piste ...

    Posté par  . Évalué à 4.

    J'ai pas vraiment d'outils à proposer, mais étant donné que j'étudie dans une fac ou se trouve un labo de recherche en imagerie, nos profs nous parlent pas mal problèmes de ce genre. Mais apparemment c'est un domaine où les recherches sont encore en cours et où il n'existe pas de théorie "unificatrice", chaque domaine a ses outils. Je parle ici plutot de reconnaissance de forme, mais je pense que ca peut s'appliquer aussi à ton problème : des profs nous parlent de bases de données d'images indexées selon divers critères (imagine des requètes sur des caractéristiques de l'image plutot que sur des attributs d'un ensemble de données, pour comparer avec les BDD classiques). De plus, les requetes peuvent aussi rechercher des images similaires mais ayant subit des transformations simples (translation, changement d'échelle, rotation, etc...). Ca doit se rapprocher de ce que tu cherches.

    Par contre, pour ton idée, ce genre de tache ne se fait pas qu'en une étape, on passe d'abord par du traitement du signal, puis par des étapes de segmentation, puis de la classification. Enfin ce que je dis n'est pas forcément à prendre au pied de la lettre, je suis justement en train de faire mes études la dedans, donc je n'ai pas la science infuse...

    Tu peux aller voir sur http://www-l3i.univ-lr.fr/(...) , ya des pistes de recherche mais pas vraiment d'outils concret.
    • [^] # Re: Une piste ...

      Posté par  . Évalué à 2.

      Merci pour cette piste. Pour le moment je vais essayer d'exploiter celle du commentaire ci-dessus, et ensuite seulement, celle la.

      Si tu entends parler autour de toi de quelque chose (technique, algo, outils, etc.) qui pourrai m'aider, je suis prenneur....

      JMS
  • # J'ai pas compris ton problème

    Posté par  . Évalué à 3.

    J'ai pas compris ton problème. Que veux tu? Donner la distance entre deux images? Classer des sites par rapport à des screenshots? ...

    Pour la distance, tu peux toujours faire le calcul de la distance euclidienne de tes deux images en considérant chaque image comme une matrice. Mais je pense pas que cela donne quelque chose de génialissime. Concernant le traitement du signalement je ne m'y connais pas assez pour te conseiller.

    Par contre si tu veux faire de la classification, tu peux tenter un réseau de neurones (c'est utilisé pour la reconnaissances de caractères, trajectoires, etc.).

    Bon courage :-)
    • [^] # Re: J'ai pas compris ton problème

      Posté par  . Évalué à 4.

      En fait j'ai 8000 URL a comparer entre deux serveurs. C'est sencé être le meme contenu, mais vu que ce sont 2 versions de serveurs différent et que ca a été migré a la main, c'est pas EXACTEMENT le meme affichage.... J'ai donc besoin de detecter sir l'affichage est loin de l'original, auquel cas la nouvelle URL ne pointe pas au bon endroit, ou si c'est proche de l'original, et donc ca doit être la meme chose...

      Je ne peux pas me baser sur le code HTML car il a beaucoup trop changé, ni sur l'url qui est exactement la meme... A la base, la comparaison devait être faite a la "main" (oeil).... L'idée, c'est que je prefere passer 2 semaines a coder un truc utile que 2 semaines a taper des URLs toute la journée...

      Pour le réseau de neuronnes, le temps que je comprenne et aue je lui aprenne le necessaire, ca sera trop tard...
      • [^] # Re: J'ai pas compris ton problème

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

        Moi j'ai plusieurs trucs en tête ;)
        Le premier c'est ça: http://www-evasion.imag.fr/DEAIVR/(...) (page d'un DEA à Grenoble)
        Tu trouvera des cours, des papiers de recherches, des liens sur ce genre de chose. Connaissant des gens dans ce domaine, je sais que certains travaillent sur ce genre de chose, et que définir la distance entre 2 images/vecteurs se fait de plusieurs façon différentes, pour des résultats tout aussi différents ;)

        L'autre chose, c'est le réseau de neurone. Plutôt que de recoder complètement un RN, tu peux en trouver des déjà tout fait, tu aura juste quelques réglages/bidouilles à faire pour appliquer à ton cas. Par exemple, tu as Matlab qui contient déjà tout ce qu'il faut =)
        Tu pourra trouver des liens/cours ici: http://diwww.epfl.ch/mantra/(...)

        Bon courage ;)
  • # Euh..

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

    le truc c'est de partir d'un algo trivial et de complexifié. Qqn a du le faire avant moi.

    Moi, je verrais d'abord :

    for each pixel :
    total += color.image1 - color.image2


    ainsi, si, par exemple, l'image est la même mais que le jaune clair est devenu foncé sur une portion, la distance sera plus faible que si cette portion est devenue bleue.

    Problème : si tu décalles ton image de 1 pixel vers le haut, tu peux avoir une distance énorme, alors que c'est quasi la même.

    Donc faut en plus jouer avec les distances.

    C'est rigolo, surtout à 3h du mat :-)

    Mes livres CC By-SA : https://ploum.net/livres.html

    • [^] # Re: Euh..

      Posté par  . Évalué à 2.

      Ben ouais, c'est ca mon soucis, c'est que la page a pu bouger legerement car une lettre était en majuscule et est maintenant en minuscule....


      Donc ca ne fonctionne pas. Je ne peux pas prendre comme hypothese que le point (x,y) dans l'image A se trouve toujours en (x,y) dans B... Il pourrait être en (x+dx,y+dy).... Ce qui ne facilite pas la chose...
      • [^] # Re: Euh..

        Posté par  . Évalué à 2.

        Le problème est à mon avis que le dx et le dy ne sont pas obligatoirement constant (pour les deux mêmes images que tu compares), si c'était juste une translation, il suffirait de retranslater l'un des images, et recalculer une distance point à point. Il faut donc un outils qui sache généraliser la position des éléments, plutot que faire du point à point (qui est une approche naïve du problème).

        Enfin quand on y reflechit un peu c'est peut-être naif d'y aller point à point, mais si tu regardes une page web il y a souvent beaucoup de partie de l'image qui sont blanche (enfin ou il n'y a rien d'écrit, ou rien de dessiner), cette approche pourrait te permettre de voir si les images sont proches à ce niveau là. Et c'est peut-être déjà pas si loin de ce que tu recherches.

        Sinon comme je te l'ai dit le seul concept informatique que je connaisse qui sache généraliser, apprendre, et classer est le réseau de neurones. J'ai entendu parler d'un truc qui s'appelle machine à vecteurs de support: http://www.support-vector.net/(...)
  • # pas vraiment simple

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

    Premièrement, je ne vois pas vraiment l'intérêt de faire une comparaison entre screenshots.
    D'une part, tu risques d'oublier toute une partie de ta page (si elle est plus grande que la surface affichée par ton navigateur).
    D'autre part, tu as un accès direct au contenu lui-même. En effet, logiquement, un même navigateur n'affichera pas de deux manières différentes un même code html.
    Dans ces conditions, le mieux à mon avis est de faire un diff sur les deux pages. Tu peux même pousser plus loin dans ton analyse en vérifiant la cohérence des éléments binaires de ta page web (images, sons...) par exemple par une signature md5.

    Maintenant, si tu tiens à passer par l'image (pourquoi faire simple quand on peut faire compliqué), tout dépend de ce que tu veux faire.
    Si tu veux avoir une idée de la différence, une simple différence d'image peut-être utilisée. Ca se fait très facilement :

    for (i de 0 à w)
    do
    for (j de 0 à h)
    do
    diff(i,j) = img1(i,j) - img2(i,j)
    done
    done

    Tu peux aussi vouloir faire plus compliqué.
    Rechercher dans un premier temps la cohérence générale entre les deux images à comparer. A ce moment là, une segmentation à basse résolution de l'image devrait te permettre d'extraire les différents blocs "graphiques" de ton image (dans le cas de linuxfr, les blocs de texte, les boîtes lattérales...), et ainsi de faire une première comparaison : y a t'il de grandes similitudes ou non et si oui, dans quelles zones. Là tu vas plutôt comparer l'organisation fonctionnelle des deux pages.
    Tu peux ensuite passer à une autre étape et analyser plus finement le contenu des différents blocs détectés : s'agit-il de texte ou de graphique, éventuellement la taille du texte... tu peux même aller jusqu'à faire de l'ocr si tu veux.

    Si t'as vraiment envie de jouer et que tu te débrouilles en C++, je te conseille cimg ( http://cimg.sourceforge.net(...) )
    • [^] # Re: pas vraiment simple

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

      Ce qui correspondrait en gros avec CImg à :

      #include "CImg.h"
      using namespace cimg_library;

      int main(int argc,char **argv) {
      const CImg<> img1("image1.png"), img2("image2.png");
      const CImg<> diff = (img1-img2).get_abs();
      const float erreur = diff.sum();
      std::fprintf(stderr,"Erreur entre les deux images : %g\n",err);
      return 0;
      }
      • [^] # Re: pas vraiment simple

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

        tiens quand on parle du loup...
        je me suis cassé la tête avec CImg aujourd'hui pour finir par m'apercevoir que l'organisation interne du buffer correspondait pas à celle de mes données.
        bouh, c'est trop dur.
  • # Histogrammes cumules

    Posté par  . Évalué à 3.

    Si tu veux un algo simple et qui marche assez bien, tu peux essayer de comparer les histogrammes HSV cumules.

    Il faut que ce soit cumule car sinon deux pixels avec une valeur de pixel tres proche mais differente vont etre vus comme completement differents.

    Bien sur, ca ne tient pas compte de la disposition spatiale des pixels, mais ca c'est plus complique et plus couteux. Si tu as besoin d'une solution simple tenant compte des formes, tu peux utiliser les anglogrammes de Grosky.
    http://scholar.google.com/scholar?q=anglograms&ie=UTF-8&oe=(...)
  • # GIFT

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

    GNU Image Finding Tool. Ça fait ce genre de chose, il faut peut être regarder de plus près comment ça marche.
  • # findimagedupes

    Posté par  . Évalué à 3.

  • # distance et comparaison générique...

    Posté par  . Évalué à 3.

    pour information, un article très intéressant dans le Pour la Science de février 2004. :

    C'est un algorithme qui classe (plus ou moins bien) des textes (tu peux utiliser alors le code source des pages en question), des langues, des musiques, des images (va pour le scrineshaute) en se basant sur la compression de données pour repérer les similarités.

    l'article en question : http://homepages.cwi.nl/~paulv/papers/SimilarityV3.pdf(...)

    le papier original qui a inspiré l'article : http://homepages.cwi.nl/~paulv/papers/cluster.pdf(...)

    Si quelqu'un sait s'il existe une implémentation ou est motivé pour en faire une, ça m'intéresse... ;-)
  • # Une question...

    Posté par  . Évalué à 4.

    Salut,

    Tu nous parles de screenshot, mais d'où les tiens-tu ? Je suppose qu'ils ont été fait automatiquement, un peu comme certains moteurs de recherche qui offre un "thumbnail" du site web. Ma question est donc, comment peut-on faire cela ?

    Merci d'avance !
  • # blabla

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

    Tu pourrais comparer le spectres des deux images, et/ou comme déjà dit appliquer un filtre passe-bas.
    L'intéret est que tu obtiens une valeur "moyenne" de la page.
    Cad qu'au lieu de bloquer parceque t'as un mot différent d'un autre, ca saura qu'une tache sombre ici et une autre tache sombre au même endroit sur l'autre page coincident, sans que tu aies à te soucier du texte.
    En gros, tu rends tes deux images bien floues, et alors la (valeur absolue de la) différence sera minime sur la soustration de l'une par l'autre, à moins qu'il y ait un bon changement de mise en page...
  • # Distance entre deux courbes

    Posté par  . Évalué à 1.

    Bonjour jmspaggi2.

    Ton interrogation est constructive.

    Pour faire la distance entre deux images, je crois qu'il n'existe pas de programme tout fait. Par contre, je pense qu'on peut facilement trouver des outils pour faire ceci. Au pire, un petit programme de base permettrait de tout regrouper. Puis en option une interface graphique serait utile.

    Je propose d'utiliser le SPECTRE d'une image (c'est ce qu'on voit dans un logiciel de graphisme quand on demande l'outil COURBES). Le spectre d'une image est un graphe avec en absisse la luminosite (256niveaux) et en ordonnee la quantite de pixels de cette valeur (256niveaux). Cela donne soit une image en deux dimensions soit une suite de valeurs (256couples) qu'on peut facilement enregistrer soit en PNG soit en ASCII.

    Normalement comme chaque image RVB on devrait avoir trois graphes: un spectre ROUGE, un spectre VERT, un spectre BLEU. On peut aussi avoir un spectre general. Pour simplifier, je baserai mon explication sur ce spectre GENERAL. Mais ce ne serait pas plus dur ensuite d'adapter ce raisonnement pour chaque composante R V B.

    Voici ce que je propose:
    1- capture-ecran de la page web dans un fichier PNG;
    2- capture-ecran de la nouvelle page dans un fichier PNG;
    3- analyse du spectre PNG-1; resultats dans un fichier ASCII (256couples);
    4- analyse du spectre PNG-2; resultats dans un fichier ASCII (256couples);
    5- analyse de la difference entre les deux; Pour chaque valeur x, on calcule le pourcentage de difference Y=((abs(y2-y1))/(y1)); resultats Y (256valeurs) dans un fichier ASCII;
    6- calcul de la moyenne des 256 valeurs Y (plus le resultat tend vers 0 pourcent, plus la nouvelle page est similaire).

    Remarques:
    - On peut se passer des etapes 1 et 2 en passant directement etapes 3 et 4;
    - On peut se passer de l'etape 5 en calculant directement le resultat de l'etape 6;
    - Pour l'etape 6, la moyenne n'est pas forcement la meilleure methode;
    - Pour les etapes 1 et 2 il serait souhaitable d'avoir TOUTE la page web et non seulement la page-ecran.

    NB: Je serais heureux d'avoir un compte-rendu de cette investigation.
    Ce n'est pas tous les jours que quelqu'un explore une nouvelle voie.

    • [^] # Re: Distance entre deux courbes

      Posté par  . Évalué à 2.

      Je trouve dommage de perdre la notion d'espace. En effet dans le couple (niveau, nb pixel) les pixels peuvent être situés n'importe ou.
      Un facon assez simple serait de découper les images en petit carrés, et appliquer l'algo si dessus sur chacun des carrés. Bon, on se retouve avec une matrice de couples, mais c'est encore jouable.
      Pour éviter le cas du léger décallage en entre les images, tu peux faire déborder les carrés sur leurs voisins.
      • [^] # Re: Distance entre deux courbes

        Posté par  . Évalué à 2.

        De toutes facons, ca depend de ce que tu cherches a faire. Mais avec tes carres ce sera assez mauvais dans le cas general car si un meme objet se trouve une fois a droite et une fois a gauche, ce sera paume. En plus ta zone de recouvrement se trouve sur-representee par rapport au reste de l'image.
      • [^] # Re: Distance entre deux courbes

        Posté par  . Évalué à 2.

        En toute rigueur, et en théorie, effectivement, il n'y a plus de notion d'espace. Mais en pratique, est-ce que celà a vraiment un impact pour les hypothèses qu'il est honnête de poser pour le problème énoncé ?

        Par exemple, si j'ai deux images qui représente la même page, avec juste un mot qui est décalé de 1 pixel, l'algorithme énoncé donnera une similarité de 100 % (si la couleur du fond reste la même, enfin je me comprends :), ce qui est si j'ai bien compris le but recherché.

        En toute rigueur, les deux images ne sont pas identiques, mais est-ce que l'oeil voit très facilement cette différence. A première vue, tu dirais que les deux sites sont les mêmes. Donc l'algorithme fonctionne à peu près.

        Un autre contre-exemple serait celui d'un site avec une classique mise en page par colonne menu/contenu. Maintenant, si on change le site en faisant la même mise en page contenu/menu, l'algo trouvera une similarité de 100%.

        En fait, en toute généralité, une image qui serait une permutation de pixels de l'image initiale lui sera à 100% similaire par rapport à l'image initiale.

        Deux images qui seraient les même à une petite translation près, serait fortement similaires, par rapport à cet algo.

        Maintenant, réciproquement, on sait que si l'algo dit que les deux images diffèrent de beaucoup, c'est qu'il y a eu du changement.
        S'il trouve que les deux images sont similaires, il convient de faire d'autres tests, si on trouve que l'algorithme n'est pas adapté au problème. Ici, je pense que c'est adapté.

        Enfin toujours est-il que cet algorithme est simple, rapide car pratiquement proportionnel à la taille (en octets) des images.

Suivre le flux des commentaires

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