Volume 30 Issue 3
May  2021
Turn off MathJax
Article Contents
LI Lingfei, WU Tieru. Automatic Spectral Method of Mesh Segmentation Based on Fiedler Residual[J]. Chinese Journal of Electronics, 2021, 30(3): 426-436. doi: 10.1049/cje.2020.11.001
Citation: LI Lingfei, WU Tieru. Automatic Spectral Method of Mesh Segmentation Based on Fiedler Residual[J]. Chinese Journal of Electronics, 2021, 30(3): 426-436. doi: 10.1049/cje.2020.11.001

Automatic Spectral Method of Mesh Segmentation Based on Fiedler Residual

doi: 10.1049/cje.2020.11.001

This work is supported by the National Natural Science Foundation of China (No.61373003, No.61872162).

  • Received Date: 2020-05-09
  • In this paper, we propose a fully automatic mesh segmentation method, which divides meshes into sub-meshes recursively through spectral analysis. A common problem in the spectral analysis of geometric processing is how to choose the specific eigenvectors and the number of these vectors for analysis and processing. This method tackles this problem with only one eigenvector, i.e. Fiedler vector. In addition, using only one eigenvector drastically reduces the cost of computing. Different from the Fiedler vector commonly used in the bipartition of graphs and meshes, this method finds multiple parts in only one iteration, vastly reducing the number of iterations and thus the time of operation, because each iteration produces as many correct boundaries as possible, instead of only one. We have tested this method on many 3D models, the results of which suggest the proposed method performs better than many advanced methods of recent years.
  • loading
  • P. Theologou, I. Pratikakis and T. Theoharis, “A review on 3D object retrieval methodologies using a part-based representation”, Computer-Aided Design and Applications, Vol.11, No.6, pp.670–684, 2014.
    A. Maglo, I. Grimstead and C. Hudelot, “Cluster-based random accessible and progressive lossless compression of colored triangular meshes for interactive visualization”. Proc. of Computer Graphics International 2011 Conference, Ottawa, Canada, Article ID: S16, 4 pages, 2011.
    E. Kalogerakis, S. Chaudhuri, D. Koller, et al., “A probabilistic model for component-based shape synthesis”, ACM Transactions on Graphics, Vol.31, No.4, Article No.55, 11 pages, 2012.
    A. Shamir, “A survey on mesh segmentation techniques”, Computer Graphics Forum, Vol.27, No.6, pp.1539–1556, 2008.
    P. Theologou, I. Pratikakis and T. Theoharis, “A comprehensive overview of methodologies and performance evaluation frameworks in 3D mesh segmentation”, Computer Vision and Image Understanding, Vol.135, pp.49–82, 2015.
    G. Taubin, “A signal processing approach to fair surface design”, Proc. of the 22nd Annual Conference on Computer Graphics and Interactive Techniques, Los Angeles, California, USA, pp.351–358, 1995.
    P. Mullen, Y.Y. Tong and P. Alliez, et al., “Spectral conformal parameterization”, Computer Computer Forum, Vol.27, No.5, pp.1487–1494, 2008.
    B. LéZvy and H. Zhang, “Spectral mesh processing”, SIGGRAPH’ 10: ACM SIGGRAPH 2010 Courses, Los Angeles, California, USA, Article No.8, 312 pages, 2010.
    G. Patané, “An introduction to Laplacian spectral distances and kernels: Theory, computation, and applications”, SIGGRAPH’17: ACM SIGGRAPH 2017 Courses, Los Angeles, California, USA, Article No.3, 54 pages, 2017.
    H. Zhang and R. Liu, “Mesh segmentation via recursive and visually salient spectral cuts”, Proc. of Vision, Modeling, and Visualization 2005, Erlangen, Germany, pp.429–436, 2005.
    R. Liu and H. Zhang, “Mesh segmentation via spectral embedding and contour analysis”, Computer Graphics Forum, Vol.26, No.3, pp.385–394, 2007.
    W.H. Tong, X.K. Yang, M.D. Pan, et al., “Spectral mesh segmentation via l0 gradient minimization”, IEEE Transactions on Visualization and Computer Graphics, Vol.26, No.4, pp.1807–1820, 2020.
    O.K.C. Au, Y.Y. Zheng, M.L. Chen, et al., “Mesh segmentation with concavity-aware fields”, IEEE Transactions on Visualization and Computer Graphics, Vol.18, No.17, pp.1125–1134, 2012.
    H. Wang, T. Lu, O.K.C. Au, et al., “Spectral 3D mesh segmentation with a novel single segmentation field”, Graphical Models, Vol.76, No.5, pp.440–456, 2014.
    R. Liu and H. Zhang, “Segmentation of 3D meshes through spectral clustering”, Proc. of the Computer Graphics and Applications, 12th Pacific Conference (PG ’04), Seoul, Korea, pp.298–305, 2004.
    J.Y. Zhang, J.M. Zheng, C.L. Wu, et al., “Variational mesh decomposition”, ACM Transactions on Graphics, Vol.31, No.3, Article No.21, 14 pages, 2012.
    P. Theologou, I. Pratikakis and T. Theoharis, “Unsupervised spectral mesh segmentation driven by heterogeneous graphs”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.39, No.2, pp.397–410, 2017.
    M. Brand and K. Huang, “A unifying theorem for spectral embedding and clustering”, Proc. of the 9th International Conference on Artificial Intelligence and Statistics, Key West, Florida, USA, 8 pages, 2003.
    S. Shlafman, A. Tal and S. Katz, “Metamorphosis of polyhedral surfaces using decomposition”, Computer Graphics Forum, Vol.21, No.3, pp.219–228, 2002.
    S. Katz and A. Tal, “Hierarchical mesh decomposition using fuzzy clustering and cuts”, ACM Transactions of Graphics, Vol.22, No.3, pp.954–961, 2003.
    J. Zhou, W.M. Wang, J. Zhang, et al., “3D shape segmentation using multiple random walkers”, Journal of Computational and Applied Mathematics, Vol.329, pp.353–363, 2018.
    M. Mortara, G. Patanè, M. Spagnuolo, et al., “Plumber: A method for a multi-scale decomposition of 3D shapes into tubular primitives and bodies”, Proc. of the 9th ACM Symposium on Solid Modeling and Applications, Genoa, Italy, pp.339–344, 2004.
    Z.P. Ji, L.G. Liu, Z.G. Chen, et al., “Easy mesh cutting”, Computer Graphics Forum, Vol.25, No.3, pp.283–291, 2006.
    Y.K. Lai, S.M. Hu, R.R. Martin, et al., “Rapid and effective segmentation of 3D models using random walks”, Computer Aided Geometric Design, Vol.26, No.6, pp.665–679, 2009.
    M.J. Milroy, C. Bradley and G.W. Vickers, “Segmentation of a wrap-around model using an active contour”, Computer-Aided Design, Vol.29, No.4 pp.299–320, 1997.
    Y. Lee and S. Lee, “Geometric snakes for triangular meshes”, Computer Graphics Forum, Vol.21, No.3, pp.229–238, 2002.
    Y. Lee, S. Lee, A. Shamir, et al., “Mesh scissoring with minima rule and part salience”, Computer Aided Geometric Design, Vol.22, No.5, pp.444–465,2005.
    J.Y. Zhang, C.L. Wu, J.F. Cai, et al., “Mesh snapping: Robust interactive mesh cutting using fast geodesic curvature flow”, Computer Graphics Forum, Vol.29, No.2, pp.517–526, 2010.
    K. Xu, V.G. Kim, Q.X. Huang, et al., “Data-driven shape analysis and processing”, Computer Graphics Forum, Vol.36, No.1, pp.101–132, 2017.
    M. Reuter, S. Biasotti, D. Giorgi, et al., “Discrete Laplace-Beltrami operators for shape analysis and segmentation”, Computers and Graphics, Vol.33, No.3, pp.381–390, 2009.
    D.D. Hoffman and M. Singh, “Salience of visual parts”, Cognition, Vol.63, No.1, pp.29–78, 1997.
    Y. Boykov, O. Veksler and R. Zabih, “Fast approximate energy minimization via graph cuts”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.23, No.11, pp.1222–1239, 2001.
    H. Ren and L. Yu, “Consistent mesh segmentation using protrusion function and graph cut”, Proc. of IEEE 2011 International Conference on Multimedia and Signal Processing, Guilin, China, pp.184–187, 2011.
    L. Shapira, A. Shamir and D. Cohen-Or, “Consistent mesh partitioning and skeletonisation using the shape diameter function”, The Visual Computer, Vol.24, No.4, pp.249–259, 2008.
    S. Katz, G. Leifman and A. Tal, “Mesh segmentation using feature point and core extraction”, The Visual Computer, Vol.21, No.8, pp.649–658, 2005.
    M. Fiedler, “A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory”, Czechoslovak Mathematical Journal, Vol.25, No.4, pp.619–633, 1975.
    U. Luxburg, “A tutorial on spectral clustering”, Statistics and Computing, Vol.17, No.4, pp.395–416, 2007.
    C. Koch and T. Poggio, “Predicting the visual world: Silence is golden”, Nature Neuroscience, Vol.2, No.1, pp.9–10, 1999.
    J.B. Shi and J. Malik, “Normalized cuts and image segmentation”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.22, No.8, pp.888–905, 2000.
    X.B. Chen, A. Golovinskiy and T. Funkhouser, “A benchmark for 3D mesh segmentation”, ACM Transactions on Graphics, Vol.28, No.3, Article No.73, 12 pages, 2009.
    H. Benhabiles, J. Vandeborre, G. Lavoué, et al., “A comparative study of existing metrics for 3D-mesh segmentation evaluation”, The Visual Computer, Vol.26, No.12, pp.1451–1466, 2010.
    M. Attene, B. Falcidieno and M. Spagnuolo, “Hierarchical mesh segmentation based on fitting primitives”, The Visual Computer, Vol.22, No.3, pp.181–193, 2006.
    A. Golovinskiy and T. Funkhouser, “Randomized cuts for 3D mesh analysis”, ACM Transactions on Graphics, Vol.27, No.5, Article No.145, 12 pages, 2008.
    E. Kalogerakis, A. Hertzmann and K. Singh, “Learning 3D mesh segmentation and labeling”, ACM Transactions on Graphics, Vol.29, No.4, Article No.102, 12 pages, 2010.
    K. Guo, D.Q. Zou and X.W. Chen, “3D mesh labeling via deep convolutional neural networks”, ACM Transactions on Graphics, Vol.35, No.1, Article No.3, 12 pages, 2015.
    R. Zabih, Y. Boykov, and O. Veksler, “System and method for fast approximate energy minimization via graph cuts”, Patent, 6744923, USA, 2004-6-1.
  • 加载中


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (24) PDF downloads(13) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint