EVALUATION METHODS OF IMAGE SEGMENTATION QUALITY
DOI:
https://doi.org/10.15588/1607-3274-2018-1-14Keywords:
segmentation, quantitative segmentation evaluation, Fr chet metric, Hausdorff metric, Gromov-Hausdorff metric, Gromov- Fr chet metric, polygon, cytological images.Abstract
Context. The basic methods of quantitative evaluation of image segmentation quality are explored. They are used to select segmentation algorithms for specific image classes. The object of the study is cytological and histological images that are used in diagnosing the pathological processes in oncology. The subject of the study is quantitative methods for segmentation algorithms’ quality evaluation.Objective. The purpose of the work is to introduce the Gromov-Fr chet metric and develop a metric-based method for quantitative
evaluation of segmentation quality for image segmentation algorithms’ comparison.
Method. The quantitative evaluation criteria, which are based on comparison with etalon image and without the comparison with etalon
image, are analyzed. The algorithms for measuring the distances between images based on the Fr chet, Hausdorff, and Gromov-Hausdorff metrics are analyzed.
To calculate the distance between the contours of images, the Gromov-Fr chet distance was introduced. The condition of identity,
symmetry and triangle is proved, and it is shown that the Gromov-Fr chet distance is a metric. The metric-based method of quantitative evaluation of segmentation quality is developed. It is based on the use of the Gromov-Hausdorff and Gromov-Fr chet metrics. The method is based on the algorithms for non-convex-into-convex polygon transformation, weighted chord algorithm, and algorithms for calculating the Fr chet and Hausdorff distances. To calculate the Hausdorff distance between convex regions, the Atalah’s algorithm was used. The Thierry and Manillo algorithm was used to find the discrete Fr chet distance. These algorithms have the lowest computational complexity among their class of algorithms.
Results. The Gromov-Fr chet metric was introduced and the metric-based method of quantitative evaluation of segmentation quality was
developed.
Conclusions. The conducted experiments on the basis of cytological images confirmed the performance of software for evaluation the
distances between images. The developed method showed a high accuracy of estimation the distances between images. The developed software module was used in intelligence systems for diagnosing the breast precancerous and cancerous conditions. The software can be used in various software systems of computer vision. Promising areas for further research are search for new metrics to evaluate the distances between images
References
Yinpeng J. Contrast Enhancement by Multi-scale Adaptive
Histogram Equalization / J. Yinpeng, L.Fayadb, A. Laine //
Proceedings of SPIE. – 2001. – Vol. 4478. – P. 206–213.
DOI: 10.7916/D8QZ2M29
Baron T. H. A Prospective Comparison of Digital Image Analysis and Routine Cytology for the Identification of Malignancy in Biliary Tract Strictures / T. H. Baron, G. Harewood, A. Rumalla // Clinical Gastroenterology and Hepatology. – 2004. – Vol. 2, Issue 3. – P. 214-219. DOI: 10.1016/S1542-3565(04)00006-0
Petushi S. Large-scale computations on histology images reveal grade-differentiating parameters for breast cancer / S. Petushi, F. U. Garcia, M. M. Haber // BMC Medical Imaging. – 2006. – Vol. 6, Issue 14. – P. 496–499. DOI: 10.1186/1471-2342-6-14
Levine M. D. Dynamic measurement of computer generated
image segmentations / M. D. Levine, A. Nazif // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 1985. – Vol. 7, Issue 2. – P. 155–164. DOI: 10.1109/TPAMI.1985.4767640
Zhang Y. J. A review of recent evaluation methods for image
segmentation / Y. J. Zhang // Signal Processing and its Applications (ISSPA) : Sixth International Symposium, Kuala Lumpur Malaysia, Aug 13–16, 2001 : proceedings. – Kuala Lumpur, 2001. – P. 148–151.
Berezsky O. Methods of quantitative evaluation of image
segmentation quality / O. Berezsky // Signal/Image Processing and Pattern Recognition (UkrOBRAZ’2014) : XIIIth All-Ukraine International Conference, Kyiv, 3–7 November 2014 : proceedings. – Kyiv, 2014. – P. 51–54.
Lee S. U. A comparative performance study of several global thresholding techniques for segmentation / S. U. Lee, S. Y. Chung, R. H. Park // Computer Vision, Graphics, and Image Processing. – 1990. – Vol. 52, Issue. 2. – P. 171–190.
Zhang Y. J. Segmentation evaluation using ultimate measurement accuracy / Y. J. Zhang, J. J. Gerbrands // Image Processing Algorithms and Technique. – 1992. – Vol. 1657. – P. 449-460.
Zhang Y. J. Objective and quantitative segmentation evaluation and comparison / Y. J. Zhang, J. J. Gerbrands // Signal Processing. – 1994. – Vol. 39, Issue.2. – P. 43-54. DOI:10.1016/0165-1684(94)90122-8
Lopez M. Hausdorff approximation of convex polygons /
M. A. Lopez, S. Reisner // Computational Geometry. – 2005. –
Vol. 32, Issue 2. – P. 139–158. DOI: 10.1016/
j.comgeo.2005.02.002
Alt H. Computing the Hausdorff distance between curved objects / H. Alt, L. Scharfz // International Journal of Computational Geometry. – 2008. – Vol. 18. – P. 307–320. DOI: 10.1142/S0218195908002647
Chew L. P. Getting around a lower bound for the minimum
Hausdorff distance / L. P. Chew, K. Kedem // Computational
Geometry. – 1998. – Vol. 10, Issue 3. – P. 197–202. DOI: S0925-7721(97)00032-1
Knauer C. Approximate nearest neighbor search under translation invariant hausdorff distance / C. Knauer, M. Scherfenberg //International Journal of Computational Geometry. – 2011. – Vol. 21, Issue 3. – P. 369–381. DOI: S0218195911003706
Alvarez V. Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric / V. Alvarez, R. Seidel // Computational Geometry. – 2010. – Vol. 43. – P. 94–98.
Atallah M. J. Computing Some Distance Functions Between
Polygons / M. J. Atallah, C. Celso // Computer Science Technical Reports. – 1990. – Vol. 9. – P. 1–10.
Alt H. Computing the Fr chet distance between two polygonal curves / H. Alt, M. Godau // International Journal of Computational Geometry and Applications. – 1995. – Vol. 5. – P. 75–91.
Mosig A. Approximately matching polygonal curves with respect to the Fr chet distance / A. Mosig, M. Clausen // Computational Geometry. – 2005. – Vol. 30, Issue 2. – P. 113–127. DOI: 10.1016/j.comgeo.2004.05.004
Buchin K. Computing the Fr chet distance between simple
polygons / K. Buchin, M. Buchin, C. Wenk // Computational
Geometry. – 2008. – Vol. 441, Issue 1–2. – P. 2–20. DOI: 10.1145/1137856.1137870
Rote G. Computing the Fr chet distance between piecewise
smooth curves / G. Rote // Computational Geometry. – 2007. –Vol. 37. – P. 162–174. DOI: 10.1016/j.comgeo.2005.01.004
Schlesinger M. I. Frechet Similarity of Closed Polygonal Curves / M. I. Schlesinger, E. V. Vodolazskiy, V. M. Yakovenko // International Journal of Computational Geometry. – 2016. – Vol. 26. – P. 53–66. DOI: 10.1142/S0218195916500035
Computing the discrete Fr chet distance with imprecise impute / [H.-K. Ahn, C. Knauer, M. Scherfenberg et al.] // International Journal of Computational Geometry. – 2016. – Vol. 22. – P. 27–44. DOI: 10.1142/S0218195912600023
Computing the Fr chet distance between folded polygons /
[A. F. Cook, Anne Driemel, Jessica Sherette et al.] //
Computational Geometry. – 2015. – Vol. 50. – P. 1–16.
Gudmundsson J. Fast algorithms for approximate Fr chet matching queries in geometric trees / J. Gudmundsson, M. Smid //Computational Geometry. – 2015. – Vol. 48. – P. 479–494.DOI:10.1016/j.comgeo.2015.02.003
Computing discrete Fr chet distance: Technical Report: CD-TR94/64 / T. Eiter, H. Mannila // Information Systems Department, Technical University of Vienna. – Vienna, 1994. – 7 p.
Deza M. M. Encyclopedia of Distances / M. M. Deza. – Berlin : Springer-Verlag, 2009. – 590 p.
Gromov M. Metric Structures for Riemannian and Non-
Riemannian Spaces / M. Gromov. – Boston, MA, Progress in
Mathematics, 1999. – 1041 p.
Regions Matching Algorithms Analysis to Quantify the Image Segmentation Results / [O. Berezsky, Y. Batko, O. Pitsun et al.] // Sensors & Transducers. – 2017. – Vol. 208, Issue 1. – P. 44–49. DOI: 10.1109/STC-CSIT.2016.7589862
Fuzzy system diagnosing of precancerous and cancerous conditions of the breast / [O. Berezsky, S. Verbovyy, L. Dubchak et al.] // Computer Sciences and Information Technologies (CSIT) : XI th International Scientific and Technical Conference, Lviv, 6–10 September 2016 : proceedings. – Lviv, 2016. – P. 200–203. DOI:10.1109/STC-CSIT.2016.7589906
Berezsky O. Automated Processing of Cytological and Histological Images / Oleh Berezsky, Oleh Pitsun // Perspective Technologies and Methods in MEMS Design (MEMSTECH’2016) : XII th International Conference, Lviv-Polyana, 20–24 April 2016 : proceedings. – Lviv, 2016. – P. 51–53. DOI:10.1109/MEMSTECH.2016.7507518
Downloads
How to Cite
Issue
Section
License
Copyright (c) 2018 O. M. Berezsky, O. Y. Pitsun
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
