' the photo- 
natching in 
tation: the 
limensional 
ierial trian- 
ith parts of 
S, 
re matched 
re matched 
generate a 
] from the 
in order to 
jects. 
image mat- 
| object in- 
During im- 
10st evident 
ongs to the 
e known to 
arantee can 
or is stable 
data. Image 
or instance, 
g point may 
re than one 
semi-trans- 
be unstable 
roblem one 
tion exhibi- 
ll-in range. 
. for initial 
determined. 
ce for these 
arise during 
> converted 
additional 
issumptions 
grammetric 
Xf a calibra- 
- the grey values of the various images have been acqui- 
red using one and the same or at least similar spectral 
band(s), 
- the illumination (possibly altered by atmospheric ef- 
fects) is constant throughout the time interval for 
image acquisition, 
- the scene depicted in the images is rigid, i.e. it is not 
deformable; this implies that objects in the scene are 
rigid, too, and do not move, 
- the object surface is piecewise smooth, 
- the object surface is opaque, 
- the object surface exhibits a more or less diffuse re- 
flection function, 
- initial values such as the approximate overlap between 
the images or an average object height are known. 
Depending on the actual problem at hand additional 
assumptions may be introduced, and some points of the 
list may be violated. It is this mixture of assumptions 
which makes the design of a good image matching algo- 
rithm difficult, and has led to the development of diffe- 
rent algorithms in the past. 
Most matching algorithms proposed in the literature 
implicitly or explicitly contain a combination of assump- 
tions about the depicted scene and the image acquisition. 
In order to assess matching algorithms it is useful to 
decompose them into smaller modules (see also Gülch 
1994a). Distinctions can be made on the basis of 
- the primitives selected for matching: 
Possibilities include grey value windows in area based 
matching, image features with descriptive attributes in 
feature based matching, and structures (a relational 
description of the image content) in relational mat- 
ching. 
- the models used for defining the geometric and radio- 
metric mapping between the primitives of the various 
images: 
Geometric models in common use are the central 
perspective projection for image acquisition and ob- 
ject surface models with varying degree of smooth- 
ness. Modelling in the radiometric domain depends 
on the selected primitives. 
- the similarity measure between primitives from diffe- 
rent images: ] 
For area based matching common similarity measures 
include the cross correlation coefficient and the sum 
of the squares of grey value differences of conjugate 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
grey value windows. Feature based and relational mat- 
ching have to rely on cost functions on the basis of 
differences in the attributes. 
- the computation of the optimal match: 
Least squares adjustment (only applicable for area 
based matching) and different search methods (tree 
search, graph matching, relaxation, simulated annea- 
ling, dynamic programming etc.) are available. 
- the strategy employed in order to control the matching 
algorithm: 
In the matching strategy the individual steps carried 
out within a matching algorithm are determined. 
In a comprehensive comparison between different image 
matching algorithms for photogrammetric applications 
Gülch (1994a) showed that while under good conditions 
accurate matching results can be achieved with a large 
variety of algorithms, a good matching strategy is decisive 
for a successful solution in more complicated situations. 
Faugeras et al. (1992) obtained a similar result for algo- 
rithms popular in computer vision. Important points in 
terms of the matching strategy are: 
- Hierarchy: 
Hierarchical methods are used in many matching al- 
gorithms in order to reduce the ambiguity problem 
and to extend the pull-in range. They are employed 
from coarse to fine, and results achieved on one reso- 
lution are considered as approximations for the next 
finer level. For this task images are represented in a 
variety of resolutions, leading to so-called image pyra- 
mids (see figure 1). It should be noted that the primi- 
tives to be matched can vary from level to level accord- 
ing to the application. For instance, a coarse matching 
can be obtained using a relational description, and the 
results can subsequently be refined using point primi- 
tives. 
  
Figure 1: Example of an image pyramid (4 levels) 
299