ABSTRACT - This paper describes an efficient parallel binary image thinning algorithm for binary images. This algorithm improves the fundamental properties of thinning such as pixel connectivity, excessive erosion , thinning,8-connectedness. The algorithm preserves the connectivity of an input image. An experimental result shows the better performance in terms of thinning.
Keywords: thinning, erosion, edge point, endpoint, skeletal.
Parallel thinning is becoming a valid and fundamental approach to thinning and skeletonization, due to the ever increasing growth of availability of parallel architectures and the real possibility of realizing machine vision systems. Recently, its interest has also grown both in design and objective standpoint; this has lead to parallel thinning algorithms. The parallel thinning algorithms are characterized by the representation of a simultaneous deletion process of all the "deletable"contour points; to be efficient, the number of repetitions or iterations should be ideally equally to half of the maximum width of the figures present in picture. Of course, the less time-units and iterations the algorithm spends the more it is efficient under the constraint of remaining the 8-curve as perfect as possible and preventing excessive erosion. To deal with the later requirements, each iteration of a parallel thinning algorithm is subdivided into n iterations/sub cycles (n=1, 2, 3,â€¦..) indeed, as stefanelli and rosenfeld indicated ,in parallel thinning, all the points in an image can be processed simultaneously, and the operation on each point depends on the values of its neighbors. Parallel thinning algorithms with a 1-sub cycle/iteration have the disadvantage that they may yield no connected or even empty medial lines for connected figures; the case where a two-pixels-wide straight stroke is entirely eliminated by a single iteration is widely known . Based on these considerations and computational requirements, we propose a thinning algorithm with 2-iterations which is able to
Get your grade
or your money back
using our Essay Writing Service!
1) Reduce the number of iterations and the time complexity of each iteration;
2) Produce a perfect 8-connected thinned image;
3) Prevent the excessive noise and excessive erosion.
The meaning of these objectives will be clarified in the next sections. According to the algorithm, described in section 4, a pixel is deletable by analyzing the values of its neighboring pixels within the area of (3X3) of pixels in the first iteration and an area of (3 X 3) in the second iteration. The algorithm is characterized by the fact that the first iteration is used to remove boundary elements of an object in all directions,
while the second iteration is used to remove corners and diagonal boundary elements in the North East, North West, South West, and South East directions. The isotropic behavior allows the generation of more regular skeletons and better qualitative results. Experimental results in terms of degree of 8-connectedness, degree of erosion, stability under rotation, boundary noise sensitivity are reported in section 6.
2. REVIEW OF PREVIOUS PARALLEL THINNING ALGORITHMS
The study of thinning has been improved until lately. The well- proved thinning algorithms are ZS algorithm, LW algorithm, etc. ZS algorithm has a problem that the slanting lines are erased.LW algorithm has the problem which slanting lines with two pixel width were remained.We can find that ZS algorithm makes one-pixel line but loses connectivity in some images. LW algorithm have the same problem, however the proposed algorithm can settle the problem and make perfect slim line of 1-pixel with 8-neighbour connectivity even for the two pixel width image. The procedure followed in ZS algorithm is as follows.
ZS parallel thinning algorithm performs sub-iterations step wise.
The first step
The pixels satisfied with the following conditions are erased.
2 â‰¤B(Pi) â‰¤ 6
A(Pi) = 1
P2 * P4 * P6 =0
P4 * P6 * P8 =0
The Second step
Condition 3 and 4 in the first step are replaced with the following condition.
3) P2 * P4 * P8 = 0
4) P2 * P6* P8 = 0
To solve the problem of slanting lines with 2-pixel width are erased, LU and Wang replaces the step 1 (2 â‰¤B(Pi) â‰¤ 6) in ZS algorithm with the condition 3 â‰¤B(Pi) â‰¤ 6. Using the modified condition, the slanting lines do not disappeared, however the algorithm can not make 1-pixel with 8-neighbour connectivity.
3. BASIC NOTATIONS
Always on Time
Marked to Standard
In the discussions below, it is understood that a pixel P examined for deletion is a black pixel, and the pixels in its (3 X 3) neighborhood are labeled as xi, i =1,â€¦ 8, as shown in Fig 1a.
Definition 1:The pixels P1, P2, ., P8 are the 8-neighbors of Pi and are collectively denoted by N(P).They are said to be 8-adjecent to P.The number of black pixels in N(P) is denoted by B(P), i.e., B(P) = âˆ‘I â‚¬ N(p) xi.
Definition 2: The pixels P1, P3, P5, and P7 are the 4-neighbors of P and are said 4-adjecent to P.
Definition 3: A sequence of points Z1, Z2,â€¦..Zn is called an 8-(or 4-) path if Zi+1 is an 8-(or 4-) neighbors of Zi for i=1, 2,.., n-1.
Definition 4: A subset C of a picture P is 8(or 4-) connected if for every pair of points (x,y) in C there exists an 8-(or 4-) path from x to y consisting of points in C.
Definition 5: The number of transitions from a white point to a black point and vice-versa (when the points in n (p) are crossed, for examples in a counter clockwise order) is called Rutowitz number and defines as
A (P) = âˆ‘8i=1 | xi+1-xi |, where x9 = x1.
Based on the previous common definitions a lot of algorithms where stated. These algorithms are widely considered to be a well assisted set for benchmarking parallel thinning . In the next section the proposed two pass thinning algorithm has been discussed.
4. PROPOSED THINNING ALGORITHM
A parallel thinning algorithm with two iterations usually requires two sets of pixels deletable in parallel whose union contains all the deletable border pixels, where "deletability in parallel" means that all black pixels P in the set can be simultaneously deleted without causing excessive erosion and retaining the topology of any binary pattern. We recall that excessive erosion commonly means that a deleted border point causes the loss of the object's shape. Some more definitions are to be joined to the previously reported definitions as they pertain to our algorithm.
Definition 6: A black point P that has at least one white 4-neighbor is called an edge-point (i.e., it lies along the edge of the pattern).
Definition 7: A black point P that has at most one black 8-neighbor is called an end-point.
Definition 8: A black point P, the deletion of which would break the connectedness of the original pattern, is called a break-point.
In essence, the proposed thinning algorithm consists of executing several iterations over the pattern, where many black points are deleted in each iteration. If no point is deleted at the end of iteration, the thinning procedure stops. In any sub cycle, the set of black pixels P to be deleted from the pattern must satisfy the following intuitive criterion. A set C of black pixels P is deletable in parallel if every point P in this set is an edge-point, but not an end-point, or a break-point. Also, its possible deletion must not cause excessive erosion in the pattern. The 3*3 mask is used for each picture element. That is, the values of the eight neighbors of a central element (P1) are used in the calculation of its values for the next iteration. The neighboring values can be denoted by the eight directions (P2, P3â€¦, P9) shown in fig 1.Let A(P1) be the number of pattern 01/10 in the order set (P2,P3,â€¦,P8,P9,P2) of the neighbors of P1, Then the point P1 is deleted from the figure, if all of the conditions are satisfied from rule 1 or rule 2.
To hold the above criterion, some rules should be stated.
Rule 1: In iteration 1, the set of black pixels P satisfying the following conditions
i) A (Pi) =1; ii) 2 â‰¤ B (Pi) â‰¤ 6;
iii) P2 * P4 * P6=0, iv) P4 * P6 * P8=0,
are deletable in parallel from any binary image.
Proof:: According to the condition ii) there exist from two up to six black pixels in the neighborhood of the pixel P candidate to deleted. The condition i) means that there are only one 0-1 (or equivalently 1-0) transitions in the same neighborhood; this corresponds to having one 1s among x1,â€¦.., x8, while the remaining seven pixels can be all 0 or four of them are 1. Based on these considerations, the set N (P) contains between two and six black pixels which are 4-connected among themselves, i.e., all the possible pairs of these pixels are connected by 4-paths; thus, P is not a break-point. Moreover, B(P) â‰¤ 6 and B(P) â‰¥ 2 ensure, respectively, that P has at least a white 4-neighbor and that P is not an isolated or end-point. Since the entire set of black pixels P that satisfy the conditions i) and ii) is deletable in parallel, objects that are two pixels wide completely disappear. This difficulty cannot be solved by using the condition i) and ii) only. To overcome this problem, conditions iii) and iv) are checked and if it is found to be true, its central pixel is saved or, equivalently, all black pixels P that satisfy the conditions iii) and iv) can be deleted in parallel. Let us now illustrate the second iteration. In this case, mentioned before, we deal with the direct thinning of the corner points and diagonal lines present in a digital pattern.
This Essay is
a Student's Work
This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.Examples of our work
Rule 2: In second iteration, the set of black pixels P satisfying the following conditions
v) A (Pi) = 1, vi) 3 â‰¤ B (Pi) â‰¤ 6,
vii) P2 *P4 *P6=0, and viii) P4 * P6 * P8=0,
are deletable in parallel from any binary image.
Proof:: According to the condition vi) there exist from three up to six black pixels in the neighborhood of the candidate pixel P to be deleted. The condition v) means that there are one 0-1 (or equivalently 1-0) transitions in the same neighborhood; Based on these considerations, the set N(P) contains between three and six black pixels which are 4-connected among themselves, i.e., all the possible pairs of these pixels are connected by 4-paths; thus, P is not a break-point. P has at least a white 4-neighbor and is not a break-point. Moreover B (P) â‰¤ 3 ensures that P is not an isolated point or end-point. Since the entire set of black pixels P satisfying condition v) is deletable in parallel, the two pixels wide diagonal lines completely disappear. To face this problem, it is necessary to save pixels which do not satisfy condition v) indeed.
Fig (2) Template Corresponding to the deletion condition
5. THINNING METHODOLOGY
Our algorithm considers only an eight neighborhood. However, it has difficulty in preserving the connectivity of a pattern. To deal with this problem, we use a 3x3 weighted template. The template shown in Fig (2) is used to indicate the variations of eight neighboring pixels. A connectivity value is the sum of each weight of eight directions. After the connectivity value is calculated and specific conditions are applied, it can be determined whether the object point is to be deleted or preserved. An essential point is defined as one which includes a connect point and an end point. The connect point is a point that its removal causes a disconnectivity in 3 x 3 window. The end point is a point that has only one of the eight-adjacent points. Our proposed parallel thinning algorithm simply applies the above definitions and the connectivity value in parallel to the entire image to over come the deficiencies in previous parallel thinning algorithms. The algorithm consists of two steps. Step 1 calculates the connectivity value for each object pixel. Step 2 removes non-essential points for each object pixel. A non-essential point is a point that is not the essential point and has the smallest connectivity value in an eight neighborhood. If all pixels are the essential points, the recursion is terminated. The deletion or retention of a (black) pixel p would depend on the configuration of pixels in a local neighborhood containing p. According to the way they examine pixels, these algorithms can be classified as sequential or parallel. In a sequential algorithm, the pixels are examined for deletion in a fixed sequence in each iteration, and the deleÂtion of p in the nth iteration depends on all the operations that have been performed so far, i.e., on the result of the (n- l)th iteration as well as on the pixels already processed in the nth itÂeration. On the other hand, in a parallel algorithm, the deletion of pixels in the nth iteration would depend only on the result that remains after the (n-l)th iteration; therefore, all pixels can be examined independently in a parallel manner.
6. RESULTS AND COMPARISONS
In this section, the results obtained by the proposed algorithm and, Zhang and Suen [3-6], Lu & Wang [4 -6], are compared by using as comparative terms
1) Degree of 8-connectedness;
2) Degree of erosion;
3) Boundary noise sensitivity.
Comparisons concerning the time-units spent by the algorithm to converge are also compared with those spent by the algorithms of Zhang and Suen, Lu & Wang which turned out to be comparable in terms of computational complexity to our algorithm. Fig. 3,4,5,6 &7 is chosen to test the degree of 8-connectedness and excessive erosion. The thinning results shown in Fig. 3(d),4(d),5(d) ,(6d) &(7d) obtained with the proposed algorithm are perfectly 8-connected and do not have an excessive erosion in thinning the images.
7. WHY THIS ALGORITHM WORKS.
A pixel can be deleted only if it satisfies the following conditions.
These conditions will allow to satisfy the conditions that are specified based on the basic notations i.e., a pixel can be deleted only when it satisfy the above conditions. The explanation of how the pixels are deleted is as follows.
According to the condition 2, A(Pi) should be equal to 1, it means that there should be only one '01' pattern in the eight neighbors, so we can say that all the 1's in 8 neighbors should be in a serial order i.e., in the order set p1, p2, p3, p4â€¦,p9.
According to the first condition if the value of B (Pi) is 1, then it means that there are seven 0's and one 1, but this should not be done because if we have only one '1' then it becomes end point, if a pixel has to be deleted If there is only one 1(one) in the neighborhood, P1 is an end point and should not be deleted. If there are seven 1's, P is not a contour point. If A (Pi) â‰ 1, P1 is an arc point and deleting P1 would break the connectivity.
Now, even if the p1 pixel is deleted there is connectivity among the other 1's present in this 3x3 subset, this proves that p1 is not a break point, where it is stated that a break point is a point, the deletion of which would break the connectedness of the original pattern, is called a break-point. Then it should never be an endpoint, so the value of B (Pi) should always be more than '1'. Now from the first two conditions we can say that all the 1's in the 3x3 matrix should be in a serial order and we should have at least two 1's, the illustration of some of examples is shown as follows.
According to the definition of an edge point, a black point, p that has at least one white 4-neighbor is called an edge-point. It means that there should be at least one '0' among the four neighbors P2, P4, P6, P8. This can be done by taking the two conditions
But if P2,P4,P6 all are 1's and only P8 is 0, this condition will not be satisfied that is the reason why we take another iteration where we specify other two conditions which are executed only when the above conditions are not satisfied.
7. 3â‰¤B (Pi) â‰¤6
8. A (Pi)=1
We know that in the ZS algorithm slanting lines are erased due to the problem of 8-connectivity, and lot of 2-pixel width lines are present. The drawback of LW algorithm is the slanting lines with 2-pixel width remain existing; the proposed algorithm can overcome the problem and make perfect slim line of 1-pixel width, 8-neighbor connectivity even for the 2-pixel width image.
In this paper we have presented a new parallel thinning algorithm that make the image one pixel thick and preserves the end points. This algorithm also ensures the 8-neighbour connectivity. The previous Zhang Suen's algorithm . Lu and Wang algorithm can reduce the end point . However, the proposed algorithm shows the better performance and outputs more quality images than the previous algorithms. The proposed algorithm is a parallel image thinning algorithm and the method can extract the one pixel thick lines. The proposed algorithm has the features like one-pixel thick, end point preservation, and perfect 8-connectivity.Our proposed an efficient two pass parallel binary image thinning algorithm can be useful in image thinning, image understanding and pre processing, etc.