Abstract
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.
Supplemental Material
Available for Download
Supplemental movie, appendix, image and software files for, Detail-Preserving Mesh Unfolding for Nonrigid Shape Retrieval
- 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). Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- V. Barra and S. Biasotti. 2013. 3D shape retrieval using kernels on extended reeb graphs. Pattern Recognit. 46, 11 (2013), 2985--2999.Google ScholarCross Ref
- S. Belongie, J. Malik, and J. Puzicha. 2002. Shape matching and object recognition using shape contexts. IEEE Trans. PAMI 24, 4 (2002), 509--522. Google ScholarDigital Library
- P. J. Besl and N. D. Mckay. 1992. A method for registration of 3D shapes. IEEE Trans. PAMI 14, 2 (1992), 239--256. Google ScholarDigital Library
- J. Bonet and R. D. Wood. 1997. Nonlinear Continuum Mechanics for Finite Element Analysis. Cambridge University Press, Cambridge, England.Google Scholar
- M. Botsch and O. Sorkine. 2008. On linear variational surface deformation methods. IEEE Trans. Visual. Comp. Graphics 14, 1 (2008), 213--230. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- A. M. Bronstein, M. M. Bronstein, and R. Kimmel. 2008. Numerical Geometry of Non-Rigid Shapes. Springer, New York, USA. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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).Google Scholar
- R. Byrd, J. Nocedal, and R. Waltz. 2006. An integrated package for nonlinear optimization. In Large-Scale Nonlinear Optimization 83 (2006), 35--59.Google ScholarCross Ref
- I. Chao, U. Pinkall, P. Sanan, and P. Schroder. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29, 4 (2010), 38. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- T. Cox and M. Cox. 2000. Multidimensional Scaling, 2nd ed. Chapman & Hall/CRC.Google Scholar
- 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. Google ScholarDigital Library
- V. de Silva and J. B. Tenenbaum. 2002. Global versus local methods for nonlinear dimensionality reduction. In Proceedings of the NIPS. 705--712.Google Scholar
- A. Elad and R. Kimmel. 2003. On bending invariant signatures for surfaces. IEEE Trans. PAMI 25, 10 (2003), 1285--1295. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- D. Giorgi, S. Biasotti, and L. Paraboschi. 2007. SHREC: Shape retrieval contest: Watertight models track.Google Scholar
- J. C. Gower. 1966. Some distance properties of latent root and vector methods used in multivariate analysis. Biometrika 53, 3--4 (1966), 325--338.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- G. Irving, C. Schroeder, and R. Fedkiw. 2007. Volume conserving finite element simulations of deformable models. In Proceedings of the SIGGRAPH. Google ScholarDigital Library
- G. Irving, J. Teran, and R. Fedkiw. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the SCA. 131--140. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- M. Kazhdan. 2007. An approximate and efficient method for optimal rotation alignment of 3D models. IEEE Trans. PAMI 29, 7 (2007), 1221--1229. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Z. Lian, A. Godil, and J. Xiao. 2013. Feature-preserved 3D canonical form. Int. J. Comput. Vision (IJCV) 102, 1--3 (2013), 221--238. Google ScholarDigital Library
- Y. Lipman and T. Funkhouser. 2009. Möbius voting for surface correspondence. ACM Trans. Graph. 28, 3 (2009), Article No. 72. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- D. G. Lowe. 2004. Distinctive image features from scale-invariant keypoints. Int. J. Comput. Vision (IJCV) 60, 2 (2004), 91--110. Google ScholarDigital Library
- M. Mahmoudi and G. Sapiro. 2009. Three-dimensional point cloud recognition via distributions of geometric distances. Graphical Models 71, 1 (2009), 22--31. Google ScholarDigital Library
- N. Mitra, L. Guibas, and M. Pauly. 2007. Symmetrization. ACM Trans. Graph. 26, 3 (2007), 63. Google ScholarDigital Library
- M. Muller, B. Heidelberger, M. Teschner, and M. Gross. 2005. Meshless deformations based on shape matching. ACM Trans. Graph. 24, 3 (2005), 471--478. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- R. Osada, T. Funkhouser, B. Chazelle, and D. Dobkin. 2002. Shape distributions. ACM Trans. Graph. 21, 4 (2002), 807--832. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- D. Panozzo, I. Baran, O. Diamanti, and O. Sorkine-Hornung. 2013. Weighted averages on surfaces. In Proceedings of the SIGGRAPH. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- R. Rustamov. 2007. Laplace-Beltrami eigenfunctions for deformation invariant shape representation. In Proceedings of the Symposium on Geometry Processing. 225--233. Google ScholarDigital Library
- Y. Sahillioglu. 2015. A shape deformation algorithm for constrained multidimensional scaling. Comput. Graphics 53 (2015), 156--165. Google ScholarDigital Library
- Y. Sahillioğlu and Y. Yemez. 2012. Minimum-distortion isometric shape correspondence using EM algorithm. IEEE Trans. PAMI 34, 11 (2012), 2203--2215. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- C. Schuller, L. Kavan, D. Panozzo, and O. Sorkine-Hornung. 2013. Locally injective mappings. Comput. Graphics Forum (Proc. SGP) 32, 5 (2013), 125--135. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- M. Skouras, B. Thomaszewski, B. Bickel, and M. Gross. 2012. Computational design of rubber balloons. Comput. Graphics Forum 31, 2 (2012), 835--844. Google ScholarDigital Library
- O. Sorkine and M. Alexa. 2007. As-rigid-as-possible surface modeling. In Proceedings of the Symposium on Geometry Processing. 109--116. Google ScholarDigital Library
- O. Sorkine and D. Cohen-Or. 2004. Least-squares meshes. In Proceedings of the Shape Modeling International. 191--199. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- A. Stomakhin, R. Howes, C. Schroeder, and J. Teran. 2012. Energetically consistent invertible elasticity. In Proceedings of the SCA. Google ScholarDigital Library
- 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. Google ScholarCross Ref
- J. Tangelder and R. Veltkamp. 2008. A survey of content based 3D shape retrieval methods. Multimedia Tools Appl. 39, 3 (2008), 441--471. Google ScholarDigital Library
- C. Twigg and Z. Kacìć-Alesić. 2011. Optimization for sag-free simulations. In Proceedings of the SCA. Google ScholarDigital Library
- H. Wang, K. Sidorov, P. Sandilands, and T. Komura. 2013. Harmonic parameterization by electrostatics. ACM Trans. Graph. 32, 5 (2013), Article No. 155. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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. Google ScholarDigital Library
Recommendations
Direct manipulation of subdivision surfaces on GPUs
We present an algorithm for interactive deformation of subdivision surfaces, including displaced subdivision surfaces and subdivision surfaces with geometric textures. Our system lets the user directly manipulate the surface using freely-selected ...
Direct manipulation of subdivision surfaces on GPUs
SIGGRAPH '07: ACM SIGGRAPH 2007 papersWe present an algorithm for interactive deformation of subdivision surfaces, including displaced subdivision surfaces and subdivision surfaces with geometric textures. Our system lets the user directly manipulate the surface using freely-selected ...
Bas-Relief Generation and Shape Editing through Gradient-Based Mesh Deformation
In this paper, we introduce a novel approach to bas-relief generation and shape editing that uses gradient-based mesh deformation as the theoretical foundation. Our approach differs from image-based methods in that it operates directly on the triangular ...
Comments