m4iv>IQ FEATURE EXTRACTION AND IMAGE SEGMENTATION 91 INTRODUCTION The discussion till now was concer with the image processing where input was an image and output was also an image. Now on words, we will study different processes in which input signal is an image and outputis the feature of images. The basic purpose of feature extraction from an image is to make easy the computer analysis and process of an image. “A feature is defined as a function of one ‘or’ more measurements, the values of some quantifiable property ofan object, computed so that it quantifies some significant characteristics of object”. One of the biggest advantages of feature extraction lies that it significantly reduces the information (in comparison to criginal image) to represent an image for understanding the content of image. Characteristics of an objectis also called ‘attribute’ of feature of an object. 9.2 CLASSIFICATION OF FEATURES Features can be categorized in different ways. But the most acceptable classification is discussed in this book Features can be catagorized in two categories: i 1. Low Level Features : Low level features can be extracted directly fromimage. 2. High Level Features : High level features can not be extracted directly from an image. They Must be based on low-level features. ; Fora good feature extraction process, the feature extraction should be invariance so that feature ®ttraction is faithful and applicable for any position, location, size and scale variations. and description and object / pattern recognition of extraction (or attribute extraction) of an image’. between these processes will be difficult. 141 pers Now onwards ‘segmentation, representation ' pee are basic and different approaches for feature “hould be clear to readers otherwise the correlation142 Digital Image Processing 9.3 FEATURES OF AN IMAGE There may be a number of features of an image, but broadly features of an image are ; ‘point, edge, line region, and corner point’ which will be discussed in this chapter. For more fine study of an image, we may study the attributes of an image that will be studiedin preceding chapters. 9.4 ATTRIBUTES OF FEATURES There may be a number of attributes (characteristics) of features, but we are basically interested in the following attributes of feature. 9.4.1 Geometrical Attributes Geometrical attribute of a feature may be orientation, length, curvature, area, perimeter, line, width, diameter, elongation, axes of symmetry, number /position of singular points. 9.4.2 Topological Attributes Topological attributes of a feature may be above, left, adjacency, common end point, parallel, vertical touch, overlap ete. Now we will start with feature extraction of an image. 9.5 COMPLETE PROCESS OF FEATURE EXTRACTION. A complete process of feature extraction has three basic parts : 1. Image preprocessing ; 2. Desired feature extraction ; and 3. Invariant extraction. By image preprocessing, we generally remove the noise from image. Due to noise generally W° calculate false features of an image. For better feature extraction, we can adjust contrast and satura” tion level of an image also. Now after preprocessing, we can extract the desired features of an image. But it is always de!" able that extract the lines always before extracting the feature of an image. The final step of feature extracting is to extract the features which are invariant so that those features are always useful because not changing with relation, location, position and size of an imas® 9.6 IMAGE SEGMENTATION 4 ee ee , ipher level Image segmentation subdivides an image into its constituent regions ‘or’ object. For Nghe a ul feature extraction, image segmentation is fundamental, For image segmentation, we depen features of an image such as point, line, edge and region.Feature Extraction and Image Segmentation 143 Image segmentation is very important but difficult process because the. ‘accuracy of image segmenta- tion defines the success ‘or’ failure of computerized analysis procedure of an image. Now let us discuss point, line, edge and region detection one by one in detail that will help us for segmentation ofan image. 9.6.1 Point Detection ion is based on discontinuities in image, Our approach is based on abrupt change in intensity of -So these isolate points, whose intensity are changing abruptly, may be detected straight forward by using the following mask: w, | w | = =I w, | ws | Ww, =1/ 8 [=1 w, | Ws | Ww» =1[-1[=1 (@) General mask (b) Mask for point detection. Fig. 9.1 Marks for point detection Recall that the general expression for response of a filter/mask is given by R= Wy 2y + Zp + eaves + Wy Zo 3 R= Yw,z; (9.1) where 2; is the gray level of the pixel associated with mask coefficient. The response of the mask is defined with respect to its center location. We say thata point has been detected at location on which maskis centered. IFat the location the response of mask is greater than a particular predefined threshold. IRI2T T= Non negative predefined threshold value, Recall that the sum of all coefficients of mask is always zero that will cause the response of mask zer0 if we have constant gray level (means we donot have any point). Point detection isa low level feature extraction. 9.6.2 Line Detection “tis also based on abrupt change in intensity of gray level of image. It also reflects a discontinuity in image”. For the line detection, we use the following mask : =] =met Esta ee ee =1]2]=1 2[-1]-1 2b ee ese S15 2a =1/ 2[-1 =) Enle0 2] -1/-1 =1/2E2 =1 2 Horizontal + 45° Vertical Fig. 9.2. Mask used for line detection. By moving first mask on the image, we can detect the one-pixel thick line in horizontal direction. The direction of line is simply decided by the coefficients of mask. The preferred direction of maskis Weighted with a larger coefficients than others. : ‘ _ On the basis of above discussion, second, third and forth masks are for + 45°, vertical and - 45 lines respectively.144 Digital Image Processing Now suppose that we have run all the masks on image a nd there are four responses Rj, Ry, R, ang R,. Suppose that at a particular point. IR, | >| R; | where j=2,3,4andj#1 ated with horizontal line. Thus we can decide, which point is associated Then that point is associ: with which line. Line det tion is a low-level feature extraction. 9.6.3 Edge Detection Edge detection is one of the most important phenomena in image processing. 9.6.3.1 Introduction and Basics of Edge Detection Edge detection is also based on discontinuity measurement. It also shows the abrupt changeinthe intensity of gray levels “Edge can be defined asa set of connected pixels that ies in the boundary between two regions”. An ideal edge has been shown in figure. Here we see that a immediate transition of gray level has been shown. Technically “An ideal edge is defined asa set of connected pixels each of which is located at an orthogonal step transition in gray level”. Thus an ideal edge has an step type response. But practically, edges cannot be sharp. Edges practically are blurred and degree of blurring factors such as quality of the image acquisition system, the sampling rateand depends upon many quired. As a result edges are ‘ramp like’ the illumination conditions under which the image is acq profile as shown in Fig. 9.3. The key points are : 1. The slope of ramp is inversely proportional to degree of blurring in the edge. More blurring means less slope. 2. Blurred edges are always thick and sharp edges are always thin. Model of an ideal digital edge Model of a ramp digital edge “Gray-level profile Gayl of ghorizontl ne fa hereon ine through the image through the image (a) Ideal Edge (b) Practical Edge Fig. 9.3 Model of ideal and practical edges 9.6.3.2 Edge Detector As discussed at the beginning of edge that edges are abrupt changes in the gray levels at the! bound: ary of two regions, so we can use derivatives for the measurement of edges. As if there is no 648"Feature Extraction and mage Segmentation 145 means nochange in intensity level, resultant derivati shows some value means, there isa possibility ofe derivative and second de ative of an practical edge. We may desc 1, Aswe know that ramp is given by igure 9.4 we have drawn the first ibe as follow : )=r()= 8=r(=t ne $o first derivative will be dg(t) _ dr(t) dt dt -(9.3) Thus for edge (means gray level transition) )) always shows a constant first derivative and for constant gray levels. § ()=r(t)=constant (94) ag) ean é dt Sanden eo) First derivative will be zero thus by first derivative, the presence of edge is decided 2. Now take the second derivative from first derivative. Here we see that we get positive second derivative for edge at dark side and negative second derivative for edge at white side. Thus by second derivative we can find the edges situated at dark side and white side of image. (Butif carefully, we are not absorbing the first derivative and second derivative of an edge, then by second derivative we can confuse about the presence of edge). Gray-level profile First derivative Second derivative i ivatives of Edges. ig. 9.4 First and second derivatives of - rivative of edge; f iti ive and negative second det Now assume a line between positive second derivative Bi vate ‘hen mille ofthis line shows the center of edge. Thus by second derivative of edge,146 Digital Image Proc ng edge (This is called the zero crossing of edge also. Because detecting center means detecting thy location where edge is crossing zero). Till now we have discussed general properties of edge operators. But now we will discuss the specific qualities and practical way of calculating derivative of edges. 9.6.3.3 First Derivative (Gradient Operator) of Edge First derivative is also called gradient of an signal mathematically. The gradient ofan image f(x,y) at location (x, y) is defined as the vector (é| | (96) vd Loy, Vf= (We know the gradient shows the maximum rate of change at any point) Magnitude of this vector is defined as meg (Vf)=[G?+G3]° This quantity gives the max rate of change of f (x, y) per unit distance in the direction of Vf. Let ot (x,y) represent the angle of vector V fat (x, y), then this angle is given by a(x, y)= tan! (2) 09 (angle is measured w.r.t. x axis) But this all is only theoretical basics of first derivative operators of edge. Practically these can nat be implemented on image. For that purpose, we have different types of masks. 2 | 2 | z % | % | 2 z, |Z) |Lza Roberts 1/211 }l-1/0]4 Sobel Fig.9.5° Di ices 89-5 Different matrices operators used for calculation of first derivative.Feature Extraction and Image Segmentation 147 (a) roberts Cross-gradient operators : Here we ha: shows the pixel values. One of the simplest wa tive at point Zs is to use the following roberts c1 = (29-25) = s—Z6) But this is only 2x 2 size mask. This is alw, masks do not have clear center. ve drawn 3x3 area for image where 2;,.. ys to implement the first-order partial de ross-gradient operators : and (9.8) ‘ays avoided, to use this size mask because these Prewitt Operator: Prewitt operator is performed using 3x3 mask. In this mask, the derivative inx direction is calculated by difference between first and third row of 3x3 mask. Gy= (27+ 25 +26) —(2) +2 + 25) (9.9) Similarly the derivative in y direction is calculated by the difference between first and third columns of mask. Gy = (23 + 26 + 25) —(z +24 +27) ++ (9.10) (Sobel Operator: Sobel operators a slightly modified version of prewitt operatorand given by Gy = (& + 2zg + 25) — (1 +22, +25) (9.11) ml Gy = (25 + 225 + 29) —(z +224 +2) (9.12) here we have doubled center coefficient of mask for giving more importance for center point. Thus, the calculating G, and G,, we can apply meg (V/)= [Gi + ely eT eaipaien| = (9.13) That also provide good result of our interest. 9.6.3.4 The Second Derivative (The Laplacian) Second derivative is also called Laplacian and defined by ORC iE (9.14) V' f= a * ay For3x 3 region, for isotropic rotation increment of 45°, itis given by V? f= 42s — (2 + 24+ 26 +28) Ce and-can be calculated by 3 x3 mask given below : 0]-1[ 0 =i 4]-1 of-1| 0 Fig. 9.6 (a) Implementation of equation. For ‘sotropic rotational increment of 90°, itis given by + (9.16) V? f= 8z5- (1 + 2 +23 + 24+ 2% +27 +25) “nd can be calculated by 3x3 mask given below448 Digital Image Processing =yete1 -1 8] -1 18 nee Fig. 9.6 (b) Implementation of equation. | But “Laplacian functions (second derivative) are not used in its real form because it has the following disadvantage: (a) More sensitive to noise () Itwill provide double edges. So confusing some time for edge detection. (0) Itwill not give the direction of edges. But itis still useful due to the following advantages : (@) todetect zero crossing means center of edge. () to know what pixels are at black side area and what pixel are at white side area. So we use Laplacian along with other smoothing functions to reduce the noise. General Laplacian is used with gaussian function that is given by h(= ON) where P= x+y ando = Deviation Now to calculate Laplacian : 26 0-18) Wh (r) = This equation (2) is referred as Laplacian of a Gaussian (LOG) Now wean draw the original LOG diagram and its cross-section. vA /\ (@ (Real) image of LOG () (Cross section) Fig.9.7. LOG Itloops like Mexican hat thats why is also called Mexican hat function. We can also find the canalso find the mask that will approximately represent the LOG function.Feature Extraction and Image Segmentation 149 0} -1 0 0 ee ei a a ce ee = S251 0 @ || =i 0 5x5 Fig. 9.8 Implementation of LOG. Ithas ‘+ ve’ high vlue at center and after that decreasing and at long distance ‘0’ to get response Convolution of Image with LOG = Convolution of image with Gaussian function and then calculating second derivative. Thus, we have conclusion, that (2) Due to Gaussian function, the smoothing function is there, that will reduce noise. o-crossing function that will help to establish the location of (b) By Laplacian function, we get zer' edge. Edge detection is alsoa low-level feature extraction.Feature Extraction and Image Segmentation 155 98 THRESHOLDING pe Thresholding plays a very important role in segmentation. Thats why we will consider thresholding here in detail. Basically thresholding may be defined as : 1. Single level thresholding and 2. Multilevel thresholding. 1. Single level thresholding : Suppose that an image (x, y) has light objects on a dark background. Ifwe draw the histogram of this type of image, it will have two dominant modes of gray levels. One group near the zero point of histogram showing dark background and one group near the maximum point of histogram showing light object. it 9.12 Single Level Thresholding. Soatany point (x, y). If f(x,y) > T itis called object and f(x,y) Ta The point (x,y) is belongin “heround if f(x,y) <7, Wecan say that thresholding itself a fundamental of segmentation.156 Digital Image Processing 9.8.1 Types of Thresholding So based on above discussion and practical analysis ; it is found that thresholding is a test function 1. Spatial co-ordinates (x, y) 2. f(x,y) gray level of point (x, ¥) 3. P (x,y); some local property at point (x, y). So it can be written as Th= Tix f(xy), P&M) +0 (9.24) 0 the basis of this function thresholding may be categorized as follows : (@ Global thresholding : If thresholding (Th) depends upon only the gray levels of an image. If thresholding (Tk) depends upon the gray levels of image and some (®) Local thresholdi local properties also. (0 Adaptive thresholding : When thresholding depends upon gray levels, local properties and spatial co-ordinates (position of pixels) of pixels. This is called dynamic thresholding. Now we will study the basic approaches for finding different type of thresholding, 9.8.1.1 Global Thresholding ‘Aswe know that global thresholding depends upon only gray levels of an image. So, 1. Selectan initial estimate of threshold, T. 2. Segment the image using T. This will produce two groups of pixels : G group consi pixels with gray level values > T and G, group consisting of all pixels with gray le’ Compute the average gray level values |1; and jy for the pixels in regions G, and G.- |. Compute a new threshold value sting ofall wvels 0 - if Vf2T andV?¢<0 wheresymbol 0, + and — represent any three distinct gray levels, Tis the threshold and V f(gradient) and V? (Laplacian) are calculated at every point (x, y) SG (9.25) Fora dark subject ona light background, the use of above equation generates (@ Allthe pixels that are not at edge are labeled ‘0’. (® All the pixels that are at the dark side of edge are labeled ‘+’. (9 Allthe pixels that are at the light side of edge are labeled ~’. The symbol ‘+’ and’ are reversed for light object on dark background 9.9 REGION BASED SEGMENTATION “Another way of extracting information from an image is to group pixels together into regions of similarities. Thus point, line and edge detection were based on discontinuities in an image on the other hand region based segmentation is based on basis of similarities” Ina 2D-image, we group pixels together according to the rate of change of their intensity over a region. For 3D-image, we group together pixels according to the rate of change of depth in image, corresponding to pixels laying on the same surface such as plane, cylinder, sphere etc. There are basically two main approaches to region based segmentation 1. Region splitting and merging ; and 2. Region growing. Now we will study these two techniques in detail one by one. 9.9.1 Region Splitting and Merging The basic idea of image splitting to break the image into a set of disjoint regions which are coherent Within themselves. The process can be defined as follows : 1. Initially take the image as a whole to be the area of interest. oe 2. Look at area of interest and decide if all pixels contained in the region satisfy some similarity constraint. 3. If TRUE’ then the area of interest corresponds to a region of image. 4, IfFALSE’ then the area of interest is splitted into subareas (usually into four equal sub-areas) and now consider each of subareas as the area of interest in turn. 5. This process is continuously performed until no further splitting is possible. In the worst case the areas may be of just one pixel size. uy J158 Digital Image Processing Thisis also called divide and conquer ‘or’ top down method. One thing should be handled carefully, if only a splitting sche tation would probably contain many neighbouring regions that h ties. Thus, a merging process is used after each split which compares them ifnecessary. That's why itis called split and merging algorithm. of these methods. Let us consider an imaginary image. dule is used then the final segmen- ave identical ‘or’ similar proper- adjacent regions and merges To illustrate the basic principle 1. Let I denotes the whole image as shown in Fig. 9-14(@) a) Fig. 9.14(@)_ Test image. Suppose that all the pixels in [are not similar so we have to split the region Tin four subre- gions. i q i I, [hs Fig. 9.14(b) I" splitting into subdivision. hand I; respectively are similar but those in I, are not, 3. Assume thatall pixels within region h, So, I, is splitted again in four subregions. Ta 1, | we * [ts Ta Fig. 9.14(c) Further subdivisions. 4. Suppose that after splitting, we found that Ijs and I,, are found to be identical so we have to merge them again. Fig. 9.140) Merging of l,; and Lys We can also show all the splitting process by a tree as given below : Ma De Ns Fig. 9.14(¢) Quadiree of splitting and merging. Itis also called quadtree. 9.9.2 Region Growing Region growing approach is the opposite of the split and Bearer lit and merge approach. The process can beFe A eature Extraction and Image Segmentation 159 Start by choosing an arbitrary seed pixel and compare it with neighbo els. x 8 P mpare it wi | ring pixel: 4 Seed Q Joint =o Be Y { Direction of growth » Fig. 9.15(a) I" stop of region growing. Re y ‘ i gion is grown from seed pixel by adding in neighbouring pixels that are similar, increasing the size of the region. | __- Grown pixel ate Fig. 9.15(b) Further process of region growing. er seed pixel which doesnot yet 3. e: When the growth of one region stops we simply choose anoth' Ba to any region and start again. is is revised until all possible regions are found. This is called bottom up. Tl “ene he main disadvantages of this technique are : 1. Current region dominates the growth process. segmentation results. 2. Different choice of seeds may give different d point lies on the edge. 3. Problem can secure if arbitrary choosen see we use ‘simultaneous region growing technique + To temove these disadvantages, 1. Similariti re; ions are also considered. ities between reg) ionsare grown. 2. Atatimea single region isnot allowed to finalized. A number ofparallel region 3. Process is difficult but many algorithms are available for easy implementatio 7