Abstract
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.
Supplemental Material
Available for Download
Supplemental material.
- Attene, M., Falcidieno, B., and Spagnuolo, M. 2006. Hierarchical mesh segmentation based on fitting primitives. Visual Computer 22, 3, 181--193. Google ScholarDigital Library
- 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
- 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
- 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
- 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
- Everitt, B. S., Landau, S., Leese, M., and Stahl, D. 2011. Cluster Analysis. Series in Probability and Statistics. Wiley.Google Scholar
- 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
- Goldman, R. N. 1992. Decomposing linear and affine transformations. In Graphics Gems III. Academic Press, 108--116. Google ScholarDigital Library
- Golovinskiy, A., and Funkhouser, T. 2008. Randomized cuts for 3D mesh analysis. ACM Trans. on Graph 27, 5, 1--12. Google ScholarDigital Library
- Golovinskiy, A., and Funkhouser, T. 2009. Consistent segmentation of 3D models. Computers & Graphics (Proc. of SMI) 33, 3, 262--269. Google ScholarDigital Library
- Hoffman, D. D., and Richards, W. A. 1984. Parts of recognition. Cognition, 65--96.Google Scholar
- 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
- 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
- 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
- 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
- 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
- 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
- Kraevoy, V., Julius, D., and Sheffer, A. 2007. Model composition from interchangeable components. In Proc. Pacific Graphics, 129--138. Google ScholarDigital Library
- 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
- Martinet, A. 2007. Structuring 3D Geometry based on Symmetry and Instancing Information. PhD thesis, INP Grenoble.Google Scholar
- 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
- 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
- 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
- Palmer, S. E. 1977. Hierarchical structure in perceptual representation. Cognitive Psychology 9, 4, 441--474.Google ScholarCross Ref
- 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
- Shamir, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 27, 6, 1539--1556.Google ScholarCross Ref
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Yumer, M., and Kara, L. 2012. Co-abstraction of shape collections. ACM Trans. on Graph (SIGGRAPH Asia) 31, 6. Google ScholarDigital Library
- 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
- Zheng, Y., Cohen-Or, D., and Mitra, N. J. 2013. Functional substructures for part compatibility. Computer Graphics Forum (Eurographics) 32, 2.Google ScholarCross Ref
Index Terms
- Co-hierarchical analysis of shape structures
Recommendations
Hierarchical Spherical Deformation for Shape Correspondence
Medical Image Computing and Computer Assisted Intervention – MICCAI 2018AbstractWe present novel spherical deformation for a landmark-free shape correspondence in a group-wise manner. In this work, we aim at both addressing template selection bias and minimizing registration distortion in a single framework. The proposed ...
Ricci Flow for 3D Shape Analysis
Ricci flow is a powerful curvature flow method, which is invariant to rigid motion, scaling, isometric, and conformal deformations. We present the first application of surface Ricci flow in computer vision. Previous methods based on conformal geometry, ...
Hierarchical shape description using skeletons
MMM'07: Proceedings of the 13th international conference on Multimedia Modeling - Volume Part IThis article presents a skeleton-based shape description scheme called a skeleton tree. A skeleton tree represents an object shape as a hierarchical structure where high-level nodes describe parts of coarse trunk of the object and low-level nodes ...
Comments