vdrf(1)

PROGRAM
vdrf - Optimal filter for Edge Detection.

SYNTAX

vdrf

-i  input image

-o  output image

[-a1]
    Filter Parameter DRF

[-a2]
    Filter Parameter DRF

[-w]
    Window size for calculating the adaptative gradient

[-t1]
    1st Hysteresis Threshold

[-t2]
    2nd Hysteresis Threshold

[-l]
    Minimum Pixel Number in a Segment

[-V]
    Gives the version for vdrf

[-U]
    Gives the usage for vdrf

[-P]
    Prompts for command line options

[-A [file1]]
    Creates the answer file called vdrf.ans or file1

[-a [file1]]
    Uses vdrf.ans or file1 as the answer file

DESCRIPTION

This Algorithm has been writen by the team of:

    Professor SERGE CASTAN

    IRIT, URA 1399

    118, route de Narbonne 31062 Toulouse FRANCE

OPTIMAL FILTER(ISEF) FOR EDGE DETECTION

PRINCIPLE :

I. Introduction

Edge detection is one of the most important subjects in image processing, which finds wide applications in the pattern recognition, the scene analysis and the 3-D vision, because the edges correspond in general to the important changes of physical or geometrical properties of objects in the scene and they are widely used as primitives in pattern recognition, image matching etc.

The edges coincide, generally speaking, with grey level transition, so they can be detected by maxima of gradient or the zero-crossing of the second derivatives calculated by some differential operators. Because the differential operators are sensitive to noise, a preprocessing such as smoothing is often necessary to eliminate the noise.

One well-known smoothing filter is the Gaussian filter and therefore the edges can be detected by a Laplacien-Gaussian filter. But there is an essential difficulty of the Laplacien-Gaussian filter which is the contradiction between the smoothing effect and the precision of edge localization. To overcome this difficulty, We proposed the optimal linear filter based on one step model (a step edge and the white noise) and the multi-edge model [9][10][11]. This optimal smoothing filter is a symmetric exponential filter of infinitely large window size and can be realized by a very simple recursive algorithm.

It is proved that the band limited Laplacien of an input image filtered by this filter can be computed from the Difference between the input and the output of this Recursive Filter (DRF). The edges detected by DRF method are less noisy and with a much better precision of localization.

II. The Difference Operators for Symmetric Exponential Filter

A normalized symmetric exponential filter on 1-D can be written :

fL(x)=C*a0*(1-a0)**|x|=f1(x)#f2(x)=C*(f1(x)+f2(x)-a0*d(x)) (1)

where:

f1(x) = {0 if x<0 and a0*(1-a0)**x if x >= 0 (2)

f2(x) = {0 if x>0 and a0*(1-a0)**-x if x <= 0 (2)

Because the exponential fonction is separable, we can write out 2-D exponential filter:

f(x,y) = fL(x)*fL(y) (5)

III. The Recursive Algorithm for realizing the These Directional Derivative Operators of Symmetric Exponential Filter

The exponential filter is an IIR filter corresponding to an infinite window size, so we should realize the fonctions f1(x) and f2(x) (see formula (2)) by a recursive algorithm.

Supposing I(x,y) is the input image, I1(x,y)=I(x,y)#f1(x) and I2(x,y)=I(x,y)#f2(x), we have the recursive algorithm :

I1(x,y) = I1(x-1,y) + a0*(I(x,y) - I1(x-1,y)) (10)

I2(x,y) = I2(x+1,y) + a0*(I(x,y) - I2(x+1,y))

From the equations (1),(6),(7),(8) and (9), the band-limited first and second directional derivative of input image can be calculated by the recursive algorithm f1 and f2 as follows

IV. Edges Detection

The band-limited Laplacien of an input image filtered by this filter can be calculated from the Difference between the input and the output of this Recursive Filter (DRF).

    1. Edges from the maxima of Difference

    The Difference magnitude image is then non maxima suppressed in the gradient direction and thresholded with hysterisis, i.e. if the entire segment of the contour lies above a low threshold T1, and at least one of part of which is above a high threshold T2, that contour is output. The non maxima suppression scheme requires three points, one of which will be the current point, and the other two should be estimated of the gradient magnitude at points displaced from the current point by vector normal to the edge direction.

V. Comparison of Performance of the Filters

Filtering is a problem of estimation from noisy signal, and edge detection is a problem of estimating the position of maximal local signal change. Up to now, many works are done for edges detection in image, and different filters are proposed, for example, Gaussien filter, Canny filter, exponential filter, Deriche filter etc...

We appreciate the performance of the filters as follows :

    (1) Precision of edge localization

    According to our analysis [10], we can calculate the average localization error xe for Gaussian filter, Canny filter [15], Deriche filter [16] and the exponential filter :

    xeG = (4*(2*e*3.14)**0.5)/a

    xec = 0.81/a

    xeD = 4*exp(-1)/a = 1.47/ a

    xeE = 0

    i.e. xeG > xeD > xec > xeE = 0.

    So, we can see that the exponential filter localizes edge points with the best precision.

    (2) Signal/Noise ratio on the edge point detected

    Because xe is the average estimation for the position of the edge point detected, we propose to calculate Signal/Noise ratio (Eq.(7)) at the point xe.

And the signal/noise ratio for the Gaussien filter, Canny filter, Deriche filter and the exponential filter is :

    SNRG = 2*s*exp(-32*s)/ ((3.14)**0.5)

    SNRc = 0.39/ a

    SNRD = 0.64/ a

    SNRE =1/ a

    i.e. SNRE > SNRD > SNRc > SNRG.

Then, we see that the exponential filter has the best noise eliminating effect among the above four.

    (3) Complexity of calculation

    For the complexity of calculation, we only tell the difference from exponential filter and Deriche filter [16], because they are implemented by recursive algorithms which have a simpler calculation.

Because ISEF can be realized by first order recursive filter, the ISEF algorithms are much simpler than that of Deriche filter. Besides, the ISEF algorithms can be implemented independently to every line and every column, it can be easily realized by a parallel system.

According to the analysis results above, the ISEF filter is superior to the others at the 3 principal aspects of the performance of the filter.

VI. Conclusion

The symmetric exponential filter of an infinite large window size is an optimal linear filter deduced from one step edge model and the multi-edge model, now we further prove that the symmetric exponential filter is the optimal edge detection filter in the criteria of the signal to noise ratio, the localization precision and unique maximum. Obviously, the real images will be still more complicated than these models, however DRF method has already provided good results for different type of images. The results obtained through the two new methods further (ie. SDEF and GEF : vsdef and vgef ) show the superior performance of this filter. The theoretical analysis for the performance of the filters shows also that the exponential filter is superior to the other current filters.

References

[1] W.K. PRATT, Digital Image Processing, New York, 1978.

[2] J. PREWITT, Object Enhancement and Extraction,Picture Processing and Psychopictories, Etd. by B. Lipkin and A. Rosenfeld, New York, pp.75-149, 1970.

[3] M. HUECKEL, An Operator Which Locates Edges in Digitized Pictures. J.A.C.M., Vol. 18, pp 113-125, 1971.

[4] R.O. DUDA and P.E. HART, Pattern Classification and Scene Analysis. Wiley, New York, 1973.

[5] R. HARALICK,Edge and Region Analysis for Digital Image Data. C.G.I.P., Vol. 12, pp 60-73, 1980.

[6] R.HARALICK and L.WATSON, A Facet Model for Image Data. C.G.I.P., Vol. 15, pp 113-129, 1981.

[8] D. MARR and E.C. HILDRETH, Theory of Edge Detection. Proc. R. Soc. Lond. B, Vol. 207, pp 187-217, 1980.

[9] J. SHEN and S. CASTAN, Un nouvel algorithme de detection de contours, proceedings of 5th Conf. on P.R.&.A.I. (in French), Grenoble, 1985.

[10] J. SHEN and S. CASTAN, An Optimal Linear Operator for Edge Detection. Proc. CVPR'86, Miami,1986.

[11] J. SHEN and S. CASTAN, Edge Detection Based on Multi-Edge Models.Proc. SPIE'87, Cannes, 1987.

[12] J. SHEN and S. CASTAN, Further Results on DRF Method for Edge Detection. 9th I.C.P.R., ROME, 1988.

[13] V.TORRE and T.A.POGGIO, On Edge Detection IEEE Transaction on Pattern Analysis and Machine Intelligence, Vol. Pami-8, N 2, March 1986.

[14] J.S.CHEN and G.MEDIONI, Detection, Localization, and Estimation of Edges. IEEE Transaction on Pattern Analysis and Machine Intelligence, Vol. 11, N 2, February 1989.

[15] J.F.CANNY, Finding Edges And Lines in Images. MIT Technical Raport N 720, 1983.

[16] R. DERICHE, Optimal Edge Detection Using Recursive Filtering. In proc. First International Conference on Computer Vision, London, June 8-12 1987.

REQUIRED ARGUMENTS

-i  type: infile
    desc: input image

-o  type: outfile
    desc: output image

OPTIONAL ARGUMENTS

-a1 type: float
    desc: Filter Parameter DRF
    default: 0.3
    bounds: 0.000000 < [-a1] < 1.000000

-a2 type: float
    desc: Filter Parameter DRF
    default: 0.3
    bounds: 0.000000 < [-a2] < 1.000000

-w  type: integer
    desc: Window size for calculating the adaptative gradient
    default: 5
    bounds: 0 < [-w] < 11

-t1 type: integer
    desc: 1st Hysteresis Threshold
    default: 12
    bounds: 0 < [-t1] < 255

-t2 type: integer
    desc: 2nd Hysteresis Threshold
    default: 15
    bounds: 0 < [-t2] < 255

-l  type: integer
    desc: Minimum Pixel Number in a Segment
    default: 10
    bounds: 0 < [-l] < 100000

EXAMPLES
vdrf -i cross.xv -o output.xv

will compute a DRF edge extraction (difference recursive filter) on the image cross.xv and write the result in output.xv.

For the DRF edge extraction the filter parameters values are generally a1 = a2 = 0.3

The size of the window has to be odd and 5 is generally a good value.

The hysteresis Thresholds T1 and T2 can be set to 12 and 15.

SEE ALSO
intro(1), verror(3), vgparms(3), vutils(3), lvdrf(3)

RESTRICTIONS
works only with single band byte images.

COPYRIGHT
Copyright 1991, University of New Mexico. All rights reserved.