“Discrete Time Evolution Process Descriptor for Shape Analysis and Matching” by Meizi, Ovsjanikov, Roffo, Cristani and Castellani
Conference:
Type(s):
Title:
- Discrete Time Evolution Process Descriptor for Shape Analysis and Matching
Session/Category Title: https://dl.acm.org/doi/10.1145/3096239
Presenter(s)/Author(s):
Moderator(s):
Abstract:
In shape analysis and matching, it is often important to encode information about the relation between a given point and other points on a shape, namely, its context. To this aim, we propose a theoretically sound and efficient approach for the simulation of a discrete time evolution process that runs through all possible paths between pairs of points on a surface represented as a triangle mesh in the discrete setting. We demonstrate how this construction can be used to efficiently construct a multiscale point descriptor, called the Discrete Time Evolution Process Descriptor, which robustly encodes the structure of neighborhoods of a point across multiple scales. Our work is similar in spirit to the methods based on diffusion geometry, and derived signatures such as the HKS or the WKS, but provides information that is complementary to these descriptors and can be computed without solving an eigenvalue problem. We demonstrate through extensive experimental evaluation that our descriptor can be used to obtain accurate results in shape matching in different scenarios. Our approach outperforms similar methods and is especially robust in the presence of large nonisometric deformations, including missing parts.
References:
Yonathan Aflalo, Anastasia Dubrovina, and Ron Kimmel. 2016. Spectral generalized multi-dimensional scaling. International Journal of Computer Vision 118, 3, 380–392.
M. Aubry, U. Schlickewei, and D. Cremers. 2011. The wave kernel signature: A quantum mechanical approach to shape analysis. In International Conference on Computer Vision (ICCV’11). 1626–1633.
S. Belongie, J. Malik, and J. Puzicha. 2002. Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence 24, 4, 509–522.
F. Bernardini and H. Rushmeier. 2002. The 3D model acquisition pipeline. Computer Graphics Forum 21, 2, 149–172.
Federica Bogo, Javier Romero, Matthew Loper, and Michael J. Black. 2014. FAUST: Dataset and evaluation for 3D mesh registration. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR’14). 3794–3801.
D. Boscaini, J. Masci, S. Melzi, M. M. Bronstein, U. Castellani, and P. Vandergheynst. 2015. Learning class-specific descriptors for deformable shapes using localized spectral convolutional networks. Computer Graphics Forum 35, 5, 13–23.
E. Boyer, A. M. Bronstein, M. M. Bronstein, B. Bustos, and others. 2011. SHREC 2011: Robust feature detection and description benchmark. In Proceedings of 3DOR. Eurographics Association, 71–78. Retrieved October 17, 2017 from http://tosca.cs.technion.ac.il/book/shrec_correspondence.html.
A. M. Bronstein and M. M. Bronstein. 2011. Shape recognition with spectral distances. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 5, 1065–1071.
Alexander M. Bronstein, Michael M. Bronstein, and Maks Ovsjanikov. 2012. Feature-based methods in 3D shape analysis. In 3D Imaging, Analysis and Applications. Springer, 185–219.
Mathieu Carrière, Steve Oudot, and Maks Ovsjanikov. 2015. Stable topological signatures for points on 3D shapes. Computer Graphics Forum 34, 5, 1–12.
Qifeng Chen and Vladlen Koltun. 2015. Robust nonrigid registration by convex optimization. In International Conference on Computer Vision (ICCV’15).
R. R. Coifman and S. Lafon. 2006. Diffusion maps. Applied and Computational Harmonic Analysis 21, 1, 5–30.
Étienne Corman, Maks Ovsjanikov, and Antonin Chambolle. 2014. Supervised descriptor learning for non-rigid shape matching. In European Conference on Computer Vision (ECCV’14) Workshops. Springer, 283–298.
Keenan Crane, Clarisse Weischedel, and Max Wardetzky. 2013. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Transaction on Graphics 32, 5, 152:1–152:11.
Ernst Rudolf, Georg Eckert, and Robert M. Drake. 1987. Analysis of heat and mass transfer.
Andrea Frome, Daniel Huber, Ravi Kolluri, Thomas Bülow, and Jitendra Malik. 2004. Recognizing objects in range data using regional point descriptors. In European Conference on Computer Vision (ECCV’04). Springer, Berlin, 224–237.
R. Gal, A. Shamir, and D. Cohen-Or. 2007. Pose-oblivious shape signature. IEEE Transactions on Visualization and Computer Graphics 13, 261–271.
K. Gebal, J. A. Bærentzen, H. Anæs, and R. Larsen. 2009. Shape analysis using the auto diffusion function. Computer Graphics Forum 28, 5, 1405–1413.
Gene H. Golub and Charles F. Van Loan. 2012. Matrix Computations. Vol. 3. Johns Hopkins University Press, Baltimore, MD.
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. 1994. Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley Longman Publishing Co., Inc., New York, NY.
Masaki Hilaga, Yoshihisa Shinagawa, Taku Kohmura, and Tosiyasu L. Kunii. 2001. Topology matching for fully automatic similarity estimation of 3D shapes. In Proceedings of SIGGRAPH. 203–212.
Qixing Huang, Fan Wang, and Leonidas Guibas. 2014. Functional map networks for analyzing and exploring large shape collections. ACM Transactions on Graphics 33, 4, 36.
J. H. Hubbard and B. B. Hubbard (Eds.). 2001. Vector Calculus, Linear Algebra, and Differential Forms: A Unified Approach (2nd ed.). Pearson, New York, NY.
Adrian Ion, Nicole M. Artner, Gabriel Peyr, Walter G. Kropatsch, and Laurent D. Cohen. 2011. Matching 2D and 3D articulated shapes using the eccentricity transform. Computer Vision and Image Understanding 115, 6, 817–834.
Andrew E. Johnson and Martial Hebert. 1999. Using spin images for efficient object recognition in cluttered 3D scenes. IEEE Transactions on Pattern Analysis and Machine Intelligence 21, 5, 433–449. \
V. G. Kim, Yaron Lipman, and T. Funkhouser. 2011. Blended intrinsic maps. ACM Transaction on Graphics 30, 4, 79:1–79:12.
Ron Kimmel and James A. Sethian. 1998. Computing geodesic paths on manifolds. Proceedings of the National Academy of Sciences 95, 15, 8431–8435.
Zhouhui Lian, Afzal Godil, Benjamin Bustos, et al. 2013. A comparison of methods for non-rigid 3D shape retrieval. Pattern Recognition 46, 1, 449–461.
O. Litany, E. Rodolà, A. M. Bronstein, M. M. Bronstein, and D. Cremers. 2016. Non-rigid puzzles. Computer Graphics Forum 35, 5, 135–143.
Roee Litman, Alex Bronstein, Michael Bronstein, and Umberto Castellani. 2014. Supervised learning of bag-of-features shape descriptors using sparse coding. Computer Graphics Forum 33, 5, 127–136.
Roee Litman and Alexander M. Bronstein. 2014. Learning spectral descriptors for deformable shape correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence 36, 1, 170–180.
David G. Lowe. 2004. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision 60, 2, 91–110.
Siddharth Manay, Byung-Woo Hong, Anthony J. Yezzi, and Stefano Soatto. 2004. Integral invariant signatures. In European Conference on Computer Vision (ECCV’04). 87–99.
Simone Melzi, Emanuele Rodola, Umberto Castellani, and Michael Bronstein. 2016. Shape analysis with anisotropic windowed Fourier transform. In International Conference on 3D Vision (3DV’16).
Joseph S. B. Mitchell, David M. Mount, and Christos H. Papadimitriou. 1987. The discrete geodesic problem. SIAM Journal of Computing 16, 4, 647–668.
Dorian Nogneng and Maks Ovsjanikov. 2017. Informative descriptor preservation via commutativity for shape matching. In Annual Conference of the European Association for Computer Graphics (Eurographics’17).
Robert Osada, Thomas Funkhouser, Bernard Chazelle, and David Dobkin. 2002. Shape distributions. ACM Transaction on Graphics 21, 4, 807–832.
Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas. 2012. Functional maps: A flexible representation of maps between shapes. ACM Transactions on Graphics 31, 4, 30:1–30:11.
Maks Ovsjanikov, Etienne Corman, Michael Bronstein, Emanuele Rodolà, Mirela Ben-Chen, Leonidas Guibas, Frederic Chazal, and Alex Bronstein. 2016. Computing and processing correspondences with functional maps. In SIGGRAPH ASIA 2016 Courses. Article 9, 60 pages.
Giuseppe Patané. 2014. Laplacian spectral distances and kernels on 3D shapes. Pattern Recognition Letters 47 102–110.
Leonid Pishchulin, Stefanie Wuhrer, Thomas Helten, Christian Theobalt, and Bernt Schiele. 2015. Building statistical shape spaces for 3D human modeling. In ArXiv.
Jonathan Pokrass, Alexander M. Bronstein, Michael M. Bronstein, Pablo Sprechmann, and Guillermo Sapiro. 2013. Sparse modeling of intrinsic correspondences. In Computer Graphics Forum, Vol. 32. 459–468.
Helmut Pottmann, Johannes Wallner, Qi-Xing Huang, and Yong-Liang Yang. 2009. Integral invariants for robust geometry processing. Computer Aided Geometric Design 26, 1, 37–60.
Kathleen M. Robinette, Hans Daanen, and Eric Paquet. 1999. The CAESAR project: A 3-D surface anthropometry survey. In Second International Conference on 3-D Digital Imaging and Modeling (3DIM’99). IEEE, 380–386.
Emanuele Rodolà, Luca Cosmo, Michael M. Bronstein, Andrea Torsello, and Daniel Cremers. 2016. Partial functional correspondence. In Computer Graphics Forum.
Emanuele Rodola, S. Rota Bulò, Thomas Windheuser, Matthias Vestner, and Daniel Cremers. 2014. Dense non-rigid shape correspondence using random forests. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR’14). 4177–4184.
Lior Shapira, Ariel Shamir, and Daniel Cohen-Or. 2008. Consistent mesh partitioning and skeletonisation using the shape diameter function. The Visual Computer 24, 4, 249–259.
Robert W. Sumner, Matthias Zwicker, Craig Gotsman, and Jovan Popović. 2005. Mesh-based inverse kinematics. ACM Transaction on Graphics 24, 3, 488–495.
Jian Sun, Maks Ovsjanikov, and Leonidas J. Guibas. 2009. A concise and provably informative multi-scale signature based on heat diffusion. Computer Graphics Forum 28, 5, 1383–1392.
Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven J. Gortler, and Hugues Hoppe. 2005. Fast exact and approximate geodesics on meshes. ACM Transaction on Graphics 24, 3, 553–560.
J. W. Tangelder and R. C. Veltkamp. 2004. A survey of content based 3D shape retrieval methods. In IEEE International Conference on Shape Modeling and Applications (SMI’04). 145–156.
Federico Tombari, Samuele Salti, and Luigi Di Stefano. 2010. Unique signatures of histograms for local surface description. In International Conference on Computer Vision (ICCV’10). 356–369.
Shi-Qing Xin, Wenping Wang, Shuangmin Chen, Jieyu Zhao, and Zhenyu Shu. 2016. Intrinsic girth function for shape processing. ACM Transaction on Graphics 35, 3, 25:1–25:14.
Yong-Liang Yang, Yu-Kun Lai, Shi-Min Hu, and Helmut Pottmann. 2006. Robust principal curvatures on multiple scales. In Symposium on Geometry Processing (SGP’06). 223–226.
Andrei Zaharescu, Edmond Boyer, and Radu Horaud. 2012. Keypoints and local descriptors of scalar functions on 2D manifolds. International Journal of Computer Vision 100, 1, 78–98.
