We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 28 Issue 5
September  2013
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Hao-Peng Lei, Xiao-Nan Luo, Shu-Jin Lin, Jian-Qiang Sheng. Automatic 3D Shape Co-Segmentation Using Spectral Graph Method[J]. Journal of Computer Science and Technology, 2013, 28(5): 919-929. DOI: 10.1007/s11390-013-1387-4
Citation: Hao-Peng Lei, Xiao-Nan Luo, Shu-Jin Lin, Jian-Qiang Sheng. Automatic 3D Shape Co-Segmentation Using Spectral Graph Method[J]. Journal of Computer Science and Technology, 2013, 28(5): 919-929. DOI: 10.1007/s11390-013-1387-4
shu

Automatic 3D Shape Co-Segmentation Using Spectral Graph Method

  • 1 School of Information Science & Technology, Sun Yat-sen University, Guangzhou 510006, China;
    2 National Engineering Research Center of Digital Life, Guangzhou 510006, China;
    3 Research Institute of Sun Yat-sen University in Shenzhen, Shenzhen 518057, China;
    4 School of Communication & Design, Sun Yat-sen University, Guangzhou 510006, China

Funds: This work is supported by the National Basic Research 973 Program of China under Grant No. 2013CB329505, the National Natural Science Foundation of China Guangdong Joint Fund under Grant Nos. U1135005, U1201252, and the National Natural Science Foundation of China under Grant Nos. 61103162, 61232011.
More Information
  • Received Date: November 13, 2012
  • Revised Date: May 20, 2013
  • Published Date: September 04, 2013
    Abstract
  • Co-analyzing a set of 3D shapes is a challenging task considering a large geometrical variability of the shapes. To address this challenge, this paper proposes a new automatic 3D shape co-segmentation algorithm by using spectral graph method. Our method firstly represents input shapes as a set of weighted graphs and extracts multiple geometric features to measure the similarities of faces in each individual shape. Secondly all graphs are embedded into the spectral domain to find meaningful correspondences across the set. After that we build a joint weighted matrix for the graph set and then apply normalized cut criterion to find optimal co-segmentation of the input shapes. Finally we evaluate our approach on different categories of 3D shapes, and the experimental results demonstrate that our method can accurately co-segment a wide variety of shapes, which may have different poses and significant topology changes.
    • FullText(HTML)
    • References (31)
  • [1]
    Attene M, Katz S, Mortara M et al. Mesh segmentation | A comparative study. In Proc. the IEEE International Conference on Shape Modeling and Applications, June 2006.
    [2]
    Katz S, Tal A. Hierarchical mesh decomposition using fuzzy clustering and cuts. ACM Transactions on Graphics, 2003, 22(3): 954-961.
    [3]
    Katz S, Leifman G, Tal A. Mesh segmentation using feature point and core extraction. The Visual Computer, 2005, 21(8/10): 649-658.
    [4]
    Agathos A, Pratikakis I, Perantonis S, Sapidis N. Protrusionoriented 3D mesh segmentation. The Visual Computer, 2010, 26(1): 63-81.
    [5]
    Liu R, Zhang H. Mesh segmentation via spectral embedding and contour analysis. Computer Graphics Forum, 2007, 26(3): 385-394.
    [6]
    Shapira L, Shamir A, Cohen-Or D. Consistent mesh partitioning and skeletonisation using the shape diameter function. The Visual Computer, 2008, 24(4): 249-259.
    [7]
    Golovinskiy A, Funkhouser T. Randomized cuts for 3D mesh analysis. ACM Transactions on Graphics, 2008, 27(5): Article No.145.
    [8]
    Kalogerakis E, Hertzmann A, Singh K. Learning 3D mesh segmentation and labeling. ACM Transactions on Graphics, 2010, 29(4): Article No.102.
    [9]
    Golovinskiy A, Funkhouser T. Consistent segmentation of 3D models. Computers & Graphics, 2009, 33(3): 262-269.
    [10]
    Sidi O, van Kaick O, Kleiman Y, Zhang H, Cohen-Or D. Unsupervised co-segmentation of a set of shapes via descriptorspace spectral clustering. ACM Transactions on Graphics, 2011, 30(6): Article No.126.
    [11]
    Huang Q, Koltun V, Guibas L. Joint shape segmentation with linear programming. ACM Transactions on Graphics, 2011, 30(6): Article No.125.
    [12]
    Meng M, Xia J, Luo J, He Y. Unsupervised co-segmentation for 3D shapes using iterative multi-label optimization. Computer-Aided Design, 2013, 45(2): 312-320.
    [13]
    Hu R, Fan L, Liu L. Co-segmentation of 3D shapes via subspace clustering. Computer Graphics Forum, 2012, 31(5): 1703-1713.
    [14]
    Rother C, Minka T, Blake A, Kolmogorov V. Cosegmentation of image pairs by histogram matching-incorporating a global constraint into MRFs. In Proc. the IEEE International Conference on Computer Vision and Pattern Recognition, July 2006, pp.993-1000.
    [15]
    Hochbaum D, Singh V. An effcient algorithm for cosegmentation. In Proc. the 12th IEEE Int. Conf. Computer Vision, Sept. 29-Oct. 2, 2009, pp.269-276.
    [16]
    Toshev A, Shi J, Daniilidis K. Image matching via saliency region correspondences. In Proc. the IEEE Int. Conf. Computer Vision and Pattern Recognition, June 2007.
    [17]
    Joulin A, Bach F, Ponce J. Discriminative clustering for image co-segmentation. In Proc. the IEEE Int. Conf. Computer Vision and Pattern Recognition, June 2010, pp.1943-1950.
    [18]
    van Kaick O, Zhang H, Hamarneh G, Cohen-Or D. A survey on shape correspondence. Computer Graphics Forum, 2011, 30(6): 1681-1707.
    [19]
    Besl P, McKay N. A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, 14(2): 239-256.
    [20]
    Elad A, Kimmel R. On bending invariant signatures for surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(10): 1285-1295.
    [21]
    Jain V, Zhang H, van Kaick O. Non-rigid spectral correspondence of triangle meshes. International Journal of Shape Modeling, 2007, 13(1): 101-124.
    [22]
    Mateus D, Horaud R, Knossow D, Cuzzolin F, Boyer E. Articulated shape matching using Laplacian eigenfunctions and unsupervised point registration. In Proc. the IEEE Int. Conf. Computer Vision and Pattern Recognition, June 2008.
    [23]
    Hilaga M, Shinagawa Y, Kohmura T, Kunii T. Topology matching for fully automatic similarity estimation of 3D shapes. In Proc. the 28th Annual Conf. Computer Graphics and Interactive Techniques, August 2001, pp.203-212.
    [24]
    Umeyama S. An eigendecomposition approach to weighted graph matching problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1988, 10(5): 695-703.
    [25]
    Horaud R, Forbes F, Yguel M, Dewaele G, Zhang J. Rigid and articulated point registration with expectation conditional maximization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(3): 587-602.
    [26]
    Chen X, Golovinskiy A, Funkhouser T. A benchmark for 3D mesh segmentation. ACM Transactions on Graphics, 2009, 28(3): Article No.73.
    [27]
    Shi J, Malik J. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.
    [28]
    Yu S, Shi J. Multiclass spectral clustering. In Proc. the 9th IEEE International Conference on Computer Vision, Oct. 2003, pp.313-319.
    [29]
    Boykov Y, Veksler O, Zabih R. Fast approximate energy minimization via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(11): 1222-1239.
    [30]
    Garland M, Heckbert P S. Surface simplification using quadric error metrics. In Proc. the 24th Conf. Computer Graphics and Interactive Techniques, Aug. 1997, pp.209-216.
    [31]
    Shapira L, Shalom S, Shamir A, Cohen-Or D, Zhang H. Contextual part analogies in 3D objects. International Journal of Computer Vision, 2010, 89(2/3): 309-326.
    • Relative Articles

  • Related Articles

    [1]Zhi-Han Chen, Shao-Wei Cai, Jian Gao, Shi-Ke Ge, Chan-Juan Liu, Jin-Kun Lin. Heuristic Search with Cut Point Based Strategy for Critical Node Problem[J]. Journal of Computer Science and Technology, 2024, 39(6): 1328-1340. DOI: 10.1007/s11390-024-2850-0
    [2]William Croft, Jörg-Rüdiger Sack, Wei Shi. Differential Privacy via a Truncated and Normalized Laplace Mechanism[J]. Journal of Computer Science and Technology, 2022, 37(2): 369-388. DOI: 10.1007/s11390-020-0193-z
    [3]Zhao-Peng Li, Yu Zhang, Yi-Yun Chen. A Shape Graph Logic and A Shape System[J]. Journal of Computer Science and Technology, 2013, 28(6): 1063-1084. DOI: 10.1007/s11390-013-1398-1
    [4]MA Jun, MA Shaohan. An Efficient Parallel Graph Edge Matching Algorithmand Its Applications[J]. Journal of Computer Science and Technology, 1999, 14(2): 153-158.
    [5]wang Zhenyu. ρ Graph: Rendezvous Ordering Graph forAda Concurrent Programs[J]. Journal of Computer Science and Technology, 1998, 13(6): 615-622.
    [6]Fu Yuxi. Reaction Graph[J]. Journal of Computer Science and Technology, 1998, 13(6): 510-530.
    [7]Wang Shitong. Normalized Exponential Neural Networks[J]. Journal of Computer Science and Technology, 1998, 13(4): 375-383.
    [8]Wang Dingxing, Zheng Weimin, Du Xiaoli, Guo Yike. On the Execution Mechanisms of Parallel Graph Reduction[J]. Journal of Computer Science and Technology, 1990, 5(4): 333-346.
    [9]Zhu Mingyuan. Two Congruent Semantics for Prolog with CUT[J]. Journal of Computer Science and Technology, 1990, 5(1): 82-91.
    [10]Li Hao, Liu Qun. A Problem of Tree Graph[J]. Journal of Computer Science and Technology, 1989, 4(1): 61-66.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (32) PDF downloads (2333) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return