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

Version imprimable

31/10/2006, 10h46
progfou

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

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 !
31/10/2006, 10h49
Matthieu Brucher

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.
31/10/2006, 10h53
progfou

Ouh là, va falloir m'expliquer ça :aie:
C'est quoi un itérateur ?
Comment je peux mettre mes pixels dans un vecteur :roll: ...
En fait je connais très mal le C++ :mrgreen:
31/10/2006, 10h57
Matthieu Brucher

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

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

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

Code:

unsigned char * buffer_Luminance;

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

Code:

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
                }
        }

31/10/2006, 11h17
Matthieu Brucher

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.
31/10/2006, 11h26
progfou

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

Code:

std::vector<int> v;

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

Code:

v.resize(n*m);

Avec (n,m) la taille du filtre.
31/10/2006, 11h29
Matthieu Brucher

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.
31/10/2006, 11h32
Charlemagne

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.
31/10/2006, 11h38
progfou

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 :( .
31/10/2006, 11h41
progfou

Sauf si quelqu'un sait comment utiliser les fonctions déjà créées de ImageMagick ?
31/10/2006, 11h49
Charlemagne

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

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

Code:

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 ?

01/11/2006, 09h30
progfou
J'ai deux soucis :
1. Je ne sais pas ce que je réserve exactement, et ça met un temps fou pour le remplissage
2. Je n'arrive pas à visualiser avec cout...
Je suis un peu un boulet quand même pour le coup :aie: .
Si quelqu'un peut me montrer mon(mes ?) erreur(s)...
01/11/2006, 09h44
Matthieu Brucher

Tu réserves n*n mais tu ne remplis que n, c'est normal ?
01/11/2006, 10h01
progfou
Chose rigolote, je viens de le voir :mouarf: .
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
01/11/2006, 10h17
Matthieu Brucher

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
01/11/2006, 10h20
progfou

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 !
01/11/2006, 10h42
Matthieu Brucher

Non, tu n'es pas obligée de toutes les triéer, regade dans le lien que je t'ai donné.
01/11/2006, 10h48
progfou

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

Code:

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

Et BC++ me renvoit :

Citation:

Could not find a match for 'nth_element<_RandomAccessIter,_Compare>(int *,unisgned int,int *)'
01/11/2006, 11h12
Matthieu Brucher

C'est 3 itérateurs en paramètre, donc le 2ème est un itérateur/pointeur vers l'élément que tu veux récupérer.
01/11/2006, 11h26
progfou

Un truc comme ça :

Code:

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

Il ne me donne plus d'erreur, mais je ne sais pas si ça fonctionne effectivement...
Je récupère, à l'issue de cet appel, ma valeur via un :

Code:

val = v[v.size()/2];
01/11/2006, 11h34
Matthieu Brucher

Si tu n'as pas confiance, fais des tests pour vérifier. D'ailleurs, même si tu as confiance, tu devrais faire des tests pour vérifier.
01/11/2006, 11h35
progfou

Ca a l'air de marcher, mais je suis surpris, ça me semble trop simple :aie: .
01/11/2006, 11h43
Matthieu Brucher

Ah :)
Non, rassure-toi, c'est normal.
01/11/2006, 12h39
Luc Hermitte
Et oui, la SL c'est simple au fond.
Mais comme l'a souligné Charlemagne, pour des petites structures, d'autres algos peuvent s'avérer plus efficace.

Au fait, empty() ne vide rien. C'est clear() qui fait ça. Mais ne t'embête pas avec ça. La taille de ton filtre est toujours la même. Ici, le remplissage par indices sera bien plus efficace.
->
Code:

1 2 3 4 std::vector<pixel> v(15); .... for (int k =0 ; k!=15 ; ++k) v[k] = ...
01/11/2006, 13h06
Matthieu Brucher

C'est là où c'est sournois. Au bord, le filtre n'a pas la même taille.
02/11/2006, 14h44
progfou

Est-ce que si j'utilise le conteneur associatif set, qui d'après ce que j'ai compris insère les éléments de manière ordonnée, je peux faire cela plus rapidement qu'avec le vecteur suivi d'un tri ?

Dans quel cas vaut-il mieux utiliser l'un que l'autre ?
02/11/2006, 14h56
Matthieu Brucher

L'accès dans un set est en log(n), l'accès adans un vecteur est en O(1)
C'est avantageux de prendre un set si les copies sont trop coûteuses lors du tri du vecteur. Dans ton cas, il faudrait faire un test et prendre le meilleur.
Dans tous les cas, toujours faire des tests pour vérifier ce qu'on avance.
02/11/2006, 16h53
Charlemagne
Je crois qu'un 'set' ne ferait pas l'affaire, mais plutôt 'multiset'.
Mais, c'est pas évident de retrouver l'élément du milieu, ni d'en retirer des éléments au fur et à mesure que le filtre avance sur l'image.
Et puis je suis pas convaincu que le l'insertion soit rapide puisque la dichotomie marche probablement avec des sauts conditionnels, qui casseraient le pipeline. (le problème existe aussi quand on choisit un vecteur à la place d'un set)

Bref, perso, je ne miserais pas la dessus pour optimiser un filtre médian, même si un algo insérant et retirant progressivement les éléments a très probablement un avantage sur la fonction 'sort'.

Si je voulais concevoir un algo rapide je miserais sur des fenêtres de tailles fixes et sur les instructions vectorielles.
Bon, maintenant si le paramétrage de la taille du filtre est également important, je m'arrangerais pour paramétrer la fonction médian soit par un template entier, soit par une fonction objet représentant le filtre.
Code:

1 2 3 template<int N> Image median(const Image &X) {...} template<class F> Image median(const Image &X, F f) {...}