An efficient integer-based skeletonization algorithm

The problem of generating vector representation of a raster image has been the question of present interest for decades. Although, there are many appr oaches to this problem, most of them suffer from sophisticated computations and irrational memory usage. We introduce here a new skeletonization algor ithm that is very efficient in terms of time and memory consumption. Starti ng from the description of our approach to the concept of skeleton on raste r grid, we present a comprehensive explanation of the algorithm. Its main i dea consists of generating a special polyline for each raster line consider ing them in top-to-bottom direction. skeleton is constructed from points of these polylines. The skeletons obtained by our algorithm allow the precise reconstruction of the initial raster shapes; therefore they may reflect so me artifacts possible on raster grid. For this reason, we also present here two algorithms of simplification and our approach to defects filtering on a stage of skeleton generation. The time of simplification by presented alg orithms depends linearly on the number of input points that makes these met hods fast and efficient. The paper concludes with performance evaluation an d discussion of possible implementations of the introduced techniques. (C) 2000 Elsevier Science Ltd. All rights reserved.