[Image]Implémentation d'un filtre médian

**progfou** · 31/10/2006, 10h46

Bonjour à tous !
Je connais beaucoup mieux le C que le C++, et j'aimerais implémenter un filtre médian (pour des images).
J'ai un tableau pour représenter ces images, à 1 dimension (le point en (x,y) est accédé par x+y*width), et j'aimerais appliquer un filtre median avec une taille qui peut être variable (pour le moment écrite en dur).
Je crois savoir que C++ possède une fonction sort(), qui est la moitié de l'algorithme...
Comment l'implémenter de manière efficace en évitant les débordements (en bord d'image, un filtre de taille 15x15 par exemple !)...

Merci d'avance de votre aide !

**Matthieu Brucher** · 31/10/2006, 10h49

Le problème du sort sur un voisinage de l'image, c'est qu'il va classer les pixels de l'image, pas très intéressant

Si tu as des itérateurs sur un voisinage de l'image, tu peux copier le voisinage dans un vecteur et le classer partiellement, puis prendre la valeur médiane.
Si tu n'as pas d'itérateurs sur un voisinage, il va falloir faire la copie et les tests à la main.

**progfou** · 31/10/2006, 10h53

Ouh là, va falloir m'expliquer ça

C'est quoi un itérateur ?
Comment je peux mettre mes pixels dans un vecteur

...
En fait je connais très mal le C++

**Matthieu Brucher** · 31/10/2006, 10h57

http://c.developpez.com/faq/cpp/?page=STL#STL_iterator

Pour copier les pixels dans un vecteur, ben tu les copies

**progfou** · 31/10/2006, 11h13

Moi j'ai déclaré comme ça :

Code :

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

unsigned char * buffer_Luminance;

Et puis c'est tout ^_^.
Je vais parcourir mon image de manière simplissime :

Code :

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

1
2
3
4
5
6
7
8
9
 
int x, y, index;
 
        for (y=0 ; y<height-1 ; y++) {
                for (x=0 ; x<width-1 ; x++) {
                        index = y*width+x;
                        //buffer_Luminance[index] est le pixel à la position (x,y) du buffer
                }
        }

**Matthieu Brucher** · 31/10/2006, 11h17

OK, dans ce cas, tu n'as pas d'itérateurs, mais tu peux tout de même copier les pixels intéressants dans un vecteur et faire le tri partiel dessus.

**progfou** · 31/10/2006, 11h26

Si j'ai bien saisi, je crée mon vecteur :

Code :

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

std::vector<int> v;

Et je m'en sert comme stockage ?
Donc je dois le dimensionner à la taille correspondant à mon filtre :

Code :

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

v.resize(n*m);

Avec (n,m) la taille du filtre.

**Matthieu Brucher** · 31/10/2006, 11h29

Oui et non. Comme tu ne connais pas la taille à priori de la zone que tu analyses, ne fais qu'un reserve(n*m). Ensuite, tu fais des push_back pour remplir ton vecteur.

**Charlemagne** · 31/10/2006, 11h32

Je réfléchissais brièvement à ton problème pour l'optimiser.

Quelques idées:

1) Implémenter toi même un tri par insertions, pour ne pas avoir à retrier entièrement le vecteur pour le pixel voisin.

2) Ne pas utiliser l'algorithme "sort" de la STL (très bien pour des grandes listes), mais implémenter quelques algos de tris pour des tailles fixes de ton filtres (2,3,4,5...), et surtout sans aucun saut conditionnel (qui briserait le pipeline du processeur et donc les performances).
Ne pas mettre les valeurs dans un vecteur, mais dans des variables locales pour:
- diminuer les accès mémoires
- optimiser l'utilisation des registres

3) Utiliser les instructions MMX/SSE (ou tout autre instruction SIMD de ton processeur) pour manipuler 8/16 pixels en parallèle. Pour le filtre horizontal il faudrait transposer l'image, mais ça vaudrait le coup point de vue performance.

Rien n'interdit de combiner les idées.

**progfou** · 31/10/2006, 11h38

Ouh là là... ça fait peur tout ça

.
Non, sérieusement, implémenter moi-même le tri, OK, mais j'ai très peu de temps...
Les instructions MMX/SSE, je verrais ça plus tard

.

Pour stocker mes valeurs dans mon vecteur, si j'ai un filtre 3x3, ça ne pose pas de problème, mais si j'ai du 15x15, il me faut une boucle pour gérer les index des pixels...
Je n'arrive pas à la construire

.

**progfou** · 31/10/2006, 11h41

Sauf si quelqu'un sait comment utiliser les fonctions déjà créées de ImageMagick ?

**Charlemagne** · 31/10/2006, 11h49

C'est toujours le compromis temps/performances.
Mais imagine SSE2 te permets de multiplier la vitesse par (presque) 16 pour des images de chars.

Effectivement si tu utilises une longueur de filtre variable, ça va sérieusement ralentir l'algo. Mais si tu sais que ton filtre aura une longueur de 15, c'est pas la mère à boire que de développer la boucle et d'écrire 15 lignes.
Il est également possible de mélanger des cas particuliers optimisés pour des longueurs fixes courantes, en plus d'un algo général....

Ah l'optimisation...

**progfou** · 31/10/2006, 12h13

Bon, pour stocker les nxn (je considère un filtre carré), je fais ça :

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
        std::vector<int> v;
        int n=15; // Taille initiale fixée à 15x15
        for (int y = (n-1)/2 ; y < height - (n-1)/2 ; y++) {
                for (int x = (n-1)/2 ; x < width - (n-1)/2 ; x++) {
                        index = y*width + x;
                        for (int j=0 ; j<n-1 ; j++) {
                        v.reserve(n*n);
                                for (int i=0 ; i<n-1 ; i++) {
                                        v.push_back(dst[index-(((j-(n-1)/2)*width)+i-(n-1)/2)]);
                                }
                        v.empty();
                        }
 
                }
        }

Je fais un reserve() et un empty() à chaque fois, car j'ai l'impression que sinon il va me grossir mon vecteur à chaque boucle, non ?

**progfou** · 01/11/2006, 09h30

J'ai deux soucis :

Je ne sais pas ce que je réserve exactement, et ça met un temps fou pour le remplissage
Je n'arrive pas à visualiser avec cout...

Je suis un peu un boulet quand même pour le coup

.
Si quelqu'un peut me montrer mon(mes ?) erreur(s)...

**Matthieu Brucher** · 01/11/2006, 09h44

Tu réserves n*n mais tu ne remplis que n, c'est normal ?

**progfou** · 01/11/2006, 10h01

Chose rigolote, je viens de le voir

.
Effectivement, mon clear est mal placé (mon réserve aussi d'ailleurs).

Si je ne m'abuse, le filtre médian, c'est bien :

Prendre les nxm points autour du point considéré
Trier les valeurs dans l'ordre croissant
Prendre la valeur du milieu (indice (nxm)/2)
Remplacer la valeur courante du point par cette valeur médiane

**Matthieu Brucher** · 01/11/2006, 10h17

Oui, mais plutôt que de faire un tri complet, tu peux plutôt récupérer le nième élément : http://www.sgi.com/tech/stl/nth_element.html

**progfou** · 01/11/2006, 10h20

Euh, c'est à dire ?
Je suis "obligé" de trier toutes mes valeurs, non ?
Car effectivement, quoique non optimisé, certes, il me faut 20 secondes pour un filtre 15x15 sur une image de 640x480 !

**Matthieu Brucher** · 01/11/2006, 10h42

Non, tu n'es pas obligée de toutes les triéer, regade dans le lien que je t'ai donné.

**progfou** · 01/11/2006, 10h48

Oui, mais je n'arrive pas à le mettre en oeuvre !
J'ai fait ça :

Code :

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

nth_element(v.begin(), v.size()/2, v.end());

Et BC++ me renvoit :

Could not find a match for 'nth_element<_RandomAccessIter,_Compare>(int *,unisgned int,int *)'

[Image]Implémentation d'un filtre médian

C++

Discussions similaires

Partager

Partager