4. DISCONTINUITY DETECTION 
There are only a few methods which try to detect discontinu- 
ities in the surface. Grimson and Pavlidis propose detecting 
discontinuities before interpolating the surface to overcome 
the problem of oscillations in the fitted surface (Grimson & 
Pavlidis, 1985). The main idea for this approach is to fit 
locally a simple surface (plane) to the data and examine the 
distribution of the residual error. If it appears to be “ran- 
dom", then the hypothesis of no discontinuity is accepted. If 
there is a systematic trend, then a discontinuity of a certain 
type is hypothesized. Discontinuities are subdivided into 
various types, each of which is characterized by a certain 
combination of change in magnitude and sign of the resid- 
ual. Once a discontinuity is detected, the surface is broken 
down into smaller regions, and the surface reconstructor is 
passed over each of them. 
The second approach, proposed by Terzopoulos (Terzopou- 
los, 1985), is related to the energy function of a thin plate. 
The thin plate surface over-shoots constraints near the dis- 
continuity causing a sign change of the bending moments at 
surface inflections. Depth discontinuities are detected and 
localized by examining the bending moments in the inter- 
polated surface. Changing control parameters within the 
energy function allows the surface to crease and fracture at 
the detected discontinuities and reduce the total energy. 
Another approach we investigated for detecting discontinu- 
ities is based on the concept of a "line process" introduced in 
(Geman & Geman, 1984. A line process is a set of variables 
located at the lines which connect the original lattice (pixels 
or grid cells) (Figure 3). The purpose of a line process is to 
decouple adjacent pixels and reduce the total energy if the 
values of these pixels are different. In such a case, the vari- 
able of the line process associated with these pixels is set to 
one, otherwise it is set to zero. 
e 00 
o 
eoeoe 
o 
eoeoe 
Figure 3: Dual lattice of depth (e) and line (o) elements. 
Eventually, breaking the surface into small pieces around 
each data point will result in the lowest energy state. To 
avoid this, a penalty o should be paid (in terms of energy) 
when a break line is introduced. Thus, a break line will only 
be introduced when paying the penalty is less expensive than 
not having the break line at all. The penalty function takes 
the form P — al;, where [; is the line process. This function is 
added to the original energy function, changing the problem 
into minimizing 
E=S+D+P. (7) 
The result is a combination of a continuous function for the 
surface and a discrete one for the lines. This combination 
allows surface reconstruction and discontinuity detection at 
the same time. However, E is a non-convex function that 
has many local minima. 
One proposal to solve the non-convex function is to adopt a 
deterministic approach. The line process P is merged with 
230 
the interpolation function S (Blake & Zisserman, 1987). The 
modified function is expressed in one dimension as 
g(vu; = U_1) = À (us "E u;_1)*(1 er l;) + al;. (8) 
The resulting function controls the interaction between 
neighboring grid cells. Such a function prefers continuity 
in the surface, but allows occasional discontinuities if that 
makes for a simpler overall description — a theme called 
“weak continuity constraints". 
The modified configuration is then solved by the gradu- 
ated non-convexity algorithm. The non-convex function E 
is gradually approximated by a convex one through a family 
of p intermediate functions. The parameter p represents a 
sequence of numbers ranging from one to zero. The function 
E) is a crude approximation to the non-convex function. 
However, as p goes to zero, E) becomes closer to the orig- 
inal non-convex one. The neighbour interaction function is 
also modified into a function of A, a, and p. 
5. EXPERIMENTS AND CONCLUSION 
For experimental purposes, we designed synthetic data rep- 
resenting a set of irregular blocks in a small region. Depth 
information is arranged in a fashion that mimics the pattern 
of the results of the matching process in the surface recon- 
struction system. Thus, depth values were provided for some 
points on, and near by, the edges of the blocks and the edge 
of the region as shown in figure 4. Figure 5 is a 3-D repre- 
  
  
  
  
Figure 4: Distribution of synthetic data points. 
sentation of these points. The location and value of a data 
point is represented by a peak, while no data points are set 
to zero. 
We evaluated the interpolation methods according to the 
following criteria: 
1. Interpolated surface must be plausible compared to the 
visible surface in the real world. 
2. The interpolation method must not jeopardize clues for 
surface analysis. 
3. The method should be able to utilize a priori informa- 
tion on break lines. 
  
Match 
data 
we hax 
nomial 
These 
the wc 
ing sp: 
equati 
nished 
chance 
Howev 
to the 
tation 
The m 
dling s 
extrem 
  
Figure | 
tablishe 
a point 
mation