Discussion :

[bert_]

Bonsoir,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[gege2061]

Bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

sqrt(92*92+112*112)

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

144,94136745594751011321656715697

A voir la précision des double sur ta machine mais ça me parais suffisant.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 x :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
Temps en secondes : 0.640000
Temps en secondes : 0.031000

Avec (-O3) :

Code x :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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.

[gege2061]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 !