VORONOI-BASED SKELETONIZATION ALGORITHM FOR SEGMENTING THE NETWORK OF BIOLOGICAL NEURONS
DOI:
https://doi.org/10.15588/1607-3274-2019-1-10Keywords:
microscopy, image processing, Voronoi diagram, Voronoi polygon, neurons, segmentation, graph.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.
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:
Downloads
How to Cite
Issue
Section
License
Copyright (c) 2019 D. V. Kotsur, V. M. Tereshchenko
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
