Read rapport.dvi text version

Techniques multi-resolution cooperatives pour l'analyse structurelle des os de la main

H. Bronnimann P. Chassignet mars 1998

Nous developpons un systeme de calcul de l'^ge osseux a partir d'une radiographie de la a main. Le probleme actuel est de pouvoir identi er les di erentes regions osseuses pour proceder aux mesures de forme, de distance ou de surface voulues. Apres avoir envisage des solutions classiques de segmentation de l'image, nous nous sommes orientes vers des solutions qui utilisent des connaissances a priori sur la morphologie du squelette de la main. Ce rapport expose une experimentation comparative de l'utilisation des deux approches, par contours et par regions, dans le cadre d'une analyse multi-resolution et en cooperation avec un modele geometrique. Nous regardons comment, dans ce contexte, les di erentes sources d'information peuvent ^tre combinees pour ameliorer la detection et l'identi cation des contours e des os. C'est la cooperation entre contours et modele qui appara^t comme la plus bene que. L'inter^t e complementaire de l'approche par regions est moins evident.

Resume

1

1 Introduction

La connaissance de l'^ge osseux est un element de diagnostic important en pediatrie. L'^ge a a osseux est une mesure precise et objective du degre de developpement de l'enfant, alors que le poids ou la taille sont des mesures de sa croissance. La main de l'enfant est une structure facile a radiographier et le developpement des parties calci ees s'observe aisement (voir gures 1 et 2).

a ^ge osseux 1 an

Fig.

a ^ge osseux 3 ans

a ^ge osseux 6 ans

a ^ge osseux 12 ans

1 { Exemples d'ossi cation des doigts en fonction de l'^ge a

a ^ge osseux 1 an

Fig.

a ^ge osseux 5 ans

a ^ge osseux 14 ans

2 { Exemples d'ossi cation du carpe en fonction de l'^ge a

La methode generalement utilisee pour la determination de l'^ge osseux consiste a comparer a visuellement la radiographie de la main avec les images d'un catalogue de reference comme, par exemple, l'atlas de Greulich et Pyle 1]. C'est une methode qui reste neanmoins imprecise et subjective. La notion de normalite, pour une structure en perpetuelle modi cation avec la croissance, reste di cile a ma^triser. Il existe des methodes d'analyse plus sophistiquees, telle que celle dite TW2 2]. Leur complexite est totalement prohibitive pour un usage systematique quotidien et de masse. D'autre part, il y a un reel besoin de pouvoir rede nir les normes pour les adapter aux populations actuelles et ensuite assurer leur mises a jour regulieres. Ces t^ches peuvent ^tre realisees dans de meilleures conditions par le traitement informatique a e des images. Notre travail vise a developper une procedure utilisable sur des images de faible resolution (de l'ordre de 300 500 pixels), mal contrastees et relativement bruitees. L'un des buts est de 2

pouvoir exploiter des images obtenues par numerisation de cliches conventionnels et de realiser les traitements sur des machines de puissance modeste. Un autre but est de pouvoir traiter rapidement un grand nombre d'images a n de constituer un nouvel atlas de reference entierement numerique. Dans ce contexte, le premier objectif est de pouvoir e ectivement identi er les di erentes regions osseuses pour ensuite proceder aux mesures de forme, de distance ou de surface caracteristiques de l'^ge osseux. a La section 2 est un recapitulatif de l'experimentation des techniques classiques dans ce but. Il s'agit de methodes de segmentation basees sur le calcul des contours a partir des derivees de l'image. Cette approche ne permet pas de traiter correctement les problemes lies a la superposition des regions osseuses qui se posent notamment pour le carpe. Ceci nous a conduit a introduire un modele geometrique qui apporte des connaissances a priori sur la morphologie du squelette de la main. Ces informations sont utilisees pour la selection des contours. La section 3 decrit ce modele, le principe de son calibrage a partir des contours des os longs et le principe de selection des contours du carpe. Nous y decrivons egalement une methode d'a nage du modele a partir des fragments de contours obtenus lors d'une premiere passe. Nous avons ensuite regarde si une approche fondamentalement di erente peut apporter de l'information supplementaire, en particulier, la ou le gradient n'est pas utilisable. La section 4 traite de la construction de regions de nies sur des criteres de coherence d'intensite puis de leur fusion guidee par le modele.

2 Segmentation par les contours

2.1 Calcul des contours par le gradient

1

Nous avons, dans un premier temps, envisage les techniques classiques de calcul des contours par les derivees de l'image . Cette approche est fondee sur la caracterisation d'un contour comme un chemin continu passant par les points ou le gradient de l'image est un maximum local dans la direction du gradient 3], c'est-a-dire, des points veri ant :

@g (g ) = 0

2

soit, encore :

gT H g = 0

(1)

ou g et H sont respectivement le gradient et le hessien de l'image et ou @g note la derivee dans la direction du gradient g. Pour les derivees secondes, le rapport signal=bruit et la localisation sont generalement mediocres, ce qui rend l'equation (1) di cilement exploitable. Notre methode est donc basee sur une recherche directe des maxima du module du gradient dans la direction du gradient. Pour calculer les composantes du gradient, nous utilisons des ltres de Deriche 4]. Ces ltres sont optimaux pour les criteres de localisation et de detection de Canny 5]. Ils ont egalement l'avantage d'^tre separables et recursifs ce qui permet une implantation e cace. e

1: l'intensite etant consideree comme une fonction des coordonnees I (x; y).

3

Dans le cas mono-dimensionnel, l'expression de la reponse impulsionnelle des ltres de Deriche est la suivante, respectivement f pour le lissage et f pour la derivee premiere :

0 1

f (x) = c (1 + jxj) e? jxj

0 0

f (x) =

1

?c x e?

1 2 1

jxj

Le parametre permet de regler le compromis entre une bonne detection, ie. attenuation du bruit (avec faible, pour un critere de qualite en p ), et une bonne localisation (avec eleve, p pour un critere de qualite en ). Nous determinons en fonction des dimensions de l'image que nous avons considerees comme representatives des dimensions des regions osseuses. Chaque composante du gradient est calculee par la convolution de I (x; y) par un ltre de derivation dans la direction consideree et par un ltre de lissage transversal :

@I = f (x) ? f (y) ? I (x; y) @x @I = f (y) ? f (x) ? I (x; y) @y

1 0 1 0

Pour calculer le module du gradient, au lieu de l'operateur classique :

(

r

utilise l'operateur : @ @x [email protected] @ @ qui permet de corriger l'anisotropie relativement importante @ @x @y @x @y des ltres de Deriche 6, 7]. Les maxima du module du gradient sont ensuite extraits par un algorithme de suppression des non-maxima 8].

+ ) ( + ) +

@

@

3

@2 @2 @x + @y , nous avons

Pour ameliorer la qualite des resultats nous avons ensuite utilise un certain nombre de rafnements 9], en particulier, un suivi des contours guide par la normale au gradient et associe a un seuillage par hysteresis. Les valeurs de seuils utilisees sont determinees par la fonction de distribution F associee aux valeurs des maxima du module du gradient. Les contours retenus sont ceux qui contiennent des points p qui veri ent :

F (jg(p)j) >

ou est un parametre.

(2)

La gure 9 montre les resultats obtenus par cette methode sur les exemples de la gure 8. Les parametres utilises dans ce cas sont = 0:7 et = 0:8, ce qui correspond a un reglage moyen. La qualite des contours ainsi obtenus ne permet pas d'automatiser l'identi cation et la mesure des di erentes regions osseuses. En particulier, les contours ne sont pas completement fermes et on observe un nombre important de contours parasites. Le rattachement d'un fragment de contour a la region correspondante n'est donc pas toujours evident. Les defauts peuvent ^tre analyses en deux categories : e Le compromis detection-localisation n'admet pas de solution satisfaisante, par exemple : { Les phalanges \absentes" dans la gure 9 n'apparaissent qu'avec un seuil plus bas, ce qui laisse alors passer beaucoup trop de bruit. Pour e acer le bruit, il faut un parametre plus faible, ce qui conduit a des contours trop imprecis. 4

2.2 Analyse des resultats

{ Certaines regions sont trop proches pour que l'on puisse separer leurs contours. On atteint les limites de la methode, lorsque l'attenuation du bruit est insu sante pour les valeurs de qui realisent une bonne separabilite. Avec les ltres de derivee premiere de Deriche, la distance minimale entre deux maxima 0:71. detectables s'exprime en p . Ce terme vaut 2 pour

2 5

D'autres defauts sont inherents a la caracterisation des contours par le gradient, par exemple : { Certaines regions osseuses se touchent ou se chevauchent. La detection et le suivi de contours ne fonctionnent pas correctement au voisinage des jonctions. Pour les images sur lesquelles nous travaillons, les detecteurs bases sur les courbures de l'image 10] sont trop sensibles au bruit pour permettre un bonne localisation. C'est le cas, T par exemple, avec les extrema de l'expression : g? H g?, ou g? designe le vecteur normal au gradient et de m^me intensite. e { Certaines regions ont une forme tridimensionnelle presque polyhedrique ou presentent des discontinuites importantes de la densite osseuse. Par la projection radiographique, ces particularites se traduisent en gradients \interieurs" souvent plus marques et mieux detectes que les contours enveloppes recherches.

2

Conclusions

Si l'on doit utiliser les derivees de l'image, la caracterisation par le gradient reste la methode la plus precise. Une methode multi-resolution, comme celle qui est decrite dans la section 2.3, permet de mieux gerer le compromis detection-localisation. Il faut disposer d'informations supplementaires pour resoudre les ambigu tes. Nous avons explore deux voies. La premiere est l'introduction de connaissances a priori sur la morphologie du squelette de la main qui nous permettent de valider les fragments de contours obtenus par le gradient. La seconde consiste a construire des regions par une methode qui n'utilise pas les derivees de l'image. Les sections 3 et 4 exposent les techniques particulieres developpees dans ce but.

2.3 Calcul des contours par le gradient multi-resolution

La methode de calcul des contours que nous avons decrite dans la section 2.1 est relativement sensible au choix des parametres et ne permet pas de trouver un bon compromis entre detection et localisation. Une faible valeur du parametre permet de detecter des contours s^rs mais grossiers. Le u bruit est tres bien e ace mais les petites structures sont absentes et les angles sont fortement arrondis. Une valeur plus elevee du parametre permet de detecter les details mais ne permet pas de separer les \vrais" contours de ceux induits par le bruit. Le traitement multi-resolution exploite la coherence des contours lorsque varie. Nous utilisons une suite geometrique d'echelles croissantes : ( i )i ::n , i = : i? avec > 1. La validation des contours a l'echelle n se fait a partir de ceux obtenus pour les echelles precedentes. L'expression de la coherence utilise a la fois l'orientation du vecteur gradient et la localisation des maxima de son module.

=0 1

H 2: c'est une \ampli cation" de la courbure isophote : = ? g? g 3g?

T

j j

5

Cette approche est fondee sur la theorie du \scale-space" qui etablit l'invariance, par changements d'echelle, des principales caracteristiques geometriques di erentielles 11, 12]. La theorie s'applique a des derivees qui sont calculees par convolution avec des derivees de gaussiennes. Il est possible de determiner des ltres recursifs qui realisent une tres bonne approximation de l'operateur gaussien requis 13]. Nous avons prefere conserver les ltres de Deriche utilises en 2.1. Ils ont l'avantage de proposer une expression simple des coe cients et nous conservons ainsi la possibilite d'adapter tres facilement la gamme des echelles utilisees d'une image a l'autre. Rappelons que la \variance" du ltre de Deriche d'ordre 0 et de parametre est egale a = .

2

En notant gi (p) le vecteur gradient au point p a l'echelle i , notre methode peut se formuler comme suit : Soit Ci = f p j @gi p gi (p) = 0 g, l'ensemble des points d'extrema du gradient a l'echelle i . u: Nous notons respectivement cos(u; v) = jujjv j , le cosinus de deux vecteurs u et v et d(p; q), la v distance de deux points p; q. On peut alors de nir recursivement, pour i > 0 :

2 ( )

c Ci =

0

f p 2 Ci j cos(gi (p); gi? (p)) cos g

1 0

C

= C

c Ci est l'ensemble des points pour lesquels la direction du gradient ne \varie pas trop" d'une f echelle a la suivante. Ci est l'ensemble des points maxima dont la localisation ne \varie pas trop"

d'une echelle a la suivante. Les points des Ci sont determines par suppression des non-maxima. Dans la caracterisation f de Ci , nous avons utilise la distance d1 et = 1, ce qui donne l'approximation discrete :

f Ci = f p 2 Ci j 9q 2 Ci? f c Ci = Ci \ Ci

1

^ d(p; q)

g

f Ci = Ci \ D(Ci? )

1

ou, D note la dilatation morphologique par la boule de rayon 1 pour d1 . L'ensemble des points coherents a l'echelle n est nalement de ni comme :

f p 2 Cn j jgn (p)j > g

(3)

Les contours retenus sont ceux qui contiennent ces points coherents. Remarquons que l'on retrouve l'expression (2) pour n = 0 et une de nition appropriee de .

2.4 Resultats

Les gures 10 et 11 montrent les resultats obtenus par cette methode sur les exemples de la gure 8. La comparaison avec la gure 9 montre une meilleure detection, on obtient plus de \vrais" contours et moins de parasites. La comparaison entre les gures 10 et 11 montre toutefois les limites de cette methode qui ne fait que repousser le probleme du seuillage. p Les resultats ont ete obtenus pour la serie i = : i? de nie par = p et = 4 2. Les p gures 10 et 11 correspondent respectivement a n = 6, ( = 1) et n = 8, ( = 2). La valeur retenue pour est une valeur moyenne determinee empiriquement pour cette qualite d'images. En s'ecartant de cette valeur, la qualite des resultats se degrade, par exemple, pour = , le rejet du bruit est insu sant et, pour = , des contours sont perdus. La valeur de doit ^tre su sament faible pour assurer une bonne continuite dans la variation d'echelle. e

1 0 1 2 2 6 8 0 0 1 2 0 1 4

6

Un avantage de cette methode est que l'on dispose d'une grande liberte pour xer le seuil . En e et, les contraintes de coherence multi-echelle su sent a ecarter le bruit. Le seuil ne sert alors qu'a ecarter les contours \vrais mais faibles". Il n'est plus necessaire de se baser sur la distribution du module du gradient comme nous l'avons fait pour l'expression (2) en 2.1. Nous avons retenu la valeur cos = 0:9 (soit 25o ). Des valeurs entre 0:8 et 0:95, soit variant de 35o a 15o , donnent les m^mes resultats. Cette grande tolerance de l'algorithme nous e permet d'utiliser sans precaution particuliere les ltres de Deriche dont on connait pourtant le manque de precision pour l'orientation du gradient 7].

3 Utilisation d'un modele geometrique de la main

Nous devons utiliser des informations particulieres pour resoudre les ambigu tes dans l'a ectation des fragments de contours aux di erentes regions osseuses. En e et, les contours obtenus ne sont pas completement fermes et le rattachement d'un fragment de contour n'est pas toujours evident. Les regions connexes ou superposees du carpe constituent la di culte principale. La de nition d'un modele qui s'inspirerait de la croissance physiologique du squelette de la main est delicate. En e et, du point de vue medical, chaque centre d'ossi cation presente une certaine independance de developpement et il n'y a pas d'ordre chronologique general. Nous nous sommes donc orientes vers la de nition d'un modele geometrique robuste et su samment general pour convenir a tous les ^ges. L'absence de modele de croissance du squelette a nous a conduit a une resolution progressive ou chaque os peut ^tre identi e isolement. e Dans un premier temps, il est facile de localiser et d'identi er les os longs, c'est-a-dire, phalanges, metacarpiens, radius et cubitus. La connaissance de la position des os longs nous permet ensuite de calibrer un modele geometrique du carpe. Nous introduisons pour cela la notion de points caracterisants qui nous permettent de quanti er l'appartenance d'un point au contour d'une region osseuse donnee. Inversement, la connaissance de fragments de contours nous permet d'a ner la position des points caracterisants.

3.1 Identi cation des os longs

Lorsque l'on a detecte l'essentiel des contours, par les methodes decrites dans la section 2, la localisation et l'identi cation des os longs se realisent de maniere able et rapide. Ceci se fait par un traitement speci que 14], en deux etapes : 1. On determine les axes des os longs. Une caracterisation directe des points de ces axes, notamment par des proprietes di erentielles, n'est pas possible. Nous procedons par l'appariement de points appartenants respectivement aux contours gauches et droits . Ces points sont caracterises par l'orientation du gradient et le point median de chaque paire est suppose ^tre un point d'axe. Un certain nombre d'heuristiques de croissance, de selection e et de regularisation nous permettent de construire les axes des doigts et des os de l'avant bras. Cette etape est realisee avec des contours obtenus a une echelle relativement grossiere. 2. On detecte ensuite, le long des axes, les points particuliers que sont les extrema de gradient et de courbure. Cette etape est realisee sur des derivees obtenues a une echelle relativement ne. Une analyse syntaxique des sequences de points particuliers nous permet ensuite d'identi er les motifs correspondant aux di erentes articulations.

3

Apres avoir localise et identi e l'ensemble des os longs, nous pouvons considerer, en particulier, ceux qui sont connexes au carpe, c'est-a-dire, les metacarpiens et les extremites des

3: relativement a l'image qui est supposee prealablement orientee \les doigts vers le haut".

7

os de l'avant-bras. Pour chacun de ces os, nous disposons de l'orientation de son axe et de la position des points d'intersection entre son axe et son contour. A partir de ces elements, un certain nombre de constructions geometriques vont nous permettre de quanti er la qualite de l'a ectation des fragments de contours aux di erentes regions osseuses. Par ailleurs, nous esperons pouvoir deduire une estimation de l'^ge osseux a partir des mea sures des os longs. Il sera necessaire d'exploiter une base de reference statistique et la precision sera limitee en raison des faibles dimensions mesurees. Cela nous permettra tout de m^me d'ene visager une adaptation du modele du carpe en fonction de l'^ge. a

3.2 De nition des caracterisants du carpe

Pour preciser cette methode, nous devons introduire quelques de nitions : Pour tout point p du plan, notons Pr (p) l'angle polaire de ce point par rapport a un point de reference Pr . Soit, d'autre part, c(s); s 2 0; 1], une courbe parametree du plan, fermee, ie. c(0) = c(1), et bijective sur 0; 1 .

De nition 1

Nous dirons que le point Pr est caracterisant pour la courbe c si et seulement si la fonction :

CPr (c) : 0; 1] ! 0; 2 s 7! Pr (c(s))

est une bijection sur 0; 1 qui veri e : d(CPr (c)) (s) 6= 0 ds

8s 2 0; 1]

(4)

En supposant une regularite su sante, cette proposition est equivalente a : d(CPr (c)) (s) > 0 8s 2 0; 1]

ds

ou partout d CPr c (s) < 0, si l'on choisit l'autre sens de parametrage. ds

( ( ))

De nition 2

Etant donnes une region R et cR (s) un parametrage de son contour, nous dirons qu'un point P est caracterisant pour la region R si c'est un point caracterisant pour la courbe cR . Remarquons que cela implique certaines conditions a la fois sur la position du point et sur la forme du contour. En particulier, P doit ^tre a l'interieur de la region. e Pour chaque region du carpe, il existe des points caracterisants. En e et, l'os est souvent convexe et alors tout point interieur convient. Dans les autres cas, on observe que le contour est \etoile", il existe alors une partie convexe, interieure a la region, non vide et dont tous les points conviennent. Nous postulons ensuite que, pour tout ensemble R = (Ri )i ::n de n regions du carpe, il est possible de de nir un ensemble P = (Pi )i ::n de n points, tels que : { 8i = 1::n, Pi est caracterisant pour Ri , { 8i; j 2 1::n; i 6= j; Ri \ Rj \ P = ;.

=1 =1

8

Autrement dit, sans ambigu te, chaque point Pi est caracterisant pour \sa" region osseuse Ri . Ceci est e ectivement possible car le recouvrement des regions osseuses reste relativement limite. En premiere approche, nous avons cherche a construire les points caracterisants comme des barycentres des points particuliers que sont les intersections entre les axes et les contours des os longs. Un jeu de coe cients barycentriques convenables, independant de l'^ge, a ete determine a empiriquement 15] pour le jeu d'images de la gure 8. Il appara^t que les coe cients barycentriques sont plus forts pour les points d'intersection proches du carpe que pour ceux situes a l'oppose. Ces derniers ne servent en fait qu'a de nir l'orientation des os longs et la geometrie du carpe semble peu dependante de l'\ouverture" des doigts ou de la rotation du poignet.

Construction des caracterisants

image 2

Fig.

image 4

image 9

3 { Exemples de placement des points caracterisants du carpe

La gure 3 montre l'emplacement des points caracterisants ainsi calcules pour les 3 exemples de la gure 2. Les points resultants ne sont pas toujours parfaitement situes au centre de leur region mais ils satisfont les proprietes enoncees ci-dessus, ce qui nous su ra. Dans un premier temps, l'analyse de chaque region peut ^tre traitee comme un probleme e independant. d d dc Rappelons que : ds CPr (c) = ds Pr (c) = ds :r Pr (c). Si l'on considere que la courbe c(s) est une isophote de l'image, sa tangente est en tout point perpendiculaire au gradient et on dc peut ecrire : ds = (s)g? , ou g? est le vecteur normal au gradient de l'image au point c(s). D'autre part, en notant ?! le vecteur du point caracterisant Pr vers le point c(s), on peut ecrire Pr c ?! r Pr (c) = Prrcj2 . jP c La proposition (4) se traduit donc par :

?

3.3 Utilisation du modele pour la selection des contours

g?:?!? 6= 0 Pr c

8s 2 0; 1]

On considere implicitement que l'image a une regularite su sante. Donc, si Pi est un point caracterisant pour la region Ri , alors la proposition precedente nous dit que les points c(s) du contour de cette region doivent veri er :

?i c g:P!

< 0

8s 2 0; 1]

9

Le choix du signe est dicte par le fait que l'on veut caracteriser le contour d'une region dont l'intensite est plus forte que celle du fond environnant. Remarquons que cette condition est su sante pour rejeter les contours d'une region voisine dont le gradient est de direction opposee. Nous avons alors cherche a de nir, en tout point p, une mesure de la qualite locale du contour d'une region i. Pour ponderer de maniere appropriee l'in uence de la distance au point caracterisant, nous avons envisage des criteres de qualite de la forme : jg(p)j cos(g(p); ?!) Q(i; )(p) = ? Pp

j?i pj P!

i

pour di erentes valeurs de . Pour = 0, le critere de qualite est independant la distance du point caracterisant Pi au point p. Des valeurs negatives de privilegient les contours eloignes, ce qui est a eviter. A quelques exceptions pres, nous pouvons alors de nir, pour chaque point p, un entier K (p) unique, tel que :

Q(K ; )(p) = imax Q(i; )(p) ::n

=1

Cet entier indique la region osseuse au contour de laquelle sera rattache le point considere. Nous postulons que, pour donne : la de nition de K (p) est non ambigue en presque tout point p d'un contour, par continuite de Q, K est constante par morceaux le long d'un contour.

4 5

Nous avons ensuite reutilise les methodes decrites en section 2 en substituant le critere Q(i; ) a jgn j dans l'expression (3). Pour chaque point caracterisant Pi , le contour ci associe est alors obtenu par un seuillage par hysteresis a partir de l'ensemble initial:

f p 2 C j K (p) = i ^ Q(i; )(p) >

ou le parametre

i

i

g

peut ^tre adapte a la geometrie de la region correspondante. e

3.4 Resultats

Nous avons experimente les valeurs = 1; 2 et 3. La gure 14 montre les resultats obtenus par cette methode, pour = 0:7 et = 2, sur les exemples de la gure 8. Sur cette gure, les points de contours p sont colories selon la valeur de K (p), on peut ainsi apprecier la validite des postulats enonces ci-dessus. La comparaison avec la gure 9 montre que l'on parvient a ecarter un certain nombre de contours parasites de forte intensite mais mal orientes. Pour simpli er, les parametres i ont ete choisis tous egaux. Ceci peut expliquer la mauvaise selection du grand os lorsqu'il prend une forme trop allongee. Il est peut ^tre necessaire de e considerer une autre caracterisation pour cet os. Pour = 1, l'attenuation en fonction de la distance est insu sante. Une in uence preponderante du facteur cos(g(p); ?!) rend la methode trop sensible a un bon Pi p placement des points caracterisants et se traduit par des coloriages errones. Pour = 3 ou plus, l'attenuation devient trop forte.

4: Par exemple, pour = ?1, avec les hypotheses \naturelles" (p) 6= 0 sur un contour et Pi 6= Pj , alors ??! Q(i; ?1)(p) = Q(j; ?1)(p) , (p):Pi Pj = 0 , autrement dit, la tangente au contour (isophote) au point p doit ??!. ^tre parallele a Pi Pj e ?j p ? 5: Autre exemple, pour = 0, Q(i; 0)(p) = Q(j; 0)(p) , cos( (p); ?!) = cos( (p); P!), autrement dit, le Pi p point p doit ^tre sur la droite passant par Pi et Pj , avec ces deux points du m^me c^te de p. e e o

g

g

g

g

10

Des contours interieurs, de faible gradient mais proches des points caracterisants, se trouvent alors privilegies. Nous avons nalement retenu la valeur = 2. Les problemes qui subsistent sont : 1. la meilleure de nition des points caracterisants, 2. la fermeture des contours dans les zones ou le gradient est mal de ni. Le premier point est traite ci-dessous. Pour le second point, nous regarderons (en 4) comment des regions construites selon une methode particuliere peuvent ^tre utiles. e Nous n'avons pas experimente de modele geometrique plus sophistique. Dans ce sens, on pourrait, par exemple, envisager d'introduire l'^ge osseux estime lors de l'analyse des axes dans a la de nition des coe cients barycentriques. On peut egalement envisager un modele progressif. Les os pour lesquels la methode est la plus robuste peuvent ^tre utilises pour ameliorer la localisation des autres regions osseuses. e Revenons a la methode detaillee ci-dessus. Elle nous permet de selectionner certains fragments de contour. Il s'agit maintenant de renverser le probleme en de nissant un critere pour la qualite d'un point q comme point determinant de la region i. Etant donne i, on de nit donc : X jg(p)j ! cos(g(p); ? ) qp ? Q(i)(q) =

p2ci

3.5 Utilisation des contours pour une amelioration du modele

! j? j qp

2

ou ci est le contour de la region i, eventuellement fragmente, que l'on a obtenu lors de l'etape precedente. On peut alors rechercher le point P qui maximise ce critere, par exemple, par la technique des gradients conjugues 16]. L'expression du gradient de Q(i) en un point q est en e et relativement simple : ? ! ! X 1 rQ(i)(q) = g(p) ? 3jg(p)j cos(g(p); pq) ? pq

p2ci

! j? j pq

3

! j? j pq

4

On determine ainsi le point le plus caracterisant du contour ci d'une image donnee. L'etape de selection des contours peut ^tre alors reprise avec ce nouveau jeu de points caracterisants. e Finalement, si l'on dispose d'un grand nombre d'images, il est possible de determiner statistiquement de meilleurs coe cients barycentriques pour le calcul des points caracterisants initiaux. Cette etude statistique, peut egalement prendre en compte l'^ge osseux estime sur les os longs. a Sur la gure 14, pour l'image 8 en particulier, on constate que certains fragments de contours contiennent des points trop eloignes. L'in uence d'un point p sur le critere de qualite Q(i)(q) ! est attenuee par le facteur 1=j? j . Il est tout de m^me preferable de limiter l'ensemble ci des pq e points de contours utilises dans la de nition de Q(i). Dans un premier temps, nous avons essaye d'utiliser des masques arbitraires determines comme des polygones dont les sommets sont des points barycentriques 15]. Toute la di culte reside dans la determination empirique de coe cients barycentriques adaptes a la forme des di erents os et a leur variation avec l'^ge. a C'est pourquoi nous avons envisage de construire des regions de maniere automatique, selon la methode decrite dans la section 4.

2

11

4 Calcul des regions

Il s'agit d'obtenir une partition de l'image en un ensemble de regions englobantes. Ces dernieres sont construites de maniere a les faire correspondre une a une a chaque region osseuse. Dans le cas d'une region osseuse isolee, celle-ci sera \recouverte" par la region englobante correspondante. De maniere generale, cet objectif n'est pas realisable. Dans le cas ou plusieurs regions osseuses se superposent, il n'y aura pas de recouvrement parfait. Une region de l'image commune a plusieurs regions osseuses se trouvera alors partagee entre les regions englobantes voisines. Dans un premier temps, nous procedons a la construction de regions elementaires de nies par des seuls criteres de coherence d'intensite. Nous construisons ces regions par une methode qui n'utilise pas les derivees de l'image. Cette approche doit ^tre complementaire des precedentes, e en particulier la ou le gradient n'est pas utilisable. Dans une seconde etape, nous procedons a la fusion des regions elementaires pour obtenir les regions englobantes. Cette fusion est organisee autour des points caracterisants obtenus en section 3.

4.1 Construction de regions homogenes

Ces regions sont caracterisees par les proprietes suivantes : a l'interieur de chaque region, les maxima locaux de l'intensite ont tous la m^me valeur et e forment un ensemble connexe, chaque pixel de la region peut ^tre relie a l'un de ces maxima par un chemin le long duquel e l'intensite est toujours croissante, si l'image est constante sur le voisinage d'un pixel, alors le chemin pour ce pixel passe par le plus proche voisin de valeur strictement superieure. En considerant que les niveaux de gris determinent les altitudes d'un terrain, l'image se decompose ainsi en un certain nombre de reliefs separes par des lignes de vallees. Cette caracterisation presente une certaine similitude avec la de nition des \bassins versants" que l'on trouve dans la methode de segmentation dite de \partage des eaux" 17].

source

Fig.

bassins versants

regions englobantes

4 { Comparaison des deux methodes sur deux exemples synthetiques 12

Pourtant, il faut noter une di erence essentielle, comme l'illustre la gure 4. La methode classique utilise une image d'intensite du gradient et les \lignes de partage des eaux" sont les lignes de contours de l'image. Elles separent des regions de faible gradient qui sont considerees comme relativement homogenes. Notre methode conduit a une segmentation que l'on peut considerer comme duale de la segmentation obtenue par la methode classique. On peut egalement remarquer que la methode classique genere des regions supplementaires qui ne correspondent pas aux regions visuellement perceptibles. Ce sont les bassins associes aux minima de gradient que l'on trouve aux \cols" de l'image source. Notre methode de calcul des regions utilise, comme 17], une liste de tous les pixels de l'image d'origine ranges par intensite decroissante. Les regions en cours de construction sont decrites par une carte, c'est-a-dire une image comme celles de la gure 4, ou chaque region est l'ensemble des pixels ayant une m^me valeur. Une description de l'algorithme est donnee en gure 5. Le e resultat depend naturellement de la distance discrete induite par l'operateur de dilatation D qui est utilise pour de nir la croissance 18]. Soit L, une liste de pixels. Soit R = fRi gi ::n , l'ensemble des regions en cours de construction. trier L ; /* par intensite decroissante */ n 0; R ;; Tant que non vide(L) 1. I intensite(tete(L)) ; ^ 2. L0 ; ; 3. Tant que non vide(L) ^ intensite(tete(L)) = I ^ L0 L0 tete(L) ; L queue(L) ; /* extraction de la liste des pixels d'intensite I */ ^ 4. Croissance parallele des regions avec des pixels de L0 ; /* cf. g. 6 */ 5. Tant que non vide(L0 ) Initialisation d'une nouvelle region avec des pixels de L0 ; /* cf. g. 7 */

=1

Fig.

5 { Algorithme de construction des regions

Il faut eviter que, dans une zone composee de pixels d'intensite constante, la totalite des pixels soit attribuee a une seule region qui se propage depuis un point arbitraire (celui en t^te e de liste, par exemple). L'algorithme de croissance parallele, donne en gure 6, assure le partage de cette zone entre toutes les regions environnantes, chacune s'appropriant la partie qui lui est la plus proche. En fait, a chaque iteration de la boucle principale, on construit localement une carte des regions de Vorono par rapport aux regions existantes. A l'issue de cette operation, il peut subsister des pixels dont l'intensite correspond a cette iteration de la boucle principale mais qui n'ont pas ete rattaches a une region existante. Ils sont alors utilises comme germes de nouvelles regions, selon l'algorithme donne en gure 7.

4.2 Analyse de complexite

Soit N = card(L). C'est aussi le nombre de pixels de l'image et de la carte des regions. 13

Le co^t en memoire est donc en O(N ). u Le co^t en calculs pour le tri initial est en O(NlogN ). u L'algorithme de croissance parallele, cf. g. 6, travaille sur card(L0 ) pixels. La liste L0 est reexaminee tant que l'un de ses pixels peut ^tre rattache a une region Ri . e L'iteration, au cours de laquelle un pixel est rattache, correspond a sa distance a la region correspondante. Dans le cas d'une image \normale", dans laquelle les regions uniformes sont de faible etendue, cette distance peut ^tre majoree par une petite constante. L'algorithme de e 0 )) pixels . croissance examine ainsi O(card(L A chaque examen, il n'est pas necessaire de tester chaque pixel vis-a-vis des n regions existantes. Le test de connexite et le choix de la region connexe se font en O(1) sur la carte des regions. Les regions frontieres @Ri sont codees temporairement comme des regions particulieres et les incrementations Ri Ri @Ri se font en reparcourant la liste des pixels nouvellement connectes, c'est-a-dire en O(card(L0 )). Cela nous donne une complexite en O(card(L0 )) pour l'etape 4. On notera qu'elle est independante de n, le nombre de regions. Sur ce m^me principe, la complexite de l'initialisation d'une region est en O(card(L0 )). Ce e qui donne O( n:card(L0 )) pour l'iteration 5, ou n est le nombre de regions initialisees au cours de cette etape. La complexite d'une iteration de la boucle principale de l'algorithme de construction est ainsi en O( n:card(L0 )), toujours pour une image \normale". La complexite globale \normale" est donc, en O(nN + NlogN ), ou n est le nombre nal de 3 regions. Dans le cas d'une image constante, cette complexite degenere en O(N 2 ).

6 7

Chaque maximum local dans l'image sera le sommet d'une region. Pour limiter le nombre de regions parasites induites par le bruit, nous procedons en preliminaire a un lissage de l'image en encha^nant une erosion morphologique, qui supprime des maxima ponctuels, puis un ltre de Deriche. Comme pour le calcul des contours, le choix du parametre du ltre de Deriche permet d'explorer di erentes formes de compromis entre detection et localisation. Les gures 12 et 13 montrent les resultats obtenus par cette methode sur les exemples de la gure 8. Les resultats ont ete obtenus pour le parametre valant respectivement 0:35 et 0:7. Une faible valeur de permet de detecter des grandes regions. Le bruit est bien e ace mais les petites structures sont absentes et les angles sont fortement arrondis. On observe que certaines des regions obtenues recouvrent plusieurs regions osseuses et que les frontieres ne sont pas toujours bien placees. Une valeur plus elevee du parametre permet d'isoler les petites regions mais ne permet pas de distinguer les \vraies" de celles induites par le bruit ou par des sous-structures. On obtient alors une partition en un grand nombre de regions, chacune etant beaucoup plus petite qu'une region osseuse. Il serait vain de vouloir trouver une valeur de donnant exactement la partition en regions englobantes. Une telle valeur devrait notamment eliminer le bruit a l'interieur de chaque os et garder su samment nettes les vallees entre deux os voisins.

6: Selon l'operateur de dilatation D utilise. 7: Dans le cas ou tous les pixels de L ne constituent qu'une seule region, cette complexite degenere en 3 O(card(L ) 2 ), pour une region en forme de disque, et en O(card(L )2 ), pour une region liforme.

0 0 0

4.3 Application et premiers resultats

14

Un traitement multi-resolution permet d'exploiter la coherence des constructions obtenues pour deux parametres voisins. Nous utilisons pour cela une suite geometrique d'echelles croissantes : ( i )i ::n , i = : i? avec > 1. Soit, pour chaque i 2 0::n], l'ensemble Ri des regions calculees par l'algorithme vu ci-dessus avec un lissage de parametre i . Le probleme va ^tre de fusionner correctement les petites regions de Rn pour obtenir les e regions englobantes. Pour cela, nous procedons a la fusion autour de regions particulieres identi ees a l'aide des points caracterisants P = (Pi )i ::Nc , obtenus comme indique en section 3.

=0 1 =1

4.4 Construction des regions englobantes

Graphe de voisinage multi-resolution

La premiere etape consiste a organiser les informations en un graphe G . Les noeuds de ce graphe sont les regions calculees pour les di erentes valeurs i . Le graphe est ainsi strati e en n + 1 niveaux, le niveau Gi etant compose des regions de Ri . Les ar^tes du graphe G sont de deux types : e Deux regions calculees pour une m^me echelle partagent une ar^te d'adjacence si elles e e ont une frontiere commune. Une ar^te de ce type est non orientee. Elle est etiquetee par un e certain nombre d'informations qui pourront ^tre utilisees lors de la fusion 19] : la longueur de e la frontiere, la distance entre les barycentres des deux regions, . . . Pour chaque niveau i, ces ar^tes de nissent un sous-graphe d'adjacence Gia . e Deux regions r et r0 calculees pour deux echelles consecutives i et i partagent une ar^te de recouvrement si elles ont une intersection non vide. Une ar^te (r; r0 ) de ce type est e e orientee du niveau i vers le niveau i + 1 (r recouvre r0 ). Elle est etiquetee par l'aire de cette intersection, exprimee en nombre de pixels et que l'on notera (r; r0 ). Ces ar^tes de nissent le sous-graphe de recouvrement G r . e

+1

For^t de recouvrement multi-resolution e Pour tout n ud de G , de niveau i > 0, on constate que parmi toutes les ar^tes de recouvree ment incidentes depuis le niveau inferieur i ? 1, il en existe une dont l'etiquette est largement superieure a celle des autres. En d'autres termes, la region de Ri consideree, est \presque" incluse dans une region de Ri? , cela traduit une certaine regularite de l'application i 7! Ri . Pour chaque region r 2 Ri ; i > 0, parmi toutes les ar^tes de recouvrement incidentes sur e b r depuis le niveau i ? 1, on peut ainsi selectionner celle d'etiquette maximale. Soit alors r la b; r) 2 G r et 8r0 2 Ri? j (r0 ; r) 2 G r alors (r0 ; r) (r; r). De b region dont elle est issue, on a : (r

1

maniere generale, on de nit ainsi une fonction de \pseudo-inclusion" :

1

Ri ! Ri? b r 7! r

1

b Les ar^tes de recouvrement (r; r) ainsi selectionnees de nissent une structure de for^t souse e r. jacente au graphe G

Etant donnes les points caracterisants P = (Pi )i ::Nc , on peut associer a chaque region r 2 Ri une etiquette E (r) = fk 2 1::Nc ] j Pk 2 rg. Autrement dit, une region est etiquetee par les point caracterisants qu'elle contient. Notons que, pour chaque niveau i, l'ensemble des etiquettes non vides forment une partition de 1::Nr ]. Le probleme est que l'etiquetage E ainsi obtenu n'est pas consistant dans le sens ou l'etiquette b E (r) d'une region r n'est pas necessairement un sous-ensemble de E (r ). En e et, il ne s'agit que

=1

Etiquetage des regions

15

d'une pseudo-inclusion et un point caracterisant Pk peut ^tre situe dans une region r sans ^tre e e b dans la region r. Il faut donc construire un etiquetage consistant E , de nit par : 8r 2 Rn; E (r) = E (r) 8i < n; 8r 2 Ri; E (r) = E (r0 ) avec l'hypothese initiale que les regions de Rn ne sont etiquetees que par l'ensemble vide ou un singleton de 1::Nc ]. En pratique, cela revient a choisir n su samment grand. Le probleme est de regrouper convenablement des regions d'un m^me niveau, en rattachant e celles qui ne contiennent aucun point caracterisant a celles qui contiennent au moins un de ces points. On introduit pour cela la notion de \region etendue". Une region etendue du niveau i est un sous-ensemble connexe de Ri dont une et une seule e de ses regions veri e E (r) 6= ;. Pour tout niveau i et toute region r 2 Ri , on notera r la region e etendue qui la contient (au sens usuel, ie. r 2 r). Pour chaque niveau i et pour toute region r 2 Ri etiquetee, ie. E (r) 6= ;, on pose provisoie rement r = frg et on va etendre ces regions par double recurrence (sur i et, pour i donne, sur les regions non etiquetees). e On doit egalement construire un nouvel etiquetage E qui, d'une part, sera uniforme sur les regions etendues, c'est-a-dire que : e e e e 8i; 8r; r0 2 Ri; r = r0 , E (r) = E (r0 ) et qui, d'autre part, sera consistant sur les regions etendues, c'est-a-dire qu'il devra veri er : eb e 8i > 0; 8r 2 Ri; E (r ) = E (r0 ) (5) Pour chaque niveau i > 0 et toute region r 2 Ri etiquetee, on commence donc par poser e e E (r) = E (r). En posant provisoirement E (r) = ; pour les autres regions, telles que E (r) = ;, la

b r 2Ri+1 jr =r

0 0

Fusion des regions

e b b r r 2Ri jr =e

0 0

propriete (5) est veri ee puisque par de nition il n'y a qu'une seule region etiquetee par region etendue. Il s'agit ensuite de construire les regions etendues en propageant l'etiquetage, tout en conservant cette propriete. Pour chaque niveau i > 0, cela se fait de maniere iterative en utilisant les regions etendues construites au niveau i ? 1. A chaque iteration, une region initialement non etiquetee est rattachee a une region etendue selon les regles decrites ci-dessous. Finalement, en faisant cro^tre i jusqu'a n, on construira les regions etendues de Rn et l'etiquetage correspondant.

Regles de fusion

Soient une region r 2 Ri non etiquetee, ie. E (r) = ;, et une region r0 2 Ri adjacente, e e ie. (r; r0 ) 2 Gia et etiquetee ou deja rattachee, ie. E (r0 ) 6= ;. Alors, r peut ^tre rattachee a la 0 si les deux regions sont pseudo-incluses dans deux regions de Ri? qui sont region etendue de r regroupees dans une m^me region etendue. e b b r e Cette condition correspond a l'expression e = r0 de la propriete (5). Pour cette region r, on e0 et E (r) = E (r0). Le probleme est qu'il n'y a pas necessairement unicite e e e peut alors poser r = r de r0 . On doit distinguer deux cas : eb 1. E (r0 ) est un singleton. On peut etiqueter, directement et sans ambigu te, toutes les regions e b b r telles que r = r0 . Dans ce cas, on peut donc construire r0 en une seule etape, en evitant une propagation iterative.

1

16

eb 2. E (r0 ) n'est pas un singleton. Pour une region r candidate a un rattachement, il est possible de trouver plusieurs regions r0 satisfaisantes. Les resultats dependent alors de l'ordre dans lequel les regions sont regroupees. e Pour selectionner la \meilleure" paire (r; r0 ), nous n'utilisons pas de critere spectral comme dans les methodes classiques de fusion de regions qui, par exemple, suppriment les frontieres le long desquelles le gradient est minimal. En e et, dans notre cas, le gradient est nul ou tres faible sur les frontieres des regions. Une technique spectrale appropriee serait de supprimer les frontieres le long desquelles la courbure maximale est minimale car les lignes de vallees sont des maxima de cette courbure. Ce critere de regroupement conduit a absorber les vallees les moins signi catives. Malheureusement, cette technique fait intervenir les derivees secondes, ce qui la rend tres sensible au bruit. Finalement, nous avons retenu un certain nombre de criteres spatiaux pour choisir la paire e (r; r0 ), par exemple, minimiser la distance entre barycentres, maximiser la longueur de la frontiere commune, . . . En pratique, entre l'un ou l'autre de ces criteres, il n'y a pas de di erence notable sur la qualite du resultat. Ils ont tous pour m^me e et de favoriser le regroupement en regions \compactes". e

8

La gure 15 montre un exemple des resultats obtenus par cet algorithme de regroupement multi-resolution. Les frontieres des regions nalement obtenues sont tracees en noir et sont superposees aux contours de la gure 14. Nous avons utilise un critere de regroupement base sur la longueur des frontieres, avec les p parametres n = 4, = 4 2, = 0:35 (comme pour la gure 12) et donc n = 0:7 (comme pour les gures 9, 13 et 14). On constate qu'en general les regions obtenues par croissance sont satifaisantes lorsque les contours sont bons, c'est-a-dire lorsque les regions osseuses sont bien separees. Dans le cas contraire, les regions obtenues par croissance ne sont pas des regions englobantes des regions osseuses considerees. Ainsi, il arrive qu'un contour franchisse la frontiere entre deux regions. Dans ce cas, on peut envisager deux modes de correction contradictoires. Soit on preserve le contour, c'est-a-dire que l'on utilise les contours pour contr^ler la fusion des regions. Soit on preserve les regions, o c'est-a-dire que l'on sectionne des contours une fois que les regions sont construites. Sur les exemples, on peut voir que c'est plut^t l'information contours qui doit ^tre privilegiee. o e Autrement dit, ce sont les contours qui sont utiles a la construction des regions alors que les regions ne permettent pas de completer ou de corriger la selection des contours. En particulier, elles ne peuvent donc pas ^tre utilisees dans le processus d'a nage du modele que nous avons e envisage en 3.5.

0

4.5 Resultats

5 Conclusions

Les techniques classiques de segmentation automatique d'images ne donnent pas de bons resultats sur des radiographies de la main. Les variations spatiales de l'intensite et du contraste compliquent le choix des seuils et les textures tres marquees engendrent des contours parasites. Les problemes se posent surtout dans le cas de regions osseuses connexes ou superposees qui creent des ambigu tes aussi bien dans le suivi des contours que dans la fusion de regions.

8: A un coe cient pres, c'est la plus grande valeur propre du hessien H.

17

C'est le cas en particulier pour les radiographies du carpe que nous voulons analyser pour la determination automatique de l'^ge osseux. a Nous nous sommes donc orientes vers la recherche d'une methode particuliere incorporant des connaisances a priori. La de nition d'un modele n'est pas simple en raison de la tres grande variabilite des images dans la position relative des os et dans leur forme. Sur le carpe, nous obtenons de bons resultats avec un modele de contraintes geometriques simple utilise en complement d'une approche contours. Pour cette derniere, la caracterisation par le gradient reste la methode la plus precise. Une analyse multi-resolution permet d'ameliorer la qualite des mesures. Nous avons egalement envisage une approche regions. Il ressort que les resultats obtenus avec les contours sont globalement meilleurs et que l'inter^t complementaire de l'approche par e regions n'est pas clair. En n, il est possible de developper un schema d'a nage du modele geometrique a partir des resultats obtenus par les contours. C'est une voie que nous voulons approfondir.

18

References

1] W.W. Greulich, S.I. Pyle, Radiographic Atlas of Skeletal Development of Hand and Wrist, Stanford University Press, 2nd edition, 1983. 2] J.M. Tanner, R.H. WhiteHouse, N. Cameron, W.A. Marshall, M.J.R. Healy, H. Goldstein, Assessment of Skeletal Maturity and Prediction of Adult Height (TW2), Academic Press, 1983. 3] R. Haralick, Digital step edges from zero crossing of second directional derivatives, IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 6, No 1, 1988, pp. 58-68. 4] R. Deriche, Using Canny's Criteria to Derive an Optimal Edge Detector Recursively Implemented, The International Journal of Computer Vision, Vol. 2, April 1987, pp. 167-187. 5] J.F. Canny, Finding Edges and Lines in Images, Technical report, No 720, MIT, 1983. 6] O.Monga, R. Horaud, Vision par ordinateur - outils fondamentaux, Hermes, 1993. 7] D. Ziou, J.P. Fabre, Rotation Invariance in Edge Detection, in D. Chetverikov, W.G. Kropatsch (Eds.), Computer Analysis of Images and Patterns, Lectures Notes in Computer Science, 719, Springer-Verlag, 1993. 8] J.F. Canny, A Computational Approach to Edge Detection, IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 8, No 6, 1986, pp. 679-698. 9] A. Elkarimi, Applications cliniques des techniques de traitement d'image, Rapport de stage d'option, Ecole Polytechnique, juillet 1993. 10] J.J. Koenderink, W. Richards, Two-Dimensional Curvature Operators, Journal of Optical Society of America, Vol. 5, No 7, 1988, pp. 1136-1141. 11] A.P Witkin, Scale space ltering, Proc. of the International Joint Conference on Arti cial Intelligence, 1983, pp. 1019-1023. 12] L.M.J. Florack, B.M. Ten Haar Romeny, J.J. Koenderink, M.A. Viergener, Scale-space and the di erential structure of images, Image and Vision Computing, No 10, 1992, pp. 376-388. 13] R. Deriche, Recursively implementing the Gaussian and its derivatives, Rapport de Recherche INRIA, No 1893, Avril 1993. 14] P. Chassignet, B. Giai-Checa, A. El Karimi, Contribution a la determination automatique de l'^ge osseux a partir de radiographies de la main, Rapport de Recherche du LIX, a LIX/RR/94/02, Ecole Polytechnique, 1994. 15] F. Fuchs, Analyse structurelle des os du carpe pour la determination de l'^ge osseux, Rapa port de stage d'option, Ecole Polytechnique, juillet 1994. 16] E. Polak, Computational Methods in Optimization, x 2.3, Academic Press, 1971. 17] L. Vincent, Algorithmes morphologiques a base de les d'attente et de lacets : Extension aux graphes, These, Ecole des Mines de Paris, 1990. 18] J.-M. Chassery, A. Montanvert, Geometrie discretre en analyse d'images, Hermes, 1991. 19] J.R. Beveridge, J. Gri th, R.R. Kohler, A.R. Hanson, E.M. Riseman, Segmenting images using localised histograms and region merging, The International Journal of Computer Vision, Vol. 2, 1989, pp. 311-347. 19

1 Introduction 2 Segmentation par les contours

2.1 2.2 2.3 2.4

Table des matieres

Calcul des contours par le gradient . . . . . . . . . . Analyse des resultats . . . . . . . . . . . . . . . . . . Calcul des contours par le gradient multi-resolution . Resultats . . . . . . . . . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . .

2 3

3 4 5 6

3 Utilisation d'un modele geometrique de la main

3.1 3.2 3.3 3.4 3.5 4.1 4.2 4.3 4.4 4.5

Identi cation des os longs . . . . . . . . . . . . . . . . . . De nition des caracterisants du carpe . . . . . . . . . . . Utilisation du modele pour la selection des contours . . . Resultats . . . . . . . . . . . . . . . . . . . . . . . . . . . Utilisation des contours pour une amelioration du modele Construction de regions homogenes . Analyse de complexite . . . . . . Application et premiers resultats . . Construction des regions englobantes Resultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. 7 . 8 . 9 . 10 . 11 . . . . . 12 13 14 15 17

7

4 Calcul des regions

12

5 Conclusions

17

20

Soit L0 , une liste non vide de pixels. Soit R = fRi gi ::n , l'ensemble des regions en cours de construction. Repeter 1. 8i = 1::n; @Ri ; ; /* on initialise la \frontiere" actuelle de chaque region */ 2. L00 ; ; 3. Tant que non vide(L0 ) 3.1. p tete(L0) ; L0 queue(L0 ) ; ^ 3.2. Si 9i j p 2 D(Ri) /* ie. le pixel p est connexe a au moins une region Ri, avec la notation D pour une dilatation morphologique, cf. 2.3 */ alors, soit ^, tel que p 2 D(R ) et choisi arbitrairement, on e ectue @R @R fpg ; sinon L00 L00 p ; 4. 8i = 1::n; Ri Ri @Ri ; /* on incremente chaque region de sa nouvelle \frontiere" */ 5. L0 L00 ; S tant que non vide(L0 ) ^ i ::n @Ri 6= ; ;

=1 ^ ^ ^ =1

Fig.

6 { Algorithme de croissance parallele des regions

Soit L0 , une liste non vide de pixels. Soit R = fRi gi ::n , l'ensemble des regions en cours de construction. n n + 1 ; Rn ftete(L0 )g ; L0 queue(L0 ) ; ^ /* on initialise une nouvelle region */ Repeter 1. @Rn ; ; /* on initialise la \frontiere" actuelle de nouvelle region */ 2. L00 ; ; 3. Tant que non vide(L0 ) 3.1. p tete(L0) ; L0 queue(L0 ) ; ^ 3.2. Si p 2 D(Rn) alors @Rn @Rn fpg ; sinon L00 L00 p ; 4. Rn Rn @Rn ; /* on incremente la nouvelle region */ 5. L0 L00 ; tant que non vide(L0 ) ^ @Rn 6= ; ;

=1

Fig.

7 { Algorithme d'initialisation d'une nouvelle region 21

Table des gures

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Exemples d'ossi cation des doigts en fonction de l'^ge . . . . . . a Exemples d'ossi cation du carpe en fonction de l'^ge . . . . . . . a Exemples de placement des points caracterisants du carpe . . . . Comparaison des deux methodes sur deux exemples synthetiques Algorithme de construction des regions . . . . . . . . . . . . . . . Algorithme de croissance parallele des regions . . . . . . . . . . . Algorithme d'initialisation d'une nouvelle region . . . . . . . . . Exemples d'images radiologiques de la main . . . . . . . . . . . . Contours obtenus par le gradient ( = 0:7) . . . . . . . . . . . . Contours obtenus par le gradient multi-resolution ( = 1) . . . . p Contours obtenus par le gradient multi-resolution ( = 2) . . Regions obtenues par croissance ( = 0:35) . . . . . . . . . . . . Regions obtenues par croissance ( = 0:7) . . . . . . . . . . . . . Selection des contours a l'aide du modele ( = 0:7 et = 2) . . . Comparaison entre contours et regions ( = 0:7) . . . . . . . . .

6 8

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

2 2 9 12 13 21 21 23 24 25 26 27 28 29 30

22

image 1

image 2

image 3

image 4

image 5

image 6

image 7

Fig.

image 8

image 9

8 { Exemples d'images radiologiques de la main

23

image 1

image 2

image 3

image 4

image 5

image 6

image 7

Fig.

image 8

image 9

9 { Contours obtenus par le gradient ( = 0:7)

24

image 1

image 2

image 3

image 4

image 5

image 6

image 7

Fig.

image 8

image 9

6

10 { Contours obtenus par le gradient multi-resolution ( = 1)

25

image 1

image 2

image 3

image 4

image 5

image 6

image 7

Fig.

image 8

image 9

11 { Contours obtenus par le gradient multi-resolution ( = 2)

8

p

26

image 1

image 2

image 3

image 4

image 5

image 6

image 7

Fig.

image 8

image 9

12 { Regions obtenues par croissance ( = 0:35)

27

image 1

image 2

image 3

image 4

image 5

image 6

image 7

Fig.

image 8

image 9

13 { Regions obtenues par croissance ( = 0:7)

28

image 1

image 2

image 3

image 4

image 5

image 6

image 7

Fig.

image 8

image 9

14 { Selection des contours a l'aide du modele ( = 0:7 et = 2)

29

image 1

image 2

image 3

image 4

image 5

image 6

image 7

Fig.

image 8

image 9

15 { Comparaison entre contours et regions ( = 0:7)

30

Information

rapport.dvi

30 pages

Report File (DMCA)

Our content is added by our users. We aim to remove reported files within 1 working day. Please use this link to notify us:

Report this file as copyright or inappropriate

1335832


You might also be interested in

BETA
rapport.dvi