Discussion :

[hksa93]

Bonjour,
j'ai une liste de points ou de pixels dans une image, Comment trouver les pixels qui se reliés (connectés) et calculer les distances entre chaque paire de pixels
Merci.

[Jean Dumoncel]

Salut,

ce que tu appelles pixels connectés, ce sont des pixels qui ont la même valeur?

Si oui, tu peux les trouver en utilisant find sur ta matrice,
exemple si X est ton image :

Code :

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

1
2
valeur = 1;
[ligne colonne] = find(X==1);

ceci va te retourner les coordonnées des points de la matrice X qui valent 1. Ensuite pour chaque couple tu peux calculer les distances par rapport aux autres points.

En espérant ne pas répondre à coté de ta question...

[hksa93]

En fait c'est une image binaire squelettisée, où j'ai des branches interconnectées.

Ce que je cherche c'est trouver des distance entre nœuds et extrémités.

Bon les nœuds et les extrémités sont trouvés, mais il faut d'abord savoir quelle extrémité ou nœud qui est connecté avec un autre.

Et ce que j'appelle connecté il n'y a pas de discontinuité entre un nœud et une extrémité ou nœud à nœud...

[Jerome Briot]

Utilise la fonction BWLABEL

[hksa93]

mais le fonction bwlabel travail sur des objets qui ne sont pas interconnectés, mais moi j'ai des branches interconnecté via des nœuds ou des extrémités.
j'ai une extrémité ou 1 nœud je dois chercher quel est le nœuds ou l'extrémité avec laquelle est connecté, puis calculer la distance de ce "morceau".
la fonction bwlabel suppose chaque objet séparément alors que moi les objets qui sont les branches, sont interconnectés.

[Jean Dumoncel]

Il faudrait en savoir plus sur tes branches et sur la finesse de ton squelette, mais en partant d'une extrémité, tu dois pouvoir trouver le noeud le plus proche en utilisant la connectivité des pixels, non?

[hksa93]

le squelette est de 1 pixel, mais si on parcours pour chaque pixel pour trouver la connexité avec une autre extrémité ou noeud, les combinaisons il y en aura trop et le programme devient tres tres couteux en temps de calcul, je crois que c'est impossible.
il doit y avoir une solution plus simple, matlab doit en disposer, peut etre avec la toolbox sur la theorie des graphes

[malab]

Pour dire que c'est trés couteux, tu as essayé ?
Ca revient a rechercher les points triples.
ImagingAll

[Jean Dumoncel]

le squelette est de 1 pixel, mais si on parcours pour chaque pixel pour trouver la connexité avec une autre extrémité ou noeud, les combinaisons il y en aura trop et le programme devient tres tres couteux en temps de calcul, je crois que c'est impossible.
il doit y avoir une solution plus simple, matlab doit en disposer, peut etre avec la toolbox sur la theorie des graphes

A moins de travailler sur des branches vraiment très très grande, je ne pense pas non plus que les temps de calcul soient astronomiques...

Si tu as essayé, peux-tu nous montrer comment tu as fait?

[hksa93]

salut magelan,
si tu as dans une image 200 extremité et 300 noeuds, tu imagine les combinaisons que tu pourras avoir pour chaque extremité tu balaye jusqu'a avoir le prochain noeud ou extremité (sans discontinuité), c'est enorme meme si tu as de petites branches, j'ai essayé avec une petite image de 150 x 150 et peu de branche, c'est pas lent (avec 48 extremité et 80 noeuds),,mais pour une image 256 x256 où il y a 800 extremités et 1000 noeuds par exemple, c'est pas la peine d'imaginer.

[Caro-Line]

Bonjour,

Je n'ai personnellement pas compris grand-chose à ce que tu essayes de faire.
Par contre je pense que si tu nous montres ton code (qui fonctionne sur une petite image),
il est fort possible que certains ici soient capables de l'améliorer pour qu'il soit plus rapide et finisse donc par fonctionner pour de grandes images.

C'est juste une idée, comme ça, en passant...

[hksa93]

a vrai dire j'ai pas encore fini a trouver ce que je cherche (c'est comment savoir que deux deux noeuds ou deux extrémité ou un nœud et une extrémité sont connecté.
voici quand même un code, juste pour trouver le nombre des extrémités, de nœuds et répertorier leurs positions:

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
21
22
23
24
25
26
27
28
29
30
31
% row1 et col1 sont les coordonnées des pt extrémités
%  row2 et col2 sont les coordonnées des pt noeuds
% h c'est l'image binaire squelettisée à 1 pixel
 
con = 0; nb_extrem = 0; nb_noeud = 0;
k = 1; kk = 1;
for i=2:m-1
    for j=2:n-1
        con = 0; 
        if(h(i,j)==1)
 
            if(h(i-1,j-1)==1) con = con + 1; end
            if(h(i-1,j)==1) con = con + 1; end
            if(h(i-1,j+1)==1) con = con + 1; end
            if(h(i,j-1)==1) con = con + 1; end
            if(h(i,j+1)==1) con = con + 1; end
            if(h(i+1,j-1)==1) con = con + 1; end
            if(h(i+1,j)==1)con = con + 1; end
            if(h(i+1,j+1)==1) con = con + 1; end
 
        end
        if(con==1) nb_extrem = nb_extrem + 1; 
            row1(k)=i;col1(k)=j; k=k+1; end
 
        if(con>2)  nb_noeud = nb_noeud + 1;
            row2(kk)=i;col2(kk)=j; kk=kk+1;end
 
    end
end
 
%---------------end

bon ce code marche bien quelque soit l'image, mais je veux savoir maintenant les connectivités entre les noeuds et les extrémités (les distances nœud-noeud, noeud-extrémité, extrémité-extrémité) c'est ca mon but
j'espere que j'etais assez clair

[Caro-Line]

Alors je pense que c'est largement optimisable.

Déjà quelques remarques très vite, bien lire les commentaires :

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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
%  row2 et col2 sont les coordonnées des pt noeuds
% h c'est l'image binaire squelettisée à 1 pixel
 
%** Regle de codage : Eviter de mettre plusieurs instructions
%** sur une meme ligne
 
%con = 0; %** celui-ci est inutile puisque tu le réinitialises  chaque fois dans la boucle
 
nb_extrem = 0;
nb_noeud = 0;
k = 1;
kk = 1;
 
 
for i=2:m-1
    for j=2:n-1
        con = 0; 
        if(h(i,j)==1)
           %Si je ne me trompe pas con est bien le nombre de h(i2,j2) == 1
           %autour de h(i,j)
           con = (h(i-1,j-1)==1) + (h(i-1,j)==1) + (h(i-1,j+1)==1) + ...
               (h(i,j-1)==1) + (h(i,j+1)==1) + (h(i+1,j-1)==1) + ...
               (h(i+1,j)==1) + (h(i+1,j+1)==1)                      
 
        if (con==1) 
            nb_extrem = nb_extrem + 1; 
            row1(k)=i;
            col1(k)=j; 
            k=k+1; 
        elseif con > 2 %evite 1 test
        %end
 
        %if (con>2)  
            nb_noeud = nb_noeud + 1;
            row2(kk)=i;
            col2(kk)=j; 
            kk=kk+1;
        end
        end %** J'ai deplace ce end, en effet si h(i,j) ~=1, con reste a 0
            %** donc les tests sont inutiles
 
    end
end
 
%---------------end

Je répète que je ne fais que modifier ton code.
Par contre un truc me "choque" : c'est normal que tu ne fasses rien si con==2 ?

[hksa93]

salut Caro-Line,

merci pour l'optimisation,
d'abord con c'est le nombre de voisins
pour con==2, je ne fais rien car j'ai pas besoin, une extremité d'on 1 seul voisin et un noeud c'est au moin 3 voisins, donc pas de con==2
et maintenant ce que je veux c'est de chercher les connectivité de ces neuds et ces extremités, c'est le plus dur.

j'ai pas encore essayé ton code s'il marche, mais la connectivité m'ai plus important, merci

[Jean Dumoncel]

Aurais-tu un exemple d'image binaire à traiter à nous fournir?

Sinon, effectivement l'idée d'associer le squelette à un graphe me parait bonne, encore faut-il construire ce graphe, en attribuant des numéros aux noeuds, branches et extremités pendant la recherche des noeuds et des extrémités.

[hksa93]

voici une image ci-dessous, comment calculer les distances noeuds extremités par exemples

[Jerome Briot]

Pour différencier les noeuds des extrémités, je ferais comme ceci :

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
[I,map] = imread('noeuds_extremite.gif','gif');
 
BW = I~=0;
 
BW = bwmorph(BW,'skel');
 
C = conv2(single(BW),[1 1 1 ; 1 0 1 ; 1 1 1],'same');
 
[a,b] = find((C==1)&BW);
 
C2 = conv2(single(BW),[0 1 0 ; 1 0 1 ; 0 1 0],'same');
 
[c,d] = find((C>2)&BW);
 
figure
imagesc(BW)
axis image
hold on
plot(b,a,'g*',d,c,'m*')

Enfin c'est l'idée...

[hksa93]

salut Dut,
programme tres court, tres interessant.
Pour la squelettisation il manque Inf, la ligne C2=.... donc elle est inutile
pour les extremité ca marche bien, pour les noeuds il y a quelque chose qui cloche.
Finallement je me rend compte une chose que l'approche de "plus de deux voisins c'est un noeud est fausse", il y a des pixels où ils presentent 3 voisins mais se ne sont pas des noeuds (voir l'image ci dessous)

[hksa93]

non finallement il y avait eu une petite erreur de frappe qui s'est glissée dans ton code Dut:
C2 est utile finallement et

[c,d] = find((C2>2)&BW);
au lieu de
[c,d] = find((C>2)&BW);

mais malgré ca, il y a des noeuds indetectés, il faut d'autres masques de convolution, le code precedent detecte seulement les noeuds en T (dans les 4 positions du T).
merci.