“Intrinsic Girth Function for Shape Processing”

  • ©

Conference:


Title:

    Intrinsic Girth Function for Shape Processing

Session/Category Title: SHAPE SIGNATURE

Abstract:


    Shape description and feature detection are fundamental problems in computer graphics and geometric modeling. Among many existing techniques, those based on geodesic distance have proven effective in providing intrinsic and discriminative shape descriptors. In this article we introduce a new intrinsic function for a three-dimensional (3D) shape and use it for shape description and geometric feature detection. Specifically, we introduce the intrinsic girth function (IGF) defined on a 2D closed surface. For a point p on the surface, the value of the IGF at p is the length of the shortest nonzero geodesic path starting and ending at p. The IGF is invariant under isometry, insensitive to mesh tessellations, and robust to surface noise. We propose a fast method for computing the IGF and discuss its applications to shape retrieval and detecting tips, tubes, and plates that are constituent parts of 3D objects.

References:


    1. Uwe Abresch and Wolfgang T. Meyer. 1997. Injectivity radius estimates and sphere theorems. Karsten Grove 30 (1997), 1–47.
    2. J. Assfalg, M. Bertini, A. D. Bimbo, and P. Pala. 2007. Content-based retrieval of 3D objects using spin image signatures. IEEE Trans. Multimed. 9, 3 (2007), 589–599.
    3. Mathieu Aubry, Ulrich Schlickewei, and Daniel Cremers. 2011. The wave kernel signature: A quantum mechanical approach to shape analysis. In Proceedings of the IEEE International Conference on Computer Vision Workshops. 1626–1633.
    4. Erhan Bas and Deniz Erdogmus. 2011. Principal curves as skeletons of tubular objects. Neuroinformatics 9, 2–3 (2011), 181–191.
    5. Serge Belongie, Jitendra Malik, and Jan Puzicha. 2000. Shape context: A new descriptor for shape matching and object recognition. In NIPS. 831–837.
    6. Alexander M. Bronstein, Michael M. Bronstein, Leonidas J. Guibas, and Maks Ovsjanikov. 2011. Shape Google: Geometric words and expressions for invariant shape retrieval. ACM Trans. Graph. 30, 1 (2011), 1:1–1:20.
    7. Michael M. Bronstein and Iasonas Kokkinos. 2010. Scale-invariant heat kernel signatures for non-rigid shape recognition. In IEEE Conference on Computer Vision and Pattern Recognition. IEEE, Washington DC, 1704–1711.
    8. Ee Chien Chang, Zhiyong Huang, Mohan S. Kankanhalli, and Rong Xu. 2003. A 3D shape matching framework. In Proceedings of the 1st International Conference on Computer Graphics and Interactive Techniques in Australasia and South East Asia (GRAPHITE’03). ACM, New York NY, 269–270.
    9. Jindong Chen and Yijie Han. 1990. Shortest paths on a polyhedron. In Proceedings of the 6th Annual Symposium on Computational Geometry. ACM, New York, NY, 360–369.
    10. Yee Ming Chen and Jen-Hong Chiang. 2010. Fusing multiple features for Fourier Mellin-based face recognition with single example image per person. Neurocomputing 73, 16 (2010), 3089–3096.
    11. Hyeong In Choi, Sung Woo Choi, and Hwan Pyo Moon. 1997. Mathematical theory of medial axis transform. Pac. J. Math. 181, 1 (1997), 57–88.
    12. Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2013. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Trans. Graph. 32, 5 (2013), 152.
    13. Tamal K. Dey, Kuiyu Li, Chuanjiang Luo, Pawas Ranjan, Issam Safa, and Yusu Wang. 2010. Persistent heat signature for pose-oblivious matching of incomplete models. Comput. Graph. Forum 29, 5 (2010), 1545–1554.
    14. Lubin Fan, Ligang Liu, and Kun Liu. 2011. Paint mesh cutting. Comput. Graph. Forum 30, 2 (2011), 603–611.
    15. R. Gal, A. Shamir, and D. Cohen-Or. 2007. Pose-oblivious shape signature. IEEE Trans. Visualiz. Comput. Graph. 13, 2 (2007), 261–271.
    16. Timothy Gatzke, Cindy Grimm, Michael Garland, and Steve Zelinka. 2005. Curvature maps for local shape comparison. In Proceedings of the International Conference on Shape Modeling and Applications. IEEE, 244–253.
    17. Samrat Goswami, Tamal K. Dey, and Chandrajit L. Bajaj. 2006. Identifying flat and tubular regions of a shape by unstable manifolds. In Proceedings of the 2006 ACM Symposium on Solid and Physical Modeling. ACM, New York, NY, 27–37.
    18. Eberhard Hopf. 1948. Closed surfaces without conjugate points. Proc. Natl. Acad. Sci. U.S.A. 34, 2 (1948), 47.
    19. Jin Huang, Muyang Zhang, Jin Ma, Xinguo Liu, Leif Kobbelt, and Hujun Bao. 2008. Spectral quadrangulation with orientation and alignment control. ACM Trans. Graph. 27, 5, Article 147, 9 pages. DOI:http://dx.doi.org/10.1145/1409060.1409100
    20. Adrian Ion, Nicole M. Artner, Gabriel Peyré, Salvador B López Mármol, Walter G. Kropatsch, and Laurent Cohen. 2008. 3D shape matching by geodesic eccentricity. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops. 1–8.
    21. Adrian Ion, Gabriel Peyré, Yll Haxhimusa, Samuel Peltier, Walter G. Kropatsch, Laurent D. Cohen, et al. 2007. Shape matching using the geodesic eccentricity transform-a study. In Proceedings of the 31st Annual Workshop of the Austrian Association for Pattern (OAGM/AAPR). 97–104.
    22. I. M. James. 1962. Convex regions in the geometry of paths. In Differential Geometry. Pergamon, London, 223–232.
    23. Kalervo Järvelin and Jaana Kekäläinen. 2000. IR evaluation methods for retrieving highly relevant documents. In Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, New York, NY, 41–48.
    24. Andrew E. Johnson and Martial Hebert. 1999. Using spin images for efficient object recognition in cluttered 3D scenes. IEEE Trans. Pattern Analy. Mach. Intell. 21, 5 (1999), 433–449.
    25. Ron Kimmel and James A. Sethian. 1998. Computing geodesic paths on manifolds. Proc. Natl. Acad. Sci. U.S.A 95, 15 (1998), 8431–8435.
    26. Zhenzhong Kuang, Zongmin Li, Xiaxia Jiang, Yujie Liu, and Hua Li. 2015. Retrieval of non-rigid 3D shapes from multiple aspects. Computer-Aided Des. 58 (2015), 13–23.
    27. Zhouhui Lian, Afzal Godil, Benjamin Bustos, Mohamed Daoudi, Jeroen Hermans, Shun Kawamura, et al. 2011. SHREC’11 track: Shape retrieval on non-rigid 3D watertight meshes. 3DOR 11 (2011), 79–88.
    28. Zhouhui Lian, Afzal Godil, Benjamin Bustos, Mohamed Daoudi, Jeroen Hermans, Shun Kawamura, et al. 2013. A comparison of methods for non-rigid 3D shape retrieval. Pattern Recogn. 46, 1 (2013), 449–461.
    29. Roee Litman, Alex Bronstein, Michael Bronstein, and Umberto Castellani. 2014. Supervised learning of bag-of-features shape descriptors using sparse coding. Comput. Graph. Forum 33, 5, 127–136.
    30. Yong-Jin Liu. 2013. Exact geodesic metric in 2-manifold triangle meshes using edge-based data structures. Computer-Aided Des. 45, 3 (2013), 695–704.
    31. Lin Lu, Andrei Sharf, Haisen Zhao, Yuan Wei, Qingnan Fan, Xuelin Chen, Yann Savoye, Changhe Tu, Daniel Cohen-Or, and Baoquan Chen. 2014. Build-to-last: Strength to weight 3D printed objects. ACM Trans. Graph. 33, 4 (2014), 1–10.
    32. Linjie Luo, Ilya Baran, Szymon Rusinkiewicz, and Wojciech Matusik. 2012. Chopper: Partitioning models into 3D-printable parts. ACM Trans. Graph. 31, 6 (2012), 129.
    33. Michael Martinek, Matthias Ferstl, and Roberto Grosso. 2012. 3D shape matching based on geodesic distance distributions. In Vision, Modeling & Visualization. The Eurographics Association, 219–220.
    34. Ivan Mendoza. 2011. Local features for partial shape matching and retrieval. In Proceedings of the 19th ACM International Conference on Multimedia (MM’11). ACM, New York, NY, 853–856.
    35. J. S. B. Mitchell, D. M. Mount, and C. H. Papadimitriou. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4 (1987), 647–668.
    36. Robert Osada, Thomas Funkhouser, Bernard Chazelle, and David Dobkin. 2002. Shape distributions. ACM Trans. Graph. 21, 4 (2002), 807–832.
    37. Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. 2012. Functional maps: A flexible representation of maps between shapes. ACM Trans. Graph. 31, 4 (2012).
    38. Ofir Pele and Michael Werman. 2009. Fast and robust earth mover’s distances. In IEEE 12th International Conference on Computer Vision. IEEE, Washington, DC, 460–467.
    39. Konrad Polthier and Markus Schmies. 1999. Geodesic flow on polyhedral surfaces. In Data Visualization’99. Springer, Berlin, 179–188.
    40. Yossi Rubner, Carlo Tomasi, and Leonidas J. Guibas. 2000. The earth mover’s distance as a metric for image retrieval. Int. J. Comput. Vision 40, 2 (2000), 99–121.
    41. Ariel Shamir, Lior Shapira, Daniel Cohen-Or, and Rony Goldenthal. 2004. Geodesic mean shift. In Proceedings of 5th Korea Israel Conference on Geometric Modeling and Computer Graphics. 51–56.
    42. Lior Shapira, Shy Shalom, Ariel Shamir, Daniel Cohen-Or, and Hao Zhang. 2010. Contextual part analogies in 3D objects. Int. J. Comput. Vision 89, 2–3 (2010), 309–326.
    43. Lior Shapira, Ariel Shamir, and Daniel Cohen-Or. 2008. Consistent mesh partitioning and skeletonisation using the shape diameter function. Vis. Comput. 24, 4 (2008), 249–259.
    44. M. Sharir and A. Schorr. 1986. On shortest paths in polyhedral spaces. SIAM J. Comput. 15, 1 (1986), 193–215.
    45. Philip Shilane, Patrick Min, Michael Kazhdan, and Thomas Funkhouser. 2004. The Princeton shape benchmark. In Proceedings of the Shape Modeling International (SMI’04). 167–178.
    46. Kaleem Siddiqi, Juan Zhang, Diego Macrini, Ali Shokoufandeh, Sylvain Bouix, and Sven Dickinson. 2008. Retrieving articulated 3D models using medial surfaces. Mach. Vis. Appl. 19, 4 (2008), 261–275.
    47. Justin Solomon, Raif Rustamov, Leonidas Guibas, and Adrian Butscher. 2014. Earth mover’s distances on discrete surfaces. ACM Trans. Graph. 33, 4 (July 2014), 67:1–67:12.
    48. Jian Sun, Maks Ovsjanikov, and Leonidas Guibas. 2009. A concise and provably informative multi-scale signature based on heat diffusion. Comput. Graph. Forum 28, 5 (2009), 1383–1392.
    49. Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven J. Gortler, and Hugues Hoppe. 2005. Fast exact and approximate geodesics on meshes. ACM Trans. Graph. 24, 3 (2005), 553–560.
    50. Johan W. H. Tangelder and Remco C. Veltkamp. 2008. A survey of content based 3D shape retrieval methods. Multimed. Tools Appl. 39, 3 (2008), 441–471.
    51. Wilbur C. K. Wong and Albert Chung. 2008. Principal curves to extract vessels in 3D angiograms. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPRW’08). 1–8.
    52. Chunlin Wu and Xuecheng Tai. 2010. A level set formulation of geodesic curvature flow on simplicial surfaces. IEEE Trans. Visualiz. Comput. Graph. 16, 4 (2010), 647–662.
    53. Ying He, Xiang Ying, and Shi-Qing Xin. 2014. Parallel Chen-Han (PCH) algorithm for discrete geodesics. ACM Trans. Graph. 33, 1 (2014), 57–76.
    54. Shi-Qing Xin, Ying He, and Chi-Wing Fu. 2012. Efficiently computing exact geodesic loops within finite steps. IEEE Trans. Visualiz. Comput. Graph. 18, 6 (2012), 879–889.
    55. Shi-Qing Xin and Guo-Jin Wang. 2009. Improving Chen and Han’s algorithm on the discrete geodesic problem. ACM Trans. Graph. 28, 4, Article 104, 8 pages.
    56. Xiang Ying, Xiaoning Wang, and Ying He. 2013. Saddle vertex graph (SVG): A novel solution to the discrete geodesic problem. ACM Trans. Graph. 32, 6 (2013), 170.
    57. Qingnan Zhou, Julian Panetta, and Denis Zorin. 2013. Worst-case structural analysis. ACM Trans. Graph. 32, 4, Article 137, 12 pages.
    58. Henrik Zimmer, Marcel Campen, and Leif Kobbelt. 2013. Efficient computation of shortest path-concavity for 3D meshes. In Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition (CVPR’13). 2155–2162.

ACM Digital Library Publication: