Algorithms in 3D Shape Segmentation

Surfaces in 3D are often represented by polygonal meshes and point clouds obtained from 3D modeling tools or acquisition processes such as laser range scanning. While these formats are very flexible and allow the representation of a wide variety of shapes, they are rarely appropriate in their raw form for the range of applications that benefit from their use. Their decomposition into simpler constituting parts is referred to as shape segmentation, and its automation remains a challenging area within computer science. We will present and analyze different aspects of shape segmentation. We begin by looking at useful segmentation criteria and present a categorization of current methods according to which type of criteria they address, dividing them into affinity-based, model-fitting, and property-based approaches. We then present two algorithmic contributions in the form of a model-based and a property-based segmentation approaches. These share the goals of automatically finding redundancy in a shape and propose shape representations that leverage this redundancy to achieve descriptive compactness. The first is a method for segmenting a surface into piece-wise ellipsoidal parts, motivated by the fact that most organic objects and many manufactured objects have large curved areas. The second is an algorithm for robustly detecting global and local planar-reflective symmetry and a hierarchical segmentation approach based on this detection method. We note within these approaches the variation in segmentations resulting from different criteria and propose a way to generalize the segmentation problem to heterogenous criteria. We introduce a framework and relevant algorithms for multi-objective segmentation of 3D shapes which allow for the incorporation of domain-specific knowledge through multiple objectives, each of which refers to one or more segmentation labels. They can assert properties of an individual part or they can refer to part interrelations. We thus cast the segmentation problem as an optimization minimizing an aggregate objective function which combines all objectives as a weighted sum. We conclude with a summary and discussion of the contributions presented, lessons learned, and a look at the open questions remaining and potential avenues of continued research.Ph