[Traitement d'image , morpho maths] Squelette Algo.

Version imprimable

Voir 40 message(s) de cette discussion en une page

10/04/2006, 18h16
parp1

[Traitement d'image , morpho maths] Squelette Algo.

Bonjour a toutes et tous.

Voila je souhaite avoir si possible un algorithme de squelette.

Je sais qu'un squelette est l'ensemble des points qui sont constitués par tous les cercles inscrit touchant au moins deux coté dans notre objet.

Primo:si je fait fausse route ou si vous avez une meilleur explication faite le moi savoir.

Deuxio: J'aimerai avoir un algo car j'ai un peu de mal a voir comment programmer ca.

Je travaille sur des matrice que j'envoi dans un tuple qui est lui meme envoyé dans une image.

Voila merci.
10/04/2006, 20h55
Matthieu Brucher

C'est l'ensemble des centres de ces cercles, oui. En fait, ça c'est ce que c'est, ensuite, on utilise des algos de morpho math. Sur le coup, je n'ai pas de lien, mais regarde skeletonize ou skeletonization sur ton moteur de recherche favori ;)
10/04/2006, 21h39
parp1

Merci bien.
J'espere que je vais trouver une ptit bout de code.

Aplus
11/04/2006, 10h53
mathieu_t

Sinon il me semble que sous Matlab il y a des fonctions toutes faites du style erode ou dilate (à vérifier)... Dans ce cas tu as aussi le source de ces fonctions, donc tu peux voir comment ça marche !

A+
11/04/2006, 11h17
ToTo13
Bonjour,

la théorie est belle, mais elle est inaplicable directement dans le cas discret.

Donc pour obtenir le squelette d'une image, il faut utiliser des masques de la formes :
Code:

1 2 3 4 0 0 0 * 1 * 1 1 1
ainsi que les sept autres rotations et symétries.

Comment les interpréter : pour un pixel de ton image, tu centre ton masque dessus, puis il faut que son voisinage corresponde : 0 le voisin ne doit pas etre plein, 1 le voisin doit être de la matière.

Ceci te permettra de calculer le squellete de toutes les formes, c'est ce que l'on appelle un squelette par amincissement.

Bonne continuation.
11/04/2006, 11h18
ToTo13

oups j'ai oublié :

une * siginifie que l'on se moque si c'est de la matière ou du vide.
;)
11/04/2006, 11h26
parp1

Ok merci a tous.

Donc enfait j'ai juste a convoluer mon image avec le masque que TOTO ma filer en le faisait roter sur les huit ou quatre connexité.? c'est si simple que ca?

Et par exemple pour le skiz, est ce que l'on pourrait appeler ca un squelette par epaississement.?
Je pense car dans le logiciel ... (que je n'aime pas a cause de la politique de l'entreprise et a cause du bug incessant.) car pour trouver le skiz il faut aller dans l'operateur thinken et selectionné skiz dans les options.

En tout cas merci pour vos intervention.

salutation
11/04/2006, 11h46
ToTo13

euh...

c'est quoi que tu appelles un skiz ???
11/04/2006, 12h16
parp1

Skeleton by influance zone

Squelette par zone d'influance.
C'est tres similaire a la LPE sous contrainte niveau resultat.

Mais j'ai des souci avec ma LPE sous contrainte. Donc si je peut passer par le skiz

Voila.
A oui une chose.

Citation:

Comment les interpréter : pour un pixel de ton image, tu centre ton masque dessus, puis il faut que son voisinage corresponde : 0 le voisin ne doit pas etre plein, 1 le voisin doit être de la matière.

Matiere et plein ce n'est pas la meme chose.Tu voulait peut etre dire Vide et matiere.
11/04/2006, 13h09
ToTo13

oui

pour moi matière et plein c'était pareil dans ce cas.
11/04/2006, 13h50
parp1
Ca y est j'ai relu mes cours de morpho maths.

Il existe plusiseur type de squelette par aminssisement.

Selon l'alphabet de Golay

Squelette homotopique L
Code:

1 2 3 4 5 6 Lskel 0 0 0 x 1 x 1 1 1
Squelette homotopique M
Code:

1 2 3 4 5 6 Mskel 1 1 x x 1 0 0 0 0
Ebarbage
Code:

1 2 3 4 5 6 E x 1 x 0 1 0 0 0 0
En appliquant ces noyaux, nous obtenons un aminssissement

En appliquant d'autre noyaux sur nos squelette :
Code:

1 2 3 4 5 6 7 E x 1 x 0 1 0 0 0 0
Nous obtiendrons les points extremes du squelette
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 F 0 x 0 1 1 1 0 1 0 et F' x 0 x 1 1 1 x 1 x et F" x 1 x 1 0 1 x 1 x
Nous obtiendrons les points multiples du squelette

Tous ca en maille Carrée
11/04/2006, 14h37
parp1
Bon assez de theorie!!!!
J'ai essayer l'aminssissement.
Avec le noyaux :
Code:

1 2 3 4 5 6 7 8 9 10 11 [0,0,0] [0,1,0] [1,1,1] en guise de [0,0,0] [x,1,x] [1,1,1]
:?: Est ce que les x peuvent etre remplaces par des 1 ou 0 arbitrairement? parcque j'obtiens un epaississement.

Je vais essayer de replacé les x par ds 1 cette fois.

Si quelqu'un a une reponse.Merci
11/04/2006, 14h43
ToTo13

Les x c'est ce que tu veux, une sorte de jocker qui fait que si c'est du vide ou du plein, ça n'a pas d'importance. En fait, c'est des voisins que l'on ne regarde pas.

Par contre, il faut utiliser les huits masque et non deux pour avoir un squelette complet.
Il faut répéter ton opération tant que tu continu à enlever de la matière.
11/04/2006, 14h49
parp1

Oui j'ai fait les huit masques.
Mais j'obtiens un epaississement donc la deja pour eviter de m'ennuyer a faire huit fois la rotation du masque je vais utilise une fonction qui me fait roter la matrice de x degrees.

Sauf que pour 45 degres il me fait une matrice 4*4 a partir d'une matrice 3*3

Donc je vais me renseigner sur le forum approprier.

Tiens comment savoir si j'arrive bien au squelette. Parcqu'il faut repeter l'operation jusqu'a que l'objet fasse 1 pixel d'epaisseur . ??? tu crois que c'est un bon critere?

Merci
11/04/2006, 14h52
ToTo13

mmmmmmmm

si tu as un epaississement c'est que tu as fait l'opération inverse.
Mais étant donné qu'il n'y a que huit masque, j'ai fait une petite fonction qui me créé le huit masque, soit en dur, soit un peu plus intelligement.

Je te file le bout de code ou ya la convolution.

Code:

1
2
3
4
5
6
7
8
9
a.setshape((hauteur,largeur)) # a est une matrice contenant les data ds pixels
a=_cv.convolve2d(a,[[0,0,0],[0,1,0],[1,1,1]]) # a devient a convolué par le masque 0 deg
a=_cv.convolve2d(a,[[0,0,0],[1,1,0],[1,1,0]]) #a devient  a convolué par le masque 45deg
a=_cv.convolve2d(a,[[1,0,0],[1,1,0],[1,0,0]]) #etc
a=_cv.convolve2d(a,[[1,1,0],[1,1,0],[0,0,0]])
a=_cv.convolve2d(a,[[1,1,1],[0,1,0],[0,0,0]])
a=_cv.convolve2d(a,[[0,1,1],[0,1,1],[0,0,0]])
a=_cv.convolve2d(a,[[0,0,1],[0,1,1],[0,0,1]])
a=_cv.convolve2d(a,[[0,0,0],[0,1,1],[0,1,1]])

a coup sur l'erreur me creve les yeux.... mais comme d'habitude... faut le voir. :cry:

12/04/2006, 10h45
Flo.

Salut,

tu dois respecter les "x" du masque.

Les "x" veulent dire : "ne te préoccupe pas de la valeur de ce pixel-là". Lors de la convolution de l'image par le masque, tu ne les considères pas, tu ne les inspectes pas.

Lors de la convolution de l'image par le masque, si un pixel et son voisinage correspondent à la configuration du masque alors une certaine action est faite sinon une autre action est faite (en gros pour ce type d'opération).

Donc si tu remplaces les "x" par des 1, tu modifies la configuration du masque, et donc tu modifies la condition pour le choix de l'action à appliquer en fonction du résultat de la convolution.

D'où le résultat non escompté.

En conclusion, il faut respecter les "x".

A+

Flo.

PS : j'ai un code en c++ si tu veux pour le squelette et l'ébarbulage
12/04/2006, 19h04
parp1

Merci Flo.
Mais le probleme c'est que je ne sais pas quoi mettre en guise de X sinon je savait bien que les X représentaient les pixel non regardés.

Si tu peut mettre ton code ca m'interesse.

Merci

Salut

Voici la fonction qui fait la convolution d'une image par un filtre de type "amincissement" :

Code:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
 * Apply a thining filter to the image.
 *
 * @param src image of the source
 * @param dst image of the destination
 * @param width width of the image
 * @param height height of the image
 * @param filter filter (unsigned char[3*3]) to apply to the image
 * @param unchecked unsigned char grey color to apply to the pixel of the image of destination if the filter configuration is not checked
 * @param checked unsigned char grey color to apply to the pixel of the image of destination if the filter configuration is checked
 *
 * @return true if the filter configuration was at least one time checked, false otherwise.
 */
bool ThinningFiltering(unsigned char * src, unsigned char * dst, int width, int height, unsigned char * filter, unsigned char unchecked, unsigned char checked)
{
        // if a filter value is equal to nomatter, then we will not consider the corresponding neighbourg
        unsigned char nomatter = 128;
 
        // to check whether filter configuration was at least one time checked
        bool wasmodified = false;
 
        // browse each line  (except the first and the last)
        for(int y = 1, index = width; y < height - 1; y++)
        {
                index++;
 
                // browse each pixel of the current line  (except the first and the last)
                for(int x = 1; x < width - 1; x++, index++)
                {
                        // if the current pixel do not checked the kernel center value
                        if(src[index] != filter[4])
                        {
                                // copy the pixel of the source to the pixel of the destinationand go on with the next pixel
                                dst[index] = src[index];
                                continue;
                        }
 
                        // Browse the 8 neighbourgs except if the corresponding filter value is "nomatter".
                        // If filter configuration is at least on time unchecked, then copy the unchecked gray color 
                        // to the current pixel of the destination and go on with the next pixel.
                        if((filter[0] != nomatter) && (filter[0] != src[index - width - 1])) {dst[index] = unchecked; continue;}
                        if((filter[1] != nomatter) && (filter[1] != src[index - width + 0])) {dst[index] = unchecked; continue;}
                        if((filter[2] != nomatter) && (filter[2] != src[index - width + 1])) {dst[index] = unchecked; continue;}
 
                        if((filter[3] != nomatter) && (filter[3] != src[index         - 1])) {dst[index] = unchecked; continue;}
                        if((filter[5] != nomatter) && (filter[5] != src[index         + 1])) {dst[index] = unchecked; continue;}
 
                        if((filter[6] != nomatter) && (filter[6] != src[index + width - 1])) {dst[index] = unchecked; continue;}
                        if((filter[7] != nomatter) && (filter[7] != src[index + width + 0])) {dst[index] = unchecked; continue;}
                        if((filter[8] != nomatter) && (filter[8] != src[index + width + 1])) {dst[index] = unchecked; continue;}
 
                        // filter configuration is checked so copy to the current pixel of the destination, the checked gray color
                        dst[index] = checked;
 
                        // memorize that filter configuration was at least one time checked
                        wasmodified = true;
                }
 
                index++;
        }
 
        // return whether filter configuration was at least one time checked or not
        return wasmodified;
}

Définition du filtre pour le calcul du squelette (configuration L) :

Code:

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
        unsigned char x = 128; // "x" real mask value (c'est le nomatter de la fonction précédente)
        unsigned char l = 255; // "1" real mask value (be carreful "l" is the "L" letter not a number)
 
        unsigned char LSkeleton1[3 * 3] = {l, l, l,
                                           x, l, x,
                                           0, 0, 0};
 
        unsigned char LSkeleton2[3 * 3] = {l, l, x,
                                           l, l, 0,
                                           x, 0, 0};
 
        unsigned char LSkeleton3[3 * 3] = {l, x, 0,
                                           l, l, 0,
                                           l, x, 0};
 
        unsigned char LSkeleton4[3 * 3] = {x, 0, 0,
                                           l, l, 0,
                                           l, l, x};
 
        unsigned char LSkeleton5[3 * 3] = {0, 0, 0,
                                           x, l, x,
                                           l, l, l};
 
        unsigned char LSkeleton6[3 * 3] = {0, 0, x,
                                           0, l, l,
                                           x, l, l};
 
        unsigned char LSkeleton7[3 * 3] = {0, x, l,
                                           0, l, l,
                                           0, x, l};
 
        unsigned char LSkeleton8[3 * 3] = {x, l, l,
                                           0, l, l,
                                           0, 0, x};

Et pour calculer le squelette :

- src : image binaire source dont tu veux calculer le squelette
- tmp : image temporaire

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
        bool wasmodified = true;
 
        // while there is something to thin in the image
        while(wasmodified)
        {
                wasmodified = false;
 
                // Apply the 8 L skeleton filters, and verify that images was thinned
                // If the filter configuration is not checked by a pixel and its neighborhood, then pixel will be set at 255
                // Otherwise (filter configuration is checked), pixel will be set at 0
                wasmodified |= ThinningFiltering(src, tmp, width, height, &LSkeleton1[0], 255, 0);
                wasmodified |= ThinningFiltering(tmp, src, width, height, &LSkeleton2[0], 255, 0);
                wasmodified |= ThinningFiltering(src, tmp, width, height, &LSkeleton3[0], 255, 0);
                wasmodified |= ThinningFiltering(tmp, src, width, height, &LSkeleton4[0], 255, 0);
                wasmodified |= ThinningFiltering(src, tmp, width, height, &LSkeleton5[0], 255, 0);
                wasmodified |= ThinningFiltering(tmp, src, width, height, &LSkeleton6[0], 255, 0);
                wasmodified |= ThinningFiltering(src, tmp, width, height, &LSkeleton7[0], 255, 0);
                wasmodified |= ThinningFiltering(tmp, src, width, height, &LSkeleton8[0], 255, 0);
        }

Le résultat final est dans src (l'image source).

Voilà.

C'est un code que j'avais fait pour tester différentes configurations de filtres. C'est pas optimisé. Si tu veux l'optimiser il faut faire une fonction de convolution de l'image par le filtre pour chaque filtre pour s'éviter les conditions de verification du "x" (du "nomatter" dans le code) pour chaque pixel voisin de chaque pixel de l'image. (je sais pas si je suis bien clair là :D :? )

Par contre c'est pas un truc sur lequel j'ai travaillé longtemps, donc garre au bug de programmation.

En cas de problème, de bug, de questions sur le code ou de son éventuelle amélioration (dans un cadre d'utilisation générique), n'hésite pas.

A+

Flo.

13/04/2006, 17h46
parp1

Donc ici Tu dit que un X est un gris. Oui c'est vrai ni blanc ni noir.... ou pas plus blanc que noir.J'y est pas penser
Sincerement merci pour ta source....

Je me suis essayer au C++,avec le mega cour de casteyde.

Je me suis arreter au chapitre "couche objet".

Le truc qui me soule c'est que tout le monde me dit "le C++ c'est chiant et dur" ....Il faut comprendre l'orientation OBjet.... J'ai compris l'héritage puisqu'il y en a en python.Les classes etc etc.
Je pense que mon probleme c'est que je n'ai pas le niveau pour faire un projet concret.
Donc je m'y remettrai parcque la rigoureusité de ce language me plait ... et elle me coutera surment des cheveux aussi ....

Voila merci encor je vais essayer .

Merci

Voir 40 message(s) de cette discussion en une page