“Detail-Preserving Mesh Unfolding for Non-Rigid Shape Retrieval” by Sahillioglu and Kavan

  • ©Yusuf Sahillioglu and Ladislav Kavan



Session Title:



    Detail-Preserving Mesh Unfolding for Non-Rigid Shape Retrieval




    We present a shape deformation algorithm that unfolds any given 3D shape into a canonical pose that is invariant to nonrigid transformations. Unlike classical approaches, such as least-squares multidimensional scaling, we preserve the geometric details of the input shape in the resulting shape, which in turn leads to a content-based nonrigid shape retrieval application with higher accuracy. Our optimization framework, fed with a triangular or a tetrahedral mesh in 3D, tries to move each vertex as far away from each other as possible subject to finite element regularization constraints. Intuitively this effort minimizes the bending over the shape while preserving the details. Avoiding geodesic distances in our computation renders the method robust to topological noise. Compared to state-of-the-art approaches, our method is simpler to implement, faster, more accurate in shape retrieval, and less sensitive to topological errors.


    1. B. Adams, M. Ovsjanikov, M. Wand, H.-P. Seidel, and L. Guibas. 2008. Meshless modeling of deformable shapes and their motion. In Proceedings of the SCA (2008). 
    2. D. Anguelov, P. Srinivasan, D. Koller, S. Thrun, J. Rodgers, and J. Davis. 2005. Scape: Shape completion and animation of people. ACM Trans. Graph. 24, 3 (2005), 408–416. 
    3. J. Assfalg, M. Bertini, and A. Delbimbo. 2007. Content-based retrieval of 3d objects using spin image signatures. Trans. Multimedia 9, 3 (2007), 589–599. 
    4. O. K.-C. Au, D. Cohen-Or, C.-L. Tai, H. Fu, and Y. Zheng. 2010. Electors voting for fast automatic shape correspondence. In Computer Graphics Forum (Proc. Eurographics) 29, 2 (2010), 645–654.
    5. V. Barra and S. Biasotti. 2013. 3D shape retrieval using kernels on extended reeb graphs. Pattern Recognit. 46, 11 (2013), 2985–2999.
    6. S. Belongie, J. Malik, and J. Puzicha. 2002. Shape matching and object recognition using shape contexts. IEEE Trans. PAMI 24, 4 (2002), 509–522. 
    7. P. J. Besl and N. D. Mckay. 1992. A method for registration of 3D shapes. IEEE Trans. PAMI 14, 2 (1992), 239–256. 
    8. J. Bonet and R. D. Wood. 1997. Nonlinear Continuum Mechanics for Finite Element Analysis. Cambridge University Press, Cambridge, England.
    9. M. Botsch and O. Sorkine. 2008. On linear variational surface deformation methods. IEEE Trans. Visual. Comp. Graphics 14, 1 (2008), 213–230. 
    10. A. M. Bronstein, M. M. Bronstein, and R. Kimmel. 2006. Generalized multidimensional scaling: A framework for isometry invariant partial surface matching. Proc. Natl. Acad. Sci. USA 103, 5 (2006), 1168–1172.
    11. A. M. Bronstein, M. M. Bronstein, and R. Kimmel. 2008. Numerical Geometry of Non-Rigid Shapes. Springer, New York, USA. 
    12. M. Bronstein, M. Bronstein, L. Guibas, and M. Ovsjanikov. 2011. Shape google: Geometric words and expressions for invariant shape retrieval. ACM Trans. Graph. 30, 1 (2011), Article No. 1. 
    13. M. M. Bronstein and I. Kokkinos. 2010. Scale-invariant heat kernel signatures for non-rigid shape recognition. In Proceedings of the Computer Vision and Pattern Recognition (CVPR).
    14. R. Byrd, J. Nocedal, and R. Waltz. 2006. An integrated package for nonlinear optimization. In Large-Scale Nonlinear Optimization 83 (2006), 35–59.
    15. I. Chao, U. Pinkall, P. Sanan, and P. Schroder. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29, 4 (2010), 38. 
    16. D. Chen, X. Tian, Y. Shen, and M. Ouhyoung. 2003. On visual similarity based 3D model retrieval. Comput. Graphics Forum 22, 3 (2003), 223–232.
    17. X. Chen, C. Zheng, W. Xu, and K. Zhou. 2014. An asymptotic numerical method for inverse elastic shape design. ACM Trans. Graph. 33, 4 (2014), Article No. 95. 
    18. T. Cox and M. Cox. 2000. Multidimensional Scaling, 2nd ed. Chapman & Hall/CRC.
    19. K. Crane, C. Weischedel, and M. Wardetzky. 2013. Geodesics in heat: A new approach to computing distance based on heat flow. In Proceedings of the SIGGRAPH. 
    20. V. de Silva and J. B. Tenenbaum. 2002. Global versus local methods for nonlinear dimensionality reduction. In Proceedings of the NIPS. 705–712.
    21. A. Elad and R. Kimmel. 2003. On bending invariant signatures for surfaces. IEEE Trans. PAMI 25, 10 (2003), 1285–1295. 
    22. O. Freifeld and M. J. Black. 2012. Lie bodies: A manifold representation of 3D human shape. In Proceedings of the European Conference on Computer Vision (ECCV). 1–14. 
    23. T. Funkhouser, P. Min, M. Kazhdan, J. Chen, A. Halderman, D. Dobkin, and D. Jacobs. 2003. A search engine for 3D models. ACM Trans. Graph. 22, 1 (2003), 83–105. 
    24. D. Giorgi, S. Biasotti, and L. Paraboschi. 2007. SHREC: Shape retrieval contest: Watertight models track.
    25. J. C. Gower. 1966. Some distance properties of latent root and vector methods used in multivariate analysis. Biometrika 53, 3–4 (1966), 325–338.
    26. M. Hilaga, Y. Shinagawa, T. Kohmura, and T. Kunii. 2001. Topology matching for fully automatic similarity estimation of 3D shapes. In Proceedings of the SIGGRAPH. 
    27. G. Irving, C. Schroeder, and R. Fedkiw. 2007. Volume conserving finite element simulations of deformable models. In Proceedings of the SIGGRAPH. 
    28. G. Irving, J. Teran, and R. Fedkiw. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the SCA. 131–140. 
    29. A. Jacobson, L. Kavan, and O. Sorkine. 2013. Robust inside-outside segmentation using generalized winding numbers. Proc. SIGGRAPH 32, 4 (2013), 33:1–33:12. 
    30. V. Jain and H. Zhang. 2006. Robust 3D shape correspondence in the spectral domain. In Proceedings of the IEEE Int. Conf. on Shape Modeling and Applications (SMI). 118–129. 
    31. V. Jain and H. Zhang. 2007. A spectral approach to shape-based retrieval of articulated 3D models. Comput.-Aided Des. 39, 5 (2007), 398–407. 
    32. A. Johnson and M. Hebert. 1999. Using spin images for efficient object recognition in cluttered 3D scenes. IEEE Trans. PAMI 21, 5 (1999), 433–449. 
    33. M. Kazhdan. 2007. An approximate and efficient method for optimal rotation alignment of 3D models. IEEE Trans. PAMI 29, 7 (2007), 1221–1229. 
    34. M. Kazhdan, T. Funkhouser, and S. Rusinkiewicz. 2003. Rotation invariant spherical harmonic representation of 3D shape descriptors. Comput. Graphics Forum (Proc. SGP) 6 (2003), 156–164. 
    35. B. Li, Y. Lu, C. Li, A. Godil, et al. 2014. SHREC’14 track: Large scale comprehensive 3D shape retrieval. In Proceedings of the Eurographics Workshop on 3D Object Retrieval. 131–140. 
    36. Z. Lian, A. Godil, and X. Sun. 2010. Visual similarity based 3D shape retrieval using bag-of-features. In Proceedings of the IEEE Int. Conf. on Shape Modeling and Applications (SMI). 25–36. 
    37. Z. Lian, A. Godil, and J. Xiao. 2013. Feature-preserved 3D canonical form. Int. J. Comput. Vision (IJCV) 102, 1–3 (2013), 221–238. 
    38. Y. Lipman and T. Funkhouser. 2009. Möbius voting for surface correspondence. ACM Trans. Graph. 28, 3 (2009), Article No. 72. 
    39. L. Liu, L. Zhang, Y. Xu, C. Gotsman, and S. Gortler. 2008. A local/global approach to mesh parameterization. Comput. Graphics Forum 27, 5 (2008), 1495–1504. 
    40. D. G. Lowe. 2004. Distinctive image features from scale-invariant keypoints. Int. J. Comput. Vision (IJCV) 60, 2 (2004), 91–110. 
    41. M. Mahmoudi and G. Sapiro. 2009. Three-dimensional point cloud recognition via distributions of geometric distances. Graphical Models 71, 1 (2009), 22–31. 
    42. N. Mitra, L. Guibas, and M. Pauly. 2007. Symmetrization. ACM Trans. Graph. 26, 3 (2007), 63. 
    43. M. Muller, B. Heidelberger, M. Teschner, and M. Gross. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. 24, 3 (2005), 471–478. 
    44. M. Muller, R. Keiser, A. Nealen, M. Pauly, M. Gross, and M. Alexa. 2004. Point based animation of elastic, plastic and melting objects. Proc. SCA (2004), 141–151. 
    45. A. Nealen, M. Muller, R. Keiser, E. Boxerman, and M. Carlson. 2006. Physically based deformable models in computer graphics. Comput. Graphics Forum 25, 4 (2006), 809–836.
    46. M. Novotni and R. Klein. 2003. 3D Zernike descriptors for content based shape retrieval. In Proceedings of the ACM Symposium on Solid Modeling and Applications. 216–225. 
    47. R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin. 2002. Shape distributions. ACM Trans. Graph. 21, 4 (2002), 807–832. 
    48. M. Ovsjanikov, Q. Mérigot, F. Mémoli, and L. Guibas. 2010. One point isometric matching with the heat kernel. Comput. Graphics Forum 29, 5 (2010), 1555–1564.
    49. D. Panozzo, I. Baran, O. Diamanti, and O. Sorkine-Hornung. 2013. Weighted averages on surfaces. In Proceedings of the SIGGRAPH. 
    50. E. Paquet, M. Rioux, A. Murching, T. Naveen, and A. Tabatabai. 2000. Description of shape information for 2-D and 3-D objects. Signal Proc. Image Comm. 16, 1–2 (2000), 103–122.
    51. D. Raviv, M. Bronstein, A. Bronstein, and R. Kimmel. 2010. Volumetric heat kernel signatures. In Proceedings of the ACM Multimedia Workshop on 3D Object Retrieval. 
    52. M. Reuter, F. Wolter, and N. Peinecke. 2006. Laplace-Beltrami spectra as ’shape-DNA’ of surfaces and solids. Comput.-Aided Des. 38, 4 (2006), 342–366. 
    53. R. Rustamov. 2007. Laplace-Beltrami eigenfunctions for deformation invariant shape representation. In Proceedings of the Symposium on Geometry Processing. 225–233. 
    54. Y. Sahillioglu. 2015. A shape deformation algorithm for constrained multidimensional scaling. Comput. Graphics 53 (2015), 156–165. 
    55. Y. Sahillioğlu and Y. Yemez. 2012. Minimum-distortion isometric shape correspondence using EM algorithm. IEEE Trans. PAMI 34, 11 (2012), 2203–2215. 
    56. Y. Sahillioğlu and Y. Yemez. 2013. Coarse-to-fine isometric shape correspondence by tracking symmetric flips. Comput. Graphics Forum 32, 1 (2013), 177–189.
    57. C. Schuller, L. Kavan, D. Panozzo, and O. Sorkine-Hornung. 2013. Locally injective mappings. Comput. Graphics Forum (Proc. SGP) 32, 5 (2013), 125–135. 
    58. K. Siddiqi, J. Zhang, D. Macrini, A. Shokoufandeh, S. Bouix, and S. Dickinson. 2008. Retrieving articulated 3-D models using medial surfaces. Mach. Vision and Applications 19, 4 (2008), 261–275. 
    59. M. Skouras, B. Thomaszewski, B. Bickel, and M. Gross. 2012. Computational design of rubber balloons. Comput. Graphics Forum 31, 2 (2012), 835–844. 
    60. O. Sorkine and M. Alexa. 2007. As-rigid-as-possible surface modeling. In Proceedings of the Symposium on Geometry Processing. 109–116. 
    61. O. Sorkine and D. Cohen-Or. 2004. Least-squares meshes. In Proceedings of the Shape Modeling International. 191–199. 
    62. O. Sorkine, D. Cohen-Or, Y. Lipman, M. Alexa, C. Rossl, and H.-P. Seidel. 2004. Laplacian surface editing. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. 179–188. 
    63. A. Stomakhin, R. Howes, C. Schroeder, and J. Teran. 2012. Energetically consistent invertible elasticity. In Proceedings of the SCA. 
    64. J. Sun, M. Ovsjanikov, and L. Guibas. 2009. A concise and provably informative multi-scale signature based on heat diffusion. Comput. Graphics Forum 28, 5 (2009), 1383–1392. 
    65. J. Tangelder and R. Veltkamp. 2008. A survey of content based 3D shape retrieval methods. Multimedia Tools Appl. 39, 3 (2008), 441–471. 
    66. C. Twigg and Z. Kacìć-Alesić. 2011. Optimization for sag-free simulations. In Proceedings of the SCA. 
    67. H. Wang, K. Sidorov, P. Sandilands, and T. Komura. 2013. Harmonic parameterization by electrostatics. ACM Trans. Graph. 32, 5 (2013), Article No. 155. 
    68. A. Zaharescu, E. Boyer, K. Varanasi, and R. Horaud. 2009. Surface feature detection and description with applications to mesh matching. In Proceedings of the Computer Vision and Pattern Recognition (CVPR). 373–380.
    69. C. Zhang and T. Chen. 2001. Efficient feature extraction for 2D/3D objects in mesh representation. In Proceedings of the IEEE International Conference on Image Processing. 3.
    70. G. Zigelman, R. Kimmel, and N. Kiryati. 2002. Texture mapping using surface flattening via multidimensional scaling. IEEE Trans. Vis. Comp. Graphics 8, 2 (2002), 198–207. 

ACM Digital Library Publication: