
vsdef(1)                     Khoros                      vsdef(1)

PROGRAM
     vsdef - Second Derivative Operator for Symmetric Exponential
     Filter.

SYNTAX
     vsdef

     -i             input image

     -o             output image

     [-a0]          Filter Parameter GEF

     [-t1]          1st Hysteresis Threshold

     [-t2]          2nd Hysteresis Threshold

     [-l]           Minimum Pixel Number in a Segment

     [-V]           Gives the version for vsdef

     [-U]           Gives the usage for vsdef

     [-P]           Prompts for command line options

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

     [-a [file1]]   Uses vsdef.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 the pat-
     tern recognition, the image matching etc.

     The edges coincide, generally speaking, grey level transi-
     tion, 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. A well-known smooth-
     ing filter is Gaussian filter and the edges can therefore 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 sym-
     metric exponential filter of an infinitely large window size
     and can be realized by very simple recursive algorithm. It
     is proved that the band limited Laplacien of an input image
     filtered by this filter can be calculated from the Differ-
     ence 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.

     The maxima of gradient or zeros of the second directional
     derivative along the gradient are a natural definition of
     intensity edges. Zeros of the Laplacian are only extensively
     used for their computational convenience. However, we must
     stress here that the zeros crossing of the Laplacien are not
     always coincided with the maxima of gradient, for example,
     the zeros of the Laplacien are farther apart than the maxima
     of gradient for circularly symmetric patterns, this lack of
     localization by the Laplacien can also be seen in the fact
     that zeros of Laplacien "swing wide" of corners. Therefore,
     it had better to detect the edges bymaxima of gradient or
     zeros of the second directional derivative along the gra-
     dient .

     So we propose two methods for edges detection, one uses max-
     ima of Gradient (GEF), another uses the zeros crossing of
     Second directional Derivative along the gradient (SDEF).

     II. The First and the Second Directional Derivative Opera-
     tors 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:

     C=1/(2-a0), # means the convolution, d(x) is dirac function.

     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)

     we can write the first derivative operator of exponential
     filter:

     fL'(x)=f2(x)-f1(x)         (3)

     And we can obtain the normalized second derivative operator
     of exponential filter :

     fL"(x)=f1(x)+f2(x)-2*d(x)  (4)

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

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

     From the equations (18),(19) and (20),  the first and the
     second directional derivative operators for symmetric
     exponential filter can be written like this:

          fx(x,y) = fL(y)*(f2(x)-f1(x))          (6)

          fy(x,y) = fL(x)*(f2(y)-f1(y))          (7)

          fxx(x,y) = fL(y)*(f1(x)+f2(x)-2*d(x))  (8)

          fyy(x,y) = fL(x)*(f1(y)+f2(y)-2*d(y))  (9)

     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

     Ix(x,y)=I(x,y)#f1(y)#f2(y)#(f2(x)-f1(x))   (11)

     Ixx(x,y)=I(x,y)#f1(y)#f2(y)#(f2(x)+f1(x))-
     2*I(x,y)#f1(y)#f2(y)  (12)

     Iy(x,y) = I(x,y)#f1(x)#f2(x)#(f2(y)-f1(y))
     (13)

     Iyy(x,y) = I(x,y)#f1(x)#f2(x)#(f2(y)+f1(y))-
     2*I(x,y)#f1(x)#f2(x)  (14)

     With this algorithm, we can calculate at the same time the
     band-limited first and second directional derivative Ix and
     Ixx ( or Iy and Iyy ) of input image.

     IV. Edges Detection

     The band-limited first and second directional derivative of
     input image can be obtained by the algorithms as stated
     above. Using them, we can then realize the edge detection
     for an image.

     The maxima of gradient or zeros of the second directional
     derivative along the gradient are a natural way of charac-
     terizing and localizing intensity edges,  so we present here
     to detect the edges from the maxima of gradient or zeros of
     the second directional derivative along the gradient by
     using the differential operators of exponential filter.

          1. Edges from the maxima of gradient

          Using the first directional derivative operator of the
          exponential filter, the two band-limited first direc-
          tional derivatives Ix and Iy can be calculated, and the
          gradient vector can be therefore determined approxima-
          tively for every point in image. The gradient 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 thres-
          hold T1, and at least one of part of which is above a
          high threshold T2, that contour is output. The non max-
          ima 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.

          2. Edges from the zero-crossings of the second direc-
          tional derivative along the gradient direction

          Because edges detected from local gradient maxima can
          not be a pixel width (less good precision of localiza-
          tion), we propose an other method which detect the
          edges from the zeros crossing of the second directional
          derivative along the gradient direction.

     We can calculate Ix,Iy,Ixx and Iyy by using the method shown
     in paragraph III, and therefore obtain approximatively the
     gradient vector and the second derivative in the gradient
     direction for every point in image. We extract at first the
     zero crossing of second derivative along the gradient direc-
     tion on which the gradient magnitude must be above a low
     threshold, so an edges image is obtained. To this image, the
     entire segment of the contour will be kept, if the gradient
     magnitude on at least one part of this contour is above a
     high threshold.

     V. Comparision 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 show the superior performance of
     this filter. The theoretical analysis for the performance of
     the filters shows also that the exponential filter is supe-
     rior to the other current filters.

     The first and second directional derivative operators can be
     realized by recursive algorithm and calculated at the same
     time. The new algorithms are therefore very simple as well
     as DRF algorithm, and they are also easy to implemente in a
     parallel way.

     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 Transac-
     tion 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 Com-
     puter Vision, London, June 8-12 1987.

REQUIRED ARGUMENTS
     -i     type: infile
            desc: input image

     -o     type: outfile
            desc: output image

OPTIONAL ARGUMENTS
     -a0    type: float
            desc: Filter Parameter GEF
            default: 0.45
            bounds: 0.000000 < [-a0] < 1.000000

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

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

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

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

     will compute a edge extraction by using the first direc-
     tional derivative operator for symmetric exponential filter
     on image cross.xv and write the result in output.xv

     For the SDEF edge extraction the filter parameter value is
     generally a0 between 0.40 and 0.9 (0.45  [default] is a good
     value)

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

     The minimum Length of segment is up to the user. It is set
     by default to 10.

     -man1_long_description_end

     -man1_examples vsdef -i cross.xv -o output.xv

     will compute an edge extraction by using the second direc-
     tional derivative operator for symmetric exponential filter
     on image cross.xv and write the result in output.xv

     For the SDEF edge extraction the filter parameter value is
     generally a0 between 0.40 and 0.9 (0.45  [default] is a good
     value)

     The hysteresis Thresholds T1 and T2 can be set to 3 and 4.
     (12 and 15 seem to be a set of good values as well, it
     depend on the level of noise in the image.)

     The minimum Length of segment is up to the user. It is set
     by default to 10.

SEE ALSO
     intro(1), verror(3), vgparms(3), vutils(3), lvsdef(3)
     vdrf(1), lvdrf(3), vgef(1), lvgef(3).

RESTRICTIONS
     works only with single band byte images.

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

Khoros                    Release: 1.0                          1

