hniques 
e method is 
original, non- 
is solved by 
t-space gray 
as a method 
te search is 
troduced for 
reprocessing 
sed on cases 
 multi-image 
letermination 
ct due to the 
f the search 
oplicability of 
early has the 
aightforward 
computation 
, the search- 
stations in a 
of numerical 
ving systems 
search, the 
iginated from 
intelligence. 
matching has 
or (1982) and 
r refined by 
age matching 
re based on 
:chniques for 
ned linearized 
ast squares 
or linearized 
directly. 
> expressed in 
1atching two 
| functions we 
X2 V2 
| f [g (x+ Ax, y+ Ay) -g, (x,7)] dydx = min! (1) 
Weis 
g, (x,y) a template or a reference image 
g, (x.y) the image to be matched 
X,»X2»Y,»Y, lower and upper bounds of the window 
in the reference image 
Ax, Ay the unknown shifts 
For multi-image matching, when one of the images is kept 
as a reference image, the basic formulation becomes 
X2 V2 
S f] [g, Gc Ax y * Ay) - g, (x, y)] dydx = min! (2) 
an 
where 
g,(x,y) a reference image 
l number of images in the match set 
(the total number of images is / +1) 
Formulas (1) and (2) are expressed in a simplified form so 
that there are no free parameters for radiometric or 
geometric corrections. For modelling the geometric 
differences of the images rigorously, it is most 
straightforward to use object space formulation (Wrobel, 
1987; Ebner and Heipke, 1988; Helava 1988: Heipke 
1992): 
! XY, 
I] le. (SQ. Y. z (X Y. p), ))-G(x.7)] dys = min! 
k=0 X Y, 
where (3) 
X.Y.Z2 object coordinate system 
S(X, Y; Zr, ) geometric transformation function from the object 
coordinate system ( X, Y, Z) to the image 
coordinate system (x. y), 
k an (approximately) known vector of the orientation 
parameters for each image k 
X,,X,,Y,,Y,  lowerand upper bounds of the match 
window (patch) in the object space 
Z(X, Y,p) an elevation function for the patch in the object space 
p an unknown vector of the parameters 
for the elevation function 
G(X, Y) an unknown fictitious gray level function of the patch 
in the object space 
Formula (3) is the corner stone for this paper. It defines 
the object function and free functions Z(X,Y,p) and 
G(X,Y). The type of these functions have to be defined 
725 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
to model the physical reality with sufficient fidelity. 
Thereafter the numerical parameters related to the model 
can be estimated by means of numerical analysis. 
Throughout of this paper we assume that orientation 
parameters are known for each image, at least 
approximately. 
For the purposes of further elaboration, a modified version 
of formula (3) is: 
sy [e (S(X..x 2 (9) ))- | - min! (4) 
k=0 ieA 
where 
a set of groundels used for match 
A 
X,,Y, the planimetric object coordinates of 
the centre point of the groundel i 
G, the unknown fictitious gray level value 
of the groundel 7 
Here a rectangular match window in the object space is 
replaced with a finite set of groundels that usually form a 
topologically connected area The gray level function has 
been replaced with simple variables. 
In computer implementations, function  g(x,y)is 
presented with an integer valued function, /, (line, column), 
where line and column are also integer variables. Using 
this as input, the numerical values for g(x,y) are 
available by means of bilinear interpolation using the 
neighboring pixels. The use of bilinear interpolation is 
essential if we want to stay in accordance with the original 
least squares matching (Fórstner, 1982). This can by 
justified by noticing that both methods use gray value 
differences of neighboring pixels for approximating the 
gray level function locally. The technique is used for 
reaching sub-pixel accuracy. 
3. LEAST SQUARES MATCHING BY SEARCH 
Search methods are based on the idea that a solution to a 
problem can be found by searching a finite number of 
states and that a criterion is given for evaluating the 
'goodness' of each state. This criterion defines the goal 
state, i.e. the state to stop the search. When applied to 
numerical analysis and especially to least squares 
adjustment this means that the search space is defined in 
terms of the unknown parameters, whereas the object 
function (here the minimum sum of squared residuals) 
defines directly the goal state. 
Search-based techniques rely on integer programming 
and therefore the unknown parameters have to been 
discretized. Regarding formula (4), a finite search space 
consists of the discretized values of p andG,,ie A. This 
assumes that realistic lower and upper bounds are