Medial axis transformation based skeletonzation of image patterns using image processing techniques

Medial axis transformation based skeletonzation of image patterns using image processing techniques

• 1.
  International Journal of Science and Research (IJSR), India Online ISSN: 2319‐7064  Volume 1 Issue 3, December 2012  www.ijsr.net  Medial Axis Transformationbased Skeletonzation of Image Patterns using Image Processing Techniques Navjot Mann1 , Parminder Singh2   1 Department of Computer Science & Engineering., SUS College of Engineering Tangori, Mohali, Punjab INDIA navjotmann.88@gmail.com 2 Department of Information Technology, Chandigarh Engineering College, Landran Mohali, Punjab INDIA singh.parminder06@gmail.com Abstract: The medial axis of an image pattern is the loci of all inscribed disks that touch two or more boundary points without crossing any of the boundaries. The medial axis transform (MAT) is a powerful representation for objects with inherent symmetry or near- symmetry. The medial axis of 2-D image patterns provides a conceptual design base, with transition to a detailed design occurring when the radius function is added to the medial axis or surface. To make such a design tool practicable, however, it is essential to be able to convert from an MAT format to a boundary representation of an object. In the proposed work, the medial axis transform has been extracted using the Euclidean distance transform based computation. The image pattern u prepared initially in binary form and then distance of each non-zero pixel to its closest zeroed pixel is computed. This process continues till the entire image pattern is scanned to its core. Keywords: Medial Axis Transform, Euclidean Distance Transform, Charge Coupled Device 1. Introduction Skeletonization is a process of extracting a skeleton from an object in a digital image. A skeleton of an image can be thought of as a one-pixel thick line through the middle of an object which preserves the topology of that object. It is a fundamental preprocessing step in many image processing and pattern recognition algorithms. Skeletonized images (skeletons) are easier to process and they reduce processing time for the subsequent operations. It is a morphological operation that is used to remove selected foreground pixels from binary images. It is somewhat like erosion or opening. It is particularly useful for thinning and Medial Axis Transform. It is only applied to binary images, and produces another binary image as output. This operation makes use of a structuring element. These elements are of the extended type meaning they can contain both ones and zeros. The skeletonization operation is related to the hit-and-miss transform and can be expressed quite simply in terms of it. The skeletonization of an image I by a structuring element J is given as: = I – hit or miss (I, J) 2. Brief Literature Survey Thinning algorithm uses flag map and bitmap simultaneously to decide if a boundary pixel can be deleted as well as incorporation of smoothing templates to smooth the final skeleton. Various performance measurements are proposed and their comparisons and analysis are presented [5]. The images interested in a scene can be characterized by structures composed of line or curve or arc patterns for shape analysis. It is used to compress the input data and expedite the extraction of image features [3]. A good fingerprint thinning algorithm can depress image noise and promote the robustness of the minutiae extraction algorithm which helps improve the overall performance of the system. Many thinning algorithms have been devised and applied to a wide range of applications including, Optical Character Recognition (OCR), biological cell structures and fingerprint patterns [10]. Service assets are proposed to be framed into a well- established categorical structure based on pattern recognition algorithm. This design aims to provide systematic methodology and enablement architecture for analyzing, clustering, and adapting heterogeneous services for dynamic application integration [13]. Parallel thinning algorithms which generate one-pixel-wide skeletons generally have difficulty in preserving the connectivity of an image or generate spurious branches. A thinning algorithm for roman, devnagri and gurumukhi numerals has been implemented and evaluated [8]. 3. Image Preparation Before extracting the medial axis transform of an image pattern, the image is first converted to binary image with white as background and black as object’s pixels. The image can be binarized using the Otsu algorithm. In the 220
• 2.
  International Journal of Science and Research (IJSR), India Online ISSN: 2319‐7064  Volume 1 Issue 3, December 2012  www.ijsr.net  presented work, theimage is acquired using CCD camera in jpeg format. The jpeg format is converted to gray scale image using rgb2gray command in matlab. Otsu algorithm is then applied over the gray scale image in order to get the binary image. The binary image is now ready to face the MAT algorithm in order to extract the skeleton of the image pattern under test. 3. Euclidean Distance Transform The distance transform provides a metric or measure of the separation of points in the image. The Euclidean distance is the straight-line distance between two pixels. 0 0 0 0 1 0 0 0 0 The bwdist function in matlab computes the Euclidean distance between each pixel that is set to off (0) and the nearest nonzero pixel for bi nary images. The Euclidean distance between points p and q is the length of the line segment connecting them ( ). In Cartesian coordinates, if P = (p1, p2,..., pn) and Q = (q1, q2,..., qn) are two points in Euclidean n-space, then the distance from p to q, or from q to p is given by: D(P,Q) = √ (P1 - Q1)2 + (P1 - Q1)2 + . . . (Pi - Qi)2 + . . . (Pn - Qn)2 Below images show the Euclidean distance (ED) transform as computed in matlab: Figure 1: Input Image  Figure 2: ED Transform 4. Extraction of MAT The medial axis transform (MAT) of an image is computed by calculating the Euclidean distance transform of the given input image pattern. The MAT is described as being the locus of the local maxima on the distance transform. After the computation of Euclidean distance transform (EDT) of the input image, the EDT is represented in image representing the Euclidean distances as gray levels. The same is shown in above images. The maximum Euclidean distance is represented as maximum gray level intensity in the EDT image. The pixel coordinates of the maximum gray level intensity are extracted from the EDT image by converting the EDT image into row x column matrix. The row and column of the matrix gives the coordinates of the MAT line of the image pattern. 5. Performance Evaluation Parameters Connectivity number (CN): It is a measure of how many objects are connected with a particular pixel [3]. It is measured by number of color changes (black to white or white to black) in neighbourhood of pixel P[i][j] Cn= Nk – (Nk+1 . Nk+2) where Nk = color of eight neighbours of pixel analyzed N0 = central pixel N1 = Pixel to the right of the central pixel and so on Thinness Measurement (TM): It measures the degree to which an object in an image is thinned [6]. TM = 1 – (TM1 / TM2) TM1 = Triangle Count (P[i][j]) TM2 = 4 × [max(m,n) – 1]2 Where Triangle Count (P[i][j]) = P[i][j] × P[i][j-1] × P[i-1][j-1] + P[i][j] × P[i-1][j-1] × P[i- 1][j] + P[i][j] × p[i-1][j] × P[i-1][j+1] + P[i][j] × P[i-1][j+1] × P[i][j+1] And TM1 = Total number of black triangles in an image. TM2= Maximum number of black triangles an image could have Triangle Count = 2 Connectivity Measurement (CM): It is used to measure the connectivity of output skeleton. An object in an image is said to be disconnected if it has 221
• 3.
  International Journal of Science and Research (IJSR), India Online ISSN: 2319‐7064  Volume 1 Issue 3, December 2012  www.ijsr.net  broken pieces. [6] CM= S(P[i][j]) Where S(P[i][j]) = Sensitivity Measurement (SM): It is used to measure the noise in an image. This noise is mainly the perturbations in an outline of an object, not unwanted extra parts in an image. [6] SM = Where S(P[i][j]) = 6. Results Following images show the input image pattern and the corresponding MAT. Figure 3 Figure 4 Figure 5 Figure 6 Figure 7 Figure 8 Input Images – Fig. 3, 5 and 7 MAT Images – Fig. 4, 6 and 8 Table 1: Performance measure of the skeletonized image Image No. CN TM CM SM Fig. 3 0.0114 0.880 0.00013 0.005 Fig. 5 0.0209 0.984 0.00015 0.103 Fig. 7 0.0300 0.896 0.00040 0.014 7. Conclusion The result table shows the results after implementing the discussed medial axis transform based skeletonzation of image patterns. The Skeletonized images are shown in fig. 4, 6 and 8. Higher the thinness factor better is the skeletonzation or thinning. The discussed algorithm has been implemented on matlab version 7.5 and a text file is generated after every skeletonization.The performance parameters are normalized with respect to size of the image. This removes the ambiguity of the image if zoomed or compressed. Euclidean transform based medial axis transformation extraction of image patterns give a good speedy skeleton of image patterns. This serves good purpose in terms of computational speed. References [1] Mark Vincze, Bence kovari: “Comparitive survey of thinning algorithms”, Budapest University of Technology and economics. [2] Khalid Sayeed, Marek Tabe˛Dzki , Mariusz Rynnik Marcin Adamski :“K3M: A Universal Algorithm For Image Skeletonization and a Review Of Thinning Techniques”, Int. J. Appl. Math. Computer Sci., 2010, 222
• 4.
  International Journal of Science and Research (IJSR), India Online ISSN: 2319‐7064  Volume 1 Issue 3, December 2012  www.ijsr.net  Vol. 20, No.2, 317–335 DOI: 10.2478/v10006-010- 0024-4 [3] Dr. P.Subashini, S.Jansi: “Optimal thinning algorithm for detection of FCD in MRI images”, International Journal of Scientific & Engineering Research Volume 2, Issue 9, September-2011 1 ISSN 2229-5518 IJSER [4] Louisa Lam, Seong-Whan lee, Member, IEEE, and Ching Y.Suen fellow, IEEE:”Thinning methodologies – A comprehensive survey”, IEEE transactions on pattern analysis and machine intelligence, Vol 14, No.9, September 1992. [5] Dr. Chi Quek,G.S.Ng, R. W. Zhou: “A Novel single pass thinning algorithm”, IEEE transaction on system man andcybernetics,8th September,1994 [6] Peter Tarabek: “Performance Measurements Of Thinning algorithms”, Journal of Information, Control and Management Systems, Vol. 6, (2008), No.2 [7] Rafael.C.Gonzalez, Richard E. Woods, Steven I. Eddins:”Digital Image processing using Matlab”. [8] Gulshan Goyal, Dr. Maitreyee Dutta, Er. Akshay Girdhar: “A parallel thinning algorithm for numerical pattern images in BMP format”,International Journal of Advanced Engineering and Applications, Jan 2010. [9] Peter Kardos, Gabor Nemeth, Kalman Palagyi:” An order Independent Sequential Thinning Algorithm”, P. Wiederhold and R.P. Barneva (Eds.): IWCIA 2009, LNCS 5852, pp. 162–175, 2009.@Springer-Verlag Berlin Heidelberg 2009 [10]N.P. Khanyile, J.R. Tapamo, E. Dube:”A Comparitive study of Fingerprint thinning Algorithms” [11]Ferid Bajramovic, Frank Mattern, Nicholas Butko, Joachim Denzler:” A Comparison of Nearest Neighbor Search Algorithms for Generic object Recognition”. J. Blanc-Talon et al. (Eds.): ACIVS 2006, LNCS 4179, pp. 1186–1197, 2006.@Springer- Verlag Berlin Heidelberg 2006 [12]Jacob Graves, Roger Mailler:”Quatifying the Accuracy of C. Elegans Image Analysis”, BIOTECHNO 2011: The Third International Conference on Bioinformatics, Biocomputational Systems and Biotechnologies. [13]Liang-Jie Zhang, Shuxing Cheng, Carl K. Chang, and Qun Zhou:” A Pattern Recognition based Algorithm and case study for clustering and selecting business services”, IEEE Transactions on systems, man, and cybernatics—Part A: Systems and Humans, VOL. 42, NO. 1, JANUARY 2012 [14]M.A. Comeau, E. Holbaek-Hanssen:”Compression and Compaction of Binary Raster Images” Author Profile Navjot Kaur received the degree in Computer Science and Engineering from Yadawindra College of Engineering in 2010. She is pursuing Masters Degree in Information Technology from Chandigarh Engineering College, Landran, Mohali from 2010 that is under thesis. She is working in SUS college of Engineering, Tanori, Mohali in Computer Science Department as Assistant Professor. 223