Pruning Process Influences on Recognition Rate of Skeletal Shapes

Amir S. Almallah and Esraa Mohammed Hassoon

Department of computer science, Collage of science, University of Mustansiriyah (UOM), Baghdad, Iraq

ABSTRACT:

This paper describes effect of Skeleton pruning process on recognition shapes or objects, Pruning is accomplished by removing branches which is redundant or unnecessary branches , The removal of these small branches does not alter the shape information. It is still quite a challenging problem because of the lack of standard measurements for the importance or significance of a branch. A pruning technique is adopted to deal with the large amount of data that results in further improvement in recognition accuracy. Experimental results showed that our method can achieve good retrieval results .The moderate pruning ratio has improved the features of the shape and improved recognition accuracy.

KEYWORDS: Pruning; Skeletonization; KNN classification; Wavelet

Copy the following to cite this article: Almallah A. S, Hassoon E. M. Pruning Process Influences on Recognition Rate of Skeletal Shapes. Orient. J. Comp. Sci. and Technol;6(4)

Copy the following to cite this URL: Almallah A. S, Hassoon E. M. Pruning Process Influences on Recognition Rate of Skeletal Shapes. Orient. J. Comp. Sci. and Technol;6(4). Available from: http://www.computerscijournal.org/?p=2866

Introduction

Skeletons can be viewed as a compact shape representation in that each shape can be completely reconstructed from its skeleton. However, the usefulness of a skeletal representation is strongly limited by its instability. Skeletons suffer from contour noise in that small contour deformation may lead to large structural changes in the skeleton. A large number of skeleton computation and skeleton pruning approaches has been proposed to address this issue1-2.

Skeleton pruning is a critical step in skeleton processing and analysis. Although the skeleton has many desirable characteristics as a shape descriptor, it has an inherent disadvantage. The process of skeleton construction is very sensitive to noise on the shape boundary. Slight noise or small perturbations of the shape boundary could generate redundant skeleton branches that may seriously disturb the topology of the skeleton graph9.

Many approaches have been developed for skeleton pruning. Some of them smooth the boundary before the computation of skeletal points ,which aim to remove unwanted boundary noise and discretization artifacts14,15,16. Others try to assign a significance measure to each skeleton point or skeleton branch, and then the skeleton points/branches are pruned when their significance values are less than a given threshold17.

The KNN classification methods (K-nearest neighbor) has been used based on the feature vector by applied wavelet with four level6.

The feature of the shape has contains points which represents shape itself along the skeleton features, branches connected to these points represent branches of greatest shape significance. Pruning is accomplished by removing branches that do not terminate at junction points. These branches represent only small amounts of shape data, producing only small branches. The removal of these small branches does not alter the shape information5.

Skeletonization Process

Skeletonization is the process of reducing foreground regions in a binary image to skeletal remnant that preserves the connectivity of the original image while throwing away most of the original foreground pixels/voxels. In other words, given an input binary image skeletonization changes non-skeletal object pixels/voxels into background pixels/voxels3.

The skeleton is calculated by translating the origin of the structuring element to each possible pixel position in the image and at each such pixel position, comparing it with the underlying image pixels. If the foreground and background pixels in the structuring element exactly match foreground and background pixels in the image, then the image pixel underneath the origin of the structuring element is set to the background. Otherwise, it is left unchanged.

The skeletonization method takes operations as follows:

1. Sweep the image with one of the given structuring elements.
2. If the 3×3 image pattern matches the structuring element then put a one on the corresponding location of the resulting image, otherwise put a zero.
3. Invert the resulting image and perform a binary AND of it with the initial image. This removes the points produced by the first structuring element.
4. Repeat process 1-3 until all structuring elements have passed over the image (each element takes as input the output of the previous one).
5. Repeat processes 1-4 until the image does not change any more.

The algorithm guarantees that connectivity will be preserved so the over all geometric structure of the object in the image is preserved4-5.

Figure 1: Skeletonization Process  Click here to View figure

 

Pruning Process

skeleton pruning algorithms usually appear in a variety of application-dependent formulations10. There are mainly two ways of pruning methods:
(1) based on significance measures assigned to skeleton points10,12,13, 2based on boundary smoothing before extracting the skeletons10,11.
In the skeletonization process, some skeletal segments are split up intentionally, which may result in some noisy skeletal branches that are not useful to shape analysis.

The goal of skeleton pruning is to remove those unnecessary skeleton points or branches arising from noise or disturbance To ensure the connectedness of skeletons, we only remove the end branches(parts of a skeleton between endpoints and their adjacent junction points where the branch attaches to the rest of the skeleton) at Thus, need to prune such branches by use Arcelli and Baja’s pruning algorithm[8]. Pruning starts from an end point of each branch. For each skeletal point p in the branch that ends with pe, the quantity is computed,

where Md represents the distance map. If r is less than a given threshold Tr, p is removed from the branch, and pruning goes on. It is stopped when either r becomes greater than or equal to Tr, or the other end of the branch is reached. The quantity r(p, pe) in equation (1) can be interpreted as the loss of information we get, in terms of reconstruction of an initial shape, if the branch from p to pe is pruned away.

Figure 2 Click here to View figure

 

After pruning has been finished, very short skeletal segments are deleted, and the final step of the skeleton extraction procedure, beautification, is performed. Beautifying a skeleton means straightening its zigzags that are mostly caused by the unit-width thinning operation.

Feature Extraction

In this work, we’ve applied Wavelet transformation in time-scale representation. In wavelet analysis, a scalable modulated window is shifted along the single and for every position the spectrum is calculated. A scalable modulated window, or also know as a mother of wavelet, is the key point in which wavelet can be used to represent continues or sharp spikes of a signal7.

wavelet transform should be applied with a fast algorithm such as multi-resolution analysis. In term of signal processing, this analysis is called pyramidal or sub band coding algorithm which decomposes a single into hierarchical set of approximation and details coefficient.

Database

A data base (reference images) consists of (100) image , our approach have two data bases, the first one contains skeleton images , the second one contains pruning images, each data bases have5 classes , each one have10 samples. There are two datasets has been trained, one during skeletonization process, and other after applied pruning process.

The illustrated figures (2) below shows samples of shapes processed during applied skeletonzation and pruning method.

Results

In this experimentation we intend to study the accuracy of object recognition. We picked images randomly from the database. In recognition step, and when choose skeletonization / pruning , the skeleton/pruning feature will be extracted and for current shape the KNN has used here to find closed feature from database which close to current feature.

The output shows how a shape is diagnosed from other shapes properly. In this approach, shapes belong to five classes: birds, hammers, camels, bones, and cats. There are two methods has been applied on both trained and during recongnization phase which are skeletonization and pruning . Tables (1-5) demonstrates the results of a set of experiments with respect to different pruning spur ratio.

The results of the proposed classification and model selection methods are presented in Tables (1-5). The best result is appear on table(4) = 70 % when we use pruning ratio=6 ,whereas the recognition rate in tables(1,2,5) = 40% and the recognition rate in tables(3) =50 % , This result of Bird shape is showing in figure below.

Table 1: Spur = 12   Click here to View table

 

Table 2: Spur = 10   Click here to View table

 

Table 3: Spur = 08   Click here to View table

 

Table 4: Spur = 06   Click here to View table

 

Table 5: Spur = 03   Click here to View table

 

This result of Bird shape is achieved using KNN on pruning phase is showing in figure below.

In addition to that, the recognition rate has been calculated for many values of pruning level as shown in figure (5).

Figure 3: Result for Bird shape based on skeletonization   Click here to View figure

 

Figure 4: result for Bird shape based on pruning   Click here to View figure

 

The best performance of the recognition has been lied at value equal to (6) of pruning level, the recognition is increased, and the false of recognition is decreased.

Figure 5: Recognition Rate during pruning process  Click here to View figure

 

Conclusion

In this research, the first aspect was survey presentation of the state of skeleton the shape and using pruning method to remove protrusions without displacing the boundary points, and consequently, without displacing the remaining skeleton points. Spurious branches are completely removed while the main branches are not shorten by using pruning technique; the results showed that the pruning has improved the recognition accuracy. This happened because the applying algorithm reduce the feature of shape by remove points whose significance is low. Therefore, the results after applying pruning algorithm gives better matching than the skeleton which has more branches and these could gives low accuracy or mismatched during recognition.
The results of classifying have revealed the effectiveness of feature selection, dimensionality reduction. In addition to that, We experiment different pruning ratios. Finally, we’ve found that the better pruning ratio (remove little branches) keeps recognition and accuracy higher is pruning ratio=6 , As an interesting future research Fuzzy-KNN can applied to estimate the probability of the object belongs to shape class using view feature extracted from an unknown object and view features of training objects.

References

1. Shen Wei , BAI Xiang , Yang Xing Wei & Latecki Longin Jan,” Skeleton pruning as trade-off between skeleton simplicity and reconstruction error”, Sci China Inf Sci January , 53(1): ( 2012 ).
2. hongzhi liu , zhong-hai wu, xing zhang, D.frank hsu ,”A skeleton pruning algorithm based on information fusion” , Pattern Recognition Letters , (2013).
3. Shen wei , bai xiang , yang xingwei & atecki long jan , “Skeleton pruning as trade- off between skeleton simplicity and reconstruction error “, Department of Electronics and Information Engineering, Huazhong University of Science and Technology, Wuhan 430074, China, Department of Computer and Information Sciences, Temple University, Philadelphia, PA 19122, USA (2012).
4. T. Sebastian, P. Klein and B. Kimia , “Shock-based indexing into large shape databases”, Proc. ECCV 731–746 (2002).
   CrossRef
5. Xiang Bai, Longin Jan Latecki, and Wen-Yu Liu; “Skeleton Pruning by Contour Partitioning”, Springer-Verlag Berlin Heidelberg , (2006).
6. Mohamed Mansoor Roomi and R.Rajashankari , “Detection Of Concealed Weapons In X-Ray Images Using Fuzzy K-Nn”, International Journal of Computer Science, Engineering and Information Technology (IJCSEIT), Vol.2, No.2,( 2012).
7. Slamet Riyadi, Asnor Juraiza Ishak, et; “wavelet-based feature extraction technqiue for fruit shape classification”, Proceeding of the 5th international Symposium on Mechatronics and its Application (ISMA08), Amman, Jordan , (2008).
8. Jeong-Hun Jang, Ki-Sang Hong; “Detection of curvilinear structures and reconstruction of their regions in gray-scale images”, Image Information Processing Laboratory, Department of Electrical Engineering, San 31, Hyojadong, Namku, Pohang, Kyungbuk, 790-784, South Korea (2001).
9. Tesfaye Admassie Aberra; “Topology Preserving Skeletonization of 2D and 3D Binary Images”, Echnische University Kaisersalutern, Department of Matchmatics (2004).
10. Shaked D, Bruckstein A. ,”Pruning medial axes”, Computer Vision and Image Understanding, 69(2): 156–169 (1998).
    CrossRef
11. Mokhtarian F, Mackworth A. ,”A theory of multiscale, curvature-based shape representation for planar curves”, IEEE Trans Pattern Analysis and Machine Intelligence, 14: 789–805 (1992).
    CrossRef
12. Ogniewicz R, K¨ubler O.,” Hierarchic voronoi skeletons”, Pattern Recognition, 28(3): 343-359 (1995).
    CrossRef
13. Malandain G, Fernandez-Vidal S., “ Euclidean skeletons”, Image and Vision Computing, 16: 317–327 (1998).
    CrossRef
14. P.Dimitrov, C.Phillips, and K.Siddiqi,” Robust and efficient skeletal graphs”, in: Conference on Computer Vision and Pattern Recognition, pp1417–1423 (2000).
    CrossRef
15. K.Siddiqi , S.Bouix , A.R.Tannenbaum, S.W.Zucker, Hamilton–Jacobi ,”skeletons”, Int.J.Comput.Vision 48(3): 215-231 (2002).
    CrossRef
16. K.Siddiqi, B.B.Kimia ,C.Shu, “Geometricshock- capturing ENO schemes for subpixel interpolation ,computation, and curve evolution”, ISCV (1995).
17. R.L.Ogniewicz ,O.K ubler , “Hierarchic Voronoi skeletons”, Pattern Recognition, 28(3): 343-359 (1995).
    CrossRef

---

This work is licensed under a Creative Commons Attribution 4.0 International License.