tri d'un tableau dynamique

Version imprimable

Voir 40 message(s) de cette discussion en une page

Bonsoir,

En effet cétait tout bête. Merci beaucoup !

Bon, mais j'ai tjrs quelques problèmes (je m’ennuierais sinon..) :

Après l'application de mon filtre median, j'obtiens une image disons...horrible. Rien à voir avec l'image de départ.
Je pense que mon erreur viens de la récupération de mon voisinage mais j'vois pas ou...
J'ai fait ceci :

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
 
// calcul du voisinage :
 
    for( i = 1; i < hauteur - 1; i++ )
    {
        for( j = 1; j < largeur - 1; j++ )
        {
 
            long elements = (i*largeur)+ j;
            int val_mediane ;
 
            vecteur_1D[elements] = newPixels [i][j]; // on copie dans vecteur_1D les pixels
 
            // récupération du voisinage (une boucle serait plus adaptée):
 
            vecteur_1D.push_back(pixels[ i - 1 ][ j - 1 ]);
            vecteur_1D.push_back(pixels[ i - 1 ][ j ]);
            vecteur_1D.push_back(pixels[ i - 1 ][ j + 1 ]);
            vecteur_1D.push_back(pixels[ i ][ j - 1 ]);
            vecteur_1D.push_back (pixels[ i ][ j + 1 ]);
            vecteur_1D.push_back ( pixels[ i + 1 ][ j - 1 ]);
            vecteur_1D.push_back(pixels[ i + 1 ][ j ]);
            vecteur_1D.push_back (pixels[ i + 1 ][ j + 1 ]);
 
            if (vecteur_1D.size()%2 == 0)      // La suite ordonnée est de taille paire
            {
                val_mediane=( (vecteur_1D.size()/2)-1 + vecteur_1D.size()/2 )/2;
 
                newPixels[i][j]=val_mediane;
 
            }
            else                    // sinon (la suite est impaire)
            {
                val_mediane=( vecteur_1D.size() )/2 ;
                newPixels[i][j]=val_mediane;
            }
            if (  vecteur_1D[elements] > 255 ) vecteur_1D [elements] =255;
            if (  vecteur_1D[elements] <0 )  vecteur_1D[elements] =0;
 
 
 
        }
    }

Ca m'arrangerait que la solution soit du même niveau que tout à l'heure et que ce ne soit qu'une erreur bête :D

D'avance merci en tout cas !

07/01/2012, 23h09
serge_galoup

ouais mais non, j'suis un peu bête quand même...
c'est le titre de mon topic et je l'oublie : le TRI !
Mon tableau n'est pas trié dans le code que j'ai posté, donc après, le calcul de la médiane n'a pas de sens.

Bon bah du coup autre question : pourquoi la méthode sort(vector.begin(),vector.end()) ne fonctionne pas dans une boucle ?

J'ai testé de la déclarer en fonction mais rien n'y fait...
07/01/2012, 23h11
DonQuiche

Citation:

Envoyé par serge_galoup

Ca m'arrangerait que la solution soit du même niveau que tout à l'heure et que ce ne soit qu'une erreur bête :D

Perdu. :mouarf:

Les erreurs sont nombreuses, en fait le code ne rime à rien. En vrac:
* Si vecteur1D a été initialisé à une taille de 100k éléments, la première itération de ta boucle va ajouter le pixel (0,0) à l'indice 100000, puis le pixel (0,1) à l'adresse 100001, etc... Ça n'a aucun sens. A ce stade ton code devrait stocker les neuf pixels du voisinage dans un tableau de neuf éléments.
* Le calcul de ta médiane ne rime à rien... A la première itération, vecteur 1D aura donc une longueur de 100008 et d'après ton code le pixel va alors être (50004 - 1 + 50004) / 2. ????? Pour calculer ta médiane, trie ton tableau de neuf pixels et récupère le 5ème. Voir la définition d'une médiane sur Wikipedia, ce n'est pas une moyenne (cela dit tu ne calculais pas une moyenne non plus ici).
* La médiane ne doit pas être calculée sur les pixels eux-même mais sur chaque canal indépendamment (R, G, B, A). Autrement dit, il te faut en réalité 4 tableaux/vecteurs de neuf bytes, calculer 4 médianes (toujours des bytes), puis les réassembler en un pixel de 32 bits.
* Neuf éléments et non pas huit parce que le pixel lui-même est inclus.
07/01/2012, 23h18
serge_galoup

ha oui en effet...gasp ! :oops:

Comme je travaille en nuance de gris (pas précisé avant, désolé) 1 seul tableau suffit j'pense.

Bon bah j'y retourne avec tes précieuses indications.

Merci !

Bon et bien j'obtiens enfin un résultat qui me semble pas trop éloigné d'un filtrage médian !

Par contre j'aimerais bien avoir un regard critique sur ce que j'ai fais car, même si cela fonctionne, ce doit être globalement... horrible.

Voici mon code :

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
 
// déclaration d'un vecteur à une dimension de taille (largeur*hauteur)
 
    vector<long>vecteur_1D(largeur*hauteur);
 
    int val_mediane; // variable locale
 
    // Filtrage médian :
 
    for( i = 1; i < hauteur - 1; i++ )
    {
 
        for( j = 1; j < largeur - 1; j++ )
        {
            vecteur_1D.clear(); // vide le vecteur à chaque itération
 
            vecteur_1D[(i*largeur)+ j] = newPixels[i][j]; // on copie dans vecteur_1D le tableau 2D newPixels
 
            // Insertion dans vecteur_1D du voisinage
 
            vecteur_1D.push_back(pixels[ i - 1 ][ j - 1 ]);
            vecteur_1D.push_back(pixels[ i - 1 ][ j]);
            vecteur_1D.push_back(pixels[ i - 1 ][ j + 1 ]);
            vecteur_1D.push_back(pixels[ i ][ j - 1 ]);
            vecteur_1D.push_back(pixels[ i ][ j ]);
            vecteur_1D.push_back(pixels[ i ][ j + 1 ]);
            vecteur_1D.push_back(pixels[ i + 1 ][ j - 1 ] );
            vecteur_1D.push_back(pixels[ i + 1 ][ j ]);
            vecteur_1D.push_back(pixels[ i + 1 ][ j + 1 ]);
 
            //tri du vecteur
 
            sort(vecteur_1D.begin(),vecteur_1D.end());
 
            //récupération de la valeur médiane
 
            val_mediane=vecteur_1D.at(4); //taille=9 donc médiane= 5ème position
 
            newPixels[i][j]=val_mediane;  //pixel courant = médiane du voisinage
 
        }
    }

J'suis pas naïf, vu mon niveau ce doit être très moche. Si quelqu'un peut me dire où comment pourquoi (rien que ça :D), ça m’intéresse !

Et sinon, un grand merci à tous, pour vos réponses rapides, précises et efficaces !
J'ai appris tout plein de choses et c'est cool !

08/01/2012, 17h24
DonQuiche

Bonjour, deux bugs demeurent, peut-être trois...

* D'abord la ligne avec le commentaire "on copie dans vecteur_1D le tableau 2D newPixels". Que vient-elle faire là ? Quel est son but ?

* Tu stockes les nouveaux pixels dans le tableau source. Autrement dit, quand tu calculeras la médiane pour (0,1), la valeur qui sera utilisée pour le pixel (0,0) sera la médiane de ce dernier, et non le pixel d'origine.

* Optionnel : quid des points aux bords, pas de médiane pour eux ?

A part ça le code est évident à comprendre et c'est l'essentiel. Les commentaires sont par contre mal utilisés (trop nombreux dont beaucoup inutiles). Plus subjectivement je regrette tout de même l'usage d'un vecteur pour un bête tableau de neuf points qui pourrait être alloué sur la pile et, même si on préfère s'en tenir à un vecteur, l'usage de clear/push_back/at plutôt qu'une assignation directe via l'indexeur. Sur un million de pixels, ça fait toujours moins d'instructions sans rien enlever à la lisibilité. Cela dit ça ne pèse pas lourd en regard du tri. A ce propos, on pourrait faire bien plus efficace mais cela dépasse sans doute le cadre de l'exercice.
09/01/2012, 14h17
serge_galoup

Bon alors voilà, mon projet est bouclé, rendu, terminé et donc je vous remercie grandement pour toute l'aide apportée. Ce fut précieux.

Mais c'est pas pasque c'est fini que je vais en rester là non mais ! :

Citation:

Envoyé par DonQuiche

* D'abord la ligne avec le commentaire "on copie dans vecteur_1D le tableau 2D newPixels". Que vient-elle faire là ? Quel est son but ?

la réponse est bien évidement : rien ! Un oubli, un reste de mes nombreux tests :roll:

Citation:

Envoyé par DonQuiche

* Tu stockes les nouveaux pixels dans le tableau source. Autrement dit, quand tu calculeras la médiane pour (0,1), la valeur qui sera utilisée pour le pixel (0,0) sera la médiane de ce dernier, et non le pixel d'origine.

Ça j'ai pas très bien compris : mon tableau contenant les pixels non traités est le tableau pixel [i][j] et je stocke dans le nouveau tableau newPixels [i][j]. Je ne stocke donc pas dans le tableau source ?

Citation:

Envoyé par DonQuiche

* Optionnel : quid des points aux bords, pas de médiane pour eux ?

Je l'ai précisé dans mon rapport, par faute de temps...cela reste optionnel !

Citation:

Envoyé par DonQuiche

A part ça le code est évident à comprendre et c'est l'essentiel.

Cool un truc bien :)

Citation:

Envoyé par DonQuiche

Les commentaires sont par contre mal utilisés (trop nombreux dont beaucoup inutiles).

Je sais que c'est un peu lourd mais je présente cette partie à un ''oral'' donc je préfère surcharger un peu..

Citation:

Envoyé par DonQuiche

L'usage de clear/push_back/at plutôt qu'une assignation directe via l'indexeur.

Là pour le coup je comprends pas. Serais-ce l'utilisation de assign() ou pas du tout ?
09/01/2012, 16h10
DonQuiche

Citation:

la réponse est bien évidement : rien ! Un oubli, un reste de mes nombreux tests :roll:

Du coup, en l'enlevant, as-tu passé à changer la taille du vecteur sur la première ligne pour la mettre à neuf ? L'impact sur les performances peut être important.

Citation:

Envoyé par serge_galoup

Ça j'ai pas très bien compris : mon tableau contenant les pixels non traités est le tableau pixel [i][j] et je stocke dans le nouveau tableau newPixels [i][j]. Je ne stocke donc pas dans le tableau source ?

Oups, au temps pour moi. La ligne à virer utilisait "newPixels" mais les neuf lignes de collecte du voisinage utilisaient bien "pixels".

Citation:

Là pour le coup je comprends pas. Serais-ce l'utilisation de assign() ou pas du tout ?

Non, l'indexeur c'est l'opérateur "[]". :)
Il diffère de "at" en ce que ce dernier vérifier les bornes de l'indice passé pour lancer une exception si besoin est.
Quant à push_back, en plus de l'assignation, il doit lui aussi vérifier les bornes pour redimensionner si nécessaire le tableau et incrémenter un compteur interne.

Citation:

Je sais que c'est un peu lourd mais je présente cette partie à un ''oral'' donc je préfère surcharger un peu..

Quand bien même je ne pense pas qu'un commentaire "variable locale" pour la déclaration d'une variable locale était nécessaire par exemple. :mrgreen:
En tout et pour tout tu avais besoin de deux à trois commentaires. J'aurais personnellement mis:
* Avant les "for": "Parcours en ignorant les bords".
* Avant la collecte des points : "Collecte des neufs points du voisinage."
* Avant le "sort" : "Calcul de la médiane"

Enfin, j'aurais renommé "vecteur1d" en "voisinage".
09/01/2012, 17h53
serge_galoup

Oui j'ai bien changé la taille !

Ok j'ai compris pour l'utilisation de l'indexeur. En gros ici, le vector c'est un peu utiliser un canon pour écraser une mouche.

( les avantages avec vector c'est que j'ai du me plonger dans la STL, au programme du partiel dans quelque temps. Mais bon, comme avantage ça n'influe pas trop sur la simplicité ou les performances de mon code :D )

Pour les commentaires c'est vrai que c'est peut-être un peu too much :roll:
Ya un mec qu'a dit " ce qui se conçoit bien s'énonce clairement et les mots pour le dire vous viennent aisément". (Boileau précisément).
J'ai retenu la leçon :ccool:

Voir 40 message(s) de cette discussion en une page