Development of a metric and the methods for quantitative estimation of the segmentation of biomedical images

Authors

DOI:

https://doi.org/10.15587/1729-4061.2017.119493

Keywords:

метрика Фреше, метрика Хаусдорфа, не выпуклые области, биомедицинские изображения, погрешности сегментации

Abstract

We analyzed modern digital microscopy. In order to categorize digital microscopy, the following criteria are introduced: level of automation, software level, the level of application of network technologies. To quantitatively estimate the quality of image segmentation, we devised the technique based on a metric approach using the Fréchet and Hausdorff metrics. Modern algorithms for calculating the Hausdorff and Fréchet distances were analyzed.

We have introduced the Fréchet distance between trees. It was proven that the Fréchet distance between trees is a metric. We devised a method for estimating a distance between trees of the non-convex regions, based on finding skeletons of regions and determining the distance between them. The algorithm for finding the Hausdorff distance between the non-convex regions is described. We constructed the algorithm for finding a distance between the non-convex regions based on the Fréchet metric between trees.

The developed algorithms are included into a hybrid intelligent system for automated microscopy, which is designed to process histological and cytological images.

The algorithms were tested using the results of segmentation of histologic and cytologic images from a database as an example

Supporting Agency

  • Дана робота виконана в рамках держбюджетної теми «Гібридна інтелектуальна інформаційна технологія діагностування передракових станів молочної залози на основі аналізу зображень». Реєстраційний номер 1016U002500.

Author Biographies

Oleh Berezsky, Ternopil National Economic University Lvivska str., 11, Ternopil, Ukraine, 46020

Doctor of Technical Sciences, Professor, Head of Department

Department of Computer Engineering

Mykhailo Zarichnyi, Ivan Franko National University of Lviv Universytetska str., 1, Lviv, Ukraine, 79000

Doctor of Physical and Mathematical Sciences, Professor

Department of Geometry and Topology

Oleh Pitsun, Ternopil National Economic University Lvivska str., 11, Ternopil, Ukraine, 46020

Postgraduate student

Department of Computer Engineering

References

  1. Medoviy, V. S. (2009). Robotizirovannaya mikroskopiya vnedryaet standarty kachestva laboratornyh analizov. Standartizatsiya, 3, 33–37.
  2. Medoviy, V. S., Sokolinskiy, B. Z., Markellov, V. V., Fedorova, D. S., Fedorov, I. V. (2011). Razrabotka i ispytanie avtomatizirovannogo kompleksa mikroskopii. Opticheskiy zhurnal, 78 (1), 66–73.
  3. Medoviy, V. S., Pyatnitskiy, A. M., Sokolinskiy ,B. Z. et. al. (2012). Sovremenniy vozmozhnosti robotizirovannoy mikroskopii v avtomatizatsii analizov i laboratornoy telemeditsine (analiticheskiy obzor). Klinicheskaya laboratornaya diagnostika, 10, 32–43.
  4. Life Science Source. Available at: https://www.biovision.com
  5. Tsenovoy list. Programmno-apparatnyy kompleks dlya mikroskopii. OOO «Nauchno-proizvodistvennaya kompaniya «Zenit». Available at: http://www.zenit-npk.ru/fprice/info/11
  6. Skaniruyushchie mikroskopy-analizatory MEKOS-TS2. Skaniruyushchie mikroskopy-analizatory. Available at: http://msk.all-gorod.ru/product/4863699-skaniruyuschie-mikroskopy-analizatory-mekos-c2
  7. Szeliski, R. (2010). Computer Vision: Algorithms and Applications. Springer, 812. doi: 10.1007/978-1-84882-935-0
  8. Blum, H. A. Dunn, W. W. (1967). Transformation for extracting new descriptors of shape. Models for the Perception of Speech and Visual Form, 5, 362–380.
  9. Koltsov, P. P., Osipov, A. S., Kutsaev, A. S., Kravchenko, A. A., Kotovich, N. V., Zaharov, A. V. (2015). On the formation of structures in nonequilibrium media in the resonant three-wave interaction. Computer Optics, 39 (4), 542–556. doi: 10.18287/0134-2452-2015-39-4-542-556
  10. Berezskiy, O. N., Berezskaya, E. N. (2015). Kolichestvennaya otsenka kachestva segmentatsii izobrazheniy na osnove metric. Upravlyayushchie sistemy i mashiny, 6, 59–65.
  11. Lopez, M. A., Reisner, S. (2005). Hausdorff approximation of convex polygons. Computational Geometry, 32 (2), 139–158. doi: 10.1016/j.comgeo.2005.02.002
  12. Alt, H., Scharf, L. (2008). Computing the hausdorff distance between curved objects. International Journal of Computational Geometry & Applications, 18 (04), 307–320. doi: 10.1142/s0218195908002647
  13. Chew, L. P., Kedem, K. (1998). Getting around a lower bound for the minimum Hausdorff distance. Computational Geometry, 10 (3), 197–202. doi: 10.1016/s0925-7721(97)00032-1
  14. Knauer, C., Scherfenberg, M. (2011). Approximate nearest neighbor search under translation invariant hausdorff distance. International Journal of Computational Geometry & Applications, 21 (03), 369–381. doi: 10.1142/s0218195911003706
  15. Alvarez, V., Seidel, R. (2010). Approximating the minimum weight spanning tree of a set of points in the Hausdorff metric. Computational Geometry, 43 (2), 94–98. doi: 10.1016/j.comgeo.2009.04.005
  16. Mosig, A., Clausen, M. (2005). Approximately matching polygonal curves with respect to the Fréchet distance. Computational Geometry, 30 (2), 113–127. doi: 10.1016/j.comgeo.2004.05.004
  17. Buchin, K., Buchin, M., Wenk, C. (2008). Computing the Fréchet distance between simple polygons. Computational Geometry, 41 (1-2), 2–20. doi: 10.1016/j.comgeo.2007.08.003
  18. Rote, G. (2007). Computing the Fréchet distance between piecewise smooth curves. Computational Geometry, 37 (3), 162–174. doi: 10.1016/j.comgeo.2005.01.004
  19. Schlesinger, M. I., Vodolazskiy, E. V., Yakovenko, V. M. (2016). Fréchet Similarity of Closed Polygonal Curves. International Journal of Computational Geometry & Applications, 26 (01), 53–66. doi: 10.1142/s0218195916500035
  20. Ahn, H.-K., Knauer, C., Scherfenberg, M., Schlipf, L., Vigneron, A. (2012). Computing the discrete fréchet distance with imprecise input. International Journal of Computational Geometry & Applications, 22 (01), 27–44. doi: 10.1142/s0218195912600023
  21. Cook, A. F., Driemel, A., Sherette, J., Wenk, C. (2015). Computing the Fréchet distance between folded polygons. Computational Geometry, 50, 1–16. doi: 10.1016/j.comgeo.2015.08.002
  22. Gudmundsson, J., Smid, M. (2015). Fast algorithms for approximate Fréchet matching queries in geometric trees. Computational Geometry, 48 (6), 479–494. doi: 10.1016/j.comgeo.2015.02.003
  23. Alt, H., Godau, M. (1995). Computing the fréchet distance between two polygonal curves. International Journal of Computational Geometry & Applications, 05 (01n02), 75–91. doi: 10.1142/s0218195995000064
  24. Chambers, E. W., Colin de Verdière, É., Erickson, J., Lazard, S., Lazarus, F., Thite, S. (2010). Homotopic Fréchet distance between curves or, walking your dog in the woods in polynomial time. Computational Geometry, 43 (3), 295–311. doi: 10.1016/j.comgeo.2009.02.008
  25. Berezsky, O. (2016). Frechet Metric for Trees. 2016 IEEE First International Conference on Data Stream Mining & Processing (DSMP). Lviv, 213–217. doi: 10.1109/dsmp.2016.7583543
  26. Berezsky, O., Pitsun, O. (2017). Computation of the minimum distance between non-convex polygons for segmentation quality evaluation. 2017 12th International Scientific and Technical Conference on Computer Sciences and Information Technologies (CSIT). Lviv, 183–186. doi: 10.1109/stc-csit.2017.8098764
  27. Atallah, M. J., Ribeiro, C. C., Lifschitz, S. (1990). Computing Some Distance Functions Between Polygons. Computer Science Technical Reports, 9.
  28. Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to Algorithms. MIT Press, 1312.
  29. Berezky, O. M., Pitsun, O. Yo., Verbovyi, S. O., Datsko, T. V. (2017). Relational database of intelligent automated microscopy system. Scientific Bulletin of UNFU, 27 (5), 125–129. doi: 10.15421/40270525

Downloads

Published

2017-12-25

How to Cite

Berezsky, O., Zarichnyi, M., & Pitsun, O. (2017). Development of a metric and the methods for quantitative estimation of the segmentation of biomedical images. Eastern-European Journal of Enterprise Technologies, 6(4 (90), 4–11. https://doi.org/10.15587/1729-4061.2017.119493

Issue

Vol. 6 No. 4 (90) (2017): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2017 Oleh Berezsky, Mykhailo Zarichnyi, Oleh Pitsun

Creative Commons License

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

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.