Stable Topological Signatures for Points on 3D Shapes
Abstract
Comparing points on 3D shapes is among the fundamental operations in shape analysis. To facilitate this task, a great number of local point signatures or descriptors have been proposed in the past decades. However, the vast majority of these descriptors concentrate on the local geometry of the shape around the point, and thus are insensitive to its connectivity structure. By contrast, several global signatures have been proposed that successfully capture the overall topology of the shape and thus characterize the shape as a whole. In this paper, we propose the first point descriptor that captures the topology structure of the shape as ‘seen’ from a single point, in a multiscale and provably stable way. We also demonstrate how a large class of topological signatures, including ours, can be mapped to vectors, opening the door to many classical analysis and learning methods. We illustrate the performance of this approach on the problems of supervised shape labeling and shape matching. We show that our signatures provide complementary information to existing ones and allow to achieve better performance with less training data in both applications.
References
- Aubry M., Schlickewei U., Cremers D.: The wave kernel signature: A quantum mechanical approach to shape analysis. In Proc. 4DMOD, ICCV Workshops (2011), pp. 1626–1633. 3
- Bronstein A.M., Bronstein M.M., Guibas L.J., Ovsjanikov M.: Shape google: Geometric words and expressions for invariant shape retrieval. ACM TOG 30, 1 (Feb. 2011), 1:1–1:20. 2
- Burago D., Burago Y., Ivanov S.: A course in metric geometry, grad. Studies in Math 33 (2001). 7
- Bronstein A.M., Bronstein M.M., Kimmel R.: Numerical Geometry of Non-Rigid Shapes. Springer, 2008. 9
- Bendich P., Cohen-Steiner D., Edelsbrunner H., Harer J., Morozov D.: Inferring local homology from sampled stratified spaces. In Foundations of Computer Science, 2007. FOCS'07. 48th Annual IEEE Symposium on (2007), IEEE, pp. 536–546. 3
- Bronstein M.M., Kokkinos I.: Scale-invariant heat kernel signatures for non-rigid shape recognition. In Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on (2010), IEEE, pp. 1704–1711. 3
10.1109/CVPR.2010.5539838 Google Scholar
- Belongie S., Malik J., Puzicha J.: Shape context: A new descriptor for shape matching and object recognition. In NIPS (2000), vol. 2, p. 3. 2
- Bubenik P.: Statistical topology using persistence landscapes. arXiv preprint arXiv:1207.6437 (2012). 3
- Carlsson G.: Topology and data. Bulletin of the American Mathematical Society 46, 2 (2009), 255–308. 3
- Chazal F., Cohen-Steiner D., Glisse M., Guibas L.J., Oudot S.Y.: Proximity of persistence modules and their diagrams. In Proc. 25th Annu. Symposium on Computational Geometry (2009), pp. 237–246. 3
- Chazal F., Cohen-Steiner D., Guibas L.J., Mémoli F., Oudot S.Y.: Gromov-hausdorff stable signatures for shapes using persistence. In CGF (Proc. SGP) (2009), vol. 28, Wiley Online Library, pp. 1393–1403. 2, 3, 7
- Cerri A., di Fabio B., Jablonski G., Medri F.: Comparing shapes through multi-scale approximations of the matching distance. In Computer Vision and Image Understanding (CVIU) (Apr. 2014), vol. 121, pp. 43–56. 3
- Chazal F., de Silva V., Oudot S.: Persistence stability for geometric complexes. Geometriae Dedicata (2013), 1–22. 7
- Chen X., Golovinskiy A., Funkhouser T.: A benchmark for 3d mesh segmentation. ACM Transactions on Graphics (Proc. SIGGRAPH) 28, 3 (Aug. 2009). 10
- Chazal F., Guibas L.J., Oudot S.Y., Skraba P.: Persistence-based clustering in riemannian manifolds. Journal of the ACM (JACM) 60, 6 (2013), 41. 3
- Chua C.S., Jarvis R.: Point signatures: A new representation for 3d object recognition. Intl. J. Computer Vision 25, 1 (1997), 63–85. 2
- Cormen T.H., Leiserson C.E., Rivest R.L., Stein C.: Introduction to Algorithms, 2nd ed. MIT Press, Cambridge, MA, 2001. 8, 9
- Corman É., Ovsjanikov M., Chambolle A.: Supervised descriptor learning for non-rigid shape matching. In Proc. 6th Workshop on Non-Rigid Shape Analysis and Deformable Image Alignment (NORDIA) (2014). 9
- Carriere M., Oudot S., Ovsjanikov M.: Local Signatures using Persistence Diagrams. June 2015. URL: https://hal.inria.fr/hal-01159297. 7, 8
- Cohen-Steiner D., Edelsbrunner H., Harer J.: Extending persistence using poincaré and lefschetz duality. J. Found. of Computational Mathematics 9, 1 (2009), 79–103. 5
- Cuturi M.: Positive Definite Kernels in Machine Learning. ArXiv e-prints (Nov. 2009). arXiv:0911.5367. 5
- Carlsson G., Zomorodian A., Collins A., Guibas L.J.: Persistence barcodes for shapes. International Journal of Shape Modeling 11, 2 (2005), 149–187. 3
10.1142/S0218654305000761 Google Scholar
- Dey T.K., Li K., Luo C., Ranjan P., Safa I., Wang Y.: Persistent heat signature for pose-oblivious matching of incomplete models. Computer Graphics Forum (2010). 3
- de Silva V., Morozov D., Vejdemo-Johansson M.: Dualities in persistent (co)homology. Inverse Problems 27 (2011), 124003. 5
- Edelsbrunner H., Harer J.L.: Computational topology: an introduction. AMS Bookstore, 2010. 9
- Edelsbrunner H., Letscher D., Zomorodian A.: Topological persistence and simplification. Discrete and Computational Geometry 28 (2002), 511–533. 3
- Frome A., Huber D., Kolluri R., Bülow T., Malik J.: Recognizing objects in range data using regional point descriptors. In Proc. ECCV. 2004, pp. 224–237. 2
- Funkhouser T., Kazhdan M.: Shape-based retrieval and analysis of 3d models. In ACM SIGGRAPH 2004 Course Notes (2004), ACM, p. 16. 1
- Frosini P., Landi C.: Size theory as a topological tool for computer vision. Pattern Recognition and Image Analysis 9, 4 (1999), 596–603. 3
- Gal R., Shamir A., Cohen-Or D.: Pose-oblivious shape signature. Visualization and Computer Graphics, IEEE Transactions on 13, 2 (2007), 261–271. 2
- Hilaga M., Shinagawa Y., Kohmura T., Kunii T.: Topology matching for fully automatic similarity estimation of 3d shapes. In Proc. SIGGRAPH (2001), pp. 203–212. 2, 3
- Ion A., Peyré G., Haxhimusa Y., Peltier S., Kropatsch W.G., Cohen L.D., et al.: Shape matching using the geodesic eccentricity transform-a study. In Proc. OAGM/AAPR (2007), pp. 97–104. 2, 3
- Johnson A.E., Hebert M.: Using spin images for efficient object recognition in cluttered 3d scenes. Pattern Analysis and Machine Intelligence, IEEE Transactions on 21, 5 (1999), 433–449. 2
- Kalogerakis E., Hertzmann A., Singh K.: Learning 3d mesh segmentation and labeling. ACM Transactions on Graphics (TOG) 29, 4 (2010), 102. 1, 2, 9, 10, 11
- Kilian M., Mitra N.J., Pottmann H.: Geometric modeling in shape space. In ACM Transactions on Graphics (TOG) (2007), vol. 26, ACM, p. 64. 1
10.1145/1275808.1276457 Google Scholar
- Kalogerakis E., Simari P., Nowrouzezahrai D., Singh K.: Robust statistical estimation of curvature on discretized surfaces. In Proc. SGP (2007), pp. 13–22. 2
- Li X., Guskov I.: 3d object recognition from range images using pyramid matching. In Proc. ICCV (2007), pp. 1–6. 2
- Li C., Ovsjanikov M., Chazal F.: Persistence-based structural recognition. In Proc. CVPR (2014), IEEE, pp. 2003–2010. 2, 3, 7
- Martinek M., Ferstl M., Grosso R.: 3D Shape Matching based on Geodesic Distance Distributions. In Vision, Modeling and Visualization (2012), M. Goesele, T. Grosch, H. Theisel, K. Toennies, B. Preim, (Eds.). 3
- Manay S., Hong B.-W., Yezzi A., Soatto S.: Integral invariant signatures. In Proc. ECCV (2004), pp. 87–99. 2
- Morozov D.: Homological Illusions of Persistence and Stability. Ph.D. dissertation, Department of Computer Science, Duke University, 2008. 5, 10
- Ovsjanikov M., Ben-Chen M., Solomon J., Butscher A., Guibas L.: Functional maps: a flexible representation of maps between shapes. ACM Transactions on Graphics (TOG) 31, 4 (2012), 30. 9
- Pottmann H., Wallner J., Huang Q.-X., Yang Y.-L.: Integral invariants for robust geometry processing. Computer Aided Geometric Design 26, 1 (2009), 37–60. 2
- Skraba P., Ovsjanikov M., Chazal F., Guibas L.: Persistence-based segmentation of deformable shapes. In Proc. CVPR Workshops (2010), pp. 45–52. 2, 3
- Sun J., Ovsjanikov M., Guibas L.: A concise and provably informative multi-scale signature based on heat diffusion. In CGF (Proc. SGP) (2009), vol. 28, pp. 1383–1392. 3
- Sumner R.W., Popović J.: Deformation transfer for triangle meshes. In ACM Transactions on Graphics (TOG) (2004), vol. 23, ACM, pp. 399–405. 1
- Shapira L., Shamir A., Cohen-Or D.: Consistent mesh partitioning and skeletonisation using the shape diameter function. The Visual Computer 24, 4 (2008), 249–259. 2
- Surazhsky V., Surazhsky T., Kirsanov D., Gortler S.J., Hoppe H.: Fast exact and approximate geodesics on meshes. ACM Trans. Graph. 24, 3 (July 2005), 553–560. 8
- Verri A., Uras C., Frosini P., Ferri M.: On the use of size functions for shape analysis. Biological cybernetics 70, 2 (1993), 99–107. 3
- Yang Y.-L., Lai Y.-K., Hu S.-M., Pottmann H.: Robust principal curvatures on multiple scales. In Symposium on Geometry Processing (2006), pp. 223–226. 2
- Zomorodian A., Carlsson G.: Computing persistent homology. Discrete & Computational Geometry 33, 2 (2005), 249–274. 3