The traditional approach to this problem is to interpo-
late both data sets to a regular grid, followed by deter-
mining the z-differences at the grid posts. There are
problems with this simple approach, however. First, the
z — differences that serve as a comparison criteria are af-
fected by interpolation errors. More critical is the re-
striction to compare differences only along the z—axis.
Take the extreme example of a vertical surface; here
z — differences would be meaningless to capture surface
differences.
An improved solution is to compute the difference be-
tween the two sets along surface normals and at the orig-
inal point location, to avoid interpolation. Suppose now
that local surface patches for S, are generated. The sim-
plest approach would be to create a TIN model—quite
adequate for laser surfaces. Let surface patch SP in Si
be defined by the 3 points Pa, Pp, Pc and let q; be a point
in the second set. Then, Eq. 2 is the shortest distance
between a point in the second set to the correspond-
ing surface patch, as illustrated in Fig. 1. If we want to
impose the condition that q; lies on the surface patch
(coplanarity condition), then we have D = 0 in Eq. 1.
Xqdi Yq: zqi 1
Dis XPa YPa ZPa | (1)
XPb. YPb ZPh. |
XP: "Vpc Zpc .1
D
dj m EL (2)
JD? + D3 + D2
Figure 1: Illustration of comparing two data sets that de-
scribe the same surface. The points of one set are shown
by circles. Solid circles represent a few points of the sec-
ond data set. The comparison is achieved by computing
the shortest distances d; from points in one data set to
the corresponding surface patches of the other data set,
here shown as triangles.
We call the association of point q; with the proper tri-
angle pa, Py, Pc the matching problem in this paper. In
the simple case of both data sets being registered in
the same reference system, the matching can be solved
in the x—, y -—coordinate plane by selecting that surface
patch which contains point q; within its perimeter.
International Archives of Photogrammetry and Remote Sensing, Vol. 32, Part 3W14, La Jolla, CA, 9-11 Nov. 1999
2.2 General Case
We generalize now the surface comparison problem by
allowing that the two data sets S, and S» are in dif-
ferent reference systems. We assume that there is a
known functional relationship between the two sets but
with unknown parameters. An example would be the
knowledge that the two sets are related by a 3-D simi-
larity transformation; and the seven parameters should
be determined without identical points. This situation
exists when merging two data sets that may be affected
by uncompensated systematic errors. Calibrating laser
systems is a classical case; here the surface defined by
laser points from an uncalibrated system is compared
with a known surface (control surface). The expected er-
rors must be modeled, e.g. by an affine transformation,
and the unknown parameters of that model—the cali-
bration parameters—can be determined with the method
described here (see, e.g. Filin and Csathó (1999)).
It is important to realize that any functional relation-
ship between the two sets can be used in our proposed
matching scheme. We use a 3-D similarity transforma-
tion as an example to aid the following discussions. The
solution sketched above must be extended by subject-
ing S» to the relevant function. With the example of a
similarity transformation, we have
q; =s-R-q;+t (3)
where s is the scale factor, t the translation vector, and
R a 3-D orthogonal rotation matrix. We can solve the
parameters in an adjustment procedure using Eq. 2 as
the target function (see Schenk (1999a) for details).
Such a procedure would determine transformation pa-
rameters that minimize the distances d; according to
the least-squares principle. This implies that the differ-
ences between the two surfaces are assumed to be ran-
dom; hence, the remaining distances after establishing
the transformation parameters are residuals.
We are faced with a new problem, however. To compute
the distances dj, a correspondence between the points
q; and the surface patches must be established. This
matching problem is no longer trivial because the two
sets are in different reference systems. The proposed
solution to this intricate problem is based on searching
the solution in the parameter space by a voting scheme.
Before delving into details we first introduce the notion
of parameter space and voting scheme by way of an ex-
ample.
3 The Notion of Parameter Space and Voting
Scheme
The method of determining parameters by a voting
scheme was first proposed by Hough (1962). Variants of
this approach are known as Hough technique or Hough
transform. Let us introduce the notion of parameter
space and voting scheme by way of an example. Sup-
pose we are interested in detecting points that happen
to lie on a circle of known radius. Fig. 2(top) depicts a
cloud of points. It would be quite cumbersome to solve
this problem in the spatial domain. Instead, we repre-
Inter
sent it in the |
ing considera
5(
4(
3(
y - axis
2(
1(
50 |
40 |
30 |
v - axis
20 }
10 |
Figure 2: llli
points. A poit
to a circle in
versa. Here,
center of the
intersection o
points 1,2,3 a
in the spatial
A circle of rad
with x, y the
of the circle (
introduce the
dinate system
ize that in thi:
switch roles;
parameters. /
sponds to a c
Xi, Vi. What c
domain there
vice versa. Tl
circles in the
