hods 
1eth- 
rage 
n by 
each 
data 
ints. 
hep- 
of a 
ng a 
one 
y for 
thod 
ta is 
er of 
oper 
or all 
(2) 
fixed 
nials 
on of 
data 
mial 
cond 
itted 
tting 
larly 
with 
ns: 
ar Or 
efer- 
lane 
yno- 
| To 
ning 
must 
nany 
form 
poly- 
one 
, dis- 
is an 
ill-conditioned normal equation system as is the case of con- 
secutive intervals that contain no data. Yet another problem 
in using polynomials is their tendency to oscillate, resulting 
in a considerably undulating surface. 
3.3 Interpolation by spline functions 
À spline is a piecewise polynomial function defined on con- 
tiguous segments. In defining a spline function, the conti- 
nuity and smoothness between two segments are constrained 
at the interior knots by demanding the existence of certain 
derivatives. For example, a spline of degree n has n-1 deriva- 
tives at the knots, denoted by C^-!. 
Bicubic splines, which have continuous second derivatives 
(i.e. C?), are commonly used for surface fitting. The solu- 
tion is obtained by a least-squares approach or the tensor 
product of orthogonal functions. With increasing number of 
data points, problems with computing efficiency and accu- 
racy may occur. B-splines are also frequently used for surface 
fitting. They are characterized by their finite support, which 
is the interval over which the function is non-zero. Limiting 
the support of a spline changes the normal equation into a 
band form. Thereafter, the amount of computations is re- 
duced by a factor of (number of knots/4)? (Hayes, 1987). 
Bicubic splines and B-splines work best in the case of gridded 
or uniformly-distributed dense data (Hayes, 1987). However, 
rank-deficiency in the system of equations becomes a serious 
problem when applying these approaches to scattered data. 
Because of data distribution, data points may not lie in the 
support region of splines. Another situation rises when the 
data are clustered in one region creating a set of linear equa- 
tions of marginal differences, thereby producing near singu- 
larity. 
Nodal basis-functions are another sub-group of methods for 
surface fitting with splines. The general procedure in this 
approach consists of defining a set of basis functions and the 
corresponding data points. Each basis function is centered 
over a data point (node). The interpolation spline function 
then is a linear combination of the basis functions. The 
advantage in using such an approach is that knowledge about 
spline locations (knots) is not required. Another advantage 
is that values at the nodes of a regular grid are found directly 
instead of the two step approach mentioned earlier (Briggs, 
1974). 
Thin plate splines are derived from the nodal basis-functions. 
These splines are also called *minimum curvature splines" 
since they are obtained by minimizing the total curvature of 
cubic spline s 
Qs Puy 
ff = + =) dz dy. (3) 
The same form can be obtained by solving the small deflec- 
tion equation of an infinite plate that deforms by bending it 
only. The displacement u due to a force f; acting at N points 
is represented by the differential equation (Briggs, 1974) 
Ou, Fu, On 
0xt 0220? Öy* 
= fi, at observation position, 
0 otherwise. (4) 
Adopting the physical analogy, depth data is represented by 
a set of vertical pins scattered within the region; the height 
229 
of an individual pin is related to the elevation of the point. 
Fitting a surface is then analogous to constraining a thin 
(elastic) plate to pass over the tips of the pins (Figure 2). 
dq 
Figure 2: Fitting thin plate over pins. 
   
  
One method for solving the differential equation is by finite 
differences or finite elements. Following this approach, the 
discrete interpolation becomes a repeated passage of a set of 
simple masks, such as the following mask for elements within 
a grid: 
1 
9 8. 9 
).-8. 20 —8 ] (5) 
2. =8 2 
1 
3.4 Surface interpolation by regularization. 
A problem is well-posed if a solution exists, is unique, and 
depends continuously on the initial data. It must also be 
well conditioned to ensure numerical stability (robust against 
noise) (Poggio et al., 1985). Shorter than these conditions, 
the problem is considered ill-posed. Reconstruction of the 
visible three-dimensional surfaces from two-dimensional im- 
ages is an ill-posed problem because some information is lost 
during the imaging process (projecting 3-D into 2-D) (Pog- 
gio et al., 1985). Other reasons are the noise and erroneous, 
inconsistent, and sparse measurements (Terzopoulos, 1985). 
Regularization is the frame within which an ill-posed prob- 
lem is changed into a well-posed one (Poggio et al., 1985). 
The class of possible solutions is restricted by introducing 
suitable a priori knowledge, which in the case of surface in- 
terpolation is the continuity of the surface. The problem 
is then reformulated, based on the variational principle, so 
as to minimize an energy function E constructed from two 
functionals. The first one measures the smoothness of the so- 
lution S, while the second one, D, provides a measure of the 
closeness of the solution to the observations. The two mea- 
sures are combined to form the energy function E — S 4- D. 
Applied to the surface reconstruction problem, the energy 
function can be written as 
J [P sata AY s)- P. (6) 
In practice, the function in the integration is either a thin- 
plate spline (f2, + 2f2, + f},), a membrane (fZ, + f2,), or a 
combination of both. The variable A is the regularization pa- 
rameter which controls the influence of the two functionals. 
If À is very large, the first term in the integral heavily affects 
the solution, turning it into interpolation (close to data). 
On the other hand, if À is small, the solution emphasizes the 
smoothness of the surface.