Surfaces discrètes et frontières d'objets dans les ordres

De
Publié par

Universit´e de Marne-La-Vall´ee
Ecole Doctorale ICMS
N˚ | | | | | | | | |
`THESE
pour obtenir le grade de
Docteur de l’Universit´e de Marne-la-Vall´ee
(sp´ecialit´e informatique)
pr´esent´ee et soutenue publiquement par
Xavier A. Daragon
Sous la direction de : Michel Couprie
le 14 octobre 2005
Surfaces discr`etes et fronti`eres d’objets dans les ordres
Posets : discrete surfaces and object boundaries
Composition du jury
Rapporteurs : Pascal Lienhardt
R´emy Malgouyres
Examinateurs : Gilles Bertrand
Maxime Crochemore
Jaccques-Olivier Lachaud
Christian Ronse
Michel Couprie (directeur)
c UMLV Remerciements
Avant d’entrer dans le vif du sujet, je tiens à remercier les nombreuses personnes qui, directement ou
indirectement, ont contribué à l’avancée de mes travaux et à la rédaction de cette thèse.
Pour commencer, je remercie Rémy Malgouyres et Pascal Lienhardt pour avoir accepté de rapporter
ma thèse et m’avoir prodigué, entre autre par ce biais, de nombreux et utiles conseils ; Maxime Cro
chemore, qui fut autrefois l’un de mes professeurs, Jacques Olivier Lachaud et Christian Ronse pour
m’avoir fait l’honneur de participer à mon jury.
D’un point de vue scientifique, je remercie mon directeur de thèse Michel Couprie qui guide mes
recherches depuis mon DEA, ainsi que Gilles Bertrand pour ses nombreux conseils et sa présence dans
mon jury. Par ailleurs, je remercie l’ensemble des doctorants, chercheurs et administratifs ayant croisé
ma route au laboratoire A2SI pour leur ...
Publié le : mardi 3 mai 2011
Lecture(s) : 113
Nombre de pages : 152
Voir plus Voir moins
Universit´e de Marne-La-Vall´ee Ecole Doctorale ICMS N˚ | | | | | | | | | `THESE pour obtenir le grade de Docteur de l’Universit´e de Marne-la-Vall´ee (sp´ecialit´e informatique) pr´esent´ee et soutenue publiquement par Xavier A. Daragon Sous la direction de : Michel Couprie le 14 octobre 2005 Surfaces discr`etes et fronti`eres d’objets dans les ordres Posets : discrete surfaces and object boundaries Composition du jury Rapporteurs : Pascal Lienhardt R´emy Malgouyres Examinateurs : Gilles Bertrand Maxime Crochemore Jaccques-Olivier Lachaud Christian Ronse Michel Couprie (directeur) c UMLV Remerciements Avant d’entrer dans le vif du sujet, je tiens à remercier les nombreuses personnes qui, directement ou indirectement, ont contribué à l’avancée de mes travaux et à la rédaction de cette thèse. Pour commencer, je remercie Rémy Malgouyres et Pascal Lienhardt pour avoir accepté de rapporter ma thèse et m’avoir prodigué, entre autre par ce biais, de nombreux et utiles conseils ; Maxime Cro chemore, qui fut autrefois l’un de mes professeurs, Jacques Olivier Lachaud et Christian Ronse pour m’avoir fait l’honneur de participer à mon jury. D’un point de vue scientifique, je remercie mon directeur de thèse Michel Couprie qui guide mes recherches depuis mon DEA, ainsi que Gilles Bertrand pour ses nombreux conseils et sa présence dans mon jury. Par ailleurs, je remercie l’ensemble des doctorants, chercheurs et administratifs ayant croisé ma route au laboratoire A2SI pour leur soutien moral et pour avoir élargi mon champ de vision par leurs propres travaux de recherche ; ceci vaut en particulier pour Christophe Lohou, Francisco Bezerra, Yukiko Kenmochi, Laurent Najman, Benoit Kaufman et Cédric Allène. Je remercie aussi Pascal Lienhard, Sylvie Alayrangues et Jacques Olivier Lachaud pour les reflexions que nous avons menées ensemble sur les liens unissant les cartes combinatoires généralisées aux n surfaces. Concernant les soutiens plus indirects, mais non moins fondamentaux, je citerai en particulier mes parents, pour avoir su maintenir mon esprit vagabond sous pression, ma soeur, pour ne pas m’avoir mis sous pression, le reste de ma famille et mes amis, pour leur soutien moral, les divers professeurs d’arts martiaux et les membres d’ARCAO qui, à défaut de m’assouplir ou de faire de moi un combattant aguerri, m’ont appris à mieux focaliser mon énergie, le club de jeux de rôle des champions de Khazad Dum et ses membres pour m’avoir aidé à garder le moral en toutes circonstances, Naruse sensei pour m’avoir enseigné les base du japonais, ouverture nécessaire à mon équilibre mental, les enseignants du dépar tement Japon de l’INALCO et les membres de Planète langues O’ pour m’avoir permis d’approfondir cette voie, Madame Bouvier et Monsieur Guyard pour leur avoir préparé le terrain. Parmis les nombreux professeurs à que je dois ma formation scientifique, je tiens en particulier à remercier Dominique Revuz, qui me poussa à continuer mes études d’informatique au delà de la maîtrise et sans qui ce travail n’aurait donc jamais vu le jour. i ii Table des matières Table des figures ix Liste des tableaux xi INTRODUCTION I Cadre Theorique´ 25 Chapitre 1 Ensembles Partiellement Ordonnes´ 1.1 Definition´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.1.1 Conventions et notions preliminaires´ . . . . . . . . . . . . . . . . . . . . . 27 1.1.2 Ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.1.3 Adherence´ et voisinage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.1.4 Isomorphisme d’ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.1.5 Sous ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.1.6 Rang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.2 Representation´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.3 Grille de Khalimsky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.4 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.4.1 Chemins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.4.2 Connexite´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.4.3 Courbe simple fermee´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.5 Jointure d’ordres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 ´1.5.1 Definition et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.5.2 Propriet´ es´ el´ ementaires´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 iii Table des matières Chapitre 2 Complexes Simpliciaux 2.1 Historique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.2 Definitions´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.2.1 Complexe simplicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.2.2 Ordre canonique associe´ a` un complexe simplicial . . . . . . . . . . . . . . 41 2.2.3 Operateurs´ el´ ementaires´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.2.4 Mouvements stellaires et bi stellaires . . . . . . . . . . . . . . . . . . . . . 44 2.2.5 Voisinage Simplicial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.3 Complexe des chaˆınes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.4 Notions de surface dans les complexes simpliciaux . . . . . . . . . . . . . . . . . . 47 2.4.1 Variet´ e´ combinatoire/stellaire . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.4.2 Pseudovariet´ e´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 Chapitre 3 n Surfaces 3.1 Definition´ et exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.2 Propriet´ es´ dans le cadre des ordres . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.2.1 Jointures de n surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.2.2 Dimension et homogen´ eit´ e´ . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.2.3 α etβ adherence´ dans une n surface . . . . . . . . . . . . . . . . . . . . . 54 3.2.4 Propriet´ e´ de separation´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.3 Propriet´ es´ dans le cadre des complexes simpliciaux . . . . . . . . . . . . . . . . . . 55 3.3.1 Bordure d’un complexe simplicial . . . . . . . . . . . . . . . . . . . . . . . 56 3.3.2 Caracterisation´ des n surfaces dans le cadre des complexes simpliciaux . . . 56 3.3.3 Jointure simpliciale de n surfaces . . . . . . . . . . . . . . . . . . . . . . . 57 ˆ3.4 Complexe des chaınes d’une n surface . . . . . . . . . . . . . . . . . . . . . . . . 57 II Principaux Resultats´ 59 Chapitre 4 n Surfaces, Pseudovariet´ es´ et Variet´ es´ 4.1 Purete,´ fermeture et forte connexite´ d’un ordre . . . . . . . . . . . . . . . . . . . . 61 4.1.1 Purete´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.1.2 Fermeture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.1.3 Forte connexite´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 iv 4.2 Comparaison entre n Surfaces, Pseudovariet´ es´ et Variet´ es´ Combinatoire . . . . . . . 66 4.2.1 n Surfaces et pseudovariet´ es´ . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.2.2 n Surfaces et variet´ es´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.2.3 Theor´ eme` de classification . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Chapitre 5 n Surfaces et Cartes Combinatoires Gen´ eralis´ ees´ 5.1 Cartes combinatoires reguli´ eres` . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.1.1 Definitions´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.1.2 Caracteristiques´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.2 n Surfaces et switch ordres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.3 n Surfaces et n G cartes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Chapitre 6 Ordres Frontier` es 6.1 Definition´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.1.1 Ordre frontiere` d’un complexe . . . . . . . . . . . . . . . . . . . . . . . . 85 6.1.2 Ordre frontiere` d’un ordre . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6.1.3 Forme alternative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.1.4 Notion d’intersection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.2 Propriet´ es´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.2.1 Fonction separante´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.2.2 Structure surfacique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 6.3 Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.3.1 Application a` la grille cubique . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.4 Adaptation a` la topologie digitale . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Chapitre 7 Ordres Frontier` es et Voisinages Deri´ ves´ 7.1 Voisinage deri´ ve´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 7.2 Voisinage deri´ ve´ et ordre frontiere` . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 7.3 Propriet´ es´ surfaciques des voisinages deri´ ves´ . . . . . . . . . . . . . . . . . . . . . 100 7.4 Retour sur les ordres frontieres` . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 v Table des matières III Exemple applicatif 103 Chapitre 8 Exemple Applicatif : Segmentation du Neo Cortex´ Cer´ ebral´ 8.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 8.2 Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 8.2.1 Passage vers la grille de khalimsky . . . . . . . . . . . . . . . . . . . . . . 106 8.2.2 Notion de point simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 ´ ´8.2.3 Algorithme d’epaississement guide homotopique . . . . . . . . . . . . . . . 108 8.2.4 Operateurs´ controles´ par la topologie . . . . . . . . . . . . . . . . . . . . . 111 8.3 Chaˆıne de traitement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 8.3.1 Traitements preliminaires´ et pre se´ gmentation . . . . . . . . . . . . . . . . 112 8.3.2 Obtention de la matiere` blanche . . . . . . . . . . . . . . . . . . . . . . . . 113 8.3.3 Extention au cortex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 8.3.4 Isolation du cortex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 8.4 Resultats´ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 CONCLUSION vi Annexes 127 Annexe A Preuves des propriet´ es´ secondaires 127 A.1 Preuve de la propriet´ e´ 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 A.2 Preuve de la propriet´ e´ 21 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 Index 129 Bibliographie 131 vii Table des matières viii
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.