Symmetry Detection Using Line Features

M. Bokeloh A. Berner M. Wand H.-P. Seidel A. Schilling
Computer Graphics Forum (Proceedings of Eurographics) 2009, to appear
paper (10 MB) video (xvid, 40 MB) video (qt, 33 MB) slides (zip, 40 MB)





Abstract


In this paper, we describe a new algorithm for detecting structural redundancy in geometric data sets. Our algorithm computes rigid symmetries, i.e., subsets of a surface model that reoccur several times within the model differing only by translation, rotation or mirroring. Our algorithm is based on matching locally coherent constellations of feature lines on the object surfaces. In comparison to previous work, the new algorithm is able to detect a large number of symmetric parts without restrictions to regular patterns or nested hierarchies. In addition, working on relevant features only leads to a strong reduction in memory and processing costs such that very large data sets can be handled. We apply the algorithm to a number of real world 3D scanner data sets, demonstrating high recognition rates for general patterns of symmetry.

@ARTICLE{Bokeloh-2009-Symmetry,
author = Martin Bokeloh and Alexander Berner and Michael Wand and Hans-Peter Seidel and Andreas Schilling,
title = Symmetry Detection Using Line Features,
journal = Computer Graphics Forum (Proceedings of Eurographics),
year = 2009
}


Line Features


We reduce the input model to a set of line features. This reduces the number of samples dramatically while preserving dominant symmetric structures. We formulate the extraction process through a projection operator that projects a sample point onto the next closest line.
Input Model Line Features

Alignment


We use the extraced line features directly for alignment. Basically we replace the point-to-plane distance metric with a point-to-line metric in the ICP algorithm. This results in a powerful alignment tool that can handle complicated situations:


Aligning two disjoint subsets of a 3D scan. Maximum alignment error: 0.6% of the maximum bounding box side length. Third column: initial pose.


Overview - Symmetry Detection


We extract line features from the input model. Inside the inner loop, we search for symmetric constellations of line features and pass the best candidate to the validation stage, where we verify it taking all data points into account. We repeat this process several times inside the candidate loop and return the best candidate (one symmetric part with its instances). This set is then refined, in order to find more instances. An outer loop repeats the process to find several symmetries.



Results



Detected Symmetries in the data set 'zwinger' (courtesy of Markus Wacker). There are three different types of windows (colored in three different colors). If two instances of the same type share a border, we indicate this by drawing a black/white colored line in between.







The data set 'old town hall' (courtesy of the Institute for Cartography and Geoinformatics Hannover) consists of 7,700,000 points. Our algorithm is able to detect small parts like windows as well as big reflective parts.



To examine the limits of our algorithm, we have applied it to the 'Happy Buddha' data set (Stanford Scanning Repository). This yields only two small reflective symmetries. Line detection and matching works in principle for such data sets, but the main problem in this case is that the data set does not contain larger rigidly symmetric parts.




As a synthetic example for completely irregular patterns of symmetry, we have engraved the Eurographics logo into a flat plane, rotated and shifted randomly. For some of the instances, we have cut out holes of different size. Our algorithm is able to detect all of the logos automatically. If we add Gaussian noise with a standard deviation of 5% of the maximum heightfield height, some of the instances with big holes are not retrieved anymore but we still obtain good results for most of the symmetric parts.




We apply our reconstruction approach to the front of the old town hall and to the Zwinger data set (rightmost). With our symmetry reconstruction technique we obtain a significantly improved quality. Surprisingly, the quality is better than one would expect from just averaging a small number of instances (just leading to square-root error decay). The reason for this is that we do not only average out noise, but also increase the sampling density; in these examples, an insufficient sampling density lead to more geometric uncertainty than the noise in the distance measurements. In addition, we can also fill holes such as the window frames, which are typically acquired from at one side only.