3 Boundaries 
What constitutes a boundary? Since the human visual system 
is so highly sophisticated, this seems to be a trivial question. 
However, a large problem in boundary detection is obtaining a 
suitable definition of a boundary which is generally applicable. 
Definitions can be given in two domains: (1) image domain, 
and (2) task domain. Within the image domain the most 
important feature that may represent a boundary is the edge: 
An edge is an intensity discontinuity in the image. 
In course of time an abundance of algorithms have been de- 
veloped, designed to trace local intensity discontinuities in 
the image. We treat some of them in sections 4 and 5. 
The objects one wants to extract, depend on the task do- 
main at hand. For example, for a large scale base map of 
an urban area one wants other objects than for a national 
road data base. This observation results in the important 
understanding that a perfect outlining of relevant objects in 
aerial and space imagery can not be established by bottom-up 
approaches alone. We define a boundary as: 
A boundary is a (closed) outlining of an object 
which is relevant for the task at hand. 
A common preassumption is that abrupt intensity changes in 
the image correspond to meaningful object boundaries in the 
scene. This may be valid for highly restricted scenes, such 
as present in industrial environments, but for unrestricted 
scenes, a boundary may be visible in the image as abrupt in- 
tensity changes, but this is neither a necessary nor a sufficient 
condition. Not all intensity changes correspond with relevant 
object outlinings. They may be, for example, due to noise, 
texture and shadows. Furthermore, boundaries may not show 
up as intensity changes, due to low contrast or occlusion. To 
resolve this problem a priori information about the objects 
relevant to the task domain is necessary. This information 
can concern radiometric and geometric properties. 
The exploration of radiometric properties is carried out regu- 
larly by the remote sensing community for multispectral aerial 
and space imagery by statistical pattern recognition tech- 
niques using as features (functions of) the grey values of the 
different spectral bands. However, pixel-based classification 
is highly prone to error, resulting in the wish of developing 
object-based classification techniques, which require, at turn, 
reliable delineation of objects. 
Geometric properties may concern generic or specific aspects. 
Generic geometric aspects concern descriptions of general ap- 
pearances of boundaries, such as: (1) smooth continuation, 
i.e. nearby edge pixels will point approximately in the same 
direction, (2) thinness, e.g. edges should be one pixel thick, 
which criterion is often necessary for further processing, and 
(3) connectivity, e.g. boundaries will be closed. A classical 
mechanism to incorporate generic geometric information is 
by probabilistic relaxation (e.g. Schachter et al., 1977; Pe- 
leg, 1980; Prager, 1980; Hancock & Kittler, 1990; Duncan 
& Birkholzer, 1992). For edge detection purposes on images 
of unrestricted scenes this mechanism shows several severe 
drawbacks. 
Specific geometric information concerns more detailed de- 
scriptions about the shape and possibly size of the bound- 
aries, for example, the objects of interest have circular or 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
rectangular boundaries. The exploration of specific geomet- 
ric information has been subject of extensive research. For 
example the Hough transform (for a good survey with many 
references, see lllingworth & Kittler (1988)), boundary de- 
lineation by dynamic programming ( e.g. Montanari, 1971; 
Martelli, 1976; Elliott & Srinivasan, 1981; Gerbrands, 1988; 
Lemmens et al., 1990), and perceptual grouping (e.g. Witkin 
& Tenenbaum, 1986; Khan & Gillies, 1992; Lu & Agger- 
wal, 1992; Mohan & Nevatia, 1992; Price & Huertas, 1992; 
Lin et al, 1995) are well-known approaches. Lemmens et al. 
(1990) suggested to use dynamic programming for road de- 
tection. Within the photogrammetric community De Gunst 
et al. (1991), and Grün & Li (1994) explored the approach 
for this purpose. 
We focus in the sequel on local edge detection schemes, be- 
cause they form the fundamental stage in any boundary de- 
lineation task. We loosely divide them into two broad classes: 
(1) monadic schemes and (2) plural schemes. Monadic 
schemes base the decision whether an edge is present or not, 
directly on the responses of the operators, without further ex- 
amination of additional responses, while plural schemes carry 
out such an evaluation in some form. 
4 Monadic Local Edge Detection 
A local edge detector is an operator of small spatial extent 
that traces changes in the image function to classify each 
pixel as edge or non-edge according to some decision rule. No 
a priori information about the scene structure or contextual 
information is employed. Monadic methods can be generally 
classified into one of four categories: (1) Differentiation, (2) 
Surface fitting, (3) Template matching, and (4) Curvature 
determination. Other approaches have been proposed, such 
as those based on morphological operators (cf. Lee et al. 
1987). We do not treat them here. 
4.1 Discrete Differentiation 
Abrupt intensity changes are traceable by computing the 
partial derivatives in two orthogonal directions: gx = 
09/02; gu = 9g/9y), usually along the grid lines. The small- 
est step possible on a sampled space is the sample interval 
Az. By definition the pixel size is unity: Az = 1. Hence the 
discrete derivative in z-direction of the 2-D discrete function 
g becomes: 
g; — limas—i[g(j-- Az) - g()]/A» — 9(3 1) 9G) (1) 
Accordingly one can define gy, the first derivative in y- 
direction. (For the Roberts operator g; and gy become: 
gs — g(i 3--1)—g(1--1, 3); gy — 9(5 3) (1-1, 3 1).) The 
edges located by the gradient components according Eq.(1) 
are situated at the grid lines yielding interpixel (crack) edges. 
The computation can be done by convolving g with the masks 
[1 1] and [71 1]7, where T' denotes the transpose. These 
above masks are not symmetrically positioned. To evade this 
we may choose the central derivative: 
ga = limaz—o[9(j + FAx) — 9(j — 5A2]/Az 
which results in: g2 = #[g(7 +1) — g(3 — 1)]. Accordingly gy 
is defined. The computation of g; and gy can now be done 
by convolving g with the masks [—1 0 1] and [-1 0 1], 
respectively. The orientation of the edge is defined by: 
0 — arctan gy/g« -- 1/27, and the edge strength (magnitude) 
by: M, = 4/92 + g?. Alternative definitions of edge strength 
that bypass squaring and square rooting reducing computa- 
436 
   
   
   
   
   
   
   
   
   
  
   
  
   
  
   
    
   
    
   
   
    
  
   
   
   
    
   
   
   
    
   
  
   
   
    
  
  
  
  
  
   
  
   
  
   
   
   
   
   
   
   
  
   
   
   
   
  
  
   
    
   
tion tim 
and the 
magnitu 
depend 
grid. F. 
tor may 
ideal st: 
operato 
degrees 
M3 is d 
is more 
to temr 
(section 
occupy 
of the | 
ally in t 
distanc« 
ing all € 
look-up 
rived fr 
version 
entiatio 
directio 
gradien 
nent: [- 
sign. | 
operato 
The So 
small si 
backgrc 
lie close 
grey va 
propert 
Since a 
tensity 
proache 
ceeds t 
tected | 
The ea 
tor, we! 
much r 
a featu 
be at le 
feature 
of the 
edges à 
ues are 
The dis 
Gaussiz 
remain 
image | 
4.2 S 
In an a 
edge fe 
model 
functio 
The lo 
tions, t 
to the 
norm, | 
Prewit 
idea- a|