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

Xavier A. Daragon <[e-mail]>

Sujets

• Complexe simplicial
• Topologie de réseau
• Graphe complet
• Base (algèbre linéaire)
• L?Image (revue)
• Grille d'Hermann

Informations

• Publié par: Chaen
• Nombre de lectures: 119
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

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 ve