Distance de Hausdorff

Version imprimable

Bonsoir,

J'ai réalisé la fonction suivante pour calculer la distance de Hausdorff entre deux images (pixbuf) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
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(92*92+112*112);
    i = (y1*l+x1)*n;
    for(x2 =0; x2 < l; x2++)
      for(y2 = 0; y2 < h; y2++)
        {
          j = (y2*l+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(92*92+112*112);
    i = (y2*l+x2)*n;
    for(x1 =0; x1 < l; x1++)
      for(y1 = 0; y1 < h; y1++)
        {
          j = (y1*l+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;
}

Avec la fonction qui calcule la distance euclidienne entre deux points :

Code:

1
2
3
4
gfloat dist(gint x1, gint y1, gint x2, gint y2)
{
  return  sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

Je calcule sur des images de 92*112 pixels. Le problème c'est que le temps de calcul est trop important (+ de 2 sec pour la mesure entre deux images) !! et il faudrait que j'en fasse plus de 1500 !!! TROP long !!

N'y aurait-il pas une astuce pour assouplir ce calcul ??

Merci.

Bonjour,

ça serait pas plus un problème d'algo/math, histoire de factoriser les calculs ?

Citation:

Envoyé par bert_

Code:

sqrt(92*92+112*112)

Tu peux déjà le calculer ça ?
ça donne :

Code:

144,94136745594751011321656715697

A voir la précision des double sur ta machine mais ça me parais suffisant.
Citation:
Envoyé par bert_
Code:

1 2 3 4 gfloat dist(gint x1, gint y1, gint x2, gint y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); }
Cette fonction semble être au coeur de l'algo et appelée un grand nombre de fois.

Voici une idée :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <stdio.h> #include <stdlib.h> #include <time.h> #include <math.h> #define COUNT 10000000 #define dist_o(x1, y1, x2, y2) sqrt ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) float dist(int x1, int y1, int x2, int y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } int main (void) { int i; clock_t start, end; float result = 0.0; start = clock (); for (i = 0; i < COUNT; i++) { result = dist (92, 112, 92, 112); } end = clock (); printf ("Temps en secondes : %f\n", (end - start) / (double)CLOCKS_PER_SEC); start = clock (); for (i = 0; i < COUNT; i++) { result = dist_o (92, 112, 92, 112); } end = clock (); printf ("Temps en secondes : %f\n", (end - start) / (double)CLOCKS_PER_SEC); return 0; }
Sans optimisation (-O0) :
Code:

1 2 Temps en secondes : 0.640000 Temps en secondes : 0.031000
Avec (-O3) :
Code:

1 2 Temps en secondes : 0.015000 Temps en secondes : 0.016000

14/05/2007, 23h54
bert_

Je ne comprends pas trop ce que tu as fait comme modification ? C'est quoi la verison avec optimisation ? Quelle optimisation as-tu faite ?

1 centième de seconde pour caucler 10 000 000 de fois la distance, ca peut être bien !!
Merci.
15/05/2007, 09h32
gege2061

Citation:

Envoyé par bert_

Je ne comprends pas trop ce que tu as fait comme modification ? C'est quoi la verison avec optimisation ? Quelle optimisation as-tu faite ?

1 centième de seconde pour caucler 10 000 000 de fois la distance, ca peut être bien !!
Merci.

J'ai juste mis la fonction sous forme de macro.

Pour info le premier temps correspond à ton code, le second à mon optimisation.

Sans opimisation du compilateur, tu gagne le temps d'appel à la fonction.
Si tu demande au compilateur le maximum d'optimisation au niveau vitesse, il est plus doué que nous : il replace surement l'appel à la fonction par le code, comme pour notre macro mais il fait autre chose (tu peux regarder le code en assembleur si tu veux t'amuser).

C'est généralement le cas, le mieux à faire est de l'aider, par exemple il peux calculer

Code:

92*92+112*112

mais ne connaissant pas le rôle de la fonction sqrt, il ne peux pas calculer le résultat. Sachant que cette fonction prend relativement beacoup de temps pour calculer une constante (toi tu le sais), autant le faire !