“Unsupervised co-segmentation of a set of shapes via descriptor-space spectral clustering” – ACM SIGGRAPH HISTORY ARCHIVES

“Unsupervised co-segmentation of a set of shapes via descriptor-space spectral clustering”

  • 2011-SA-Technical-Paper_Sidi_Unsupervised-Co-Segmentation-of-a-Set-of-Shapes-via-Descriptor-Space-Spectral-Clustering-3

Conference:


Type(s):


Title:

    Unsupervised co-segmentation of a set of shapes via descriptor-space spectral clustering

Session/Category Title:   Shape Analysis and Deformation

Presenter(s)/Author(s):


Abstract:


    We introduce an algorithm for unsupervised co-segmentation of a set of shapes so as to reveal the semantic shape parts and establish their correspondence across the set. The input set may exhibit significant shape variability where the shapes do not admit proper spatial alignment and the corresponding parts in any pair of shapes may be geometrically dissimilar. Our algorithm can handle such challenging input sets since, first, we perform co-analysis in a descriptor space, where a combination of shape descriptors relates the parts independently of their pose, location, and cardinality. Secondly, we exploit a key enabling feature of the input set, namely, dissimilar parts may be “linked” through third-parties present in the set. The links are derived from the pairwise similarities between the parts’ descriptors. To reveal such linkages, which may manifest themselves as anisotropic and non-linear structures in the descriptor space, we perform spectral clustering with the aid of diffusion maps. We show that with our approach, we are able to co-segment sets of shapes that possess significant variability, achieving results that are close to those of a supervised approach.

References:


    1. Biasotti, S., Giorgi, D., Spagnuolo, M., and Falcidieno, B. 2008. Reeb graphs for shape analysis and applications. Theoretical Computer Science 392, 1–3, 5–22. Google ScholarDigital Library
    2. Boykov, Y., Veksler, O., and Zabih, R. 2001. Fast approximate energy minimization via graph cuts. IEEE Trans. Pattern Anal. Mach. Intell. 23, 11, 1222–1239. Google ScholarDigital Library
    3. Chen, X., Golovinskiy, A., and Funkhouser, T. 2009. A benchmark for 3D mesh segmentation. ACM Trans. on Graphics (Proc. SIGGRAPH) 28, 3, 1–12. Google ScholarDigital Library
    4. Coifman, R. R., and Lafon, S. 2006. Diffusion maps. Applied and Computational Harmonic Analysis 21, 1, 5–30.Google ScholarCross Ref
    5. Comaniciu, D., and Meer, P. 2002. Mean shift: a robust approach towards feature space analysis. IEEE Trans. Pattern Anal. Mach. Intell. 24, 5, 603–619. Google ScholarDigital Library
    6. de Goes, F., Goldenstein, S., and Velho, L. 2008. A hierarchical segmentation of articulated bodies. Computer Graphics Forum (Proc. SGP) 27, 5, 1349–1356. Google ScholarDigital Library
    7. Fu, H., Cohen-Or, D., Dror, G., and Sheffer, A. 2008. Upright orientation of man-made objects. ACM Trans. on Graphics (Proc. SIGGRAPH) 27, 3, 1–8. Google ScholarDigital Library
    8. Gal, R., Sorkine, O., Mitra, N. J., and Cohen-Or, D. 2009. iWIRES: an analyze-and-edit approach to shape manipulation. ACM Trans. on Graphics (Proc. SIGGRAPH) 28, 3, 1–10. Google ScholarDigital Library
    9. Golovinskiy, A., and Funkhouser, T. 2009. Consistent segmentation of 3D models. Computers & Graphics (Proc. of SMI) 33, 3, 262–269. Google ScholarDigital Library
    10. Huang, Q., Koltun, V., and Guibas, L. 2011. Joint shape segmentation with linear programming. ACM Trans. on Graphics (Proc. SIGGRAPH Asia) 30, 6. Google ScholarDigital Library
    11. Joulin, A., Bach, F., and J. Ponce. 2010. Discriminative clustering for image co-segmentation. In Proc. IEEE Conf. on CVPR, 1943–1950.Google Scholar
    12. Kalogerakis, E., Hertzmann, A., and Singh, K. 2010. Learning 3D mesh segmentation and labeling. ACM Trans. on Graphics (Proc. SIGGRAPH) 29, 3, 1–11. Google ScholarDigital Library
    13. Kazhdan, M., Funkhouser, T., and Rusinkiewicz, S. 2004. Shape matching and anisotropy. ACM Trans. on Graphics 23, 3, 623–629. Google ScholarDigital Library
    14. Mitra, N. J., Yang, Y.-L., Yan, D.-M., Li, W., and Agrawala, M. 2010. Illustrating how mechanical assemblies work. ACM Trans. on Graphics (Proc. SIGGRAPH) 29, 4, 1–12. Google ScholarDigital Library
    15. 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
    16. Rother, C., Kolmogorov, V., Minka, T., and Blake, A. 2006. Cosegmentation of image pairs by histogram matching — incorporating a global constraint into MRFs. In Proc. IEEE Conf. on CVPR, 993–1000. Google ScholarDigital Library
    17. Shamir, A., Shapira, L., and Cohen-Or, D. 2006. Mesh analysis using geodesic mean-shift. The Visual Computer 22, 99–108. Google ScholarDigital Library
    18. Shamir, A. 2008. A survey on mesh segmentation techniques. Computer Graphics Forum 27, 6, 1539–1556.Google ScholarCross Ref
    19. Shapira, L., Shalom, S., Shamir, A., Cohen-Or, D., and Zhang, H. 2009. Contextual part analogies in 3D objects. Int. J. Comput. Vision 89, 2–3, 309–326. Google ScholarDigital Library
    20. Simari, P., Nowrouzezahrai, D., Kalogerakis, E., and Singh, K. 2009. Multi-objective shape segmentation and labeling. Computer Graphics Forum (Proc. SGP) 28, 5, 1415–1425. Google ScholarDigital Library
    21. van Kaick, O., Zhang, H., Hamarneh, G., and Cohen-Or, D. 2010. A survey on shape correspondence. In Proc. Eurographics State-of-the-Art Report, 1–23.Google Scholar
    22. van Kaick, O., Tagliasacchi, A., Sidi, O., Zhang, H., Cohen-Or, D., Wolf, L., and Hamarneh, G. 2011. Prior knowledge for part correspondence. Computer Graphics Forum (Proc. EUROGRAPHICS) 30, 2, 553–562.Google ScholarCross Ref
    23. 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 (Proc. EUROGRAPHICS) 30, 2, 287–296.Google ScholarCross Ref
    24. Xu, W., Wang, J., Yin, K., Zhou, K., van de Panne, M., Chen, F., and Guo, B. 2009. Joint-aware manipulation of deformable models. ACM Trans. on Graphics (Proc. SIGGRAPH) 28, 3, 1–9. Google ScholarDigital Library
    25. 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 Graphics (Proc. SIGGRAPH Asia) 29, 5, 1–9. Google ScholarDigital Library
    26. Zhang, H., van Kaick, O., and Dyer, R. 2010. Spectral mesh processing. Computer Graphics Forum 29, 6, 1865–1894.Google ScholarCross Ref

ACM Digital Library Publication:


Overview Page:


Submit a story:

If you would like to submit a story about this presentation, please contact us: historyarchives@siggraph.org