Séminaire LIGM - Homologie algorithmique appliquée aux objets discrets

Un séminaire de l'équipe A3SI du LIGM (unité mixte de recherche de l'Université Paris Est) aura lieu le jeudi 30 mars de 13h30 à 14h30, salle 260 (ESIEE PARIS).

Homologie algorithmique appliquée aux objets discrets
Aldo Gonzalez Lorenzo
LSIS, Polytech' Marseille

Résumé :

La théorie de l'homologie formalise la notion de trou dans un espace. Pour un sous-ensemble de l'espace Euclidien, on définit une séquence de groupes d'homologie, dont leurs rangs sont interprétés comme le nombre de trous de chaque dimension. Ainsi, b0, le rang du groupe d'homologie de dimension zéro, est le nombre de composantes connexes, b1 est le nombre de tunnels ou anses et b2 est le nombre de cavités. Ces groupes sont calculables quand l'espace est décrit d'une façon combinatoire, comme c'est le cas pour les complexes simpliciaux ou cubiques. À partir d'un objet discret (un ensemble de pixels, voxels ou leur analogue en dimension supérieure) nous pouvons construire un complexe cubique et donc calculer ses groupes d'homologie.

Je vais présenter trois approches relatives au calcul de l'homologie sur des objets discrets. En premier lieu, j'introduirai le champ de vecteurs discret homologique, une structure combinatoire généralisant les champs de vecteurs gradients discrets, qui permet de calculer les groupes d'homologie. Cette notion permet de voir la relation entre plusieurs méthodes existantes pour le calcul de l'homologie et révèle également des notions subtiles associés. Je présenterai ensuite un algorithme linéaire pour calculer les nombres de Betti dans un complexe cubique 3D, ce qui peut être utilisé pour les volumes binaires. Enfin, je vais présenter deux mesures (l'épaisseur et la largeur) associées aux trous d'un objet discret, ce qui permet d'obtenir une signature topologique et géométrique plus intéressante que les simples nombres de Betti. Cette approche fournit aussi quelques heuristiques permettant de localiser les trous, d'obtenir des générateurs d'homologie ou de cohomologie minimaux, d'ouvrir et de fermer les trous.