Edge Detection by Relative Dispersion Analysis Based Fractal Dimension

Gary L. Buterbaugh Indiana University of Pennsylvania

Soundararajan Ezekiel

Ohio Northern University

Abstract

Edge detection is a problem of fundamental importance in image analysis. Edges are places in the image with strong intensity contrast. In typical images, edges characterize object boundaries and are therefore useful for applications in 3D reconstruction, motion, recognition, image enhancement and restoration, image registration, image compression, and so on. Usually, edge detection requires smoothing and differentiation of the image. Differentiation is an ill-conditioned problem and smoothing results in a loss of information. It is difficult to design a general edge detection algorithm that performs well in many contexts and captures the requirements of subsequent processing stages. The classical edge detection approaches are based on first derivative, second derivative techniques, and surface fitting. In this paper, we present fractal based edge detection method.

1.Introduction

Edges in image can occur on the boundary between two pixels when the respective brightness values between two pixels are significantly different. Most edge detection methods work on the assumption that an edge occurs where there is a discontinuity in the intensity function or a very steep intensity gradient in the image. The main problem one has to deal with in differential edge detection schemes is noise. The spikes in the derivative from the noise can mask the real maxima that indicate edges. If we smooth the image then the effects of noise can be reduced. A maximum of the first derivative will occur at a zero crossing of the second derivative. To get both horizontal and vertical edges we look at second derivatives in both the x and y directions. However, there are some problems with these methods such as influences of noises, false edges, missing edges, and missing corners and junction. The current standard edge detection scheme widely used around the world is the Canny edge detector. This is the work John Canny did for his Masters degree at MIT in 1983. He treated edge detection as a signal-processing problem and aimed to design the `optimal' edge detection. In this paper, we use fractal-based technique to extract edges because it is more reliable than some of the classical methods. This method seems to be well suited for problems involving noises as well as other problems. The paper is organized as follows. In section II the methodology is described. The experimental result is described in section III. Finally, in Section IV we summarize and conclude our work.

2.Methodology

This section briefly explains our methodology. The basic idea is to calculate the local Hurst[3] exponents for an image. The local fractal dimension [2][5] is then derived from the value of the Hurst exponent. A small value of FD (large value of the parameter H) represents a fine texture, while a large FD (small H) corresponds to a coarse texture. Based on this description, we can segment the image and find the edges with a simple thresholding method. Thresholding is the transformation of an input image I to an output binary image BI as follows: where T is the threshold.

We begin with each pixel, calculate the spread of the probability density function at the highest level of resolution, then to lump nearest-neighbor elements together to obtain the local mean of the pair of elements and recalculate the dispersion at the reduced level of resolution. Then the slope value gives the local Hurst [5] exponent at the pixel center of the neighborhood. We use a special neighborhood called Quincunx mask [4]. We continue this procedure for the entire image and form the image, whose pixel intensities are these local Hurst exponents. We call this image the slope image See Figure 1. We now present the one-dimensional algorithm for this procedure.

Algorithm: Step 1. Define the signal. Consider the simple case of a signal measured at even intervals of the independent variable, for example function of positions along a line: . Start with group size m, with m=1. Step 2. Calculate the mean of the whole set of observations, f:

Step 3. Calculate the standard deviation SD of the set of n observations: where the denominator is n, using the sample SD rather than the population SD where n-1 would be used. Calculate the RD for this group size, Step 4. For the second grouping aggregate adjacent samples into groups of two data points and calculate the mean for each group, the SD for the group means and the RD for the group means. Step 5. Repeat Step 4 with increasing group size until the number of group is small. Step 6. Plot the relationship between the number of data points in each group and the observed RDs. That is plot log-log plot. A plot of log of RD(m) versus the log of the number of the data points in each group. Step 7. Calculate fractal dimension FD=1-slope

3.Experimental Result

In this section, we describe two examples to illustrate the concept introduced. Based on the method previously discussed, we estimated the local fractal dimension for each pixel in both images (Lena and Rice) and we formed the slope images respectively. Finally, we apply threshold technique to extract edges from the slope image. Figure 1 shows the original image, slope image and the edges. Figure 2 shows the original image and edge image.

Figure 1: Original Image Slope Image Edges

Figure 2: Original Image Edge Image

4.Discussions

We have presented the approach that uses fractal dimension for classification of edges in the image. This method has potential applications in image analysis such as edge-based segmentation, texture classification. Two examples were shown to demonstrate the use and the advantage of the proposed method. Future work will integrate wavelets and multifractal analysis in this approach.

5.References

[1] A.P Pentland, “Fractal-based description of natural scenes’, IEEE Trans. on Pattern Analysis and Machine Intelligence, 6:661-674, 1984.

[2] B.B. Mandelbrot, “ Fractal Geometry of Nature “, Freeman, New York, 1982,

[3] H E. Hurst.”Long-term storage capacity of reservoirs”. Trans. of ASCE, 116:770-808, 1951

[4] Soundararajan E, Robert A. Hovis. “Texture Based Image Compression by Using Quincunx Mask, IASTED International Conference on Applied Informatics” , Innsbruck, Austria, February 19 - 22, 2001

[5]. J.Feder., Fractals, New York, London Plenum Press, 1989.