Hello !  
 
Je me demandais si il existait un algo pour détérminer la médiane d'un ensemble de valeurs sans les trier...
 
Il doit bien y avoir une technique pour determiner le n-ieme element sans tout trier, ou du moins pas dans tous les cas...
Là je vois pas...
 
Mes tableaux sont de 30 à 60 valeurs toutes comprises entre 0 et 255...
 
??
merci !
joan.

Si tu trouves, préviens, ça va intéresser du monde...:lol:

tiens, c'est un truc pour DocMaboul. en temps constant o(n) ou je sais plus trop quoi, n'est-ce pas

Cela va sans dire!

Bon pour revenir à ton pb (on le connait pas...yen a un? ), un lien vers des méthodes de calcul de médianes :
http://ndevilla.free.fr/median/

 
ça me dit quelque chose ce lien

Comme quoi j'écoute ce qu'on me dit!

en utilisant un pivot comme pour le quick sort.
je dois faire ca un exo c++

je posterai la reponse ici une fois trouve.
 

Ah, donc ça veut dire que c'est pas complètement utopique...
Bon, ben y'a plus qu'a chercher...

Mais c'est quoi le but, au final? Pourquoi tu veux pas trier?

je suppose que si tu utilises des partitions, tu dois plus être loin du tri par partition (le qsort quoi ) quand même

 
De toute manière pour trouver une médiane ya pas 50 manières hein...

 
oulà mais il est super ce lien !
merci bicoup !

dis merci à moktar, c'est lui qui me l'a filé ya quelques jours...:lol:

 
je veux pas trier parceque j'ai des tableaux de 50 valeurs parfois plus...
et que je dois repeter l'opération un grand nombre de fois.
 
En fait je calcule le pixel médian de chaque pixel d'une vidéo.
donc pour une vidéo de 3 sec en 320x200 : ça fait (320x200) tris de tableaux de (3x25)...ça prend du temps...

Je suis en train d'essayer de le faire sur de la video en 50 images  768*288 par seconde...pas gagné!
Bon ok je le fais que sur la lumi, mais j'en suis à 31ms par image, là...
[edit]
Avec un tri (lien filé plus haut), sur une image RGB 512x512 et median sur R, G et B, 47ms.
[edit2]
...et 16ms sur une image RGB 320x200 et median sur R, G et B.
 
Si tu veux un bout de code pas de pb.

Ben ouais je veux bien, mais t'es un rapide...je suis encore en train de lire le papier sur les différentes methodes...
 
quel tri t'as utilisé ?

et juste comme ça, sur les images que tu analyses, ta médiane est éloigné de ta moyenne ?

J'ai utilisé le opt_med9 trouvé ici:
http://ndevilla.free.fr/median/median/src/optmed.c
Légèrement adapté à mon cas.

gnere le mec est entrain de nous faire un boulot de template C++ ... t'as vérififé que tout était inliné comme il faut ? d'ailleurs est-ce que c'est bénéfique par rapport à une boucle appelant PIX_SORT comme il faut ? est-ce que t'as bien recherché du côté de ton compilateur : réglages spécifiques, etc ?

Taz> tu parles à qui là? à moi?

bah un peu ... quand je vois ce joli déroulage de boucle à la main, je me demande : - s'il est optimale (faut pas trop faire péter de lignes de cache quand même, là ça me parait long à souhait) - si tout a été fait côté compilateur pour améliorer la situation (en tout cas gcc avec O3 / march / ftracer / fssa voire d'autres paramètres pour influer sur le mode de calcul me sort un code bien meilleur

 
Ah, ouais, alors je me rend compte qu'on parle pas tout a fait de la meme chose...
 
Je ne fait pas le calcul de la médiane pour filtrer une image et ecarter les pixels aberrants.
 
Je fais le calcul de la médiane de la valeur d'un pixel d'un emplacement donné dans l'image, au cours du temps.
 
pour le pix 0,0, je prend la médiane de tous les pix 0,0 des différentes images.
 
donc l'opti 9  n'est pas adapté...Il me faudrait un opti 75 ou opti 50 en fonction du nombre total d'images, ce que je ne connais pas à l'avance.
 

ouaip.
 
 
 
 
 
 
 
 
 

Mon machin actuellement je le compile sous dev-cpp avec -O2 -march=athlon-xp si c'est ça qui t'intéresse...
Je lui propose ça parce-qu'on me l'a filé ya quelque jours et que j'ai constaté que ça marchait plutôt bien, après non j'ai pas cherché bcp plus loin, et je le ferai p-e quand j'en aurai le temps...

ahhhhhhhh...ben regarde dans le reste du code filé, yen a pas mal, ton cas doit bien se retrouver...

 
+1

t'as combien d'image à analyser au pire des cas ? si c'est pas beaucoup, et sachant déjà que qsort prend une claque par std::sort du C++ pour cause d'appel de fonction, tu aurais peut être interet a essayer un petit tri léger fait maison. meme s'il a une complexite supérieure, il risque d'être plus rapide

 
Facile étant donné que ton intervalle de valeurs est borné. Il suffit de reprendre l'idée du tri par dénombrement qui est O(n).

 
En analyse d'image, etant donnee l'intervalle des valeurs [0, 255] petit, on resout ce probleme avec un tri par comptage (complexite en O(n))
Jvois pas pkoi ca vous est pas venu a l'idee ca  
 
EDIT : cela revient a precalcule l'histogramme de repartition des niveaux de gris

 
pas obligé...
certains systèmes bossent sur du [0,65535], et sur plusieurs couches (longueurs d'onde) donc forcément tu multiplies ta complexité

 
La complexite reste toujours en O(n) : c'est de simple parcours de tableau...seulement plus ton intervalle est grand, plus la memoire en prends un coup !

ce que je voulais dire c'est qu'on se retrouvait avec m itérations d'un algo de complexité O(n)
de toutes manières, sans trier (pour répondre à la première question) ça ne semble pas trop possible

 
m est fixe (c'est une constante, donc independant de la taille du tableau). Je crois qu'il faut faire 3 ou 4 parcours c tout.
Sinon, pour moi si, ca me semble tout a fait possible !   (un tri par comptage !)
 
EDIT : le tri par comptage ne tri pas ton tableau (enfin tu peux mais pas oblige). C'est une simple table de correspondance : un peu comme les tables de hachage

Merci de me donner des leçons d'analyse d'image, j'en ai bien besoin...:jap:
Aux dernières nouvelles, dans "tri par comptage", il y a tri...
 

Tu fais du comptage sur des images de taille variable en temps constant toi? Tu me montreras?
 
[edit]
J'avais lu n au lieu de m...
Reste que c'est n'importe-quoi. Si tu as 3 canaux tu vas pas faire indépendemment la médiane de chaque canal hein...

 
[citation=741177,0,35]Mes tableaux sont de 30 à 60 valeurs toutes comprises entre 0 et 255...[/citation]
 
C'est ce qui est en gras qui est important, le nombre de valeur on s'en moque ! Tu crees juste un tableau de correspondance de taille 255. c tout  

256.
Et ta technique reste un tri, qui ne modifie pas le tableau d'origine certes, mais un tri.
D'ailleurs si tu lis la suite, tu verras qu'il n'y a pas de tableau d'origine, les données sont réparties dans n images.
 
[edit]
Tes tu peux te les mettre où je pense, au fait!
Surtout quand tu quotes mes messages sans tenir compte des edit...

 
ben avec ces donnees, il fait sont tableau d'origine non ?    
Ce tableau t bien oblige de le creer (il regroupe les valeurs sur lesquelles s'appuyer)
Sinon, non   tu ne tries pas ! Avec une table de hash, tu fais de la correspondance, tu ne tris pas !
Le tri comptage c vraiment un truc bateau ...

 
Pas forcément, il peut accéder directement au pixel i de chaque image.
 
 

Mais ça reste un tri, bougre d'imbécile! Un tri c'est quelquechose qui te permet d'ordonner tes données, rien de plus! Pourquoi ça s'appelle tri comptage, d'après toi, pour faire joli?
Et je sais très bien ce qu'est un tableau de correspondance ou une table de hashage, merci...

 
admettons un tableau de pixel (taille 5) contenant le niveau de gris chacun :
initTab = {100, 38, 45, 78, 38}
avec un tableau de correspondance (de taille 256) tu obtiens :
tmpTab = {37*0, 2, 6*0, 1, 36*0, 1, 21*0, 1}
ensuite tu connais le nombre de valeurs (5)
ensuite tu parcours ton tmpTab : en cumulant les valeurs des cases a chaque fois, des que t'arrives a une valeur cumulee de 5/2, tu a trouve le point median (ton tmpTab, pointe sur la case de initTab correspondant a la valeur mediane)
 
non ?