Next: harris Up: Reference Previous: align_mdl   Contents   Index

#### canny

Name

canny Canny-Deriche's Edge Detector

Command Synopsis

canny [-a alpha] IN OUT

-a alpha : Width of the impulse response, default 1

IN : input fimage

OUT : output fimage

Function Summary

Fimage canny (alpha , IN , OUT )

float *alpha ;

Fimage IN , OUT ;

Description

This method is an approach of edge extraction preceded by an optimisation of criteria keeping in mind a pre-defined model of the edge to detect. The approach introduced by Deriche consists in a research of the optimal operator of the Canny's filter [Can86] under a infinite impusionnal response filter (RII) [Der87].

Canny's filter :

Considering I(x) a monodimensionnal signal representing a jump of amplitude A, lost in a Gaussian noise n(x) with a null average and variance n02. Let (x0), the output at the point x0 of the convolution of the signal I(x) whit a detection operater f (x):

(x0) = I(x)f (x0 - x) dx

So the issue is to find f (x) where (x0) is maximum under the following constraints:

• Good detection : The probability of not detecting a point of a real edge has to be small, same as the probabilty to detect a point which does not belong to an edge. This criteria leads to find f (x) so as the ratio signal-noise is maximum:

=

• Good localisation : The detected points which belong to an edge, have to be as close as possible of the middle of the real edge. This criteria corresponds to the minimisation of the variance 2 of the zero passages position. It is equivalent to maximize the localisation defined as the inverse of 2:

=

• No multiplicity of responses : This criteria corresponds to the limitation of the number of local maxima detected in reply of an only edge. the average distance between the local maxima, noted down xmax is constraint to the following egality:

xmax = 2

The Canny's method consists in combinig with those three conditions in order to finf f (x) which maximises . under the third constraint that the criteria is fixed to constant k. This leads to find the solution of the following differentail center :

2f (x) - 2f''(x) + 2f''''(x) + = 0

which accepts the general solution :

f (x) = a1exsin(x) + a2excos(x) + a3e-xsin(x) + a4e-xcos(x) + C

Seeking for the operator f (x) under the form of a finite impulsionnal response (RIF) defined on the interval [- W, + W] and having a slope S at the origin, Canny has imposed the following limit conditions:

f (0) = 0   f (W) = 0   f'(0) = S   f'(W) = 0

Those four limit conditions allow us to determine the coefficients a1 to a4. f (x) beeing odd, the solution can be extend for x negative with f (x) = - f (- x).

Deriche's filter :

The Deriche's approach consists in the research of the optimal operator under the form of a RII filter. This approach leads to the same Canny's differential center, but limit conditions are as follow :

f (0) = 0   f (+ ) = 0   f'(0) = S   f'(+ ) = 0

It results as solution the following operator:

f (x) = - c.e-| x|sin(x)

Now we introduce the procedure that summarize the Deriche's operator in two dimensions. We create in the x (resp y) direction a 2D mask resulted from the product of a lined up dectector in x (resp y) with a projection operator parallel to the direction y (resp x). We have a recursive implementation if we choose the smoothing operator f (x). We obtain the following centers:

X(m, n) =

Y(m, n) =

The variables k and c are fixed by the normalization constraint, so we have:

c =

k =

In the realization of a RII filter, the size of both masks X(m, n) and Y(m, n) depends of . After the image is convolued with the two masks, we obtain two image r(m, n) and s(m, n). The direction of the edge (m, n) and the amplitude A(m, n) are estimated in fonction of r(m, n) and s(m, n) as follow :

A(m, n) = (r(m, n)2 + s(m, n)2)

(m, n) = arctg

The suppression of the non local maxima of A(m, n) in the exact direction of gradient (m, n) is then realized. So an linear interpolation is made on the gradient. The extaction of local maxima is done in a neighbourhood of 3*3 of the gradient's norm image. The aim is to extract all the pixels coming in the form of a local maxima in the gradient's direction. We use the images coming from the precedent steps in order to obtain an approxiamtion of the gradient's direction.

Version 1.1

Last Modification date : Thu Nov 29 20:23:56 2001

Author

Yann Guyonvarc'h

Next: harris Up: Reference Previous: align_mdl   Contents   Index
mw 2004-05-05