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
Journal Distance entre deux images...
24
fév.
2005
# Une façon simple et efficace
Posté par Jerome Herman . Évalué à 7.
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 Jean-Marc Spaggiari . Évalué à 3.
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 Jllc . Évalué à 7.
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 Jean-Marc Spaggiari . Évalué à 5.
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 doublehp (site web personnel) . Évalué à 3.
- 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 benoar . Évalué à 4.
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 Jean-Marc Spaggiari . Évalué à 2.
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 gph . Évalué à 3.
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 Jean-Marc Spaggiari . Évalué à 4.
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 Marc (site web personnel) . Évalué à 3.
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 ploum (site web personnel, Mastodon) . Évalué à 3.
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 Jean-Marc Spaggiari . Évalué à 2.
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 gph . Évalué à 2.
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 Thomas MARTIN (site web personnel) . Évalué à 2.
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 David Tschumperlé (site web personnel) . Évalué à 1.
#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 Thomas MARTIN (site web personnel) . Évalué à 1.
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 Erwan . Évalué à 3.
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 jerome (site web personnel) . Évalué à 3.
[^] # Re: GIFT
Posté par Pascal Terjan (site web personnel) . Évalué à 4.
[^] # Kimdaba
Posté par Yhar Gla . Évalué à 1.
http://ktown.kde.org/kimdaba/(...)
En matant les sources ça peut aider.
# findimagedupes
Posté par nuxer . Évalué à 3.
(ça existe en package debian)
# distance et comparaison générique...
Posté par aedrin . Évalué à 3.
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... ;-)
[^] # Re: distance et comparaison générique...
Posté par Le_Rat_2004 . Évalué à 1.
> pour information, un article très intéressant dans le Pour la Science de février 2004. :
Quelle page?
# Une question...
Posté par saorge . Évalué à 4.
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 Axioplase ıɥs∀ (site web personnel) . Évalué à 1.
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 Le_Rat_2004 . Évalué à 1.
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 Anonyme . Évalué à 2.
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 Erwan . Évalué à 2.
[^] # Re: Distance entre deux courbes
Posté par kd . Évalué à 2.
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.