AN OPTIMIZED ALGORITHM FOR COMPUTING THE VORONOI SKELETON
DOI:
https://doi.org/10.47839/ijc.19.4.1987Keywords:
Voronoi diagram, Voronoi graph, skeleton, polygon, shape simplification, heuristic, optimizationAbstract
The skeleton-based representation is widely used in such fields as computer graphics, computer vision and image processing. Therefore, efficient algorithms for computing planar skeletons are of high relevance. In this paper, we propose an optimized algorithm for computing the Voronoi skeleton of a planar object with holes, which is represented by a set of polygons. Such skeleton allows us to use efficiently the properties of the underlying Voronoi diagram data structure. It was shown that the complexity of the proposed Voronoi-based skeletonization algorithm is O(N log N), where N is the number of polygon’s vertices. We have also proposed theoretically justified optimization heuristic based on polygon/polyline simplification algorithms. In order to evaluate and prove the efficiency of the heuristic, a series of computational experiments were conducted involving the polygons obtained from MPEG 7 CE-Shape-1 dataset. We have measured the execution time of the skeletonization algorithm, computational overheads related to the introduced heuristics and also the influence of the heuristic onto accuracy of the resulting skeleton. As a result, we have established the criteria, which allow us to choose the optimal heuristics for our skeletonization algorithm depending on the system’s requirements.
References
P. K. Saha, G. Borgefors, G. S. Baja, “A survey on skeletonization algorithms and their applications,” Pattern Recognition Letters, vol. 76, pp. 3-12, 2016.
H. Sundar, D. Silver, N. Gagvani, S. Dickinson, “Skeleton based shape matching and retrieval,” 2003 Shape Modeling International, Seoul, South Korea, 2003, pp. 130-139.
J. Xie, P. Heng, M. Shah, “Shape matching and modeling using skeletal context,” Pattern Recognition, vol. 41, issue 5, pp. 1756-1767, 2008. doi:10.1016/j.patcog.2007.11.005.
A. Chaudhuri, K. Mandaviya, P. Badelia, S. Ghosh, Optical Character Recognition, Springer, Cham, 2017, 248 p.
R. S. Torres, A.X. Falcão, “Contour salience descriptors for effective image retrieval and analysis,” Image and Vision Computing, vol. 25, issue 1, pp. 3-13, 2007.
K. Rezaee, J. Haddadnia, A. Tashk, “Optimized clinical segmentation of retinal blood vessels by using combination of adaptive filtering, fuzzy entropy and skeletonization,” Applied Soft Computing, vol. 52, pp. 937-951, 2017. doi: 10.1016/j.asoc.2016.09.033.
W. Lasso, Y. Morales and C. Torres, “Image segmentation blood vessel of retinal using conventional filters, Gabor transform and skeletonization,” Proceedings of the 19th Symposium on Image, Signal Processing and Artificial Vision, Armenia, Colombia, September 17-19, 2014, pp. 1-4. doi: 10.1109/STSIVA.2014.7010170
Y. Al‐Kofahi, N. Dowell‐Mesfin, C. Pace, W. Shain, J. N. Turner, B. Roysam, “Improved detection of branching points in algorithms for automated neuron tracing from 3D confocal images”, Cytometry, vol. 73, pp. 36-43, 2008. doi: 10.1002/cyto.a.20499
C. Faulkner, J. Zhou, A. Evrard, G. Bourdais, D. MacLean, H. Häweker, P. Eckes, S. Robatzek, “An automated quantitative image analysis tool for the identification of microtubule patterns in plants,” Traffic, vol. 18, pp. 683–693, 2017. doi: 10.1111/tra.12505
M. Beil, H. Braxmeier, F. Fleischer, V. Schmidt, P. Walther, “Quantitative analysis of keratin filament networks in scanning electron microscopy images of cancer cells,” Journal of Microscopy, Vol. 220, pp. 84-95, 2005. doi: 10.1111/j.1365-2818.2005.01505.x
S. Changxian, M. Yulong, “Morphological thinning based on image's edges,” Proceedings of the 1998 International Conference on Communication Technology, Beijing, China, October 22-24, 1998, pp. 5-10. doi: 10.1109/ICCT.1998.743232
T. Y. Zhang, C. Y. Suen, “A fast parallel algorithm for thinning digital patterns,” Communications of the ACM, vol. 27, issue 3, pp. 236-239, 1984.
T. Q. Yan, C. X. Zhou, “A continuous skeletonization method based on distance transform,” in: D. S. Huang, P. Gupta, X. Zhang, P. Premaratne (Eds.), Emerging Intelligent Computing Technology and Applications. Communications in Computer and Information Science, Springer, Berlin, 2012, pp. 251-258. doi: 10.1007/s00371-018-1549-z
J. Chen, M. Du, X. Qin, “An improved topology extraction approach for vectorization of sketchy line drawings,” The Visual Computer, vol. 34, issue 12, pp. 1633–1644, 2018.
X. Hilaire, K. Tombre, “Robust and accurate vectorization of line drawings,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, issue 6, pp. 890-904, 2006. doi: 10.1109/TPAMI.2006.127
L. Acciai, P. Soda, G. Iannello, “Automated neuron tracing methods: An updated account,” Neuroinformatics, Vol. 14, Issue 4, pp. 353–367, 2016.
L. Cheng, J. De, X. Zhang, F. Lin, H. Li, K. H. Ong, W. Yu, Y. Yu, S. Ahmed, “A graph-theoretical approach for tracing filamentary structures in neuronal and retinal images,” IEEE Transactions on Medical Imaging, vol. 35, issue 1, pp. 257-272, 2016.
A. M. Stein, D. A. Vader, L. M. Jawerth, D. A. Weitz, L. M. Sander, “An algorithm for extracting the network geometry of three‐dimensional collagen gels,” Journal of Microscopy, vol. 232, pp. 463-475, 2008.
C. Maple, “Geometric design and space planning using the marching squares and marching cube algorithms,” Proceedings of the 2003 International Conference on Geometric Modeling and Graphics, London, UK, July 16-18, 2003, pp. 90–95.
O. Aichholzer, F. Aurenhammer, D. Alberts, B. Gärtner, “A novel type of skeleton for polygons,” Journal of Universal Computer Science, vol. 1, issue 12, pp. 752-761, 1995.
D. Eppstein, J. Erickson, “Raising roofs, crashing cycles, and playing pool: applications of a data structure for finding pairwise interactions,” Discrete & Computational Geometry, vol. 22, issue 4, pp. 569-592, 1999.
F. Chin, J. Snoeyink, C. A. Wang, “Finding the medial axis of a simple polygon in linear time,” Proceedings of the 6th Annual International Symposium on Algorithms and Computation, Cairns, Australia, December 4-6, 1995, pp. 382-391.
R. Ogniewicz, M. Ilg, “Voronoi skeletons: theory and applications,” Proceedings of the 1992 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Champaign, USA, 1992, pp. 63-69. doi: 10.1109/CVPR.1992.223226
G. Székely, “Voronoi skeletons,” in: K. Siddiqi, S. M. Pizer (Eds.), Medial Representations. Computational Imaging and Vision, Springer, Dordrecht, 2008, pp. 191-221.
F. P. Preparata, M. I. Shamos, Computational Geometry: An introduction, first ed., Springer, Berlin, Heidelberg, 1985, 390 p.
M. I. Shamos, D. Hoey, “Closest-point problems,” Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science, Berkley, USA, October 13-15, 1975, pp. 151-162.
S. Fortune, “A sweepline algorithm for Voronoi diagrams,” Algorithmica, vol. 2, pp.153-174, 1987. doi:10.1007/BF01840357
M. Berg, O. Cheong, M. Kreveld, M. Overmars, Computational Geometry: Algorithms and Applications, third ed., Springer, Berlin, 2008, 386 p. doi:10.1007/978-3-540-77974-2
A. Okabe, B. Boots, K. Sugihara, Spatial Tessellations, Concepts and Applications of Voronoi diagrams, second ed., John Wiley & Sons, New York, 2000, 696 p.
D. Douglas, T. Peucker, “Algorithms for the reduction of the number of points required to represent a digitized line or its caricature,” The Canadian Cartographer, vol. 10, issue 2, pp. 112–122, 1973.
M. Visvalingam, J. D. Whyatt, “Line generalisation by repeated elimination of points,” Cartographic Journal, Vol. 30, pp. 46-51, 1993.
K. Reumann, A. P. M. Witkam, Optimizing curve segmentation in computer graphics, in A. Gunther, B. Levrat, H. Lipps (Eds.), International Computing Symposium, American Elsevier, North Holland, 1973, pp. 467–472.
H. Opheim. “Fast data reduction of a digitized curve,” Geo-Processing, vol. 2, pp. 33-40, 1982.
T. Lang, “Rules for robot draughtsman,” Geographical Magazine, vol. 42, pp. 50-51, 1969.
Z. Zhao, A. Saalfeld, “Linear-time sleeve-fitting polyline simplification algorithms,” Proceedings of the Annual Convention and Exposition Technical Papers, Seattle, USA, April 7-10, 1997, pp. 214-223.
P. Raposo, “Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation,” Cartography and Geographic Information Science, vol. 40, issue 5, pp. 427-443, 2013.
Z. Li, S. Openshaw. “Linear Feature's Self-Adapted Generalization Algorithm Based on Impersonality Generalized Natural Law,” Translation of Wuhan Technical University of Surveying and Mapping, vol. 1, pp. 49-58, 1994.
J. Song, R. Miao, “A novel evaluation approach for line simplification algorithms towards vector map visualization,” International Journal of Geo-Information, vol. 5, issue 12, pp. 223-236, 2016.
A. A. Taha, A. Hanbury, “An efficient algorithm for calculating the exact Hausdorff distance,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37, issue 11, pp. 2153-2163, 2015.
A. Beristain, M. Graña, A. I. Gonzalez, “A pruning algorithm for stable voronoi skeletons,” Journal of Mathematical Imaging and Vision, vol. 42, pp. 225-237, 2012.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. 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 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.
