1 Introduction
Document image analysis and recognition (DIAR) techniques are a primary application of pattern recognition. DIAR techniques aim to extract information from document images to enhance knowledge. There are two categories of DIAR applications: textual applications and graphical applications [1]-[2]. Textual applications deal with the text body in a document image. They include tasks related to text processing and text recognition. Text processing represents several applications such as text skew detection and correction, text extraction, text skeleton, layout analysis and text segmentation.
The skeleton of the pattern is the output of the thinning process "Skeletonization", which means peeling the contour of the text until it reaches the most medial one pixel width. Goodness of the thinning method is measured by how much the extracted skeleton preserves the topology of the shape without any interrupt [3]. Skeletonization is used in the preprocessing phase for several applications such as writer identification [4]-[6], script identification [7], and optical character recognition OCR [8].
Skeletonization is divided into two main approaches: iterative and non-iterative [9]. In iterative techniques; the peeling contour processes iteratively performed either parallel or sequential way, all unwanted pixels are erased after identifying the whole wanted pixels [9]. In sequential techniques, the unwanted pixels are removed in identifying the desired pixels in each iterative input [9]. In noniterative approach, the skeleton is extracted directly without examining each pixel individually, but these techniques are difficult to implement and slow to operate [10].
Some algorithms suffer from traditional problems such as non-one-pixel width of the skeleton and disconnected skeleton. Distortion in topological shape of skeleton is a serious problem in thinning application [11]. Moreover, several techniques fail to preserve the shape topology [12]-[13]. Spurious tails and rotating the text shape is another serious problem that most thinning methods fail to solve [12]-[14].
In this paper, a new thinning algorithm is proposed to solve the problems of previous methods. Set of experiments are conducted on shape benchmark dataset to evaluate the proposed technique. The results show that the proposed method's performance is better than that of the compared methods. Moreover, it solves the problems of skeleton width, spurious branches, distortion, and tolerance to invariance rotation.
In the following, Section 2 gives a general overview in thinning approaches and iterative methodologies. In this section, the various approaches to image skeletonization and an overview of prior work on this field are provided. Section 3 illustrates the proposed method. Section 4 describes the results of experiment. Conclusion is given in Section 5.
2 General Overview
This section describes the various approaches to image skeletonization and overview of prior work on this field.
2.1 Thinning Categories
There are two approaches of skeletonization: iterative and non-iterative. The iterative approach is divided into sequential or parallel processes by removing the contour pixels iteratively until they reach one pixel width [15]. Sequential and parallel thinning techniques are similar in determining the wanted and unwanted pixels, while dissimilar in removing time. In sequential, the removal of unwanted pixels starts in identifying the wanted process [16]-[18], while in parallel the pixels are removed after identifying all unwanted pixels [12], [19]- [21].
Non-iterative techniques produce a skeleton directly without investigating all of the individual pixels [22]. Numerous methods have been appointed to extract the skeleton using a non-iterative approach, including neural networks [23], Voronoi diagrams [24] and wavelet transforms [25].
2.2 Iterative Methods
Parallel iterative method consists of two sub-iterations proposed by Zhang and Suen [19]. Contour peeling based on 8-neighbor pixels passes over each pixel. The algorithm keeps the connectivity but two-pixel width accords in some portion of the skeleton. Ahmed and Ward are proposed a parallel iterative thinning method [13] proposes an enhancement of Zhang and Suen method based on PTA2T template; a set of rules are applied for the deletion purpose based on 8-neighbor pixels passes over each pixel. The method keeps the connectivity with one pixel width. So the author claims the proposed method is faster than other algorithms. However, it is suffering from desertion in the end of tails by extra branches appearing in the skeleton.
However, Rockett [26] claimed that Ahmed and Ward method extracted a skeleton with two-pixel width in shape portion. Rockett has modified Ahmed and Ward method to treat two-pixel width. The modification has done by adding extra rules to avoid two-pixel width in the post-processing phase. However, the method still suffers from superior tails.
Saeed, et al. [10] proposed a parallel thinning algorithm based on fixed window, where pixels are examined for deletion based on 8-neighbor weight value. Certain rules are applied at same time for each pixel. The supplementary phase comprises other rules used to keep the connectivity. The drawback is that some portion of the shape totally disappears.
A sequential iterative thinning method is proposed based on weight value of the 8-neighbors used in Huang, et al. [27]. The method goes through seven phases applied in each iteration, which lead to slow running time. The supplementary phase is used to guarantee one-pixel width of the skeleton. It is claimed that an extremely high computation time is required due to the big number of phases. However, the method does not keep the topology of shape and suffers from rotation variant by extra tails' appearing.
3 The Proposed Method
The proposed algorithm consists of three main stages: conditional contour selection, pixel removing, and one pixel width stage. The structure of these stages is addressed in the flowchart as shown in Figure 1.
Figure 1 Flowchart of the proposed method.
The binary image is acquired into the proposed method as black pixels, which is considered as both a foreground and consider an object pixel for deletion. The pixels having value '0' are considered as background pixels.
Contour detection and analysis phase: The contour is flagged where any foreground pixel '1' is found with any single background pixel '0' and considered as contour pixels. In case of the flagged pixels being adjacent either vertically or horizontally, it will cause desertion in deletion process, or stork will disappear. To avoid this problem, a single side of flagged pixels is repeated as foreground '1'. Before moving to the thinning process phase, the foreground pixels sited in corner positions are flagged as contour pixels.
Figure 2 Example of 8 neighboring pixel (a) example on discontinuance sequence by '0' (b) example on continuance sequence by '0'.
Thinning process stage: In this stage, all flagged pixels should be either removed 'pixel assigned to 0' or return it to foreground 'pixels assigned to 1'. For each flagged pixel, the examination process for the 8 surrounding pixels is conducted. These eight sequence pixels contain either flagged '×' or foreground
'1' (see Figure 2). Then, the connectivity is checked by examining if there is any background pixel '0' in this series of pixels. Afterwards, the examined pixel is removed to be assigned into '0'. Otherwise, it will be assigned into '1' as foreground. This process is repeated until all pixels are un-flagged.
One-pixel width stage: The skeleton is extracted until two previous stages remain imperfect, since a two-pixel width occurs in some portion and superior tails. Thus, one more stage is needed to overcome these problems. In this stage, a \(3 \times 3\) weight value matrix is used. Starting from the upper center, matrix value is assigned clock wise to 2n. Then the summation of these values \(\sum_{n=0}^{7} 2^n\)equals to 255. Then all cases are studded individually where they are accurate. All these values are calculated identically as shown Figure 3.
Figure 3 (a) weight values of the 8-neighbor pixels, (b) is case of 145 weights and it is result in (c), (d) is the case of 151 weight and it is result in (e).
4 Experiments and Results
Set of experiments are conducted to demonstrate the proficiencies of the proposed method on binary images. The experiments are conducted on benchmark, and different types of thinning challenges are treated. The proposed method is evaluated by comparing the performance with other commonly used methods, such as Zhang and Suen [19], Huang, et al. [26] and Saeed, et al. [9] (the K3M method). The superior tails and topological distortions are considered as basic thinning problems and are solved in the earlier methods. The present work addresses certain difficult problems that still remain unresolved, such as overlap text, highly sloped text, multiple branches, varying thicknesses and irregular text boundaries.
A benchmark textual and non-textual datasets are used in these experiments: for textual benchmark H DIBCO 2010 benchmark dataset, for non-textual, tools and mythological creatures 2D benchmark dataset [28]. The handwritten Latin text image is chosen from H_ DIBCO 2010 dataset (see Figure 4(a-1)). Nontextual binary images like the "man" class is chosen from the mythological creature's dataset (see Figure 5(a-d)), and the "horse" class is chosen (see Figure 5(e-h)). The scissor class as in Figure 5(i-l) is conducted on the tools' 2D image dataset, which includes binary shapes of tools such as scissors, pincers and others.
The method is applied on several traditional thinning challenges such as spurious tails and connectivity in the textual images (Figure 4), where they failed in other challenges such as overlap text, highly sloped text, multiple branches, varies thicknesses and irregular text boundaries. Figure 4(a) shows that the proposed method produces the best result in the case of intersecting points and that it acquires a one-pixel width of the skeleton shorn of extra pixel with smooth tracks of the text body. However, in the Huang method (Figure 4(a)), the skeleton contains excessive pixels in the cases with intersections and high slopes shape.
Figure 4 Examples of challenging in textual images and the skeleton using the proposed method (a, e, i, m, q, u), K3M method (b, f, j, n, r, v), Huang method (c, g, k, o, s, w) and Zhang and Suen method (d, h, l, p, t, x).
The method is applied on several traditional thinning challenges such as spurious tails and connectivity in the textual images (Figure 4), where they failed in other challenges such as overlap text, highly sloped text, multiple branches, varies thicknesses and irregular text boundaries. Figure 4(a) shows that the proposed method produces the best result in the case of intersecting
points and that it acquires a one-pixel width of the skeleton shorn of extra pixel with smooth tracks of the text body. However, in the Huang method (Figure 4(a)), the skeleton contains excessive pixels in the cases with intersections and high slopes shape.
Figure 5 Examples of challenging in non-textual images (man, horse and scissor) shapes from mythological creatures 2D dataset benchmark dataset [27], and the skeleton using the proposed method (a, e, i), K3M (b, f, j), Huang (c, g, k) and Zhang and Suen (d, h, l).
In addition, some pixels track aside from the proper skeleton. In Figure 4(e), the K3M skeleton includes many extra and unnecessary pixels at intersection points. The skeleton is less smooth than that obtained using the other methods in highly sloped and other challenging shapes. In total, the skeleton shapes obtained from the proposed method are smoother than that obtained using the other methods, and they preserve the text topology with the minimum number of pixels. Needless pixels in the sloped text are a serious problem in the K3M method. The proposed method overcomes thinning challenges such as the twopixel width problem, rotation through any angle, preserving the shape topology and maintaining the connectivity of the skeleton. Figure 4 shows that the proposed method (Figure 4(a)) achieved superior topology preservation compared to the other methods. The K3M method suffered from the superior tail problem (Figure 4(b)).
In the non-textual document images, a superior performance is achieved compared to other methods (see Figure 5). In 'man' class, the skeleton represents the heel and elbow smoothly in one-pixel width. In addition, there are no superior tails as in the other methods (Figure 5(f-h)).Topology preservation and connectivity are clearly maintained in the human body. In 'horse' class, one-pixel width is extracted while the other methods suffer from two-pixel width in a portion of the skeleton (see Figure 5(a)). The K3M method suffers from spurious tails in the horse legs, and misses one of the main skeleton strokes in the head (see Figure 5(b)). The Huang, Zhang and Suen and K3M methods also face difficulties with sharp turns, as in the horse tail in Figure 5(fh). The results of the final experiment also demonstrate that the proposed method yields the most accurate one-pixel-wide skeleton of the shape image (Figure 5(i-l)). However, the other methods suffer from the two-pixel width problem, as shown in Figure 5(k-l). The tails on the knobs of the scissors are preserved along with the overall shape when the proposed method is used. In Figure 5(j), the K3M method misses one of the tails on the knobs of the scissors. Moreover, the proposed method has the smoothest skeleton in the forepart of the scissors' shape compared to the other methods. Table 1 shows a comparison of the performance of the proposed, K3M, Huang and Zhang and Suen methods in the most difficult thinning problems among the images in the datasets.
The proposed method is robust in extracting a one-pixel wide skeleton in variant angles' rotation perfectly (Figure 6). The angle rotation of text body does not distress the skeleton extraction resulted and yields satisfactory results. Experimental results presented show that the proposed method is more effective and capable to thin both textual and non-textual binary images efficiently with any direction of rotation or flipping.
| 1 1 | |||||
|---|---|---|---|---|---|
| 1-pixel width | Topology preservation | Topology tracing | Rotation invariance | Tails and connectivity | |
| K3M | Yes | No | No | No | Average |
| Huang | No | Yes | No | No | Average |
| Zhang & Suen | No | Yes | No | No | Average |
| Proposed | Yes | Yes | Yes | Yes | Good |
Table 1 Performance comparison between the K3M, Huang, Zhang and Suen, and proposed methods for the most difficult thinning problems.
Figure 6 An example of text image "B", rotated and thinned (middle line) by the proposed method.
5 Conclusion
The present paper proposes a new iterative thinning algorithm. The method consists of three stages. First two stages are for extracting the skeleton, and the third is for optimizing the skeleton into one-pixel width. The experiments are conducted into multi-class chosen sets of benchmark. Textual and non-textual datasets are used for experiment purpose; for textual benchmark dataset, the H DIBCO 2010 was used, while, for non-textual the mythological creatures' 2D benchmark dataset was used. The visual experiments prove the high-quality performance for shape binary images. The superior tails and the topology problem are perfectly resolved as shown in Figure 4. Thus, the proposed method has shown superior performance rotation invariance for both textual and non-textual.
Acknowledgements
The authors would like to thank the Faculty of Information Science and Technology and Center for Research and Instrumentation Management of the Universiti Kebangsaan Malaysia for providing facilities and financial support under Exploration Research Grant Scheme Project No. ERGS/1/2011/STG/ UKM/01/18 entitled "Calligraphy Recognition in Jawi Manuscripts using Palaeography Concepts Based on Perception Based Model" and Fundamental Research Grant Scheme No. FRGS/1/2012/SG05/UKM/02/8 entitled "Generic Object Localization Algorithm for Image Segmentation".