ints.
oles,
aber
ured
free
rves
are
| of
iary
yy a
tom
ined
ject
| are
rate
-rep
med
rom
ical
ts a
rt it
gital
ades
ains
Jous
1age
and
area
tion
jage
ace.
that
| be
jage
hich
| be
CD
:dge
the
raph
sect
n be
90).
trast
age
and
pply
ased
Digital Images
| Image Preprocessing |
i
Generation of the Approximate
Surface model
5
-
i ES
Area Based Matching Edge Based Matching
aestu ina (Dynamic Programming)
Combination of Matching
Results
|
Elimination of Matching Errors
and Interpolation
Criteria Fulfilled ?
Yes
Digital Surface Model
Figure 3. A schema of the algorithm for reconstruction of
a surface with discontinuities by digital image matching
technique.
An approximate surface is built hierarchically with a pyramid
structure by digital image matching. This process begins with
an image pair of reduced resolution and a sparse grid on the
XY plane in the object space. At every grid point in the object
space, Z values are determined by Vertical Line Locus (VVL)
Matching (Cogan and Hunter, 1984, Li, 1990). The image pair
with a larger format size is used and the grid is densified after
Z values for all grid points are calculated. Z values of grid
points calculated during the previous iteration, are used to
estimate approximate values in the current iteration. This
procedure continues until the image pair reaches its original
resolution. This insures a reliable approximate surface and
reduces computing time.
With the approximated surface model, an area based image
matching module, namely a least squares matching in object
space (Li, 1990), is used to calculate grid points in the object
space point after point. This refines the Z values at all grid
points in relative flat regions. At the same time edges are
extracted and matched by a dynamic programming procedure
to determine discontinuities of the surface. In this procedure,
there are three similarity criteria for recognizing identical
edges in the objective function: a) similarity of gray value
distributions near edges, b) differences between edge
directions, and c) image texture characteristics. This edge
matching procedure (using dynamic programming) is
constrained by edge continuity and geometric consistence with
the obtained object surface. The first condition requires that a
pair of correctly matched edges should be matched at all
intersection points between these edges and epipolar lines. The
second constraint implies that correctly matched edges in the
object space should be within a proper tolerance to the
calculated surface model. Thus, elimination of a part of
mismatched edges is included in the matching procedure itself.
À detailed description of this edge based image matching can
be found in Li (1990).
In order to acquire a complete surface model in continuous
and discontinuous regions, results achieved by the area based
and edge based image matching methods have to be combined.
One of most important considerations is the preservation of
local surface discontinuities during the integration of the
results. It is realized in such a way that a) unmatched points
along an edge are linearly interpolated; b) points with
matching failures, which often appear near surface
discontinuities are interpolated separately on both sides of
edges. This local interpolation method makes it possible, to
prevent depression of surface discontinuities due to global
interpolation.
Because of lack of image texture, effects of
object-camera-geometry, and surface discontinuities,
mismatches are unavoidable. False matches are detected by
checking points in their neighborhood. They are then replaced
by values calculated according to their neighborhood. Until
here, a complex surface model is generated.
In the image matching procedures, area and edge based image
matching modules run separately (Figure 3). That is, the result
from one image matching module does not benefit the other
directly. In fact, area based matching improves the digital
surface model and could provide better geometric constrains
for the edge based matching. Conversely, the reconstructed
discontinuities may improve the estimation of surface points
near edges (potential surface discontinuities) by area based
matching. In that sense, it is necessary to restart the image
matching procedure with the improved digital surface model
as an approximate surface, and to refine the digital surface
model iteratively. This iterative procedure continues until
some criteria such as the number of iterations and/or the
percentage of total mismatched points are satisfied. The final
result is a digital surface model, which approximates the real
object surface as closely as possible.
The presented algorithm for the reconstruction of digital
surface models is applied successfully to different image
types, e.g. aerial photography, close-range photography and
electron-microscopic images (Li, 1990).
3.3 Conversion from a Digital Surface Model to
an Octree Representation
3.3.1 Octree Representation
Octree representations describe objects by a spatial numerical
structure. Octree micro cells approach geometric details of
objects hierarchically. An original octant is defined as a cube
which contains the object to be described by an octree
representation (Spur et al, 1989, 1990, Samet, 1990, Li,
1991). The original octant is then divided into suboctants
which fit the object shape by their hierarchical spatial
structure. As shown in Figure 4(a), at first level, the original
octant is divided into eight suboctants by halving it in three
directions. Each suboctant is then checked whether it is
occupied by the object. The suboctants are classified into three
categories: a) F=Full (occupied by the object); b) E=Empty
(no object element in the suboctant); and c) P=Partial (the
suboctant is partially occupied by the object). On the other
hand, these eight suboctants correspond to eight digits from 0
to 7, which enable the suboctants to be related to the 3D