nuée dynamique

Bonjour à tous ,

je voudrais appliquer l'algorithme des nuées dynamique sur l'histogramme de niveaus de gris pour trouver trois seuils.

je n'ai  pas compris comment l'appliquer  sur un histograme d'une seule dimension.

merci pour votre aide

c'est exactement le meme principe que sur un univers à n dimensions :

- première étape : placer les barycentres ( les niveaux de gris sont quantifiables ? si c pas le cas t'auras du mal à appliquer l'algo des nuées), tu les repartie de manière qu'ils couvrent uniformement ton univers.(blanc (0 /n)- gris (n/2 / n) - noir ( n /n) )
- deuxième étape : tu associe à chaque pt (dans ton cas c des barres d'histogramme) le barycentre qui lui est le plus proche.
- troisième étape : tu recalcule chacun des barycentre en fonction des points qui leur sont associés.
- tu reitère autant de fois que tu souhaite les étapes 2 et 3 (normalement ca converge, les barycentre n'évolue plus apres un certain nombre d'étapes)

si t as placé trois barycentres , à la fin tu trouve tes trois seuils.

voilà si j'ai pas été clair n'hésite pas.

Bonjour VULpetrus ,
 
merci beaucoup de ton aide,

non j'ai pas quatifié mes niveaux de gris , pourquoi les quatifier? 

je t'explique si j'ai bien compris :
j'ai un histograme dans mon cas je voudrais troi seuils c'est dire le coupe en 4 (4classe)et aprés je choisi un barycentre dans chaque classe ( je peux choisir des pics de l'histogramme),
je n'ai pas compris la troisième étapes 
est ce que je choisi chaque point  dans l'histogrmme et je calcule ça distance  avec les autre barycentre pour les affecter a la classe.

S12

ben la quantification te permet le calcul de barycentres.
----------------------

non trois seuils => trois classes
pour chaque classe tu lui associe un pic d'histogramme.
une classe est déterminée par son barycentre.

dans notre cas,pour savoir à quelle classe appartient un point de l'histo, tu determine la distance de ce point par rapport à chacun des barycentres, le point appartiendra alors à la classe dont le barycentre est le plus proche.

pour chaque point de l'histogramme tu determine la classe (barycentre) qui lui est la plus proche.

une fois que tu as fait cela, tu recalcule la valeur du barycentre de chaque classe : pour cela tu determine le barycentre propre à chaque classe : calcul du barycentre de tous les points appartenant à  la classe.

tu reassocies à chaque classe son nouveau barycentre...

tu recherche alors à nouveau pour chaque point de l'histo, le barycentre qui lui est le plus proche et tu lui associe ce barycentre.

tu refais les etapes autant de fois que possible.

la troisème étape : elle consiste à calculer le barycentre réel de la classe, il correspond au point "moyen" qui represente le mieux les points de cette classe. ( le barycentre entre deux points correspond au centre de ces deux points, celui de n points quantifiables p1, p2, ..., pn de valeurs respectives v1,...,vn est : barycentre = (p1.v1+p2.v2+...+pn.vn)/n

voilà en espérant que j'ai été plus clair ^^
a+

pardon barycentre = (v1+v2+...+vn)/n

bonjour
voici le programme du kmeans que j'ai fait avec matlab est ce que c'est juste. aprés je vais le convertir en C

A = imread('noirsat.bmp');

B = double(A(:,:,1));

his = zeros(256,1);

d3 = zeros(256,1);

[nl nc] = size(B) ;
% calcule l'histogramme

for i=1:nl

for j=1:nc

val= B(i,j)+1;

his(val) = his(val) + 1;

end

end

% une gaussienne pour lisser l'histogramme

Bp = var(var(his))

[f1, nn] = FIRGAUSS(2,'minorder',1);

%histt = his(1:50);

res2=conv(his,f1);

p=1;

v=1;

res2=max(his)*(res2/max(res2));

[n2,m2] = size(res2);

dn2 = round((n2-length(his))/2);

res22 = res2(dn2:n2-dn2-1);

y2=diff(res22);

figure(3)

plot(y2)

%trouver les pic de l'histogramme

for i=1:length(y2)-1

if ( y2(i) >=0 & y2(i+1)<=0)

pic(p)= i+1;

p=p+1;

end

if (y2(i) < 0 & y2(i+1) > 0)

val(v)= i+1;

v=v+1;

end

end

% je prend les trois premier pic comme des barycentre

bary1 = pic(1);

bary2 = pic(2);

bary3 = pic(3);

% Kmeans
for kk= 1 : 20

j=1

k=1

f= 1

for i = 1 : 256 ,

%calcule la distance entre chaque point et les barycentre

dist= sqrt( ((bary1-i)^2) + ((bary1-i)^2) );

dist1= sqrt( ((bary2-i)^2) + ((bary2-i)^2) );

dist2= sqrt( ((bary3-i)^2) + ((bary3-i)^2) );

if(dist <dist1 & dist <dist2)

% d1 classe 1
d1(j)=i;

j=j+1;

end

if(dist1 <dist & dist1 <dist2)

% d2 classe 2
d2(k)=i;

k=k+1;

end

if(dist2 <dist & dist2 <dist1)

% d3 classe 3
d3(f)=i;

f=f+1;

end

end

% recalcule le barycentre

for j=1 :length(d1)

bary1 = bary1 + d1(j)

end

bary1 = bary1/length(d1)

for j=1 :length(d2)

bary2 = bary2 + d2(j)

end

bary2 = bary2/length(d2)

for j=1 :length(d3)

bary3 = bary3 + d3(j)

end

bary3 = bary3/length(d3)

end

merci pour votre aide

je ne suis pas vraiment rentré dans le détail mais bon pour tout ce qui est nuée dynamique ca à l'air pas mal (initialisation/affectation des points/calcul des bary/réaffectation.)...par contre tu dois faire une moyenne pondérée pour calculer le barycentre, dans le cas contaire les seuils à la fin du traitement ne reflèteront pas ton histogramme : en fait tu risque de récuperer trois seuils respectivement à 1/3, 2/3 et 3/3 de ton espace.

donc supposons que ton histogramme se represente par la fonction y=f(x),

on aura alors :

% recalcule le barycentre

total1=0;
for j=1 :length(d1)
bary1 = bary1 + d1(j)*f( d1(j) )
total1 = total1 + d1(j)*f( d1(j) )
end

bary1 = bary1/total1

tu fais la même chose pour bary2 et bary3.

j'ai un avis assez partagé sur l'utilisation de ta fonction de lissage qui semble être une bonne idée.

bonne chance.

 merci encore
tu m'a dis de remplacer par ça

total1=0;
for j=1 :length(d1)
bary1 = bary1 + d1(j)*f( d1(j) )
total1 = total1 + d1(j)*f( d1(j) )
end

bary1 = bary1/total1

mais ici je vois que tolal1 est le même que bary1

mdr ^^

effectivement, excuses-moi je suis allé un peu vite ^^

total1=0;
for j=1 :length(d1)
bary1 = bary1 + d1(j)*f( d1(j) )
total1 = total1 + f( d1(j) )             ( total des repartitions : nb d'elements sur lesquels portent l'histo)
end

bary1 = bary1/total1