tri d'un tableau dynamique

**serge_galoup** · 19/12/2011, 19h32

Bonjour à tous !

Deux petites questions:

-Afin de réaliser un filtrage médian sur une image (en c++), j'aimerais trier un tableau dynamique à 2 dimensions (mon tableau de pixels). J'ai bien regardé dans tous ce qui est algo de tri rapide mais je vois pas du tout comment les implanter avec des tableaux dynamique.

-Laquelles des écritures il faut privilégier pour définir un tableau dynamique à 2 dimensions ?

-vector< vector<int> > tab;

ou

-**int tab;

il y a une différence notable ?

D'avance merci pour vos lumières !

**3DArchi** · 19/12/2011, 20h27

Salut,
L'allocation dynamique à la main int** va rapidement devenir inextricable pour assurer une garantie face aux exceptions. Je te le déconseille fortement.

Si le nombre de colonnes par lignes est toujours le même, je me demande si un vecteur à plat (std::vector<int>(nbrLigne*nbrColonne)) ne serait pas préférable à un std::vector<std::vector>> (au - meilleur localité dans le premier cas).

Je ne suis pas expert en traitement d'image, loin de là, mais à quoi sert ton tri ? Le filtrage médian ne consiste-t-il pas à prendre la moyenne des pixels autour de chaque pixel ? Quel rapport avec le tri ?

Autre chose : n'existe-t-il pas de bibliothèque éprouvée faisant ce que tu souhaites ?

**cob59** · 19/12/2011, 22h46

Sous OpenCV on peut le faire assez simplement :
(je n'ai pas vérifié le code, c'est sûrement truffé d'erreurs)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
#include <opencv2/opencv.hpp>
 
int main() {
cv::Mat image_in = imread("image.jpg");
cv::Mat image_out(image_in);
 
cv::medianBlur(image_in, image_out, 3);
 
cv::imshow("Resultat", image_out);
 
return 0;
}

Construire une matrice sous OpenCV ?
Filtrer cette matrice avec medianBlur ?

**serge_galoup** · 21/12/2011, 16h44

Bonsoir,

Déjà merci de vos réponses et ensuite précisions :

- Le truc s'inscrit dans le cadre d'un projet en cours d'informatique , exit l'utilisation des bibliothèques qui feraient (presque) tout le boulot à notre place

Ce s'rait pas drôle sinon !

-@ 3DArchi : ce que tu me décrits est le filtrage Moyen. Le filtrage Median, c'est attribuer au pixel traité la valeur médiane de son voisnage. D'où le tri. Bon c'est vrai, Median, Moyen... c'est jouer sur les mots mais c'est le jeu

Alors pour le coup de la déclaration des tableaux dynamiques, j'ai commencé- et même bien avancé- avec ce que tu m'as déconseillé, les int**...
C'est une erreur ou une faute ? J'veux dire, j'dois m'amuser à tout redéfinir ou le prof ne verra pas la différence ? Question d'élégance ? De quelles exception parles tu ?
Mes tableaux dynamiques correspondent au matrice de l'image et sont globalement assez gentils ( de simple int en ligne et colonne quoi !)

Enfin bref ça me résout pas la question du tri tout ça

**dragonjoker59** · 21/12/2011, 17h19

Qu'est-ce que tu entends par "valeur médiane de son voisinage" ?
De plus, c'est un code C ou C++ que tu dois produire ? Car si c'est un code C++, je ne vois pas en quoi le fait d'utiliser la STL (pour vector) peut poser un problème, même à ton prof.

**jblecanard** · 21/12/2011, 17h57

Envoyé par dragonjoker59

je ne vois pas en quoi le fait d'utiliser la STL (pour vector) peut poser un problème, même à ton prof.

Il disait ça par rapport à OpenCV.

Par contre, je vois toujours pas pourquoi tu veux trier. Trier comment, dans quel sens ? Quelle est la relation d'ordre entre les pixels ?

A mon avis, c'est un filtre, pas un tri. Le mieux je pense est d'utiliser la solution proposée par 3DArchi. T' encapsules ça dans une classe qui va te représenter une matrice de pixels et le tour est joué.

Ensuite tu auras ta matrice de départ, et ta matrice d'arrivée. Tu ne peux pas écrire directement dans la matrice de départ car tu as besoin de la valeur initiale du pixel sur lequel tu écris pour que l'algo fonctionne.

**serge_galoup** · 21/12/2011, 18h28

Oui en effet, c'est pour OpenCV que je disais cela.

Et absolument d'accord pour le reste aussi : j'ai ma matrice de pixel d'entrée ( contenue dans le tableaux dynamique 2 dimensions) que je convolue ( un filtre quoi) par différents filtres.
J'ai déjà réalisé differentes convolutions (aller, on va dire "filtre" c'est moins pédant

) genre Laplacien, Gaussien, filtre de Sobel i tutti quanti.

Pour le filtre médian, le pixel courant vaut la valeur médiane de son voisinage . C'est donc bien un filtre que je réalise. Mais pour récupérer la valeur médiane, j'dois bien trier dans l'ordre croissant les valeurs de mon voisinage pour récupérer ensuite la valeur médiane ( qui d'après mes souvenirs de stats de 2nd "coupe" l'effectifs trié en ordre croissant en 2) ?

D'ou l'idée du tri de mon tableaux dynamique.

Après j'suis p'tet complètement à côté de la plaque !

J'peux p'tet poster mon code quelque part histoire d'y voir plus clair mais je ne sais trop où .. ici même ?

**jblecanard** · 21/12/2011, 19h32

Envoyé par serge_galoup

Pour le filtre médian, le pixel courant vaut la valeur médiane de son voisinage . C'est donc bien un filtre que je réalise. Mais pour récupérer la valeur médiane, j'dois bien trier dans l'ordre croissant les valeurs de mon voisinage pour récupérer ensuite la valeur médiane ( qui d'après mes souvenirs de stats de 2nd "coupe" l'effectifs trié en ordre croissant en 2) ?

D'ou l'idée du tri de mon tableaux dynamique.

J'ai compris ! En fait tu veux juste obtenir une valeur, la position du pixel dans le voisinage n'a pas d'importance (ou alors il a un poids mais ça change pas grand chose en fait).

Dans ce cas, la solution à ton problème est simple : tu n'as pas besoin d'un tableau à deux dimensions mais à une seul dimension, puisque la valeur de chaque pixel n'a aucune corrélation avec sa position dans la matrice.

J'ai pas le temps de détailler le code, mais il te faut un std::vector< Pixel > (ou simplement std::vector< (int | float) > si tu travailles en niveaux de gris). Ensuite tu peux utiliser std::sort et tout le tsoin tsoin. A chaque pixel, tu stockes le voisinage dans ton tableau d'une dimension et tu le tries. Puis tu récupères ta valeur.

C'est sûrement pas optimisé mais là n'est pas le problème : ça fonctionnera.

**3DArchi** · 22/12/2011, 07h15

La valeur médiane, si mes souvenirs sont bons, est celle où 50% de l'échantillon est en dessous et 50% est au dessus. D'où le tri puisqu'il suffit ensuite de prendre celle du milieu.

Pour le stockage, je te (re)déconseille les int** et repasse sur une seule dimension, idéalement vector<int>. Par exception, j'entendais la possibilité de ton code de lever une exception (allocateur par expl) et sa solidité face à ce problème : tout sera-t-il bien libéré ? Mais aussi je pense que l'allocation sur une ligne te garantie une certaine localité des données là où plusieurs allocations peuvent très bien conduire à une fragmentation de ta matrice sur la mémoire. Ca aura probablement une conséquence sur les perf.

pour ton problème de tri, je pense que tu dois copier le voisinage du pixel dans un tableau temporaire de dimension réduite puis effectuer le tri dessus.

**DonQuiche** · 22/12/2011, 08h53

Je rejoins 3Darchi sur l'utilisation d'un tableau unidimensionnel.

Maintenant, plutôt que copier et trier (tri = o(25 * 7) = o(175)), pourquoi ne pas profiter du fait que les valeurs sont comprises entre 0 et 255 ? On crée un tableau de 256 compteurs, on les remplit à partir des 25 valeurs, puis on parcourt le tableau jusqu'à avoir plus de 12 occurrences. En moyenne ce sera du o(128) et il y aura moins de branchements conditionnels et pas de récursion. Surtout, c'est plus élégant.

**ac_wingless** · 22/12/2011, 10h36

A noter que ce problème est un vrai cas d'école d'utilisation des shaders de GPU. Puisqu'il s'agit d'un environnement scolaire, j'espère que votre enseignant le mentionne.

**serge_galoup** · 23/12/2011, 14h56

Merci beaucoup pour toutes ces réponses et conseils avisés !!

Pour le coup de "l'utilisation des shaders de GPU" j'ai envi de dire "What is the fuque ?" mais j'le dirais pas, c'est grossier

Je n'ai pas souvenir de cela dans les cours dispensés mais je suis plutôt du genre au-fond-près-du-radiateur en cours d'info.. et voilà ou ça me mène ! 'Fin bref, c'est pas le sujet.

Vacances de Noël obligent, je risque d'être absent quelque temps mais promis, je tente ça dès que possible ( suppression de l'écriture int** et passage en uninidimensionel pour le filtrage median ) et je vous tient au jus !

Encore merci et comme c'est l'époque, joyeuses Pâques à tous !

**3DArchi** · 26/12/2011, 12h30

Envoyé par DonQuiche

Je rejoins 3Darchi sur l'utilisation d'un tableau unidimensionnel.

Maintenant, plutôt que copier et trier (tri = o(25 * 7) = o(175)), pourquoi ne pas profiter du fait que les valeurs sont comprises entre 0 et 255 ? On crée un tableau de 256 compteurs, on les remplit à partir des 25 valeurs, puis on parcourt le tableau jusqu'à avoir plus de 12 occurrences. En moyenne ce sera du o(128) et il y aura moins de branchements conditionnels et pas de récursion. Surtout, c'est plus élégant.

Salut
L'idée est effectivement élégante pour un petit échantillon.

Mais pourquoi supposer que les valeurs sont sur un octet ? A priori, il encode ses pixels sur des ints ?

**DonQuiche** · 26/12/2011, 13h42

Envoyé par 3DArchi

Salut
L'idée est effectivement élégante pour un petit échantillon.

Mais pourquoi supposer que les valeurs sont sur un octet ? A priori, il encode ses pixels sur des ints ?

Parce que chaque canal réclame un traitement séparé je présume : R est la valeur médiane des R des 25 pixels voisins, etc.

**JolyLoic** · 29/12/2011, 10h43

Je ne sais pas trop, entre le tri de 8 valeurs et la lecture d'en moyenne 128 valeurs dans un tableau ce qui sera en pratique le plus lent.

Par contre, le voisinage étant de taille fixe (même pour une image étant un tableau dynamique), pour le mettre dans un mini conteneur adapté au tri, un [boost/std]::array<int, 8> est probablement plus intéressant qu'un vector<int>.

**DonQuiche** · 29/12/2011, 10h49

Envoyé par JolyLoic

Je ne sais pas trop, entre le tri de 8 valeurs et la lecture d'en moyenne 128 valeurs dans un tableau ce qui sera en pratique le plus lent.

Tu pars du principe qu'on ne considère que les 8 voisins (rayon égal à 1) mais le filtre peut très bien être de rayon variable.

**JolyLoic** · 29/12/2011, 10h54

En effet, si le voisinage est variable, ce que j'ai dit sur array ne s'applique plus, et plus il est grand, plus la méthode à base de stockage dans un tableau de valeurs a des chances d'être plus efficace.

**serge_galoup** · 04/01/2012, 14h41

Bonjour à tous !

Je vois que j'ai été gâté pour les fêtes !

C'est en effet la solution de passer par un tableau une dimension qui fonctionne !

Pour le coup de **int ou vector <> c'est également vector qui s'avère le mieux (plus souple à utiliser , et visiblement moins de problèmes, même si ça j'ai pas trop compris

); ) La STL a du bon !

Du coup j'vous salue bien bas et vous remercie grandement pour l'aide !

**serge_galoup** · 07/01/2012, 15h19

Et bien en fait je reviens vers vous car je croyais avoir résolu mon problême mais en regardant bien...pas du tout.

C'est bien le fait de passer par un tableau dimension qui marche mais là, c'est le drame !

( attention, question d'une simplicité confondante, mais pas pour moi !)

J'ai un vecteur de dimension 2 et je veux le transformer en un vecteur 1 dimension. Ben comment qu'on fait dites ?

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
16
17
18
19
20
 
// déclaration d'un vector 2 dimensions :
 
 vector< vector<int> >vecteur_2D (largeur, std :: vector <int> (hauteur));
 
 
// on alloue vecteur_2D avec les valeurs de newPixels:
 
    for( i = 0; i < vecteur_2D.size(); i++ )
    {
        for( j = 0; j < vecteur_2D[i].size(); j++ )
        {
 
/* alors là c'est moche, j'ai finalement gardé la notation int** ( pour mon niveau ça passe et j'ai pas envie/pas le temps de tout transformé..:s)*/
 
            vecteur_2D [i][j]=  newPixels [i][j]; 
 
 
        }
    }