Computational Homology Applied to Discrete Objects

Description

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, β0, le rang du groupe d'homologie de dimension zéro, est le nombre de composantes connexes, β1 est le nombre de tunnels ou anses et β2 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. Cette thèse étudie trois approches relatives au calcul de l'homologie sur des objets discrets. En premier lieu, nous introduisons 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ées. Nous présentons ensuite un algorithme linéaire pour calculer les vi nombres de Betti dans un complexe cubique 3D, ce qui peut être utilisé pour les volumes binaires. Enfin, nous présentons 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.

Abstract

Homology theory formalizes the concept of hole in a space. For a given subset of the Euclidean space, we define a sequence of homology groups, whose ranks are considered as the number of holes of each dimension. Hence, β0, the rank of the 0-dimensional homology group, is the number of connected components, β1 is the number of tunnels or handles and β2 is the number of cavities. These groups are computable when the space is described in a combinatorial way, as simplicial or cubical complexes are. Given a discrete object (a set of pixels, voxels or their analog in higher dimension) we can build a cubical complex and thus compute its homology groups. This thesis studies three approaches regarding the homology computation of discrete objects. First, we introduce the homological discrete vector field, a combinatorial structure which generalizes the discrete gradient vector field and allows us to compute the homology groups. This notion allows us to see the relation between different existing methods for computing homology. Next, we present a linear algorithm for computing the Betti numbers of a 3D cubical complex, which can be used for binary volumes. Finally, we introduce two measures (the thickness and the breadth) associated to the holes in a discrete object, which provide a topological and geometric signature more interesting than only the Betti numbers. This approach provides also some heuristics for localizing holes, obtaining minimal homology or cohomology generators, opening and closing holes.

Abstract

La teoría de la homología formaliza la noción de agujero en un espacio. Dado un subconjunto del espacio Euclídeo, se define una secuencia de grupos de homología, cuyos rangos se consideran el número de agujeros de cada dimensión. Así, β0, el rango del grupo de homología de dimensión 0, es el número de componentes conexas, β1 es el número de túneles o asas y β2 es el número de cavidades. Estos grupos son calculables cuando el espacio es descrito de manera combinatoria, como ocurre con los complejos simpliciales o cúbicos. También, dado un objeto discreto (un conjunto de píxeles, vóxeles o elementos de dimensión superior), podemos construir un complejo cúbico y así calcular sus grupos de homología. Esta tesis estudia tres enfoques relativos al cálculo de la homología en los objetos discretos. En primer lugar, introducimos el campo de vectores discreto homológico, una estructura combinatoria que generaliza el campo de vectores gradiente discreto y que permite calcular los grupos de homología. Este concepto permite ver la relación entre varios métodos existentes para el cálculo de la homología. Posteriormente presentamos un algoritmo lineal para calcular los números de Betti de un complejo cúbico 3D, y por tanto, de un volumen binario. Por último introducimos dos medidas (el espesor y la amplitud) asociadas a los agujeros de un objeto discreto, las cuales proporcionan una firma topológica y geométrica más interesante que simplemente los números de Betti. El cálculo de estas medidas además también aporta unas heurísticas para localizar los agujeros, obtener generadores de homología o cohomología mínimos, abrir o cerrar agujeros.

Additional details