Temps d'execution très lent

Version imprimable

Bonjour à tous,
J’ai écrit un programme qui permet d’attribuer à chaque pixel d’une image la valeur minimale de tous les pixels voisins qui se trouvent à une distance inférieure ou égale à d (d représente le rayon d’un disque).

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
 
int tri[1000];
H=Image1->Picture->Bitmap->Height;
W=Image1->Picture->Bitmap->Width;
for(int x=0;x<W;x++)
        for(int y=0;y<H;y++)
        {
        a=Image1->Picture->Bitmap->Canvas->Pixels[x][y];
        b=a%256;
        g=(a/256)%256;
        r=(a/(256*256))%256;
        Image[x][y]=(int)(r*0.299+g*0.587+b*0.114);
        }
 
int px, py;
double d;
int min;
for(int x = 0; x < W; x++)
    for(int y = 0; y < H; y++)
       {
       int k=1;
       for (int i = -50; i <= +50; i++)
           {
           px = x + i;
           for(int j = -50; j <= +50; j++)
              {
               py = y + j;
               if((px >= 0) && (px < W) && (py >= 0) && (py < W))
                 {
 
                  d=sqrt(pow(x-px,2)+pow(y-py,2));
 
		  if (d <= 50)
                     {
                     tri[k]=Image[px][py];
                     k=k+1;
                     }
                   }
                }
             }
             min=tri[1];
             for (int l=2;l<=k;l++)  {
                                     if (min>tri[l])min=tri[l];
                                     }
image[x][y]=min;
        }
 
for(int x=0;x<W;x++)
    for(int y=0;y<H;y++)
    {
    Image1->Canvas->Pixels[x][y]=(TColor)((int)(image[x][y]+256*image[x][y]+256*256*image[x][y]));
    }

Mon problème est le suivant : quand d augmente l’exécution devient plus lente et mon application nécessite un d>=50:aie: .
Si vous avez une idée pour résoudre ce problème veuillez me laisser un message;)

15/07/2007, 14h40
DjmSoftware

Bonjour
ton code me semble obscur
qu'en est il de la variable <image> ,<Image> et <Image1>
cordialement
15/07/2007, 16h30
bahiatoon
:salut:
Pour <image> et <Image> il suffit d'ajouter:
Code:

1 2 3 4 5 6 7 #pragma package(smart_init) #pragma resource "*.dfm" TForm1 *Form1; int H,W,a,r,g,b; unsigned char image[1000][1000]; byte Image[1000][1000];
<Image1> représente le nom de l'image du composant graphique TImage

A+

Code:

1 2 3 d=sqrt(pow(x-px,2)+pow(y-py,2)); if (d <= 50) ....
sqrt et pow sont des fonctions couteuses en temps de calcul. Il est plus rapide de faire
Code:

1 2 3 4 int d; d=(x-px)*(x-px)+(y-py)*(y-py);// ou d = i*i+j*j if (d <= 2500) .....

16/07/2007, 18h34
bahiatoon
Salut,
Citation:
sqrt et pow sont des fonctions couteuses en temps de calcul. Il est plus rapide de faire

Code:

1 2 3 4 5 int d; d=(x-px)*(x-px)+(y-py)*(y-py);// ou d = i*i+j*j if (d <= 2500) .....
je viens de l'essayer et malheureusement ça donne le même résultat:aie:

A+

Salut, un petit conseil essaie d'optimiser ton code. Par exemple dans ta boucle:
Code:

1 2 3 4 5 6 7 8 for(int y=0;y<H;y++) { a=Image1->Picture->Bitmap->Canvas->Pixels[x][y]; b=a%256; g=(a/256)%256; r=(a/(256*256))%256; Image[x][y]=(int)(r*0.299+g*0.587+b*0.114); }
Essai d'utiliser moins d'allocation de mémoire si c'est possible, ne déclare pas de variable si ce n'est pas pour les utiliser plus d'une fois:
Code:

1 2 3 4 5 6 7 for(int y=0;y<H;y++) { a = Image1->Picture->Bitmap->Canvas->Pixels[x][y]; Image[x][y]=(int)(((a/(256*256))%256) * 0.299 + ((a/256)%256) * 0.587 + (a%256) * 0.114); }
En plus, ne calcule pas des valeurs que tu conais (256*256 = 65536):
Code:

1 2 3 4 5 6 7 for(int y=0;y<H;y++) { a = Image1->Picture->Bitmap->Canvas->Pixels[x][y]; Image[x][y]=(int)(((a/(65536))%256) * 0.299 + ((a/256)%256) * 0.587 + (a%256) * 0.114); }
Se n'est pas ceci qui va faire un gros changement, mais c'est un début. Une autre chose que tu peux c'est d'essayer d'utiliser moins de boucle for, essaie d'en inclure une dans les autres quand c'est possible.

PS: je ne suis pas au courant de tout les optimisations que fait le compilateur.

Salut !

Peut-être en commençant par :

Code:

1
2
3
4
5
6
7
class jPixel
{
public :
Byte Blue;
Byte Green;
Byte Red;
};

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
jPixel *Pixel;
int b;
int r;
int g;
Graphics::TBitmap *B = Image1->Picture->Bitmap;
 
for(int y = 0; y < B->Height; y++)
    {
    Pixel = (jPixel*)B->ScanLine[y];
    for(int x = 0; x < B->Width; x++)
        {
        b = Pixel->Blue * 11; //0.114
        g = Pixel->Green * 59; //0.587
        r = Pixel->Red * 30; //0.299
        Image[y][x] = (Byte)((b + g + r) / 100);
        Pixel++;
        }
    }

Ici, j'ai supposé que l'on travaille sur un bitmap 24 bits.

A plus !

17/07/2007, 19h00
bahiatoon

Salut,

J'ai suivi tous vos conseils mais malheuresement le problème persiste:bug:

A+

Salut !

Ensuite remplacer :

Citation:

d=sqrt(pow(x-px,2)+pow(y-py,2));

par :

Code:

d = hypot(x-px, p-py); //racine de a²+b² est donné par hypot

Puis remplacer la partie :

Citation:

for(y)
for(x)
Image1->Canvas->Pixels[x][y]=(TColor)((int)(image[x][y]+256*image[x][y]+256*256*image[x][y]));

par (selon le même principe...):
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 Byte v; for(y=0; y < B->Height...) { Pixel = (jPixel*)B->ScanLine[y]; for(int x = 0; x < B->Width...) { v = image[y][x]; //ici selon ma propre vision au niveau du tableau Pixel->Blue = v; Pixel->Green = v; Pixel->Red = v; Pixel++; } }
Plus tard en soirée... je testerai l'ensemble...

Salut !

17/07/2007, 22h44
bahiatoon

:merci:

Salut !

Cette érosion de l'image a déjà été abordée (à l'époque c'était avec un seuillage max il me semble)

En fait, il faut précalculer les offsets pour chaque point sur le disque de manière à ne pas le faire dans le traitement, sinon, on a une grande redondance au niveau calcul pour chaque centre (x,y).

Code:

1
2
3
int Rayon;  //ici Rayon <= 50
int Ofx[10000]; // 100 * 100
int Ofy[10000];

Précalculer les offsets :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int NbOf=0;
for(int y = -Rayon; y <= Rayon; y++)
    {
    for(int x = -Rayon; x <= Rayon; x++)
        {
        d = sqrt((x*x) + (y*y)); //un peu plus rapide que hypot
        if(d < Rayon)
            {
            Ofx[NbOf] = x;
            Ofy[NbOf] = y;
            NbOf++;
            }
        }
    }

Pour le traitement :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(int y = 0; y < he; y++)
    {
    for(int x = 0; x < we; x++)
        {
        min = 0xFF; //max = 0;
        for(int of=0; of < NbOf; of++)
            {
            px = x + Ofx[of];
            py = y + Ofy[of];
            if((py>=0) && (py<he) && (px>=0) && (px<we))
                {
                v = I[py][px];
                if(min > v) min = v; // if(max < v) max = v; 
                }
            }
        T[y][x] = min; // T[y][x] = max;
        }
    //Caption = IntToStr(y); //Echo de la progression
    }

A plus !

Il y a des erreurs dans le code que tu proposes :
- 1

Code:

1
2
3
for (int l=2;l<k;l++)  {
          if (min>tri[l])min=tri[l];
   }

-2 plus grave, la dimension de tri est beaucoup trop faible et conduit presque à coup sûr à des dépassements pour d = 50. La dimension de sécurité devrait être de 4*d*d. Ceci peut expliquer des comportements bizarres pour d de l'ordre de 20 ou supérieur.
- Il est inutile de calculer d avec puissance, racine carrée ou hypothénuse
- la valeur de d est la même pour i et -i et pour j et -j. Les boucles i et j de 0 à d devrait suffire.
- Il n'est peut être pas astucieux de déclarer ces variables dans l'instruction for, ce qui amène à leur création/destruction à chaque pas de la boucle supérieure.

Je te propose qq chose du genre

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
int i,j,x,y;
int p;
int min;
int d;
int L = 50;
int L2 = L*L;
for(x = 0; x < W; x++)
    for(y = 0; y < H; y++)
    {
        min = 255; // si Image est un tableau de unsigned char
        for (i = 0; i <= L; i++)
        {
           d = i*i;
           for(j = 0; j <= L; j++)
           {
               if (d+ j*j > L2) break;
               if(x+i<W)
               {
                  if(y+j<W)
                  {
                     p = Image[x+i][y+j];
                     min = min > p ? p : min;
                  }
                  if(y-j>=0)
                  {
                     p=Image[x+i][y-j];
                     min = min > p ? p : min;
                   }
               }
               if(x-i>=0)
               {
                  if(y+j<W)
                  {
                     p=Image[x-i][y+j];
                     min = min > p ? p : min;
                  }
                  if(y-j>=0)
                  {
                     p=Image[x-i][y-j];
                     min = min > p ? p : min;;
                  }
               }
            }
 
        }
 
          image[x][y]=min;
    }

18/07/2007, 18h08
henderson

Salut !

J'ai supprimé le tableau tri puisqu'il est inutile (il me semble) !
Par ailleurs, il vaut mieux précalculer l'offset des points dans le disque.
Parce que dans le code qui a été donné, ce que l'on fait pour (0,0) on le répète sans cesse de y en y et de x en x... ce qui représente une perte de temps énorme !

Ce faisant, chez moi, ça divise le temps de calcul par 6 !

A plus !
18/07/2007, 22h48
bahiatoon

Salut à tous,

Merci pour vos messages:king:

je vais tout essayer maintenant;)
henderson à écrit:

Citation:

il faut précalculer les offsets pour chaque point sur le disque

ma question va peut être te paraitre bizarre:oops: <les offsets> c'est quoi?

A+
18/07/2007, 23h22
bahiatoon

Citation:

-2 plus grave, la dimension de tri est beaucoup trop faible et conduit presque à coup sûr à des dépassements pour d = 50. La dimension de sécurité devrait être de 4*d*d. Ceci peut expliquer des comportements bizarres pour d de l'ordre de 20 ou supérieur.

Mille mercis:king: en changeant la dimension de tri j'arrive à visualiser l'image pour d=50 :yaisse2:
18/07/2007, 23h44
henderson

Salut !

En parlant d'offset, je voulais parler des coordonnées relatives pour chaque point du disque depuis un centre quelconque (x,y) sur ton image.
On a donc bien à un moment donné x+i et y+j.
Le fait de les précalculer revient également à limiter le nombre de points à ce qui est utile pour la surface du disque. C'est autant que le traitement n'aura pas à vérifier.
Ton algo lui, calcule en permanence ces coordonnées relatives pour chaque cercle en (x,y) en vérifiant à chaque fois si un point d'une surface carré est celui d'un disque, d'où la lenteur du traitement.

A plus !
19/07/2007, 23h45
bahiatoon

:salut:

Je vous remercie de tout coeur, grâce à vous mon problème est résolu:lahola: