
vdrf(1)                      Khoros                       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 pat-
     tern 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 opera-
     tors are sensitive to noise, a preprocessing such as smooth-
     ing 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 infin-
     itely 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 Recur-
     sive 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 Direc-
     tional 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 fol-
     lows

     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 con-
          tour lies above a low threshold T1, and at least one of
          part of which is above a high threshold T2, that con-
          tour 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 pro-
     posed, for example, Gaussien filter, Canny filter, exponen-
     tial 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 exponen-
          tial 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 algo-
          rithms 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 imple-
     mented 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 detec-
     tion 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 Digi-
     tized 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 Tran-
     saction 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 gra-
            dient
            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.

Khoros                    Release: 1.0                          1

