DOI: https://doi.org/10.15588/1607-3274-2018-1-14

EVALUATION METHODS OF IMAGE SEGMENTATION QUALITY

O. M. Berezsky, O. Y. Pitsun

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

Keywords


segmentation; quantitative segmentation evaluation; Fr chet metric; Hausdorff metric; Gromov-Hausdorff metric; Gromov- Fr chet metric; polygon; cytological 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


GOST Style Citations


1. 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
2. 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
3. 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
4. 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
5. 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.
6. 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.
7. 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.
8. 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.
9. 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
10. 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
11. 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
12. 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
13. 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
14. 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.
15. Atallah M. J. Computing Some Distance Functions Between
Polygons / M. J. Atallah, C. Celso // Computer Science Technical Reports. – 1990. – Vol. 9. – P. 1–10.
16. 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.
17. 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
18. 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
19. 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
20. 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
21. 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
22. 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.
23. 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
24. 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.
25. Deza M. M. Encyclopedia of Distances / M. M. Deza. – Berlin : Springer-Verlag, 2009. – 590 p.
26. Gromov M. Metric Structures for Riemannian and Non-
Riemannian Spaces / M. Gromov. – Boston, MA, Progress in
Mathematics, 1999. – 1041 p.
27. 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
28. 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
29.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.7






Copyright (c) 2018 O. M. Berezsky, O. Y. Pitsun

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
Zaporizhzhya National Technical University, 
Zhukovskiy street, 64, Zaporizhzhya, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.