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

7.1.2

7.1.3

7.1.4

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

Les points d’intersections . . . . . . . . . . . . . . . . . . . 172

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

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

7.2

Méthode d’extraction 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 d’extraction des caractéristiques os- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 seuses Autres applications . . . . . . . . . . . . . . . . . . . . . . . . . . 204

IV Annexe

205 Temps d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . 207 La base d’images testées . . . . . . . . . . . . . . . . . . . 207 Carte de distance . . . . . . . . . . . . . . . . . . . . . . . 209 Axe médian . . . . . . . . . . . . . . . . . . . . . . . . . . 212 Squelettisation . . . . . . . . . . . . . . . . . . . . . . . . 216 Extraction des caractéristiques osseuses . . . . . . . . . . . . . . . 228 Caractéristiques extraites d’une image d’os. . . . . . . . . 229 Caractéristiques extraites par le logiciel d’odonto . . . . . 238

1.1 1.2 1.3 1.4

2.1 2.2

1 2 3

4

1

2

Production scientifique

Bibliographie

243

245

8

Introduction générale

9

Table des matières

“La médecine est une science des pannes, celles de l’organisme humain... Mais si le médecin est un dépanneur - rien de plus, rien de moins - il est le dépanneur d’une 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 à différents outils de travail. L’imagerie 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 différences avec ou sans pathologie donnée.

Il existe différents types d’imagerie médicale : les rayons X, l’imagerie 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 l’IRM.

À partir des images produites, les médecins peuvent visualiser un état phy- siologique on l’appelle “imagerie structurelle”. Elle donne des informations sur l’anatomie des organes comme la taille ou la forme. Les médecins peuvent égale- ment avoir recours à “l’imagerie fonctionnelle”. Comme son nom l’indique, ce type d’imagerie permet aux médecins de visualiser le fonctionnement d’un organe.

C’est dans ce contexte que se positionne ce travail : caractériser des formes soit d’organes soit de matériaux constituants d’organes. Les mesures s’effectuent sur des formes : c’est la première étape dite de « reconnaissance des formes ». Si on image l’ensemble d’un organe, on peut donc comparer statistiquement les paramètres explicitant la forme de l’organe vis-à-vis d’un ensemble d’organes sains ou atteints d’une maladie spécifique. C’est la seconde étape de « classification de formes ». On pourra ainsi classifier l’organe du patient dans une classe saine/malade en fonction des paramètres de la forme. Si on image une partie d’organe constituée d’un ensemble de petites formes, le même raisonnement s’applique en réalisant des moyennes sur chaque élement de forme élementaire qu’on est capable de dissocier des voisins.

Dans notre étude, nous visons à caractériser l’architecture osseuse ou plus préci- sément l’os trabéculaire. L’os trabéculaire a une architecture particulièrement com- pliquée (forme spongieuse), nous allons mettre en place des traitements d’image

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 d’obtenir 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 d’images que nous souhaitons appliquer nécessitent le stockage

en mémoire de N × N pixels constituants l’image.

Dans ce travail, nous réduisons l’occupation mémoire de ces traitements à 2N pixels. Outre cette meilleure gestion de la mémoire, nous remarquerons l’efficacité 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 l’espace dans lequel nous allons travailler et présenter les traitements d’images que nous allons développer. La seconde partie présente les différentes phases du traitement que nous avons

mis en œuvre.

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

risation de l’os.

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 l’appelation géométrie, la géométrie discrète n’en n’est 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 effet boule de neige, la discre- tisation de l’information nous a forcé à savoir analyser ces données discrètes.

L’utilisation de capteurs, lors de l’acquisition de l’image, 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 difficile d’estimer la distance entre les deux objets à partir d’une photographie de cette même scène. Car au delà du problème d’échelle de l’image de la scène, l’image est composée de pixels dû au mécanisme d’acquisition de celle ci.

C’est dans les années 1960 que des chercheurs français découvrent la morpho- logie mathématique, une discipline de l’analyse d’image. Il a alors fallu apprivoi- ser ce monde discret en commençant par définir l’espace discret. Des notions de connexités de pixels ont permis d’effectuer 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 d’image : le squelette. Le processus de squelettisation est également présenté dans cette partie.

15

Chapitre 1

L’espace 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 l’image est en fait un volume d’images 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 l’espace utilisé en imagerie numérique. Pour faire ce pavage régulier on utilise la même forme que l’on déplace pour remplir le plan. Il existe plusieurs types de pavages (voir figure 1.1). Parmi ces pavages le pavage carré reste le plus utilisé parce qu’il facilite l’extraction des points discrets. Ainsi chaque point a une paire de coordonnées correspondant à l’indice des lignes et des colonnes de l’image 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 l’image). 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 figure 1.1.

17

Chapitre 1. L’espace 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 différentes contraintes :

– Acquisition de l’information ou l’étape de numérisation, – Restitution de l’information (aspect visuel), – Manipulation de l’information. 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éfinition et la caractérisation d’un point simple sont présentées dans la section 1.3.3. La section 1.4 définit ce qu’est une distance, quelles sont ses propriétés et présente ses principales mises en œuvre. Enfin 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éfinitions 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éfinition 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 l’ensemble des points q de coordonnées (xq,yq) qui vérifient :

|xp − xq| + |yp − yq| ≤ 1

(1.1)

On considère qu’un point est voisin à lui-même. De la même manière,

Définition 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 l’ensemble des points q de coordonnées (xq,yq) qui vérifient :

max (|xp − xq| , |yp − yq|) ≤ 1

(1.2)

N1(p) est constitué de p et de l’ensemble 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 figure 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éfinitions, on peut relier 2 points entre eux avec un

chemin.

Définition 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}) à pi−1 pour 1 ≤ i ≤ n.

19

Chapitre 1. L’espace 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 d’une 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 l’on peut transformer l’un en l’autre grâce à la rotation, transla- tion, réflexion, 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 figure 1.4 présente trois objets binaires. Dans cet exemple, la pomme est topologiquement équivalente au marteau. La paire de ciseaux n’est pas topologique à la pomme ni au marteau parce que la paire de ciseaux présente deux trous alors que les deux autres objets n’ont pas de trous.

Figure 1.4 – Formes binaires.

Dans cette section sont abordées des notions relatives à la topologie de l’image. Dans un premier temps, dans la sous-section 1.3.1, une définition des composantes

20

1.3. Notion de topologie d’une image

connexes et un algorithme permettant de les identifier sont présentés. En second lieu, dans la sous-section 1.3.2, le nombre d’Euler et son calcul sont présentés. Enfin, dans la sous-section 1.3.3 la notion de point simple est présentée ainsi que différentes méthodes pour le caractériser.

1.3.1 Les composantes connexes

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

figure 1.5).

Définition 4 (α-connexité). Soit X un ensemble de points. Deux points sont α- connectés si il existe un α-chemin dans X les reliant.

Définition 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 l’exemple de la figure 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 n’existe 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 l’indique, cette fonction distribue une étiquette unique à chaque composante connexe. Si on étiquette à partir de 1 et par ordre

21

Chapitre 1. L’espace 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 figure 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 l’image (de gauche à droite et de haut en bas) et lorsqu’il rencontre un point de la forme, il propage l’étiquette de son voisin haut. Si le point en question n’a pas de voisin il crée une nouvelle étiquette et il attribue à ce point cette nouvelle étiquette comme nous le montre la figure 1.7. Dans cette figure les points déjà balayés sont identifié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 qu’il agrandit à chaque nouvelle étiquette crée. Ainsi lorsque toute l’image a été balayée, il procède à une simplifi- cation du tableau d’étiquettes.

22

1.3. Notion de topologie d’une image

1.3.2 Le nombre d’Euler

Le nombre d’Euler, noté E, ou encore la caractéristique d’Euler est un invariant

topologique [48].

E = S − A + F

(1.3)

Avec S, A et F qui désignent respectivement le nombre de sommets, d’arêtes et de faces.

Dans une image binaire 2D la propriété d’Euler-Poincaré s’exprime de la façon

suivante :

E = O − T

(1.4)

Où O désigne le nombre de composantes connexes dans l’image et T le nombre de trous. Un trou est une composante α−connexe dans le complémentaire de l’image. La figure 1.8 présente deux exemples d’objets binaires. Le nombre d’Euler de la configuration 1.8(a) vaut 0 puisque E = 2 − 2 tandis que dans la configuration illustrée dans 1.8(b), E = 1 − 3.

(a) E = 0

(b) E = −2

Figure 1.8 – Exemple d’objets et leurs nombre d’Euler.

Dans la pratique, un algorithme [41] somme des configurations de pixels pour extraire le nombre d’Euler. Il compte les angles qui forment une convexité et sous- trait les angles formants une cavité. Pour cela il utilise des configurations, dans un voisinage 2 × 2, pondérées. Ces configurations sont illustrées dans la figure 1.9, il faut également ajouter à ces configurations leurs rotations à 90 ◦, 180 ◦ et −90 ◦.

23

Chapitre 1. L’espace discret et distances discrètes

(a) +1/4

(b) −1/4

(c) −1/2

Figure 1.9 – Masques 2 × 2 de configurations pour déterminer le nombre d’Euler.

La figure 1.10 présente deux exemples. Dans le premier, on compte 5 configu- rations de type 1.9(a) et une configuration de type 1.9(b). Le nombre d’Euler est E = 1 Le nombre d’Euler 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 d’Euler.

1.3.3 Points simples

Cette section présente ce qu’est un point simple et comment on le caractérise. Cette notion est utilisée dans le processus d’extraction du squelette, introduit dans le chapitre 2.

Définition

La notion de point simple, introduite par Rosenfeld dans [77], permet d’iden-

tifier les points pouvant être supprimés sans changer la topologie de la forme.

24

1.3. Notion de topologie d’une image

Définition 6 (Point simple). Soit X une partie de Z2 avec un nombre fini de composantes α-connexes et de composantes α-connexes. Un point A de X est α- simple dans X si :

– l’ensemble X et X \ {A} ont le même nombre de composantes α-connexes ; – l’ensemble 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 figure 1.11 illustre un objet et identifie un point p. Si l’on 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 configuration, le point p n’est pas 8-simple. En revanche, si l’on 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 configuration, 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éfinir la simplicité d’un point. En effet le “crossing number” renseigne, grâce au nombre de voisins du point p à étudier, la topologie

25

Chapitre 1. L’espace discret et distances discrètes

locale du sous ensemble de l’objet. La méthode de Rutovitz [80] consiste à compter le nombre de changement de valeur d’un pixel à l’autre 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 figure 1.12 montre l’indexation, 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 figure 1.13(a) montre un cas où le point p n’est 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é d’un point a été étudiée par Hilditch [45].

À la diffé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 d’une image

où bi =

 



1 si x2i−1 = 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 figure 1.14.

p

p

(a) XH (p) = 2

(b) XH (p) = 1

Figure 1.14 – Exemple où le crossing number d’Hilditch vaut 2 et 1.

Dans le premier cas (figure 1.14(a)), le crossing number vaut 2 car le point p n’est pas simple. Dans le second cas (figure 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 figure 1.14.

Exemple 1.14(a)

Exemple 1.14(b)

i 1 2 3 4 i=1 bi

P4

x2i−1 x2i x2i+1 0 0 0 1

0 1 0 1

1 0 1 0

bi x2i−1 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 d’utiliser 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 l’identification des pixels de la figure 1.12.

27

Chapitre 1. L’espace 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 l’espace continu, il est possible d’effectuer des mesures dans l’es- 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éfinir des distances applicables au domaine discret : les dis- tances discrètes. Certains travaux s’appliquent à 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. C’est pourquoi nous n’aborderons 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éfinition

Les distances discrètes ont été introduites par Rosenfeld et Pfaltz dans [79]. On définit généralement la distance comme la longueur du plus petit chemin qui relie un point à un autre.

28

Définition 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éfinie positive d(x, y) ≥ 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(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érifiées et une distance

invariante en translation si toutes les conditions sont vérifiées.

La plupart des distances discrètes peuvent s’exprimer comme la longueur du plus court chemin allant d’un point p à un autre q. Rappelons qu’un chemin est une séquence de points (p0 = p, p1, .., pn = q) dont deux points successifs sont adjacents.

Le coût ou la longueur d’un 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éfinition 8).

Définition 8 (Disque (ou boule)). Soient d une distance, p un point dans X et r un rayon. Le disque fermé D≤ est l’ensemble :

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

(1.10)

C’est-à-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éfinit également le disque ouvert D< :

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

(1.11)

Lorsqu’il n’y a pas de précision sur la dénomination du disque D, on considère un disque fermé. Pour simplifier la notation, le disque D(r) désigne le disque fermé de centre O et de rayon r.

29

Chapitre 1. L’espace 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 pn−1 appartiennent à N1. La suite de disques associée à cette distance est donnée dans la figure 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 pn−1 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 figure 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 diffé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. L’espace 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 l’un des deux voisinages (N1 ou N2) selon la séquence B. La somme de Minkowski 1.14 associe à deux parties P1 et P2 l’ensemble 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 suffit d’utiliser le disque de rayon inférieur et de faire une somme de Minkowski avec le voisinage correspondant au rayon du disque que l’on cherche à calculer. La figure 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 figure 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éfini par la séquence B Dans cet exemple il s’agit 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 d’opérations de Minkowski. La particularité de son algorithme réside dans le fait qu’il décentre le centre des disques. Ainsi il peut calculer une distance selon un seul balayage de l’image.

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. L’espace 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 d’opérations mor- phologiques (Minkowski) utilisant alternativement diffé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 Beatty [16, 17] de paramètre irrationnel α est la séquence des

parties entières des multiples de α :

bαc, b2αc, b3αc, ... = (bnαc)n≥1

(1.16)

Ils définissent une séquence de voisinage comme la séquence des écarts de la

suite de Beatty :

avec 1 ≤ α ≤ 2.

B(r) = brαc − b(r − 1)αc

(1.17)

On utilise la fonction 1B comme compteur d’apparitions de la valeur 1 dans la séquence B (équation 1.18). De la même manière 2B compte le nombre d’appari- tions de la valeur 2 dans la séquence (équation 1.19). Donc pour tous les r :

et

1B(r) = card{i : B(i) = 1, 1 ≤ i ≤ r}

2B(r) = card{i : B(i) = 2, 1 ≤ i ≤ r}

(1.18)

(1.19)

Par commodité on écrit 1B(0) = 2B(0) = 0. On notera que 1B(r) + 2B(r) = r avec r ∈ N. Le tableau 1.2 montre une séquence B(r) et ses correspondants 1B et 2B.

Table 1.2 – Suite de Beatty 4 r 1 2 B 1 2 1 1B 2 0 2B

5 1 3 2

3 1 2 1

6 2 3 3

7 1 4 3

2 2 1 1

8 2 4 4

34

1.4. Les distances discrètes

Pour tout r ∈ N on a 2B(r) = b(α − 1)rc. On notera que l’utilisation de α = 3/2 produit la séquence B = (1, 2). B(r) = b3/2rc − b3/2(r − 1)c = br/2c − b(r − 1)/2c + 1 La figure 1.20 présente les disques de la distance octogonale.

(a) D<(1)

(b) D<(2)

(c) D<(3)

(d) D<(4)

Figure 1.20 – Suite de disques dN S avec B = (1, 2).

1.4.4 Distances de chanfrein

La famille des distances de chanfrein a été introduite par Montanari dans [54] qui propose une distance qui utilise des masques pondérés. On les appelle également les distances pondérées. Le principe de cette distance est de donner des poids aux voisinages. La figure 1.21 illustre différents masques de chanfrein, noté M, avec leurs poids wi =a,b et c.

a

a

a

x

a

(a)

b

a

b

a

x

a

b

a

b

(b)

c

b

a

b

c

c

c

c

c

c

b

a

b

c

a

x

a

(c)

Figure 1.21 – Masques de chanfrein.

Borgefors [22] popularise cette distance grâce à des poids spécifiques comme

d3,4 (où a = 3 et b = 4) ou encore d5,7,11 (où