Séminaire du 31/03/2017, 14h00

vendredi 31 mars 2017, 14h00

Homologie algorithmique appliquée aux objets discrets

Conférencier : Aldo González Lorenzo (LSIS)

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, β₀, le rang du groupe d'homologie de dimension zéro, est le nombre de composantes connexes, β₁ est le nombre de tunnels ou anses et β₂ 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.