“A planar-reflective symmetry transform for 3D shapes” by Podolak, Shilane, Golovinskiy, Rusinkiewicz and Funkhouser

Symmetry is an important cue for many applications, including object alignment, recognition, and segmentation. In this paper, we describe a planar reflective symmetry transform (PRST) that captures a continuous measure of the reflectional symmetry of a shape with respect to all possible planes. This transform combines and extends previous work that has focused on global symmetries with respect to the center of mass in 3D meshes and local symmetries with respect to points in 2D images. We provide an efficient Monte Carlo sampling algorithm for computing the transform for surfaces and show that it is stable under common transformations. We also provide an iterative refinement algorithm to find local maxima of the transform precisely. We use the transform to define two new geometric properties, center of symmetry and principal symmetry axes, and show that they are useful for aligning objects in a canonical coordinate system. Finally, we demonstrate that the symmetry transform is useful for several applications in computer graphics, including shape matching, segmentation of meshes into parts, and automatic viewpoint selection.

1. Abbasi, S., and Mokhtarian, F. 2000. Automatic view selection in multi-view object recognition. In Proc. ICPR, vol. 1, 1013. Google ScholarDigital Library
2. Atallah, M. 1985. On symmetry detection. IEEE Trans. on Computers 34, 663–666.Google ScholarDigital Library
3. Besl, P. J., and Mckay, N. D. 1992. A method for registration of 3-D shapes. IEEE Trans. PAMI 14, 2, 239–256. Google ScholarDigital Library
4. Bigun, J. 1997. Pattern recognition in images by symmetries and coordinate transformations. Computer Vision and Image Understanding 68, 3, 290–307. Google ScholarDigital Library
5. Blanz, V., Tarr, M., Buelthoff, H., and Vetter, T. 1999. What object attributes determine canonical views. Perception 28.Google Scholar
6. Blum, H. 1967. A transformation for extracting new descriptors of shape. In Models for the Perception of Speech and Visual Form, MIT Press, W. Whaten-Dunn, Ed., 362–380.Google Scholar
7. Bonneh, Y., Reisfeld, D., and Yeshurun, Y. 1994. Quantification of local symmetry: application to texture discrimination. Spatial Vision 8, 4, 515–530.Google ScholarCross Ref
8. Chazelle, B., Dobkin, D. P., Shouraboura, N., and Tal, A. 1995. Strategies for polyhedral surface decomposition: an experimental study. In SCG ’95: Proceedings of the eleventh annual symposium on Computational geometry, ACM Press, New York, NY, USA, 297–305. Google ScholarDigital Library
9. Chetverikov, D. 1995. Pattern orientation and texture symmetry. Computer Analysis of Images and Patterns 970, 222–229. Google ScholarDigital Library
10. Choi, I., and Chien, S. 2004. A generalized symmetry transform with selective attention capability for specific corner angles. IEEE Signal Processing Letters 11, 2 (Feb.), 255–257.Google ScholarCross Ref
11. Di Gesù, V., Valenti, C., and Strinati, L. 1997. Local operators to detect regions of interest. Pattern Recognition Letters 18, 11–13 (Nov.), 1088–1081. Google ScholarDigital Library
12. Duda, R., Hart, P., and Stork, D. 2001. Pattern Classification, Second Edition. John Wiley & Sons, New York. Google ScholarDigital Library
13. Ferguson, R. W. 2000. Modeling orientation effects in symmetry detection: The role of visual structure. In Proc. Conf. Cognitive Science Society.Google Scholar
14. Funkhouser, T., Min, P., Kazhdan, M., Chen, J., Halderman, A., Dobkin, D., and Jacobs, D. 2003. A search engine for 3D models. ACM Trans. Graph. 22, 1, 83–105. Google ScholarDigital Library
15. Garland, M., Willmott, A., and Heckbert, P. S. 2001. Hierarchical face clustering on polygonal surfaces. In SI3D ’01: Proceedings of the 2001 Symposium on Interactive 3D graphics, ACM Press, New York, NY, USA, 49–58. Google ScholarDigital Library
16. Kamada, T., and Kawai, S. 1988. A simple method for computing general position in displaying three-dimensional objects. Comput. Vision Graph. Image Process. 41, 1, 43–56. Google ScholarDigital Library
17. Katz, S., and Tal, A. 2003. Hierarchical mesh decomposition using fuzzy clustering and cuts. Proceedings of ACM SIGGRAPH 22, 3, 954–961. Google ScholarDigital Library
18. 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
19. Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2003. Rotation invariant spherical harmonic representation of 3D shape descriptors. In Symposium on Geometry Processing. Google ScholarDigital Library
20. Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Symmetry descriptors and 3D shape matching. In Proc. Symposium on Geometry Processing. Google ScholarDigital Library
21. Kelly, M. F., and Levine, M. D. 1995. Annular symmetry operators: A method for locating and describing objects. In Proc. ICCV, 1016–1021. Google ScholarDigital Library
22. Lee, J., Moghaddam, B., Pfister, H., and Machiraju, R. 2004. Finding optimal views for 3d face shape modeling. In FGR, IEEE Computer Society, 31–36. Google ScholarDigital Library
23. Lee, C. H., Varshney, A., and Jacobs, D. W. 2005. Mesh saliency. Proceedings of ACM SIGGRAPH 24, 3, 659–666. Google ScholarDigital Library
24. Li, X., Toon, T., Tan, T., and Huang, Z. 2001. Decomposing polygon meshes for interactive applications. In Proceedings of the 2001 Symposium on Interactive 3D graphics, 35–42. Google ScholarDigital Library
25. Loy, G., and Zelinsky, A. 2002. A fast radial symmetry transform for detecting points of interest. In Proc. ECCV, 358–368. Google ScholarDigital Library
26. Mangan, A. P., and Whitaker, R. T. 1999. Partitioning 3d surface meshes using watershed segmentation. IEEE Transactions on Visualization and Computer Graphics 5, 4, 308–321. Google ScholarDigital Library
27. Manmatha, R., and Sawhney, H. 1997. Finding symmetry in intensity images. Tech. Rep. UM-CS-1997-007, University of Massachusetts, Jan. Google ScholarDigital Library
28. Martinet, A., Soler, C., Holzschuch, N., and Sillion, F. 2005. Accurately detecting symmetries of 3D shapes. Tech. Rep. RR-5692, INRIA, September.Google Scholar
29. Minovic, P., Ishikawa, S., and Kato, K. 1993. Symmetry identification of a 3D object represented by octree. IEEE Transactions on Pattern Analysis and Machine Intelligence 15, 5 (May), 507–514. Google ScholarDigital Library
30. Reisfeld, D., and Yeshurun, Y. 1992. Robust detection of facial features by generalized symmetry. In Proc. ICPR, 117.Google Scholar
31. Reisfeld, D., Wolfson, H., and Yeshurun, Y. 1995. Context-free attentional operators: The generalized symmetry transform. IJCV 14, 2, 119–130. Google ScholarDigital Library
32. Shah, M. I., and Sorensen, D. C. 2005. A symmetry preserving singular value decomposition. SIAM Journal of Matrix Analysis and it’s Application (October).Google Scholar
33. Shan, Y., Matei, B., Sawhney, H. S., Kumar, R., Huber, D., and Hebert, M. 2004. Linear model hashing and batch ransac for rapid and accurate object recognition. IEEE International Conference on Computer Vision and Pattern Recognition. Google ScholarDigital Library
34. Shilane, P., Min, P., Kazhdan, M., and Funkhouser, T. 2004. The Princeton Shape Benchmark. In Proc. Shape Modeling International. Google ScholarDigital Library
35. Sun, C., and Sherrah, J. 1997. 3D symmetry detection using the extended Gaussian image. IEEE Transactions on Pattern Analysis and Machine Intelligence 2, 2 (February), 164–168. Google ScholarDigital Library
36. Thrun, S., and Wegbreit, B. 2005. Shape from symmetry. In Proceedings of the International Conference on Computer Vision (ICCV), IEEE, Bejing, China. Google ScholarDigital Library
37. Vázquez, P.-P., Feixas, M., Sbert, M., and Heidrich, W. 2001. Viewpoint selection using viewpoint entropy. In VMV ’01: Proceedings of the Vision Modeling and Visualization Conference 2001, Aka GmbH, 273–280. Google ScholarDigital Library
38. Wolter, J. D., Woo, T. C., and Volz, R. A. 1985. Optimal algorithms for symmetry detection in two and three dimensions. The Visual Computer 1, 37–48.Google ScholarCross Ref
39. Zabrodsky, H., Peleg, S., and Avnir, D. 1993. Completion of occluded shapes using symmetry. In Proc. CVPR, 678–679.Google Scholar
40. Zabrodsky, H., Peleg, S., and Avnir, D. 1995. Symmetry as a continuous feature. Trans. PAMI 17, 12, 1154–1166. Google ScholarDigital Library
41. Zhang, J., and Huebner, K. 2002. Using symmetry as a feature in panoramic images for mobile robot applications. In Proc. Robotik, vol. 1679 of VDI-Berichte, 263–268.Google Scholar