Fast computation of medial representations for dynamic shapes
Computing medial axes for 2D shapes is a well understood topic, with efficient, robust, and easy-to-use methods (see e.g., Ogniewicz and Kubler, 1995; Telea and van Wijk, 2002; Falcao et al., 2004; Siddiqi and Pizer, 2009). The 2D medial axis transform (MAT) fully encodes a shape’s boundary by its medial axis. In contrast, 3D shapes admit two kinds of medial structures: Surface skeletons generalize 2D medial axes and their MATs to fully capture the shape’s geometry and topology. Curve skeletons capture the shape topology as a set of 1D curves, but do not provide the full boundary encoding given by the MAT. Hence, curve skeletons are good descriptors for tubular shapes such as vessel structures, but are less suited as analysis and processing tools for generic 3D shapes. Recently, fast and accurate medial-surface computation was made possible for complex 3D models of millions of polygons (Ma et al., 2012; Jalba et al., 2013). Those advances in MAT computation allowed for the development of further refined descriptors enabling improved operations such as shape segmentation and feature extraction (Kustra et al., 2015).
However, most real world shapes present some type of dynamic behavior, i.e., a continuous deformation in time. Examples of such shape behaviors can be found in multiple areas, e.g., in healthcare the motion of the heart, lungs, or the swelling of an organ during clinical intervention present challenges where shape feature extraction can add crucial information.
Despite the potential value of dynamic shape processing approaches, the computation of the 3D medial axis in a dynamic shape is still an embryonic field. With this project, the goal is to develop computational techniques enabling the extraction of a 3D medial axis of complex 3D shapes.
The work breakdown would consist of the following:
- Static 3D medial axis computation using existing approaches (Jalba et al. 2013)
- Reusable feature analysis (what features can be reused from a previous shape computation ?)
- Define conditions under which medial points can be reused
- Implement and test the time gained approaches
- Study relationship between medial axis point features (e.g. radius, importance) and dynamic behavior.
- Develop dynamic visualization approaches (e.g. using OpenGL, VTK) of dynamic medial axis.