144
4 Squelette et chirurgie aux rayons gamma
et qui se rapproche d’un graphe, reste connexe, et qu’on ne cr´ ee pas de cycle dans le
graphe. Voyons maintenant les d´ etails.
Implantation pratique de la deuxi` eme partie On commence par d´ ecider que les
pixels de la fronti` ere ne font pas partie du squelette. On analyse ensuite les pixels un
par un, en partant de la fronti` ere. Pour un pixel P , on commence par calculer I(P ). Si
|I(P )| < <, le pixel P peut ˆ etre enlev´ e. Pour d´ ecider si on l’enl` eve, on regarde l’´ etat de
ses huit voisins de la figure 4.16a. Si aucun des voisins n’a ´ et´ e enlev´ e, on n’enl` eve pas
P , car on cr´ eerait un trou. Si au moins un des voisins a ´ et´ e enlev´ e, alors on construit un
graphe sur les voisins non enlev´ es. On met une arˆ ete entre i et j si i et j sont voisins par
un cˆ ot´ e ou par un coin. Les paires de voisins possibles sont : (1, 2), (2, 3), (3, 4), (4, 5),
(5, 6), (6, 7), (7, 8), (8, 1), (2, 4), (4, 6), (6, 8), (8, 2). Par contre, on ne veut pas cr´ eer de
cycle dans le graphe. De tels cycles sont donn´ es par les triplets d’arˆ etes
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
{(1, 2), (8, 1), (8, 2)},
{(2, 3), (3, 4), (2, 4)},
{(4, 5), (5, 6), (4, 6)},
{(6, 7), (7, 8), (6, 8)}.
Si un tel triplet est pr´ esent, alors on enl` eve l’arˆ ete diagonale. Par exemple, on remplace le
triplet d’arˆ etes {(1, 2), (8, 1), (8, 2)} par le couple d’arˆ etes {(1, 2), (8, 1)}. Une fois qu’on
a construit ce graphe dont les sommets sont les voisins de P qui n’ont pas ´ et´ e enlev´ es,
on enl` eve P si et seulement si ce graphe est un arbre (voir figure 4.16b et c). Une fois
qu’on a d´ ecid´ e si on enl` eve P ou non, on s’occupe du pixel suivant de la mˆ eme mani` ere.
Notons qu’une m´ ethode pour tester si ce graphe est un arbre est donn´ ee ` a l’exercice 15.
Remarque Cette m´ ethode peut ˆ etre g´ en´ eralis´ ee pour des r´ egions tridimensionnelles.
4.5.3 Preuve de la proposition 4.17
Rappelons que la proposition 4.17 affirme que, si R est une r´ egion telle que ∂R est de
classe C
2 (respectivement C
3 ), alors la fonction d(X) est de classe C
1 (respectivement
C
2 ) aux points de R \ Σ(R), et le champ ∇d(X) est continu (respectivement C
1 ) sur
R \ Σ(R).
Pour montrer cela, il nous faut « calculer » d(X). Ceci se fait par le th´ eor` eme des
fonctions implicites que nous rappelons :
Th´ eor` eme 4.22 Soit F = (f 1 , . . . , f n ) : U → R
n une fonction de classe C
r , r ≥ 1, sur
un ouvert U ⊂ R
n+k . On note les points de U comme des couples (X, Y ), avec X ∈ R
n
et Y ∈ R
k , et on note X = (x 1 , . . . , x n ). Soit (X 0 , Y 0 ) ∈ U tel que F (X 0 , Y 0 ) = 0 et tel
que la matrice jacobienne partielle
J(X 0 , Y 0 ) =
⎛
⎜
⎝
∂f1
∂x1
. . .
∂f1
∂xn
. . .
. . .
. . .
∂fn
∂x1
. . .
∂fn
∂xn
⎞
⎟
⎠ (X 0 , Y 0 )
4 Squelette et chirurgie aux rayons gamma
et qui se rapproche d’un graphe, reste connexe, et qu’on ne cr´ ee pas de cycle dans le
graphe. Voyons maintenant les d´ etails.
Implantation pratique de la deuxi` eme partie On commence par d´ ecider que les
pixels de la fronti` ere ne font pas partie du squelette. On analyse ensuite les pixels un
par un, en partant de la fronti` ere. Pour un pixel P , on commence par calculer I(P ). Si
|I(P )| < <, le pixel P peut ˆ etre enlev´ e. Pour d´ ecider si on l’enl` eve, on regarde l’´ etat de
ses huit voisins de la figure 4.16a. Si aucun des voisins n’a ´ et´ e enlev´ e, on n’enl` eve pas
P , car on cr´ eerait un trou. Si au moins un des voisins a ´ et´ e enlev´ e, alors on construit un
graphe sur les voisins non enlev´ es. On met une arˆ ete entre i et j si i et j sont voisins par
un cˆ ot´ e ou par un coin. Les paires de voisins possibles sont : (1, 2), (2, 3), (3, 4), (4, 5),
(5, 6), (6, 7), (7, 8), (8, 1), (2, 4), (4, 6), (6, 8), (8, 2). Par contre, on ne veut pas cr´ eer de
cycle dans le graphe. De tels cycles sont donn´ es par les triplets d’arˆ etes
⎧
⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎩
{(1, 2), (8, 1), (8, 2)},
{(2, 3), (3, 4), (2, 4)},
{(4, 5), (5, 6), (4, 6)},
{(6, 7), (7, 8), (6, 8)}.
Si un tel triplet est pr´ esent, alors on enl` eve l’arˆ ete diagonale. Par exemple, on remplace le
triplet d’arˆ etes {(1, 2), (8, 1), (8, 2)} par le couple d’arˆ etes {(1, 2), (8, 1)}. Une fois qu’on
a construit ce graphe dont les sommets sont les voisins de P qui n’ont pas ´ et´ e enlev´ es,
on enl` eve P si et seulement si ce graphe est un arbre (voir figure 4.16b et c). Une fois
qu’on a d´ ecid´ e si on enl` eve P ou non, on s’occupe du pixel suivant de la mˆ eme mani` ere.
Notons qu’une m´ ethode pour tester si ce graphe est un arbre est donn´ ee ` a l’exercice 15.
Remarque Cette m´ ethode peut ˆ etre g´ en´ eralis´ ee pour des r´ egions tridimensionnelles.
4.5.3 Preuve de la proposition 4.17
Rappelons que la proposition 4.17 affirme que, si R est une r´ egion telle que ∂R est de
classe C
2 (respectivement C
3 ), alors la fonction d(X) est de classe C
1 (respectivement
C
2 ) aux points de R \ Σ(R), et le champ ∇d(X) est continu (respectivement C
1 ) sur
R \ Σ(R).
Pour montrer cela, il nous faut « calculer » d(X). Ceci se fait par le th´ eor` eme des
fonctions implicites que nous rappelons :
Th´ eor` eme 4.22 Soit F = (f 1 , . . . , f n ) : U → R
n une fonction de classe C
r , r ≥ 1, sur
un ouvert U ⊂ R
n+k . On note les points de U comme des couples (X, Y ), avec X ∈ R
n
et Y ∈ R
k , et on note X = (x 1 , . . . , x n ). Soit (X 0 , Y 0 ) ∈ U tel que F (X 0 , Y 0 ) = 0 et tel
que la matrice jacobienne partielle
J(X 0 , Y 0 ) =
⎛
⎜
⎝
∂f1
∂x1
. . .
∂f1
∂xn
. . .
. . .
. . .
∂fn
∂x1
. . .
∂fn
∂xn
⎞
⎟
⎠ (X 0 , Y 0 )