h;,k = 1,..., K, then we denote the response of template 
hi to an image patch g containing the grey values g; by: 
AR > 
Remarks 
(1) The widely used edge and line detection templates en- 
countered in literature fulfil the above defined normalization 
conditions (see, e.g., Nevatia, 1982; Rosenfeld & Kak, 1982; 
Davies, 1990; Pratt, 1991). For example, the eight masks 
of the three level Robinson (1977) operator, are obtained by 
permuting the mask coefficients of Figure 1b cyclically. In 
the same way, cyclical permutation of the mask coefficients 
of Figure 1a yields the eight masks of the Kirsch (1971) op- 
erator. 
(2) Each hypothesized edge direction requires a template. 
The maximum response of all directional templates at a pixel 
defines the edge strength at that pixel. The template pro- 
ducing the largest response defines the edge direction. 
(3) Because of the condition: 5 77 , h; — 0, the three types 
of templates compute derivatives, h can contain both first 
and higher order derivatives. 
(4) The usual mask size is 3 x3 pixels. Larger template masks 
are less sensitive to noise and provide a denser division of the 
edge direction compass-card. However, they require more 
computational effort. Furthermore, when object density is 
high, the response will be often a merged version of two or 
more boundaries. 
Depending on the underlying image and noise model, test 
statistics on the template responses are (Lemmens, 1996): 
maxi | Ran, | 2 Zo0nV/m 
m(n—1) 
K - 
max;=1 |Rgn,| 2 tavög t2 ,+n—2 
maxË_1 | Ron, | > ta /m zZ 
where za is the critical value of the z-score, ta,y the critical 
value of the Student's t-score, with o level of significance and 
v the degrees of freedom. o2 is the variance of the image 
noise, 62 is the variance of the grey values covered by the 
template, and à? and 62 are the variances of the grey values 
at each side of the hypothesized boundary. It is assumed that 
the templates hi, k — 1,..., K are normalized. To obtain 
tests for semi-normalized templates replace the variable m by 
S h?; for fully normalized templates this variable should 
be replaced by 1. 
4.4 Curvature Determination 
The image function may be looked at as a two-dimensional 
curved surface in 3-D space. The structure present in a land- 
scape can be categorized into 8 principle surface types (see 
e.g. Besl & Jain, 1988): (1) plane, (2) peak, (3) pit, (4) 
ridge, (5) valley, (6) saddle ridge, (7) saddle valley, and (8) 
minimal. These eight surfaces are uniquely determined by the 
sign and value of the two principle curvatures. 
It can be shown that the principle curvatures x; and kz of 
g(z,y) can be achieved by solving the quadratic form: x? — 
K(gzz d duy) + gaa gyy — Jay = 0 leading to: 
d 2 
a = Jazz Ha + Em ; us) + gl, 
According to the definition of discrete differentiation, Eq.(1), 
438 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
using the masks [—1 1] and [—1 1]7, we obtain: 
Juz: = 09(2--1,9). — 29(2. y) + 9(z.— 1,9) 
Juy = 9(z,y+1)—29(z,y) +9(z,y—1) 
Joy = g(x+1,y+1) - g(x +1,y) — g(z, y +1) + g(x, y) 
We may also fit through the local image function a sec- 
ond order polynomial (see section 4.2) yielding: gz. = 
204; Guy = 205; ry 7 da, And. Kj z 04 + 05 + M: Ka = 
a4 -- as — D, with D — 4/(a4 — as)? + a2. The parameters 
ao, a1, az, as, as and as can be computed from a least-squares 
adjustment. 
The curvature approach is e.g. used by Dreschler & Nagel 
(1982) for matching of image time sequences. The method 
is sensitive to noise and texture due to the need to compute 
second order derivatives. 
4.5 Final Remarks 
Although the last three approaches (sections 4.2-4.4) model 
explicitly the feature to be traced, they are essentially based 
on differentiation of the local image function. Consequently, 
the desired immunity to non-edge features is not at all war- 
ranted. This yields low performance on images of non- 
restricted scenes, where many other types of features than 
edges may be present and where the image function is much 
more complex than the ideal step edge/Gaussian noise model 
that underlies the design of the majority of the schemes. Fur- 
thermore, the derivation of many operators is done in the 
continuous domain. Next, the filter is sampled, truncated, 
and usually implemented with a small local support, often as 
3 x 3 windows. As a consequence, the curious situation may 
occur that operators that are derived along entirely different 
theoretical lines, may result in the same convolution filters. 
5 Plural Local Edge Detection 
The plural methods we consider here are: (1) Marr-Hildreth 
operator, (2) Canny operator, (3) Forstner operator, (4) Ed- 
geness operator, (5) Cascade of local edge detectors, and (6) 
Orientation coherence operator. 
5.1 Marr-Hildreth Operator 
The Marr-Hildreth (1980) operator is not primarily based on 
any underlying image model but on a theory of the human 
visual system, based on neurophysiological studies. We con- 
sider here only the engineering aspects. The image is first 
convolved with a Gaussian filter of which the blurring effect 
is controlled by the scale parameter c. Next the edges are 
detected as the zero-crossings of the rotation-invariant Lapla- 
cian (V?g = gzz + gyy). The conjunction of the Gaussian 
with the Laplacian is called Laplacian of Gaussian (LOG). 
The basic notion is that edges appear at a wide variety 
of scales. Therefore, edges should be detected at several 
amounts of blur, controlled by o of the Gaussian. The edges 
detected at different scales are next combined to form the 
"primal sketch”. This notion has resulted in the more general 
signal analysis technique of scale space filtering, introduced 
in the early 1980's by Witkin (1983), and further developed in 
(Babaud et al. 1986; Bergholm, 1987; Perona & Malik, 1990; 
Lindeberg, 1990; Zuerndorfer & Wakefield, 1990; Liu et al., 
1991; Lu & Jain, 1992). The essential idea is to embed the 
original image in a family of derived images, the scale-space 
g(z, y; 0) obtained by convolving the original image g(z, y; 0) 
    
   
   
    
  
  
    
  
   
   
    
   
   
   
   
    
   
    
     
  
      
   
   
   
   
    
   
   
   
   
   
   
    
   
   
   
    
    
    
    
     
    
   
    
with a ! 
the scal 
of scale 
larger tt 
the mor 
motivat 
of funct 
(Babauc 
generat 
the blur 
grey val 
deficits: 
5.2 
Canny 
problen 
edges Ii 
and the 
using a 
localiza 
appear. 
— 
1: 
tn m ar 
N nh ob RV