Sample-Based Shape Analysis

Short Summary

This project investigates new methods for sample-based 3D shape analysis. The goal is to define new data structures and algorithms for efficient database retrieval, segmentation, feature extraction, and shape classification.

Project Description

This project investigates new methods for sample-based 3D shape analysis. The goal is to define new data structures and algorithms for efficient database retrieval, segmentation, feature extraction, and shape classification. The central idea is to use a sample-based approach, where the model is first decomposed into a set of local surface patches. Local shape characteristics are then evaluated on each patch separately, which allows efficient, parallelizable computations.
Given the relevant shape information on each local surface element, a global inference step combines this data to extract meaningful properties of a given shape, or geometric and topological relations among multiple shapes. Since the number of local surface elements can be very large (> 100k), the complexity of the global inference step quickly leads to excessive computation time. To make this problem computationally tractable, two main concepts are applied. Spatial datastructures for high dimensions can be used to related per-patch shape characteristics to allow efficient proximity queries for clustering. This idea has been used to extract partial and approximate symmetries in 3D models (see publications). A second important concept is randomization. Using a small set of 'random experts', a significant reduction in data complexity can be achieved, effectively exploiting the redundancy of the local data with respect to the inference step. This approach has been used to define probabilistic fingerprints for efficient partial matching of shapes, with applications in database retrieval, partial scan alignment, and shape correspondence.

Results

 

 

 

Publications

Symmetrization
Niloy J. Mitra, Leonidas J. Guibas, Mark Pauly
ACM Transactions on Graphics (Proceedings of SIGGRAPH) 2007
[paper] [movie]

Partial and Approximate Symmetry Detection for 3D Geometry
Niloy J. Mitra, Leonidas J. Guibas, Mark Pauly
ACM Transactions on Graphics (Proceedings of SIGGRAPH) 2006
[paper]

Probabilistic Fingerprints for Shapes
Niloy J. Mitra, Leonidas J. Guibas, Joachim Giesen, Mark Pauly
Symposium on Geometry Processing 2006
[paper]

The Conformal Alpha Shape Filtration
Frederic Cazals, Joachim Giesen, Mark Pauly, Afra Zomorodian
The Visual Computer 2006
[paper]

Conformal Alpha Shapes
Frederic Cazals, Joachim Giesen, Mark Pauly, Afra Zomorodian
Symposium on Point-Based Graphics 2005
[paper]

Uncertainty and Variability in Point Cloud Surface Data
Mark Pauly, Niloy Mitra, Leo Guibas
Symposium on Point-Based Graphics 2004
[paper]

Participating Researchers

Mark Pauly, Frederic Cazals, Joachim Giesen, Leonidas J. Guibas, Niloy Mitra, Afra Zomorodian