1strial
ation,
some
mator
e the
using
local
sitive
is of
nition.
it two
ting a
rfaces
le, in
d and
pochs
ins of
each
ficult,
ering,
ble in
faces,
. With
Isis a
ed by
them
til the
ormed
1993)
(ching
que to
large
large
1996)
ecting
their
indom
rence
F local
Zhu Xu
2 SURFACE MATCHING
2.1 Review of Matching Methods
As mentioned above, both Karras et al. (1993) and Pilgrim (1991) used in their studies the surface matching method
developed by Rosenholm and Torlegard (1988). However, to make the choice of matching method sensible, it is
necessary to review various methods for surface matching and analyze their characters.
According to the abstraction level of information used for matching, matching method could be divided into two
categories [Zhang 1994]: primitive-based approach and surface-based approach. Similar classification of matching
methods is given by Nevatia (1996), in which primitive-based approach corresponds to feature-based method and
structure-based method. The so-called structure-based method is characterized by considering not only individual
feature properties but also some explicit relations between them and by employing graph matching techniques.
In the primitive-based approach, features in the sense of differential properties are first extracted and then
correspondences between features are established through comparing their properties and finally transformation
parameters are computed using these correspondences generally by least squares method. Features used can be points of
maximal curvature (Goldgof et al.1988), contours characterizing surface variation (Rodriguz and Aggarwal 1990)
(Stein and Medioni 1993) and surface patches acquired by segmenting surface according to sign variation of curvature
(Lee and Milios 1990) (Fan 1990).
Generally speaking, the primitive-based matching approach is capable of dealing with large orientation differences
between surfaces and is preferable for the purpose of object recognition [Zhang 1994] due to the concise information
used for matching, which are invariant to orientation differences. However, the large amount of process needed for
feature extraction and correspondence building makes them computationally inefficient. Further, since the procedure of
extracting features is highly sensitive to random errors and the sudden variations of surface, the primitive-based
approach yields only rough estimates of transformation parameters. What's more, feature-based approach relies on
existence of distinctive features and may be impractical for smooth surfaces. The structure-based approach seems to be
restricted to recognition of objects whose surface can be decomposed into planar and quadric patches.
Complexity of the matching task can depend greatly on what constraints from prior knowledge can be placed [Nevatie
1996]. This gives room for surface-based approach. Given that the orientation difference between the two images to be
matched is small, match could be achieved by finite trials of simply moving one image relatively to the other and
measuring their coincidence by some measurements. This is the basic idea of correlation matching method for intensity
images. Such idea is not directly applicable to surface matching where the moving has six degrees of freedom, each
three for rotation and translation, much more than two degrees of freedom considered in the case of intensity image
matching. Reduction of degrees of freedom involves use of differential information like the feature-based approach.
In the correlation matching method, one surface is artificially moved around to match with the other. A procedure of
automatically and directly moving to solution can serve as a substitute for artificial movement if some objective
function of minimizing the distances between the two surface is imposed on the matching process as the power of
movement. The energy function derived from a data compatibility constraint and a smoothness constraint is used in the
work of Szeliski (1988). Sum of distances between temporarily paired points is minimized in the ICP algorithm
developed independently by the Besland Mckay (1992), Zhang (1994) and Chen and Medioni (1992). Sum of Z
coordinate differences between pairs of points, which lie on the two surfaces but are of the same (x, y) coordinates, was
minimized in [Rosenholm and Torlegard 1988]. (For briefness, we call this method the LZD method). For other similar
methods, refers to [Besl and Mckay 1992] and [Zhang 1994]. We call these matching methods least squares matching
based on sample points for they are usually formulated as a least squares problem and they use directly the coordinates
of all sample points of DEM or range data.
Two obvious benefits of least squares matching based on sample points are their efficiency and precision: no process for
extracting features is needed; no reduction of precision will be caused by using derived information in place of original,
precise information; all information are used and the redundancy is rather high. The main disadvantage is that they are
only suitable for matching surfaces between which the orientation difference is small. However, we think the orientation
difference can usually be limited within a small range in most applications of surface difference detection by making
the surfaces of concern approximately orthogonal to range data acquiring systems without or with little extra work.
Therefore, such methods are preferred in our study. Another benefit of least squares matching methods, as will be seen
in the following sections, is that they can be readily reformed in order to detect surface difference.
2.2 The LZD surface matching Algorithm
The ICP and the LZD matching algorithms are employed in our study for the reasons given above. And the LZD
algorithm gave better results than ICP did. Therefore only LZD algorithm is introduced here.
Resenholm and Torleghed (1988) developed the LZD algorithm originally for the purpose of absolute orientation of
International Archives of Photogrammetry and Remote Sensing. Vol. XXXIII, Part B3. Amsterdam 2000. 1001
