Optimization techniques for segmenting 3D shapes
Abstract/Contents
- Abstract
- With increasing amounts of data describing 3d shapes, geometry processing is becoming extremely important in fields ranging from computer graphics to robotics to medicine to computational biology. A fundamental task in geometry processing is to segment shapes into meaningful parts. Segmentation assists global parameterization, compression, animation and more. Moreover, it is crucial to shape understanding and semantics based object representations, which rely on feature extraction and structure extraction from 3d meshes that represent these objects and shapes. This thesis aims to advance shape segmentation techniques in three directions: joint segmentation of a collection of shapes, segmentation of repeated elements on curved surfaces, and vector field based segmentation. First, we present an approach to segmenting shapes in a heterogenous shape database. By considering multiple shapes in concert, our approach is able to identify meaningful parts despite the lack of strong geometric cues on a particular shape. Likewise, the approach is able to identify coherent single parts even when the geometry of the individual shape suggests the presence of multiple segments. The approach is entirely unsupervised and is based on an integer quadratic programming formulation of the joint segmentation problem. The program optimizes over possible segmentations of individual shapes as well as over possible correspondences between segments from multiple shapes. The integer quadratic program is solved via a linear programming relaxation, using a block coordinate descent procedure that makes the optimization feasible for large databases. We evaluate the presented approach on the Princeton segmentation benchmark and show that joint shape segmentation significantly outperforms single-shape segmentation techniques. Near-regular structures are common in man-made and natural objects. The second approach targets at segmenting the repeating elements of a near-regular structure on a curved surface. The approach proceeds in two steps. In the first step, it computes a near-regular mesh which represents the skeleton of the underlying near-regular structure. We present a sparse integer programming formulation to this problem whose linearized program is both tight and can be efficiently solved. In the second step, the approach segments the repeating elements through consistent region growing, starting at vertices of the near-regular mesh. Finally, we introduce vector-field based shape segmentation, which builds on the dual relationship between generalized Killing vector fields and segmentations. This approach allows us to control segmentations by designing appropriate Killing vector fields. It also features a low dimensional design space and interactive vector field editing. We show the application of this approach in interactive macro-patch segmentation for designing geodesic patterns.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2011 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Huang, Qixing |
|---|---|
| Associated with | Stanford University, Computer Science Department |
| Primary advisor | Guibas, Leonidas J |
| Thesis advisor | Guibas, Leonidas J |
| Thesis advisor | Carlsson, G. (Gunnar), 1952- |
| Thesis advisor | Koltun, Vladlen, 1980- |
| Advisor | Carlsson, G. (Gunnar), 1952- |
| Advisor | Koltun, Vladlen, 1980- |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Qixing Huang. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Ph. D. Stanford University 2011 |
| Location | electronic resource |
Access conditions
- Copyright
- © 2011 by Qixing Huang
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...