A Graph-Based Approach to Symmetry Detection

A. Berner M. Bokeloh M. Wand A. Schilling H.-P. Seidel
IEEE/EG International Symposium on Volume and Point-Based Graphics, 2008

[ paper pdf (1 MB) ] - [ slides pdf (16 MB) ]






Abstract


Symmetry detection aims at discovering redundancy in the form of recurring structures in geometric objects. In this paper, we present a new symmetry detection algorithm for geometry represented as point clouds that is based on analyzing a graph of surface features. We combine a general feature detection scheme with a RANSAC-based randomized subgraph searching algorithm in order to reliably detect reoc-curring patterns of locally unique structures. A subsequent segmentation step based on a simultaneous region growing variant of the ICP algorithm is applied to verify that the actual point cloud data supports the pattern detected in the feature graphs. We apply our algorithm to synthetic and real-world 3D scanner data sets, demonstrating robust symmetry detection results in the presence of scanning artifacts and noise. The modular and flexible nature of the graph-based detection scheme allows for easy generalizations of the algorithm, which we demonstrate by applying the same technique to other data modalities such as images or triangle meshes.

BibTeX

@INPROCEEDINGS{Berner2008,
  AUTHOR = {Berner, Alexander and Bokeloh, Martin and Wand, Michael and Schilling, Andreas and Seidel, Hans-Peter},
  TITLE = {A Graph-Based Approach to Symmetry Detection},
  BOOKTITLE = {Symposium on Volume and Point-Based Graphics},
  PUBLISHER = {Eurographics Association},
  YEAR = {2008},
  PAGES = {1--8},
  ADDRESS = {Los Angeles, CA} }

Graph-Based Approach


Our first step is building a graph of salient features.
detected features k-nearest neighbor graph

Pipeline


Processing pipeline - first a set of locally unique features is detected, which then form a graph on the object surface. Next, subgraphs with matching topology and approximately matching geometric embedding are extracted. From these discrete candidate matches, data points are assigned to symmetric regions using an ICP-based simultaneous region growing algorithm, which yields the final result.




Result of random sub-graph search





Geometric Validation





Some results presented in the paper



Faces - synthetic data set: left: detected subgraphs, right: symmetry detection result.



Engraved horseman (historical artifact): Top: Detected features, middle: symmetry detection result, bottom: matching residuals (blue = low, red = high). Data set courtesy of Allan Chalmers.




Application to image data: Circuit diagram (from left to right: input, features, feature graph, detected subgraphs; corresponding instances obtain the same color)




Application to triangle meshes: All instances of the same type are coded in the same color. For such clean data, we obtain a more or less perfect recognition performance. Power Plant triangle mesh courtesy of UNC Chapel Hill.



This was just a quick overview...


... for more details, please see the [paper pdf] or the [talk slides pdf].