“Multi-scale partial intrinsic symmetry detection”
Conference:
Type(s):
Title:
- Multi-scale partial intrinsic symmetry detection
Session/Category Title: Generating and Understanding Models
Presenter(s)/Author(s):
Abstract:
We present an algorithm for multi-scale partial intrinsic symmetry detection over 2D and 3D shapes, where the scale of a symmetric region is defined by intrinsic distances between symmetric points over the region. To identify prominent symmetric regions which overlap and vary in form and scale, we decouple scale extraction and symmetry extraction by performing two levels of clustering. First, significant symmetry scales are identified by clustering sample point pairs from an input shape. Since different point pairs can share a common point, shape regions covered by points in different scale clusters can overlap. We introduce the symmetry scale matrix (SSM), where each entry estimates the likelihood two point pairs belong to symmetries at the same scale. The pair-to-pair symmetry affinity is computed based on a pair signature which encodes scales. We perform spectral clustering using the SSM to obtain the scale clusters. Then for all points belonging to the same scale cluster, we perform the second-level spectral clustering, based on a novel point-to-point symmetry affinity measure, to extract partial symmetries at that scale. We demonstrate our algorithm on complex shapes possessing rich symmetries at multiple scales.
References:
1. Attene, M., Falcidieno, B., and Spagnuolo, M. 2006. Hierarchical mesh segmentation based on fitting primitives. The Visual Computer 22, 3, 181–193.
2. Ben-Chen, M., Butscher, A., Solomon, J., and Guibas, L. 2010. On discrete Killing vector fields and patterns on surfaces. Computer Graphics Forum (Special Issue of SGP) 29, 5, 1701–1711.
3. Berner, A., Wand, M., Mitra, N. J., Mewes, D., and Seidel, H.-P. 2011. Shape analysis with subspace symmetries. Computer Graphics Forum (Special Issue of Eurographics) 30, 2, 277–286.
4. 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.
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. Campen, M., and Kobbelt, L. 2011. Walking on broken mesh: Defect-tolerant geodesic distances and parameterizations. Computer Graphics Forum (Special Issue of Eurographics) 30, 2, 623–632.
7. Clark, A. 1984. Elements of Abstract Algebra. Dover, New York.
8. Gal, R., and Cohen-Or, D. 2006. Salient geometric features for partial shape matching and similarity. ACM Trans. on Graph 25, 1, 130–150.
9. Golovinskiy, A., and Funkhouser, T. 2008. Randomized cuts for 3d mesh analysis. ACM Trans. on Graph 27, 5, 145:1–12.
10. Kim, V. G., Lipman, Y., Chen, X., and Funkhouser, T. 2010. Möbius transformations for global intrinsic symmetry analysis. Computer Graphics Forum (Special Issue of SGP) 29, 5, 1689–1700.
11. Lehoucq, R., Sorensen, D., and Yang, C. 1998. ARPACK users’ guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods, vol. 6. SIAM.
12. Ling, H., and Jacobs, D. W. 2007. Shape classification using the inner-distance. IEEE Trans. Pat. Ana. & Mach. Int. 29, 286–299.
13. Lipman, Y., Chen, X., Daubechies, I., and Funkhouser, T. 2010. Symmetry factored embedding and distance. ACM Trans. on Graph 29, 4, 103:1–12.
14. 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.
15. Mitra, N. J., Pauly, M., Wand, M., and Ceylan, D. 2012. Symmetry in 3D geometry: Extraction and applications. In Proc. of Eurographics STAR Report.
16. Ovsjanikov, M., Sun, J., and Guibas, L. 2008. Global intrinsic symmetries of shapes. Computer Graphics Forum (Special Issue of SGP) 27, 5, 1341–1348.
17. 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.
18. Pele, O., and Werman, M. 2009. Fast and robust earth mover’s distances. In Proc. Int. Conf. on Comp. Vis., 460–467.
19. 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.
20. Raviv, D., Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2010. Full and partial symmetries of non-rigid shapes. Int. J. Comp. Vis. 89, 18–39.
21. Rustamov, R. M. 2007. Laplace-beltrami eigenfuctions for deformation invariant shape representation. In Proc. Symp. on Geom. Proc., 225–233.
22. Shamir, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 27, 6, 1539–1556.
23. Simari, P., Kalogerakis, E., and Singh, K. 2006. Folding meshes: hierarchical mesh segmentation based on planar symmetry. In Proc. Symp. on Geom. Proc., 111–119.
24. Sun, J., Ovsjanikov, M., and Guibas, L. J. 2009. A concise and provably informative multi-scale signature based on heat diffusion. Computer Graphics Forum (Special Issue of SGP) 28, 5, 1383–1392.
25. 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.
26. Wang, Y., Xu, K., Li, J., Zhang, H., Shamir, A., Liu, L., Cheng, Z., and Xiong, Y. 2011. Symmetry hierarchy of man-made objects. Computer Graphics Forum (Special Issue of Eurographics) 30, 2, 287–296.
27. Xu, K., Zhang, H., Tagliasacchi, A., Liu, L., Li, G., Meng, M., and Xiong, Y. 2009. Partial intrinsic reflectional symmetry of 3D shapes. ACM Trans. on Graph 28, 5, 138:1–10.
28. Zelnik-Manor, L., and Perona, P. 2004. Self-tuning spectral clustering. In Proc. Advances in Neural Information Processing Systems (NIPS), vol. 17, 1601–1608.
