“Co-hierarchical analysis of shape structures” by Kaick, Xu, Zhang, Wang, Sun, et al. …

  • ©Oliver van Kaick, Kai Xu, Hao Zhang, Yanzhen Wang, Shuyang Sun, Ariel Shamir, and Daniel Cohen-Or



Session Title:

    Shape Analysis


    Co-hierarchical analysis of shape structures




    We introduce an unsupervised co-hierarchical analysis of a set of shapes, aimed at discovering their hierarchical part structures and revealing relations between geometrically dissimilar yet functionally equivalent shape parts across the set. The core problem is that of representative co-selection. For each shape in the set, one representative hierarchy (tree) is selected from among many possible interpretations of the hierarchical structure of the shape. Collectively, the selected tree representatives maximize the within-cluster structural similarity among them. We develop an iterative algorithm for representative co-selection. At each step, a novel cluster-and-select scheme is applied to a set of candidate trees for all the shapes. The tree-to-tree distance for clustering caters to structural shape analysis by focusing on spatial arrangement of shape parts, rather than their geometric details. The final set of representative trees are unified to form a structural co-hierarchy. We demonstrate co-hierarchical analysis on families of man-made shapes exhibiting high degrees of geometric and finer-scale structural variabilities.


    1. Attene, M., Falcidieno, B., and Spagnuolo, M. 2006. Hierarchical mesh segmentation based on fitting primitives. Visual Computer 22, 3, 181–193. Google ScholarDigital Library
    2. Carlson-Radvansky, L., Covey, E., and Lattanzi, K. 1999. “What” effects on “where”: Functional influence on spatial relations. Psychological Science 10, 6, 519–521.Google ScholarCross Ref
    3. Chaudhuri, S., Kalogerakis, E., Guibas, L., and Koltun, V. 2011. Probabilistic reasoning for assembly-based 3D modeling. ACM Trans. on Graph (SIGGRAPH) 30, 4. Google ScholarDigital Library
    4. Chen, X., Golovinskiy, A., and Funkhouser, T. 2009. A benchmark for 3D mesh segmentation. ACM Trans. on Graph (SIGGRAPH) 28, 3, 73:1–12. Google ScholarDigital Library
    5. de Goes, F., Goldenstein, S., and Velho, L. 2008. A hierarchical segmentation of articulated bodies. Computer Graphics Forum (SGP) 27, 5, 1349–1356. Google ScholarDigital Library
    6. Everitt, B. S., Landau, S., Leese, M., and Stahl, D. 2011. Cluster Analysis. Series in Probability and Statistics. Wiley.Google Scholar
    7. Fisher, M., Savva, M., and Hanrahan, P. 2011. Characterizing structural relationships in scenes using graph kernels. ACM Trans. on Graph (SIGGRAPH) 30, 4. Google ScholarDigital Library
    8. Goldman, R. N. 1992. Decomposing linear and affine transformations. In Graphics Gems III. Academic Press, 108–116. Google ScholarDigital Library
    9. Golovinskiy, A., and Funkhouser, T. 2008. Randomized cuts for 3D mesh analysis. ACM Trans. on Graph 27, 5, 1–12. Google ScholarDigital Library
    10. Golovinskiy, A., and Funkhouser, T. 2009. Consistent segmentation of 3D models. Computers & Graphics (Proc. of SMI) 33, 3, 262–269. Google ScholarDigital Library
    11. Hoffman, D. D., and Richards, W. A. 1984. Parts of recognition. Cognition, 65–96.Google Scholar
    12. Huang, Q., Koltun, V., and Guibas, L. 2011. Joint shape segmentation with linear programming. ACM Trans. on Graph (SIGGRAPH Asia) 30, 6. Google ScholarDigital Library
    13. Jain, A., Thormählen, T., Ritschel, T., and Seidel, H.-P. 2012. Exploring shape variations by 3D-model decomposition and part-based recombination. Computer Graphics Forum (Eurographics) 31, 2. Google ScholarDigital Library
    14. Kalogerakis, E., Hertzmann, A., and Singh, K. 2010. Learning 3D mesh segmentation and labeling. ACM Trans. on Graph (SIGGRAPH) 29, 3, 102:1–12. Google ScholarDigital Library
    15. 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. Google ScholarDigital Library
    16. Katz, S., and Tal, A. 2003. Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Trans. on Graph (SIGGRAPH) 22, 3, 954–961. Google ScholarDigital Library
    17. Kim, Y. M., Mitra, N., Yan, D., and Guibas, L. 2012. Acquiring 3D indoor environments with variability and repetition. ACM Trans. on Graph (SIGGRAPH Asia) 31, 6. Google ScholarDigital Library
    18. Kraevoy, V., Julius, D., and Sheffer, A. 2007. Model composition from interchangeable components. In Proc. Pacific Graphics, 129–138. Google ScholarDigital Library
    19. Liu, R., and Zhang, H. 2007. Mesh segmentation via spectral embedding and contour analysis. Computer Graphics Forum (Eurographics) 26, 3, 385–394.Google ScholarCross Ref
    20. Martinet, A. 2007. Structuring 3D Geometry based on Symmetry and Instancing Information. PhD thesis, INP Grenoble.Google Scholar
    21. Mitra, N. J., Yang, Y.-L., Yan, D.-M., Li, W., and Agrawala, M. 2010. Illustrating how mechanical assemblies work. ACM Trans. on Graph (SIGGRAPH) 29, 58:1–58:12. Google ScholarDigital Library
    22. Nadler, B., Lafon, S., Coifman, R. R., and Kevrekidis, I. G. 2005. Diffusion maps, spectral clustering and eigenfunctions of Fokker-Planck operators. In NIPS, 1–8.Google Scholar
    23. 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. Google ScholarDigital Library
    24. Palmer, S. E. 1977. Hierarchical structure in perceptual representation. Cognitive Psychology 9, 4, 441–474.Google ScholarCross Ref
    25. Rose, R. C., and Karnowski, T. P. 2010. Deep machine learning – a new frontier in artificial intelligence research. IEEE Computational Intelligence Magazine 5, 4, 13–18. Google ScholarDigital Library
    26. Shamir, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 27, 6, 1539–1556.Google ScholarCross Ref
    27. Shapira, L., Shalom, S., Shamir, A., Cohen-Or, D., and Zhang, H. 2010. Contextual part analogies in 3D objects. Int. J. Comp. Vis. 89, 1–2, 309–326. Google ScholarDigital Library
    28. 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. Google ScholarDigital Library
    29. Sudderth, E. B., Torralba, A., Freeman, W. T., and Willsk, A. S. 2005. Learning hierarchical models of scenes, objects, and parts. In Proc. Int. Conf. on Comp. Vis., 1331–1338. Google ScholarDigital Library
    30. Torsello, A., Hidovic-Rowe, D., and Pelillo, M. 2005. Polynomial-time metrics for attributed trees. IEEE Trans. Pat. Ana. & Mach. Int. 27, 7, 1087–1099. Google ScholarDigital Library
    31. Wang, Y., Xu, K., Li, J., Zhang, H., Shamir, A., Liu, L., Cheng, Z., and Xiong, Y. 2011. Symmetry hierarchy of man-made objects. Computer Graphics Forum (Eurographics) 30, 2, 287–296.Google ScholarCross Ref
    32. 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. Google ScholarDigital Library
    33. Wolf, L., Bileschi, S., and Meyers, E. 2006. Perception strategies in hierarchical vision systems. In Proc. IEEE Conf. on Comp. Vis. and Pat. Rec., 2153–2160. Google ScholarDigital Library
    34. 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, 184:1–9. Google ScholarDigital Library
    35. Xu, K., Zhang, H., Cohen-Or, D., and Chen, B. 2012. Fit and diverse: Set evolution for inspiring 3D shape galleries. ACM Trans. on Graph (SIGGRAPH) 31, 4. Google ScholarDigital Library
    36. Yumer, M., and Kara, L. 2012. Co-abstraction of shape collections. ACM Trans. on Graph (SIGGRAPH Asia) 31, 6. Google ScholarDigital Library
    37. Zhang, M.-L., and Zhou, Z.-H. 2009. Multi-instance clustering with applications to multi-instance prediction. Applied Intelligence 31, 47–68. Google ScholarDigital Library
    38. Zheng, Y., Cohen-Or, D., and Mitra, N. J. 2013. Functional substructures for part compatibility. Computer Graphics Forum (Eurographics) 32, 2.Google ScholarCross Ref

ACM Digital Library Publication: