“Symmetry factored embedding and distance” by Lipman, Chen, Daubechies and Funkhouser

We introduce the Symmetry Factored Embedding (SFE) and the Symmetry Factored Distance (SFD) as new tools to analyze and represent symmetries in a point set. The SFE provides new coordinates in which symmetry is “factored out,” and the SFD is the Euclidean distance in that space. These constructions characterize the space of symmetric correspondences between points — i.e., orbits. A key observation is that a set of points in the same orbit appears as a clique in a correspondence graph induced by pairwise similarities. As a result, the problem of finding approximate and partial symmetries in a point set reduces to the problem of measuring connectedness in the correspondence graph, a well-studied problem for which spectral methods provide a robust solution. We provide methods for computing the SFE and SFD for extrinsic global symmetries and then extend them to consider partial extrinsic and intrinsic cases. During experiments with difficult examples, we find that the proposed methods can characterize symmetries in inputs with noise, missing data, non-rigid deformations, and complex symmetries, without a priori knowledge of the symmetry group. As such, we believe that it provides a useful tool for automatic shape analysis in applications such as segmentation and stationary point detection.

1. Belkin, M., and Niyogi, P. 2001. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in Neural Information Processing Systems 14, MIT Press, 585–591.Google Scholar
2. Berner, A., Bokeloh, M., Wand, M., Schilling, A., and Seidel, H.-P. 2008. A graph-based approach to symmetry detection. In IEEE/EG Symposium on Volume and Point-Based Graphics. Google ScholarDigital Library
3. Bokeloh, M., Berner, A., Wand, M., Seidel, H.-P., and Schilling, A. 2009. Symmetry detection using line features. Computer Graphics Forum (Eurographics) 28, 2, 697–706.Google ScholarCross Ref
4. Bronstein, A., Bronstein, M., Bruckstein, A., and Kimmel, R. 2009. Partial similarity of objects, or how to compare a centaur to a horse. Int. J. Comp. Vis. 84, 2, 163–183. Google ScholarDigital Library
5. Chertok, M., and Keller, Y. 2010. Spectral symmetry analysis. In IEEE Transactions on Pattern Analysis and Machine Intelligence, to appear. Google ScholarDigital Library
6. Coifman, R. R., Lafon, S., Lee, A. B., Maggioni, M., Nadler, B., Warner, F., and Zucker, S. W. 2005. Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps. Proceedings of the National Academy of Sciences 102, 21 (May), 7426–7431.Google Scholar
7. Gold, S., Rangarajan, A., ping Lu, C., and Mjolsness, E. 1998. New algorithms for 2d and 3d point matching: Pose estimation and correspondence. Pattern Recognition 31, 957–964.Google ScholarCross Ref
8. Hays, J., Leordeanu, M., Efros, A. A., and Liu, Y. 2006. Discovering texture regularity as a higher-order correspondence problem. In 9th European Conference on Computer Vision. Google ScholarDigital Library
9. Imiya, A., Ueno, T., and Fermin, I. 1999. Symmetry detection by random sampling and voting process. In CIAP99, 400–405. Google ScholarDigital Library
10. Kazhdan, M., Chazelle, B., Dobkin, D., Funkhouser, T., and Rusinkiewicz, S. 2003. A reflective symmetry descriptor for 3D models. Algorithmica 38, 1 (Oct.). Google ScholarDigital Library
11. Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Symmetry descriptors and 3D shape matching. In Symposium on Geometry Processing. Google ScholarDigital Library
12. Leordeanu, M., and Hebert, M. 2005. A spectral technique for correspondence problems using pairwise constraints. In ICCV ’05: Proceedings of the Tenth IEEE International Conference on Computer Vision, IEEE Computer Society, Washington, DC, USA, 1482–1489. Google ScholarDigital Library
13. Leung, T., and Malik, J. 1996. Detecting, localizing and grouping repeated scene elements from an image. In European Conference on Computer Vision, 546–555. Google ScholarDigital Library
14. Li, W., Zhang, A., and Kleeman, L. 2005. Fast global reflectional symmetry detection for robotic grasping and visual tracking. In ACRA05.Google Scholar
15. Li, M., Langbein, F., and Martin, R. 2006. Constructing regularity feature trees for solid models. Geom. Modeling Processing, 267–286. Google ScholarDigital Library
16. Lipman, Y., and Funkhouser, T. 2009. Mobius voting for surface correspondence. ACM Transactions on Graphics (Proc. SIGGRAPH) 28, 3 (Aug.). Google ScholarDigital Library
17. Liu, S., Martin, R., Langbein, F., and Rosin, P. 2007. Segmenting periodic reliefs on triangle meshes. In Math. of Surfaces XII, Springer, 290–306. Google ScholarDigital Library
18. Mitra, N. J., Guibas, L., and Pauly, M. 2006. Partial and approximate symmetry detection for 3d geometry. In ACM Transactions on Graphics, vol. 25, 560–568. Google ScholarDigital Library
19. Nadler, B., Lafon, S., Coifman, R. R., and Kevrekidis, I. G. 2005. Diffusion maps, spectral clustering and reaction coordinates of dynamical systems. ArXiv Mathematics e-prints.Google Scholar
20. Ovsjanikov, M., Sun, J., and Guibas, L. 2008. Global intrinsic symmetries of shapes. Computer Graphics Forum (Symposium on Geometry Processing) 27, 5, 1341–1348. Google ScholarDigital Library
21. Pauly, M., Mitra, N. J., Wallner, J., Pottmann, H., and Guibas, L. 2008. Discovering structural regularity in 3D geometry. ACM Transactions on Graphics 27, 3, #43, 1–11. Google ScholarDigital Library
22. Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 15–36.Google ScholarCross Ref
23. Podolak, J., Shilane, P., Golovinskiy, A., Rusinkiewicz, S., and Funkhouser, T. 2006. A planar-reflective symmetry transform for 3D shapes. ACM Transactions on Graphics (Proc. SIGGRAPH) 25, 3 (July). Google ScholarDigital Library
24. Raviv, D., Bronstein, A., Bronstein, M., and Kimmel, R. 2007. Symmetries of non-rigid shapes. In Int. Conf. on Comp. Vis.Google Scholar
25. Reisfeld, D., Wolfson, H., and Yeshurun, Y. 1995. Context-free attentional operators: The generalized symmetry transform. IJCV 14, 2, 119–130. Google ScholarDigital Library
26. Rustamov, R. 2008. Augmented planar reflective symmetry transform. The Visual Computer 24, 6, 423–433. Google ScholarDigital Library
27. Shi, J., and Malik, J. 1997. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence 22, 888–905. Google ScholarDigital Library
28. Shikhare, D., Bhakar, S., and Mudur, S. 2001. Compression of large 3d engineering models using automatic discovery of repeating geometric features. 233–240.Google Scholar
29. Xu, K., Zhang, H., Tagliasacchi, A., Liu, L., Li, G., Meng, M., and Xiong, Y. 2009. Partial intrinsic reflectional symmetry of 3d shapes. ACM Transactions on Graphics (SIGGRAPH ASIA) 28, 5. Google ScholarDigital Library
30. Yip, R. 2000. A hough transform technique for the detection of reflectional symmetry and skew-symmetry. PRL 21, 2, 117–130. Google ScholarDigital Library
31. Zabrodsky, H., Peleg, S., and Avnir, D. 1993. Continuous symmetry measures, ii: Symmetry groups and the tetrahedron. Journal of the American Chemical Society 115, 8278–8289.Google ScholarCross Ref