the subsequent level of resolution, and warping the left and 
right images with respect to the interpolated surface. The 
whole process is repeated until the final refined surface is 
reached. At each level, images are rectified, the matching 
accuracy and reliability are improved, and a better surface 
representation is obtained. At the last level, the matching 
vectors vanish, the warped images become orthophotos, and 
the true surface is reconstructed. 
From this overview, it is clear that one of the objectives 
of surface interpolation is to construct as a realistic surface 
representation as possible. This task is crucial for the success 
of matching on subsequent levels. The search for a match is 
performed by centering a correlation window over a point of 
a zero-crossing contour in one image. On the other image, 
the search window is placed and shaped according to the 
expected depth range in that area (Schenk & Toth, 1991). 
The other goal of the surface interpolation is to provide in- 
formation for the surface analysis. It is important that the 
interpolator does not introduce new characteristics to the 
surface other than what is derived from the observations. 
Creating new maxima or minima in the surface is an exam- 
ple for undesired side effects of interpolation. Additionally, 
the surface interpolator should not smear essential surface 
shape characteristics. Such a situation may occur when a 
smooth surface is interpolated over observations on break 
lines. 
3. SURFACE INTERPOLATION 
The problem of surface fitting consists of taking a region 
containing a list of function values, and finding a function 
on this region that agrees with the data to some extent and 
behaves reasonably between data points (Lancaster & Salka- 
uskas, 1986). The accuracy that can be obtained from a 
fitting process depends on the density and the distribution 
of the reference points, and the method. Data points are 
arranged in various distribution patterns and densities. Ac- 
cordingly, surface fitting methods designed for one case differ 
from those designed for dealing with other distribution pat- 
terns. 
There are several criteria for classifying surface fitting meth- 
ods. The first criterion is the closeness of fit of the result- 
ing representation to the original data. Thereby, a fitting 
method can be either an interpolation or an approximation. 
Interpolation methods fit a surface that passes through all 
data points. Approximation methods construct a surface 
that passes near data points and minimizes, at the same 
time, the difference between the observed and the interpo- 
lated values. 
Another criterion is the extent of support of the surface fit- 
ting method; a method is classified as a global or a local one. 
In the global approach, the resulting surface representation 
incorporates all data points to derive the unknown coeffi- 
cients of the function. By doing so, some of the local details 
submerge in the overall surface, and editing one point affects 
all distinct points. With local methods, the value of the con- 
structed surface at a point considers only data at relatively 
nearby points. Thus, the resulting surface emphasizes the 
small-scale trends in the data (Watson, 1992). Many global 
schemes can be made local by partitioning the original do- 
main into subdomains. 
Yet another criterion for classifying interpolation methods 
is their mathematical models. Surface interpolation meth- 
ods are divided into three main classes; weighted average 
methods, interpolation by polynomials, and interpolation by 
splines. 
3.1 Weighted average methods 
These methods use a direct summation of the data at each 
interpolation point. The value of the surface at a non-data 
point is obtained as a weighted average of all data points. 
The weight is inversely proportional to the distance r;. Shep- 
ard’s method may serve as an example. Here, the value of a 
point is evaluated as 
N , Fir? sy 1/75, when 7; #0, 
f(z,y) = (1) 
F when r; = 0. 
Weighted average methods are suitable for interpolating a 
surface from arbitrarily distributed data. However, one 
drawback is the large amount of calculations, especially for 
many data points. To overcome this problem, the method 
is modified into a local version. A smaller subset of data is 
selected for each non-data point based on a fixed number of 
points, or a fixed area. The problem now is to define proper 
parameters (e.g. the variable u in equation (1)). 
3.2 Interpolation by polynomials 
A polynomial p is a function defined in one dimension for all 
real numbers æ by 
p(z) — ao -F a2 4 -F ay iz" + anz”, (2) 
where N is a non-negative integer and ao,...,aw are fixed 
real numbers. Generally, fitting a surface by polynomials 
proceeds in two steps. The first one is the determination of 
the coefficients of the polynomial based on the set of data 
points and the criteria controlling the fit of the polynomial 
function. Then, using the computed parameters, the second 
phase evaluates the polynomial to obtain values of the fitted 
surface at given locations. 
Piecewise polynomials are the local version for surface fitting 
with polynomials. This approach works well with irregularly 
spaced data. The general procedure for surface fitting with 
piecewise polynomials consists of the following operations: 
1. partitioning the surface into patches of triangular or 
rectangular shape, the vertices of which are the refer- 
ence points. 
2. fitting locally a leveled, tilted, or second-degree plane 
at each patch, using one or more terms of the polyno- 
mial. 
3. solving the unknown parameters of the polynomial. To 
enforce continuity (and smoothness) along the joining 
sides of neighboring patches, partial derivatives must 
have been estimated at each reference point. 
Least squares fitting by polynomials performs well if many 
points are available and the surface has fairly simple form 
(Hayes, 1987). On the other hand, interpolation by poly- 
nomials with scattered data causes serious difficulties, one 
of which is a singular system of equations due to data dis- 
tribution (e.g. data lie on a line). Another problem is an 
228 
ill-co 
secut 
in us 
ina 
3.3 ] 
A sp 
tiguo 
nuity 
at th 
deriv 
tives 
Bicul 
(ie. 
tion 
prodi 
data 
racy ı 
fittin 
is the 
the s 
band 
duce 
Bicul 
or un 
rank- 
probl 
Becai 
supp: 
data 
tions 
larity 
Noda 
surfa« 
apprc 
corres 
OVET : 
then 
advar 
spline 
is tha 
instez 
1974) 
Thin 
These 
since 
cubic 
The s 
tion e 
only. 
is rep 
9^ 
Ör‘ 
Adopt! 
a set «