Automatic Spectral Method of Mesh Segmentation Based on Fiedler Residual

LI Lingfei; WU Tieru

doi:10.1049/cje.2020.11.001

Volume 30 Issue 3

May 2021

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2021 > 30(3): 426-436

LI Lingfei and WU Tieru, “Automatic Spectral Method of Mesh Segmentation Based on Fiedler Residual,” Chinese Journal of Electronics, vol. 30, no. 3, pp. 426-436, 2021, doi: 10.1049/cje.2020.11.001

Citation:

LI Lingfei and WU Tieru, “Automatic Spectral Method of Mesh Segmentation Based on Fiedler Residual,” Chinese Journal of Electronics, vol. 30, no. 3, pp. 426-436, 2021, doi: 10.1049/cje.2020.11.001

Citation:

PDF( 5325 KB)

Automatic Spectral Method of Mesh Segmentation Based on Fiedler Residual

doi: 10.1049/cje.2020.11.001

LI Lingfei^,,
WU Tieru

Institute of Mathematics, Jilin University, Changchun 130000, China

Funds:

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

Received Date: 2020-05-09

Abstract

Abstract

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.
- Mesh segmentation,
- Spectral analysis,
- Fiedler residual,
- Graph cut

FullText(HTML)

References(46)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views