Optimization heuristics for computing the voronoi skeleton

Autoren Dmytro Kotsur
Vasyl Tereshchenko
Editoren J. Rodrigues
et al.
Titel Optimization heuristics for computing the voronoi skeleton
Buchtitel Computational Science – Proc. ICCS 2019, Part I
Typ in Konferenzband
Verlag Springer
Serie Lecture Notes in Computer Science
Band 11536
ISBN 978-3-030-22733-3
DOI 10.1007/978-3-030-22734-0_8
Monat June
Jahr 2019
Seiten 96-111
SCCH ID# 19023

A skeletal representation of geometrical objects is widely used in computer graphics, computer vision, image processing, and pattern recognition. Therefore, efficient algorithms for computing planar skeletons are of high relevance. In this paper, we focus on the algorithm for computing the Voronoi skeleton of a planar object represented by a set of polygons. The complexity of the considered algorithm is O(N log N), where N is the total number of polygon’s vertices. In order to improve the performance of the skeletonization algorithm, we proposed theoretically justified shape optimization heuristics, which are based on polygon simplification algorithms. We evaluated the efficiency of such heuristics using polygons extracted from MPEG 7 CE-Shape-1 dataset and measured the execution time of the skeletonization algorithm, computational overheads related to the introduced heuristics and the influence of the heuristic onto the accuracy of the resulting skeleton. As a result, we established the criteria allowing us to choose the optimal heuristics for Voronoi skeleton construction algorithm depending on the critical system’s requirements.