Télécharger le fichier original (Mémoire de fin d’études)
Topologie et homologie (concepts de base)
En introduction, nous avons mentionné la classification classique à propos des caractéristiques extraites de l’image, c-à-d, qu’elles sont de bas et de haut niveau. Ces caractéristiques peuvent aussi être classifiées en trois nouveaux profils (photométriques, géométriques et topologiques). Les caractéristiques photométriques (binaire, niveau de gris, couleur), géométriques (points, seg-ments, courbes, surfaces, volumes, …) sont des entrées aux traitements réali-sés par plusieurs méthodes et algorithmes qui déja existants dans la littéra-ture. Tandis que, les caractéristiques topopologiques nécessitent encore beau-coup de soucis. Ces caractéristiques sont des propriétés d’objet qui peuvent être maintenues où préservées pendant des déformations où des transfor-mations continues que peut subir l’image. Et c’est dans cette optique que la topologie computationnelle a été prouvée comme outil pouvant servir de base pour analyser les caractéristiques topologiques.
Que mesure la topologie ?
En topologie, la propriété la plus importante qui différencie deux formes n’est pas la taille inégale, ni l’apparence différente, mais plutôt le nombre des morceaux connexes de la forme, qu’on appelle aussi les composantes connexes. Un exemple dans les figures 2.1 illustre la topologie au sens des composantes connexes. Dans la figure 2.1(a) la forme est constituée d’une seule composante connexe, alors que dans la figure 2.1(b), elle est constituée de deux composantes connexes. La topologie est donc une science qui étudie les propriétées invariantes d’un objet quand celui-ci est étiré, tordu ou rétréci de manière continue [50].
FIG. 2.1 – Exemple des caractéristiques topologiques d’une forme 2D consis-tante de: (a) une seule composante connexe ; (b) deux composantes connexes
Nous présentons, dans ce chapitre, une brève revue des notions basiques et de la terminologie de la topologie algébrique. Pour une description plus complète, nous référons le lecteur à n’importe quel texte standard dans le domaine, tels que [14, 33, 43, 64].
Homotopie et homéomorphismes
La caractérisation des objets subdivisés selon leur structure topologique est intéressante dans différents domaines en infographie, géométrie discrète, mo-délisation géométrique et visualisation 3D [57, 65]. Plus précisément, deux espaces topologiques sont « égaux », s’il existe un homéomorphisme entre eux. En général, il est très difficile de prouver qu’il existe où non un homéomor-phisme entre deux espaces topologiques. Cependant, les invariants topolo-giques ont été introduits. Un invariant topologique est une propriété qui est conservée par les homéomorphismes. Par exemple, pour deux espaces topo-logiques quelconques, si une propriété est vraie dans le premier, alors elle sera également vrai dans le deuxième, seulement si les deux espaces sont homéomorphiques. Il existe de nombreux invariants topologiques comme le nombre de composantes connexes, la caractéristique d’Euler, le groupe fon-damental, les groupes d’homologie et l’orientabilité. Parmi tous les invariants topologiques existants, nous sommes particulièrement intéressés aux groupes d’homologie car ils sont classiquement étudiés dans la topologie algébrique [64] et connu d’être des puissant proprietés. Pour chaque dimension q = 0,.., n, le groupe d’homologie Hq d’un objet nD caractérise les cycles d’homologie (les composantes connexes par H0, les trous où tunnels par H1, les cavités par H2, …). De façon informelle, les groupes d’homologie peuvent être dé-finis comme la caractérisation de la façon comment les cellules sont collées ensemble, et cela se fait en étudiant la frontière de chaque cellule. De plus, de point de vue calculatoire, les groupes d’homologie sont définis de la même manière dans n’importe quelle dimension et sont directement liés aux cellules d’un objet et à leurs relations d’incidence.
Une déformation de retraction d’un espace topologique X sur un sous-espace A est une famille de fonctions ft : X → X, t ∈ [0,1], telle que f0 = id (la fonc-tion d’identité), f1(X) = A et ft|A = id pour tout t. La famille ft, doit être continue dans le sens que la fonction associée X × [0,1] → X, (x,t) ft(x) est continue.
Une déformation de retraction est un cas special de la notion générale d’ho-motopie. Une homotopie est simplement toute famille de fonctions ft : X → Y,t ∈ [0,1], telle que la fonction associée F : X × [0,1] → Y donnée par F(x,t) = ft(x) est continue. Deux fonctions f0,f1 : X → Y sont appelées des fonctions homotopiques, s’il existe une homotopie ft qui connecte les deux et une fois s’écrit f0 ⋍ f1. Dans ces termes, une déformation de retraction de X sur un sous-espace A est une homotopie de la fonction d’identité de X sur A, une fonction r : X → X telle que r(X) = A et r|A = id [63].
Homologie
Dans la plupart des cas, il s’avère difficile de déterminer si deux transfor-mations entre deux espaces sont homotopiques ou si ces deux espaces sont homotopiquement équivalents. En pratique, lorsqu’on veut comparer des es-paces ou des transformations à l’aide d’outils topologiques, on peut le faire d’une manière très satisfaisante, en comparant leurs structures d’homologie respectives, ce qui est moins général mais plus facile à calculer. Même si l’ho-mologie est moins intuitive que l’homotopie, sa nature combinatoire la rend plus attractive. Son grand avantage est qu’elle peut être utilisée pour dire que deux espaces topologiques sont équivalents en homotopie (où homéomorphes) où non, sans avoir besoin de prouver qu’il existe où non un homéomorphisme où une équivalence homotopique entre les deux espaces. Pour un espace to-pologique, l’homologie est un moyen algébrique qui compte les cycles non triviaux et qui caractérisent cet espace. Dans l’espace 3D, les trois groupes d’homologie H0, H1 et H2 peuvent être non triviaux, leurs rangs respectifs β0, β1, et β2 (appelés aussi les nombres de Betti) déterminent respectivement le nombre de composantes connexes, de tunnels et de vides (où cavités) [86]. En infographie et traitement d’images, le fait que le groupe d’homologie est un invariant topologique qui intègre ces propriétés, l’homologie est considérée comme un outil utile pour décrire et caractériser les objets dans les images 2D et 3D. Pour des complexes cellulaires, la construction des groupes d’ho-mologie est basée sur le concept de frontière des cellules. En 2D, la frontière d’un point est l’ensemble vide qui correspond au zéro algébrique, la frontière d’une arète est formée de ses deux points extrêmes. De façon similaire, la frontière d’une cellule carrée sera son contour formé de quatre arètes. Un raisonnement analogue nous permettra de déterminer les frontières de cel-lules de plus grandes dimensions. Dans une image 2D où 3D, si ces cellules sont organisées dans une grille cubique de son support composé de pixels où voxels d’objet, elles seront appelées des cubes et sont assemblées pour former un complexe cubique. Lorsque ces cellules sont le résultat d’une triangula-risation de support, elles seront appelées des simplexes et sont assemblées suivant certaines règles pour former ainsi un complexe simplicial [85].
Chaines, groupes de cycles et de frontières
En analogie simpliciale, les chaînes et les cycles sont respectivement des che-mins et des boucles dans le domaine continu. Une q-chaîne est une somme for-melle de cellules de dimension q avec des coefficients d’entiers. D’où, chaque q-chaîne cq peut être représentée de facon unique comme [45] cq = αiσiq , αi ∈ Z i=1 où nq note le nombre de q-cellules dans la collection. L’ensemble de toutes les q-chaînes ensemble avec l’opération d’addition forme un groupe Cq . Une collection de faces de dimension (q − 1) d’une q-cellule σ, elle-même est une (q − 1)-chaîne et une frontière ∂σ. La frontière d’une q-chaîne est la somme des frontières des cellules dans cette chaîne, c-à-d.
nQ ∂q cq = αi(∂q σiq ) i=1
Par exemple, la frontière de la chaîne 2c1 −3c2 (notée ∂(2c1 −3c2)) est définie comme 2∂c1 − 3∂c2. Il est facile de montrer aussi que pour une q-chaîne c ∂q−1∂q c = 0, signifiant que la frontière de la frontière d’une q-chaîne quelconque est nulle, c-à-d, n’ayant pas de frontières. L’opérateur de frontière ∂ est une homomor-phisme ∂q : Cq −→ Cq−1 et les opérateurs ∂q pour q = 0, 1,.., n, connectent les groupes à chaînes dans un complexe à chaînes de dimension n: 0 ∂ ∂N 1 ∂1 ∂0 . Les homomorphismes de frontières −→ Cn −→N Cn−1 −→− … −→ C0 −→ 0 sont définis sur les chaînes de cellules comme des extensions linéaires des opérateurs de la frontière de base pour chaque cellule.
En discret, un complexe à chaînes est associé à une structure de complexe géométrique (simplicial, cubique où autre) qui est à son tour construit à par-tir d’objets nD discretisés subdivisés. Chaque groupe à chaînes de dimension q, est généré à partir de collection des q-cellules de ces objets (simplexes ou cubes). Ainsi, calculer les groupes d’homologie sur une structure combina-toire (complexe simplicial, complexe cubique, …) nécessite un opérateur de frontière de base sur les cellules [3].
Parmi toutes les chaînes possibles, l’homologie considère deux types particu-liers de chaînes: les cycles et les frontières. Un cycle z est une chaîne satisfai-sant ∂z = 0, une chaîne b est une frontière s’il existe une chaîne c satisfaisant ∂c = b. Pour chaque dimension q, l’ensemble des q-cycles muni de l’addition est un sous-groupe de Cq , noté Zq . L’ensemble de toutes les frontières muni de l’addition est un sous-groupe de Zq , noté Bq (une frontière est un cycle ayant comme propriété ∂∂c = 0 qui doit être satisfaite pour les chaînes). Le groupe d’homologie Hq est défini comme le quotient de groupes Zq /Bq . Alors, les éléments du groupe d’homologie Hq sont les classes d’équivalence telle que deux cycles sont dans la même classe d’équivalence s’ils diffèrent par une frontière. Les groupes d’homologie sont des groupes abéliens générés finis, donc le théorème suivant décrit leur structure [43]. Formellement, tout groupe abélien généré fini G est isomorphe à une somme directe de la forme: Z• • • Z Z/t1Z • • • Z/tk Z (2.1) β où 1 < ti ∈ Z et ti divise ti+1. Le rang β d’un groupe d’homologie est aussi appelé son nombre de Betti, et les ti sont aussi connus comme leur coefficients de torsion.
Groupes d’homologie et générateurs
En topologie calculatoire, les invariants topologiques sont divers: groupes d’homologie et de co-homologgie, groupe fondamental, coefficients de torsion, orientabilité, etc. Les groupes d’homologie sont des invariants topologiques principaux donnés pendant l’exécution d’un algorithme de calcul d’homolo-gie. Alors que le nombre de ces invariants topologiques est donné par le rang de ces groupes d’homologie. Cependant, le rang des groupes d’homologie non triviaux H0, H1 et H2 donne respectivement le nombre de composantes connexes, de trous (ou tunnels en 3D) et de cavités (uniquement en 3D).
Nous introduisons maintenant les groupes d’homologie. Formellement, sup-posons un complexe K (cubique, simplicial ou autres) construit à partir d’un espace topologique X. Le q-ième groupe d’homologie du complexe K est le groupe quotient, défini par la formule suivante: Hq = ZQ /BQ = Ker ∂q /I m ∂q+1 (2.2)
Si z1 = z2 + BQ , (z1,z2 ∈ ZQ ), alors la différence entre z1 et z2 est la frontière et z1 et z2 sont homologues. Le q-iéme nombre de Betti du complexe K est β (Hq ), le rang de q-iéme groupe d’homologie, βq = rang Hq où βq = dim Hq . De l’expression (2.2) βq = rang(Hq ) = rang(ZQ ) − rang(BQ )
Ce quotient permet de distinguer les q-cycles non frontières des q-cycles fron-tières (Intuitivement, le calcul de l’homologie suppose que nous avons sup-primé les cycles qui sont frontières d’un sous-complexe de dimension supérieure de l’ensemble de toutes les q-cycles, pour que les cycles restantes ex-trairent des informations sur les trous de dimension q du complexe. En termes simplifiées, la dimension de q-iéme homologie (connue par q-iéme nombre de Betti) compte le nombre de cycles de dimension q dans le complexe).
Pour plus de détails, et d’après la proprieté de dualité d’Alexander [43], il y a une représentation intuitive des trois premiers nombres de Betti agréablement expliqués dans [88]. Comme un 0-cycle non frontière représente un ensemble des composantes connexes du complexe correspondant, il y a un élément de base par composante afin que β0 représente le nombre des composantes de ce complexe. D’où, rang(H0) = 1 pour un complexe connecté, donc la notion de connectivité est reflété dans H0. Un 1-cycle non frontière représente une collection de courbes fermées non-contractibles, ou basée sur la proprieté de dualité, un ensemble de tunnels formé par ce complexe. Chaque tunnel peut être representé comme une somme des tunnels de la base pour que β1 repré-sente la dimension de la base pour les tunnels. Ces tunnels peuvent être percus comme étant un graphe avec les cycles [88]. Un 2-cycle qui n’est pas lui même une frontière représente l’ensemble des surfaces fermées non-contractibles. La dimension de la base pour les cavités, qui est égale au nombre des cavités est représenté par β2.
Homologie simpliciale
Construction du complexe simplicial
D’après [45], tout sous-ensemble de V = {vα0 ,vα1 ,…,vαN } détermine un n-simplexe noté par vα0 ,vα1 ,…,vαN . Les éléments vαI de V sont des sommets du simplexe noté par vαI et n est la dimension du simplexe. Tout ensemble de simplexes avec sommets dans V est appelé une famille simpliciale et sa di-mension est la plus grande dimension de ces simplexes. Un q-simplexe σq est une q-face d’un n-simplexe σn, noté par σq σn, si chaque sommet de σq est aussi un sommet de σn. L’union des faces d’un simplexe σn est une frontière de σn. Un complexe simplicial représente une collection de simplexes. Plus for-malement, un complexe simplicial K sur un ensemble fini V = {vα0 ,vα1 ,…,vαN } de sommets est un sous-ensemble non vide du grand ensemble V , afin que le complexe simplicial K soit fermé sous la formation des sous-ensembles. D’où, si σ ∈ K et ρ ∈ σ, alors ρ ∈ K. Un simplexe de dimension 0 est un point (où sommet), de dimension 1 est un segment, de dimension 2 est un triangle, de dimension 3 est un tétrahédron et ainsi de suite. La définition formelle d’un complexe simplicial implique que le complexe simplicial K exige que
– chaque face de tout simplexe dans K est aussi dans K et
– l’intersection de simplexes σ1 et σ2 dans K est soit vide où est une face commune pour les deux.
Exemple de complexe simplicial
Dans la figure 2.2 à gauche, la collection de simplexes est l’unique confi-guration qui satisfait ces exigences bien que les deux autres ne sont pas des complexes simpliciaux. Au milieu, les simplexes (triangles) intersectent, mais pas le long de simplexes communs. À droite, un triangle manque une arête.
La dimension du complexe est 2 puisqu’elle est la dimension maximale d’un simplexe. En plus, ils y avaient quatre 2-dimensionnel simplexes (ou triangles), douze 1-dimensionnel simplexes (ou arètes) et huit 0-dimensionnel simplexes (ou sommets). La manière la plus commode (ou convenable) afin de représenter un complexe simplicial est à travers qu’on appelle la matrice d’incidence, dont les colonnes sont étiquetées par leurs sommets et les lignes sont étiquetées par leurs simplexes.
Table des matières
1 INTRODUCTION
1.1 Description de l’approche
1.2 Contributions
2 Topologie et homologie (concepts de base)
2.1 Homotopie et homéomorphismes
2.2 Homologie
2.2.1 Chaines, groupes de cycles et de frontières
2.2.2 Groupes d’homologie et générateurs
2.2.3 Homologie simpliciale
2.2.4 Homologie cubique
2.3 Homologie relative
2.4 Algorithmes de calcul d’homologie
2.4.1 Méthode de forme normale de Smith
2.4.2 Méthode de réduction (ou Éffondrement)
3 État de l’art
3.1 Approches d’homologie et localisation
3.2 Techniques de représentations d’objets 3D
3.2.1 Représentations topologiques
3.2.2 Représentations géométriques
4 Représentation d’objets basée sur le bloc
4.1 Bloc cubique
4.2 Méthode de fractionnement
4.3 Génération du complexe à chaînes simplifié
4.4 Homologie du complexe cellulaire simplifié
5 LOCALIZATION DES CARACTÉRISTIQUES TOPOLOGIQUES
5.1 Principe de localisation
5.2 Processus de reconstruction
5.3 Optimisation de la localisation
6 RÉSULTATS EXPÉRIMENTAUX
6.1 Homologie des complexes cubique standard et cellulaire
6.2 Localisation des caractéristiques topologiques
6.3 Optimisation de la localisation
CONCLUSION ET PERSPECTIVES
