Bonjour à tous,
Je cherche à mesurer la distance entre deux images. Ce sont des images en niveaux de gris de 92 par 112 pixels. Si on considère deux tableaux de pixels correspondant aux images : pixels1[i][j] et pixels2[i][j], et que chaque valeur de niveaux de gris est comprise dans [0;255], comment calculer la distance de hausdorff entre ces deux images ?
PS : je sais que généralement on ne mesure pas tous les pixels d’une image… mais je n’ai pas trouvé d’autres idées…
Compliquée ton histoire, il te faut une distance qui soit invariante par translation et au bruit. Je te suggère la chose compliquée suivante:
Ton image peut être vue comme un tableau [0,L]x[0,H]
Je te suggère de la transformer en une image [-L,L]x[-H,H] par symétrie suivant les deux axes, cela te définit une fonction spatiale périodique. Tu en fait la transformée de Fourier.
Tu fais de même pour ton autre image puis tu prend comme distance la somme des valeurs absolues des écarts entre chaque composante de tes deux tableaux représentants ta transformée de Fourier. Tu auras une distance qui sera telle qu’une image sera très proche d’elle même décalée. Une image sera très proche d’elle même rayée, floutée ou mélangée à un bruit. Mais ça demande un peu de calcul…
En fait, il ne faut pas beaucoup de calculs, je m’explique :
[ul]Je compare une image à une base d’images (1500 environs).
J’ai deux classes d’images (visages et non-visages)
Je mesure la distance entre mon image et toutes les autres.
Je garde les plus petites distances pour déterminer la classe (algo des k-ppv si tu connais).[/ul]
C’est pourquoi je ne peux pas avoir une mesure de distance qui demande trop de calculs (car beaucoup de mesures). J’ai essayé avec la distance euclidienne et je voulais essayer avec cette distance mais je ne vois pas trop comment faire !
Ben oui, le k-ppv ou algorithms des plus proches voisins fonctionnent avec une distance quelle qu’elle soit. Tu peut prendre la distance de Haudorff stricto sensu, autrement dit pour chaque point de A, tu cherche la plus petite distance d’un point de B identique puis tu fais la moyenne. Pour en faire une distance, il te faut faire faire la même chose en inversant A et B mais en terme de complexité tu te retrouves en O(taiile de A fois taille de B) et la distance de A à A décalé de n pixels sera n alors qu’avec les transformées de Fourier, tu auras une complixité en O(taille de A + taille de B) et une invariance par translation. C’est à toi de choisir ta distance en fonction de tes désirs…
Merci je comprends mieux ! Par contre, d’après le Wikipédia (http://fr.wikipedia.org/wiki/Distance_de_Hausdorff_modifi%C3%A9e) c’est la distance de hausdorff modifiée. Et si j’ai bien compris ensuite je prends max(d(A,B),d(B,A)) pour cette distance !
J’ai quand même une question : si pour un point de A, il n’y a pas de point de B identique, quelle valeur on prend ?
Re-Merci.
Il est d’usage de considérer les images comme torique, quand tu sors d’un coté tu recommences de l’autre. L’astuce est de prendre une image que tu quadruplue par symétrie par rapport au coté gauche et au coté bas, tu n’as plus de discontinuité brutale aux bords de ton image, ça enlève tout un tas d’effet indésirable en évitant de particulariser les bords (tous les points du bords auraient des voisins complètement différent sinon). Ça évite par exemple le phénomène de Gibbs lors de la transformation en Jpeg d’une image qui se traduirait par une grave distorsion de l’image après décompression au niveaux des bords de cette image (d’où ma suggestion dans mon premier message).
Cela résout ton problème quand tu calcules la distance d’une image à elle même décalée. Pour deux images distinctes, tu peux mettre comme distance une constante comme la diagonale de l’image.
Merci. En fait je compare des images distinctes, donc je vais mettre une constante (la diagonale de l’image me semble bien !). Par contre, je peux sans doute programmer cet algorithme autrement, mais pour l’instant, le temps de calcul est très long ce qui le rend inutilisable dans mon cas… il faut que je l’améliore…
Merci.
Ben oui, ça te fait un algorithme en O(n^4) où n est une dimension de tes images (largeur et hauteur). La distance avec la transformée de Fourier te fait une distance en O(n².ln(n)), c’est pour ça que je te l’ai suggérée.
[quote=“bert_”]Merci. En fait je compare des images distinctes, donc je vais mettre une constante (la diagonale de l’image me semble bien !). Par contre, je peux sans doute programmer cet algorithme autrement, mais pour l’instant, le temps de calcul est très long ce qui le rend inutilisable dans mon cas… il faut que je l’améliore…
Merci.[/quote]En fait, de ce que j’ai compris, il est impossible d’avoir une distance entre deux points identiques supérieure à la moitié de la diagonale (le nadir du milieu de la photo sur le tore etant les quatre angles qui sont un seul et même point).
Ceci étant dit, etant donné que le but est de faire des comparaisons de distances, peu importe que tu définisse ta distance infinie sur le tore à d au lieu de d/2: l’ordre est respecté.
Sinon, par extension du fait que l’essentiel de tes calculs me semble déboucher sur une comparaison, il me semble inutile d’une part de travailler avec des moyennes (je ne sais pas comment tu calcules finalement tes distances mais il me semble qu’il y a un numerateur commun qui est le nombre de pixels) et comme autre simplification qu’il doit y avoir dans les calculs, tu dois pouvoir simplifier les calculs en travaillant avec les carrés des distances.
Enfin sans comprendre finement de quoi vous parlez ceci etant dit ni connaitre le détail de tes implémentations.
Voici une notion de temps : plus de 2 sec pour mesurer la distances entre deux images de 92*112 !! ça fait long, sachant qu’il faut qe j’en fasse plus de 1500…
Ceci dit, je trouve ça un peu démesuré, il doit y avoir un problème dans mon programme :
[code]gfloat distance_hausdorff(GdkPixbuf *p1, GdkPixbuf *p2)
{
gint i, j;
gint x1, y1, x2, y2;
gint l, h, n;
guchar *pixels1, *pixels2;
gfloat d, temp;
gfloat resultat1, resultat2;
l = gdk_pixbuf_get_width(p1);
h = gdk_pixbuf_get_height(p1);
n = gdk_pixbuf_get_n_channels(p1);
pixels1 = gdk_pixbuf_get_pixels(p1);
pixels2 = gdk_pixbuf_get_pixels(p2);
/* Calcul de la distance entre p1 et p2 */
resultat1 = 0;
for(x1 = 0; x1 < l; x1++)
for(y1 = 0; y1 < h; y1++)
{
temp = sqrt(9292+112112);
i = (y1*l+x1)n;
for(x2 =0; x2 < l; x2++)
for(y2 = 0; y2 < h; y2++)
{
j = (y2l+x2)*n;
if(pixels1[i] == pixels2[j])
{
d = dist(x1, y1, x2, y2);
if(d < temp)
temp = d;
}
}
resultat1 += temp;
}
/* Moyenne */
resultat1 = resultat1/(l*h);
/* Calcul de la distance entre p2 et p1 */
resultat2 = 0;
for(x2 = 0; x2 < l; x2++)
for(y2 = 0; y2 < h; y2++)
{
temp = sqrt(9292+112112);
i = (y2*l+x2)n;
for(x1 =0; x1 < l; x1++)
for(y1 = 0; y1 < h; y1++)
{
j = (y1l+x1)*n;
if(pixels2[i] == pixels1[j])
{
d = dist(x1, y1, x2, y2);
if(d < temp)
temp = d;
}
}
resultat2 += temp;
}
/* Moyenne */
resultat2 = resultat2/(l*h);
/* On retourne max(resultat1, resultat2) */
return (resultat1 > resultat2) ? resultat1 : resultat2;
}[/code]
et voici dist qui calcule la distance euclidienne entre 2 points :
gfloat dist(gint x1, gint y1, gint x2, gint y2)
{
return (sqrt(pow(x1-x2, 2)+pow(y1-y2, 2)));
}
Dans ta fonction gfloat, utilise x*x plutôt que power qui passe au log et prend du temps. Je te suggère même de prendre abs(y1-y2) + abs(x1-x2) qui est une distance équivalente.
Ça ne me fait pas gagner de temps de manière significative !! Je ne vais pas pouvoir utiliser cette distance dans mon algo des k-ppv… À moins qu’il y ait un autre moyen de programmer cette distance !
Merci !!
n représente quoi? (je vois pas son initialisation)
Dans tes “for” la dernière instruction préfère ++var que var++.
T’es obligé de déclarer tout dès le départ?
A vu de nez ce qui te prend du temps c’est l’algo en lui même tu dois comparer chaque pixel avec tout ceux de l’autre image?
J’ai pas suivi la discutions sur les algo avec les 4 boucles “for” imbriquées, mais si c’est pour vérifier des doublons entre deux images?
Si c’est le cas tu peut limiter le nombre de teste (ne pas faire le calcul entre les bords et le milieu). Si c’est le cas tu dois pourvoir gagner 25 à 50% de teste en moins.
On doit pouvoir optimiser les multiplications avec des décalages peut être.
[code] /* On retourne max(resultat1, resultat2) */
return (resultat1 > resultat2) ? resultat1 : resultat2;[/code]
Pourquoi ne pas utiliser max? 
Edit: Oups! Il y a un dernier point qui peut t’aider, les options de compilation. Tu as quoi comme CPU?
Sur mon portable, j’ai un Duo T2250. Mais le programme doit fonctionner sur des machines moins puissantes !
Tu compte le distribuer à grande échelle?
Parce que tant je suis pas fan de ce genre de solution des fois pour un petit prog qu’on doit juste exécuter pour une tâche précise ajouter un -march=prescott -O2 -fomit-frame-pointer ça peut faire gagner 10% du temps d’exécution.
[quote=“Yoko”]Tu compte le distribuer à grande échelle?
Parce que tant je suis pas fan de ce genre de solution des fois pour un petit prog qu’on doit juste exécuter pour une tâche précise ajouter un -march=prescott -O2 -fomit-frame-pointer ça peut faire gagner 10% du temps d’exécution.[/quote]
Non c’est un projet universitaire à rendre !
Je regrette quand même de ne pas pouvoir utiliser cette distance (trop de temps de calcul) car je suis sûr qu’elle aurait été plus adaptée que la disrance euclidienne…
Essaye avec Fourier je te dis…
Petite précision sur ce topic : calculer une distance de Hausdorff en brute-force est à bannir (cf. résultats obtenus par bert_). En règle générale, on préfère d’abord calculer la carte de distances des deux images puis faire un simple parcours pour obtenir la distance finale. Du coup, la complexité est linéaire en fonction du nombre de pixels 