IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

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


Sujet :

C++

  1. #1
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut [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 !

  2. #2
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    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.

  3. #3
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut
    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++

  4. #4
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    http://c.developpez.com/faq/cpp/?page=STL#STL_iterator

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

  5. #5
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut
    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
                    }
            }

  6. #6
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    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.

  7. #7
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut
    Si j'ai bien saisi, je crée mon vecteur :
    Et je m'en sert comme stockage ?
    Donc je dois le dimensionner à la taille correspondant à mon filtre :
    Avec (n,m) la taille du filtre.

  8. #8
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    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.

  9. #9
    Inactif  
    Profil pro
    Inscrit en
    Mars 2004
    Messages
    743
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2004
    Messages : 743
    Par défaut
    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.

  10. #10
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut
    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 .

  11. #11
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut
    Sauf si quelqu'un sait comment utiliser les fonctions déjà créées de ImageMagick ?

  12. #12
    Inactif  
    Profil pro
    Inscrit en
    Mars 2004
    Messages
    743
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2004
    Messages : 743
    Par défaut
    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...

  13. #13
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut
    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 ?

  14. #14
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut
    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 .
    Si quelqu'un peut me montrer mon(mes ?) erreur(s)...

  15. #15
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    Tu réserves n*n mais tu ne remplis que n, c'est normal ?

  16. #16
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut
    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

  17. #17
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    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

  18. #18
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut
    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 !

  19. #19
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 43
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Par défaut
    Non, tu n'es pas obligée de toutes les triéer, regade dans le lien que je t'ai donné.

  20. #20
    Membre éprouvé

    Inscrit en
    Juin 2004
    Messages
    1 397
    Détails du profil
    Informations forums :
    Inscription : Juin 2004
    Messages : 1 397
    Par défaut
    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 *)'

Discussions similaires

  1. filtre médian avec image couleur
    Par Marie_7 dans le forum Images
    Réponses: 3
    Dernier message: 28/05/2012, 22h55
  2. essai de code de filtre médian
    Par Jérôme5 dans le forum Traitement d'images
    Réponses: 9
    Dernier message: 20/04/2009, 17h26
  3. [Débutant] Implémenter un filtre médian
    Par bahja29 dans le forum MATLAB
    Réponses: 1
    Dernier message: 17/03/2009, 04h29
  4. filtre médian appliquer à une image
    Par tapouni dans le forum Images
    Réponses: 2
    Dernier message: 23/05/2008, 21h35
  5. Implémentation récursive du filtre gaussien
    Par Invité dans le forum Traitement d'images
    Réponses: 1
    Dernier message: 24/04/2008, 16h35

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo