Institut Gaspard-Monge · Mathématiques Appliquées, Technologies de l’Information et de la Communication · notes

UNIVERSITÉ PARIS DESCARTES École doctorale ED386 de Sciences Mathématiques de Paris Centre Laboratoire Mathématiques Appliquées (MAP5)

UNIVERSITÉ DE CARTHAGE École doctorale de Technologies de l’Information et de la Communication Laboratoire Communication, Signaux et Images (COSIM)

THÈSE Pour obtenir le grade de

Docteur de l’Université Paris Descartes en Mathématiques Appliquées

Docteur de l’Université de Carthage en Technologies de l’Information et de la Communication

Présentée par Rabaa Youssef ep. Douss Squelettisation d’images en niveaux de gris et applications

Dirigée par

M. Frédéric Richard, Professeur à l’Université Aix-Marseille Mme Amel Benazza Benyahya, Professeure à Sup’COM

Soutenue le : 26 novembre 2015

Devant un jury composé de :

Mme Agnès Desolneux , M. Slim Mhiri, M. Hugues Talbot, M. Slim Kanoun, Mme. Christine Chappard, M. Anis Youssef, M. Frédéric Richard, Mme Amel Benazza, Mme. Anne Ricordeau, Mme. Sylvie Sevestre-Ghalila, Maître de conférence détâchée CEA-DRT,

Directrice de recherche CNRS, Maître de conférence HDR à l’ENSI, Professeur à l’ESIEE, Maître de conférence HDR à l’ENIS, Chargée de recherche HDR Inserm, Ph.D et directeur Telnet Innovation Labs., Professeur à l’Université Aix-Marseille, Professeure à SUP’COM, Maître de conférence à Paris 8,

Présidente Examinateur Rapporteur Rapporteur Invitée Invité Co-directeur de thèse Co-directrice de thèse Co-encadrante Co-encadrante

Responsable CEA-Linklab

Thèse ﬁnancée et accueillie par le laboratoire CEA-Linklab

Résumé

L’opération morphologique de squelettisation transforme chaque objet d’une image en une forme linéique qui préserve la topologie de ce dernier (propriété d’homotopie). Elle est lar- gement utilisée en biométrie mais aussi dans la reconnaissance des caractères ainsi que pour l’extraction de la microarchitecture osseuse. L’objectif de cette thèse est de développer une méthode de squelettisation appliquée directement sur les niveaux de gris de l’image, ce qui a pour large avantage de s’aﬀranchir de prétraitement comme la binarisation, nécessaire à une squelettisation binaire. Une revue des méthodes de squelettisation en niveaux de gris permet de constater que l’amincissement est l’une des approches les plus usitées de par sa propriété d’homotopie. Cependant, cette approche est sensible au bruit de l’image et produit des squelettes sur-connectés. Un premier paramétrage de l’amincissement a été proposé dans la littérature aﬁn d’abaisser des conﬁgurations de pixels liées au bruit. La première contribution de ce travail est de proposer un ajustement de ce paramètre basé sur une décision statistique. Il s’agit d’identiﬁer les tests d’hypothèses correspon- dants aux diﬀérentes conﬁgurations d’abaissement en vue de ﬁxer ce paramètre de façon locale. Ceci conduit à la mise en place d’une squelettisation par amincissement appelée Self Contrast Controlled Thinning (SCCT) puisque robuste au bruit tout en s’adaptant automatiquement au contraste de l’image. La squelettisation SCCT est rendue accessible aux domaines d’application grâce à son implantation optimisée basée sur les ﬁles d’attente hiérarchiques. Ayant noté le peu d’eﬀorts consacrés à l’évaluation de la squelettisation en niveaux de gris, la deuxième contribution de ce travail est de proposer un protocole visant à évaluer l’opération de squelettisation sur la base de l’ensemble des propriétés requises à savoir la préservation de la topologie et de la géométrie. Ce protocole est déroulé sur une base d’images synthétiques et nous permet de comparer notre approche à celles de la littérature. La troisième contribution est de proposer une structuration du squelette en graphe donnant accès aux descripteurs structurels et morphométriques des objets étu- diés, à la base de l’exploitation du squelette par les experts des domaines d’applications. Dans le cadre du projet Voxelo coordonné par le laboratoire B2OA de l’Université Paris Diderot, cette structuration est exploitée pour extraire d’images RX haute résolution les descripteurs de la qualité de la microarchitecture osseuse.

Dédicace

Je dédie ce travail à mes chers parents et à mes beaux-parents, à mon tendre mari qui m’a soutenue sans relâche, à mes frères et sœur, mes modèles de réussite professionnelle et personnelle, à mes belles sœurs et mon beau frère, à mes neveux et nièces, mon rayon de soleil, à tous ceux qui ont veillé à ce que ce travail soit à la hauteur.

Remerciements

A l’issue de ces années de thèse, je suis convaincue que le travail qui m’a été conﬁé est loin d’être uniquement scientiﬁque. C’est un apprentissage qui ﬁnit par nous inculquer la patience, la persévérance, l’échange, le don de soi et le respect de tout eﬀort qui ait pu contribuer, de près ou de loin, à atteindre la ligne d’arrivée.

Mes remerciements vont particulièrement à Madame Sylvie Sevestre-Ghalila, Maître de Conférences détachée au CEA-DRT et responsable de la plateforme de recherche CEA-Linklab, pour l’aide et le temps qu’elle m’a consacré, autant pour améliorer la qualité de mon travail que pour me soutenir dans les moments diﬀciles. Chaque discussion avec elle est une vraie motivation et un vrai encouragement vers l’avant.

Je remercie mes directeurs de thèse, Madame Amel Benazza, Professeure à Sup’COM et Monsieur Frédéric Richard, Professeur à l’Université Aix-Marseille qui malgré les longues années de thèse, ont continué à croire en moi et m’ont soutenue jusqu’à la ﬁn.

Je remercie Mme Ricordeau, Maître de Conférences à l’Université Paris 8 et co-encadrante de cette thèse qui par sa rigueur et sa patience, m’a amenée à comprendre en profondeur tout ce que j’entreprenais.

Ce travail a été ﬁnancé pendant ces trois dernières années par le projet ANR-Voxelo et réalisé en partie au CEA-LinkLab, plateforme commune de recherche entre le CEA-LIST et Telnet Innovation Labs. De ce fait, je tiens aussi à remercier Mme Christine Chappard, Chargée de recherche à l’Inserm et coordinatrice du projet Voxelo et M. Anis Youssef, directeur de Telnet Innovation Labs pour m’avoir donné la possibilité d’appliquer ma contribution aux domaines respectifs d’imagerie médicale et de biométrie.

Je remercie les rapporteurs M. Hugues Talbot, Professeur à l’ESIEE et M. Slim Ka- noun, Maître de conférence HDR à l’ENIS, qui ont bien voulu rapporter mon travail.

J’exprime ma gratitude aux membres de mon jury de thèse : Mme Agnès Desolneux, HDR et Directrice de Recherche CNRS à ENS-Cachan, et M. Slim M’hiri, Maître de Conférences HDR à l’ENSI, d’avoir accepté d’évaluer ce modeste travail.

Je tiens également à remercier ici l’ensemble de l’équipe du CEA-LinkLab, Mme Meriem Jaidane Professeure à l’ENIT, Neska, Amira, Nader, Yosra et Khawla. Nos nombreux échanges ont contribué à créer une synergie qui fait que l’équipe est plus que la somme individuelle de ses membres.

Table des matières

Introduction générale

1 Contexte général de la squelettisation par amincissement

i ii iii iv v

1.2 Méthodes de squelettisation des images en niveaux de gris

1.1 La squelettisation : déﬁnition et propriétés . . . . . . . . . . . . . . . . . . 1.1.1 Propriétés d’un squelette . . . . . . . . . . . . . . . . . . . . . . . . L’homotopie . . . . . . . . . . . . . . . . . . . . . . . . . La préservation de la géométrie . . . . . . . . . . . . . . . L’épaisseur unitaire . . . . . . . . . . . . . . . . . . . . . . La reconstructibilité . . . . . . . . . . . . . . . . . . . . . L’invariance au bruit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Approches analytiques . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Approches morphologiques . . . . . . . . . . . . . . . . . . . . . . . 1.3 Amincissement binaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 L’amincissement : du contexte binaire au gris . . . . . . . . . . . . . . . . 1.4.1 Déﬁs de l’amincissement gris classique 1.5 Amincissement paramétré . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.1 Notions topologiques de l’amincissement paramétré . . . . . . . . . 1.5.2 Algorithmique de l’amincissement paramétré . . . . . . . . . . . . . 1.5.3 Analyse du comportement de l’amincissement paramétré au cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Pink et son implantation de l’amincissement paramétré . . . . . . . . . . . 1.6.1 Options du λ-Skeleton . . . . . . . . . . . . . . . . . . . . . . . . . 1.6.2 Réglage du paramètre de l’amincissement . . . . . . . . . . . . . . .

des itérations

2 Contribution à la squelettisation par amincissement

2.1 Révision des conditions d’abaissement des pics et des extrémités . . . . . . . . . . . . . . . . . 2.2 Tests statistiques relatifs aux conditions d’abaissement 2.2.1 Première évaluation empirique du paramètre λ . . . . . . . . . . . . 2.2.2 Première approche statistique pour l’ajustement de λ par la loi de l’étendue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.3 Tests statistiques pour la décision d’abaisser pic et extrémité . . . . 2.2.4 Fusion de tests d’hypothèses pour l’abaissement des λ-crˆetes . . . . 2.2.5 Estimation des paramètres de notre proposition . . . . . . . . . . . 2.3 Optimisation algorithmique de notre méthode SCCT . . . . . . . . . . . . 2.3.1 Déﬁs algorithmiques du λ-amincissement . . . . . . . . . . . . . . .

17 19 19 19 19 20 20 20 20 20 21 22 26 29 31 31 32

34 37 37 40

42 43 46 46

47 50 52 55 56 57

TABLE DES MATIÈRES

i ii iii iv

Dépendance au parcours . . . . . . . . . . . . . . . . . . . Procédure séquentielle . . . . . . . . . . . . . . . . . . . . Tri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Complexité des notions topologiques . . . . . . . . . . . . 2.3.2 Fonctionnement FAH et applications aux outils de la morphologie mathématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 Contributions pour l’optimisation de l’implantation de SCCT . . . Notre implantation des FAHs . . . . . . . . . . . . . . . . Comparaison des implantations SCCT et λ-Skeleton . . . Autres améliorations de l’implantation du SSCT . . . . . . 2.4 Discussion sur l’impact du bruit et du contraste sur notre méthode SCCT .

i ii iii

3 Proposition d’un protocole d’évaluation des méthodes de squelettisation

sur des images synthétiques 3.1 Revue des protocoles d’évaluation de la squelettisation existants . . . . . . 3.1.1 Propriétés évaluées du squelette . . . . . . . . . . . . . . . . . . . . 3.1.2 Données idéales et leurs perturbations . . . . . . . . . . . . . . . . 3.1.3 Mesures d’évaluation binaire . . . . . . . . . . . . . . . . . . . . . . Opérateur Area . . . . . . . . . . . . . . . . . . . . . . . . Méthode du buﬀer . . . . . . . . . . . . . . . . . . . . . . Distance de Hausdorﬀ et sa variante . . . . . . . . . . . . Connectivité du squelette . . . . . . . . . . . . . . . . . . Score de performance . . . . . . . . . . . . . . . . . . . . . 3.2 Proposition d’un protocole d’évaluation . . . . . . . . . . . . . . . . . . . . 3.2.1 Génération des images synthétiques . . . . . . . . . . . . . . . . . . 3.2.2 Critères d’évaluation et mesures . . . . . . . . . . . . . . . . . . . . 3.2.3 Réglage des paramètres des 3 méthodes de squelettisation à évaluer 3.2.4 Résultats de l’évaluation . . . . . . . . . . . . . . . . . . . . . . . .

i ii iii iv v

57 57 57 57

57 59 59 62 63 64

69 70 71 72 75 77 78 80 82 83 84 85 87 89 91

4 Structuration du squelette en graphe pour une exploitation haut niveau

par ses attributs 4.1 Caractérisation des structures curvilignes par les attributs d’un squelette et 98 son graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Attributs utilisés pour l’étude d’un squelette . . . . . . . . . . . . . 98 4.1.2 Utilité du graphe d’un squelette . . . . . . . . . . . . . . . . . . . . 101

4.2 Notre contribution : Extraction d’attributs par construction de graphe et

ébarbulage en niveaux de gris . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.2.1 Phase de binarisation . . . . . . . . . . . . . . . . . . . . . . . . . . 102 Identiﬁcation des conﬁgurations topologiques des pixels du squelette 103 4.2.2 4.2.3 Construction du graphe à partir du squelette . . . . . . . . . . . . . 104 4.2.4 L’extraction d’attributs . . . . . . . . . . . . . . . . . . . . . . . . 109 4.2.5 Procédure d’ébarbulage suivant la longueur et le niveau de gris

moyen des segments

. . . . . . . . . . . . . . . . . . . . . . . . . . 110

TABLE DES MATIÈRES

5 Applications

114

5.1 Analyse de la microarchitecture de l’os sous-chondral du tibia dans le cadre

du projet Voxelo 5.1.1 Protocole semi-automatique d’extraction de ROIs de l’os sous-chondral

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

sur images HR-pQCT . . . . . . . . . . . . . . . . . . . . . . . . . . 116 Segmentation semi-automatique de l’os . . . . . . . . . . . 117 i Construction automatique de l’enveloppe convexe et dé- ii coupage en ROIs . . . . . . . . . . . . . . . . . . . . . . . 120 Evaluation de la méthode d’extraction : résultats et dis- cussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

iii

5.1.2 Application de la squelettisation SCCT et de l’extraction d’attributs

aux images du projet Voxelo . . . . . . . . . . . . . . . . . . . . . . 126 Comparaison qualitative des méthodes de squelettisation . 127 i Résultats de l’extraction de paramètres morphométriques ii sur un genou . . . . . . . . . . . . . . . . . . . . . . . . . 132 5.2 La squelettisation appliquée à des lettres manuscrites et image biométrique 133 5.2.1 Applications d’intérêts . . . . . . . . . . . . . . . . . . . . . . . . . 133 5.2.2 Réglage des paramètres des méthodes de squelettisation . . . . . . . 134 5.2.3 Résultats et Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 135

Conclusion générale

Publications scientiﬁques

138

141

Annexe 1 : Détection de structures curvilignes par la géométrie diﬀéren-

tielle

Bibliographie

143

148

Table des ﬁgures

C1 et

81. (b) : Image d’intersection 100

1.2 Exemple de composantes connexes du fond et de l’objet.

neaux 81 151 inversion des couleurs.

aléatoires de la liste Moyenne des squelettes de 10 parcours aléatoires de image. (a) : simple. (b) : pic. (c) : extr´emit´e.

1.1 Voisinage du pixel central x (en rouge). A gauche : les voisins 4-connexes sont en blanc. A droite : les voisins 8-connexes sont en blanc. . . . . . . . . C2 : compo- santes 4-connexes du fond . En blanc : la composante 8-connexe de l’objet. 1.3 Conﬁguration topologique du pixel central x. (a) : simple, (b) : pic, (c) : extr´emit´e. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Cas d’amincissement binaire sur images synthétiques : (a) : Image d’an- 100. (c) : Image d’un réseau 121. (d),(e),(f) : Résultat de l’amincissement de (a),(b) et (c) après . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Dépendance au parcours : S1 et S2 squelettes obtenus par diﬀérents parcours pour les images binaires de la ﬁgure 1.4. Smoy : obtenus pour chaque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 1.7 Dépendance au parcours : S1 et S2 squelettes obtenus par diﬀérents parcours pour l’image en niveaux de gris I. Smoy : Moyenne des aléatoires de la liste obtenus pour I. Sapp. : squelette squelettes de 10 parcours aléatoires de obtenu en suivant l’ordre d’apparition. Sր : squelette obtenu en triant la liste L à chaque itération selon les niveaux de gris ascendants. . . . . . . . 1.8 Exemple sur un proﬁl de ligne de la progression des abaissements des ni- veaux de gris lors d’un amincissement suivant un tri ascendant des niveaux de gris des pixels de la liste L. . . . . . . . . . . . . . . . . . . . . . . . . . 121 dont les niveaux de gris varient dans [0..1]. (a) : Squelette en rouge superposé au relief idéal. (b) : Ajout d’un bruit gaussien σ = 0.03 à l’image (a). (c) : Squelette gris de (b) en utilisant un fond clair pour distinguer les crêtes faiblement contrastées. (d) : Proﬁl de l’image idéale (a) et son squelette en . . . . . . . . . pointillé. Proﬁl de l’image (b) et son squelette (c) en gras. 1.10 Trois exemples de conﬁguration de pixel λ-crˆete. (a) : x est λ-crˆete pour C4 sont les composantes du C2, C1, K fond 4-connexes et 4-adjacentes au pixel x. En blanc : les pixels du voisinage de x qui séparent le fond en . . . . . . . . . . . . . . . . . composantes. 1.11 Traitement ne respectant pas l’ordre ascendant au cours des itérations de l’amincissement paramétré . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.9 Amincissement basique appliqué sur une image synthétique 153

= 3 et (c) :

= 2, (b) :

C3 et

= 4.

26 27

TABLE DES FIGURES

1.12 Traitement respectant l’ordre ascendant au cours des itérations de l’amin- cissement paramétré. Les deux crêtes ﬁnales b et g sont préservées. . . . . . 1.13 Abaissements au cours de la 1ère et la 3ème itération de l’amincissement paramétré sur une image synthétique bruitée (σ = 5) avec λ = 12 . . . . . 1.14 Nombre de pixels simple, λ-crˆete, λ-pic and λ-extr´emit´e abaissés au cours des 15 premières itérations de l’amincissement paramétré appliqué à l’image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . de la ﬁgure 1.9. 1.15 Description d’un pixel λ-abaissable. . . . . . . . . . . . . . . . . . . . . . . 1.16 Squelettisation par λ-Skeleton de l’mage synthétique de la ﬁgure 1.9 avec λ = 25. (a) : ajout d’un bruit gaussien d’écart-type σ = 5. (b) : Squelette sans pic avec extr´emit´e. (c) : Squelette sans pic et sans extr´emit´e. (d) : Squelette avec pic et avec extr´emit´e. (e) : Squelette avec pic et sans extr´emit´e. 39

36 37

1.17 Résultats du λ-Skeleton sur d’autres images synthétiques : Anneaux (300 300) avec bruit gaussien additif d’écart-type σ = 5.1 et Intersection (100 100) avec σ = 12.49 .

× × . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.18 Résultats du λ-Skeleton pour diﬀérentes valeurs de λ sur l’image synthé- tique de la ﬁgure 1.9 après avoir fait varier le contraste entre les branches verticales et horizontales. σbruit = 5. . . . . . . . . . . . . . . . . . . . . . .

2.1 Ordre de traitement des conﬁgurations λ-dépendantes au cours des instruc- tions d’abaissement du λ-Skeleton. λ-Skeleton appliqué sur l’image synthé- tique de test de la ﬁgure 1.16.(a) pour obtenir le squelette de la ﬁgure 1.16.(d). 44 47

bas.

2.2 Evolution linéaire du paramètre λ en fonction de σ avec une pente u = 2.6. 2.3 Histogrammes de données simulées pour n = 2 et n = 6. Taille de l’échan- tillon utilisé : 10000 et tableau τn au niveau de conﬁance α = 0.05 . . . . . Y(n−1) : Taille de l’échantillon utilisé : 10000. . . . = 2. En vert, .

2.4 Histogramme des simulations de Y(n) − 2.5 Graphe dee α = f (α0). En bleu = 3. En rouge, K 2.6 Courbe τn en fonction de α pour n = 2, 3, 4, 5, 6 et dans le cas où 2.7 Fonctionneent de la FAH : premier empilement se fait à un niveau de gris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Organigramme de l’implantation du λ-amincissement. . . . . . . . . . . . . 2.9 Evolution des niveaux de gris des pixels abaissés lors des dépilement de la FAH pour la méthode λ-Skeleton (en vert) et notre méthode SCCT (en rouge). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 Construction de l’image des lignes horizontales. Dinf et Dsup indiquent res- pectivement la distance minimale et maximale entre le fond et l’objet dans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . une même image. 2.11 Résulats de la squelettisation SCCT pour diﬀérents bruits et niveau de test α. L’image admet un contraste Dinf = 50, Dsup = 95 par rapport au fond. . 2.12 Résulats de la squelettisation SCCT pour diﬀérents bruits et niveau de test

= 4. = 2.

K K

49 50 54 55

58 60

α. L’image admet un contraste Dinf = 110, Dsup = 140 par rapport au fond. 66

2.13 Résulats de la squelettisation SCCT pour diﬀérents bruits et niveau de test

α. L’image admet un contraste Dinf = 140, Dsup = 200 par rapport au fond. 67

3.1 Exemples d’images de la base MPEG7 : perturbations par rotation, distor- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

sion de contours.

TABLE DES FIGURES

3.10 Première ligne : Les squelettes de référence binaires S∗

Illustration de la diﬀérence entre squelette réel S et squelette idéal S∗

3.2 Exemples de formes de la base de Kimia. . . . . . . . . . . . . . . . . . . . 3.3 Exemples de lettres arabes de la base IFN/ENIT . . . . . . . . . . . . . . . . . . . . . . 3.4 3.5 Conﬁgurations Qk : le pixel entouré est toujours simple. . . . . . . . . . . 3.6 Appariement de la référence et de l’extraction par la méthode du buﬀer sur une ligne droite représentant le squelette. . . . . . . . . . . . . . . . . . . . 3.7 Exemple 1 : Segments de deux squelettes S∗ et S . . . . . . . . . . . . . . 3.8 Exemple 2 : S∗ et S où un pixel lié au bruit est ajouté à S2 . . . . . . . . 3.9 Distance de Hausdorﬀ entre deux courbes ne reﬂétant pas la préservation de la géométrie. En noir les pixels du premier objet S. En gris les pixels du second objet T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . I . Deuxième ligne : images en niveaux de gris lisses avec une diﬀérence moyenne de contraste D entre le fond et l’objet. Troisième ligne : Images de la deuxième ligne bruitées par un bruit gaussien additif. IR : 326 121, I∩ : 100 100. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.11 Application du buﬀer width pour le calcul de Cp et Cr avec une tolérance r = 3. Ligne 1 : σ = 2.5 et α = 10−2. Ligne 2 : σ = 5.1, α = 10−3. Ligne 3 : σ = 2.5, α = 10−4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12 Graphe d’évaluation sur les 3 images synthétiques utilisant 5 mesures quan- titatives. Bruit gaussien additif variant de σnoise = 2 à 12 avec un pas de 0.5. Mesures : Cp Complétude, Cr, BCC, OCC etE. Méthodes évaluées : (Pink1) : ni extrémités ni pics maintenus. (Pink2) : pics supprimés et extré- mités maintenues. (DLD) : méthode diﬀérentielle. (SCCT) : notre méthode.

326, IN : 150

N and S∗

R, S∗

3.13 Résultats sur les images d’intersection et des anneaux. Un bruit gaussien additif d’écart-type σ = 12.49 est appliqué. Pink1 : suppression de tous les pics et extrémités. Pink2 : maintien des extrémités et suppression des pics. 3.14 Résultats sur l’image du réseau synthétique. Un bruit gaussien additif d’écart- . . . . . . . . . . . . . . . . . .

type σ = 2.55 puis σ = 12.49 est appliqué.

4.1 Composition d’un système biométrique . . . . . . . . . . . . . . . . . . . . 4.2 Etapes de traitement et d’extraction de minuties du réseau veineux de la

73 74 75 78

79 80 81

main . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 4.3 Étapes de traitement et d’extraction de minuties de l’empreinte digitale . . 101 4.4 Étapes d’extraction des paramètres morphométriques. . . . . . . . . . . . . 102 4.5 Conﬁguration d’un voisinage où le squelette gris est ﬁn et son équivalent

binaire non ﬁn.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.6 Conﬁgurations topologiques possibles des pixels du squelette. . . . . . . . . 104 . . . . . . . . . . . . . . . . . . 105 4.7 Décomposition possible d’amas de nœuds. 4.8 Squelette labellisé contenant plusieurs conﬁgurations de structure point. . . 105 4.9 Exemple des diﬀérents types de segments avec leurs labels respectifs. . . . 106 4.10 Segment à tête multiple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 . . . . . . . . . . . . . . . . . . . . . . . 107 4.11 Deux segments entre deux points. 4.12 Un exemple de conﬁguration des segments et le graphe associé. . . . . . . . 108 4.13 Résultat de la squelettisation par SCCT et λ-Skeleton. Intensité de bleu

reﬂétant la longueur des segments.

. . . . . . . . . . . . . . . . . . . . . . 111

TABLE DES FIGURES

5.1 Anatomie du genou et déﬁnition des compartiments sur une coupe trans-

versale du tibia. Image DICOM 16 bits 1400

1400. . . . . . . . . . . . . . 117 5.2 Exemple d’histogramme d’une image DICOM de coupe au niveau du tibia. 118 . . . . . . . . . . . . . . 119 5.3 Gauche : image DICOM. Droite : masque binaire. 5.4 Volume de l’os après séparation du tissu mou environnant. En rouge le

5.5

. . . . . . . . . . . . . . . . . . . 120

parallélépipède circonscrit hypothétique. (a) et (b) : Première et dernière coupe du volume d’intérêt au niveau du tibia avec leurs enveloppes convexes respectives. (c) : Union des enveloppes convexes superpose à la première coupe du volume. (d) : En jaune, le rec- tangle circonscrit base du parallélépipède et en bleu, les sommets du rectangle.121 5.6 Coupe partitionnée en ROIs avec leurs labels respectifs. . . . . . . . . . . . 122 5.7 Protocole semi-automatique de l’extraction des compartiments de l’os sous-

chondral du tibia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

5.8 Variation du seuil facilement supervisé par l’utilisateur. Gauche : q = 0.89 (présence de tissu mou). Centre : q = 0.87 (le bon seuil). Right : q = 0.85 (défaut dans l’os). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

5.9 Résultats du BV/TV en % pour chaque compartiment divisé en 3 segments

à partir de la surface articulaire. . . . . . . . . . . . . . . . . . . . . . . . . 125

5.10 image HR-pQCT du projet Voxelo (1400

× compartiment latéral postérieur à traiter (249 selon la ligne en noir dans l’image.

1400) avec une sélection du 241). Le proﬁl 1D est tracé

. . . . . . . . . . . . . . . . . . . . . . 127

5.11 Squelettes superposés à l’image initiale. (DLD) : Résultat pour s = 2.5 et les σbruit = 4

seuils hystérésis l = 0.2 et u = 0.8. (SCCT) : Notre résultat pour et α = 5.10−2. (Pink) : Résultat du λ-Skeleton pour

. . 128 5.12 Segmentation et squelettisation de deux coupes du volume d’intérêt. . . . . 130 5.13 Exemple d’extraction de régions d’intérêt sur une coupe segmentée avec

σbruit = 16. b

λ = τn.

leurs squelettes respectifs.

. . . . . . . . . . . . . . . . . . . . . . . . . . . 131

5.14 Variation du nombre de nœuds et du nombre de segments par ROIs pour l’ensemble du volume d’intérêt. L1 : Compartiment médial postérieur. L2 : latéral postérieur. L3 : médial antérieur. L4 : latéral antérieur.

5.15 Image d’empreinte digitale de la base FVC2000 (215 5.16 Exemple de lettres manuscrites persanes. Carré noir délimite la région où

189).

. . . . . . . 132 . . . . . . . . 133

on estime le bruit.

σbruit = 7.93.

. . . . . . . . . . . . . . . . . . . . . . . . 134

5.17 Résultats de la squelettisation sur l’image d’empreinte. (DLD) : Résultat σbruit = 16 and

pour s = 1.8, l = 3 et u = 6. (SCCT) : Notre résultat γ = 10−5. (Pink) : Résultat du λ-Skeleton

λ = τn.

. . . . . . . . 135

5.18 Résultats de la squelettisation sur l’image des lettres persanes. (DLD) : Résultat de DLD pour s = 1.5, l = 7 et u = 21. (SCCT) : Notre résultat σbruit = 7.93 et γ = 10−3. (Pink) : Résultat du λ-Skeleton

λ = 30.

. . . . . 136

σbruit = 80. b

5.19 Une image synthétique 153 b mitée par le rectangle.

121 et son proﬁl surfacique dans la zone déli- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 . . . . . . . . . . . . . . . . . 145 5.20 Localisation d’un point crête sur une image. 5.21 Exemple de suivi de segment entre deux pixels crêtes P1 et P2. . . . . . . . 146 5.22 (a) : fonction parabolique f (x) = 1 de paramètre d’échelle σ variable.

− . . . . . . . . . . . . . . . . . . . . . . . 147

(x/w)2 convolué à un noyau gaussien

Liste des tableaux

RAM Quadcore. Image de test de la Figure 1.9.

2.1 Calcul de α0 en fonction de α et du nombre de composantes connexes . . 2.2 Temps d’exécution des notions topologiques sur une machine 64bits/16G . . . . . . . . . . . . . . .

57 2.3 Méthode de génération des labels pour toutes les conﬁgurations d’un voisinage 63 2.4 Temps d’exécution des tests d’abaissement pour les diﬀérentes conﬁgura- tions sur 3 images diﬀérentes. Machine 64bits 16G RAM Quadcore. Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . d’exécution "Debug". 2.5 Temps d’exécution de l’amincissement par ajustement local du contraste SCCT sur une Machine 64bits 16G RAM Quadcore. Mode d’exécution "Re- . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . lease".

76 . . . 3.1 Tableau comparatif des protocoles existants selon le type de données. 3.2 Evaluation de la squelettisation : de la propriété à la mesure. . . . . . . . . 84 3.3 Réglage des paramètres des méthodes concernées par le protocole d’évaluation. 90 94 3.4

Indicateurs moyens pour chaque méthode.

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

4.1 Structure de données : P oint . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.2 Structure segment. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.3 Tableau des structures segments de la Figure 4.12. . . . . . . . . . . . . . 108

5.1 Tests de Reproductibilité de l’extraction de ROIs. 5.2 Erreur de déviation pour un quantile variant de

. . . . . . . . . . . . . . 123 0.02. . . . . . . . . . . . 124

Introduction générale

La squelettisation d’une image vise à fournir une représentation ﬁlaire des objets qu’elle contient. Son objectif est de préserver l’essentiel de l’information portée par chacun des objets sous une forme simple. C’est aussi une manière de les représenter indépendam- ment de leurs épaisseurs initiales. Dans l’espace continu, le squelette a été déﬁni par Blum [1] comme le lieu des centres de boules maximales. Il n’existe cependant pas de déﬁnition unique du squelette dans l’espace discret. C’est pourquoi, on se limite à garantir un nombre de propriétés telles que l’unicité d’épaisseur du squelette, la préservation de la géométrie et de la topologie de l’objet, l’invariance du squelette face au bruit, sa robustesse aux transformations aﬃnes et pour certaines applications sa reversibilité permettant de reconstruire l’objet initial.

L’intérêt porté aux méthodes de squelettisation a débuté par la reconnaissance de carac- tères dans les années 90 [2]-[3]-[4] et continue à ce jour [5]-[6]-[7]. Ensuite, d’autres domaines d’application se sont intéressés à la squelettisation tels que la biométrie [8]-[9]-[10]-[11]- [12], l’extraction de routes [13]-[14]-[15]-[16]-[17], l’imagerie médicale pour l’analyse de la vascularisation tumorale [18], la détection de vaisseaux sanguins pour l’angiographie à ré- sonance magnétique [19] ou la caractérisation de la microarchitecture de l’os [20]-[21]-[22].

De multiples méthodes de squelettisation sur images binaires ont été proposées dans la littérature. Toutefois, l’application de ces méthodes aux images réelles et donc, en ni- veaux de gris, nécessite des techniques de prétraitement permettant la binarisation des données en entrée. Outre le fait qu’elles représentent des étapes à ajouter en amont à la chaîne d’analyse d’images (reconnaissance, caractérisation d’objets etc), ces étapes de prétraitement et de binarisation génèrent une perte d’information et dans la plupart des cas, une dégradation de la qualité et de la pertinence des squelettes obtenus. Le succès de cette opération de traitement d’images dans les diﬀérents domaines d’application a donc conduit à l’évolution des méthodes de squelettisation vers le traitement direct des images en niveaux de gris pour s’aﬀranchir de cette étape de binarisation. Dans ce nouveau contexte, les déﬁs majeurs de la squelettisation résident toujours dans la préservation de la connexité (l’homotopie) et de la géométrie des objets à traiter ainsi que dans la robustesse au bruit. Ces propriétés du squelette représentent une priorité dans notre contribution à la squelettisation compte tenu des applications visées, à savoir l’image- rie médicale pour l’extraction de la micro-architecture osseuse, l’identiﬁcation biométrique et la reconnaissance de caractères qui se basent sur les caractéristiques topologiques des objets.

INTRODUCTION GÉNÉRALE

On choisit de classer les méthodes de squelettisation en niveaux de gris en trois grandes catégories d’approches, tout en suivant un ordre chronologique d’apparition des méthodes de chaque classe. La première catégorie de méthodes se base sur la géométrie diﬀérentielle pour localiser les pixels « crêtes » d’un squelette. Ces approches considèrent l’image comme une fonction et en extraient les lignes centrales des objets en utilisant les propriétés de la géométrique dif- férentielle. Les auteurs de [23] utilisent une transformée en distance appliquée sur l’image du gradient aﬁn de calculer un score qui permet de localiser les crêtes du squelette. Cette technique repose sur l’hypothèse de proﬁls symétriques pour les objets à traiter et n’est donc pas adaptée à des objets quelconques. Dans [24], les auteurs modélisent l’évolution des courbes de niveaux de l’objet à l’aide des équations diﬀérentielles partielles classique- ment utilisées par les méthodes de contours actifs. Les points de plus forte courbure de ces courbes d’évolution représentent des points du squelette que les auteurs lient entre eux pour construire le squelette ﬁnal. Quant à la proposition détaillée dans [25], elle consiste en une modélisation de l’opération morphologique d’érosion par des équations diﬀéren- tielles partielles aﬁn d’appliquer itérativement cette opération à l’image jusqu’à obtenir le squelette de l’objet. Une autre méthode de la géométrie diﬀérentielle [26] consiste à modé- liser un objet en niveaux de gris comme une surface et à utiliser la direction maximisant la courbure concave de surface pour localiser les points de crêtes. Une fois ces points de crêtes détectées, un suivi est opéré aﬁn de reconnecter le squelette ﬁnal. D’autres auteurs combinent la géométrie diﬀérentielle à l’analyse sémantique des régions de l’image [27] ou aux contours actifs encore une fois [28]. Ces méthodes diﬀérentielles peuvent opérer sur diﬀérentes échelles et ont l’avantage de produire des squelettes robustes au bruit. Néan- moins, ces techniques ne mettent aucune condition sur la préservation de la topologie des objets, ce qui limite leur utilisation dans des applications qui requièrent l’extraction de caractéristiques topologiques telles que les jonctions.

Une autre catégorie de méthodes de squelettisation en niveaux de gris est basée sur les transformées en distance ou l’extraction de carte de distances aﬁn d’identiﬁer l’axe médian. Ces méthodes sont répandues dans le contexte d’images binaires. Quelques au- teurs ont proposé d’étendre leur utilisation aux images en niveaux de gris [29, 30, 31]. Certaines de ces méthodes requièrent une segmentation implicite [29, 30] aﬁn d’identiﬁer les pixels "objets" voisins du fond. C’est à partir de ces pixels qu’une carte de distance est calculée, partant de ces pixels de bord et allant vers les hauteurs du relief topographique que représente un objet en niveaux de gris. Outre la nécessité de prétraitement tel que la segmentation du fond, ces méthodes ne mettent aucune contrainte sur la connexité du squelette et ne sont donc pas adaptées aux applications visées par cette thèse.

La troisième catégorie est celle de l’amincissement basée sur la topologie discrète qui a pu évoluer du cadre binaire au gris. En eﬀet, l’amincissement séquentiel ou parallèle d’images binaires a été largement étudié dans le cadre des applications de reconnaissance de caractères, soulignant ainsi leur rôle dans l’extraction de descripteurs structurels à la base de l’appariement d’objets. Ces méthodes appliquées aux images binaires procèdent par l’élimination de pixels qui ne changent pas la connexité jusqu’à atteindre l’axe mé- dian de l’objet. Elles maintiennent les branches libres en bloquant la suppression de pixels extr´emit´es comme proposé par [32]. Le déﬁ de l’application de cette catégorie de méthodes

INTRODUCTION GÉNÉRALE

aux images en niveaux de gris, qu’elles soient parallèles ou séquentielles, réside soit dans la déﬁnition de la connexité en niveaux de gris, soit dans la déﬁnition de nouveaux critères d’amincissement ou dans la segmentation implicite de l’image. Dans la famille des amincissements parallèles, les auteurs de [33] proposent de binariser le fond et de traiter les niveaux de gris de l’objet dans un ordre croissant. Les auteurs suppriment des pixels en partant du bord de manière à ne pas changer la topologie de l’objet. Quant aux méthodes proposées dans [34, 35], aucune segmentation n’est requise et le squelette est ﬁdèle à la connexité de l’objet initial grâce à l’utilisation de critères d’amincissement indépendants de l’ordre de passage. Par ailleurs, les auteurs de [36] déﬁ- nissent les critères d’amincissement séquentiel dans l’espace topologique connexe ordonné et parviennent ainsi à paralléliser l’opération d’amincissement. Dans un autre travail, le cadre des noyaux critiques est utilisé aﬁn de proposer un amincissement parallèle [37]. Les méthodes d’amincissement parallèle citées ci-dessus sont homotopiques sans garantir une robustesse au bruit. Dans la famille des amincissements séquentiels, les auteurs de [38] utilisent une formule de pondération exprimant la connexité en niveaux de gris. En eﬀet, ils binarisent le voisinage d’un pixel en fonction d’un seuil calculé sur la base du max et du min des niveaux de gris des voisins et décident si le pixel est « supprimable » ou non. Une autre méthode proposée par [39] et qui a inspiré la version diﬀérentielle de [25] citée plus haut, utilise une combinaison d’érosion et de dilatation aﬁn d’atteindre les crêtes centrales d’un objet. L’in- convénient des deux méthodes sus-citées est la non préservation de la connexité de l’objet, étant donnée que la déﬁnition de la connexité en gris telle que choisie ne permet pas de mettre en place un amincissement homotopique. En 1990, les auteurs de [40] proposent un amincissement basé sur une première étape de classiﬁcation des pixels selon la probabi- lité d’appartenir au squelette ou non. Cette technique implique une binarisation implicite du fond aﬁn d’opérer les amincissements itératifs à partir de pixels du contour. D’autres méthodes d’amincissement séquentiel telles que proposées par [41, 42, 43] requièrent une binarisation du fond ou un prétraitement par lissage de l’image et ne garantissent pas, par conséquent, l’homotopie d