An efficient edge detection approach in image processing

Autor: A. A. Frolov, S. N. Primechaev <froloa1(at)feld.cvut.cz>, Pracoviště: České vysoké učení technické v Praze, FEL, Téma: Digitální zpracování signálu, Vydáno dne: 08. 11. 2006

Methods for the separation of contours in the image area are presented. The contour separation is useful in the segmentation-based tasks. For the real time image and video processing, simple and fast methods are important. In our paper we propose a novel real time capable method for the contour separation which is based on the thresholding and filtering. The results of experiments are included.



In the object recognition tasks the image segmentation represents an important operation. For the classification of the objects in the image area, the determination of their contours is essential. The procedure of image contour separation is intended for the fast reduction of image data volume and simplification of the consecutive algorithms of recognition. In our paper we are focused on simple and fast algorithms useful for the real-time spatial selection and segmentation. The edge-based segmentation methods are intended for the finding of the edges of objects in the image area. There are numerous edge operators available. Present gradient operators as a measure of edge sheerness can be divided into three categories:

  1. operators approximating the derivatives of the image function using finite differences (e.g. Roberts, Prewitt, Sobel, Laplace, Robinson, Kirsh, Compass edge operators),
  2. operators based on the zero crossings of the second derivatives of the image function (e.g. Marr-Hildreth or Zero Crossing, Laplacian of Gaussian, Canny edge detector) and
  3. operators which attempt to match an image function to a parametric model of edges (parametric operators).

It may be difficult to select and realize the optimal edge detection strategy.

Methods for image segmentation

a) The simple thresholding procedures

Principal edge detection procedures include convolution matrices of the edge operators, Hough transform and some other methods for further refinement of the results, e.g. image thresholding, edge relaxation and border tracing [3], [4], [5]. There are many characteristics we might use to segment an image into regions e.g. colour, brightness, texture and edge detection. Usually, the obtained edges need some additional improvement for the satisfactory segmentation. These post-processing techniques have two purposes. The first one is to remove false edges, and the second one is to complete edges which have lost information due to the noise or a weak gradient. Edge relaxation techniques attempt to address both of these problems. One of the main goals in the image pre-processing is to remove the redundant information as much as possible using simple and high-speed methods. The transition from the input image to its binary counterpart is often done by the thresholding procedures. However, part of the useful information is always lost. The simple static thresholding [1] is expressed as

 
img_process_1
(1)

where B(i, j) is the brightness of an element with coordinates i, j and T is the threshold value. The maximal speed is obtained using the constant threshold. Usually, we have to deal with the non-constant object illumination. The variation in the object illumination can be compensated to some extent by the adaptation of the threshold value T

 
img_process_2
(2)

where the factor k considers the object illumination and T(k) is the threshold value which is chosen from the histogram. As a rule we get more satisfying results. However, the speed of the processing decreases. Good results can be obtained with the method [1] using the comparison the difference of brightness of two neighboring elements.

 
img_process_3
(3)

where the threshold Tmax defines the limit of an interval of admission. This method does not react to changing of brightness within the limits of a hysteresis. But it is inferior to the method with a constant threshold in terms of speed.

b) The common operators

The family of different filters concerns with detecting of gradients in a number of directions. The filters are convolved with the image to produce a number of filtered images which are combined in order to provide the final edge image. Often, the convolution operators are defined as 2x2, 3x3 or 5x5 matrices. The simplest and earliest of these filters is the Roberts operator [4]. It gains in execution speed and loses in fidelity because of its small support of 2x2 neighborhood elements. Consequently it is very sensitive to the noise. The Prewitt operator [4], [5] is defined by eight convolution masks of 3x3 coefficients corresponding to the image orientation in the eight compass directions. It is possible to extend the mask beyond 3x3 coefficients, but it reduces the fidelity of the final edge image and increases the computation time. The Prewitt operator, similarly to the Sobel, Kirsch, Robinson (as discussed later) and some other operators, approximates the first derivative. The Sobel operator consists of three filters, defined as h1, h2, h3 [4]. Normally, only h1 and h3 can be interpreted as finding horizontal and vertical gradients respectively. The Sobel operator is often used as a simple detector of horizontal and vertical edges. In this case only masks h1 and h3 are used. The Laplace operator [4], [5] is used to calculate the second derivative of the image. It is defined either for the 4- or for the 8-neighbourhood. A linear differential operator is called the Laplacian. The Laplace operator has the same properties in all directions and is therefore invariant to the rotation. The Laplace operator is a very popular operator approximating the second derivative which gives the gradient magnitude only. Compass Edge Detection [8] is an alternative approach to the differential gradient edge detection (see the Roberts Cross and Sobel operators). The operation of this detection usually produces two images. The first one estimates the local edge gradient magnitude while the second one estimates the edge orientation of the input image. This family of filters performs clear and straight edges. However, these methods tend to introduce a lot of noise to the edge image. The Zero Crossing detector [7] looks for values in the Laplacian of Gaussian of an image crossing the level, i.e. points where the Laplacian changes its sign. Such points often occur at edges in images but they also occur at places which are difficult to associate with edges. Zero crossings always lie on closed contours so the output of the zero crossing detectors is usually a binary image with single pixel thickness lines showing the positions of the zero crossing points. Excellent edge detection is obtained by the Canny edge operator [6] with derivative of Gaussian. In this case we can use different values of the parameter σ (Gaussian kernel size) for the detecting of edges with different precision.

The last category of filters is called parametric. Parametric models [3] describe edges more precisely than simple edge magnitude and direction. They are much more computationally intensive and additionally, they carry the potential for sub-pixel edge localization. Parametric models are based on the idea that the discrete image intensity function can be considered as a sampled noisy approximation of the underlying continuous or piecewise continuous image intensity function. Piecewise continuous functions are called facet models. The simplest of the flat facet models which uses piecewise constants and each pixel neighborhood is represented by a flat function of constant intensity. They may have simple or complicated modifications, e.g. the sloped model, quadratic, bi-cubic facet models etc.

c) Anisotropic filtering and real time contour separation

We have got good results using anisotropic filtering [2] of the input image which decreases the influence of the separate (pulse-like) spots and blanks not related to the silhouette of the object. The anisotropic 2-D FIR filters can be designed using frequency transformations [9]-[12]. The anisotropic filtering is effective in the processing of the images degraded by the additive normal noise. It is given by the formula

 
img_process_4
(4)

where a (i, j) is the element of a matrix of the filtered image, b (i+n, j+x) is the element of a matrix of the image degraded by the additive noise, A (<n,x) is the element of the aperture representing a matrix with size Na x Na (Na, as a rule, is odd number), h is the threshold of a filtering and L is the threshold function

 
img_process_5
(5)

For filtering of all pixels of the input image of the size N x N it is necessary to complete the input image by zero elements (zero-padding) resulting in the extended input image of the size [N+ (Na-1)/2] x [N+ (Na-1)/2]. The essence of the anisotropic filtering is that the brightness of the central element of an image segment of the size 3x3 is given by the cumulative brightness of the neighboring elements. If the number of pixels with individual brightness of a mask from 9 elements is more 5 then brightness of the central element accepts value "1". Otherwise it accepts value "0". The filtered image is formed in additional buffer memory. The efficiency of the filtering can be improved using the recursive filtering [2]. Initial elements and also elements of already filtered image participate in this filtering. Elements of the filtered image replace corresponding elements of initial image directly in the working buffer. Thus the memory requirements decrease twice and the speed rises. We have elaborated own simple and extremely fast method for the edge contour separation. The essence of the method consists in the calculation of the difference between the thresholded binary image and the same image diagonally displaced by one element, e.g. to the left and upwards given as

 
img_process_6
(6)

This method gives a thin continuous contour line of objects with the thickness of one element. The dealing with the brightness of the background and of the object is automatically eliminated.

Results of experiments

We have verified the efficiency of the above mentioned methods. One of the experiments is presented in Fig. 1 and Fig. 2.

 
imp_process_7
 
imp_process_8
 
 
a)
 
b)
 
Fig.1. The input grayscale image of an object (a) and this image after simple thresholding (b)
 
 
imp_process_9
 
imp_process_10
 
 
a)
 
b)
 
Fig.2. The anisotropic filtering of the image (a) and contour separation of the objects (b)

Conclusions

A novel method for the real-time contour separation was introduced. It provides continuous contours of the thickness 1-2 elements. One example demonstrated the efficiency of the method.

Acknowledgement

This work has been supported by the grant No.102/05/2054 “Qualitative Aspects of Audiovisual Information Processing in Multimedia Systems” of the Grant Agency of the Czech Republic.

References

[1] V. Borisenko, A. Znatopolskiy, I. Muchnik, Segmentation of images, Automatics and telemechanics. 1987
[2] J. Zubarev, J. Sagdullaev, Spectral selection of optical images. The FAN, 1987
[3] R. M. Haralic and L. G. Shapiro, Computer and Robot Vision, 1992
[4] R. Fisher, S. Perkins, A. Walker, E. Wolfart, Image Processing, Edinburgh 2004
[5] Ming Jiang, Digital image processing, Peking 2003
[6] J. Canny, A Computational Approach to Edge Detection, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 8, No. 6, Nov 1986.
[7] D. Marr, Vision, Freeman, 1982, pp 54-78.
[8] E. Davies, Machine Vision: Theory, Algorithms and Practicalities, Academic Press, 1990, pp 101-110.
[9] P. Zahradník, M. Vlček, Frequency Transformations in Two-Dimensional Digital FIR Filter Design, Proc. of the The 11th European Conference on Circuit Theory and Design ECCTD'93, Davos, 1993, pp. 379-384.
[10] P. Zahradník, R. Unbehauen, Frequency Shift of Two-dimensional Real Coefficient Zero Phase FIR Digital Filters, Proceedings of The IEEE International Symposium on Circuits and Systems ISCAS'95, Seattle, May 1995, pp. 331-334.
[11] P. Zahradník, R. Unbehauen, Frequency Shift of Two-dimensional Real Coefficient FIR Digital Filters for Image Processing Applications, Proceedings of The European Conference on Circuit Theory and Design ECCTD'95. Istanbul, August 1995, pp. 765-768.
[12] P. Zahradník, M. Vlček, B. Šimák, Analytical Design of Maximally Flat Notch FIR Filters for Communication Purposes. 4th International Conference on Networking ICN2005. Reunion Island, April 2005, pp. 392-400.