VORONOI-BASED SKELETONIZATION ALGORITHM FOR SEGMENTING THE NETWORK OF BIOLOGICAL NEURONS
Context. The problem of automated processing and analysis of microscopy image data is of high relevance due to its extreme impact on the research and recent developments in the field of biology and medicine. Efficient image processing algorithms facilitate the development of new medical diagnostic tools and therapy processes. They help us to broaden our knowledge of underlying
mechanisms and processes inside living organisms. The primal focus of this paper is the processing of the microscopy images of the biological neural network. This aims to facilitate further studies of biological neural network that would lead to the development of better methods for diagnosis, prevention and cure of the related deceases.
Objective. The goal of the work is to development of an efficient image processing algorithm for segmenting the network of biological neurons based on the fluorescent microscopy image data.
Method. The introduced algorithm for segmenting the network of biological neurons comprises several steps. Firstly, we apply image processing routines, which aim to enhance the quality of the image data and extract the contours of the biological neural network. Then we construct the skeleton of the network applying the Voronoi diagram for line segments extracted from the object’s contours. We employ Voronoi skeleton to identify the cellular somas and differentiate them from axons and dendrites.
Results. The developed Voronoi-based algorithm allows us to segment individual neurons, localize their somas, axons and dendrites and extract graph representation of the neural network. The underlying Voronoi diagram data structure allows us to compute such graph efficiently in O(N log N) operations (where N is a number of contour points). The proposed segmentation method was
implemented in the C++/Python programming language and evaluated on the fluorescent images from CellImageLibrary (CIL).
Conclusions. The proposed segmentation method aims to facilitate studies of biological neural networks. It computes segmentation of the network of biological neurons in O(N log N) operations using the Voronoi diagram data structure. This data structure, in turn, gives us an attributed graph representation of the segmented network. Therefore, classical graph processing algorithms can be
applied to analyze the neural and compute such network’s characteristics as the number of connections between individual neurons, the shortest signal transduction path between two neurons, etc.
Full Text:PDF (Українська)
Mai J., Paxinos G. The Human nervous system, Third Edition.
London, Academic Press, 2012, 1428 p.
Cormen T. H., Leiserson C. E., Rivest R. L. , Stein C. Introduction
to Algorithms, Third Edition. Cambridge, The MIT
Press, 2009, 1312 p.
Berg M., Cheong O., Kreveld M., Overmars M. Computational
Geometry: Algorithms and Applications, Third Edition.
Berlin, Springer, 2008, 386 p. DOI: 10.1007/978-3-
Changxian S., Yulong M. Morphological thinning based on
image’s edges, Communication Technology: International
Conference, 22–24 October 1998 : proceedings. Beijing,
IEEE, 1998, Vol. 1, pp. 1–5. DOI:
Zhang T. Y., Suen C. Y. A fast parallel algorithm for thinning
digital patterns, Communications of the ACM, 1984,
Vol. 27, Issue 3, pp. 236–239. DOI: 10.1145/357994.358023
Liu L., Chambers E. W., Letscher D. et al. A simple and
robust thinning algorithm on cell complexes, Computer
Graphics Forum, 2010, Vol. 29, Issue 7, pp. 2253–2260.
Saha P. K., Borgefors G., Baja G. S. A survey on skeletonization
algorithms and their applications, Pattern recognition
letters, 2016, Vol. 76, Issue C, pp. 3–12. DOI:
Stein A. M., Vader D. A., Jawerth L. M. et al. An algorithm
for extracting the network geometry of three-dimensional
collagen gels, Journal of Microscopy, 2008, Vol. 232, Issue
, pp. 463–475. DOI: 10.1111/j.1365-2818.2008.02141.x.
Zhou Z., Sorensen S. A., Peng H. Neuron crawler: An automatic
tracing algorithm for very large neuron images, IEEE
th International Symposium on Biomedical Imaging
(ISBI), 2015, 1, pp. 870–874.
Xie J., Zhao T., Lee T. et al. Automatic neuron tracing in
volumetric microscopy images with anisotropic path searching,
Medical Image Computing and Computer-Assisted Intervention:
International Conference, 20–24 September
: proceedings. Beijing, Springer, 2010, pp. 472–479.
Acciai L., Soda P., Iannello G. Automated Neuron Tracing
Methods: An Updated Account, Neuroinformatics, 2016,
Vol. 14, № 4, pp. 353-367. DOI: 10.1007/s12021-016-9310-
Yang. J., Gonzalez-Bellido P. T., Peng H. A distance-field
based automatic neuron tracing method, BMC Bioinformatics,
, Vol. 14, No. 93. P. 93-104. DOI: 10.1186/1471-
Gonzales R. C., Woods R. E. Digital image processing,
Third Edition. Missouri, Pearson Education, 2007, 976 p.
Okabe A., Boots BSugihara., K., Chiu S., Kendall D. G.
Spatial Tessellations: Concepts and Applications of Voronoi
Diagrams. London, J. Wiley & Sons, 2000, 696 p.
Ogniewicz R., Ilg M. Voronoi skeletons: theory and applications,
Proceeding of IEEE Computer Society Conference on
Computer Vision and Pattern Recognition, 1992, 1, pp. 63–
Sharma O., Mioc D., Anton F. Voronoi diagram based automated
skeleton extraction from colour scanned maps, 3rd
International Symposium on Voronoi Diagrams in Science
and Engineering : International Conference, 2–5 July 2006:
proceedings. Banff, IEEE, 2006, Vol. 1, pp. 186–195. DOI:
Brandt J. W., Algazi V. R. Continuous skeleton computation
by Voronoi diagram, CVGIP: Image Understanding, 1992,
Vol. 3, Issue 55, pp. 329–338. DOI: 10.1016/1049-
Fortune S. A sweepline algorithm for Voronoi diagrams,
Algorithmica, 1987, Vol. 2, No. 1–4, pp. 153–174. DOI:
Shamos M., Hoey D. Closest-point problems, Proceedings
of 16th Annual Symposium on Foundations of Computer Science,
, 1, pp. 131–162. DOI: 10.1109/SFCS.1975.8
Ramamurthy R., Farouki R. T. Voronoi diagram and medial
axis algorithm for planar domains with curved boundaries I.
Theoretical foundations, Journal of Computational and Applied
Mathematics, 1999, Vol. 102, №1, pp. 119–141. DOI:
Ramamurthy R., Farouki R. T. Voronoi diagram and medial
axis algorithm for planar domains with curved boundaries –
II: Detailed algorithm description, Journal of Computational
and Applied Mathematics, 1999, Vol. 102, No. 2, pp. 253–
Farouki R. T., Ramamurthy R. Specified–Precision Computation
of Curve/Curve Bisectors, International Journal of
Computational Geometry & Applications, 1998, Vol. 8, No.
–6, pp. 599–617. DOI: 10.1142/S0218195998000291
Alt H., Cheong O., Vigneron A. The Voronoi Diagram of
Curved Objects, Discrete & Computational Geometry, 2005,
Vol 34, No. 3, pp. 439–453. DOI: 10.1007/s00454-005-
Hoff K., Culver T., Keyser J. et al. Fast Computation of
Generalized Voronoi Diagrams Using Graphics Hardware,
Proceedings of 26th Annual Conference on Computer
Graphics and Interactive Techniques, 1999, 1, pp. 277–286.
Har-Peled S. Geometric Approximation Algorithms, Mathematical
Surveys and Monographs, 2011. 1, pp. 129–132.
Ho Y., Liu J. Collision-free curvature-bounded smooth path
planning using composite Bezier curve based on Voronoi
diagram, Proceedings of IEEE International Symposium on
Computational Intelligence in Robotics and Automation,
, 1, pp. 463–468. DOI: 10.1109/CIRA.2009.5423161
[Kwak H. J., Lee S. J., Lee Y. et al. Quantitative study of
total variation (TV) noise reduction algorithm with chest XRay
imaging, Journal of Instrumentation, 2018, 1, pp. 1–14.
Frangi A. F., Niessen W. J., Vincken K. L. et al. Multiscale
vessel enhancement filtering, Proceeding of Medical Image
Computing and Computer-Assisted Intervention, 1998, 1,
Schneider P. An Algorithm for Automatically Fitting Digitized
Curves, Graphics Gems. San Diego, Academic Press
Professional, 1990, Section 11, pp. 612–626.
Pagani L., Scott P. J. Curvature based sampling of curves
and surfaces, Computer Aided Geometric Design, 2018,
Vol. 59, pp. 32–48.
Preparata F., Shamos M. Computational Geometry: An Introduction.
Berlin, Springer, 1985, 390 p.
Cell Image Library [Electronic resource]. Access mode:
GOST Style Citations
Copyright (c) 2019 D. V. Kotsur, V. M. Tereshchenko
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»,
National University "Zaporizhzhia Polytechnic",
Zhukovskogo street, 64, Zaporizhzhia, 69063, Ukraine.
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
The reference to the journal is obligatory in the cases of complete or partial use of its materials.