Digital Image Processing PDF

12-04-2024 Digital Image Processing Introduction Image Segmentation Image Segmentation...

12-04-2024 Digital Image Processing Introduction Image Segmentation Image Segmentation Density Based Image Segmentation Similarity Based Image Segmentation Edge Detection Dr. Ram Prakash Sharma Edge Linking NIT Hamirpur Thresholding Reference: R. Gonzalez and R. Woods. Digital Image Processing, Prentice Hall, 2008. RPS 1 RPS 2 1 2 Derivatives Image Segmentation Segmentation divides an image into its constituent regions or objects. Segmentation of images is one of the most important and difficult task in image processing. Still under research. Segmentation allows to extract objects in images. Segmentation is unsupervised learning. RPS 3 RPS 4 3 4 1  12-04-2024  Point Detection  Line Detection 9 Edge Detection R  w1 z1  w2 z 2 ...  w9 z 9   wi z i  i1 RPS 5 RPS 6 5 6  Point Detection  Line Detection  Edge Detection RPS 7 RPS 8 7 8 2  12-04-2024 Line Detection Line Detection Different Line Detection Kernels RPS 9 RPS 10 9 10 Line Detection Apply every masks on the image Let Z1, Z2, Z3, Z4 denotes the response of the horizontal, +45 degree, vertical and - 45 degree masks, respectively. if, at a certain point in the image |Zi| > |Zj|, for all j≠i, that point is said to be more likely associated with a line in the direction of mask i. RPS 11 RPS 12 11 12 3  12-04-2024 Edge Detection  Point Detection  Line Detection  Edge Detection RPS 13 RPS 14 13 14 Edge Detection Edge Detection RPS 15 RPS 16 15 16 4  12-04-2024 Edge Detection Edge Detection Steps for edge detection 1. Image smoothing 2. Detection of edge points 3. Edge localization RPS 17 RPS 18 17 18 Edge Detection Edge Detection Gradient operators  The gradient of an image f(x,y) at location  The direction of the gradient vector also is an (x,y) is defined as the vector important quantity. Let  (x, y) represent the f  direction angle of the vector f at (x,y). Then, G   x  from vector analysis, f   x   f  G  y   y   G y   An important quantity in edge detection is the  (x, y)  tag 1   Gx  magnitude of this vector, denoted f ,where  f  mag(f )  Gx2  G y2  1/ 2 RPS 19 RPS 20 19 20 5  12-04-2024 Edge Detection Edge Detection RPS 21 RPS 22 21 22 Edge Detection Edge Detection  Roberts cross-gradient operators:  An approach using masks of size 3*3 is given by Gx  (z 9  z5 ) G x  (z 7  z8  z9 )  (z1  z 2  z3 ) and  and G y  (z 8  z6 ) G y  (z 3  z 6  z9 )  (z1  z 4  z 7 ) RPS 23 RPS 24 23 24 6  12-04-2024 Edge Detection Edge Detection  A slight variation of these two equations uses  An approach used frequently is to a weight of 2 in the center coefficient: approximate the gradient by absolute values: G x  (z 7  2z8  z9 )  (z1  2z 2  z3 ) f  G x  G y and G y  (z 3  2z 6  z 9 )  (z 1  2z 4  z 7 ) RPS 25 RPS 26 25 26 Edge Detection Edge Detection RPS 27 RPS 28 27 28 7  12-04-2024 Edge Detection Edge Detection RPS 29 RPS 30 29 30 Edge Detection Edge Detection RPS 31 RPS 32 31 32 8  12-04-2024 Edge Detection Edge Detection The Laplacian  The Laplacian of a 2-D function f(x,y) is a second-order derivative defined as 2 f 2 f 2 f   x 2 y 2  For a 3*3 region, one of the two forms encountered most frequently in practice is  2 f  4 z  z  z  z  z  5 2 4 6 8 RPS 33 RPS 34 33 34 Edge Detection Edge Detection  A digital approximation including the diagonal neighbors is given by  2 f  8z  z  z  z  z  z  z  z  z  5 1 2 3 4 6 7 8 9 RPS 35 RPS 36 35 36 9  12-04-2024 Marr Hildreth Edge Detector Marr Hildreth Edge Detector Suggests the operator used for edge detection should have two salient features. It should be differential operator capable of computing 1st or 2nd order derivative at every image point It should be capable of being tuned to any desired scale. 2 2 x  y  ( x , y )   2 2  G e , : s p a c e c o n s ta n t. L a p la c ia n o f G a u s s ia n (L o G )  2 G ( x , y )  2 G ( x , y )  2 G ( x , y )    x 2  y 2   x    y  2 2 2 2 x  y x  y           2 2 2  2  e e  x    y   2 2   2 2 2 2 x  y x  y  x 2 1    y 2 1       2 2 2  2    4  2  e   4  2  e     2 2   x    x y 2  y 2 2   2 2    4  e   RPS 37 RPS 38 37 38 Marr Hildreth Edge Detector Marr Hildreth Edge Detector 1. Filter the input image with an n x n Gaussian lowpass filter. Size of the n should be equal or greater than 6σ Identifying zero crossing points 2. Compute the Laplacian of the image resulting from step 1 1. Use 3 by 3 neighborhood centered at pixel p of the filtered image. 2. P is zero crossing point if signs of two of its opposing neighboring pixels differ. 3. Find the zero crossing of the image from step 2 3. If thresholding is used, then not only the sign but the absolute numerical difference should also exceed the threshold value to consider This operator is based upon a 2nd derivative operator and can be scaled using p as zero crossing point. the parameter  to fit a particular image or application, i.e., small operators for sharp detail and large operators for blurry edges RPS 39 RPS 40 39 40 10  12-04-2024 Marr Hildreth Edge Detector Canny Edge Detector Optimal for step edges corrupted by white noise. The Objective 1. Low error rate All the edges detected must be detected and there should not be any spurious responses. 2. Edge points should be well localized The edges located must be as close as possible to the true edges 3. Single edge point response The number of local maxima around the true edge should be minimum. It should return only one point for each true edge point. RPS 41 RPS 42 41 42 Canny Edge Detector Canny Edge Detector Step 1 – Smooth image Step 2 – Compute Gradient Create a smoothed image from the original one We located the edges using direction of the point using Gaussian function. with the same method as basic edge detection – 𝑥 2 +𝑦 2 gradient: 𝐺(𝑥, 𝑦) = 𝑒− 2𝜎2 𝜕𝑓𝑠 𝜕𝑓𝑠 𝑔𝑥 = 𝑔𝑦 = 𝜕𝑥 𝜕𝑦 𝑔 𝑓𝑠 (𝑥, 𝑦) = 𝐺(𝑥, 𝑦)𝑓(𝑥, 𝑦) 𝑀(𝑥, 𝑦) = √𝑔 2 𝑥 + 𝑔2 𝑦 𝖺 (𝑥, 𝑦) = tan−1 [ 𝑦 ] 𝑔𝑥 RPS 52 43 RPS 53 44 43 44 11  12-04-2024 Canny Edge Detector Canny Edge Detector Step 3 – Nonmaxima suppression Edges generated using gradient typically contain wide ridges around local maxima. We will locate the local maxima using non- maxima suppression method. We will define a number of discrete orientations. For example in a 3x3 region 4 direction can be defined. RPS 54 45 RPS 46 45 46 Canny Edge Detector Canny Edge Detector Step 4 – Double Thresholding Step 3 – Nonmaxima suppression The received image may still contain false edge points. We will now generate a local maxima function We will reduce them using hysteresis (or double) thresholding. Let 𝑇𝐿 , 𝑇𝐻 be low and high thresholds. The suggested ratio is 1:3 or 2:3. We will define 𝑔𝑁𝐻 For each point: (𝑥, 𝑦) and 𝑔𝑁𝐿 (𝑥, 𝑦) to be 𝑔𝑁(𝑥, 𝑦) after threshloding it with 𝑇𝐿 , 𝑇𝐻. 1. Find the direction 𝑑𝑘 that is closest to 𝖺 (𝑥, 𝑦) It is clear that 𝑔𝑁𝐿 (𝑥, 𝑦) contains all the point located in 𝑔𝑁𝐻(𝑥, 𝑦). We will separate them by 2. If the value of 𝑀(𝑥, 𝑦) is less than at least one of two neighbors substruction: along 𝑑𝑘 , 𝑔𝑁(𝑥, 𝑦) = 0 otherwise 𝑔𝑁(𝑥, 𝑦) = 𝑀(𝑥, 𝑦). 𝑔𝑁𝐿 (𝑥, 𝑦) = 𝑔𝑁L(𝑥, 𝑦) − 𝑔𝑁H (𝑥, 𝑦) Now 𝑔𝑁𝐿 (𝑥, 𝑦) and 𝑔𝑁𝐻(𝑥, 𝑦) are the “weak” and the “strong” edge pixels. In the figure in the previous slide we would compare 𝑝5 to 𝑝2 and 𝑝8. RPS 56 47 RPS 57 48 47 48 12  12-04-2024 Canny Edge Detector Canny Edge Detector Step 4 – Double Thresholding The algorithm for building the edges is: 1. The input image is smoothed using a Gaussian filter. 1. Locate the next unvisited pixel 𝑝 in 𝑔𝑁𝐻 (𝑥, 𝑦). 2. The local gradient magnitude and angle for each point in the smoothed image. 2. Mark as valid pixels all the weak pixels in 𝑔𝑁𝐿(𝑥, 𝑦) that are 3. The edge points at the output of step 2 result in wide ridges. The algorithm thins those ridges, connected to 𝑝, using say 8-connectivity leaving only the pixels at the top of each ridge (non-maximal suppression). 3. If not all non-zero pixels in 𝑔𝑁𝐻 (𝑥, 𝑦) have been visited return to step 1. 4. The ridge pixels are then thresholded using two thresholds, Tlow and Thigh: ridge pixels with 4. Set all the non-marked pixels in 𝑔𝑁𝐿(𝑥, 𝑦) to 0. value greater than Thigh are considered strong edge pixels; ridge pixels with values between 5. Return 𝑔𝑁𝐻 (𝑥, 𝑦) + 𝑔𝑁𝐿 (𝑥, 𝑦). Tlow and Thigh are said to be weak pixels. This process is known as hysteresis thresholding. 5. The algorithm performs edge linking, aggregating weak pixels that are 8-connected to the strong pixels. RPS 58 49 RPS 50 49 50 Canny Edge Detector Canny Edge Detector RPS 51 RPS 52 51 52 13  12-04-2024 RPS 53 RPS 54 53 54 RPS 55 55 14