PRESERVING TOPOGRAPHY IN 3D DATA COMPRESSION FOR SHAPE RECOGNITION
Reda Ezzat Fayek
Systems Design Engineering
University of Waterloo
Waterloo, Ontario N2L 3G1, CANADA
reda@watnow.uwaterloo.ca
Commision Ill, Working Group 3
KEY WORDS: Object Modeling, Recognition, Surface Triangulation, DEM/DTM Model.
ABSTRACT
This paper presents a powerful interaction of two 3D object modeling concepts with the goal of enhanced 3D object recog-
nition from dense sensory range information. The first concept is the careful and subjective coarsening of a triangular mesh
representation of the sensory data to reduce the complexity of the model matching during recognition. For this purpose, we
use an iterative mesh decimation approach which reduces the number of vertices and triangles in the mesh while preserving
its important features. The importance of a particular vertex or edge in the triangular mesh is determined using topographic
concepts and local surface properties. This process is repeated to produce meshes at various controlled resolution levels of the
same scene. This technique finally produces a coarser mesh with the same topography as the original data. Typical reductions
in mesh complexity are about 90%. The other concept is the use of generic symbolic 3D object models. Such a model describes
invariant relations between sections of the object’s bounding surface and, therefore, is invariant to translation, rotation, scale
variations and partial occlusion. The 3D object recognition task is therefore reduced to matching such an object model against
subsets of the reduced meshes resulting from the coarsening phases. This model matching procedure is greatly simplified due
to the abstraction capability of the coarsening technique and the flexibility of the generic models. We provide experimental
results demonstrating the strength of this interaction.
1 INTRODUCTION
Triangular meshes have been frequently used for mod-
eling general 3D curved surfaces (Boender et al., 1994,
Cheng et al., 1988, — Fua & Sander, 1991, Garcia, 1994,
George, 1991, Schroeder et al., 1992). This spatial data
representation is attractive for its simplicity and flexibil-
ity. The main advantage in using triangular meshes for
modeling complex 3D surfaces and objects is that they
can adapt to fit an arbitrary surface with any desired
accuracy or abstraction. Nonetheless, the extensive usage
of triangular meshes in modeling has been mostly confined
to special-purpose visualization or scientific computation
tasks (Rippa, 1992, Schroeder et al., 1992). This was mainly
due to concerns about storage, accuracy, and combinatorics.
Recently, however, with the rapid increase in computing
and storage capabilities made affordable, it is becoming
more reasonable to adopt this representations for most
3D modeling applications. This is also encouraged by the
frequent use of 3D sensors yielding massive amounts of data
such as photogrammetry, stereo-imaging and laser scanners.
Modeling such large data sets is not feasible without an
abstraction and compression of the available huge data.
Furthermore, although parametric and analytical representa-
tions of curved surfaces (e.g., NURBS) may be easier in de-
sign, triangular meshes are more suitable for modeling sen-
sory 3D data. While mathematical manipulations of analyti-
cal representations facilitate the iterative design revisions of
generated 3D surfaces (e.g., mechanical parts, automotive
design, artistic design, etc.), they provide no support for the
automated symbolic reasoning about such 3D objects. In con-
trast, acquired 3D sensory data need to be effectively modeled
in order to facilitate computer-based 3D scene interpretation.
Triangular meshes provide both aspects of surface modeling,
i.e., accurate surface description from scattered points and
support for symbolic, feature-based scene interpretation.
186
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
We use a general-purpose 3D representation based on irreg-
ular triangular meshes (ITM) (Fayek & Wong, 1994) for the
modeling of large amounts of spatial sensory data expressed
by digital elevation maps (DEM). The main advantage of
these is the high 3D data compression which can be achieved
while preserving surface topography (Fayek & Wong, 1995).
Compression ratios of over 90% are achieved with different
types of sensory range data yielding 3D models at various res-
olutions. Arbitrary generic 3D object models are defined and
used to recognize objects and structures irrespective of the
chosen resolution level. Experiments with range data from
remote sensing, laser scanning and stereo-imaging were per-
formed with consistent results.
2 TOPOGRAPHIC COMPRESSION OF
TRIANGULAR MESH SPATIAL DATA
We are mostly concerned with the modeling of sensory range
data for practical applications. This is opposed to the mod-
eling of synthesized 3D models for visualization and anima-
tion. While model accuracy and intricate details are the main
issues in the later research area, our main focus is in the ab-
straction and interpretation issues of such scenes. Therefore,
while most of the work done on triangular mesh modeling
is towards mesh refinement and reduction of approximation
errors, our work tackles the mesh coarsening while preserving
the topography; which is the reverse problem.
The strength of our approach in comparison with previous
work (Chew, 1993, Rippa, 1992) lies in our efficient compres-
sion mechanism. More precisely, at each compression phase,
the goal is to ensure the high quality of the preserved data and
the insignificance of the discarded data. We achieve this tar-
get by the subjective selection of the information to preserve
and the removal of all other redundant information. The ma-
jority of work done in triangular mesh modeling of 3D data,
however, follows the following general pattern: (i) preselect
a certain a
bitrary init
a very coal
in the mes
tolerance |
erative me
is comput:
iterations :
associated
introducec
global opt
tions of tl
We adop!
proach fo
mesh coar
niques (C
Schroeder
points, al:
tal amour
on the au
tures in a
are compr
all remain
points are
certain qu
built with
Therefore
(which ca
Each sub:
data by r
curacy. T
initial me:
the topos
For insta
(e.g., pea
segments
3D surfac
ary of the
topograp
feature e
ysis of th
mesh. Cc
ened by ¢
feature e
embedde
above m
constrain
ample of
the trian
top left),
identifica
ure 1-toj
left) and
tures (Fi
Althougt
in rang
lar repr
ers (Zhe
graphic
mesh. If
be trian
topograj
