“SHED: shape edit distance for fine-grained shape similarity”
Conference:
Type(s):
Title:
- SHED: shape edit distance for fine-grained shape similarity
Session/Category Title: Shapes and Images
Presenter(s)/Author(s):
Abstract:
Computing similarities or distances between 3D shapes is a crucial building block for numerous tasks, including shape retrieval, exploration and classification. Current state-of-the-art distance measures mostly consider the overall appearance of the shapes and are less sensitive to fine changes in shape structure or geometry. We present shape edit distance (SHED) that measures the amount of effort needed to transform one shape into the other, in terms of re-arranging the parts of one shape to match the parts of the other shape, as well as possibly adding and removing parts. The shape edit distance takes into account both the similarity of the overall shape structure and the similarity of individual parts of the shapes. We show that SHED is favorable to state-of-the-art distance measures in a variety of applications and datasets, and is especially successful in scenarios where detecting fine details of the shapes is important, such as shape retrieval and exploration.
References:
1. Ankerst, M., Kastenmüller, G., Kriegel, H.-P., and Seidl, T. 1999. 3D shape histograms for similarity search and classification in spatial databases. In Proc. Int. Symp. Advances in Spatial Databases, 207–226.
2. Averkiou, M., Kim, V. G., Zheng, Y., and Mitra, N. J. 2014. ShapeSynth: Parameterizing model collections for coupled shape exploration and synthesis. Computer Graphics Forum (Eurographics) 33.
3. Barra, V., and Biasotti, S. 2013. 3D shape retrieval using kernels on extended Reeb graphs. Pattern Recognition 46, 11.
4. Berg, A. C., Berg, T. L., and Malik, J. 2005. Shape matching and object recognition using low distortion correspondences. In Proc. IEEE Conf. on CVPR, 26–33.
5. Bommes, D., Zimmer, H., and Kobbelt, L. 2012. Practical mixed-integer optimization for geometry processing. In Curves and Surfaces. Springer, 193–206.
6. Bronstein, A. M., Bronstein, M. M., Guibas, L. J., and Ovsjanikov, M. 2011. Shape Google: Geometric words and expressions for invariant shape retrieval. ACM Trans. on Graph 30, 1, 1:1–20.
7. Chen, D.-Y., Tian, X.-P., Shen, Y.-T., and Ouhyoung, M. 2003. On visual similarity based 3D model retrieval. Computer Graphics Forum 22, 3, 223–232.
8. Chen, X., Golovinskiy, A., and Funkhouser, T. 2009. A benchmark for 3D mesh segmentation. ACM Trans. on Graph (SIGGRAPH) 28, 3, 73:1–12.
9. Denning, J. D., and Pellacini, F. 2013. MeshGit: Diffing and merging meshes for polygonal modeling. ACM Trans. on Graph (SIGGRAPH) 32, 4, 35:1–10.
10. Fisher, M., Savva, M., and Hanrahan, P. 2011. Characterizing structural relationships in scenes using graph kernels. ACM Trans. on Graph (SIGGRAPH) 30, 4, 34:1–12.
11. Funkhouser, T., Kazhdan, M., Shilane, P., Min, P., Kiefer, W., Tal, A., Rusinkiewicz, S., and Dobkin, D. 2004. Modeling by example. ACM Trans. on Graph (SIGGRAPH) 23, 3, 652–663.
12. Gao, X., Xiao, B., Tao, D., and Li, X. 2010. A survey of graph edit distance. Pattern Anal. Appl. 13, 1, 113–129.
13. Harchaoui, Z., and Bach, F. 2007. Image classification with segmentation graph kernels. In Proc. IEEE Conf. on CVPR, 1–8.
14. Hilaga, M., Shinagawa, Y., Kohmura, T., and Kunii, T. L. 2001. Topology matching for fully automatic similarity estimation of 3D shapes. In Proc.SIGGRAPH, 203–212.
15. Huang, Q., Koltun, V., and Guibas, L. 2011. Joint shape segmentation with linear programming. ACM Trans. on Graph (SIGGRAPH Asia) 30, 6, 125:1–12.
16. Huang, Q.-X., Su, H., and Guibas, L. 2013. Fine-grained semi-supervised labeling of large shape collections. ACM Transactions on Graphics (TOG) 32, 6, 190.
17. Huang, S.-S., Shamir, A., Shen, C.-H., Zhang, H., Sheffer, A., Hu, S.-M., and Cohen-Or, D. 2013. Qualitative organization of collections of shapes via quartet analysis. ACM Trans. on Graph (SIGGRAPH) 32, 4, 71:1–10.
18. Kalogerakis, E., Chaudhuri, S., Koller, D., and Koltun, V. 2012. A probabilistic model of component-based shape synthesis. ACM Trans. on Graph (SIGGRAPH) 31, 4, 55:1–11.
19. Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2003. Rotation invariant spherical harmonic representation of 3D shape descriptors. In Symp. on Geom. Proc., 156–164.
20. Kezurer, I., Kovalsky, S. Z., Basri, R., and Lipman, Y. 2015. Tight relaxation of quadratic matching. Computer Graphics Forum 24, 5.
21. Kim, V. G., Li, W., Mitra, N. J., DiVerdi, S., and Funkhouser, T. 2012. Exploring collections of 3D models using fuzzy correspondences. ACM Trans. on Graph (SIGGRAPH) 31, 4, 54:1–11.
22. Kim, V. G., Li, W., Mitra, N. J., Chaudhuri, S., DiVerdi, S., and Funkhouser, T. 2013. Learning part-based templates from large collections of 3D shapes. ACM Trans. on Graph (SIGGRAPH) 32, 4, 70:1–12.
23. Kleiman, Y., Fish, N., Lanir, J., and Cohen-Or, D. 2013. Dynamic maps for exploring and browsing shapes. Computer Graphics Forum (SGP) 32, 5, 187–196.
24. Kurtek, S., Srivastava, A., Klassen, E., and Laga, H. 2013. Landmark-guided elastic shape analysis of spherically-parameterized surfaces. Computer Graphics Forum 32, 2pt4, 429–438.
25. Laga, H., Mortara, M., and Spagnuolo, M. 2013. Geometry and context for semantic correspondences and functionality recognition in man-made 3D shapes. ACM Trans. on Graph 32, 5, 150:1–16.
26. Leordeanu, M., and Hebert, M. 2005. A spectral technique for correspondence problems using pairwise constraints. In Proc. Int. Conf. on Comp. Vis., 1482–1489.
27. Li, B., Godil, A., Aono, M., Bai, X., Furuya, T., Li, L., Lopez-Sastre, R., Johan, H., Ohbuchi, R., Redondo-Cabrera, C., Tatsuma, A., Yanagimachi, T., and Zhang, S. 2012. SHREC’12 track: Generic 3D shape retrieval. In Eurographics Workshop on 3D Object Retrieval (3DOR), M. Spagnuolo, M. Bronstein, A. Bronstein, and A. Ferreira, Eds.
28. Litman, R., Bronstein, A., Bronstein, M., and Castellani, U. 2014. Supervised learning of bag-of-features shape descriptors using sparse coding. Computer Graphics Forum 33, 5, 127–136.
29. Lyzinski, V., Fishkind, D., Fiori, M., Vogelstein, J., Priebe, C., and Sapiro, G. 2015. Graph matching: relax at your own risk. IEEE TPAMI.
30. Mitra, N. J., Wand, M., Zhang, H., Cohen-Or, D., and Bokeloh, M. 2013. Structure-aware shape processing. In Proc. Eurographics State-of-the-art Reports.
31. Neuhaus, M., and Bunke, H. 2007. Bridging the Gap Between Graph Edit Distance and Kernel Machines. World Scientific, River Edge, NJ, USA.
32. Osada, R., Funkhouser, T., Chazelle, B., and Dobkin, D. 2002. Shape distributions. ACM Trans. on Graph 21, 4, 807–832.
33. Ovsjanikov, M., Mérigot, Q., Mémoli, F., and Guibas, L. 2010. One point isometric matching with the heat kernel. Computer Graphics Forum (SGP) 29, 5, 1555–1564.
34. Ovsjanikov, M., Li, W., Guibas, L., and Mitra, N. J. 2011. Exploration of continuous variability in collections of 3D shapes. ACM Trans. on Graph (SIGGRAPH) 30, 4, 33:1–10.
35. Rustamov, R. M. 2007. Laplace-Beltrami eigenfunctions for deformation invariant shape representation. In Symp. on Geom. Proc., 225–233.
36. Schultz, M., and Joachims, T. 2004. Learning a distance metric from relative comparisons. Advances in neural information processing systems (NIPS), 41.
37. Sebastian, T., Klein, P., and Kimia, B. 2004. Recognition of shapes by editing their shock graphs. IEEE Trans. Pat. Ana. & Mach. Int. 26, 5, 550–571.
38. Shamir, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 27, 6, 1539–1556.
39. Shapira, L., Shamir, A., and Cohen-Or, D. 2008. Consistent mesh partitioning and skeletonisation using the shape diameter function. The Visual Computer 24, 4, 249–259.
40. Sidi, O., van Kaick, O., Kleiman, Y., Zhang, H., and Cohen-Or, D. 2011. Unsupervised co-segmentation of a set of shapes via descriptor-space spectral clustering. ACM Trans. on Graph (SIGGRAPH Asia) 30, 6, 126:1–10.
41. Sundar, H., Silver, D., Gagvani, N., and Dickinson, S. 2003. Skeleton based shape matching and retrieval. In Shape Modeling International, 130–139.
42. Tangelder, J. W. H., and Veltkamp, R. C. 2008. A survey of content based 3D shape retrieval methods. Multimedia Tools and Applications 39, 3, 441–471.
43. van Kaick, O., Fish, N., Kleiman, Y., Asafi, S., and Cohen-Or, D. 2014. Shape segmentation by approximate convexity analysis. ACM Trans. Graph. 34, 1, 4:1–11.
44. Wang, Y., Asafi, S., van Kaick, O., Zhang, H., Cohen-Or, D., and Chen, B. 2012. Active co-analysis of a set of shapes. ACM Trans. on Graph (SIGGRAPH Asia) 31, 6, 157:1–10.
45. Xu, K., Li, H., Zhang, H., Cohen-Or, D., Xiong, Y., and Cheng, Z. 2010. Style-content separation by anisotropic part scales. ACM Trans. on Graph (SIGGRAPH Asia) 29, 6.
46. Zelnik-Manor, L., and Perona, P. 2004. Self-tuning spectral clustering. In NIPS, vol. 17, 1601–1608.
47. Zheng, Y., Cohen-Or, D., Averkiou, M., and Mitra, N. J. 2014. Recurring part arrangements in shape collections. Computer Graphics Forum (Eurographics) 33.
