Open Access Open Access  Restricted Access Subscription or Fee Access

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

Fatima Rafii Zakani(1*), Khadija Arhid(2), Mohcine Bouksim(3), Mohamed Aboulfatah(4), Taoufiq Gadi(5)

(1) Laboratory of Informatics, Imaging and Modeling of Complex Systems (LIIMSC), Faculty of Sciences and Techniques, Hassan 1st University, Morocco
(2) Laboratory of Informatics, Imaging and Modeling of Complex Systems (LIIMSC), Faculty of Sciences and Techniques, Hassan 1st University, Morocco
(3) Laboratory of Informatics, Imaging and Modeling of Complex Systems (LIIMSC), Faculty of Sciences and Techniques, Hassan 1st University, Morocco
(4) Laboratory of Analysis of Systems and Treatment of Information (LASTI) Faculty of Sciences and Techniques, Hassan 1st University Settat, Morocco
(5) Laboratory of Informatics, Imaging and Modeling of Complex Systems (LIIMSC), Faculty of Sciences and Techniques, Hassan 1st University, Morocco
(*) Corresponding author


DOI: https://doi.org/10.15866/irecos.v11i12.10922

Abstract


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.

Keywords


Segmentation; 3D Models; Segmentation Evaluation; Levenshtein Distance

Full Text:

PDF


References


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.
http://dx.doi.org/10.1145/2693443

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..
http://dx.doi.org/10.1016/j.patrec.2015.04.006

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).
http://dx.doi.org/10.1109/smi.2006.24

A. Shamir, A survey on mesh segmentation techniques, (2008) Computer Graphics Forum, 27(6), pp. 1539–1556.
http://dx.doi.org/10.1111/j.1467-8659.2007.01103.x

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.
http://dx.doi.org/10.1016/j.cad.2004.09.001

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).
http://dx.doi.org/10.1109/icra.2015.7139875

L. Yi, H. Su, X. Guo, L. Guibas, SyncSpecCNN: Synchronized Spectral CNN for 3D Shape Segmentation, (2016) arXiv preprint arXiv:1612.00606.
http://dx.doi.org/10.1038/nature.2014.16643

I. Biederman, Recognition-by-components: a theory of human image understanding.,(1987) Psychological review, 94 (2), pp. 115–47.
http://dx.doi.org/10.1037/0033-295x.94.2.115

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,.
http://dx.doi.org/10.1016/j.jcp.2015.03.046

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.
http://dx.doi.org/10.15866/irecos.v9i9.3039

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.
http://dx.doi.org/10.15866/irecos.v9i11.4046

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.
http://dx.doi.org/10.15866/irecos.v10i12.8110

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.
http://dx.doi.org/10.1016/j.cviu.2014.12.008

X. Chen, A. Golovinskiy, T. Funkhouser, A benchmark for 3D mesh segmentation, (2009) ACM Transactions on Graphics, 28 (3), p. 1.
http://dx.doi.org/10.1145/1531326.1531379

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).
http://dx.doi.org/10.1109/smi.2009.5170161

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.
http://dx.doi.org/10.1007/s00371-010-0494-2

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).
http://dx.doi.org/10.1109/mmsp.2010.5662046

Z. Liu, S. Tang, S. Bu, H. Zhang, New evaluation metrics for mesh segmentation,(2013) Computers and Graphics (Pergamon), 37 (6), pp. 553–564.
http://dx.doi.org/10.1016/j.cag.2013.05.021

V. I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, (1966) Soviet Physics Doklady, 10 (8), pp. 707–710.
http://dx.doi.org/10.1109/isit.1994.394907

W. M. Rand, Objective Criteria for the Evaluation of Clustering Methods, (1971) Journal of the American Statistical Association, 66 (336) pp. 846–850.
http://dx.doi.org/10.2307/2284239

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).
http://dx.doi.org/10.1109/cist.2016.7805082

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).
http://dx.doi.org/10.1109/cist.2016.7805087

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).
http://dx.doi.org/10.1109/cist.2016.7805083

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.
http://dx.doi.org/10.1016/j.jcomdis.2015.09.004

A. Raskin, P. Rudakov, Using Levenshtein Distance for Typical User Actions and Search Engine Switching Detection, (2016) Springer International Publishing, pp. 158–168.
http://dx.doi.org/10.1007/978-3-319-41718-9_9

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).
http://dx.doi.org/10.1109/tenconspring.2016.7519368

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.
http://dx.doi.org/10.1007/978-3-642-15880-3_11

A. Golovinskiy T. Funkhouser, Randomized cuts for 3D mesh analysis, (2008) ACM Transactions on Graphics, 27 (5), p. 1.
http://dx.doi.org/10.1145/1409060.1409098

M. Attene, B. Falcidieno, M. Spagnuolo, Hierarchical mesh segmentation based on fitting primitives,(2006) The Visual Computer, 22 (3), pp. 181–193.
http://dx.doi.org/10.1007/s00371-006-0375-x

S. K. Shymon Shlafman, Ayellet Tal, Metamorphosis of Polyhedral Surfaces using Decomposition,(2002) Computer Graphics Forum, 21 (3), pp. 219–228.
http://dx.doi.org/10.1111/1467-8659.00581


Refbacks

  • There are currently no refbacks.



Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2022 Praise Worthy Prize