Home

Mode d'emploi

1. a L image originale b L image obtenue par c L image obtenue par l utilisation d un filtre l utilisation d un filtre ouverture fermeture fermeture ouverture Figure 4 4 1 Deux exemples d utilisation des filtres sequentiels Dans les deux exemples nous avons utilis des l ments structurants carr s de dimension 1 58 4 Op rateurs morphologiques de segmentation La segmentation est l une des m thodes de traitement de l image les plus importantes Elle pr pare l image pour son analyse et pour la reconnaissance des objets qu elle contient La segmentation de l image signifie le partage de l image en zones homog nes selon certains crit res Donc c est une op ration indispensable pour la reconnaissance des objets qui composent l image Les crit res voqu s plus haut sont toujours tr s g n raux tels que la variation de luminance l int rieur d une zone ou le contraste fort aux fronti res La segmentation morphologique se propose d aller plus loin dans la reconnaissance en ISOLANT DIRECTEMENT L OBJET QUE L ON VEUT ETUDIER en liminant tout ce qui pourrait g ner la reconnaissance La morphologie math matique permet de faire a en termes g om triques par le choix de la suite des op rateurs que l on appliquera et le r glage des param tres associ s nombres et l ments structurants Parmi les op rateurs de segmentation les op rateurs de squeletisation ont une position
2. 2Y VO Z WY S VO 2 y Oyo oy En m me temps 4 Wo Wo VO WY yo amp Oyo Yo En utilisant les in galit s 3 et 4 on peut crire oY V WO lt OY Donc la quatri me in galit de 1 est prouv e Passons la derni re in galit de 1 V Y OV2ZUY S OY yS YO 2 WY amp yoy y On a finit avec 1 On commence la d monstration de 2 Pour pouvoir affirmer que oy est un filtre il faut montrer que cet op rateur est idempotent oy oY WOW lt OW OY OYOY lt poy OY 5 owoy lt oy Donc En m me temps 6 V V gt OV YY E yS OY 2 yS Woy 2 YY amp oy 2 Y oyoy oy En utilisant les in galit s 5 et 6 on peut crire ovoy oy Donc l op rateur yest idempotent Il d crit alors un filtre On montre maintenant que Vop rateur myo d crit aussi un filtre 55 9 OVO OYO yoyo lt OYO OYOWO lt OYO S OYOOYO lt OY 10 Wo Wo OYd 2 Yo gt yoyo 2 Yo gt OYOYd 2 oyo OYooYd Yd En utilisant les in galit s 9 et 10 on peut crire OYOOYO OY odyo est un op rateur idempotent Il d crit donc un filtre En utilisant la m me m thode de d monstration on peut montrer que l op rateur yoy d crit aussi un filtre On commence la d monstration de 3 Soit f un filtre sup rieur et yo Alors ff f Mais f 2 yo ff fyo ae gt oyo owe Donc f gt yo On a montr ainsi que Ow est le plus petit filtre sup rieur OWv wo S
3. La relation 52 est v rifi e 63 Supposons maintenant que Le Le B x r c Bly r e Prenons le cas pr sent dans la figure 4 1 1 2 B x r B y r e Le Le Figure 4 1 1 2 Exemple de sph res qui v rifient la condition d inclusion B x r Cc Bly r e On constate que la condition d inclusion conduit Le Y X lt ESx2YV ESXxE B y e et la relation 53 est v rifi e Un point x est centre d une boule maximale de rayon r si et seulement si x F et x n appartient pas aucune ouverture de F r alis e l aide d un l ment structurant de type sph rique En effet Parce que x est le centre d une boule maximale de rayon r on peut crire la relation B x r c G ou tenant compte de la relation 51 on peut affirmer que xe F 54 D autre part on pr sente un exemple dans la figure 4 1 1 3 G Ono Figure 4 1 1 3 Un exemple d ensembles G et F 64 On observe que le point x est sur la fronti re de l ensemble F Donc il n appartient pas l int rieur de l ensemble F x F Mais l ouverture est un op rateur anti extensif Donc pour chaque e positif on peut crire F BC cH F le C Fr Voil pourquoi on peut crire ou xe F F ple On peut affirmer que xe N EAE se 55 e gt 0 Si on note avec s l ensemble des centres de boules maximales de rayon r on peut crire sr G N F E ste 56 gt 0 Donc tenant compte de sa d
4. par le cadre de l analyse fonctionnelle Mais pour toutes les cat gories d images est tr s important de d crire la relation g om trique entre les diff rents objets qui composent l image consid r e Cette caract risation g om trique ne peut tre faite dans le cadre de l analyse fonctionnelle On a besoin d une autre th orie Il s agit de la topologie Donc pour pouvoir apprendre la morphologie math matique il faut tudier au commencement la th orie des ensembles l analyse fonctionnelle et la topologie Voil pourquoi on pr sente dans la suite les connaissances n cessaires de ces trois th ories pour l tude de la morphologie math matique 1 2 Quelques l ments utiles de la th orie des ensembles Pour l tude des objets l ments d une certaine image il faut les ordonner Pour introduire une relation d ordre entre les objets de l image il faut que le support de celle ci ait une structure de treillis bool en On d finit dans la suite cette notion A ce but on commence par la d finition du treillis Au commencement on d finit la notion de relation d ordre D finition 1 Une RELATION D ORDRE que l on notera g n riquement lt d finie sur un ensemble E est une relation qui v rifie l x lt x 2 x lt yety lt x gt x y 3 x lt yet y lt z x lt z La premi re est la condition de r flexivit la seconde est la condition d antisymetrie et la troisi me est la condition de transitivit Tout ensem
5. une camera ou d un appareil photographique Cette image est de nature analogique et correspond une distribution d intensit s lumineuses ayant pour support un intervalle de R7 elle est repr sent e par une fonction f La repr sentation num rique de cette image consiste construire partir de f une fonction f4 d finie sur un domaine d nombrable de R dans lequel les l ments de repr sentation sont manipulables ais ment par ordinateur La fonction f est definie partir de f par la relation d int gration suivante Cette formulation est issue du mod le de num risation d fini pour un capteur qui int gre en un point P l information contenue dans un voisinage de P et semble naturelle pour le traitement d images en niveaux de gris Deux l ments sont ind termin s dans la formulation pr c dente d une part la localisation des points P et d autre part la sp cification de leur voisinage Vp Si on se r f re au th or me d chantillonnage la distribution des points P est li e l information variationnelle des valeurs de l image analogique f Cette distribution se caract rise par un crit re de r gularit Par ailleurs tant donn une distribution de points P l ensemble des voisinages Vp que l on veut d finir doit former une partition du support de la fonction image analogique f Si on restreint le nombre de configurations possibles pour les Vp et que l on utilise repetitivement les m mes
6. 36 2 2 1 Propri t s math matiques Gr ce la dualit entre l rosion et la dilatation on peut noncer des propri t s correspondantes aux propri t s pr sent es dans 2 1 1 pour la dilatation Dans Pre 86 on trouve la d monstration de la propri t suivante P1 1 et sont stables pour la dilatation i e V ge d VEe Ve sf OSE etf Oged 2 La dilatation est une application continue de dans et s c i de dans Une autre propri t de la dilatation est celle de croissance P2 f lt fi fOg lt f Og 25 g lt emfOE lt fO 26 D monstration F a x sup Fly a x fre R fssup O4 EG v e r f f g x Donc FOEXx lt f EXx ce qu il fallait d montrer F B x supf y a y ye R fssupF y E1K y ye R J Donc f ENx lt F g Xx c q f d La relation entre la dilatation et l op rateur fait l objet de la propri t suivante P4 fleasg Eag FER D monstration Soit x un point de R Consid rons que Alors g Ag x g x et fO gAg f Og 37 Parce que dans ce cas fOg lt f Og on a gagi getf O grg f Og lt f Og En m me temps g f g f Og Donc f O grg f ag g a f g et la relation 27 est v rifi e dans ce cas aussi Une autre propri t int ressante de la dilatation est celle qui exprime la relation avec V op ration v P5 FOs s O g Gg 28 D monstratio
7. P Dobrin M Gabbouj Implementation of a Distributed Watershed Algorithm In Mathematical Morphology and its applications to Image Processing Eds Jean Serra et Pierre Soile Kluwer Academic 1994 pp 281 288 Naj Sch 93 L Najman M Schmitt Watershed of a continuous function Signal processing 38 1994 pp 99 112 104 Ogn Kub 95 R L Ogniewicz O Kubler Voronoi Tessellation of Points with Integer Coordinates Time Efficient Implementation and Online Edge List Generation Pattern Recognition vol 28 no 12 pp 1839 1844 1995 Orb Ben Nor 93 C L Orbert E W Bengtsson B G Nordin Watershed Segmentation of Binary Images using Distance Transformations SPIE vol 1902 Nonlinear Image Processing IV 1993 pp 156 170 Pre 87 F Preteux Description et interpretation des images par la morphologie mathematique Application a l imagerie m dicale Th se de doctorat es sciences math matiques Universit Paris VI 1987 Pre 92 F Preteux On a distance function approach for gray level mathematical morphology In Mathematical Morphology in Image Processing ed E R Dougherty Chapter 10 pp 323 349 Pre 95 F Preteux La morphologie math matique Ses fondements ensembliste topologique probabiliste Cours fournit au d partement Signal et Image INT Evry 1995 Roe 92 J B T M Roendink Mathematical morphology with Noncommutative Symetry Groups In Mathematical Morphology in I
8. amp b lt x gt b Donc en utilisant la relation 33 3 on peut crire 5 b lt x gt e x 5 x gt b La relation 33 4 est prouv e Maintenant montrons que x lt e y 8 x lt y 33 5 Si par la croissance de on peut crire b lt 5 amp 54 8 b lt x Mais gr ce la d finition pr c dente commute avec sup Donc 5 v b 5 b lt x v fb 5 b lt x v S b 5 b lt x lt x On a montr ainsi que 5 b lt x Donc la relation 33 5 est prouv e Finalement il faut montrer que si 5 est croissant et v rifie la relation 31 alors 5 commute avec le sup Soit la famille x Comme 5 est croissant on a slv Xj 2 x pour tout 1 Soit i tel que 8 x v8 x Alors x v lx 33 6 On peut crire 33 8 x lt va x gt xj lt eV B x v 43 ou 33 VX lt e v kx eo Slv x Sv x 33 7 En utilisant les relations 33 6 et 33 7 on peut donc crire slv x valx Donc l op rateur 5 commute avec le sup On dira que 5 et sont OPERATEURS ADJOINTS Le th or me suivant nous montre le lieu privil gi de l op rateur d rosion dans le cadre de la morphologie math matique Th or me Soit un op rateur Il est croissant et v rifie Y U Usi et seulement si est un sup d rosions et on a v be S avec U si xeU 4 x 4W b six Uetx2b 34 P sinon La d monstration de ce th or me peut tre trouv
9. e si elle est la fois major e et minor e autrement dit si A est contenu dans un intervalle ferme a b D finition 6 On appelle RECOUVREMENT OUVERT d un ensemble A de la droite tout recouvrement de A par des ensembles ouverts de R En utilisant les d finitions d ja pr sent es on peut noncer a la fin de ce paragraphe deux th or mes tr s importants de topologie Th or me 1 de Heine Borel Lebesgue De tout recouvrement ouvert d un intervalle ferm born a b on peut extraire un sous recouvrement ouvert fini La preuve est pr sent e dans Cho 92 Th or me 2 de Bolzano Weierstrass Pour tout intervalle ferm born a b tout sous ensemble infini X a un point d accumulation sur a b 1 4 2 Topologie de l espace R D finition 1 Soit i 1 2 n un ouvert de R qui soit ou bien un intervalle ouvert ai bi ou bien l ensemble vide Dans R on appelle PAV OUVERT de bases le sous ensemble 1xX02X de R il est vide si l une des bases est vide lorsqu il n est pas vide son centre est le point de cordonn es 2 aj b Xi 2 L intersection de deux pav s ouverts de bases i est le pav ouvert de base a On d finirait de fa on analogue les pav s ferm s en rempla ant les intervalles ouverts par des intervalles ferm s D finition 2 Dans R on dit qu un ensemble V est voisinage d un point x s il contient un ensemble ouvert contenant x on dit qu un
10. extensivit P7 g 0 gt 0of lt f Og 30 D monstration Prenons le cas d un l ment structurant plan dans ce cas la fonction g x satisfait la 39 condition g 0 gt 0 On peut utiliser la relation 24 DsffKx v f u g x ueK Mais est vident que pour chaque x le sup des fonctions f u pour chaque u appartenant a K est plus grand que la fonction f x v f u f gt f x ueK xX Voila pourquoi on peut crire f x lt f g x Donc l op rateur d addition de Minkovski est extensif Voila pourquoi on peut affirmer que la dilatation est un op rateur extensif 2 2 2 Effets sur les images La dilatation par un disque connecte les objets quand ils sont proches comble les trous troits pr sents dans les objets largit les objets d une taille correspondant au rayon du disque On peut observer un exemple d image et sa dilat e dans la figure 2 2 2 1 a L image initiale s b L effet de la dilatation c L image d erreure Figure 2 2 2 1 L effet de l operateur de dilatation sur les images 40 2 2 3 Dilatations et rosions alg briques Les op rateurs d rosion et de dilatation peuvent tre d finis sur les treillis aussi On obtient ainsi des g n ralisations des notions introduits d j Voil pourquoi on appelle ces op rateurs rosion et dilatation alg briques Dans la suite S sera un treillis complet On appellera op rateur sur un treillis complet 3 toute
11. finition le squelette de G not Sq G vaut Sq G U NE E ee 57 r gt 0e gt 0 Cette formule a t tablie par Lantu joul dans sa th se de doctorat Lan 78 Elle nous permet de calculer le squelette d un ensemble l aide de l rosion pour le calcul du F et de la dilatation pour calculer louverture il faut calculer une rosion et une dilatation 4 1 2 Squelette de l erod On calcule le squelette de l erod d un ensemble en utilisant le squelette de l ensemble Pour le commencement on d montre la relation suivante Le F a G B r 58 o G signifie l erod de taille a de l ensemble G D monstration Feta Gife sib rradec 65 G Br hu B u r e a lastne eje o hu Donc la relation 58 est d montr e Voil pourquoi on peut crire en utilisant la relation 56 B u r a c c Sr Ga N Fa Fes se e gt 0 En m me temps Sr a G N Fa EE e gt 0 On a d montre ainsi que s G s 4 G 59 ou en d autres termes Sq G U s G U Sr1a G U N EF F a p e 60 r gt 0 r gt 0 r gt 0e gt 0 Cette formule s interpr te en disant que le squelette de l erod de taille a est l ensemble des centres des disques maximaux de G de taille au moins a Il n y a aucune formule analogue pour le squelette du dilat de l ouvert ou du ferm 4 1 3 Formules de reconstruction Tout point x de G est inclus dans une boule
12. s de la fermeture 1 2 E E ACA 3 AN B ANB 4 A A Ces propri t s peuvent etre d montr es l aide des propri t s de la fermeture Par exemple b o5 cP coje COX E donc E E ce qu il fallait demontr D finition 8 La fronti re A d un sous ensemble A de E est l ensemble des points x dont tout voisinage V contient au moins un point de A et un point de C A On a donc A ANC A Sur cette formule on voit que la fronti re de tout ensemble est ferm e et que deux ensembles compl mentaires ont m me fronti re Proposition 1 Pour toute partie A de E ona A A A 15 Preuve A ANCIA o l A AnCAb A A Mae CATE A 1 c q f d D finition 9 Soit A un sous ensemble d un espace E On dit que A est PARTOUT DENSE sur E DENSE sur E ou NON DENSE sur E suivant que A E A a son interieur non vide a son interieur vide D finition 10 On dit que l espace E est s parable si celui ci contient un sous ensemble d nombrable partout dense D finition 11 On dit qu un espace E est s par lorsque deux points distincts quelconques de E poss dent deux voisinages disjoints Les espaces les plus utiles sont toujours s pares par exemple la droite R est s par e Dans un espace s par l intersection des voisinages ferm s d un point a est r duite ce point En effet pour tout bza il existe deux ouverts disjoints et contenant respectivement a et b donc C est
13. Cette proc dure permettra d ordonner les points du plateau pour Tf par ajout de niveaux de gris interm diaires Le choix classique est l utilisation de la fonction distance au bord du plateau soit le bord descendant soit le bord montant Le bord descendant resp le bord montant est d fini comme l ensemble des points du plateau qui sont voisins d un point d altitude strictement inf rieure resp strictement sup rieure On peut montrer que la distance au bord descendant ne cr e pas de nouveaux arcs la p e Cette particularit est surtout int ressante si l on cherche a connecter des objets 5 1 2 3 3 Quelques applications de la l p e discr te En utilisant la l p e on peut s parer les objets se recouvrant Observons une image repr sentant un ensemble d objets qui se recouvrent partialement Comment d couper les amas des objets correspondant aux composantes connexes de l image originale pour que chaque composante connexe de l image r sultat corresponde un seul objet Pour cela nous allons d abord transformer l image binaire en une image num rique ou les lignes de cr te sont pr cis ment les s parations d sir es Lorsque l on rode X progressivement avec l l ment structurant unit H carr ou hexagone les diff rents objets ont tendance se s parer au niveau des tranglements L image transform e par les rosions repr sente l inverse de la fonction distance d x C X Les
14. Donc l expression ensembliste de l addition est A K UA 14 keK Chaque l ment appartenant A K a la propri t xe JAk keK Il y a donc un certain k tel que x Ag ou x ke A Voil pourquoi on peut crire A K u dke K u ke A 15 ou A K u dke K u ke A 16 ou A K u ake Kue Ay 17 La relation 15 nous donne l expression de l addition de Minkovski des ensembles A et K L rosion du ensemble A par l l ment structurant K est donn e par la pseudo soustraction de Minkovski des ensembles A et K Par dualit la dilatation du ensemble 31 A par l l ment structurant K est donn e par l addition de Minkovski des ensembles A et K pr sent e dans les relations 16 et 17 Revenant la relation 16 la condition u ke A est quivalente la condition K cA d o K NA Donc la relation 16 devient A K u K NA Cette d finition de la dilatation est favorable pour le calcul de cette op ration On pr sente dans la suite quelques exemples On consid re les m mes exemples pris pour la pseudo soustraction de Minkovski et pour l rosion El A a a K e e avec e lt lt a voir figure 2 1 Si a lt u alors Ku AA Si a2 u alors Ky NA Donc A K a e ate Parce que dans ce cas on a K K on peut dire que l addition de Minkovski des ensembles A et K est l intervalle a e a e L op ration est pr sent e dans la fi
15. alg brique si et seulement si yest anti extensif et idempotent west une fermeture alg brique si et seulement si west extensif et idempotent Dans le treillis II E la dilatation X 8 X et son rosion adjointe X e X n admettent pas d inverse Il n y a donc aucun moyen pour d terminer un l ment X partir de 8 X ou de e X On a seulement S e X lt X lt e 5 x En notant I application identit de II E dans lui m me une autre fa on d exprimer ce r sultat est E lt I lt E En revanche on montrera que 6 et e sont des op rateurs idempotents Proposition Soit Sune dilatation et son rosion adjointe Alors eest une ouverture alg brique appel e OUVERTURE MORPHOLOGIQUE et edest une fermeture alg brique appel e FERMETURE MORPHOLOGIQUE Soit 6 une dilatation sur le treillis bool en usuel L ouverture y e s exprime alors par YX Uk 8x x 50 xeX On peut observer l analogie avec la d finition ensembliste de l ouverture Si Wy est une ouverture alg brique agissant sur un treillis bool en son application duale y x Cly cx est une fermeture 3 4 5 Filtres morphologiques Les filtres morphologiques sont des s quences d op rateurs morphologiques de base qui ont la propri t d idempotence D finition 3 4 5 1 On appelle composition propre l application qui tout op rateur w associe Vop rateur yoy not yy 53 La notion d idempot
16. alors celle ci peut tre d crite par une fonction d finie sur X le support de l image valeurs dans un ensemble Y f X gt fny ns npf Y Dans le cas d ensembles de fonctions on peut parler de treillis aussi Par exemple l ensemble X f X gt Y est ordonn par la relation f lt g e vkeX f x lt g x et constitue un treillis complet ou l inf et le sup sont donn s par les relations f vi f x sup f k V xe X f af f x inf f x V xe X On analyse dans la suite le treillis des fonctions semicontinues sup rieur scs D finition 1 La fonction f d finie sur R valeurs en R est semicontinue sup rieur au point x si et seulement si pour chaque t de R avec f x lt t il y a un voisinage V de x tel que pour chaque y de V t gt f y Exemples El n 1 f x x Figure 1 Le premier example de fonction semicontinue E2 La fonction pr sent e dans la figure 2 Figure 2 Le deuxi me exemple de fonction semicontinue sup rieure On peut donner une d finition pareille pour les fonctions semicontinues inf rieur sci D finition 2 La fonction f d finie sur R valeurs dans R est sci dans le point x de R si et seulement si pour chaque t de R avec t lt f x il y a un voisinage V de x en R tel que pour chaque y de V t lt f y Exemple E3 n 2 La fonction pr sent e dans la figure 3 Figure 3 Un exemple de fonction semicontinue inf rieur On dit que
17. application de S dans lui m me D finissons pr sent les propri t s alg briques que peuvent v rifier les op rateurs D finition Soit S un treillis complet et soit un op rateur de 3 Y est CROISSANT si V x ye 3 x lt y V x lt Hy Y est EXTENSIF resp ANTI EXTENSIF si V x e 3 x lt x resp x gt x Y est IDEMPOTENT si V x 3 P x Y Y x Soit 3 un treillis complet et soit un op rateur croissant sur 9 alors pour toute famille x 7 x 3 ona v Xj gt VY x et P A Xi lt AW x On dit qu un ensemble A c S est ferm pour l op rateur 6 ou 8 FERME si Vxe A O x e A L ensemble des op rateurs croissants sur le treillis 3 est lui m me un treillis pour la relation d ordre lt P o V xe 3 B x lt W x VE x v Ek Si S est le treillis bool en usuel TI R notons T le groupe des translations de R Voici la d finition des op rateurs compatibles avec les translations les t op rateurs qui forment une des classes fondamentales que nous tudierons par la suite Le sup est donn alors par D finition Un op rateur Y sur I E est dit compatible avec la translation ou T op rateur si W X x P X kk V Xe T E Vike E Maintenant on peut introduire les op rateurs d rosion et dilatation alg briques D finition Soit 3 un treillis complet Un op rateur croissant 5 est une dilatation si et seulement si il existe un op rateur v ri
18. ce au th or me 3 4 5 1 on peut affirmer que n mj 1 ets sont des filtres La proposition suivante montre que l on ne doit pas iterer n importe comment ces filtres Proposition 4 4 1 Soit ik Ia des entiers strictement positifs tels que i lt i ip Alors mi ip Mi Mi Mi mis n n n Nn ip i il ip pi Pi Une d monstration pour cette proposition peut tre trouv e dans Sch Mat 94 Les filtres altern s s quentiels sont d finis par les it rations suivantes M m mj _ m 2m Ni nin _j non Rj fr_ jt Si S S 1 S251 57 Nous avons en particulier les relations suivantes Rj iMi et Sj YiN Ces filtres jouissent de tr s nombreuses propri t s Voici quelques relations concernant leurs compositions Pour i lt jJ On peut maintenant se demander ce qui se passe si l on itere les m en ordre d croissant Cela d finit les filtres s quentiels transpos s t t M MM M j_1M R fr ll Le Ta N nyng 14 40 S S8 89 oe S778 Ils ont des propri t s analogues aux filtres altern s s quentiels Si l on veut qu un bon nombre des in galit s entre filtres deviennent des galit s on utilise les filtres altern s s quentiels sym triques 7 mt p _pte went Xot M M M Ri R R Ni NiNi 8 S S Ces quatre filtres ont la propri t M M M Mi M supli j Dans la figure suivante on pr sente deux ae d utilisation des filtres altern s s quentiels
19. cessite la notion d amincissements homotopiques que sera pr sent e dans la suite 5 1 2 1 1 Amincissements Abandonnons la notion d hexagone maximal et tudions les transformations qui liminent tous les points possibles sans briser localement la connexit des objets Consid rons les images digitalis es selon une trame hexagonale Les configurations locales qui ne brisent pas la connexit sont rotation pr s lorsque l on remplace le pixel central par la valeur 0 signifie que le valeur du pixel n a pas d importance L amincissement par L par exemple fonctionne ainsi Pour tous les pixels de l image en parall le mettre 0 tous les pixels qui ont pour voisinage L Tourner L de 60 et recommencer amincir Dans la figure suivante on pr sente un exemple d amincissement 96 b L image obtenue apr s le premier balayage c L image obtenue apr s le deuxieme d L image obtenue apr s les autres balayage quatres balayages e Le contour de l objet initial et son squelette Cette image est obtenue en prenant le compl mentaire de l int rieur de l image present e dans la section c Figure 5 1 2 1 1 1 Un exemple d amincissement Dans l image finale pr sent e dans la figure 5 1 2 1 1 1 e on peut observer qu l int rieur de l objet initial a t obtenue la courbe marqu e par une ligne plus grasse Celle ci est connexe et a une paisseur gale
20. ch i 13 ce qu il fallait d montrer 2 Propri t s de la fermeture D d 9 2 B ACA 3 A A 4 ay os AUB AUB Preuves Grace a la propri t F3 l ensemble vide est un ferm La propri t 1 est donc v rifi e 9 Garce la d finition de la fermeture d finition 6 la fermeture de A contient A Donc AcA La propri t 2 est donc v rifi e Grace au corollaire d ja pr sent parque A est un ensemble ferm on peut crire A A La propri t 3 est v rifi t elle aussi Pour d montrer la quatri me propri t observons que AUBCAUB 6 BCB et que AUB est un ensemble ferm Mais gr ce la d finition 6 le plus petit ensemble ferm contenant AUB est AUB Voil pourquoi on peut crire AUBCAUB R ciproquement si XCY gt XcY ou Y est un ensemble ferm Mais le plus petit ensemble ferm qui contient X est Donc x XcY 14 Soit X l ensemble A ou l ensemble B et Y l ensemble AUB En vertu de la relation pr c dente on peut crire A CAUB et B CAUB d o AUBCAUB 4 Les relations 3 et 4 prouvent la propri t 4 Cette propri t importante s tend videmment toute r union finie Par contre elle ne s tend pas aux r unions infinies cause du fait qu une r union quelconque de ferm s n est pas toujours un ferm On n a pas non plus de relation analogue pour l intersection m me finie 3 Propri t s de l int rieur Elles sont duales aux propri t
21. discret vers les lignes du gradient joignant les points de P f n cessite un Hessien sans valeurs propres nulles Le graphe ligne de partage des eaux ne peut pas avoir de points terminaux Ceci est du au fait que nous avons suppos que le Hessien ait deux valeurs propres non nulles Sans cette hypoth se la ligne de partage des eaux peut pr senter des points terminaux De m me les points triples ne peuvent tre que des maxima r gionaux L encore si on ne suppose pas les deux valeurs propres du Hessien diff rentes les points multiples sont des points critiques puisque par un point non critique passe une seule ligne maximale descendante du gradient Le th or me montre que la ligne de partage des eaux est une notion profond ment globale En effet par tout point non critique passe une seule ligne maximale du gradient Le seul moyen de distinguer une ligne maximale faisant partie de la ligne de partage des eaux d une n en faisant pas partie est d examiner ses extr mit s Il est m me illusoire de trouver un crit re local comme le montre la proposition suivante Proposition 4 3 2 1 Soit a un point du support de f tel que Vf a 0 Soit Va un voisinage d a ne contenant pas de point singulier Soit y la restriction v de la ligne int grale maximale du gradient passant par a Il existe une fonction fg gale f sur v telle que y soit dans la ligne de partage des eaux de fo En d autres termes il n y a pas de caract ri
22. extensivit Si Opn e supp g et g 0 gt 0 la pseudo soustraction de Minkovski est anti extensive 1 e f g lt f D monstration Soit x un point de R Gr ce la relation 7 on peut crire E eXx er EUX Mais est vidente que Auer EU lt f Voil pourquoi on peut affirmer que la relation 12 est v rifi e et que op rateur d rosion est anti extensif lui m me 2 1 2 Effets sur les images L rosion par un disque s pare les objets au niveau de leurs tranglements limine les objets trop troits ne contenant pas le disque r tr cit les objets d une taille correspondante au rayon du disque Figure 2 1 3 L image originale gauche et sa rod e droite obtenue en utilisant un l ment structurant carr 30 2 2 La dilatation L op rateur dual de l op rateur d rosion est l op rateur de dilatation Pour d finir cet op rateur il faut trouver l op ration duale de la pseudo soustraction de Minkovski A ce but on cherche une expression plus simple de la peudo soustraction de Minkovski Cette op ration est definie par A K xeR K cA Pour chaque x de A K ona K CA ou v ke K x keA ou XEA k Donc xe Ax flAk keK keK On peut donc crire A K A 13 ke K Cette nouvelle expression de la pseudo soustraction de Minkovski nous permet de trouver son op ration duale not e par l addition de Minkovski A K A K Ax U Ak UAg keK keK keK
23. initiale Figure 5 1 2 2 Un exemple de squelettisation d une image discr te En analysant la figure 5 1 2 2 on constate que le squelette discret n est pas un ensemble connexe Le squelette continu est toujours connexe Donc le squelette discret d finit g n ralement un ensemble de points non connexe pour un objet connexe Un autre probl me du squelette discret est son paisseur Il y a certains cas d images discr tes qui ont des squelettes d paisseur 2 ou plusieurs pixels Au contraire le squelette d une image analogique a toujours une paisseur d un pixel Finalement on peut montrer que le squelette discret d une image num rique n est pas identique avec la digitalisation du squelette de l image analogique utilis e pour l obtention de l image num rique consid r e Autres questions li es de cette approche discr te du squelette sont pr sent es dans Cha Mon 91 Une autre approche de la digitalisation de l op rateur squelette est bas sur la digitalisation de la formule de Lantu joul Cette formule sa G U NAF te r gt 0e gt 0 a t pr sent e dans le paragraphe 4 1 1 Pour digitaliser cette formule il faut calculer la fonction distance au bord de l objet F et on en soustrait l ouvert par l l ment structurant l mentaire de la trame F le hexagone ou carr selon la trame utilis e Le r sultat est d cevant car il n est pas connexe et ne ressemble pas vraiment a u
24. k le nombre de polygones communs un sommet S conform ment la figure 5 1 S sommet de k polygons Polygone r gulier Figure 5 1 Caract ristique d une tesselle 83 ss eae 27 L angle B en P limit par les deux extr mit s d une m me cot du polygone est B n L angle 0 20 form entre deux cot s adjacents du polygone en S est tel que B 2a 7 d o k polygones se rencontrent en chaque sommet donc k0 27 d o la relation k 2n n 2 k et n devant tre entiers et strictement sup rieurs 2 n gt 2 car il repr sente le nombre des sommets du polygone et k gt 2 car les polygones ne se rencontrent qu en leurs sommets Remarquant que pour n 27 ona 2n n 2 l quation n admet alors que les trois solutions n 3 k 6 les tesselles sont des triangles n 4 k 4 les tesselles sont des carr es n 6 k 3 les tesselles sont des hexagones On obtient ainsi les trois partitions courantes du plan appel es partitions r guli res pr sent es dans la figure 5 2 lt 3 DAAAAA INI AWAY QED DALY Figure 5 2 Pavages par triangles carr es et hexagones 84 Les trames correspondantes dans le plan aux pavages par carr s et par hexagones sont pr sent es dans la figure 5 3 IXI CRT pp Element du maillage Element de la trame a Trame carr e b Trame carr e c Trame hexagonale 4 connexit 8 connexit 6 connexit Figure 5 3 E
25. l ensemble C X On a montr ainsi que toutes les boules de centre z et de rayon d z X sont dans C X Si on prend une boule de centre z et de rayon r tel que r gt min d a 1 alors B z r AX 74 Donc la boule Bl min d est maximale dans C X 1 Nous sommes donc en pr sence d un sous ensemble du squelette de C X qui est g n ralement strictement plus petit En effet les boules maximales qui ne touchent qu une seule composante X sont dans le squelette de C X et non pas dans le Skiz voir figure 4 2 1 b Figure 4 2 1 Diff rence entre le Skiz et le squelette du compl mentaire a Le squelette de C X b Le Skiz de X Dans le cas o les X sont des points le Skiz est appel DIAGRAME DE VORONOI 4 2 1 Le Skiz est un graphe Le Skiz est un graphe sous des hypoth ses bien plus g n rales que celles pour lesquelles le squelette en est un Th or me 4 2 1 Dans le plan soit X JX une union localement finie de i compacts deux a deux disjoints Alors le Skiz de X est un graphe de type fini D monstration Consid rons l ensemble Y dont le compl mentaire est C Y ul B x pe x xe sui 68 75 o Pc x est la fonction distance sur C X donc la distance des points de C X X Cet ensemble est un ouvert C Y ventuellement plus petit que C X Son compl mentaire Y est encore une union localement finie de compacts chacun contenant un X Ainsi le Skiz de Y est gal ce
26. mentaire est ouvert Il r sulte imm diatement des nonc s O O et O trois nonc s F P gt F quivalents aux pr c dents par dualit et concernant les ferm s de E F Toute intersection finie ou non de ferm s est ferm e F Toute r union finie de ferm s est ferm e F L ensemble vide et l ensemble E sont ferm s D finition 3 On appelle VOISINAGE d un point x de E tout sous ensemble de E contenant un ouvert contenant x Voici quelques propri t s essentielles des voisinages V Tout voisinage de x contient x et tout x a au moins un voisinage V Tout ensemble contenant un voisinage de x est un voisinage de x V3 L intersection de deux voisinages de x est un voisinage de x VA Si V est un voisinage de x il existe un sous voisinage W de x c est dire que WCV tel que V soit un voisinage de chaque point de W On d signe par V x l ensemble des voisinages V de x On appelle VOISINAGE D UNE PARTIE A DE E tout sous ensemble de E contenant A D finition 4 On dit qu une partie B de V x constitue UNE BASE DE V x si tout V appartenant a V x contient un l ment W qui appartient a B D finition 5 Soit A une partie de E et soit x un point de E On dit que x est ADHERENT a A si tout voisinage de x contient un point de A On dit que x est POINT D ACCUMULATION de A si tout voisinage de x contient un point de A autre que x On dit que x est POINT ISOL de A s il appartient A mais n en est pas un point d accumu
27. op rations d rosion et l op ration v fait l objet de l nonc suivant P3 f lgevg f g a f g 10 28 D monstration Consid rons par exemple que pour le point x on a a x lt g x Alors gvg eg et fe eve f g 10 1 et f g gt f g grace a la propri t P2 d ou f g A f g f 0 10 2 Tenant compte des relations 10 1 et 10 2 on observe que la relation 10 est v rifi e Si a x gt g x alors EVES et f gvg f g 10 3 Mais f g lt f g grace a la propri t P2 d ou g a f g f g 10 4 Tenant compte des relations 10 3 et 10 4 on constate que la relation 10 est v rifi e dans ce cas aussi Parce que l analyse d j faite est valable pour chaque x de R on peut affirmer que la relation 10 est vraie La propri t suivante pr sente la relation entre la soustraction de Minkovski et l op ration A P4 f lgag 2 g v f g 11 D monstration Soit x un point de R Si a x lt g x alors g Ag x g x et F ensNx 8Xx 11 3 En m me temps f eXx 2 Ff 2 C e VE 8 Xx 8Xx 11 5 Tenant compte des relations 11 3 11 4 et 11 5 on peut crire f erg x f 2Xx s 8 8 Xx Donc dans ce cas la relation 11 est v rifi e aussi Parce que la s lection du point x a t arbitraire on peut affirmer que la relation 11 est v rifi e pour chaque x dans R x 11 4 d o PS Anti
28. privil gi e 4 1 Squelettes Avec le squelette nous abordons des transformations morphologiques plus complexes dans le sens o elles sont compos es de nombreux op rateurs de base Le squelette de l objet G parfois appel AXE MEDIAN peut tre d fini de nombreuses mani res qui d ailleurs ne conduisent pas toujours au m me objet seules des conditions de r gularit des formes feront dispara tre les diff rences Soit B x r la boule ferm e de centre x et de rayon r et B x r la boule ouverte correspondante l int rieur de la boule ferm e B x r Le Definition Soit X un ensemble du plan La boule ouverte B x r resp ferm e B x r est maximale dans X si et seulement si B xr cB x r cx ou Sx x etr r B x r B x 1 cX Definition Le squelette de l ensemble X est le lieu des centres des boules ouverts maximales dans X Prenons deux exemples 59 E1 On cherche le squelette d un carr comme celui ci pr sent dans la figure 4 1 1 Dans ce cas les boules B x r sont des cercles Quelques boules maximales sont pr sent es dans la figure 4 1 2 Le lieu des centres des boules ouverts maximales dans l image consid r e est pr sent dans la figure 4 1 3 Figure 4 1 1 L image traiter Figure 4 1 2 Les centres des cercles pr sent s sont des points qui appartient au squelette du carr Figure 4 1 3 Le squelette de l image pr sent e dans la figure 4 1 1 E2 On cher
29. s 3 1 Le gradient morphologique 3 2 Les filtres de contraste 3 3 L ouverture morphologique 3 4 La fermeture morphologique 3 4 1 Propri t s math matiques 3 4 2 Effets de l ouverture et de la fermeture sur les images 3 4 3 Un exemple d utilisation de l ouverture morphologique 3 4 4 Ouvertures et fermetures alg briques 3 4 5 Filtres morphologiques 3 4 5 1 Filtres altern s s quentiels 4 Op rateurs morphologiques de segmentation 4 1 Squelettes 4 1 1 Formule de Lantu joul 4 1 2 Squelette de l erod 4 1 3 Formule de reconstruction 4 1 4 Propri t s math matiques du squelette 4 2 Squelette par zones d influence 4 2 1 Le Skiz est un graphe 4 3 Ligne de partage des eaux 4 3 1 Approche par immersion 4 3 2 Ligne de partage des eaux d une fonction r guli re 4 3 3 L approche m trique 4 3 3 1 La ligne de partage des eaux est un Skiz 5 Digitalisation des op rateurs morphologiques 5 1 Digitalisation des op rateurs 5 1 1 Digitalisation des op rateurs de base 5 1 2 Digitalisation des op rateurs de segmentation 5 1 2 1 Ce que l on demande d un algorithme digital de squeletisation 5 1 2 1 1 Amincissements 5 1 2 1 2 Algorithmes base de files d attente 5 1 2 2 La digitalisation de SKIZ 5 1 2 2 1 SKIZ et diagramme de Voronoi 5 1 2 3 La digitalisation de la L p e 5 1 2 3 1 Notion de distance topographique 5 1 2 3 2 Le probl me des plateaux 5 1 2 3 3 Quelques appli
30. superieure lorsque l on utilise un l ment structurant plan de type gg Chaque image plusieurs tentes de gris peut 48 tre regard e comme une fonction tridimensionnelle On peut sectionner le graphique de cette fonction par des plans parall les correspondant chaque niveau de gris Chaque tel plan est en fait une image binaire Donc on peut appliquer chaque telle image une ouverture Les r sultats obtenues peuvent tre comme les sections de l ouverture de l image plusieurs tentes de gris C est une m thode de calcul pour le r sultat de l application de n importe quel op rateur morphologique une image plusieurs tentes de gris bas e sur les calculs des r sultats des applications de l op rateur binaire correspondent aux images de section Pour l ouverture on peut crire fe Er 43 o est l indice de la section du niveau de gris La derni re relation signifie que la section de l ouverture morphologique de l image f est identique l ouverture morphologique de l image binaire f la section de l image f L op rateur dual de l ouverture morphologique est la fermeture morphologique 3 4 La fermeture morphologique Parce que l op rateur dual de l rosion est la dilatation et r ciproquement on peut calculer la fermeture de l ensemble X par l l ment structurant B not e par X avec la relation x x B B 44 3 4 1 Propri t s math matiques Ce so
31. x y On constate que lim Fy Parce qu il existe des ouverts G disjoints qui ont des intersections non vides avec les ensembles F gt et des intersections vides avec les ensembles F2 En m me temps on peut crire limF x y 17 En effet soit le compact K tel que Ka x yj Aucun point d abscisse x et d ordonn e y n appartient pas K Donc K O x 0 Kn4 0 y On peut affirmer que K est disjoint de n importe quel l ment de la suite Fn et la valeur de la limite superieure est en effet x y Pour v rifier la convergence d une certaine suite d ensembles on peut utiliser le th or me suivant Th or me 1 La suite F converge vers F dans F T si et seulement si les deux conditions suivantes sont satisfaites 1 Pour chaque x l ment de l ensemble F il existe un seuil nombre naturel N x tel que pour chaque n plus grand que N x dans chaque ensemble F il existe un l ment x qui appartient une suite X convergent vers x 2 Pour chaque sous suite de F Fnk il existe une sous suite Xnk k tel que XpKE Fax et la limite de la Xnx x appartient a F Les conditions 1 et 1 2 et 2 sont quivalentes et correspondent la d finition de la lim lim Maintenant on peut parler de la continuit des fonctions d ensemble Soit O un espace s parable et une application de Q dans F Les l ments de O sont des ensembles Donc est une fonction d ensemble Elle met en cor
32. 2 2 1 2 Figure 5 1 2 2 1 2 Diagramme de Voronoi et triangulation de Delaunay associ e construits partir de germes ponctuels Pour la diagramme de Voronoi on parle de graphe r gulier car chaque sommet de la diagramme poss de un nombre constant de sommets voisins savoir trois voisins sauf dans le cas particulier de germes cocirculaires Tout sommet de la diagramme de Voronoi plus proche du germe P dans l ensemble S appartient une ar te du polygone de Voronoi associ P Le positionnement des germes dans l image d pend dans la pratique du type de probl me r soudre il peut par exemple figurer des villes sur une carte Pour une tude du m canisme de construction du diagramme on peut choisir une r partition al atoire des germes dans le plan C est un sujet de morphologie statistique cette fin on peut utiliser un processus de Poisson homog ne planer qui constitue le moyen le plus simple pour g n rer des points de fa on al atoire Un processus de Poisson est d fini par les deux postulats suivants 1 le nombre d v nements dans une r gion planer A d aire A suit une distribution de Poisson de param tre NA ii tant donn s n v nements x dans une r gion A les x sont un chantillon de la loi uniforme sur A 5 1 2 3 La digitalisation de la L p e Nous supposerons dans cette section que nous travaillons sur une image discr te Ce type d image va nous permettre de d fini
33. 3 Op rateurs morphologiques d riv s L rosion et la dilatation seules ne permettent pas de mettre en vidence des caract ristiques tr s int ressantes des images En utilisant ces deux op rateurs on peut obtenir diff rentes combinaisons qui repr sentent des op rateurs morphologiques d riv s Prenons pour le commencement deux exemples le gradient morphologique et les filtres de contraste 3 1 Le gradient morphologique Le gradient est un op rateur utilis souvent pour le traitement de l image surtout pour l extraction des contours Cet op rateur est definie l aide des d riv es partielles de l image Son module peut tre approxim l aide des op rateurs morphologiques d rosion et de dilatation Soit B r la boule de rayon r et gg r l l ment structurant plan associ au compact B r 0 sur B r g t sur R B r Le module du gradient morphologique est definie par f f lim B r 8B r r 0 2r L expression f gg r f gp nous donne une bande d paisseur 2r centr e sur les contours de l image f Voil pourquoi la d finition pr c dente peut tre utilis e pour l extraction des contours de l image f 3 2 Les filtres de contraste Leur principe est de renforcer le contraste d une image en faisant basculer des pixels de fa on discontinue Formellement soit f une image et f f 2 deux images transform es v rifiant fi lt f lt f Typiquement f sera
34. Figure 11 Le sous graph de la fonction f g On peut remarquer que l aire du SG f g est plus petite que l aire du SG f C est la cause de l rosion de la fonction f l aide de l l ment structurant g Dans la figure 12 sont pr sent s la fonction f et sa rod e Figure 12 La fonction f et sa rod e La relation 3 peut tre pos e dans la forme SGE F x tle R xR SGH Salf x t e R xR v u glu x t lt f u f x t v u t lt f u glu x 4 26 Donc pour chaque u la borne inferieure de la fonction f u g u x est superieure ou gale t Cette borne inferieure qui d pend de u peut tre crite dans la forme Au f u g u x En utilisant cette notation la relation 4 devient SG ff 0 u f gu x e ou en utilisant la d finition du sous graph SGE ff SGhr fu g u x 5 Voila pourquoi on peut crire une nouvelle expression pour op rateur d rosion Eolf Au f u g u x 6 Le cas des l ments structurants plans est tr s important pour le traitement de l image Consid rons comme l ment structurant une fonction de type gx associ e un compact K de R et definie par 0 sixe K gx x sinon L erod e de f par l l ment structurant plan gg est ff 8k Hx Auttu gxu x Mais 0 siu xe K gx u x oo sinon ou 0 siue K gx u x Rise sinon Donc flu siueK Oe A a
35. MORPHOLOGIE MATHEMATIQUE Responsable fran ais Responsable roumain Professeur Fran oise Preteux Professeur Alexandre Isar Lorsqu on veut appliquer la g ometrie et le calcul des sujets de la physique trop compliqu s des objets dont nous ne connaisson pas assez les propri t s pour pouvoir les mesurer on est oblig dans tous ces cas de faire des suppositions toujours contraires a la Nature de d pouiller le sujet de la plupart de ses qualit s d en faire une tre abstrait qui ne ressemble plus 1 tre r el et lorsqu on a beaucoup raisonn et calcul sur les rapports et les propri t s de cet tre abstrait et qu on est arriv une conclusion tout aussi arbitraire on croit avoir trouv quelque chose de r el et on transporte ce r sultat id al dans le sujet r el ce qui produit une infinit de fausses cons quences et d erreurs Buffon Histoire Naturelle Discours d introduction 1752 TABLE DE MATIERES 1 1 Qu est ce que la morphologie math matique 1 2 Quelques l ments utiles de la th orie des ensembles 1 3 Quelques l ments utiles d analyse fonctionnelle 1 4 Quelques l ments utiles de topologie 2 Op rateurs morphologiques de base 2 1 L rosion 2 1 1 Propri t s math matiques 2 1 2 Effets sur les images 2 2 La dilatation 2 2 1 Propri t s math matiques 2 2 2 Effets sur les images 2 2 3 Dilatations et rosions alg briques 3 Op rateurs morphologiques d riv
36. Un exemple o la fonction de distance et la fonction d tanch it se confonde Definition Pour tout point x G on d finit l amont de x Am x z ypc y PG x d x y Paval de x Av x pe v pa x dlx y l ar te de x Ar x Av x U Am x Dans la figure suivante on donne des exemples pour les notions introduites dans la derni re d finition Figure 4 1 4 2 El ments des ensembles Am x Av x et Ar x 69 Ces objets sont des segments ou unions de segments dont quelques propri t s seront pr sent es dans la suite Proposition 4 1 4 2 Soit xe G L amont de x est un unique segment ventuellement r duit au point x L aval de x est compos de un ou plusieurs segments dont l une des extr mit s est x Soit P l ensemble des points de C G qui r alisent la distance de x C G pour tout ye P d x y PG x Alors l aval de x est Ul y ye Px D monstration Soit y un l ment de l ensemble Am x Alors Pcly pg x d x y Pa y mi Bou et pg x min Eku On peut donc crire PG x d x y min d x u ue C G H d x y d x Uo d x y Si les points x y et u sont dispos s comme on peut voir dans la figure 4 1 4 3 on peut crire d x ug d x y dly u pour chaque y situ sur la droite qui passe par les points x et Uo Uo C G y Figure 4 1 4 3 Un exemple Donc la relation Pg ly PG x d x y est satisfaite En cons quence on peut affirm
37. ale du gradient ou simplement ligne maximale du gradient si ve R 216 vF y s Oet ie i UE 69 ds s gt 0 ds s oo ds Nous disons que la ligne maximale est descendante resp ascendante si 16 Ve r s resp LO ve ds ds D apr s les hypoth ses de r gularit faites sur f par tout point x tel que f x 0 il passe une et seulement une ligne maximale descendante Ces lignes maximales relient deux points critiques de f et n ont aucun point critique en leur int rieur Malheureusement une ligne descendante n aboutit pas toujours un minimum r gional Il est donc n cessaire de recoller ces lignes pour aboutir effectivement un minimum r gional Pour cela nous allons munir l ensemble des points singuliers de f d une relation d ordre partiel D finition 4 3 2 2 Soient a et b deux points singuliers de f Nous dirons que b est au dessus d a s il existe une ligne maximale ascendante du gradient d a vers b Cette relation tant antisym trique en prenant la fermeture transitive de cette relation nous obtenons la relation d ordre au dessous Cette relation d ordre permet de distinguer trois sortes de points singuliers les minima r gionaux les points au dessus d un seul minimum les points au dessus de plusieurs minima Ces derniers devraient clairement appartenir une d finition de la ligne de partage des eaux d une image continue d crite par une fonction continue et non par une fonctio
38. amille d l ments structurants utilis s pour le traitement morphologique de l image L effet de l application d un certain op rateur morphologique pour le traitement d une image donn e d pende de l l ment structurant utilis pour le traitement On notera dans la suite l l ment structurant avec K Une op ration souvent utilis e pour la construction des op rateurs morphologiques est la soustraction de Minkovski On appelle le sym trique de l ensemble K K k E R et on le note K l ensemble Kalag R xe K On appelle la diff rence de Minkovski des ensembles A et K et on la note avec A K l ensemble A K ke R K CAfetK f kke K Exemples EL Soit n 1 A a a K avec lt lt a Les ensembles A et K sont pr sent s dans la figure 2 1 he a 0 a Figure 2 1 Les ensembles impliqu s dans l exemple El Si a lt e x alorsK CA Si a2e x alorsK CA Donc A K at e a e E2 Soit n 2 A a a x a a K x e lt lt a Ces ensembles sont pr sent s dans la figure 2 2 19 Figure 2 2 Les ensembles consid r s dans l exemple E2 Si a lt E x alors Ky y CA as e y Si a2e x alors Ky y CA a2et y Donc A K f a e lt x lt a e a e lt y lt a e L ensemble A K est pr sent dans la figure 2 3 ate e Figure 2 3 Le r sultat de l op ration pr sent e dans l exemple 2 20 2 1 L ro
39. ans modifier la ligne de partage des eaux de f Th or me L ensemble des points galed distance de deux minima r gionaux distincts de f est l ensemble des lignes maximales du gradient reliant deux points de P f Il coincide donc avec la ligne de partage des eaux de f Dans la figure 4 3 3 1 1 on pr sente l effet de l application de l op rateur de ligne de partage des eaux sur une image JN i NA LH NY iZ Sea a L image originale b L image de la ligne de partage des eaux de l image originale Figure 4 3 3 1 1 L effet de l application de l op rateur de ligne de partage des eaux une image On peut observer l effet de sur segmentation de l op rateur ligne de partage des eaux 81 5 Digitalisation des op rateurs morphologiques Une cat gorie tr s importante d images est celle des images digitales Ce sont les images trait es par les systemes de transmission num rique On obtient ce genre d images par l chantillonnage des images continues Les images digitales sont des fonctions d finies sur une trame sous ensemble de Z muni de relations de voisinage L image analogique est li e au plan associ un capteur et ce plan est d fini comme tant le plan de projection de la sc ne observ e Cette projection peut s effectuer suivant des faisceaux parall les ou des faisceaux coniques Le cas le plus courant est celui de l image optique fournie dans le plan de focalisation d
40. atical Morphology in Image Processing ed E R Dougherty Chapter 3 pp 93 120 Beu Mey 92 S Beucher F Meyer The Morphological Approach to Segmentation The Watershed Transformation In Mathematical Morphology in Image Processing ed E R Dougherty Chapter 12 pp 433 481 Boi Gei 92 J D Boissonat B Geiger Three Dimensional Reconstruction of Complex Shapes based on the Delaunay Triangulation Rapport de recherche INRIA no 1697 1992 Boi Sha Tag Yoi 95 J D Boissonat M Sharir B Taganski M Yoinec Voronoi Diagrams in Higher Dimensions under Certain Polyhedral Distance Functions Rapport INRIA no 2629 1995 Bre Gil Kir Wer 95 H Breu J Gil D Kirkpatrik M Werman Linear Time Euclidean Distance Transform Algorithms IEEE Transactions on Pattern Analysis and Machine Inteligence vol 17 no 5 May 1995 pp 529 533 Cam Cre Gla Rak 95 F Campillo F Cereu F L Gland R Rakotozofy Particle and Cell Aproximations for Nonlinear Filtering Rapport INRIA no 2567 Juin 1995 Cha Mon 91 J M Chasseray A Montavert G om trie discr te en analyse d images Herm s Paris 1991 Cho 92 G Choquet Cours de topologie Masson 1992 Dob Vic Gab 94 B P Dobrin T Viero M Gabbouj Fast Watershed Algorithms Analysis and Extensions SPIE vol 2180 Nonlinear Image Processing V 1994 pp 209 220 Mog Vic Dob 94 A N Moga T Viero B
41. ble muni d une relation d ordre est dit ordonn Soit X un sous ensemble du ensemble E L l ment m du E est appel MINORANT du X si pour chaque x qui appartient X on a m lt x L l ment M du E est appel MAJORANT du X si pour chaque x qui appartient X ona x lt M L l ment m est la BORNE INFERIEURE de X s il est le plus grand des minorants de X L l ment M est la BORNE SUPERIEURE de X s il est le plus petit des majorants de X L ensemble X poss de un l ment MINIMUM a si et seulement si ae X pour tout xeX on a a lt x L l ment a est dit minimal si et seulement si ae X etpourtoutxe X x gt a Tout l ment minimum est donc minimal la r ciproque tant fausse D finition 2 Un treillis X est un ensemble ordonn o deux l ments x et y pour chaque x et y dans X poss dent en m me temps une borne sup rieure not e xvy et une borne inf rieure not e xAy Chaque l ment d un treillis a les propri t s suivantes 1 1 V ke X XAX XVX x V x ye X xAy yax et xvy yvx 3 Absorption Vik ye X xa xvy xv kay x 4 In galit s de distributivit v y ze X fs VS x V yYAZ us a IV IA PR lt gt lt lt x gt lt CREER lt gt N N a en 7 5 L in galit des modules V x y z X Z gt Xv yaz s lt xv y Az Si les in galit s 1 deviennent des galit s alors le treillis X s appelle treillis distributif 2 D finition 3 Le treillis X est
42. cadre de la premi re approche on positionne les points P avant de d finir leur territoire Les points P sont consid r s comme les germes de cellules que l on fait isotropiquement grossir en parall le Cette strat gie assure l unicit du pavage une fois les germes distribu s dans le plan La propagation est stopp e en chaque point o 1l y a rencontre entre deux cellules ce qui am ne ces lieux de rencontre s tendre progressivement en segments de droite qui d finissent les ar tes des tesselles Vp ces tesselles sont convexes Dans le cas o les germes sont positionn s de mani re r guli re les Vp appartiennent un ensemble fini des formes l mentaires et on peut obtenir des pavages dits r guliers D finition 5 1 Une trame T V E est d finie par la donn e d un ensemble de points V et d un ensemble de relations de voisinage E V x V Deux points p et q de V sont voisins si p q e E D finition 5 2 On appellera voisinage d un point p l ensemble NE p des voisins de p Il y a plusieurs types de voisinages donc plusieurs types de voisins Pour chaque type on trouve un type correspondent de trame Pour viter certains pathologies on supposera que E poss de les propri t s suivantes 1 p q E pour tout pe V 2 p q e ES q p e E Supposons dans un premier temps que l on d sire utiliser le m me polygone pour toute la partition Soit n le nombre de cot s de ce polygone P son centre et
43. cations de la L p e discr te 1 1 Qu est ce que la morphologie math matique La morphologie math matique repr sente l ensemble de r gles math matiques utilis es pour la description des formes Le concept de forme est li troit du concept d image Voil pourquoi est recommand d utiliser la morphologie math matique pour le traitement de l image L interpr tation d une image la reconnaissance de certains objets qui s y trouvent requi rent g n ralement deux tapes la premi re consiste rep rer sur l image les structures int ressantes et les isoler C est ce que l on appelle la SEGMENTATION la seconde QUANTIFIER ces objets en leur associant des valeurs nombres ou symboles en vue de leur classification Magistral labor par le math maticien fran ais G Matheron la morphologie math matique a ses fondements la th orie des ensembles la topologie l analyse fonctionnelle et la th orie des probabilit s Les premiers travaux de Matheron ont analys le cas des images binaires seulement deux niveaux pour chaque l ment d image pixel 1 pour blanc et 0 pour noir Il a introduit quelques op rateurs morphologiques de base l rosion la dilatation la fermeture l ouverture et le squelette Chaque image binaire peut tre regard e comme une fonction f d finie sur un sous ensemble du R le support de l image X valeurs dans l ensemble 0 1 Cette fonction associe chaque l ment d image la
44. ces composants est l int rieur de la courbe discr te l autre est l ext rieur 90 5 1 Digitalisation des op rateurs G n ralement il n est pas possible de passer simplement de la transformation d finie pour les images continues fonctions R gt R un algorithme sur une trame H Le squelette est un bon exemple Ce passage du continu au discret la digitalisation n est pas bien r solu Si nous notons D l op rateur de digitalisation qui partir d un ensemble F du plan ou de l espace associe les points de la trame qu il contient et P l op rateur de plongement qui partir d un ensemble de points de la trame fournit un ensemble continu g n ralement sous forme polygonale une transformation 6 est digitalisable s il existe une transformation Qo travaillant sur les sous ensembles de la trame et v rifiant 9 X D o P X Xe H Les op rateurs tels que la dilatation ou l ouverture sont justiciables de ce proc d Malheureusement cette approche est inop rante pour le squelette 5 1 1 Digitalisation des op rateurs de base On pr sente dans la suite les d finitions pour les op rateurs morphologiques digitaux de base Les images num riques peuvent tre binaires ou a plusieurs niveaux de gris Pour les images num riques binaires l erod de l ensemble discret A par l l ment structurant discret K est la diff rence de Minkovski entre A et K EB A AzK e Z K ca Un exemple
45. chaque minimum fig 4 3 1 1 a Lorsque deux eaux en provenance de minima diff rents se rencontrent on place un barrage de telle sorte que deux eaux diff rents ne se m langent pas fig 4 3 1 1 b La ligne de partage des eaux est constitu e par l ensemble de ces barrages Elle partage l image en diff rentes zones que l on peut consid rer comme les zones d influence ou d attraction des minima r gionaux On appelle ces zones les bassins versants de l image a Altitude h b Altitude h A Figure 4 3 1 1 Construction de ligne de partage des eaux pour une fonction monodimensionelle En dimension un le lieu des barrages se calcule naturellement Ils sont localis s sur les maxima locaux de l image En dimension deux il est beaucoup plus d licat de caract riser ces barrages directement Comme les barrages sont les fronti res des bassins versants ce sont des lignes Ces lignes contiennent bien plus que les maxima locaux 77 Travaillant sur une fonction en escalier le contact entre deux eaux provenant de deux bassins diff rents s effectue sur un plateau On suppose alors que cette rencontre a lieu au milieu de ces plateaux Pour calculer le milieu sur les plateaux on utilisera le squelette par zones d influence Nous avons maintenant toutes les id es pour poser de mani re formelle D finition Soit f R N une fonction en escalier que nous supposerons born e Notons 1 Bin inf f x et h max su
46. che le squelette d un rectangle comme celui ci pr sent dans la figure 4 1 4 60 Figure 4 1 4 L image squeletiser dans l exemple 2 Quelques boules maximales pour cet exemple sont pr sent es dans la figure 4 1 5 Figure 4 1 5 Quelques cercles qui ont les centres sur le squelette du rectangle de la figure 4 1 4 La r union des points pr sent s dans la figure 5 donne le squelette de l ensemble X pr sent dans la figure 4 1 6 Figure 4 1 6 Le squelette de l image pr sent e dans la figure 4 1 4 En utilisant les r sultats obtenus dans ces deux exemples on peut d montrer que l op rateur squelette n est pas semicontinue Consid rons ce but qu on a deux carr s qui tendent l un vers l autre comme on peut voir dans la figure 4 1 7 a Le cas quand les deux carr s se tachent est pr sent dans la figure 4 1 7 b Le rectangle obtenu ainsi est pr sent dans la figure 4 1 7 c Le squelette de deux carr s ne tende pas vers le squelette du rectangle Donc le squelette n est pas un op rateur continu 61 mn mur Aer Sie Figure 4 1 7 Un contre exemple de la semicontinuit e du squelette a deux carr s qui tendent un vers l autre b le cas quand les deux carr s se touchent c le rectangle obtenu ainsi d le squelette de deux carr s e le squelette du rectangle Donc le squelette n est pas un op rateur semicontinue Pour viter ces inconv nients 1l est n cessaire d utiliser
47. complet si 1 L ensemble X est ordonn 2 Pour chaque famille x finie ou pas en X il existe un le plus petit majorant v x nomm sup et not U un le plus grand minorant A x nomm inf et not D finition 4 On appelle compl ment d un l ment x d un treillis X qui contient et U un l ment y de X tel que xAy et xvy U D finition 5 Le treillis X sera nomm e COMPLEMENTE si tous ses l ments poss dent un compl ment D finition 6 Un treillis distributif et complement est appel treillis bool en Exemple L ensemble de parties d un ensemble X II X est un treillis bool en La relation d ordre est dans ce cas la relation d inclusion L l ment sup est dans ce cas l ensemble X et l l ment inf est l ensemble vide L op ration v est la r union des ensembles et l op ration est l intersection des ensembles On peut parler de la dualit des op rations effectu es sur des ensembles L op ration Y est nomm duale de l op ration si et seulement si agit au m me sens que sur les compl mentaires des ensembles pour lesquels est d finie Une description formelle de cette d finition est WY CoPoC Soit par exemple l optration de r union entre les ensembles A et B Alors AYB AUB AY B AUB ANB ANB Donc l op ration duale de la r union est l intersection 1 3 Quelques l ments utiles d analyse fonctionnelle S il s agit d une image P niveaux de gris
48. configurations de base pour recouvrir R on parle de pavage Il s agit par cons quent de d finir ce pavage c est dire l ensemble des points P et des surfaces l mentaires VE qui leur sont associ s Si l on n impose aucune contrainte suppl mentaire les possibilit s de d finition des points P et des voisinages Vp sont infinis Des propri t s concernant les points P et les l ments de surface Vp peuvent tre nonc es caract risant alors diff rentes constructions et limitant leur nombre Elles peuvent porter sur la disposition des points P sur la forme et la r gularit des surfaces Vp sur les propri t s du pavage r sultant Au premier abord deux m thodologies apparaissent pour r soudre ce probl me selon que l on d finira tout d abord la distribution des points P avant que chacun d eux ne s attribue un territoire Vp ou que 82 l on d finisse a priori des mod les l mentaires Vp partir desquels on construit une partition du plan On verra qu une troisi me m thode consiste g n rer les fronti res du pavage Dans le contexte de l analyse d image les pavages qui sont retenus v rifient des propri t s tels que la repetitivit l infini du partitionement les m thodes rejoignent les principes de caract risation et de construction de mosa ques et de fresques o des tesselles de forme complexe peuvent s emboiter l infini sur le plan ou sur la surface d un volume Dans le
49. de S C est la r gion d influence du point consid r Dans le cas de la m trique euclidienne les l ments que l on obtient sont alors des polygones construits partir des m diatrices des segments de droite qui joignent les couples de points de S Pour chaque point P de S galement appel germe la r gion polygonale compos e des points plus proches d un germe que de tous les autres est appel e polygone de Voronoi et not e V P Propri t 1 Dans le cas de la distance euclidienne les polygones de Voronoi sont convexes Un exemple est pr sent dans le figure 5 1 2 2 1 1 1 germe de Voronoi 2 sommet de Voronoi 3 ar te de Voronoi 4 polygone de Voronoi Figure 5 1 2 2 1 1 Illustration des d finitions de polygone de Voronoi et de diagramme de Voronoi D finition Le r seau form des points quidistants 4 deux germes constitue la diagramme de Voronoi de S il est form de sommets points adjacents plus de deux sommets et d ar tes portions de m diatrices 99 Propri t 2 Dans le cas particulier ou il n existe pas de quadruplait de points de S cocirculaires tout sommet de Voronoi est centre d un cercle passant par trois germes et ne contenant aucun autre germe On parle de cercle de Delaunay La triangulation obtenue en joignant les triplets de sommets est appel e triangulation de Delaunay La dualit entre diagramme de Voronoi et triangulation de Delaunay est illustr e la figure 5 1
50. des notions topologiques pour la d finition du squelette 4 1 1 Formule de Lantu joul Nous allons d abord tudier une formule d crivant le squelette au moyen d rosions et de dilatations puis montrer dans quelle mesure il est possible de reconstruire un ensemble a partir de son squelette Soit G un sous ensemble ouvert du plan et notons G G B r et F G B r Alors nous avons les relations BG r cGexeF 51 Bly r e CG amp Bly e C F 52 53 Le Le B x r en B y r e xE B y D monstration u B u r c cle F B x r CG ER E et la relation 51 est d montr e 62 Bly e CF SB y e c Ie B u r c a Pour chaque y et e les points int rieurs de la sph re de centre y et de rayon peuvent tre des centres d une sph re de rayon r contenue dans G Prenons le cas pr sent dans la figure 4 1 1 1 B E r B C r B A r Figure 4 1 1 1 Quelques sph res de rayon r aux centres situ s sur la sph re de centre y et de rayon r Soient les points A E C et D les centres des sph res de rayon r inclues dans G construites aux centres int rieurs la sph re B y e Alors Le B A r U BC r UB D r U BEE r CG Pratiquement la sph re de centre n importe quel point de la superficie de la sph re B y e et de rayon r B s r est inclue dans G Donc LB s r cG Mais la sph re de centre y et rayon r e est inclue dans UB sr Donc S Le B y r e cG c q f d
51. e partition de E en deux parties ferm es non vides 1 4 4 La topologie en TOUT ou RIEN Soit E un espace localement compact s parable Par exemple E peut tre R Soit F l ensemble de ferm s du E et G l ensemble des ouverts du E On partage les l ments du F en ensembles fermes et compactes F on utilise K pour sp cifier le caract re compact de l ensemble consid r Cette partition induit sur F la topologie en tout ou rien D finition 1 On appelle TOPOLOGIE EN TOUT OU RIEN sur F not e T la topologie engendr e par les deux familles F Ke K et GeG Dans Pre 86 est d montr e la proposition suivante Proposition 1 L espace F muni de la topologie T est compact s parable On peut parler de diff rentes propri t s diff rentielles sur les topologies parce qu on peut d finir la convergence dans ce cas D finition 2 Une suite d ensembles F converge vers l ensemble F dans F T si et seulement si les deux conditions suivantes sont satisfaites 1 Si un ouvert G intersecte F il intersecte tous les F sauf un nombre fini d entre eux 2 Si un compact K est disjoint de F il est disjoint de tous les F sauf d un nombre fini d entre eux La condition 1 d finie la convergence inferieure On utilise la notation lim F F La condition 2 d finie la notion de convergence superieure On note lim F F Exemple Soit dans F la suite F definie par vhe N F x 0 Fan 0 y x0 e E 0 y e E
52. e centre P est de rayon R est definie par Bg P R Qid P Q lt R Sur l image de distance puisque chaque point P est porteur de la plus petite distance au fond la boule discr te By P Rp centr e en P de rayon Rp d P F a est incluse dans l ensemble des points objets O conform ment a la figure 5 1 2 1 Figure 5 1 2 1 Images de distances au fond b et de rayons c pour la distance dg de l image initiale a Ainsi O U Ba P R P PeO parce que toute boule centr e en P contient au moins le point P Donc l objet O peut tre reconstruit l aide des boules discr tes associ es la distance consid r e 93 Pe AM O VRE 0 By P Rp c Ba Q Ro Autrement dit tout point retenu est tel que la boule qui lui est associ e n est pas compl tement incluse dans une autre boule ces boules sont alors appel es maximales Puisque tout point non retenu correspond une boule non maximale on a O UBq P Rp Pe AM O L ensemble des centres P des boules retenues compl t des rayons associ s Rp forme l axe m diane AM O le squelette des objets de l image Le squelette de l image de la figure 5 1 2 1 a est pr sent dans la figure 5 1 2 2 b Les boules discr tes associ es aux points de AM O d finissent un recouvrement de l ensemble O il est donc vident que l ensemble AM O assure la reconstruction de O b Le squelette de l objet contenu dans l image initiale a L image
53. e dans Sch Mat 94 Ainsi les rosions permettent elles d engendrer tous les op rateurs croissants l aide du sup On identifie dans la suite le treillis S au treillis bool en T E o E est gal soit R soit Z D crivons les op rateurs de M E I E comme des extensions d applications de E gt I E Un point x de E pris comme un l ment de T E sera toujours not par x Th or me Soit 5 une dilatation de I E L op rateur 5 est enti rement d termin par les dilat s des ensembles x xe E 8 X Ul Xe T E 35 xeX R ciproquement toute fonction 5 E TI E s tend de mani re unique dans une dilatation de II E T E Ainsi par abus de notation la lettre 5 repr sente soit une application de E dans IT E qui s tend dans une dilatation soit une dilatation alg brique de II E II E En morphologie math matique on appelle FONCTION STRUCTURANTE sur E toute application de E sur II E Une fonction structurante sur E peut aussi tre consid r e comme une APPLICATION MULTIVOQUE de E dans E appel e parfois CORRESPONDENCE Th or me Toute t dilatation 5 sur I E est de la forme 5 X X A pour A fix appel ELEMENT STRUCTURANT Son rosion adjointe est e X X A En fait la classe des dilatations 8 II E II E invariantes par translation coincide avec la classe des fonctions X X Apour Ae TII E Les dilatations morphologiques sont donc bien des dilatations alg briques 44
54. e risque d ambigu t savoir que les chemins sont 6 connexes Soit P et Q deux points de l image et soit S un sous ensemble de points contenant P et Q On dit que P et Q sont connect s dans S si et seulement s il existe un chemin connexe inclus dans S reliant P et Q La relation tre connect dans S est une relation d quivalence r flexive sym trique et transitive Les composantes connexes de l image sont gales aux classes d quivalence de cette relation Sur le maillage carr en fonction de la notion de chemin connexe utilis e on d finit des composantes 4 connexes ou 8 connexes conform ment la figure 5 6 a b Figure 5 6 Composants 4 connexe a et 8 connexe b La reconnaissance des composantes connexes dans une image c est dire le m canisme d association entre les points qui appartient une m me composante connexe est appel e tiquetage de composantes connexes Dans la figure 5 7 est pr sent un exemple d tiquetage 0 ooooco Figure 5 I 0 1 1 1 0 0 n oorceo 0 0 S 0 0 0 0 0 0 0 2 2 0 0 0 0 OS D 0 0 Un exemple d tiquetage des composantes 4 connexes Soit S un sous ensemble non vide de points de S est un arc si et seulement si S est connexe et si chacun de ses points except s deux d entre eux poss de exactement deux points adjacents dans S Les deux points d e
55. ence yy y peut se d composer en deux in galit s D finition 3 4 5 2 Soit wun op rateur croissant L op rateur west un sous filtre si py lt y L op rateur yest un sur filtre si py 2 y L op rateur west un filtre si west idempotent yy w Notons qu il n y a aucune raison pour que le sup l inf ou la composition de deux filtres soit un filtre cependant Th or me 3 4 5 1 th or me de composition de filtres Soit det y deux filtres v rifiant y Alors 1 O20 2 OY V YO 2 OWA WO 2 yoy 2 2 OW Wo dwo et Woy sont des filtres 3 ovyo est le plus petit filtre sup rieur a OW v wo et wow le plus grand inf rieur v Wo D monstration On commence avec 1 o 0 gt 06 gt yo amp p gt Wo Mais est croissant gt oo gt oo En utilisant de nouveau l idempotence dep on peut crire 0 oyo Donc la premi re in galit est montr e Y lt gt yy lt yd S y lt Wo par l idempotence de y Donc VSO lt o OV lt OYO lt 0 S 1 EEES On a obtenu ainsi l in galit 1 Mais 2 YO YO WYO lt OYO WO lt OYO On a obtenu ainsi l in galit 2 En utilisant les in galit s 1 et 2 on peut crire ov v Wo lt Oyo Donc la deuxi me in galit de 1 est prouv e 54 La troisi me in galit est vidente parce que la borne inf rieur doit tre plus petite que la borne superieure OV V WO Z OY VO Passons la quatri me in galit de 1 3
56. er que l ensemble Am x est le segment qui commence en x et qui s tend dans la direction oppos e du point u sur la droite 70 qui passe par les points up et x Donc la proposition est vraie On peut raisonner d une mani re similaire pour affirmation li e de l aval La proposition suivante montre comment on peut d finir le squelette au moyen de l amont Proposition 4 1 4 3 L amont d un point x G est un segment x y tel que 1 yeSq G 2 Sq G est l ensemble des points dont l amont est r duit un point D monstration Le Soit xe Get Am x x y x y Les deux boules ouvertes B x PG x et B y pG y sont tangentes car Pcly pcG x d x y Leur point de contact appartient C G Donc toute boule B z contenant Bly pg y inclue en G et tangente au m me point a la propri t PG z PG x d x z avec d x z gt d x y Pour que ze Am x il est n cessaire que Z Y Donc la boule B y pG y est maximale dans G Ainsi ye Sq G et la propri t 1 est d montr e Si Pamont d un point est r duit ce point il est un point du squelette A l inverse l amont du centre d une boule maximale ne peut tre que r duit un point ce qui prouve la deuxi me partie de la proposition En r sum Deux arr ts non identiques sont disjoint ou se coupent en un point x du squelette qui est leur commune extr mit amont En ce qui concerne l aval les choses sont m
57. est pr sent dans la figure 5 1 1 1 O l origine du plan LS SRE rares SES ERS EES NINININI VA NINININI NS NINININI NSI a L ensemble A b L ensemble K c L ensemble Ex A Figure 5 1 1 1 Un exemple d rosion discr te Pour les images num riques plusieurs niveaux de gris on appelle rosion morphologique de la fonction f par l ment structurant ga la pseudo soustraction de Minkovski de f4 par la fonction Eu a fa 84 x inry 219 e y x 91 On peut introduire un op rateur d rosion discret pour la trame carr e et l l ment structurant Carr aussi Le dilat de l ensemble discret A par l ment structurant discret K est donn par l addition de Minkovski des ensembles A et K Dy A A K e Z Ka OA zo En utilisant les m mes ensembles discrets consid r s dans l exemple ant rieur on obtient Vexemple de dilatation pr sent dans la figure 5 1 1 2 10000 Meee AAA RRO L ensemble xa A Figure 5 1 1 2 Un exemple de dilatation discr te Pour les images num riques plusieurs niveaux de gris la dilatation est d finie par la relation De fa x Ea 8a Xx sup fa y 84 x y yez L ouverture morphologique de l objet discret A qui fait part d une image num rique binaire l aide de l l ment structurant discret K est d finie par la relation OK A Ag A K K La fermeture morphologique de l objet discret A ap
58. exagones maximaux qui contiennent les points supprim s fournit un ensemble de points align s et d connect s ne formant pas la m diatrice enti re de deux points Un exemple est pr sent dans la figure 5 1 2 1 1 VS NN point extrait XXX OY XX Centres d hexagones maximaux VAV a qui contienent les deux points AAC extraits XX MXR XX O Point appartenant la mediatrice VVVVVY i KARAKANA L Figure 5 1 2 1 1 Un exemple envisageant les diff rences entre la m diatrice d un segment et le lieu des centres des hexagones maximaux qui passent par les extr mit s du segment On peut observer que les centres des hexagones maximaux ne sont pas connexes Le principe pour obtenir des squelettes connexes consiste partir de centres d hexagones maximaux et remonter le long de la fonction distance selon une ligne de plus grande pente pour les connecter En utilisant ce principe pour l image pr sent e dans la figure 5 1 2 1 1 on obtient le squelette pr sent dans la figure 5 1 2 1 2 95 00000 WOOO XXY XXX AAAA ATAT ANA VN YNY YY Figure 5 1 2 1 2 La construction du squelette connexe de l image pr sent e dans la figure 5 1 2 1 1 Le squelette obtenu ainsi peut avoir un paisseur au plus deux pixels r traction de la forme et contenant tous les centres des hexagones maximaux inclus dans la forme Cependant le passage d un ensemble d paisseur deux pixels un ensemble d paisseur un pixel n
59. ext rieur Figure 5 4 Illustration du th or me de Jordan dans R 2 e Pour noncer le th or me de Jordan dans Z il faut d finir quelques notions comme chemin ou arc digital On utilise galement pour parler de points voisins les termes de points adjacents ou points cons cutifs 86 On peut caract riser comme points adjacents au point P les points Q tels que Vpet Vo ont une ar te commune Ainsi sur le maillage triangulaire P poss de trois points adjacents il en poss de quatre sur le maillage carr et six sur le maillage hexagonal On peut relier la notion de cons cutivit la notion de m trique pour obtenir des relations entre points plus larges que celles donn es strictement par le maillage Ces deux notions sont si troitement li es dans l espace discret que l on peut se demander laquelle appara t en premier Maillage carr Tout point P est caract ris par ses coordonn es i j sur le maillage i et j sont des entiers qui permettent aussi l adressage de la matrice de codage de l image Les quatre points adjacents et li s P par le maillage sont galement caract ris s comme tant les points distance 1 de P en prenant pour distance la somme des diff rences des coordonn es des points en abscisse et en ordonn On d finit bien ainsi une m trique que nous appelons d4 par d4 P Q ip ig ip jq Cette distance est appel e en anglais City Block Distance ou Square Distance Les points Q dis
60. f est scs ou sci sur R si et seulement si elle est scs ou sci dans chaque point de R 5 Soit et les espaces de fonctions d finies sur R valeurs dans R semicontinues inf rieur ou sup rieur Une fonction qui est scs ou sci est appel e semicontinue Soit l espace de fonctions semicontinues d finies sur R valeurs dans R Dans Pre 86 est prouv e la lemme suivante Lemme 1 Les espaces et ont une structure de treillis Donc on a les propri t s P11 et sont ordonn s par la relation lt d finie par f lt f o V keR x lt f x P12 VE er CPs gt fieb et v fiep ieI iel vE cp Af et v f e VIE cb inf fe iel A chaque fonction scs f on peut associer la r gion situ e sous le graphe de la fonction Cette r gion est appel e sougraphe et est d finie par la relation sa r x t je R xR f x gt t Exemple Soit f la fonction pr sent e dans la figure 1 On pr sente dans la figure 4 l ensemble SG f SG f Figure 4 La fonction f et son sougraphe On peut d montrer la proposition suivante L ensemble SG f est ferm si et seulement si la fonction f est scs A l aide du sougraphe on peut introduire une nouvelle relation d ordre sur le treillis R f lt g SG f cSG g Cette relation d ordre induit elle aussi une structure de treillis sur l espace plus proche de la structure de treillis bool en Les l ments s
61. fiant 41 S x lt yex lt ely VXx yes 31 L op rateur est une rosion donn e par e x vibe 3 amp b lt x 32 De m me soit un op rateur croissant alors est une rosion si et seulement si il existe un op rateur v rifiant la relation 31 L op rateur 6 est alors une dilatation donn e par 8 x Afb e 3 8 b lt x 33 Ainsi les classes de dilatations et d rosions sur 3 forment deux treillis complets isomorphes qui sont duaux pour la bijection definie par la relation 31 D monstration Montrons d abord que la formule 31 implique l unicit de en montrant que ne peut valoir que 8 x v b 5 b lt x Par hypoth se v 5 b lt x b lt e x Donc v b 5 b lt x lt e x On a montr ainsi que 5 x lt e x 33 1 Mais 31 v x e x lt e x x 8 e x P Parce que est un op rateur croissant on peut crire 5 x 28 S elx vib 5 b s tk ou par la croissance de 5 x 2v b b lt e x e x Donc 5 x gt e x 33 2 Grace aux relations 33 1 et 33 2 on peut crire 5 x e x Parce que cette relation est valable pour chaque l ment x on obtient le r sultat o 33 3 42 Donc l op rateur est unique Montrons maintenant l quivalence donn e par la relation 31 Pour le commencement montrons que 8 x lt y gt x lt ely V x ye 3 33 4 Supposons que 5 b lt x Par sa d finition 5 x v b
62. gure 2 2 1 a e A K ate Figure 2 2 1 L addition de Minkovski de l exemple 1 32 E2 A a a x a a K e e xE e lt lt a Si ase x a lt E y alors K x y MAZ Si a2 x a2 y alors K x y NA AP Donc A K A K a e lt x lt a e a e lt y lt a e Cet ensemble est pr sent dans la figure 2 2 2 Figure 2 2 2 L addition de Minkovski de l exemple 2 Dans les figures 1 et 2 on peut observer deux exemples de dilatation parce que dans ces cas K K Ce sont des exemples de traitement des images binaires Dans la suite on pr sente la dilatation des images plusieurs teintes de gris On calcule pour le d but l op rateur dual de l op rateur de pseudo soustraction de Minkovski On sait que f g int F y alx y ye R 33 Mais ax F ek E yya r gt supf y 80 y ly r Donc l addition de Minkovski est donn e par F g x supf y e x y ye R f 19 L rosion morphologique est la pseudo soustraction de Minkovski de la fonction f par g L op rateur dual de l rosion la dilatation est donc l addition de Minkovski de la fonction f par g DDE aNx sup y ax yyeR J e Dans Sch Mat 94 est nonc e une propri t tr s int ressante du sous graph de la dilatation SG D f x sG f SG 21 Celui ci peut tre calcul l aide de l addition de Minkovski des sous graphes des fonctions f et g Donc SG D f
63. ide sont ouverts On dit encore que l ensemble IT E de parties de E d finie sur E une topologie Voici que l ensemble de parties de E IT E est en m me temps un treillis bool en voir l exemple apr s la d finition 6 du paragraphe 2 Mais comme nous l avons d j dit les objets d une image peuvent tre d crits comme des l ments de l ensemble de parties du 10 support de l image Voil pourquoi ont peut consid rer cette collection d objets comme un treillis bool en et en m me temps comme une topologie Le mod le de treillis bool en est utile quand il s agit des transformations de l image bas es sur les op rations bool ennes effectu es sur les objets de l image r union intersection Le mod le topologique est utile quand il s agit des transformations g om triques de l image Les transformations de l image bas es sur les op rations bool ennes sont d crites l aide des op rateurs sur les treillis Il s agit d applications d finies sur les treillis On appelle ces applications des op rateurs parce que les op rations bool ennes sur les l ments du treillis peuvent tre consid r es comme des fonctions Donc l application est d finie sur un espace de fonctions Ces applications transforment les ensembles l ments du treillis en autres ensembles Soit E un treillis complet et soit un op rateur d finit sur E On dit que l op rateur est croissant si Vx yeE x lt y Y x lt Y y On dit que l op
64. ilis comme l ment structurant un triangle Tenant compte de sa d finition ensembliste voir la relation 1 on peut affirmer que l op rateur d rosion peut tre utilis pour le traitement des images binaires 22 Comme nous l avons d j montr dans le paragraphe 3 du premier chapitre pour le traitement des images plusieurs niveaux de gris on utilise l analyse fonctionnelle Parmi les outiles de cette analyse il y a le sous graph Soit f et g deux fonctions d finies sur R semicontinues Leurs pseudo soustraction de Minkovski est not e par f get est la fonction VkeR f x int g x y ye R i On appelle rosion morphologique de la fonction f par l ment structurant g la pseudo soustraction de Minkovski de f par la fonction g o ke R 8 x g x E otf Hx Xx inf y gly x yeR i Calculons le sous graph du E f cle x t E R xR EfXx gt tf Eg f x gt t Donc Mais la relation est quivalente la relation suivante inf f y gly x ly eR b t Donc pour chaque y de R on a f y gly x gt t ou f y gt t g y x 2 Mais g y x repr sente la translat e de la fonction g y avec la quantit x et t g y x est la fonction dont le graphe est obtenu par translation verticale du graphe de la fonction g y x avec la quantit t Soit 8 x t y t g y x La condition 2 est quivalente a la condition SG x aasal Voila pourquoi on peut c
65. la connexit Quand un pixel est limin tous ses voisins dans l objet sont alors mis sur la fille Quand un pixel n est pas limin le remettre sur la fille Le processus s arr te lorsque plus aucun pixel ne peut pas tre limin 98 5 1 2 2 La digitalisation de SKIZ Dans le plan les points quidistants forment la m diatrice du segment form par ces deux points Sur la trame hexagonale munie de sa distance usuelle hexagonale il en va tout autrement les points quidistants de deux pixels sur une m me ligne de la trame s organisent selon un segment ayant chacune de ses deux extr mit s un c ne Ce n est donc pas un ensemble d paisseur unit Les algorithmes par files d attente sont les plus simples pour calculer un SKIZ d paisseur unit ayant la bonne connexit Ils choisissent de mani re arbitraire une ligne dans le c ne que nous avons d crit Si l on veut une ligne mieux centr e l aide d une fonction distance auxiliaire est n cessaire 5 1 2 2 1 SKIZ et diagramme de Voronoi Nous avons montre d j l quivalence entre le SKIZ et la diagramme de Voronoi Dans la suite on pr sentera la diagramme de Voronoi pour les images num riques Soit S P Po P un ensemble de n points du plan analogique R On d sire g n rer une partition du plan pour laquelle chaque l ment est le sous ensemble des points du plan qui sont plus proche d un point de S de tous les autres points
66. lation autrement dit s il existe un voisinage de x qui ne contient aucun autre point de que x D finition 6 On appelle FERMETURE de A le plus petit ensemble ferm de E contenant A Corollaire 1 La relation A A caract rise les ensembles ferm s 2 Pour que A soit ferm il fallait et il suffit qu il contienne ses points d accumulation 12 cfefcia ch La notion duale de celle de fermeture est celle d int rieur D finition 7 On appelle INTERIEUR d un sous ensemble A de E la reunion eventuelement vide de tous les ouverts contenus dans A C est donc le plus grand des ouverts contenus dans A on le note Il est imm diat que la relation A A caract rise les ouverts On pr sente dans la suite quelques relations entre les op rations topologiques A A et les op rations l mentaires 1 Dualit entre fermeture et int rieur 1 clal c 1 Preuve Soit un ouvert contenu dans A Alors apr s la d finition 7 on peut crire A U Oj ou iel o De Morgan CA C Jo Nco iel iel Soit cio On constate que est un ferm Mais c A gt C a gt C A Donc ie1 d signe la famille des ferm s contenant C A Voila pourquoi conform ment la d finition 6 l intersection des f repr sente la fermeture de C A Donc la relation 1 est vraie 2 cfa cia Cette formule se d duit de la pr c dente en y remplacent A par C A En effet cl ctal CICTA A cia
67. lui de X Dans Sch Mat 94 est montr que Sq Y est un graphe de type fini On loigne de ce graphe les ar tes correspondant des boules maximales touchant un seul X Nous obtenons le Skiz de X sous graphe de Sq Y qui reste un graphe de type fini Enfin l une des diff rences majeurs avec le squelette est que le Skiz ne peut pas avoir des points terminaux En effet un point terminal correspondrait a une boule maximale qui ne toucherait qu un seul des X ce qui par d finition du Skiz est impossible On pr sente dans la figure 4 2 1 1 effet de l op rateur Skiz sur une image N A M Figure 4 2 1 1 Traitement par Skiz a L image originale b L effet de la transformation a b 4 3 Ligne de partage des eaux L une des id es pour segmenter les images est de d terminer les lignes le long desquelles les niveaux de gris varient rapidement Ces lignes repr sentent les contours des objets On peut donc les mod liser par les lignes de cr te du module du gradient de l image G ographiquement la notion de ligne de cr te ne semble poser aucun probl me une ligne de cr te est une ligne joignant les points les plus lev s d un terrain C est la ligne de partage des eaux Cependant lorsque l on veut traduire en termes math matiques le concept de ligne de cr te on se rend compte qu il y a plusieurs mani res de le faire maxima locaux du module du gradient dans la direction du gradient z
68. mage Processing ed E R Dougherty Chapter 7 pp 205 254 Rou Pre 91 N Rougon F Preteux Deformable Markers Mathematical morphology for active contour models control SPIE vol 1568 image Algebra and Morphological Image Processing II 1991 pp 78 89 Rus 95 J C Russ Improvments in watershed segmentation with a smoothed Euclidean distance map Journal of computer assisted microscopy vol 7 no 1 1995 Seq Pre 96 R E Sequiera F Preteux Dynamic Algorithm for Constructing Discrete Voronoi Diagrams SPIE Proceedings vol 2662 Nonlinear Image Processing VII 1996 Sch Mat 94 M Schmitt J Mattioli Morphologie math matique Masson Paris 1994 Vim Soi 91 L Vincent P Soille Watersheds in digital spaces an efficient algorithm based on immersion simulatons IEE Transactions on PAMI vol 13 no 6 June 1991 pp 583 598 105
69. minima r gionaux de cette fonction sont les rod s ultimes de X les composantes connexes de X nH qui disparaissent par rosion de taille n 1 La s paration d objets est r alis e l aide de la ligne de partage des eaux En effet la ligne de partage des eaux de la fonction d x C X est une image o toutes les objets de l image X sont s par s La principale application de la l p e est la segmentation Dans la suite on pr sente quelques consid rations sur la segmentation num rique Le premier principe est de construire l image ad quate sur laquelle sera appliqu e la L p e Classiquement elles seront de trois types module de gradient morphologique f H f H ou autre gradient chapeau haut de forme f f permettant de mettre en vidence les structures lin aires claires l image originale 102 Apres on calcule la p e Souvent l effet de cette proc dure est une sur segmentation l image obtenue contienne beaucoup sous regions elle est trop d taill e Il est donc n cessaire de mettre en place des proc dures permettant d liminer certains minima r gionaux Il y a deux variantes de l p e destin es ce but la L p e contrainte par des marquers et la p e contrainte par le contraste Ces op rateurs sont pr sent s dans Sch Mat 94 103 Bibliographie Ast Kos Neu 92 J Astola L Koskonen Y Neuvo Statistical Properties of Discrete Morphological Filters In Mathem
70. n Calculons le sous graph de la fonction f g g 21 21 SG f g g SG f g SG g SG f SG g SG g Calculons le sous graph de la fonction f g g 21 21 SG f g g SG f SG g g SG f SG g SG g Donc SG f g g SG f O g g Voila pourquoi on peut dire que la relation 28 est vraie L rosion a une propri t semblable P6 f g g f g g 29 D monstration On a montr d ja que 38 f g f g 29 1 d ou f g f g Soit h f On obtient h g Ch g 29 2 Prenons le membre droit de la relation 29 En utilisant une relation du type 29 2 on peut crire f g g Cf g g h e g En utilisant la relation 28 on obtient f g g h g g f g g 29 3 Mais tenant compte de la relation 29 2 et la relation 29 3 devient f g g C f g g ou en utilisant une relation de type 29 2 f g g f e e ce qu il fallait d montrer Les propri t s P et Pe nous donnent la possibilit de d composer la dilatation Ainsi on peut calculer la dilatation d une fonction l aide d un l ment structurant compliqu en utilisant les dilatations de cette fonction calcul es avec des l ments structurants plus simples obtenus par la d composition de l l ment structurant original Enfin la derni re propri t int ressante de l op rateur de dilatation est l
71. n en escalier D finition 4 3 2 3 Nous noterons P f le sous ensemble des points singuliers a de f qui sont au dessus de plusieurs minima r gionaux Nous obtenons alors le th or me de convergence suivant qui aurait pu tre la d finition directe de la ligne de partage des eaux d une fonction r guli re Th or me 4 3 2 1 Soit f une fonction C Nous supposerons de plus que f n a que des points singuliers isol s et que en ces points singuliers le Hessien a deux valeurs propres non nulles Approximons f par la suite de fonctions en escalier 79 k o E est la partie enti re E e EO 21 La limite au sens de la topologie en tout ou rien des lignes de partage des eaux de fa est l ensemble des lignes maximales du gradient reliant deux points de P f Sous les hypoth ses du th or me la ligne de partage des eaux est donc un graphe de type fini Les ar tes de ce graphe sont des lignes int grales du gradient reliant soit deux points selles point o le Hessien a deux valeurs propres de signe contraire soit un point selle un maximum local En particulier par tout point de la ligne de partage des eaux sauf pour les points singuliers passe une seule ligne maximale descendante qui se divise au niveau du point selle et non pas deux qui aboutissent deux minima r gionaux distincts Notons que pour d finir P f il suffit de supposer que f a ses points critiques isol s Cependant la convergence de l algorithme
72. n graphe 94 5 1 2 1 Ce que l on demande d un algorithme digital de squelettisation En poussant plus loin le r flexion les choses sont beaucoup moins claires si nous avons une image binaire un ensemble de pixels quel ensemble de pixels constitue le squelette Si on transforme les pixels en un polygone carr ou hexagone par exemple par recouvrement un arc de squelette doit partir de chaque sommet convexe ce qui n est pas acceptable Chercher lisser ce polygone m ne une impasse car il n y a pas de technique universelle de lissage En partant l inverse d une forme dans le plan continu et en prenant les pixels de la trame qu elle contient il n y a pas non plus de solution De nombreuses formes planes donnant naissance aux m mes pixels peuvent avoir des squelettes totalement diff rents du fait de la semi continuit inf rieure Quel squelette alors nous digitaliser Ceci a pouss certains auteurs s engager dans deux voies distinctes refaire la th orie du lieu des centres des boules maximales dans un cadre digital en substituant aux boules des hexagones chercher les transformations d ensembles aboutissant des graphes et pr servant la connexit des objets La notion d hexagones maximaux ne suffit pas fournir un squelette correspondant l intuition En effet si on prend la trame dont on supprime deux points non adjacents situ s sur une m me ligne de la trame l ensemble des h
73. nt des propri t s duales aux propri t s de l ouverture P1 La fermeture est croissante Keysxk ey 45 D monstration xB c Cx YP c Cy 12 X CYSCX5DCY CX p D CY R c q f d C CX lt C CY g e xX c YP 49 P2 La fermeture est extensive xc xB 46 D monstration xB C Cx L ouverture est anti extensive CX z CX e C CX gt C CX KX eX c XP c q f d P3 La fermeture est idempotente BP x 47 D monstration ke clex clcler x p L ouverture est idempotente Donc CX g Jp CX g C CX g C CX g X et C C c cx g clclx x Donc xB F P Se c q f d P4 La fermeture commute avec les translations xB x 8 48 D monstration x c Cx 50 L ouverture commute avec les translations CX g CX Jp C CX g CX pe REX Cata 3 4 2 Effets de l ouverture et de la fermeture sur les images L ouverture par un disque a essentiellement trois effets sur les images binaires filtrage des contours limination des particules trop troites s paration en plusieurs composantes des particules pr sentant un tranglement assez long et troit La fermeture par un disque a sur les images binaires les effets duaux Dans les figures 3 4 2 1 b et 3 4 2 1 c sont pr sent s des exemples d ouverture et de fermeture morphologiques a L image originale E b L image de l ouverture de l image o
74. oins simples Definition On appelle point simple un point dont l aval est r duit un seul segment Les points multiples sont les points dont l aval poss de plusieurs segments L ensemble de points multiples est not D G Ona D G c Sq G 65 71 car si y x est un segment maximal de l aval de x alors ye C G S1 l aval de x est constitu de plusieurs segments le minimum de la distance C G est atteint en plusieurs points ce qui implique que l amont de x est r duit un point donc x est un point du squelette Donc chaque point multiple est un point du squelette et la derni re relation est prouv e Malheureusement tout point du squelette n est pas multiple comme le montre le cas de l extr mit du squelette d une ellipse pr sent dans la figure 4 1 4 4 L aval de point x se r duit ce point Donc x est un point simple Voila pourquoi l ensemble D G n est pas identique au squelette Sq G On peut cependant montrer que les points simples du squelette sont rares parce que D G Sq G Sq G G Figure 4 1 4 4 Un exemple de point dont l aval est r duit un seul point Dans la figure 4 1 4 5 sont pr sent es diff rents points repr sentatifs d un squelette Point triple Point simple Figure 4 1 4 5 Amont aval ar te d un point ainsi que differents points remarquables du squelette 72 Jusqu ici on a tudi seulement des propri t s g om triques du squele
75. oit g un filtre inf rieur dyet y g gg g gg lt gowy ae gt g lt wooy yoy g lt wo Donc woy est le plus grand filtre inf rieur OW v y Si l on consid re la relation d ordre habituelle lt sur l ensemble des filtres la notion de sup est alors definie par Th or me 3 4 5 2 Soit y une famille de filtres Le plus petit filtre sup rieur v y est le plus grand l ment de la classe des transformations croissantes ferm e pour le sup et la composition propre engendr e par les y D monstration Soit f un filtre et a une transformation croissante Alors 56 f2a gt f ff 2fazaa Si f 2a pour une famille de transformations croissantes a on peut crire f2va i Donc le plus petit filtre majorant v y majore la classe ferm e pour le sup et la composition propre engendr e par les w Cette classe a un plus grand l ment son sup qui est croissant Donc 60 lt 6 D autre part cette classe ne contient pas que des sur filtres D o dd p ce qui prouve que est un filtre 3 4 5 1 Filtres altern s s quentiels Leur principe est d iterer des ouvertures et des fermetures de tailles croissantes Soit yi une famille d ouvertures et b une famille de fermetures v rifiant Soit les op rateurs m n r ets d finis comme Mj Yidi jn OI gt QiYiQi ssi VO Vi Comme toute ouverture est plus petite que toute fermeture on peut crire Yi S i Alors gr
76. ontinuit e inf rieur L application G gt Sa G est S C 1 D monstration Soit G une suite d ouverts convergente vers G Montrer la s c i de cette op ration revient montrer que lim inf Sq G gt Sq G Vv Sq G x Sq G x gt x n Nous trouverons en fait une suite x Sq G convergente vers x Soit B x r une boule maximale dans G Notons B Bzr n B CG On a Donc il existe un nombre N tel que B C Gp pour p 2 Na Notons D Bn pour Np Sp lt Ngy Alors Dp C Gp Soit M une boule maximale dans G qui contienne Dy D CM CG En passant la limite pour une sous suite Mp qui converge vers M on peut crire Le B x r C McG Mais la suite M n a pas qu une seule valeur d adh rence donc Mp converge vers B x r Donc M est maximale dans G et vaut B x r On en d duit que Xp le centre du M p converge vers x ce qui ach ve la d monstration Il y a une relation tr s int ressante entre le squelette et la fonction distance 68 Definition On appelle fonction distance sur G la fonction Pg x d x C G minfd x y y C G Cette fonction repr sente donc la plus petite distance entre le point x et un point y d x y qui se trouve dans l ensemble G Definition On appelle fonction d tanch it la restriction de pg Sq G que l on notera encore pg par abus de notation On pr sente un exemple dans la figure 4 1 4 1 Figure 4 1 4 1
77. ouverte de rayon non nul car G est ouvert Il existe donc une boule ouverte maximale qui contient x Donc G Us G B r 61 r gt 0 En d autres termes la connaissance du squelette de G et de la taille des boules maximales 66 permet de reconstruire G Cette formule reste la base d algorithmes de codage de formes binaires Pour la reconstruction de l erod d un ensemble on peut utiliser la formule analogue G Us G B r a 62 r gt a Comme la dilatation commute avec l union on peut aussi reconstruire le dilat et l ouvert d un ensemble en partant de son squelette G eBo Us G soleso TOTON Us o Jobless r gt 0 r gt 0 r gt 0 On a d montr que G B a Js G B r a 63 r gt 0 63 o Gp a G B a Bla G B a Us G B r a r gt 0 Us G B r a Usr a G B r a r gt 0 r gt 0 En utilisant le changement de variable R r a on peut crire GB 1 Usr G B R 64 R gt a La derni re relation repr sente la formule de reconstruction du fermeture de l ensemble G en utilisant le squelette de l ensemble G Notons cependant que les formules de reconstruction n impliquent pas que le squelette du dilat ou de l ouvert se d duise de celui de l ensemble de d part 4 1 4 Propri t s math matiques du squelette On pr sente dans la suite quelques propri t s math matiques de l op rateur morphologique de squeletisation 67 P4 1 4 1 semic
78. p f x 2 f la section inferieure de f au niveau h f x f x lt h 3 Reg_ Min l ensemble des bassins versants de f et l ensemble Xh nax obtenu apr s la r currence suivante O Xh fhmin Gi Xp41 Reg _ Ming 4 f U IZ nt Xp V h hmin Bmax 1 o IZA B est l union des zones d influence de B dans A La ligne de partage des eaux de f est alors le compl mentaire de X mnax figure 4 3 1 2 EE niveau niveau 2 ET niveau 3 SA Reg_ Min Reg_ Min CC Figure 4 3 1 2 Illustration du processus d immersion 4 3 2 Ligne de partage des eaux d une fonction r guli re Supposons que l image f fonction bidimenssionelle cette fois ci est 78 suffisamment r guli re de classe C pour permettre l application d op rateurs diff rentiels Nous allons chercher une caract risation de la ligne de partage des eaux de f en faisant tendre vers 0 la distance entre deux sections inf rieures de f et en passant la limite dans l algorithme de la d finition pr c dente Le gradient Vf est le vecteur plan des d riv es premiers de f et le Hessien Hf est la matrice sym trique des d riv s secondes de f Un point singulier est un point en lequel le gradient de f s annule Vf 0 Nous tudions d abord les lignes int grales du gradient Ce sont les lignes de plus grande pente D finition 4 3 2 1 Un chemin 00 00 gt R de classe Clest appel ligne int grale maxim
79. partenant une image num rique discr te binaire qui utilise l l ment structurant discret K est d finie par la relation Fx A AK A K K En utilisant les m mes moyens de digitalisation on peut parler de chapeau haute de forme discr te ou des filtres morphologiques discrets On pr sente dans la suite les op rateurs morphologiques de segmentation des images num riques 92 5 1 2 Digitalisation des op rateurs de segmentation Une approche digitale directe semble une solution naturelle Le premier op rateur de segmentation qu on a tudi est le squelette l axe m dian La d finition de cet op rateur qu on a donn e dans le paragraphe 4 1 est Le squelette de l ensemble X est le lieu des centres des boules ouvertes maximales dans X Pour digitaliser cet op rateur il faut trouver la signification de la notion de boule maximale pour l espace Ze On consid re une image comprenant un ensemble O des points objets les autres points forment le fond F de l image Tout point d objet peut tre tiquet par la valeur de sa distance au fond c est dire la distance par rapport au point fond qui lui est le plus proche On utilise une distance d de facteur d chelle a Autrement dit les points de F forment l ensemble de points de r f rence n cessaires la construction de l image de distance les points de O qui poss dent un 4 voisin dans F sont affect s la valeur a Une boule discr te By P R d
80. point x est point d accumulation d un ensemble A si dans tout voisinage de x il existe au moins un point de A autre que x Nous pourrions tudier ici en d tail les cons quences de ces d finitions comme nous l avons fait pour R Mais d s maintenant il est plus instructif de faire cette tude dans un cadre plus g n ral Toutefois il sera bon d avoir toujours pr sents l esprit les cas particuliers plus concrets que constituent la droite r elle R les espaces R et leurs sous ensembles 1 4 3 Espaces topologiques Dans l tude l mentaire de R et de R qu on vient de faire presque toutes les notions ont t d finies partir des ouverts et la plupart des propri t s ont t obtenus en n utilisant que les propri t s fondamentales de ces ouverts D o l id e de fonder la topologie sur la notion d ensemble ouvert on va tenter d exprimer toutes les notions topologiques classiques telles que limite et continuit en termes d ouverts et de retrouver le plus possible des th or mes classiques partir de quelques hypoth ses simples sur l ensemble de ces ouverts D finition 1 On appelle ESPACE TOPOLOGIQUE tout couple constitu par un ensemble E et un ensemble II E de parties de E appel es ENSEMBLES OUVERTS ou abr g OUVERTS et satisfaisant aux trois propri t s suivantes O1 Toute r union finie ou non d ouverts est ouverte O2 Toute intersection finie d ouverts est ouverte O3 L ensemble E et l ensemble v
81. q en particulier si p et q sont int rieurs un m me plateau Nous verrons au paragraphe suivant comment traiter ces plateaux Proposition Pour tout p et q on a Ts p q 2 f q f p 74 De plus T p a f a f p si et seulement si il existe un chemin IT P Pi sPn 1 gt 9 tel que pj f j 1 Wj 1 Pj Cout pi_1 pi pour tout i 0 lt i lt n La d finition de la ligne de partage des eaux discr te suit D finition Supposons que f soit minor e Modifions la valeur de tous les minima r gionaux de f en leur imposant la valeur inf f x Le bassin versant associ un minimum r gional M est l ensemble de points x tel que BV M ix v j i Te x M lt Te k M 75 La ligne de partage des eaux discr te est le compl mentaire de l union des bassins versants 101 Notons que par cette d finition la lpe n est g n ralement pas un ensemble de points d paisseur unit En particulier certains bassins versants peuvent se toucher La mise en place d algorithmes r els partira de ces bassins versants pour en d duire une ligne d paisseur unit n cessairement arbitraire qui les s parera 5 1 2 3 2 Le probl me des plateaux Dans la pratique les images poss dent souvent des plateaux points au voisinage desquels la fonction est constante Or la distance topographique ne permet pas de les distinguer Le principe consiste modifier l ordre des niveaux de gris que nous supposerons entiers
82. quelette par zones d influence Consid rons X des ensembles compacts en nombre localement fini Ca veut dire que tout domaine born ne coupe qu un nombre fini des X Soit X UX Le squelette 1 de l ensemble C X motive une nouvelle notion D finition Soit X une population d objets compacts disjoints deux deux La zone d influence iz X associ e X est l ensemble des points plus proches de X que des autres objets iz X kld X lt d x X X 66 Le squelette par zones d influence Skiz est l ensemble des points qui n appartient aucune zone d influence Skiz X C IZ X avec 1Z X iz X 67 1 En d autres termes la boule de centre ze Skiz X et de rayon d z X est maximale dans C X D monstration Soit idz d z X Pour le commencement on prouve que B z d Je C X ze Skiz X ze ZX e zelJiz X e d z X gt d z X X Vie d z xX gt d z x nC x Wi 1 Supposons que ze X Alors d z X 0 et la derni re relation devienne d z X NC X lt 0 C est absurde parce que la distance est une quantit positive On a montr ainsi que le point z du Skiz X ne peut pas tre inclus dans X pour aucun 1 Donc les points du Skiz X n appartiennent pas l ensemble X Donc z Xe ze C X La distance entre le point z et l ensemble X vaut d z X min d z X min d 1 1 Donc les points de la boule de centre z et de rayon min d sont l int rieur de 1
83. r les bassins associ s un minimum r gional de mani re simple Nous noterons par p les points de la trame par N p l ensemble des voisins de p sur la trame et par I p q la distance l mentaire de deux points voisins p et q Cette proc dure permet d appr hender des distances sur la trame qui s approchent aussi pr s que l on veut de la distance euclidienne pourvu que N p consid re des points suffisamment loign s de p 5 1 2 3 1 Notion de distance topographique D finissons pr sent les lignes de plus grande pente d une image digitale f 100 D finition La pente descendante en p not e Desc p est la pente maximale avec laquelle on descend vers un voisin de p Desc p max f p f q I p q q N p 71 On d fini alors un co t de d placement le long de lignes d finies sur l image f par Si f p gt f q Cout p q Desc p Si f p lt f a Cout p q Desc q Si f p f q Cout p q ee Dese q Ainsi la d nivel e associ e un chemin IT Po DED sera donn e par n Ty 11 LP Pi JCout pi_1 pi 72 1 D finition La distance topographique Tt entre deux points p et q est la d nivel e minimale des chemins d extr mit s p et q Te p q inf r 1 1 p py Pn 10 73 Cette distance topographique est en fait seulement un cart en effet elle est positive sym trique et v rifie l in galit triangulaire Cependant T p q 0 n implique pas toujours p
84. rame de la figure 5 1 c est hexagonale Chaque point a six voisins Donc c est une trame hexagonale 6 connexit On rappelle qu un ensemble est dit connexe s il ne peut tre form de l union de deux ouverts disjoints au sens de la topologie associ e L l ment structurant unit de la trame que nous noterons H est l ensemble form de l origine et des voisins de l origine Voici les l ments structurants unit pour les trois types de trame 85 a Trame carr e b Trame carr e c Trame hexagonale 4 connexit 8 connexit 6 connexit Figure 5 2 Les l ments structurants unit s des trois trames couramment utilis es L l ment structurant de taille n sera le dilat n fois par lui m me de l l ment structurant unit Malheureusement il n est pas possible de d finir une topologie convenable dans Z pour tous les maillages Les probl mes viennent pour la plupart du fait que l une des premi res tapes lors de la traduction de concepts de g om trie discr te est d exprimer de mani re coh rente le th or me de Jordan Il est utile de rappeler d s pr sent la formulation de ce th or me dans l espace continu Th or me de Jordan dans R Toute courbe ferm e simple c est dire ne se recoupant par elle m me s pare le plan en deux domaines ensembles connexes qui sont le domaine int rieur et le domaine ext rieur de la courbe conform ment la figure 5 4 P simple
85. rateur Y est extensif ou anti extensif si Ve E x lt Y x ou x gt WY x On dit que l op rateur Y est idempotent si Ve E P x P x Soit E un treillis complet et soit un optrateur croissant sur E Pour toute famille xi ie1 d l ments d E on a y pve et i i P A xi j SA W x i i On dit qu un ensemble X inclus dans E est ferm pour l op rateur ou Y ferm si vV xeX gt P x e X L ensemble des op rateurs croissants sur le treillis E est lui m me un treillis pour la relation d ordre lt o V xe E B x lt Yh Le sup est alors donn par vo v Ea i Sur tout ensemble E on peut d finir plusieurs topologies sauf lorsque E contient au plus un point L une d elle est la topologie discr te c est celle pour laquelle E est l ensemble de toutes les parties de E C est la topologie sur E qui comporte le plus d ouverts possible Une autre est la topologie grossi re c est celle pour laquelle IT E ne contient que deux l ments l ensemble vide et E C est la topologie sur E qui comporte le moins d ouverts possible Mais les topologies int ressantes ne sont en g n ral ni discr tes ni grossi res On remarquera que les propri t s O O2 et O sont celles que nous avons mises en vidence dans l tude de la topologie de la droite Il est remarquable qu elles suffisent obtenir des nonc s tr s riches D finition 2 On dit qu un sous ensemble A de E est FERM lorsque son compl
86. respondance chaque ensemble u ment de O avec un autre ensemble m U ment de F On pr sente dans la suite les conditions pour la semicontinuit de telles applications Proposition 2 La fonction est s c s si et seulement si pour tout de et pour tout suite convergente vers dans Q on a lim wo c Y o Proposition 3 La fonction est s c i si et seulement si pour tout de Q et pour tout suite convergente vers dans Q on a Yo lim P o Exemples El E R l intersection est s c s sur F T E2 E R la compl mentation est s c i sur F T Ces fonctions d ensemble d finies sur des espaces topologiques peuvent tre regard es comme on l a d j vu dans le cas de treillis comme des op rateurs Le motif est que l ensemble de parties d un ensemble E II E peut tre regard comme une topologie ou comme un treillis bool en en m me temps Ici prend fin cette pr sentation succincte des outils math matiques qui se trouvent a la base de l tude de la morphologie math matique 2 Op rateurs morphologiques de base Le cas le plus simple est celui d images binaires Celles ci sont d crites l aide de la th orie des ensembles On pr sente dans la suite les principaux op rateurs morphologiques utilis s pour le traitement et l analyse des images binaires Pour la construction de ces op rateurs on utilise des ensembles sp cifiques appel s ELEMENTS STRUCTURANTS Il y a une f
87. riginale c L image de la fermeture de l image originale Figure 3 4 2 1 Les effets sur les images de l op rateur d ouverture et de fermeture 3 4 3 Un exemple d utilisation de louverture morphologique Un premier exemple d utilisation de l ouverture est dans le cadre de l op rateur morphologique 51 appel CHAPEAU HAUT DE FORME top hat en anglais Il s agit de la transformation morphologique la plus populaire permettant d extraire sur une image les structures contrast es et de faible paisseur ceci ind pendamment de la valeur absolue de l clairage ambiant Il est donn par Pot 49 o g peut tre tout l ment structurant en particulier gg o B est un cercle Dans le cas du sous graphe d une demi sphere on parle plut t de ROLLING BALL On pr sente dans la figure 3 4 3 1 l effet de l application de l op rateur morphologique chapeau haute de forme une image On a utilis un l ment structurant carr FAR RU i Fa f i ot gl a L LA F ry iy F3 af ato i hN i mn Hs F Hy b L image obtenue par l utilisation de a L image originale la chapeau haute de forme 52 3 4 4 Ouvertures et fermetures alg briques Nous nous int ressons pr sent la composition d op rateurs croissants et aux nouvelles propri t s qu ils poss dent D finition Soit yun op rateur croissant sur le treillis bool en II E yest une ouverture
88. rire sale ff x eR xR SGE y eSa t 3 Si on compare les relations 1 et 3 on constate leurs ressemblance formelle Kx Sr AoSG f Cette ressemblance formelle justifie la d finition de l rosion morphologique qu on a donn e La relation 3 nous donne un outil pour le calcul de l erod e morphologique d une fonction L exemple suivant nous pr sente le mode d emploi de cet outil 23 E3 Pour n 1 soit f x la fonction avec la repr sentation graphique f x Figure 2 7 Le graphe de la fonction roder et l l ment structurant pr sent dans la figure 2 8 g x Pa Figure 2 8 L l ment structurant Le sous graph de la fonction f est pr sent dans la figure 2 9 a et le sous graph de la fonction g dans la figure 2 9 b 24 gx a SGD Figure 2 9 Les sous graphes des fonctions f a et gx b Pour d terminer le sous graph de la fonction f g il faut pr ciser l ensemble des points x t pour lesquelles le sous graph de la fonction g x est inclus dans le sous graph de la fonction f A ce but on prend diff rentes valeurs pour x et pour t et on v rifie la condition SGH SG Dans la figure suivante on pr sente les valeurs limites des x et t qui v rifient la condition Figure 10 Le calcul du sous graph de la fonction f g La r union des points de la forme ktk marqu s dans la figure 10 conduit vers la repr sentation de la figure 11 25
89. ros du Laplacian attracteurs des minima pour n en citer que quelques unes Chacune de ces d finitions donne naissance des objets qui sont bien sur diff rents La morphologie math matique est partie de la notion d attracteur des minima c est dire qu tout minimum sera associ la zone g ographique d o une goutte d eau suivant la ligne de plus grande pente arrivera dans ce minimum Le compl mentaire des attracteurs est donc bien une ligne de partage des eaux ou Ipe 4 3 1 Approche par immersion Cette approche suppose que l image que nous tudions est une fonction en escalier f R N Nous verrons alors comment passer la limite et calculer la ligne de partage des eaux d une fonction assez r guli re Nous appellerons plateaux de f l ensemble des points au voisinage desquels f est constante Rendre alors math matique la notion d une goutte d eau qui descend selon la ligne de plus grande pente jusqu un minimum r gional est d licat sur les fonctions en escalier sur un plateau la pente est nulle Le moyen le plus simple pour contourner cette difficult est de proc der en immergeant progressivement dans l eau la fonction f par le bas Pour que l eau monte partout de mani re r guli re on supposera que les minima r gionaux sont perc s comme la montre la figure 4 3 1 1 Passant par les ouvertures que l on a cr es l eau progresse alors dans les bassins correspondant
90. sation locale de la ligne de partage des eaux Ceci est du la r gularit C de f Si f est moins r guli re il peut exister des crit res locaux En particulier si f est la distance un ensemble compos de plusieurs composantes la ligne de partage des eaux de f est incluse dans les points de non differentiabilit de f Cette remarque sugg re une approche m trique de la ligne de partage des eaux o celui ci serait un Skiz au sens d une distance g n rale 4 3 3 L approche m trique Dans le cas continu sous des hypoth ses de r gularit convenables C points 80 singuliers isol s et Hessien ayant ses deux valeurs propres non nulles la ligne de partage des eaux est un graphe compos de lignes int grales du gradient Toujours sous ces m mes hypoth ses nous allons d finir une m trique pour laquelle la ligne de partage des eaux est en fait un squelette par zones d influence D finition La distance image dy d une fonction f de classe C est definie par B v a b e supp xsupp t de a b inf IVE ra s 70 Yab Q o Yap est un chemin d a b parametr par son abscisse curviligne 4 3 3 1 La ligne de partage des eaux est un Skiz Sous nos hypoth ses d est alors une distance Pour des raisons techniques nous supposerons que f a tous ses minima au m me niveau que nous prendrons gal a O par convention Une transformation permettant f de v rifier cette hypoth se peut tre effectu e s
91. sinon et Ay f u er lu x aex Fx 7 Voila pourquoi l rosion de la fonction f par l l ment structurant gg peut tre calcul e par la relation Eg fHX Anex fux T C est une expression tr s simple pour l rosion que l on utilise en pratique dans les programmes 2 1 1 Propri t s math matiques On pr sente quelques propri t s de op rateur d rosion Ce sont des propri t s 27 utiles pour sa caract risation et pour son utilisation dans les applications Dans Pre 86 on trouve la d monstration de la proposition suivante P1 L rosion par une fonction ge est une application s c s de dans et une application continue de dans Donc le cadre naturel de l op rateur d rosion est celui des fonctions semicontinues P2 L rosion est croissante selon f et d croissante selon g i e f lt f gt frg lt f s 8 g lt g gt fig lt f g 9 D monstration s x inf y gly xJye R i Si f lt f alors V yeR fly gly x sf y gly x donc inf f y gly x yeR sine P Q aly xlyeR et la croissance de l rosion est prouv e Si gsg alors gly x 2 g y x e fly gly x 2 fly g y x gt are gly x yeR inff y g y xJyeR a f 8 x 2 f z Xx et la d croissance de l rosion selon la fonction g est d montr e On pr sente dans la suite quelques propri t s de la soustraction de Minkovski La relation entre les
92. sion Le premier op rateur morphologique est celui d rosion L rod de l ensemble A par l l ment structurant K est la diff rence de Minkovski entre A et K On note Ex A A K ke R K ca 1 Si on r p te les exemples 1 et 2 pour calculer les rod s on obtient les m mes r sultats parce que dans ces cas les ensembles K sont sym triques K K Si on regarde les r sultats obtenus dans les exemples 1 et 2 on constate que les ensembles r sultats sont inclus dans les ensembles A Voila pourquoi on appelle cet op rateur rosion Le r sultat de l rosion d pende de la forme de l l ment structurant Prenons de nouveau l exemple E2 mais consid rons cette fois ci l l ment structurant pr sent dans la figure 2 4 Figure 2 4 Le nouvel l ment structurant La description analytique de cet ensemble est K x lt y x sef Donc son sym trique est K x lt e y x se repr sent dans la figure 2 5 Figure 2 5 Le sym trique de I l ment structurant 21 L rod de l ensemble A dans l exemple E2 l aide de l l ment structurant K dans la figure 2 4 est calcul dans la suite Si a lt E x a lt E y gt K CA y lt 0 Si aze x as e y gt K cA y lt 0 Si azy a lt E Xx gt K cA y gt 0 Si aze x aZ2Y gt K cA y gt 0 Le r sultat est pr sent dans la figure 2 6 a Figure 2 6 L rod d un rectangle On a ut
93. ste aucun chemin connexe en 4 connexit l int rieur de la courbe Donc l int rieur de la courbe n est pas un ensemble connexe et le principe de Jordan n est pas respect En ce qui concerne l image c l ensemble int rieur de la courbe n est pas connexe en 8 connexit parce qu il ne contienne qu un seul point Donc ni dans le cas de la figure c le principe de Jordan n est pas respect Seulement dans la figure b le principe de Jordan est respect Parce que les points int rieurs sont connexes en 6 connexit Voil pourquoi on pr f re la trame hexagonale 6 connexit La r union des ensembles int rieure a la courbe constitu e par le chemin digital et ext rieur cette courbe repr sente le compl mentaire du chemin digital En utilisant cette observation on peut formuler le principe de Jordan pour l espace ZX Z Etant donn un arc de longueur finie dans le plan son compl mentaire est compos d une seule r gion connexe On peut faire s appliquer le principe de Jordan sur le maillage carr aussi si le compl mentaire d un arc ou d une courbe 4 connexe respectivement 8 connexe est analyse en 8 connexite respectivement 4 connexite Le th or me de Jordan se formule alors de la mani re suivant dans l espace discret Le compl mentaire de toute courbe discr te 4 connexe respectivement 8 connexe est form de deux composants 8 connexes respectivement 4 connexes L une de
94. t B 46 Le r sultat de l op ration est pr sent dans la figure 3 3 2 Figure 3 3 2 L ouverture de l image X en utilisant l l ment structurant B On pr sente dans la suite quelques propri t s de l ouverture P1 L ouverture est croissante D monstration XB UB gt Bu Cc X c UB Bu Cc Y YB u u P2 L ouverture est anti extensive Xg cX 39 D monstration Xg UtBu Bu cX u Mais pour chaque u B X Voil pourquoi on peut crire UB Bu cX cX c q f d u 47 P3 L ouverture est idempotente Xp p Xp 40 D monstration Xg U Bu Bu cX Xg UBs By cXg u V Mais gr ce la propri t P2 Xp X Voil pourquoi la derni re relation devient Xp p B By c X Xp 41 V Donc la propri t 3 est prouv e P4 L ouverture commute avec les translations Xp Xx p 42 D monstration Xp x B B U K B u qxe be B be B be B b Xp Ul ae X atx 42 1 be B beB D autre part x K B B U x B u a beB beB beB 42 2 J NaexX a x beB beB b Les membres droits des relations 42 1 et 42 2 sont identiques C est pourquoi la relation 42 est v rifi e Malheureusement il n y a pas de formule fonctionnelle sympathique pour l ouverture et l application de cet op rateur aux images plusieurs tentes de gris semble difficile Heureusement on peut effectuer une ouverture section superieure par section
95. t s c i 1 4 Quelques l ments utiles de topologie On pr sente dans la suite quelques l ments de topologie qui seront utiles l introduction des op rateurs de la morphologie math matique On commence avec la topologie de R et on finit avec la topologie des espaces fonctionnels 1 4 1 Topologie de la droite R D finition 1 On dit qu un sous ensemble A de R est OUVERT s il est vide ou si pour tout x de A il existe un intervalle ouvert contenant x et contenu dans A De cette d finition r sultent les cons quences presque imm diates suivantes O1 Toute r union finie ou non d ouverts est ouverte O2 Toute intersection finie d ouverts est ouverte O3 La droite R et l ensemble vide sont des ouverts D finition 2 On dit qu un sous ensemble A de R est ferm lorsque son compl mentaire CRA est ouvert Les cons quences correspondantes sont F1 Toute intersection de ferm s est ferm e F2 Toute r union finie de ferm s est ferm e F3 La droite R et l ensemble vide sont des ensembles ferm s D finition 3 Si A est un sous ensemble de R un point x9 de R est dit POINT D ACCUMULATION de A si dans tout voisinage de x il existe du moins un point de A autre que Xo D finition 4 Un point ISOLE d un ensemble A est un point x de A qui n est pas point d accumulation de A Autrement dit c est un point x de A qui poss de un voisinage V tel que ANV x D finition 5 On dit qu une partie non vide A de R est born
96. tincts de P qui v rifient d4 P Q lt 1 sont appel s points 4 adjacents P ou points 4 connexes P On peut introduire une autre distance not e de dg P Q max ip iQl jp iol Cette distance est appel e en anglais Chessboard Distance ou Diamond Distance Les points qui ont la propri t kd dg P Q lt 1 sont le points 8 connexes P Maillage triangulaire Celui ci associe chaque point P trois voisins Donc on parle de 3 connexit Le 9 voisinage de P est donn par son 3 voisinage auquel on ajoute les points de coordonn es i 1 j 1 G 1 j 1 j 2 G 1 j D G 1 j 1 sur le codage matriciel Les six points ainsi rajout s sont centres des tesselles qui ont seulement un sommet commune avec les tesselles associ e P et une ar te commune avec les tesselles du 3 voisinage de P Pour le 12 voisinage on ajoute au 9 voisinage les trois points i 1 j G 1 j 2 G 1 j 2 si i j est pair i 1 j G 1 j 2 G 1 j 2 si i j est impair La notion de points adjacents s tend la notion de chemin connexe Dans le cas du maillage carr on voit apparaitre deux types de chemins des chemins 4 connexes ou 8 connexes conform ment la figure 5 5 P xx a a 3 b Figure 5 5 Chemins 4 connexe a et 8 connexe b sur le maillage carr 87 Pour le maillage triangulaire les chemins pourront tre 3 connexes 9 connexes ou 12 connexes Pour le maillage hexagonal il n y a aucun
97. tte On pr sente dans la suite sans preuve quelques propri t s topologiques Proposition 4 1 4 4 En tout point de l ouvert G Sq G la fonction distance sur G est differetiable et son gradient est le vecteur unit orient selon l amont de x Proposition 4 1 4 5 La fonction distance sur G n est pas differentiable sur D G ensemble des points multiples de Sq G Th or me 4 1 4 6 L adh rence du squelette est le compl mentaire du plus grand ouvert de G o pgest differentiable En regardant les squelettes de diff rents ensembles on peut observer leur ressemblance avec des graphes Voila pourquoi dans la suite on tudie cette ressemblance Definition Un graphe est une union de courbes simples qui ne peuvent pas s interrsecter qu en leurs extr mit s Les courbes simples sont appel es ar tes et leurs extr mit s sommets Definition Un graphe est de type fini si 1 Le nombre d ar tes incidents un sommet est fini 2 L ensemble des sommets est isol On rappelle que Un ensemble A est isol si pour tout compact K K A A est compos d un nombre fini de points Si Pon ne fait pas d hypoth ses suppl mentaires le squelette n a pas de structure de graphe Dans la figure suivante on pr sente l effet de la squeletisation sur une image Figure 4 1 4 6 Un exemple de squeletisation L image originale est celle de gauche Son squelette est pr sent dans l image de droite 73 4 2 S
98. un pixel Cette courbe peut tre consid r e comme le squelette de l objet consid r Cet algorithme le premier connu et implant est particuli rement lent il faut balayer 6 fois l image pour liminer les points eliminables de la fronti re de l objet Notons que le fait que ces transformations pr servent la connexit n est pas premi re vue vident car les pixels sont examin s en parall le chaque tape 97 Le squelette utilis habituellement est calcul l aide de L Celui obtenu par M fournit de trop nombreuses branches ou barbules La configuration D r duit un point tout objet sans trou et peut donc tre utilis e pour marquer de mani re homotopique un objet le transformer en un point unique 5 1 2 1 2 Algorithmes base de files d attente Le principe de ces algorithmes consiste liminer dans un certain ordre les pixels du bord de l objet Un pixel sera dit liminable si sa suppression ne modifie pas la connexit de l objet Dans une premi re tape les points que l on veut voir figurer dans le squelette sont d termin s Ce sont typiquement les maxima locaux de la fonction distance au bord Ce points sont appel s points d ancrage L algorithme consiste alors mettre sur une fille d attente les pixels du contour des objets puis examiner dans l ordre les pixels de la file liminer des objets tous ceux qui ne sont pas points d ancrage et qui ne modifie pas
99. un voisinage ferm de a ne contenant pas b En particulier tout ensemble a est ferme puisqu il est l intersection de ses voisinages ferm s D finition 12 0n dit qu un espace E est COMPACT s il est s par et si de tout recouvrement ouvert de E on peut extraire un sous recouvrement fini Il existe de nombreux espaces qui sans tre compacts se comportent localement comme un espace compact c est le cas de R par exemple De fa on pr cise Definition 13 On appelle espace LOCALEMENT COMPACT tout espace s par E dont tout point poss de au moins un voisinage compact Exemples 1 Tout espace compact est localement compact 2 Tout espace topologique discret est localement compact exemple Z 3 La droite R est localement compacte en effet d abord R est s par e ensuite pour tout x appartenant a R il existe a et b appartenant R tels que a lt x lt b et a b est un voisinage compact de x R n est pas compacte 4 Le sous espace Q de R n est ni compact ni localement compact en effet supposons par exemple que O poss de dans Q un voisinage compact V le voisinage V de O contient un sous voisinage de la forme Qr a a comme ce dernier est ferm dans Q l ensemble A Qr a a serait alors compact or ceci est manifestement faux puisque pour tout irrationnel x dans a a la suite d croissante des ferm s AMN x 1 n x 1 n a une intersection vide D finition 14 On dit qu un espace topologique E est CONNEXE s il n existe aucun
100. une rod e et f sera une dilat e de f L image transform e sera fik si x f x lt fy x f x f x gt f x Si f x f x gt f x f x f x sinon La valeur des pixels est donc remplac e par la valeur la plus proche selon f et f L rosion et la dilatation sont des transformations duales Elles ne sont pas inverses Ceci nous permet d tudier quelques op rateurs classiques donnant acc s des primitives morphologiques plus 45 complexes et ayant de meilleures propri t s en particulier l idempotence Parmi ceux ci les plus importantes deux sont l ouverture et la fermeture 3 3 L ouverture morphologique Soit X une image et B un l ment structurant Cette op ration morphologique est definie pour les images binaires par Xp X B OB 36 Mais x B B u K B nB b tu G ve X B et ve B f fu ay B cXetve B Mais ve B be B u b gt v u b gt u v b gt ue B Donc x B B u Av B cXetue B u B cX J Bu Bu c X u On a obtenu la relation quivalente Xp U By By cX 37 u Donc Xp repr sente l espace balay par l l ment structurant B lorsqu il est totalement inclus dans X Prenons un exemple ET Soit n 2 X a a x a a et B e e x e e e lt lt a On peut observer que B B Le r sultat de l op ration X Best pr sent dans la figure 3 3 1 Figure 3 3 1 L rosion de l image X en utilisant l l ment structuran
101. up et inf de ce treillis sont donnes par les relations f vf SG t Jsclf f Afj SG f SG 1 1 Ainsi le treillis de fonctions a t r duit un treillis d ensembles Soit f une fonction d finie sur R qui prenne des valeurs dans R On appelle r gularis e sup rieure de f la plus petite majorante s c s de f f inf g ge P et f lt g On appelle regularis e inferieure de f la plus grande minorante s c i de f f sup g g etg lt f Le concept de dualit peut tre introduit aussi dans le cadre fonctionnel L op rateur dual de l op rateur peut tre d finit comme suit v fe o Y f w f Pr sentons deux exemples E1 Cherchons par exemple l op rateur dual de l op rateur A ke fra a a fa g x min F Cex Si f x lt g x alors f x 2 g x gt min f C g x g x et min f C g x g x max f x ax Ff v g x Si f x g x 7 alors f x lt x min f Cg i x f min Cf Cg x maxtf x GE Fv g x On a montr ainsi que sy v E2 On consid re l op rateur W f f Alors W x PE Lx Fx PY Donc Un tel op rateur s appelle autodual Dans Pre 86 est d montr e la proposition suivante Soit un opirateur d finit sur valeurs dans tel que P D c d et P c Alors si Vest continu alors est continu si Vests c s alors est s c s si Vest s c i alors es
102. valeur O ou la valeur 1 Si on consid re la restriction de cette fonction l ensemble X form e par les l ments d image ou la valeur de f est gale a 1 alors cette fonction f d crit l ensemble des objets de l image f Le compl ment de l ensemble X par rapport l ensemble X repr sente le fond de l image X Par l application d un op rateur morphologique a la fonction f on obtient la fonction f2 Celle ci d crit un ensemble d objets diff rent On peut donc affirmer que par l application de l op rateur morphologique consid r la forme des objets d crits par f est modifi e Donc les op rateurs morphologiques transforment la forme des objets de l image On peut observer que la fonction f est la fonction indicatrice de l ensemble X peste X Vhxe X fi x 4 7 0 sinon En cons quence le formalisme ad qu pour la description des op rateurs morphologiques pour les images binaires est la th orie des ensembles Une autre cat gorie d images est celle d images a TEINTES DE GRIS ou IMAGES NUMERIQUES Ceux ci peuvent tre d crits par fonctions d finies sur des ensembles inclus en R valeurs dans un ensemble n n5 np n E 0 1 k 1 P Les couleurs claires correspondent a des valeurs lev es des niveaux de gris les couleurs sombres a des valeurs faibles Pour d crire ces images le cadre de la th orie des ensembles suffisant pour les images binaires devient insuffisant Ce cadre doit tre remplac
103. x U SG F SG 2 22 Calculons par exemple la dilatation de la fonction f avec le sous graph pr sent dans la figure 2 2 3 a l aide du l ment structurant g avec le sous graph pr sent dans la figure 2 2 3 b v 4 gu b Le sous graph de c Le sous graph de la d Le sous graph de la l element structurant fonction z fonction amp V a Le Rnb d la fonction f 34 f Le sous graph de la fonction f g et sa representation graphique Figure 2 2 3 Le calcul du sous graph de la dilatation L aire du SG f amp est plus grande que l aire du SG f C est la cause que f repr sente la dilatation de la fonction f Trouvons une nouvelle expression pour la dilatation d une fonction donn e On utilise ce but la relation 6 du paragraphe 2 1 Es tf x u flu glu x et on prends le dual DeF x Eg f x Ey F fx F u g u x vy F u gu x On a d montr ainsi que Det Kx Vutt u lux 23 35 Dans le cas des l ments structurants plans associ s au compact K 0 sur K 8K six K on a fo siu xeK gx u x co sinon ou 0 siueK gg u x co sinon On peut donc crire f u si ue K F u ex u x gt 00 sinon et De tf x Vuer U 24 Donc dans le cas des l ments structurants plans l expression de la dilatation est tr s simple voir la derni re relation Cette expression est utilis e en pratique
104. xception sont appel s les extr mit s de l arc S Deux exemples sont pr sent s dans la figure 5 8 88 Figure 5 8 Arcs 4 connexes a et 8 connexes b Soit S un sous ensemble non vide de points de S est une courbe si et seulement si S est connexe et si chacun de ses points poss de exactement deux points adjacents dans S Dans la figure 5 9 sont pr sent es deux exemples de courbes a b Figure 5 9 Courbes 4 connexes a et 8 connexes b Le terme de courbe 8 connexe ne peut pas tre employ moins de quatre points et celui de courbe 4 connexe moins de huit points D finition 5 3 Un chemin digital est une suite ordonn e de points voisins p aa Un arc digital est l ensemble des points d un chemin digital sans notion d ordre En utilisant cette notion on peut faire une classification des trames On utilise ce but le principe de Jordan L nonc de ce principe est Un chemin qui ne se croise pas s pare la trame en deux composantes connexes exactement En utilisant la figure 5 10 on peut constater que seulement la trame hexagonale 6 connexit respecte le principe de Jordan 89 2 TRES SR N L XK a Trame carr e b Trame hexagonale c Trame carr e 4 connexit 6 connexit e 8 connexit e Figure 5 3 Exemples semnificatives de chemins digitaux En effet les point int rieurs de la figure a ne sont pas connexes en 4 connexit parce qu il n exi
105. xemples de trames Ayant obtenu un pavage on associe un point P l int rieur de chacune des tesselles Vp intervenant dans sa constitution Les points P peuvent tre les centres de gravit des Vp nous rappellerons que nous avons restreint dans cette approche les Vp tre des polygones convexes r guliers comme est montr dans la figure 5 2 En langage d imagerie les points P sont appel s pixels picture elements On d finit ensuite le maillage associ un pavage A tout point P est associ l ensemble des points Q tels que Vp et Vg ont une arr te commune L ensemble de tous les segments P Q ainsi d finis forme le maillage associ au pavage Les segments du maillage forment un nouveau pavage pour lequel les points repr sentatifs des tesselles sont les sommets du pavage initial Ainsi pavage et maillage sont des repr sentations duales du partitionnement du plan On remarque que le partitionnement d fini par le maillage associ au pavage triangulaire est le pavage hexagonal que celui d fini a partir du pavage carr reste carr et que celui ci d fini a partir du pavage hexagonal est triangulaire Chaque point int rieur de la trame pr sent e dans la figure 5 3 a a 4 voisins Il s agit donc d une trame carr e 4 connexit Dans la figure 5 3 b est pr sent e une autre trame carr e Dans ce cas ci chaque point a 8 voisins Voila pourquoi on dit qu il s agit d une trame carr e 8 connexit La t

Mode d'emploi

Contents

Download Pdf Manuals

Related Search

Related Contents