This article covers a wave skeletonization algorithm for raster images. It contains diagrams of algorithms for primary graph building and separating wave generation into wavelets. It is proposed to store the graph's structure in nested form to save memory and make it easier to modify. Deming orthogonal regression is proposed for primary graph optimization as part of successive approximations method.
There is a number of tasks which require building raster image skeletons, e.g. handwritten text recognition, fingerprint comparison, processing medical or cartographical images, technical drawings [1-5], etc.
Various skeletonization algorithms exist, including Zhang-Suen algorithm [4], template method, wave algorithm [1, 6, 7], etc. The wave algorithm is covered in this article.
Essence of the wave algorithm for raster image skeleton calculation has already been described and illustrated in detail particularly in [1, 4, 6]. However, when implementing programs with this method, a number of questions, subtleties and nuances may arise, which are the subject of this article. The article contains diagrams of algorithms for primary graph building and separating wave generation into wavelets. Scientific novelty of this publication is that the graph describing object’s skeleton is stored in a nested structure instead of connectivity and incident matrices which saves memory and makes it easier to change graph’s structure, and also that Deming orthogonal regression is used for primary graph optimization as part of successive approximations method.
Image skeleton refers to a set of points equidistant from image borders. Several preparatory steps are usually taken before object’s skeleton is built. These steps include image preprocessing (eliminating minor noise, etc.) and binarization. Binarization refers to the process of converting color and halftone images into dual-color, i.e. binary, images. Binarization is done using thresholding, point transformation, folding and border enhancement methods, extracting low-frequency and highfrequency image components, etc.
For our purpose, wave skeletization algorithm can be divided in two stages: primary graph building, including wave initiation and tracking covered distance, separation and attenuation points, followed by graph optimization where excessive information is dropped. Workflow for these stages is illustrated in figure 1.
At the first stage, spherical wave is initiated within an object. Wave generation is the wave front. Points that belong to certain wave generations are marked by different colors in the image. Central pixels of each odd generation included in the primary graph as its nodes are tracked.
However, primary graph usually contains a lot of excessive information, so redundant point are eliminated at the optimization stage.
Graph is built by tracking spherical wave propagation path over the image. 2.1. Spherical wave propagation Spherical wave is initiated at any pixel inside the object.
Spherical wave generation is obtained by using 4- and 8-connected propagation alternatively. Connectivity refers to number of pixels adjacent to the current pixel. For 4-connected wave propagation, the pixels above, below, to the left and to the right of the current one are considered its neighbor pixels (see figure 2(a)). For 8-connected propagation, accordingly, all 8 pixels around the current one are considered its neighbor pixels (see figure 2(b)). In figure 2, the current pixel is designated as P, and its neighbors for 4-connected and 8-connected representations are numbered.
When a wave is initiated, the 4-connected propagation is applied first; then 8-connected propagation is applied to each pixel of the previous 4-connected generation, and so on alternately. This way, the wave propagates in octagonal shape. This approach is based on Huygens-Fresnel wave theory principle positing that each element of wave front can be considered as secondary disturbance center producing secondary spherical waves.
There are several special aspects to spherical waves: wave propagation becomes steady regardless of its initial point after at most 2N steps, where N is the line width in pixels (see figure 3); such wave is “able to” turn and effectively go round various obstacles. Small one- or two-pixel obstacles have little impact on wave propagation. However, it is recommended to eliminate such obstacles at the binary image generation stage for wave stability.
Zero generation consists of one initial pixel that is marked as first in the image. It is located at the center in figure 4.
Object’s graph is stored in memory as a nested structure [8]. When this method of storing graph structure is used, each of its nodes is determined by a nest consisting of (x, y) coordinates of graph node and a list of addresses for transitions to next (child) nests (graph nodes). Advantages to this method are that it allows to easily modify graph’s structure and does not require much RAM as opposed to connectivity or incident matrices.
An example of graph and corresponding nested structure are shown in figure 5. Nests contain graph node coordinates (xi,yi) and Ai – a reference to the list of references to neighbor nests (graph nodes).
A diagram of the primary graph building algorithm is shown in figure 6.
Figure’s skeleton is built by tracking centers of each odd wave generation. Current wave generation is stored in memory as a list of pixel coordinates of this front. Let us designate the list of points of any odd generation as S4, because its points are 4-connected neighbors of previous generation’s points.
Accordingly, we shall designate lists of even generations as S8, because they are 8-connected neighbors of previous generation’s points.
Each generation of a wave is located between extreme pixels that have coordinates (x1, y1) and (x2, y2). Extreme pixels of a wave are pixels that have at most one neighbor in their generation. For the
Besides, wave generation may include several separate fronts. This happens when wave generation is separated into wavelets.
This situation can be identified using the number of extreme points in S4 list of generation points. If there are more than two extreme points, separation has taken place and several wavelets are in the list (an example of a wave divided into three fronts is shown in figure 7). In this case, separate lists of wavelets (D1, D2,.., Dn) are queued. Separation of S4 wave generation list into D1, D2,.., Dnwavelets is shown in figure 8. of the parent wave and wavelets [5, 6, 9].
Whenever a wave turns or an image element becomes thicker, the number of extreme points remains constant, thus the wave width increase can be neglected.
A wave attenuates when encountering another wave. In this case, the graph closes.
The first method used to optimize the graph (i.e. eliminate redundant information) is successive approximations method. It works as follows: a straight line is drawn through the first two nodes of the graph, and a check of deviation of each successive point from that line is done. If the deviation is within ɛ limit (which is specified comparable to thickness of lines in the image), the point belongs to this line; otherwise, it forms the next line.
In successive approximations method, equation coefficients of the line + + = 0 going through points ( 1, 1) and ( 2, 2) are calculated using the following formulas: = 1 − 2, = 2 − 1, = 1 2 − 1 2.
Then, for each successive point ( , ) of graph, its distance from the line + + = 0 is calculated using the formula = | + + | ∙ ( 2 + 2)−1/2. If r< ɛ, the point belongs to the current line.
The obtained set of points belonging to the same line is approximated using orthogonal regression. Orthogonal regression differs from simple linear regression in that it makes allowances for observation errors along both x and y directions (see figure 10).
If points are approximated by the line that is determined by equation = 0 + 1 , regression coefficients are calculated using the following formulas [10]: 1 = ( − + (( − )2 + 4 2)1/2) ∙ (2 ) , −1 where
0 = ̅ − 1 ̅, ̅= 1 ∑ , ̅ = 1
∑ , = = = 1 −1
1 −1
1 −1
∑( − ̅)2, ∑( − ̅)2, ∑( − ̅) ( − ̅).
Since the equation y= 0 + 1 does not determine vertical lines, let us put it to the form +
= 0. For that purpose, we shall calculate the following coefficients , , : = 1, = −1, = 0.
If = 0, the line is parallel to Y axis, and the equation looks like = . In this case, the line has the following coefficients: = −1, = 0, = .
If, on the other hand, = 0, the line is parallel to X axis, and the equation looks like = . In this case, the line has the following coefficients: = 0, = −1, = .
After the coefficients of approximating line have been found, extreme points are adjusted, i.e. projected onto approximating line, whereas other intermediary points are eliminated from the graph.
Coordinates ( , ) of projection of extreme point ( 0, 0) onto line + + = 0 obtained with orthogonal regression method are calculated using the following formulas: = ( ( 0 − 0) − = ( ( 0 − 0) − )⁄( 2 + 2), )⁄( 2 + 2).
Because, in general, the graph may be closed, all processed nodes are marked so the program does not get caught in an endless loop. 4. Results and conclusions In this article, diagrams of algorithms for primary graph building and separating wave generation into wavelets are proposed. A suggestion is made to store the structure of the graph representing object’s skeleton in nested form instead of connectivity or incident matrices to save memory and make the graph’s structure easier to modify. Scientific novelty of this publication is also that Deming orthogonal regression is used in successive approximations method for primary graph optimization.
A wave skeletonization program has been developed using C# language. The program proactively converts color raster image into binary image using thresholding where the threshold is an average between maximum and minimum brightness. Then the primary graph is built and optimized.
Wave skeletization algorithm does not require much memory because memory is only allocated to store graph’s skeleton and lists of pixels of the current and next wave generations. Spherical wave marking is done in the source image which is easily restorable. The algorithm is easily parallelized when several starting points of wave initiation are used. For wave initiation, it is preferable to choose pixels on lower or upper borders of symbol images; this makes skeletons smoother.
Today, wave skeletization is used successfully to build skeletons of symbols (letters, digits, etc.) for further processing as part of recognition process. However, this algorithm is not as effective for building fingerprint skeleton, because finger papillary picture has more complex structure, thus wave propagation and further analysis have poor accuracy [1]. Points for Fingerprint Recognition Bulletin of the South Ural State University. Ser. Computer Technologies, Automatic Control, Radio Electronics 15(3) 11-17 Khaustov P A 2017 Algorithms for handwritten character recognition based on constructing structural models Computer Optics 41(1) 67-78 DOI:10.18287/2412-6179-2017-41-1-67-78 Glaister P 2001 Least squares revisited The Mathematical Gazette 85 104-107 Zhang T Y and Suen C Y 1984 A fast parallel algorithm for thinning digital patterns Comm. of ACM 27(3) 236-239 DOI:10.1145/357994.358023 Saeed K, Tabędzki M, Rybnik M and Adamski M 2010 K3M: A universal algorithm for image skeletonization and a review
of thinning techniques International Journal of Applied
Mathematics and Computer Science 20(2) 317-335 DOI:10.2478/v10006-010-0024-4