Partial intrinsic reflectional symmetry of 3D shapes

ABSTRACT

While many 3D objects exhibit various forms of global symmetries, prominent intrinsic symmetries which exist only on parts of an object are also well recognized. Such partial symmetries are often seen as more natural than a global one, even when the symmetric parts are under complex pose. We introduce an algorithm to extract partial intrinsic reflectional symmetries (PIRS) of a 3D shape. Given a closed 2-manifold mesh, we develop a voting scheme to obtain an intrinsic reflectional symmetry axis (IRSA) transform, which is a scalar field over the mesh that accentuates prominent IRSAs of the shape. We then extract a set of explicit IRSA curves on the shape based on a refined measure of local reflectional symmetry support along a curve. The iterative refinement procedure combines IRSA-induced region growing and region-constrained symmetry support refinement to improve accuracy and address potential issues arising from rotational symmetries in the shape. We show how the extracted IRSA curves can be incorporated into a conventional mesh segmentation scheme so that the implied symmetry cues can be utilized to obtain more meaningful results. We also demonstrate the use of IRSA curves for symmetry-driven part repair.

References

1. Atallah, M. J. 1985. On symmetry detection. IEEE Trans. Comput. 34, 7, 663--666.
2. Bokeloh, M., Berner, A., Wand, M., Seidel, H.-P., and Schilling, A. 2009. Symmetry detection using line features. Computer Graphics Forum (Special Issue of Eurographics) 28, 2, 697--706.
3. Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2006. Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching. Proc. National Academy of Sciences (PNAS) 103, 5, 1168--1172.
4. Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2007. Calculus of non-rigid surfaces for geometry and texture manipulation. IEEE Trans. Vis.&Comp. Graphics 13, 5, 902--913.
5. Bronstein, A. M., Bronstein, M. M., Bruckstein, A. M., 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.
6. Chaouch, M., and Verroust-Blondet, A. 2008. A novel method for alignment of 3D models. Proc. IEEE Int. Conf. on Shape Modeling and Applications, 187--195.
7. Chen, X., Golovinskiy, A., and Funkhouser, T. 2009. A benchmark for 3D mesh segmentation. ACM Trans. on Graph 28, 3, 73:1--12.
8. Elad, A., and Kimmel, R. 2001. Bending invariant representations for surfaces. Proc. IEEE Conf. on Comp. Vis. and Pat. Rec., 168--174.
9. Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. Proc. of Int. Conf. on Knowledge Discovery and Data Mining, 226--231.
10. Gal, R., and Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity. ACM Trans. on Graph 25, 1, 130--150.
11. Gatzke, T., Grimm, C., Garland, M., and Zelinka, S. 2005. Curvature maps for local shape comparison. Proc. IEEE Int. Conf. on Shape Modeling and Applications, 246--255.
12. Golovinskiy, A., Podolak, J., and Funkhouser, T. 2007. Symmetry-aware mesh processing. Princeton University TR-782-07.
13. Hoffman, D. D., and Richards, W. A. 1984. Parts of recognition. Cognition 18, 65--96.
14. Hoffman, D. D., and Singh, M. 1997. Salience of visual parts. Cognition 63, 1, 29--78.
15. Kazhdan, M., Chazelle, B., Dobkin, D., Finkelstein, A., and Funkhouser, T. 2002. A reflective symmetry descriptor. Proc. Euro. Conf. on Comp. Vis. 2, 642--656.
16. Kazhdan, M., Chazelle, B., Dobkin, D., Funkhouser, T., and Rusinkiewicz, S. 2003. A reflective symmetry descriptor for 3D models. Algorithmica 38, 1, 201--225.
17. Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Symmetry descriptors and 3D shape matching. Symp. on Geom. Proc., 115--123.
18. Köhler, W. 1929. Gestalt Psychology. Liveright, New York.
19. Leyton, M. 1992. Symmetry, Causality, Mind. MIT Press.
20. Leyton, M. 2001. A Generative Theory of Shape. Lecture Notes in Computer Science, Vol. 2145. Springer.
21. Liu, R., and Zhang, H. 2007. Mesh segmentation via spectral embedding and contour analysis. Computer Graphics Forum (Special Issue of Eurographics) 26, 3, 385--394.
22. Loy, G., and Eklundh, J.-O. 2006. Detecting symmetry and symmetric constellations of features. In Proc. Euro. Conf. on Comp. Vis., 508--521.
23. Martinet, A., Soler, C., Holzschuch, N., and Sillion, F. X. 2006. Accurate detection of symmetries in 3D shapes. ACM Trans. on Graph 25, 2, 439--464.
24. Mitra, N. J., Guibas, L. J., and Pauly, M. 2006. Partial and approximate symmetry detection for 3D geometry. ACM Trans. on Graph 25, 3, 560--568.
25. Mitra, N. J., Guibas, L. J., and Pauly, M. 2007. Symmetrization. ACM Trans. on Graph 26, 3, 63:1--8.
26. Ovsjanikov, M., Sun, J., and Guibas, L. 2008. Global intrinsic symmetries of shapes. Computer Graphics Forum (Proc. of Symposium on Geometry Processing) 27, 5, 1341--1348.
27. Pauly, M., Mitra, N. J., Wallner, J., Pottmann, H., and Guibas, L. 2008. Discovering structural regularity in 3D geometry. ACM Trans. on Graph 27, 3, 43:1--11.
28. Podolak, J., Shilane, P., Golovinskiy, A., Rusinkiewicz, S., and Funkhouser, T. 2006. A planar-reflective symmetry transform for 3D shapes. ACM Trans. on Graph 25, 3, 549--559.
29. Podolak, J., Golovinskiy, A., and Rusinkiewicz, S. 2007. Symmetry-enhanced remeshing of surfaces. Symp. on Geom. Proc., 235--242.
30. Raviv, D., Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2007. Symmetries of non-rigid shapes. Proc. Int. Conf. on Comp. Vis.
31. Riklin-Raviv, T., Kiryati, N., and Sochen, N. 2006. Segmentation by level sets and symmetry. Proc. IEEE Conf. on Comp. Vis. and Pat. Rec. 1, 1015--1022.
32. Rustamov, R. M. 2007. Laplace-beltrami eigenfuctions for deformation invariant shape representation. Symp. on Geom. Proc., 225--233.
33. Rustamov, R. M. 2008. Augmented planar reflective symmetry transform. The Visual Computer 24, 6, 423--433.
34. Shamir, A. 2006. Segmentation and shape extraction of 3D boundary meshes. Eurographics STAR Report, 137--149.
35. Shapira, L., Shamir, A., and Cohen-Or, D. 2008. Consistent mesh partitioning and skeletonization using the shape diameter function. The Visual Computer 24, 4, 249--259.
36. Simari, P., Kalogerakis, E., and Singh, K. 2006. Folding meshes: hierarchical mesh segmentation based on planar symmetry. Symp. on Geom. Proc., 111--119.
37. Stewart, I., and Golubitsky, M. 1992. Fearful Symmetry: Is God a Geometer? Blackwell Cambridge, MA.
38. Surazhsky, V., Surazhsky, T., Kirsanov, D., Gortler, S. J., and Hoppe, H. 2005. Fast exact and approximate geodesics on meshes. ACM Trans. on Graph 24, 3, 553--560.
39. Thrun, S., and Wegbreit, B. 2005. Shape from symmetry. Proc. Int. Conf. on Comp. Vis., 1824--1831.
40. Weyl, H. 1983. Symmetry. Princeton University Press.
41. 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, 1, 37--48.
42. Yeh, Y.-T., and Mech, R. 2009. Detecting symmetries and curvilinear arrangements in vector art. Computer Graphics Forum (Special Issue of Eurographics) 28, 2, 707--716.
43. Yu, Y., Zhou, K., Xu, D., Shi, X., Bao, H., Guo, B., and Shum, H.-Y. 2004. Mesh editing with poisson-based gradient field manipulation. ACM Trans. on Graph 23, 3, 644--651.
44. Zabrodsky, H., and Weinshall, D. 1997. Using bilateral symmetry to improve 3D reconstruction from image sequences. Computer Vision and Image Understanding 67, 48--57.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Computer vision

      • Computer vision representations

        • Image representations

      • Image and video acquisition

        • 3D imaging

  • Computer graphics

    • Animation

    • Shape modeling

      • Parametric curve and surface models

      • Volumetric models