Multi-resolution shape analysis based on discrete Morse decompositions

Abstract

Representing and efficiently managing scalar fields and morphological information extracted from them is a fundamental issue in several applications including terrain modeling, static and dynamic volume data analysis (i.e. for medical or engineering purposes), and time-varying 3D scalar fields. Data sets have usually a very large size and adhoc methods to reduce their complexity are needed. Morse theory offers a natural and mathematically-sound tool to analyze the structure of a discrete scalar field as well as to represent it in a compact way through decompositions of its domain. Starting from a Morse function, we can decompose the domain of the function into meaningful regions associated with the critical points of the field.

Such decompositions, called ascending and descending Morse complexes, are characterized by the integral lines emanating from, or converging to, some critical point of a scalar field. Moreover, another decomposition can be defined by intersecting the ascending and descending Morse complexes which is called the Morse-Smale complex. Unlike the ascending and descending Morse complexes, the Morse-Smale complex decomposes the domain into a set of regions characterized by a uniform flow of the gradient between two critical points. In this thesis, we address the problem of computing and efficiently extracting Morse representations from a scalar field.

The starting point of our research is defining a representation for both ascending and descending Morse complexes. We have defined a dual representation for the two Morse complexes, called Morse incidence graph. Then we have fully investigated all the existing algorithms to compute a Morse or Morse-Smale complex. Thus, we have reviewed most important algorithms based on different criteria such as discrete complex used to describe the domain, features extracted by the algorithm, critical points used to perform the extraction and entities used by the segmentation process. Studying such algorithms has led us to investigate the strengths and weaknesses of both the Morse theory adaptations to the discrete case, piecewise-linear Morse theory and the discrete Morse theory due to Forman. We have defined and investigated two dimension-independent simplification operators to simplify a Morse complex and we have defined them in terms of updates on the Morse complexes and on the Morse incidence graph.

Thanks to such simplification operators and their dual refinement operators, we have defined and developed a multi-resolution model to extract morphological representations of a given scalar field at different resolution levels. A similar hierarchical approach has been used to define and develop a multi-resolution representation of a cell complex based on homology-preserving simplification and refinement operators which allows us to extract representations of a cell complex at different resolutions, all with the same homology of the original complex, and to efficiently compute homology generators on such complexes.