Squelettisation en un balayage. Application à la caractérisation osseuse.

6.4

Quest-ce que los trab culaire ? . . . . . . . . . . . . . . . . . . . 153

Comment caract riser los ? . . . . . . . . . . . . . . . . . . . . . 155

Acquisition et pr -traitements . . . . . . . . . . . . . . . . . . . . 160

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

7

Extraction des caract ristiques de los trab culaire

169

7.1

D nition des caract ristiques extraire . . . . . . . . . . . . . . 169

7.1.1

7.1.2

7.1.3

7.1.4

Les points terminaux . . . . . . . . . . . . . . . . . . . . . 170

Les points dintersections . . . . . . . . . . . . . . . . . . . 172

La longueur des trab cules . . . . . . . . . . . . . . . . . . 173

La largeur des trab cules . . . . . . . . . . . . . . . . . . . 174

7.2

M thode dextraction des informations . . . . . . . . . . . . . . . 176

7.2.1

7.2.2

7.2.3

7.2.4

Rappel des tapes pr c dentes . . . . . . . . . . . . . . . . 177

Dernier amincissement . . . . . . . . . . . . . . . . . . . . 177

Extraction des points sp ciaux . . . . . . . . . . . . . . . . 178

tiquetage des trab cules

. . . . . . . . . . . . . . . . . . 181

7.3

R sultats

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

Conclusion

191

7

Table des mati res

Conclusion g n rale

195

Perspectives

201

Squelettisation 3D en un balayage . . . . . . . . . . . . . . . . . . 201

Distances utilis es

. . . . . . . . . . . . . . . . . . . . . . . . . . 202

Am lioration de la m thode dextraction des caract ristiques os-

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

seuses

Autres applications . . . . . . . . . . . . . . . . . . . . . . . . . . 204

IV Annexe

205

Temps dex cution . . . . . . . . . . . . . . . . . . . . . . . . . . 207

La base dimages test es . . . . . . . . . . . . . . . . . . . 207

Carte de distance . . . . . . . . . . . . . . . . . . . . . . . 209

Axe m dian . . . . . . . . . . . . . . . . . . . . . . . . . . 212

Squelettisation . . . . . . . . . . . . . . . . . . . . . . . . 216

Extraction des caract ristiques osseuses . . . . . . . . . . . . . . . 228

Caract ristiques extraites dune image dos.

. . . . . . . . 229

Caract ristiques extraites par le logiciel dodonto . . . . . 238

1.1

1.2

1.3

1.4

2.1

2.2

1

2

3

4

1

2

Production scientique

Bibliographie

243

245

8

Introduction g n rale

9

Table des mati res

La m decine est une science des pannes, celles de lorganisme humain... Mais

si le m decin est un d panneur - rien de plus, rien de moins - il est le d panneur

dune machine dont il ne poss de pas les plans. Lucien Isra l.

Les gens tombent malades et les m decins soignent les malades. Pour cela ils ont

recours di rents outils de travail. Limagerie m dicale est notamment devenue

un outil tr s pr cieux pour les m decins. Elle permet aux m decins de visualiser

et d tudier un corps sain et en d duire les di rences avec ou sans pathologie

donn e.

Il existe di rents types dimagerie m dicale : les rayons X, limagerie par

r sonance magn tique (IRM), l chographie,...

Chacune de ces modalit s produit soit des images de projection comme la ra-

diographie rayons X, soit des coupes apr s reconstruction tomographique comme

lIRM.

partir des images produites, les m decins peuvent visualiser un tat phy-

siologique on lappelle imagerie structurelle. Elle donne des informations sur

lanatomie des organes comme la taille ou la forme. Les m decins peuvent gale-

ment avoir recours limagerie fonctionnelle. Comme son nom lindique, ce type

dimagerie permet aux m decins de visualiser le fonctionnement dun organe.

Cest dans ce contexte que se positionne ce travail : caract riser des formes soit

dorganes soit de mat riaux constituants dorganes. Les mesures seectuent sur des

formes : cest la premi re tape dite de reconnaissance des formes . Si on image

lensemble dun organe, on peut donc comparer statistiquement les param tres

explicitant la forme de lorgane vis- -vis dun ensemble dorganes sains ou atteints

dune maladie sp cique. Cest la seconde tape de classication de formes .

On pourra ainsi classier lorgane du patient dans une classe saine/malade en

fonction des param tres de la forme. Si on image une partie dorgane constitu e

dun ensemble de petites formes, le m me raisonnement sapplique en r alisant des

moyennes sur chaque lement de forme lementaire quon est capable de dissocier

des voisins.

Dans notre tude, nous visons caract riser larchitecture osseuse ou plus pr ci-

s ment los trab culaire. Los trab culaire a une architecture particuli rement com-

pliqu e (forme spongieuse), nous allons mettre en place des traitements dimage

11

Table des mati res

adapt s.

Les images que nous allons analyser se composent de millions de pixels dont les

valeurs sont comprises entre 0 et 255 (images dites en niveaux de gris). Les post-

traitements qui ont t appliqu s ant rieurement ce travail permettent dobtenir

une image binaire (dont la valeur des pixels est soit de 0 soit de 1) et r duisent la

taille des images un millier de pixels traiter.

Les traitements dimages que nous souhaitons appliquer n cessitent le stockage

en m moire de N N pixels constituants limage.

Dans ce travail, nous r duisons loccupation m moire de ces traitements 2N

pixels. Outre cette meilleure gestion de la m moire, nous remarquerons lecacit

en terme de temps de calculs et ce, sans changer la complexit algorithmique de

nos traitements.

La premi re partie de ce travail consiste pr senter lespace dans lequel nous

allons travailler et pr senter les traitements dimages que nous allons d velopper.

La seconde partie pr sente les di rentes phases du traitement que nous avons

mis en Suvre.

La troisi me partie montre comment ce traitement a t appliqu la caract -

risation de los.

12

Premi re partie

G om trie discr te

13

Introduction

La g om trie discr te est un sous ensemble de la g om trie au m me titre que

la g om trie continue. Cette derni re nous a tous t enseign e dans notre en-

fance. Si la g om trie continue a pris le monopole de lappelation g om trie, la

g om trie discr te nen nest pas moins int ressante.

L re du num rique a v ritablement propuls la g om trie discr te au devant de la

sc ne en mettant en cause le monde continu. Par eet boule de neige, la discre-

tisation de linformation nous a forc savoir analyser ces donn es discr tes.

Lutilisation de capteurs, lors de lacquisition de limage, provoque une discr -

tisation du monde r el. Si nous savions calculer la distance entre deux objets pos s

sur une table, il tait par contre plus dicile destimer la distance entre les deux

objets partir dune photographie de cette m me sc ne. Car au del du probl me

d chelle de limage de la sc ne, limage est compos e de pixels d au m canisme

dacquisition de celle ci.

Cest dans les ann es 1960 que des chercheurs fran ais d couvrent la morpho-

logie math matique, une discipline de lanalyse dimage. Il a alors fallu apprivoi-

ser ce monde discret en commen ant par d nir lespace discret. Des notions de

connexit s de pixels ont permis deectuer des liens entre pixels, qui aboutiront

progressivement la naissance de premi res distances discr tes.

Cette premi re partie pr sente cet espace discret et certaines distances dis-

cr tes. La suite de ce travail concerne un descripteur de formes morphologiques

tr s utilis en analyse dimage : le squelette. Le processus de squelettisation est

galement pr sent dans cette partie.

15

Chapitre 1

Lespace discret et distances

discr tes

1.1

Introduction

Une image num rique peut tre repr sent e comme un tableau 2D o chaque

case du tableau repr sente un pixel et contient une valeur (0 ou 1 pour une image

binaire et de 0 255 pour une image en niveau de gris). En 3D limage est en

fait un volume dimages qui est repr sent par un tableau 3 dimensions. Dans ce

sens nous travaillerons, dans cette th se, dans un espace discret compos de pixels.

Cet espace discret est en fait un espace continu partitionn par un pavage r gulier.

Le pavage est une repr sentation de lespace utilis en imagerie num rique. Pour

faire ce pavage r gulier on utilise la m me forme que lon d place pour remplir le

plan. Il existe plusieurs types de pavages (voir gure 1.1). Parmi ces pavages le

pavage carr reste le plus utilis parce quil facilite lextraction des points discrets.

Ainsi chaque point a une paire de coordonn es correspondant lindice des lignes

et des colonnes de limage et en 3D chaque voxel a ainsi un triplet de coordonn es

(la derni re coordonn e repr sentant le num ro de plan de limage). Le centre de

chaque cellule de ce pavage est un point discret. Le maillage est un graphe reliant

les points discrets de chaque cellule voisine comme illustr sur la gure 1.1.

17

Chapitre 1. Lespace discret et distances discr tes

Figure 1.1 Pavages associ s leur maillage carr , triangulaire et hexagonal

En 3D les pavages r guliers peuvent avoir des formes plus complexes.

La forme du pixel, ou du voxel en 3D, d pend de di rentes contraintes :

Acquisition de linformation ou l tape de num risation,

Restitution de linformation (aspect visuel),

Manipulation de linformation. Par exemple, un pixel triangulaire n cessite

un codage particulier pour acc der ses coordonn es.

Dans ce travail de th se nous utiliserons des pixels carr s car il est plus pratique

de manipuler un chantillonnage orthogonal.

Dans ce chapitre sont introduites des notions de base utilis es dans la suite de

ce travail. Dans la section 1.2 nous d crivons comment deux points sont voisins

puis connexes. Ces notions sont ensuite utilis es pour en d duire un chemin qui

permet de d crire une forme. La d nition et la caract risation dun point simple

sont pr sent es dans la section 1.3.3. La section 1.4 d nit ce quest une distance,

quelles sont ses propri t s et pr sente ses principales mises en Suvre.

Enn dans la derni re section 1.7 est pr sent le probl me g n ral du d placement

dans un espace discret 2D.

1.2 Voisinage et connexit

On consid re un objet (ou une forme) X dans Z2, un ensemble de points. Cet

objet a une topologie et les points le constituant, des relations. Cette section pr -

sente quelques d nitions de relations entre pixels.

Avec un chantillonnage carr , il existe plusieurs types de voisinages, les plus

courants sont le 4-voisinage et le 8-voisinage. On les appelle aussi voisinages de

18

type 1 (N1) et de type 2 (N2) respectivement. Dans ce travail, nous continuerons

les noter de cette fa on.

1.2. Voisinage et connexit

D nition 1 (Voisinage N1(p)). Soit p un point de coordonn es (xp,yp). Le voisi-

nage de type 1 du point p (not N1(p)) est lensemble des points q de coordonn es

(xq,yq) qui v rient :

|xp xq| + |yp yq| d 1

(1.1)

On consid re quun point est voisin lui-m me. De la m me mani re,

D nition 2 (Voisinage N2(p)). Soit p un point de coordonn es (xp,yp). Le voisi-

nage de type 2 du point p (not N2(p)) est lensemble des points q de coordonn es

(xq,yq) qui v rient :

max (|xp xq| , |yp yq|) d 1

(1.2)

N1(p) est constitu de p et de lensemble des 4 points situ s en haut, gauche,

en bas et droite de p. Pour N2(p) il faut ajouter N1(p) les 4 points diagonaux

du point p [47, 79]. La gure 1.2 repr sente ces deux types de voisinage, le point

p est repr sent par le point central noir.

(a) N1

(b) N2

Figure 1.2 Voisinages de type 1 et 2

Gr ce aux pr c dentes d nitions, on peut relier 2 points entre eux avec un

chemin.

D nition 3 ( -chemin). Un -chemin du point p au point q est une suite de

points p = p0, p1, p2, ..., pn = q telle que pi est -voisin (avec {4, 8}) pi1

pour 1 d i d n.

19

Chapitre 1. Lespace discret et distances discr tes

q

q

p

p

(a) chemin de type 1

(b) chemin de type 2

Figure 1.3 Exemples de chemin de type 1 et 2.

1.3 Notion de topologie dune image

La topologie vient des mots topos (lieu) et logos ( tude), elle vise tudier

les lieux. Plus pr cis ment, la topologie permet d mettre une quivalence entre

deux objets si lon peut transformer lun en lautre gr ce la rotation, transla-

tion, r exion, changement de taille/volume, etc. Pour que les deux objets restent

topologiquement quivalents, la transformation ne doit pas induire de trou, d chi-

rements, sections. La gure 1.4 pr sente trois objets binaires. Dans cet exemple,

la pomme est topologiquement quivalente au marteau. La paire de ciseaux nest

pas topologique la pomme ni au marteau parce que la paire de ciseaux pr sente

deux trous alors que les deux autres objets nont pas de trous.

Figure 1.4 Formes binaires.

Dans cette section sont abord es des notions relatives la topologie de limage.

Dans un premier temps, dans la sous-section 1.3.1, une d nition des composantes

20

1.3. Notion de topologie dune image

connexes et un algorithme permettant de les identier sont pr sent s. En second

lieu, dans la sous-section 1.3.2, le nombre dEuler et son calcul sont pr sent s.

Enn, dans la sous-section 1.3.3 la notion de point simple est pr sent e ainsi que

di rentes m thodes pour le caract riser.

1.3.1 Les composantes connexes

Dans [79], Rosenfeld introduit la notion de composantes connexes (exemple

gure 1.5).

D nition 4 ( -connexit ). Soit X un ensemble de points. Deux points sont -

connect s si il existe un -chemin dans X les reliant.

D nition 5 (Composante -connexe). Une composante -connexe est un en-

semble maximal de points -connect s dans X.

q

p

Figure 1.5 Composante 8-connexe.

Dans lexemple de la gure 1.5 on peut voir que le chemin reliant les points

p et q est de type 2. Donc on peut d duire que la forme X est une composante

8-connexe. Comme il nexiste pas de chemin de type 1 reliant ces deux points, X

se compose de deux composantes 4-connexes.

Dans sa contribution, Rosenfeld introduit galement la labelisation" ou fonc-

tion d tiquetage. Comme son nom lindique, cette fonction distribue une tiquette

unique chaque composante connexe. Si on tiquette partir de 1 et par ordre

21

Chapitre 1. Lespace discret et distances discr tes

croissant, cela veut dire que la valeur maximale des tiquettes (ou des labels) cor-

respond au nombre de composantes connexes. La gure 1.6 repr sente une image

compos e de 3 composantes connexes tiquet es.

1

1

1

1

1

1

2

2

2

3

3

Figure 1.6 Image labelis e".

Dans sa m thode Rosenfeld parcourt limage (de gauche droite et de haut en

bas) et lorsquil rencontre un point de la forme, il propage l tiquette de son voisin

haut. Si le point en question na pas de voisin il cr e une nouvelle tiquette et il

attribue ce point cette nouvelle tiquette comme nous le montre la gure 1.7.

Dans cette gure les points d j balay s sont identi s en gris clair et ont un label

contrairement aux autres points.

1

1

2

2

3

Figure 1.7 Processus de labelisation.

Les tiquettes sont stock es dans un tableau quil agrandit chaque nouvelle

tiquette cr e. Ainsi lorsque toute limage a t balay e, il proc de une simpli-

cation du tableau d tiquettes.

22

1.3. Notion de topologie dune image

1.3.2 Le nombre dEuler

Le nombre dEuler, not E, ou encore la caract ristique dEuler est un invariant

topologique [48].

E = S A + F

(1.3)

Avec S, A et F qui d signent respectivement le nombre de sommets, dar tes et

de faces.

Dans une image binaire 2D la propri t dEuler-Poincar sexprime de la fa on

suivante :

E = O T

(1.4)

O O d signe le nombre de composantes connexes dans limage et T le nombre de

trous. Un trou est une composante connexe dans le compl mentaire de limage.

La gure 1.8 pr sente deux exemples dobjets binaires. Le nombre dEuler de la

conguration 1.8(a) vaut 0 puisque E = 2 2 tandis que dans la conguration

illustr e dans 1.8(b), E = 1 3.

(a) E = 0

(b) E = 2

Figure 1.8 Exemple dobjets et leurs nombre dEuler.

Dans la pratique, un algorithme [41] somme des congurations de pixels pour

extraire le nombre dEuler. Il compte les angles qui forment une convexit et sous-

trait les angles formants une cavit . Pour cela il utilise des congurations, dans un

voisinage 2 2, pond r es. Ces congurations sont illustr es dans la gure 1.9, il

faut galement ajouter ces congurations leurs rotations 90 , 180 et 90 .

23

Chapitre 1. Lespace discret et distances discr tes

(a) +1/4

(b) 1/4

(c) 1/2

Figure 1.9 Masques 2 2 de congurations pour d terminer le nombre dEuler.

La gure 1.10 pr sente deux exemples. Dans le premier, on compte 5 congu-

rations de type 1.9(a) et une conguration de type 1.9(b). Le nombre dEuler est

E = 1

Le nombre dEuler du second exemple est ainsi E = 1

4 = 1.

4 1

4 + 1

4 + 1

4 + 1

4 + 1

4 + 1

4 1

4 1

4 1

4 1

4 = 0.

4 + 1

4 + 1

(a) E = 1

(b) E = 0

Figure 1.10 Exemples du calcul du nombre dEuler.

1.3.3 Points simples

Cette section pr sente ce quest un point simple et comment on le caract rise.

Cette notion est utilis e dans le processus dextraction du squelette, introduit dans

le chapitre 2.

D nition

La notion de point simple, introduite par Rosenfeld dans [77], permet diden-

tier les points pouvant tre supprim s sans changer la topologie de la forme.

24

1.3. Notion de topologie dune image

D nition 6 (Point simple). Soit X une partie de Z2 avec un nombre ni de

composantes -connexes et de composantes -connexes. Un point A de X est -

simple dans X si :

lensemble X et X \ {A} ont le m me nombre de composantes -connexes ;

lensemble X et X \ {A} ont le m me nombre de composantes -connexes.

p

Figure 1.11 Exemple o le point p est 4-simple mais pas 8-simple.

La gure 1.11 illustre un objet et identie un point p. Si lon consid re la

8-connexit de la forme et la 4-connexit du fond, le point p ne peut pas tre sup-

prim sans scinder la forme en deux. Dans cette conguration, le point p nest pas

8-simple.

En revanche, si lon consid re la 4-connexit de la forme et la 8-connexit du fond,

la forme est compos e de deux composantes 4-connexes. La suppression du point

p ne change alors pas la topologie de la forme. Dans cette conguration, le point

p est 4-simple.

Cette derni re notion est importante dans le cadre de la squelettisation qui

demande la pr servation de la topologie de la forme (voir le chapitre 2).

Caract risation des points simples

Il existe plusieurs m thodes pour d terminer si un point est simple. Dans la

litt rature on appelle crossing number le nombre de connexit dans le voisinage

du point p, permettant de d nir la simplicit dun point. En eet le crossing

number renseigne, gr ce au nombre de voisins du point p tudier, la topologie

25

Chapitre 1. Lespace discret et distances discr tes

locale du sous ensemble de lobjet.

La m thode de Rutovitz [80] consiste compter le nombre de changement de valeur

dun pixel lautre lors du parcours du voisinage de p.

x4

x5

x6

x3

p

x7

x2

x1

x8

Figure 1.12 Repr sentation du voisinage du point p.

XR(p) =

8

X

i=1

kxi+1 xik

(1.5)

Avec x9 = x1. Le point p est simple si et seulement si XR(p) = 2.

La gure 1.12 montre lindexation, correspondante l quation, des voisins de p.

p

p

(a) XR(p) = 4

(b) XR(p) = 2

Figure 1.13 Exemple o le crossing number de Rutovitz vaut 4 et 2.

La gure 1.13(a) montre un cas o le point p nest pas simple et le crossing

number vaut 4. En revanche quand le point est simple 1.13(b), le crossing number

vaut 2. Une autre mani re de calculer la simplicit dun point a t tudi e par

Hilditch [45].

la di rence de la m thode de Rutovitz, Hilditch somme des combinaisons

de bi correspondants aux trois points formant le coin du voisinage.

XH(p) =

4

X

i=1

bi

(1.6)

26

1.3. Notion de topologie dune image

o bi =

1 si x2i1 = 0 et (x2i = 1 ou x2i+1 = 1)

0 sinon

Le point p est simple si et seulement si XH(p) = 1.

Le tableau 1.1 montre la d composition du calcul de la simplicit selon Hilditch

des exemples pr sent s dans la gure 1.14.

p

p

(a) XH (p) = 2

(b) XH (p) = 1

Figure 1.14 Exemple o le crossing number dHilditch vaut 2 et 1.

Dans le premier cas (gure 1.14(a)), le crossing number vaut 2 car le point p

nest pas simple. Dans le second cas (gure 1.14(b)), le point p est simple car le

crossing number vaut 1.

Table 1.1 D composition du calcul de XH des exemples de la gure 1.14.

Exemple 1.14(a)

Exemple 1.14(b)

i

1

2

3

4

i=1 bi

P4

x2i1 x2i x2i+1

0

0

0

1

0

1

0

1

1

0

1

0

bi x2i1 x2i x2i+1

0

1

0

1

0

0

1

0

0

1

1

0

0

0

1

1

bi

0

1

0

0

2

1

Une autre fa on de d terminer si un point est simple ou non est dutiliser le

nombre de Yokoi [98].

Pour le 4-voisinage de la forme et le 8-voisinage du fond le nombre de Yokoi se

note Y4 et pour le 8-voisinage de la forme et le 4-voisinage du fond le nombre de

Yokoi se note Y8. Les equations 1.7 et 1.8 utilisent lidentication des pixels de la

gure 1.12.

27

Chapitre 1. Lespace discret et distances discr tes

Y4 = x1(1 x8x7) + x7(1 x6x5) + x5(1 x4x3) + x3(1 x2x1)

(1.7)

Y8 = x0

1(1 x0

8x0

7) + x0

7(1 x0

6x0

5) + x0

5(1 x0

4x0

3) + x0

3(1 x0

2x0

1)

(1.8)

o x0

i = 1 xi.

Avec cette m thode le pixel p est simple si et seulement si le nombre de Yokoi vaut

1.

1.4 Les distances discr tes

Comme dans lespace continu, il est possible deectuer des mesures dans les-

pace discret. La distance euclidienne est une mesure de distance entre deux objets

A et B dans le domaine continu. Dans le domaine discret, de nombreux travaux

ont t r alis s pour d nir des distances applicables au domaine discret : les dis-

tances discr tes.

Certains travaux sappliquent calculer la distance euclidienne dE dans le do-

maine discret [35, 72]. Soit deux points p et q et de coordonn es p = (p1, .., pn) et

q = (q1, ..., qn) dans Rn :

dE(p, q) =

q

(q1 p1)2 + ... + (qn pn)2

(1.9)

Dans la suite de ce travail, on se placera dans un contexte s quentiel et en 2

dimensions. Cest pourquoi nous naborderons pas les algorithmes de calcul de

distance en n-dimensions [23, 37, 72, 76, 86, 88, 89] et parall les [27, 35, 72, 78].

1.4.1 D nition

Les distances discr tes ont t introduites par Rosenfeld et Pfaltz dans [79].

On d nit g n ralement la distance comme la longueur du plus petit chemin qui

relie un point un autre.

28

D nition 7 (Distance discr te). Soit une fonction d : Zn Zn N et x, y, z

Zn. On consid re les propri t s suivantes :

1.4. Les distances discr tes

1. d nie positive d(x, y) e 0 et d(x, y) = 0 x = y ,

2. sym trique d(x, y) = d(y, x) ,

3. in galit triangulaire d(x, z) d d(x, y) + d(y, z) ,

4. invariante en translation d(x + z, y + z) = d(x, y) ,

d est appel e une distance si les conditions 1 3 sont v ri es et une distance

invariante en translation si toutes les conditions sont v ri es.

La plupart des distances discr tes peuvent sexprimer comme la longueur du

plus court chemin allant dun point p un autre q. Rappelons quun chemin est

une s quence de points (p0 = p, p1, .., pn = q) dont deux points successifs sont

adjacents.

Le co t ou la longueur dun chemin est le nombre de ces d placements, ici n.

Pour la compr hension de ce chapitre, nous introduisons la notion de boule de

distance ou disque (d nition 8).

D nition 8 (Disque (ou boule)). Soient d une distance, p un point dans X et r

un rayon. Le disque ferm Dd est lensemble :

Dd(p, r) = {q : d(p, q) d r}

(1.10)

Cest- -dire que le point q est un point du disque si sa distance p (le centre

de ce disque) est inf rieure ou gale r (son rayon).

On d nit galement le disque ouvert D< :

D<(p, r) = {q : d(p, q) < r}

(1.11)

Lorsquil ny a pas de pr cision sur la d nomination du disque D, on consid re

un disque ferm . Pour simplier la notation, le disque D(r) d signe le disque ferm

de centre O et de rayon r.

29

Chapitre 1. Lespace discret et distances discr tes

1.4.2 Distances simples

Les premi res distances utilis es sont les distances d4 aussi appel e City Block

distance, Manhattan distance ou Square distance et d8 appel e aussi Chessboard

distance ou diamond distance. Dans [79], Rosenfeld les nomme respectivement d

et d. Dans la suite de ce travail nous les appellerons d4 et d8.

d4(x, y) =

2

X

i=1

|yi xi|

(1.12)

La distance d4 est la longueur du plus petit chemin 4-connexe entre deux

points : p = p0, p1, p2, ..., pn = q o pn et pn1 appartiennent N1. La suite de

disques associ e cette distance est donn e dans la gure 1.15.

D<(1)

D<(2)

D<(3)

D<(4)

Figure 1.15 Suite de disques d4.

De la m me mani re que pour d4, la distance d8 est la longueur du plus pe-

tit chemin 8-connexe entre deux points : p = p0, p1, p2, ..., pn = q o pn et pn1

appartiennent N2(p).

d8(x, y) = max

i=1,2

|yi xi|

(1.13)

Cette distance permet des d placements verticaux, horizontaux et diagonaux.

La suite de disques correspondant cette distance est repr sent e 1.16

30

D<(1)

D<(2)

D<(3)

D<(4)

1.4. Les distances discr tes

Figure 1.16 Suite de disques d8.

Mais ces distances sont une mauvaise estimation de la distance euclidienne car

d4 sur-estime cette distance en diagonale alors que d8 la sous-estime par rapport

aux chemins verticaux et horizontaux. La gure 1.17 montre un disque d4 et un

autre disque d8 et une boule euclidienne de m me rayon. Ainsi on peut se rendre

compte de la di rence des distances discr tes simples par rapport une distance

euclidienne.

Figure 1.17 Disques d4, d8 et boule euclidienne.

Pour rem dier ce probl me, il existe deux autres types de distances. La pre-

mi re que nous allons tudier est la distance s quence de voisinage.

1.4.3 Distances s quence de voisinage

Les distances s quence de voisinage, not es dns, utilisent les deux types de

voisinage N1 et N2. La s quence utilis e, not e B par la suite, est une combinaison

de N1 et de N2.

31

Chapitre 1. Lespace discret et distances discr tes

Cette s quence est utilis e pour cr er une suite de disques en faisant une somme

de Minkowski avec le dernier disque calcul de la suite et lun des deux voisinages

(N1 ou N2) selon la s quence B.

La somme de Minkowski 1.14 associe deux parties P1 et P2 lensemble form des

sommes d l ments de P1 et de P2.

P1 P2 = {p1 + p2 | p1 P1, p2 P2}

(1.14)

L quation 1.15 permet de calculer la suite de disques.

D(p, 0) = {p}, D(p, r) = D(p, r 1) NB(r)

(1.15)

Le premier disque de la s quence contient un seul point, le centre de ce disque p.

Pour calculer les autres disques il sut dutiliser le disque de rayon inf rieur et de

faire une somme de Minkowski avec le voisinage correspondant au rayon du disque

que lon cherche calculer. La gure 1.18 d crit le calcul de D<(3). P1 repr sente

le disque D<(2) dans N1 et P2 repr sente le disque D<(2) dans N2.

=

P1

P2

P1 P2

Figure 1.18 Exemple P1 P2.

La gure 1.19 illustre les disques utilis s pour cr er les chemins suivant la

distance utilis e :

Pour la distance d4, le voisinage utilis pour faire la somme de Minkowski

est N1.

Pour la distance d8 le voisinage utilis pour faire la somme de Minkowski est

N2.

Pour une distance dN S le voisinage utilis pour faire la somme de Minkowski

32

1.4. Les distances discr tes

est d ni par la s quence B Dans cet exemple il sagit de la distance octo-

gonale (doct). Dans cet exemple, B = (1, 2) donc les voisinages utilis s pour

faire la somme de Minkowski sont N1 et N2 alternativement.

D<(1) D<(2)

D<(3)

D<(4)

Distance

d4

Distance

d8

Distance

doct

Figure 1.19 Suites de disques de rayons 1 4 correspondantes aux distances

d4, d8 et doct.

Dans son travail de th se, Nicolas Normand [57] calcule une distance s quence

de voisinage gr ce une succession dop rations de Minkowski. La particularit

de son algorithme r side dans le fait quil d centre le centre des disques. Ainsi il

peut calculer une distance selon un seul balayage de limage.

Rosenfeld introduit la distance octogonale, dans [78], qui utilise une s quence

de voisinage alternant successivement les voisinages N1 et N2. On notera cette

s quence B = (1, 2). Cette distance a t tudi e plus pr cis ment par la suite par

33

Chapitre 1. Lespace discret et distances discr tes

Das dans [36] et ses travaux ont t g n ralis s n dimensions par Nagy dans [56].

Wang et Bertrand [97] calculent doct gr ce une succession dop rations mor-

phologiques (Minkowski) utilisant alternativement di rents l ments sructurants.

Contrairement aux autres approches, Hajdu et Hajdu proposent des distances

s quence de voisinages non p riodiques dans [44]. Pour ce faire, ils utilisent les

s quences de Beatty pour obtenir une s quence et ainsi cr er une suite de disques.

La s quence de B...