proven that every finite lattice is complete [Kainz et al., 1993]. 
2.2. Mathematical Morphology 
Mathematical morphology (MM) is an approach to the analysis 
of structures based on set theoretic concepts. Let X be a given 
object set, B be a set of structure element, the two fundamental 
morphological operations on X are defined as follows: 
Dilation: Xe BzU,., X, [1] 
Erosion: XO B= fl... > [2] 
where X, is defined as the translation of X by vector b, 
ie, X, = {x+b|x € X} . From equations [1] and [2], we know 
that dilation is an expansion of the set and erosion is a 
shrinking of the set. The detail definitions of other 
morphological operators and their properties can be found in 
[Serra, 1982]. 
2.3. Metric Spaces 
A metric space is a pair consisting of a set E and a mapping 
(p, p,) O d(p,, p,) of E x E into R, ,having the properties: (1). 
D, 7 p, € d(p, p,) -0; Q).d(p, p) - d(p,,p,) (symmetry); 
(3).d(p..p,) &d(p,p,) * d(p,,p,) (triangle inequality). The 
function d is called a metric and d(p,, p,) is called the distance 
between the points p,and p,. Distance between points 
D,(X4:X55...,X,) in R” is described in terms of the Minkowski 
d, -metric: 
d (py P) 0,3, - xD" [3] 
j=l 
Conventional Euclidean distance is defined by the 4, -metric. 
Similarly, the Manhattan distance defined by the 4, -metric, 
and the maximum distance defined by the 4, -metric. Some 
examples of different distances are shown in Fig.1. 
2.4. Topological Spaces 
A topological space is a pair consisting of a set E and a 
collection # of subsets of E called the open sets, satisfying the 
three following properties: (1). every union (finite or otherwise) 
of open sets is open; (2). every finite intersection of open sets is 
open; (3). the set E and the empty set M are open. 
One of the most important properties which a topological space 
can satisfy is that of compactness. A topological space E is said 
to be compact if it is separated and if from every open covering 
of E one can select a finite subcovering of E. Some other related 
definitions of topological concepts, such as interior, closure and 
boundary can be found in [Egenhofer and Franzosa, 1991]. 
2.5. The Hausdorff Metric 
(a). Metric topology: A metric d on a set E includes a topology 
on £, called metric topology defined by d. This topology is such 
that U c E is an open set if, for each p, EU , thereisan e» 0 
such that the d-ball of radius e around p, is contained U . A 
d-ball is the set of points whose distance from p, in the metric 
d is less thanz, ie. (p, €E|d(p,, p,) « €) . Notice that the 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
  
  
  
  
  
  
  
  
  
  
à |d,=max (a,b) 
4 
e 
= 
il 
» 
>. 
e 
  
  
  
  
  
  
  
  
  
Fig.1. Three methods of measuring distance in the plane and the 
corresponding unit sets 
ve” ^. 
(a) £ X 
a 
d ~ \ 
A47 
-- N 
SC # x 
  
  
  
  
  
Fig.2. (a). the Hausdorff distance £, ; (b).the distance properties. 
metric topological spaces are Hausdoff and separable. 
(b). The Hausdorff metric: Hausdorff's metric is defined on the 
space X where each point is a non empty compact set of R^ . If 
K, and K, denote two non empty compact set in R^ (or 
equivalently two points in €), and B (e) is the closed ball with 
a radius e , then the quantity: 
p(K,, K,) inf(e:K, € K, © B(e), K, c K, 9 B(¢)} [4] 
defines a metric p on X , known as the Hausdorff metric. From 
equation [4], p is the radius ofthe smallest closed ball B such 
that both K, is contained in the set K, € B(£) generated by 
dilation and K, is contained in the dilated set K, & B(e) . It 
can be proven that the Hausdorff distance o(K,,K,) satisfies 
all the properties of distance functions [Serra, 1982]. Fig.2 
illustrates the notation and properties of Hausdorff distances. 
In particular case, when K, and K, are reduced to two points, 
the Hausdorff distance p(K,, K,) coincides with the Euclidean 
distance. 
3. SPATIAL RELATIONS BETWEEN SETS 
3.1. Topological Relations between Sets 
Topological relations are spatial relations that are preserved 
under such as rotation, scaling, and rubber sheeting. The model 
for binary topological relations is based on the usual concepts of 
point-set topology with open and closed sets [Egenhofer et al., 
1994]. The binary topological relations between two objects, 
K, and K,, in IR? is based upon the intersection of K,'s 
interior ( K7 ), boundary ( &K, ),and exterior ( K, ) with K,'s 
interior ( K7), boundary (6K,), and exterior ( Kj ). A 3x3 
matrix 5$, , called the 9-intersection as follows: 
Km KR; Knk 
Sk, KD CGGK nCOK, EKnkK [5] 
KR? SKOOYOR C KUnK; 
100 
    
   
  
  
  
  
  
    
   
   
  
  
  
  
  
   
   
  
    
    
  
    
   
  
    
    
   
    
  
    
  
  
   
  
  
    
    
    
     
   
   
   
   
   
  
    
        
   
    
  
  
  
  
  
  
Topologica 
content (i 
dimension. 
Franzosa, 
criterion a 
non-empty 
paper. By 
one can 
relations ii 
objects of. 
(1991) she 
embedded 
different 1 
covers, co 
apply the 
relations t 
objects an 
combining 
region, a | 
will be m 
al. (1995) 
possible, 
detail de: 
[Egenhofe 
3.2. Metr 
3.2.1. Dy 
According 
dilation [ 
set B(e,) 
also the c 
9-intersec 
e9 = 
Sa3 (07 
e 
Sen(;)