Discussion :

[progfou]

Bonjour tout le monde,
Dans un algorithme que j'ai, il me faut, pour chaque bloc de 3*3 pixels, déterminer le minimum et le maximum parmi 6 valeurs. Le fait est que je sais le faire, mais je cherche à le faire de manière optimale...
Lorsque l'on souhaite avoir le minimum entre 2 valeurs, on fait, en C, une macro.
Je travaille, en l'occurence, en C++, mais j'aimerais savoir s'il existe un algo optimal pour déterminer le minimum (et le maximum) dans un ensemble de n valeurs ?

Merci d'avance de vos réponses !

[roulious]

Bonjour tout le monde,
Dans un algorithme que j'ai, il me faut, pour chaque bloc de 3*3 pixels, déterminer le minimum et le maximum parmi 6 valeurs. Le fait est que je sais le faire, mais je cherche à le faire de manière optimale...
Lorsque l'on souhaite avoir le minimum entre 2 valeurs, on fait, en C, une macro.

Ou une fonction, c'est tellement plus propre et pas forcément plus lent.

Je travaille, en l'occurence, en C++, mais j'aimerais savoir s'il existe un algo optimal pour déterminer le minimum (et le maximum) dans un ensemble de n valeurs ?

Tu n'as pas vraiment le choix dans les algorithmes : il te faut appliquer n fois ton critère de comparaison pour une séquence de n éléments. Puisque tu travailles en C++, regarde donc du côté de min_element (http://dinkumware.com/manuals/?manua...ml#min_element)
Ce n'est pas forcément le plus rapide, mais ça t'évite de ré-inventer la roue.

[PRomu@ld]

Ou une fonction, c'est tellement plus propre et pas forcément plus lent.

Pour un Min ou un Max, une macro suffit, ça n'est pas forcement plus "sale ..."

mais j'aimerais savoir s'il existe un algo optimal pour déterminer le minimum (et le maximum) dans un ensemble de n valeurs ?

Soit tu prends la solution toute faite, soit tu le codes toi même. En l'occurence, il faut tester tous les éléments donc tu auras entre 8 et 16 tests :

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
 
soit M ta matrice 3x3 indéxée à partir de 0.
 
Min <- M[0][0]
Max <- M[0][0]
 
pour i allant de 1 à 8 faire
     val <- M[ i mod 3 ][ i / 3 ]
     si ( val < Min ) alors
          Min <- val 
     sinon 
          si ( val > Max ) alors
               Max <- val 
          fin si
     fin si
fin pour

mod est le reste de la division euclidienne.
/ est la division euclidienne.

Voilà, je ne crois pas que l'on puisse faire mieux ...

[roulious]

Pour un Min ou un Max, une macro suffit, ça n'est pas forcement plus "sale ..."

Question de goût. Pour m'être arraché les cheveux sur une erreur de compilation due à une macro pendant plusieurs heures, je préfère les éviter. Si on ne peut vraiment pas utiliser std::min et std::max, je préfère encore faire un

Code :

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

1
2
 
(a<b)?a:b

que mettre une macro.

Code :

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

1
2
3
4
5
6
7
8
9
10
 
soit M ta matrice 3x3 indéxée à partir de 0.
 
Min <- M[0][0]
Max <- M[0][0]
 
pour i allant de 1 à 8 faire
     val <- M[ i mod 3 ][ i / 3 ]
     <des choses coupées ...>
fin pour

En traitement d'images, on représente très souvent les images (2d ou 3d) comme un tableau à une dimension, ce qui permet de s'affranchir des multiples modulo et divisions entières quand on peut et de n'y avoir recours que lorsqu'on n'a pas le choix (en général des opérations portant sur un voisinage donné).

Dans le cas de la recherche d'extrema, ces coordonnées ne sont pas nécessaires pendant le traitement : en représentant ton image 3x3 comme un tableau de taille 9, tu auras uniquement deux conversions index->coordonnées, une pour le min, une pour le max.

[PRomu@ld]

Question de goût. Pour m'être arraché les cheveux sur une erreur de compilation due à une macro pendant plusieurs heures, je préfère les éviter.

Oui, je comprend ta position, mais pour un min ou un max, ça n'est pas forcément plus dur tout de même !

En traitement d'images, on représente très souvent les images (2d ou 3d) comme un tableau à une dimension, ce qui permet de s'affranchir des multiples modulo et divisions entières

Oui, je sais mais comme progfou faisait état de blocs de 3*3 pixels, je suis parti du principe d'une matrice, mais avec un tableau 1D ça ne pose pas de problème.

Dans le cas de la recherche d'extrema, ces coordonnées ne sont pas nécessaires pendant le traitement : en représentant ton image 3x3 comme un tableau de taille 9, tu auras uniquement deux conversions index->coordonnées, une pour le min, une pour le max.

Oui, nous sommes d'accord, le tout est de savoir quel est la représentation d'origine, si elle se fait sous forme de tableau 1D ou si elle est sous forme de matrice.

D'ailleurs, d'une manière interne, un tableau 2D est la plupars du temps un tableau 1D.

[FrancisSourd]

j'aimerais savoir s'il existe un algo optimal pour déterminer le minimum (et le maximum) dans un ensemble de n valeurs ?

Trouver le minimum demande au moins n-1 comparaisons. Trouver le maximum demande au moins n-1 comparaisons. Mais on peut trouver le maximum ET le minimum simultanément avec 3n/2 comparaisons (au lieu des 2n-2 qu'on pourrait croire).

Pour cela, on parcourt le tableau en maintenant le minimum et le maximum trouvé mais, au lieu de regarder les éléments 1 par 1 on regarde les éléments par pair.
On a déjà parcouru le 2i premiers éléments et on a pour l'instant trouvé le min et le max sur ces 2i éléments. On compare alors les éléments 2i+1 et 2i+2. Si le premier et plus petit que le second, il est candidat pour être min et le second est candidat pour être max (et inversement). On traite donc ces 2 éléments avec seulement 3 comparaisons au lieu de 4 si on avait considéré ces 2 éléments comme éligibles pour être min et max. Il me semble qu'on ne peut pas fait mieux en nombre de comparaisons.

Pour plus d'info, c'est dans "Introduction à l'algorithmique" de Cormen et al.

[Nemerle]

exact! on peut songer a passer des paires aux triplets, mais on perd: 5*n/3, moins bon que 3*n/2

[progfou]

Merci à tous pour vos réponses !
Je vais tâcher de me procurer ce livre .