Optimisation algo filtre médian

Bonjour,

J'ai écrit un algorithme permettant de réaliser un filtre median sur des images, et je souhaiterais l'optimisé afin que son execution prenne moins de temps.

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

void CWebCam::filtreMedianImage ( Image &image, Image &nvelImage, int taille ) {   // classe dans l'ordre les pixels de la fenetre traitée et prend la valeur du milieu et l'affecte au pixel du centre de la fenetre   int k = taille %2; int t=taille/2; Image imageAgrandi, imageTemp; int iMat, jMat, n; int *tablNdg; int ordre = ((taille*taille)+1)/2;   tablNdg=new int [taille*taille];     agrandirBordsImage(image,imageAgrandi,taille);   //allocation de l'image temporaire allocationImage(imageTemp,imageAgrandi.hauteur,imageAgrandi.largeur,imageAgrandi.type);   for ( int i=t; i<(int)(imageAgrandi.hauteur-t); i++ ) { for ( int j=t; j<(int)(imageAgrandi.largeur-t); j++ ) { n=0; for ( iMat=i-t; iMat<=i+t; iMat++ ) { for ( jMat=j-t; jMat<=j+t; jMat++) { tablNdg[n]=imageAgrandi.ptrLigne[iMat][jMat]; n++; }   } triTableauOrdreCroissant(tablNdg,(taille*taille)); imageTemp.ptrLigne[i][j]=tablNdg[ordre]; } } //remise de l'image à la bonne taille reduireBordsImage(imageTemp,nvelImage,taille);   liberationImage(imageAgrandi); liberationImage(imageTemp);   delete tablNdg; tablNdg=NULL; }     typedef struct { unsigned long hauteur; unsigned long largeur; unsigned char type; // BINARY, GRAY ou RGB unsigned char* pixel; unsigned char** ptrLigne; } Image;

---

Si vous avez des idées je suis preneur, car j'ai aussi mes fonctions de morphologie maths à optimiser aussi.

Il y a une implémentation rapide du filtre médian qui se base sur des histogrammes.

Tu peux trouver des infos en cherchant : "fast median filter"

Il y a une implémentation en Java ici :
http://subversion.developpez.com/pro...nOperator.java

Avec une implémentation de l'histogramme qui est optimisé pour trouvé la valeur médiane d'un histogramme :
http://subversion.developpez.com/pro...Histogram.java

Salut,

Je crois voir que c'est du c/c++.

Dans le cadre d'un projet, j'avais implémenté un filtre médian 3x3 en XMMX. Pour cela il avait fallu repenser le filtre médian pour que l'opération soit parallélisable. Et j'étais parvenu à un filtre médian entièrement codé en XMMX calculant le médian 16 pixels par 16 pixels, soit plus de 16 fois plus vite qu'en c/c++. Le "plus de (16 fois)" venant du gain amené par le codage en assembleur.

C'est dommage, je ne me rappelle plus des performances sur le poste client, mais en XMMX sur des images monochrome 16 bits (donc traitement 8 pixels par 8 pixels) sur des images 1120 pixels par 725 pixels, je crois que j'étais inférieur à 10ms. J'ai refait les tests sur mon PC portable ACER TravelMate 7720 Intel Centrino, en c/c++ je suis entre 1000ms et 1090ms, en XMMX je suis aux environs de 15ms. Bon après je ne me rappelle pas comment été codé mon filtre médian 3x3 en c/c++. Et je ne connais pas de soft qui le fasse en 16 bits pour te donner une comparaison avec une application reconnue.

A noter que cela ne fonctionne que sur un filtre médian 3x3 car après il manque des registres pour stocker les données.

Après tu n'as peut-être pas accès à du XMMX.

Sinon et à mon avis, une implémentation rapide nécessite de passer par des fonctions spécifiques à une taille de filtre (une fonction pour du 3x3, une pour du 5x5, etc) pour éviter la boucle for de parcours du noyau.

Ensuite, par exemple, au code suivant :

Code:

---

1 2	for(int index = 0; index < count; index++) dst[index] = src[index];

---

il faut préfèrer celui-ci

Code:

---

1 2 3 4 5 6

unsigned char * ptrsrc = src; unsigned char * ptrend = src + count; unsigned char * ptrdst = dst;   while(ptrsrc < ptrend ) *ptrdst++ = *ptrsrc++;

---

Tu évites ainsi de trainer un "index" en plus. Dans ce cas c'est peut-être pas flagrant mais sur des choses compliquées on y gagne.

Déroule un maximum les boucles toi-même. Même si on me rétorquera que le compilateur le fait mieux que nous, en faisant l'effort de dérouler soi-même on voit plus souvent les optimisations importantes qu'on n'aurait pas vues en se la jouant à la feignante.

N'alloue pas de mémoire (style ton allocation d'image temporaire) à chaque passage dans la fonction. L'allocation de mémoire prend du temps. Par ailleurs ça oblige le processeur à jouer avec son cache. L'idée est de travailler systématiquement avec les mêmes buffers. Alloue les buffers une bonne fois pour toute. Par exemple mon filtre médian XMMX au premier passage il mets un peu plus de 80ms puis il tombe et reste à 15ms les autres fois. La différence entre le premier passage et le suivant c'est que dans le premier il met en cache les buffers à utiliser (ça prend du temps) puis pour les autres fois, comme il les a déjà en cache, il fait juste le processing.

Utilise les const quand tu définis des variables sensées rester à leur valeur.

Code:

---

1 2 3 4

const int k = taille %2; const int t=taille/2; const int ordre = ((taille*taille)+1)/2;

---

Cela n'introduira à tous les coups une optimisation de la part du compilateur mais cela lui permet de mettre en œuvre toutes les optimisations s'il en connaît. A noter que niveau mémoire c'est mieux (je n'en suis pas sur).

L'histoire du const c'est plus philosophique qu'autre chose mais ça illustre bien ce qu'est l'optimisation. L'optimisation c'est une logique poussée au bout. On supprime tous les degrés de liberté inutiles (constantes et non variables, dérouller les boucles). de manière à ce que le compilateur produise le code le plus simple et donc qu'il fasse intervenir ses meilleures optimisations.

Flo.

bonjour,

pour optimaliser ton code, tu dois sortir un max de calcul de tes boucles.

par exemple:

for ( int i=t; i<(int)(imageAgrandi.hauteur-t); i++ )
devient
int iMax = imageAgrandi.hauteur-t;
for ( int i=t; i<iMax; i++ )

(même avec J)

il faut regarder également ta fonction triTableauOrdreCroissant()...
Il y a des fonction qui permettent de calculer la valeur médiane qu'en calculant jusqu'à la moitié de la solution (pas besoin d'aller plus loin).

pour reprendre les valeur de ta matrice image, tu peux faire un memcpy d'une matrice sur une autre (tant que tu ne change pas de ligne), ce qui ne te fera que recherche la valeur de ta dernière ligne

...

Oui effectivement. Bien vu.

A la relecture du code de TheCreech, je me demande si la prise en compte du bord de l'image présente vraiment un intérêt.

J'ai toujours considéré que si effectivement des logiciels d'édition graphique tels que Photoshop et autres se devaient de prendre en compte les bords, en vision industrielle, par contre, on s'arrange généralement pour mettre au centre de l'image les éléments d'intérêt. Cela permet de ne pas avoir à s'intéresser aux bords de l'image et d'accélérer les opérations.

Ceci étant dit, si t'y tiens à tes bords, t'y tiens ... il n'y a que toi que ça regarde.

Cependant, si t'y tiens je te conseille de revoir ta méthode pour prendre en compte les bords car là encore tu crées de la mémoire dans ta fonction puisque tu utilises :

Code:

---

1 2	liberationImage(imageAgrandi);

---

C'est pas bon du tout. Sache qu'il y a tout un tas de techniques pour prendre "intelligemment" les bords en compte. Techniques que je connais de très loin mais qui avaient, me semble-t-il, fait l'objet d'une discussion sur le forum.

Citation:

---

Il y a des fonction qui permettent de calculer la valeur médiane qu'en calculant jusqu'à la moitié de la solution (pas besoin d'aller plus loin).

---

Il y a std::nth_element .

Flo.