DOI: https://doi.org/10.15588/1607-3274-2019-1-10

### VORONOI-BASED SKELETONIZATION ALGORITHM FOR SEGMENTING THE NETWORK OF BIOLOGICAL NEURONS

#### Abstract

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.

#### Keywords

#### Full Text:

PDF (Українська)#### References

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-

-77974-2

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:

1109/ICCT.1998.743232

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.

DOI: 10.1111/j.1467-8659.2010.01814.x

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:

1016/j.patrec.2015.04.006

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.

DOI: 10.1007/978-3-642-15745-5_58

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-

-14-93

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:

1109/ISVD.2006.39

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-

(92)90030-7

Fortune S. A sweepline algorithm for Voronoi diagrams,

Algorithmica, 1987, Vol. 2, No. 1–4, pp. 153–174. DOI:

1007/BF01840357

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:

1016/S0377-0427(98)00211-8

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–

DOI: 10.1016/S0377-0427(98)00223-4

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-

-0

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.

DOI: 10.1145/311535.311567

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,

pp. 130–137.

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:

http://www.cellimagelibrary.org/home

#### 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»,

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.**