Segmenting images and triangular meshes using methods of algebraic topology

OData support
Dr. Várady Tamás László
Department of Control Engineering and Information Technology

My task was to get acquainted with image and mesh segmentation algorithms that use algebraic topology. Algebraic topology examines the topology of spaces by studying abstract algebraic structures, while Morse theory constructs the space sequentially, taking note of changes in its topology. Persistence theory is what makes the connection between these approaches quantitative, by assigning to each topological feature its lifetime in a step-by step construction of the space. This theory can be utilized for segmentation purposes mostly through watershed-based methods. Essentially, the watershed procedure considers the image or mesh as a topographical landscape being flooded by water, with lakes emerging in the basins. As the level rises, the waters from adjacent basins meet along watershed lines, forming the segment boundaries. This usually leads to oversegmentation, so a merging step is neccessary, for which we can use persistence theory.

The considered algorithms are based on a clustering procedure, developed by Frederic Chazal, et. al. of INRIA [1] Saclay, France; which builds up a neigbourhood graph as in watershed methods, and merges segments meeting at saddle points based on the height difference between the corresponding local extrememum and the saddle point, i.e. persistence. In case of grayscale images, the bitmap iself, or its gradient gives the graph, while color images are mapped to a point cloud in color space, where we look for the basins of attraction of density maxima. Generally triangular meshes are to be segmented by some approximation of the curvature.

In accordance with the project proposal I have only implemented the image segmentation algorithms, in the language C++. In the grayscale case, I got useful results for synthetic and some simple natural images. For color images, I was able to effectively reproduce the results of the original article, but the algorithm is difficult to tune, and performance optimizations are neccesary for practical use.

For triangular meshes, I have considered various signature functions and persistence-based segmentation algorithms, along with the potential issues related to a prospective implementation.

[1] Institut National de Recherche en Informatique et en Automatique


Please sign in to download the files of this thesis.