Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1108 connectés 

  FORUM HardWare.fr
  Programmation
  C

  Optimisation d'une fonction img 2D

 
 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Optimisation d'une fonction img 2D

n°1312081
red factio​n
Posté le 23-02-2006 à 11:49:58  profilanswer
 

A coup de grof j'ai remarque que cette partie de code prenait 50% du temps du rendu :S
Quel modifs je pourrais fait pour rendre cette partie un peu plus rapide ?  (mmx?)
 
ici l'algo prend juste les 8 points voisin dun pixels et fait la moyenne, reduce est fixe a 3
eg :  trilinearfilter(img,3,640,480)
 

Code :
  1. void trilinearfilter(BYTE *image,int reduce,int width,int height)
  2. {
  3.     int i,j;
  4.     BYTE *dest;
  5.     int len=width/reduce*height/reduce*3;
  6.     dest=malloc(len);
  7.     for(i=0;i<width/reduce;i++)
  8.     {
  9.         for(j=0;j<height/reduce;j++)
  10.         {
  11.             int cp=(1+j*reduce)*width+(1+i*reduce);
  12.             int rp=j*width/reduce+i;
  13.             int a1=max(cp-width-1,0);
  14.             int a2=max(cp-width,0);
  15.             int a3=max(cp-width+1,0);
  16.             int a4=max(cp-1,0);
  17.             int a6=min(cp+1,width*height);
  18.             int a7=min(cp+width-1,width*height);
  19.             int a8=min(cp+width,width*height);
  20.             int a9=min(cp+width+1,width*height);
  21.             dest[rp*3+0]=(image[a1*3+0]+image[a2*3+0]+image[a3*3+0]+image[a4*3+0]+image[a6*3+0]+image[a7*3+0]+image[a8*3+0]+image[a9*3+0])/8;
  22.             dest[rp*3+1]=(image[a1*3+1]+image[a2*3+1]+image[a3*3+1]+image[a4*3+1]+image[a6*3+1]+image[a7*3+1]+image[a8*3+1]+image[a9*3+1])/8;
  23.             dest[rp*3+2]=(image[a1*3+2]+image[a2*3+2]+image[a3*3+2]+image[a4*3+2]+image[a6*3+2]+image[a7*3+2]+image[a8*3+2]+image[a9*3+2])/8;
  24.         }
  25.     }
  26.     memcpy(image,dest,len);
  27.     free(dest);
  28. }


Message édité par red faction le 23-02-2006 à 11:50:54
mood
Publicité
Posté le 23-02-2006 à 11:49:58  profilanswer
 

n°1312101
skelter
Posté le 23-02-2006 à 12:07:13  profilanswer
 

il y a beaucoup de choses que tu peux pré calculées ('height/reduce', width*height, ...) quand meme, et utilises plus de constantes
 
aussi vérifie l'ordre dans le quel tu accedes aux éléments pour optimiser l'utilisation du cache, la tu parcours ton image en width->height et si c'est équivalent à un tableau [height][width] c'est pas bon

n°1312116
red factio​n
Posté le 23-02-2006 à 12:38:23  profilanswer
 

Code :
  1. void trilinearfilter(BYTE *image,int reduce,int width,int height)
  2. {
  3.     int i,j;
  4.     BYTE *dest,*dp;
  5.     int destwidth=width/reduce;
  6.     int destheight=height/reduce;
  7.     int totalsize=width*height;
  8.     int len=destwidth*destheight*3;
  9.     dp=dest=malloc(len);
  10.     for(j=0;j<destheight;j++)
  11.     {
  12.         for(i=0;i<destwidth;i++)
  13.         {
  14.             int cp=(1+j*reduce)*width+(1+i*reduce);
  15.             int cpup=cp-width;
  16.             int cpdown=cp+width;
  17.             int a1=3*max(cpup-1,0);
  18.             int a2=3*max(cpup,0);
  19.             int a3=3*max(cpup+1,0);
  20.             int a4=3*max(cp-1,0);
  21.             int a6=3*min(cp+1,totalsize);
  22.             int a7=3*min(cpdown-1,totalsize);
  23.             int a8=3*min(cpdown,totalsize);
  24.             int a9=3*min(cpdown+1,totalsize);
  25.             *dp=(image[a1+0]+image[a2+0]+image[a3+0]+image[a4+0]+image[a6+0]+image[a7+0]+image[a8+0]+image[a9+0])>>3; dp++;
  26.             *dp=(image[a1+1]+image[a2+1]+image[a3+1]+image[a4+1]+image[a6+1]+image[a7+1]+image[a8+1]+image[a9+1])>>3; dp++;
  27.             *dp=(image[a1+2]+image[a2+2]+image[a3+2]+image[a4+2]+image[a6+2]+image[a7+2]+image[a8+2]+image[a9+2])>>3; dp++;
  29.         }
  30.     }
  31.     memcpy(image,dest,len);
  32.     free(dest);
  33. }

n°1312128
skelter
Posté le 23-02-2006 à 12:55:33  profilanswer
 

si reduce, width et height ne changent pas d'un rendu à l'autre, le variable cp et celles qui en dépendent peuvent etre précalculées dans une table au moment ou reduce, width et height sont fixés


Message édité par skelter le 23-02-2006 à 12:55:50
n°1312134
red factio​n
Posté le 23-02-2006 à 13:03:39  profilanswer
 

Code :
  1. void trilinearfilter(BYTE *image,int reduce,int width,int height)
  2. {
  3.     int i,j;
  4.     BYTE *dest,*dp;
  5.     int destwidth=width/reduce;
  6.     int destheight=height/reduce;
  7.     int totalsize=width*height;
  8.     int len=destwidth*destheight*3;
  9.     dp=dest=malloc(len);
  10.     for(j=0;j<destheight;j++)
  11.     {
  12.         int cp=(j*width*reduce)+1;
  13.         for(i=0;i<destwidth;i++)
  14.         {
  15.             int cpup=cp-width;
  16.             int cpdown=cp+width;
  17.             BYTE *a0=image+3*max(cpup-1,0);
  18.             BYTE *a1=image+3*max(cpup,0);
  19.             BYTE *a2=image+3*max(cpup+1,0);
  20.             BYTE *a3=image+3*max(cp-1,0);
  21.             BYTE *a4=image+3*min(cp+1,totalsize);
  22.             BYTE *a5=image+3*min(cpdown-1,totalsize);
  23.             BYTE *a6=image+3*min(cpdown,totalsize);
  24.             BYTE *a7=image+3*min(cpdown+1,totalsize);
  25.             *dp=(*(a0+0)+*(a1+0)+*(a2+0)+*(a3+0)+*(a4+0)+*(a5+0)+*(a6+0)+*(a7+0))>>3; dp++;
  26.             *dp=(*(a0+1)+*(a1+1)+*(a2+1)+*(a3+1)+*(a4+1)+*(a5+1)+*(a6+1)+*(a7+1))>>3; dp++;
  27.             *dp=(*(a0+2)+*(a1+2)+*(a2+2)+*(a3+2)+*(a4+2)+*(a5+2)+*(a6+2)+*(a7+2))>>3; dp++;
  28.             cp+=reduce;
  29.         }
  30.     }
  31.     memcpy(image,dest,len);
  32.     free(dest);
  33. }


Message édité par red faction le 23-02-2006 à 13:32:36
n°1312148
skeye
Posté le 23-02-2006 à 13:27:17  profilanswer
 

euh tu redéclares tes variables à chaque tour de boucle, là...[:pingouino]

Message cité 2 fois

---------------
Can't buy what I want because it's free -
n°1312158
red factio​n
Posté le 23-02-2006 à 13:33:25  profilanswer
 

ca pose un probleme ?

n°1312161
skeye
Posté le 23-02-2006 à 13:34:58  profilanswer
 

à tester.[:skeye]
Sors les déclarations de la boucle, au pire ce sera pareil...et au mieux tu éviteras la création/destruction à chaque tour.


---------------
Can't buy what I want because it's free -
n°1312164
red factio​n
Posté le 23-02-2006 à 13:39:14  profilanswer
 

Code :
  1. void trilinearfilter(BYTE *image,int reduce,int width,int height)
  2. {
  3.     int i,j;
  4.     int cp,cpup,cpdown;
  5.     BYTE *dest,*dp,*a0,*a1,*a2,*a3,*a4,*a5,*a6,*a7;
  6.     int destwidth=width/reduce;
  7.     int destheight=height/reduce;
  8.     int totalsize=width*height;
  9.     int len=destwidth*destheight*3;
  10.     dp=dest=malloc(len);
  11.     for(j=0;j<destheight;j++)
  12.     {
  13.         cp=(j*width*reduce)+1;
  14.         for(i=0;i<destwidth;i++)
  15.         {
  16.             cpup=cp-width;
  17.             cpdown=cp+width;
  18.             a0=image+3*max(cpup-1,0);
  19.             a1=image+3*max(cpup,0);
  20.             a2=image+3*max(cpup+1,0);
  21.             a3=image+3*max(cp-1,0);
  22.             a4=image+3*min(cp+1,totalsize);
  23.             a5=image+3*min(cpdown-1,totalsize);
  24.             a6=image+3*min(cpdown,totalsize);
  25.             a7=image+3*min(cpdown+1,totalsize);
  26.             *dp++=(*(a0+0)+*(a1+0)+*(a2+0)+*(a3+0)+*(a4+0)+*(a5+0)+*(a6+0)+*(a7+0))>>3;
  27.             *dp++=(*(a0+1)+*(a1+1)+*(a2+1)+*(a3+1)+*(a4+1)+*(a5+1)+*(a6+1)+*(a7+1))>>3;
  28.             *dp++=(*(a0+2)+*(a1+2)+*(a2+2)+*(a3+2)+*(a4+2)+*(a5+2)+*(a6+2)+*(a7+2))>>3;
  29.             cp+=reduce;
  30.         }
  31.     }
  32.     memcpy(image,dest,len);
  33.     free(dest);
  34. }

 
40 ms

n°1312168
skeye
Posté le 23-02-2006 à 13:42:28  profilanswer
 

Bon après tu peux p-e gagner en déroulant la boucle. Du genre remplacer ton i++ par un i+=4 et dérouler le contenu sur 4...


---------------
Can't buy what I want because it's free -
mood
Publicité
Posté le 23-02-2006 à 13:42:28  profilanswer
 

n°1312172
skeye
Posté le 23-02-2006 à 13:43:15  profilanswer
 

(si tu as un multiple de 4, évidemment. :D)
 
...et plus éventuellement (8, 16...?), faut voir ce que t'y gagnes et si tu peux.:o


Message édité par skeye le 23-02-2006 à 13:44:22

---------------
Can't buy what I want because it's free -
n°1312176
red factio​n
Posté le 23-02-2006 à 13:43:53  profilanswer
 

si je maitrisait les template :p mais bon le projet est en C

Message cité 1 fois
n°1312181
skeye
Posté le 23-02-2006 à 13:46:28  profilanswer
 

(en faire plusieurs à la suite te permettrait de réutiliser tes indices aX au lieu de les recalculer pour chaque...;))


---------------
Can't buy what I want because it's free -
n°1312194
skelter
Posté le 23-02-2006 à 14:01:30  profilanswer
 

red faction a écrit :

si je maitrisait les template :p mais bon le projet est en C


 
meme avec les templates du c++ tu ne pourrais pas dérouler une boucle dont le nombre d'itération n'est pas connu à la compilation, et un bon compilateur peu faire la meme chose
 
que représente width, height et reduce ? si c'est fixe entre chaque rendu tu peux tout précalculé

n°1312209
Taz
bisounours-codeur
Posté le 23-02-2006 à 14:15:30  profilanswer
 

skeye a écrit :

euh tu redéclares tes variables à chaque tour de boucle, là...[:pingouino]


ce qui ne change rien. plutot que d'optimiser à l'aveugle, regarde l'assembleur et fait des mesures. je suis pas sur du tout qu'il y ait une différence entre ton code du début et le dernier.
 
 
par contre ça :
 
#
           a0=image+3*max(cpup-1,0);
#
           a1=image+3*max(cpup,0);
#
           a2=image+3*max(cpup+1,0);
 
 
 
t'as certainement moyen d'éviter de faire ces 3 max. idem pour les min.

Message cité 1 fois
n°1312210
chrisbk
-
Posté le 23-02-2006 à 14:17:27  profilanswer
 

skeye a écrit :

euh tu redéclares tes variables à chaque tour de boucle, là...[:pingouino]


mais cesses donc de dire des anneries [:pingouino]

Message cité 1 fois
n°1312212
chrisbk
-
Posté le 23-02-2006 à 14:19:25  profilanswer
 

taz a raison. Par exemple regarde ce que ton compilo fais de ca :
 

Code :
  1. int cp=(1+j*reduce)*width+(1+i*reduce);


 
s'ils te sort bien les invariants de la boucle et remplace ta multiplication par un increment tout seul comme un grand, bin change rien, sinon fais le, la tu fais 3muls par pixel qui servent a rien


Message édité par chrisbk le 23-02-2006 à 14:20:06
n°1312213
red factio​n
Posté le 23-02-2006 à 14:20:17  profilanswer
 

Code :
  1. void trilinearfilter(BYTE *image,int reduce,int width,int height)
  2. {
  3.     int i,j;
  4.     BYTE *cp,*cpup,*cpdown;
  5.     BYTE *dest,*dp,*a0,*a1,*a2,*a3,*a4,*a5,*a6,*a7;
  6.     BYTE *lastp=image+(width*height*3);
  7.     int linewidth=3*width;
  8.     int destwidth=width/reduce;
  9.     int destheight=height/reduce;
  10.     int len=destwidth*destheight*3;
  11.     dp=dest=malloc(len);
  12.     for(j=0;j<destheight;j++)
  13.     {
  14.         cp=image+j*reduce*linewidth+3;
  15.         for(i=0;i<destwidth;i++)
  16.         {
  17.             cpup=cp-linewidth;
  18.             cpdown=cp+linewidth;
  19.             a0=max(cpup-3,image);
  20.             a1=max(cpup,image);
  21.             a2=max(cpup+3,image);
  22.             a3=max(cp-3,image);
  23.             a4=min(cp+3,lastp);
  24.             a5=min(cpdown-3,lastp);
  25.             a6=min(cpdown,lastp);
  26.             a7=min(cpdown+3,lastp);
  27.             *dp++=(*(a0+0)+*(a1+0)+*(a2+0)+*(a3+0)+*(a4+0)+*(a5+0)+*(a6+0)+*(a7+0))>>3;
  28.             *dp++=(*(a0+1)+*(a1+1)+*(a2+1)+*(a3+1)+*(a4+1)+*(a5+1)+*(a6+1)+*(a7+1))>>3;
  29.             *dp++=(*(a0+2)+*(a1+2)+*(a2+2)+*(a3+2)+*(a4+2)+*(a5+2)+*(a6+2)+*(a7+2))>>3;
  30.             cp+=reduce*3;
  31.         }
  32.     }
  33.     memcpy(image,dest,len);
  34.     free(dest);
  35. }

n°1312221
chrisbk
-
Posté le 23-02-2006 à 14:23:18  profilanswer
 

sinon tu fais des alias plein pot, d'une part ca peut perturber le compilo et d'autre part ca te fais faire un quintal d'addition inutile (tous tes a1...an)
 
Vu la facon dont tu accede à tes données, je crains qu'il n'y ai pas grand chose a faire en mmx
 
oups pardon c'est red faction le roi de l'alias
 
 

Code :
  1. *(a0+0)


 
a part rendre la lecture penible, c'est quoi l'interet par rapport a a0[0] ?

Message cité 2 fois
Message édité par chrisbk le 23-02-2006 à 14:24:35
n°1312229
red factio​n
Posté le 23-02-2006 à 14:27:45  profilanswer
 

Premiere version : 1.5s
derniere : 260ms

n°1312232
red factio​n
Posté le 23-02-2006 à 14:29:01  profilanswer
 

chrisbk a écrit :

sinon tu fais des alias plein pot, d'une part ca peut perturber le compilo et d'autre part ca te fais faire un quintal d'addition inutile (tous tes a1...an)
 
Vu la facon dont tu accede à tes données, je crains qu'il n'y ai pas grand chose a faire en mmx
 
oups pardon c'est red faction le roi de l'alias

 

Code :
  1. *(a0+0)


 
a part rendre la lecture penible, c'est quoi l'interet par rapport a a0[0] ?


c quoi se bo*** :o  je demande comment ameliorer on me dit : "tu peux pré calculées ('height/reduce', width*height, ...)"

Message cité 1 fois
n°1312233
nargy
Posté le 23-02-2006 à 14:29:06  profilanswer
 

Une petite suggestion à propos de:
    memcpy(image,dest,len);
tu peux p-e t arranger pour faire les calculs inplace, avec un tableau plus petit (3 lignes de pxl) pour garder les valeurs initiales.

n°1312243
nargy
Posté le 23-02-2006 à 14:33:26  profilanswer
 

Pour éviter les min et max, tu peux envisager de travailler sur une taille d image plus grande d un pixel sur chaque bord.

Message cité 1 fois
n°1312244
red factio​n
Posté le 23-02-2006 à 14:34:13  profilanswer
 

chrisbk a écrit :


oups pardon c'est red faction le roi de l'alias



 
 :pfff:  

chrisbk a écrit :

Code :
  1. *(a0+0)


 
a part rendre la lecture penible, c'est quoi l'interet par rapport a a0[0] ?


Bon ok cest pa bon

Message cité 1 fois
n°1312247
chrisbk
-
Posté le 23-02-2006 à 14:34:28  profilanswer
 

red faction a écrit :

c quoi se bo*** :o  je demande comment ameliorer on me dit : "tu peux pré calculées ('height/reduce', width*height, ...)"


 
du calme [:twixy] chu tellement pas reveilé que j'avais vu que le topic etait de toi :d

n°1312249
red factio​n
Posté le 23-02-2006 à 14:34:59  profilanswer
 

nargy a écrit :

Pour éviter les min et max, tu peux envisager de travailler sur une taille d image plus grande d un pixel sur chaque bord.


 
oui mais il faut redecouper apres :/
 

Code :
  1. void trilinearfilter(BYTE *image,int reduce,int width,int height)
  2. {
  3.     int i,j;
  4.     BYTE *cp,*cpup,*cpdown;
  5.     BYTE *dest,*dp,*a0,*a1,*a2,*a3,*a4,*a5,*a6,*a7;
  6.     BYTE *lastp=image+(width*height*3);
  7.     int linewidth=3*width;
  8.     int destwidth=width/reduce;
  9.     int destheight=height/reduce;
  10.     int len=destwidth*destheight*3;
  11.     dp=dest=malloc(len);
  12.     for(j=0;j<destheight;j++)
  13.     {
  14.         cp=image+j*reduce*linewidth+3;
  15.         for(i=0;i<destwidth;i++)
  16.         {
  17.             cpup=cp-linewidth;
  18.             cpdown=cp+linewidth;
  19.             a0=max(cpup-3,image);
  20.             a1=max(cpup,image);
  21.             a2=max(cpup+3,image);
  22.             a3=max(cp-3,image);
  23.             a4=min(cp+3,lastp);
  24.             a5=min(cpdown-3,lastp);
  25.             a6=min(cpdown,lastp);
  26.             a7=min(cpdown+3,lastp);
  27.             *dp++=(a0[0]+a1[0]+a2[0]+a3[0]+a4[0]+a5[0]+a6[0]+a7[0])>>3;
  28.             *dp++=(a0[1]+a1[1]+a2[1]+a3[1]+a4[1]+a5[1]+a6[1]+a7[1])>>3;
  29.             *dp++=(a0[2]+a1[2]+a2[2]+a3[2]+a4[2]+a5[2]+a6[2]+a7[2])>>3;
  30.             cp+=reduce*3;
  31.         }
  32.     }
  33.     memcpy(image,dest,len);
  34.     free(dest);
  35. }


 
210 ms pour du 1994x2610, qui dit mieux ??
 
joffre une glace a celui qui me donne une meilleure solution

Message cité 1 fois
Message édité par red faction le 23-02-2006 à 14:36:56
n°1312250
chrisbk
-
Posté le 23-02-2006 à 14:35:14  profilanswer
 

red faction a écrit :

:pfff:  


 
bah tu vas pas me quoter 15x non plus ?
 

red faction a écrit :


Bon ok cest pa bon


nan mais jpense ca change rien au code generer, c'est juste que c'est moche

n°1312264
red factio​n
Posté le 23-02-2006 à 14:38:22  profilanswer
 

bah moi non plus jsuis pa reveille  
deja que jme suis amene a la bourre au taf  
 
10h30 c pa des heures :whistle:

n°1312302
Lam's
Profil: bas.
Posté le 23-02-2006 à 14:53:53  profilanswer
 

Allez, courage: découpe ton algo en:

  • bord supérieur
  • bord gauche - centre - bord droit
  • bord inférieur

Et fait sauter les a1, a2, etc. dans la partie du centre....

n°1312366
skeye
Posté le 23-02-2006 à 15:39:10  profilanswer
 

Taz a écrit :

ce qui ne change rien.


 
C'est bien ce que je disais, au pire c'est pareil.[:petrus75]
 

chrisbk a écrit :

mais cesses donc de dire des anneries [:pingouino]


 
C'est pas pour aujourd'hui, ça.[:dawa]
 
...et essayer de dérouler un peu la boucle si possible pour gagner sur les calculs de positions, aneries aussi? [:petrus dei]
 


---------------
Can't buy what I want because it's free -
n°1312391
nargy
Posté le 23-02-2006 à 16:00:53  profilanswer
 

Citation :


Pour éviter les min et max, tu peux envisager de travailler sur une taille d image plus grande d un pixel sur chaque bord.


 
Peut ne s appliquer qu au tableau temporaire de 3 lignes.
Au total: Gain en mémoire + gain en cache + gain min/max
 

n°1313320
el muchach​o
Comfortably Numb
Posté le 24-02-2006 à 22:27:51  profilanswer
 

red faction a écrit :


 
210 ms pour du 1994x2610, qui dit mieux ??
 
joffre une glace a celui qui me donne une meilleure solution


Bah, tu vas voir l'API de ta carte graphique...
Sinon la suggestion de Lam's et nargy est certainement la meilleure, ton temps de calcul devrait faire un bond.
Ou au minimum vérifie que min/max sont des macros et pas des appels de fonctions (en C, normalement c'est le cas).


Message édité par el muchacho le 25-02-2006 à 08:01:16
n°1313401
Taz
bisounours-codeur
Posté le 25-02-2006 à 08:52:19  profilanswer
 

personne m'écoute avec l'histoire des min/max à la con ...

mood
Publicité
Posté le   profilanswer
 


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C

  Optimisation d'une fonction img 2D

 

Sujets relatifs
[résolu]probleme entre fonction et regex[ MySQL 4.1 ] Créer une fonction MySQL
VBA - Probleme Appel de fonctionscript JS qui affiche une zone de texte en fonction d'un select
DirectX: déplacer la caméra en fonction de la sourisfonction FORM : modification taille
Fonction Recherche[JavaS] recuperer le type de navigateur et exec une fonction
la fonction select()...VBA : Fonction Dir et attributs.
Plus de sujets relatifs à : Optimisation d'une fonction img 2D

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.102 secondes

Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR