4.5 Un algorithme num´ erique
143
Implantation pratique de la premi` ere partie Supposons que la fonction d de
(4.3) et son gradient aient d´ ej` a ´ et´ e calcul´ es. La r´ egion R est identifi´ ee ` a un ensemble
de pixels appartenant ` a R. Prenons un pixel P et d´ ecidons si ce point appartient ou
non au squelette. Ses huit voisins, c’est-` a dire les pixels qui le touchent par le coin
ou par un cˆ ot´ e, sont repr´ esent´ es sur la figure 4.16a. Soit δ la longueur du cˆ ot´ e d’un
(a) Les huit voisins
de P
(b) On enl` eve P
(c) On n’enl` eve
pas P
Fig. 4.16. Les huit pixels voisins du pixel P et les graphes permettant de d´ ecider si on enl` eve
P
pixel. Consid´ erons le cercle S(P, δ) centr´ e en P de rayon δ et prenons huit points P i ,
i = 1, . . . , 8, divisant ce cercle en huit arcs ´ egaux et situ´ es respectivement dans le carr´ e
repr´ esentant le pixel i. On calcule le vecteur unitaire N i normal ` a S(P, δ) en P i . On
approxime (` a une constante pr` es) l’int´ egrale (4.4) par la quantit´ e
I(P ) =
2π
8
8
i=1
N i , ∇d(P i ).
Le point P peut ˆ etre exclu si |I(P )| < <, o` u est un seuil ad´ equatement choisi. Si le
seuil est assez ´ elev´ e, on r´ eussit ` a enlever les branches qui ne font pas partie du squelette.
Par contre, on risque d’en enlever trop et de se retrouver avec un squelette en plusieurs
morceaux.
4.5.2 Deuxi` eme partie de l’algorithme
Comment pr´ evenir ce fractionnement du squelette ? Et comment peut-on conserver
au squelette sa forme d’arbre ? Pour cela, on construit le squelette `
a petits pas. Pour
chaque pixel, on doit d´ ecider s’il est ou non dans le squelette. On proc` ede d´ elicatement,
en enlevant les pixels non compris dans le squelette. On y va, couche par couche, en
partant de la fronti` ere et on obtient une r´ egion de plus en plus petite, qui, `
a la fin, n’est
que le squelette suffisamment ´ epaissi pour ˆ etre bien visible `
a l’´ ecran. Chaque fois qu’on
doit enlever un pixel, on v´ erifie que la r´ egion restante, qui devient de plus en plus mince
143
Implantation pratique de la premi` ere partie Supposons que la fonction d de
(4.3) et son gradient aient d´ ej` a ´ et´ e calcul´ es. La r´ egion R est identifi´ ee ` a un ensemble
de pixels appartenant ` a R. Prenons un pixel P et d´ ecidons si ce point appartient ou
non au squelette. Ses huit voisins, c’est-` a dire les pixels qui le touchent par le coin
ou par un cˆ ot´ e, sont repr´ esent´ es sur la figure 4.16a. Soit δ la longueur du cˆ ot´ e d’un
(a) Les huit voisins
de P
(b) On enl` eve P
(c) On n’enl` eve
pas P
Fig. 4.16. Les huit pixels voisins du pixel P et les graphes permettant de d´ ecider si on enl` eve
P
pixel. Consid´ erons le cercle S(P, δ) centr´ e en P de rayon δ et prenons huit points P i ,
i = 1, . . . , 8, divisant ce cercle en huit arcs ´ egaux et situ´ es respectivement dans le carr´ e
repr´ esentant le pixel i. On calcule le vecteur unitaire N i normal ` a S(P, δ) en P i . On
approxime (` a une constante pr` es) l’int´ egrale (4.4) par la quantit´ e
I(P ) =
2π
8
8
i=1
N i , ∇d(P i ).
Le point P peut ˆ etre exclu si |I(P )| < <, o` u est un seuil ad´ equatement choisi. Si le
seuil est assez ´ elev´ e, on r´ eussit ` a enlever les branches qui ne font pas partie du squelette.
Par contre, on risque d’en enlever trop et de se retrouver avec un squelette en plusieurs
morceaux.
4.5.2 Deuxi` eme partie de l’algorithme
Comment pr´ evenir ce fractionnement du squelette ? Et comment peut-on conserver
au squelette sa forme d’arbre ? Pour cela, on construit le squelette `
a petits pas. Pour
chaque pixel, on doit d´ ecider s’il est ou non dans le squelette. On proc` ede d´ elicatement,
en enlevant les pixels non compris dans le squelette. On y va, couche par couche, en
partant de la fronti` ere et on obtient une r´ egion de plus en plus petite, qui, `
a la fin, n’est
que le squelette suffisamment ´ epaissi pour ˆ etre bien visible `
a l’´ ecran. Chaque fois qu’on
doit enlever un pixel, on v´ erifie que la r´ egion restante, qui devient de plus en plus mince