A Better First- Derivative Approach for EDGE Detection

A Better First- Derivative Approach for EDGE Detection

Sujoy Kumar Goswami

Senior Engineer, iGATE Global Solutions Ltd., Pune, Maharashtra

Partha Ghosh

Asst. Professor, Govt. College of Engg. & Ceramic Technology, Kolkata, West Bengal

Abstract

This paper shows a better approach (first derivative) for edge detection than the other commonly used first- derivative methods (like Roberts operator, Prewitt operator, Sobel operator etc.).

1. Introduction

   In gray scale image, the edge is a local feature that, within a neighbourhood, separates two regions in each of which the gray level is more or less uniform with different values on the two sides of the edge. So, an ideal edge has a step like cross-section as shown in Fig. 1(a).

   Fig. 1(b) exemplifies the cross section of a more realistic edge which has a shape of ramp function corrupted with noise.

   Fig. 1(a) Fig. 1(b)

   In derivative approach, edge pixels are detected by taking derivative (e.g. Roberts operator, 4-neighbor operator) followed by Thresholding. They occasionally incorporate noise-cleaning scheme (e.g. Prewitt operator, Sobel operator). The backbone of derivative approach is the discrete approximation of derivative operation.

2. Theory and Methods

   Consider the following gray level values around the centre candidate pixel at (r, c) with gray level value g:

   	A1	A2	A2
   C1	A4	A5	A6	D1
   C2	F	G	H	D2
   C3	B1	B2	B3	D3
   	B4	B5	B6

   The 4-Neighbor operator [1] approximates the actual edge strength at (r, c) as,

   dr = b2 – a5, dc = h – f;

   The magnitude of gradient at (r, c) is then given by g =

   [(dr2 + dc2)/2].

   However this method is very sensitive to noise & hence other operators like Prewitt operator, Sobel operator etc. are used more frequently which have averaging nature.

   To minimize the noise effect on the edge-image & to get a proper Threshold for final edge image, the edge strengths at (r, c) can be defined as [method-1],

   dr = [average gray level over the (3×3) neighbourhood at (r+1, c)] [average gray level over the (3×3) neighbourhood at (r-1, c)],

   dr = (1/9)[bi ai];

   Where, defines summation over i.

   Similarly, dc = [average gray level over the (3×3) neighbourhood at (r, c+1)] [average gray level over the (3×3) neighbourhood at (r, c-1)],

   dc = (1/9)[ a6 + h + b3 + di (a4 + f + b1 +

   ci)];

   The corresponding masks are given by,

   0	-1	-1	-1	0
   0	-1	-1	-1	0
   0	0	_	0	0
   0	1	1	1	0
   0	1	1	1	0

   0	0	0	0	0
   -1	-1	0	1	1
   -1	-1	_	1	1
   -1	-1	0	1	1
   0	0	0	0	0

   0	0	0	0	0
   0	-1	0	1	0
   -1	-1	_	1	1
   0	-1	0	1	0
   0	0	0	0	0

   0	0	0	0	0
   0	-1	0	1	0
   -1	-1	_	1	1
   0	-1	0	1	0
   0	0	0	0	0

   Among all the methods discussed in this paper, the above one is least sensitive to noise because of its robust averaging nature.

   Now it will be shown that this mask size is optimum. If it is tried to find dr by taking averages over (5×5) neighbourhood at (r+1, c) & (r-1, c) respectively, then the equivalent horizontal mask will be as follow:

   0	-1	-1	-1	-1	-1	0
   0	-1	-1	-1	-1	-1	0
   0	0	0	0	0	0	0
   0	0	0	_	0	0	0
   0	0	0	0	0	0	0
   0	1	1	1	1	1	0
   0	1	1	1	1	1	0

   It can be seen from the above equivalent mask that the candidate pixel at (r, c) gets no edge information (horizontal) from its immediate neighbours, which is not desired, as maximum edge information is stored in immediate neighbours. Hence the method-1 mask is optimum for the proposed approach.

   Average can also be computed on 4-neighbor basis [method-2]; the corresponding masks are given by,

   0	0	-1	0	0
   0	-1	-1	-1	0
   0	0	_	0	0
   0	1	1	1	0
   0	0	1	0	0

3. Experiments and Results

   A synthetic test image is taken & salt & pepper noise is added. Original gradient image (X) & noisy gradient images (Y) are found for all the operators. From these the gradient images for noise (X-Y) are found & corresponding standard deviations & mean square measures are calculated (following table is to be referred for different types of operators & different measures of noise).

   Table 1(a): Mean Square Noise measure

   Operator	Mean Square NoiseEstimation (1% noise)	Mean Square Noise Estimation (10% noise)
   Roberts	617.43	6001
   4- neighbour	613.75	5907
   Prewitt	200.26	1960
   Sobel	226.61	2208
   Method-1	97.21	962
   Method-2	147.18	1442

   Table 1(b): Standard Deviations of noise

   Operator	Standard Deviation of Gradient noise image (1% noise)	Standard Deviation of Gradient noise image (10% noise)
   Roberts	11.08	6.56
   4- neighbour	9.01	5.73
   Prewitt	5.04	3.29
   Sobel	5.18	3.11
   Method-1	2.46	2.08
   Method-2	3.43	2.23

   The mean square measure is calculated as: [g(r, c)2]/(R*C), where g(r, c) is the pixel value at location (r, c), R is the number of rows in the image & C is the number of columns in the image.

   The following pictures show the results by the proposed methods:

   Fig. 2(a): Original synthetic test image

   Fig. 2(b): Noisy gray level image (1% salt & pepper noise is added)

   Fig. 2(e): Edge image (after Thresholding of noisy gradient image) by method-1

   Fig. 2(c) Result (gradient image) by method-1

   Fig. 2(d) Result (gradient image) by method-2

   Fig. 2(f): Edge image (after Thresholding of noisy gradient image) by method-2

4. Discussion

   Even if here only salt & pepper noise is taken, but the above methods give good results for other types of noises also because of its robust averaging nature. The above two approaches are the most general first derivative edge detection approaches.

5. Conclusions

   From Table 1(a) it is clear that Mean Square Noise is least for method-1 followed by method-2. Hence these are more effective in reducing noise effects.

   From Table 1(b) it is clear that Standard Deviation of noises is least for method-1 followed by method-2. Hence noises are more around their means in these

   methods; which helps to choose a better Threshold for final noise free edge image.

   .

6. References

1. Bhabatosh Chanda & Dwijesh Dutta Majumder, Digital Image Processing and Analysis, Prentice- Hall of India Private Ltd, New Delhi, India,2007, pp. 239- 246.

2. Rafael C. Gonzalez & Richard E. Woods, Digital Image Processing, Pearson Education Asia Private Ltd, Delhi, India, 2002.