EVALUATION METHODS OF IMAGE SEGMENTATION QUALITY
Abstract
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
Full Text:
PDF (Українська)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
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
DOI: https://doi.org/10.15588/1607-3274-2018-1-14
Copyright (c) 2018 O. M. Berezsky, O. Y. Pitsun
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.