Open Access Open Access  Restricted Access Subscription or Fee Access

A New Evaluation Method for Mesh Segmentation Based on the Levenshtein Distance

(*) Corresponding author

Authors' affiliations



3D mesh segmentation is an important preprocessing in many 3D shape applications and it is considered as one of the most challenging tasks in 3D mesh analysis. Recently, interests have been developed in creating different approaches for 3D mesh segmentation and many solutions have been proposed in the literature. Hence, one of the most important issues is how to evaluate the proposed segmentation methods and judge the quality of segmentation results. In this paper, we present a new evaluation metric, based on the Levenshtein distance to perform an objective evaluation of 3D mesh segmentation methods. Most of the existing metrics judge the quality of an automatic segmentation with only one ground-truth, which is considered as a limit since we can have many semantic segmentations for the 3D meshes. Furthermore, they do not take into consideration the regularity of meshes. Therefore, the novel metric allows both comparison with multiple ground truth segmentations and has the ability to give a relevant evaluation for both regular and irregular 3D meshes. Several experiments have been done to show the performance and the potential of the proposed metric.
Copyright © 2016 Praise Worthy Prize - All rights reserved.


Segmentation; 3D Models; Segmentation Evaluation; Levenshtein Distance

Full Text:



A. Maglo, G. Lavoué, F. Dupont, and C. Hudelot, 3D Mesh Compression: Survey, Comparisons, and Emerging Trends, (2015) ACM Computing Surveys, 47 (3), pp. 1–41.

P. K. Saha and G. Sanniti di Baja, A survey on skeletonization algorithms and their applications, (2016) Pattern Recognition Letters 76 (1), pp 3-12..

Attene, M., Katz, S., Mortara, M., Patane, G., Spagnuolo, M., Tal, A., Mesh Segmentation - A Comparative Study, Proceedings of the IEEE International Conference on Shape Modeling and Applications (Page:7 Year of Publication: 2006).

A. Shamir, A survey on mesh segmentation techniques, (2008) Computer Graphics Forum, 27(6), pp. 1539–1556.

G. Lavoué, F. Dupont, and A. Baskurt, A new CAD mesh segmentation method, based on curvature tensor analysis, (2005) Computer-Aided Design, 37(10), pp. 975–987.

Wolf, D., Prankl, J., Vincze, M., Fast semantic segmentation of 3D point clouds using a dense CRF with learned parameters, Poceedings of the IEEE International Conference on Robotics and Automation (ICRA), (Page: 4867–4873 Year of Publication: 2015).

L. Yi, H. Su, X. Guo, L. Guibas, SyncSpecCNN: Synchronized Spectral CNN for 3D Shape Segmentation, (2016) arXiv preprint arXiv:1612.00606.

I. Biederman, Recognition-by-components: a theory of human image understanding.,(1987) Psychological review, 94 (2), pp. 115–47.

Y. Wang, N. Qin, N. Zhao, Delaunay graph and radial basis function for fast quality mesh deformation, Journal of Computational Physics, (2015) 294, pp. 149–172,.

G. Chandramohan S. K. Subramanian, An Efficient Hybrid Segmentation Algorithm for Computer Tomography Image Segmentation, (2014) International Review on Computers and Software (IRECOS), 9 (9), pp. 1576-1582.

M. Eapen, R. Korah, Integration of Improved Region Growing (iRG) and Level Set Method for Automated Medical Image Segmentation, (2014) International Review on Computers and Software (IRECOS), 9 (2), pp 278-284.

Kishore, P., Raghava Prasad, C., Shape Prior Active Contours for Computerized Vision Based Train Rolling Stock Parts Segmentation, (2015) International Review on Computers and Software (IRECOS), 10 (12), pp. 1233-1243.

P. Theologou, I. Pratikakis, T. Theoharis, A comprehensive overview of methodologies and performance evaluation frameworks in 3D mesh segmentation, (2015) Computer Vision and Image Understanding, 135, pp. 49–82.

X. Chen, A. Golovinskiy, T. Funkhouser, A benchmark for 3D mesh segmentation, (2009) ACM Transactions on Graphics, 28 (3), p. 1.

Benhabiles, H., Vandeborre, J.-P., Lavoue, G., Daoudi, M., A framework for the objective evaluation of segmentation algorithms using a ground-truth of human segmented 3D-models, Proceedings of the IEEE International Conference on Shape Modeling and Applications (Page. 36–43 Year of Publication: 2009).

H. Benhabiles, J.-P. Vandeborre, G. Lavoué, M. Daoudi, A comparative study of existing metrics for 3D-mesh segmentation evaluation, (2010) The Visual Computer, 26 (12), pp. 1451–1466.

Benhabiles, H., Lavoué, G., Vandeborre, J. P., Daoudi, M., A subjective experiment for 3D-mesh segmentation evaluation, Proceedings of the IEEE International Workshop on Multimedia Signal Processing, MMSP2010, (Page: 356–360 Year of Publication: 2010).

Z. Liu, S. Tang, S. Bu, H. Zhang, New evaluation metrics for mesh segmentation,(2013) Computers and Graphics (Pergamon), 37 (6), pp. 553–564.

V. I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, (1966) Soviet Physics Doklady, 10 (8), pp. 707–710.

W. M. Rand, Objective Criteria for the Evaluation of Clustering Methods, (1971) Journal of the American Statistical Association, 66 (336) pp. 846–850.

Arhid, K., Bouksim, M., Zakani, F. R., Aboulfatah, M., Gadi, T., New evaluation method using sampling theory to evaluate 3D segmentation algorithms, Proceedings of the 4th IEEE International Colloquium on Information Science and Technology (Page: 410–415 Year of Publication:2016).

Bouksim, M., Zakani, F. R., Arhid, K., Aboulfatah, M., Gadi, T., New evaluation method for 3D mesh segmentation, Proceedings of the 4th IEEE International Colloquium on Information Science and Technology (Page: 438-443 Year of Publication: 2016).

Zakani, F. R., Arhid, K., Bouksim, M., Aboulfatah, M., Gadi ,T., New measure for objective evaluation of mesh segmentation algorithms, Proceedings of the 4th IEEE International Colloquium on Information Science and Technology (Page: 416-421 Year of Publication: 2016).

J. Faes, J. Gillis, S. Gillis, Phonemic accuracy development in children with cochlear implants up to five years of age by using Levenshtein distance, (2016) Journal of Communication Disorders, 59, pp. 40–58.

A. Raskin, P. Rudakov, Using Levenshtein Distance for Typical User Actions and Search Engine Switching Detection, (2016) Springer International Publishing, pp. 158–168.

Kumar, B. T. H., Vibha, L., Venugopal, K. R., Web page access prediction using hierarchical clustering based on modified levenshtein distance and higher order Markov model, Proceedings of the IEEE Region 10 Symposium (TENSYMP), (Page: 1–6 Year of Publication: 2016).

C. Barat, C. Ducottet, E. Fromont, Weighted symbols-based edit distance for string-structured image classification (2010), Machine Learning and Knowledge Discovery in Databases, 6321, pp. 72–86.

A. Golovinskiy T. Funkhouser, Randomized cuts for 3D mesh analysis, (2008) ACM Transactions on Graphics, 27 (5), p. 1.

M. Attene, B. Falcidieno, M. Spagnuolo, Hierarchical mesh segmentation based on fitting primitives,(2006) The Visual Computer, 22 (3), pp. 181–193.

S. K. Shymon Shlafman, Ayellet Tal, Metamorphosis of Polyhedral Surfaces using Decomposition,(2002) Computer Graphics Forum, 21 (3), pp. 219–228.


  • There are currently no refbacks.

Please send any question about this web site to
Copyright © 2005-2022 Praise Worthy Prize