Similar considerations for the translational parameters
lead a request of 7.2- 10!? cells capable to store the num-
ber of solutions. Again, it appears that the approach is
highly impractical.
The problems just identified are caused by the attempt
to determine all seven transformation simultaneously.
Let us pursue the other extreme and calculate the param-
eters sequentially, in an iterative fashion. Consequently,
the accumulator array will be one dimensional and the
memory problem disappears. The total number of point
to surface patch combinations reduces to m X ns with
m the number of points in set S? and n, the number of
surface patches, e.g. triangles, in S,. Since this is now
an iterative process that has to be repeated for every pa-
rameter, the computational complexity is proportional
to m x n, x 7 x maximum number of iterations.
The method proceeds along the following steps:
1. Select one of the parameters, e.g. ty. The cur-
rent values of the other parameters are considered
constants. Initialize the 1-D accumulator array for
parameter tx.
2. Pick point q; in set S».
3. Select surface patch SP; in S,, e.g. defined by
points Pa,Pp,Pc and compute parameter ty by
solving the coplanarity condition.
4. Update accumulator array.
5. Repeat steps 3 to 4 until all plausible point to sur-
face patch correspondences have been explored.
6. Repeat steps 2 to 5 until all points q have been
evaluated.
7. Analyze accumulator array for a distinct peak. Up-
date parameter tx with the peak value.
8. Repeat steps 1 to 7 until all parameters have been
updated.
9. Repeat the entire procedure if the parameters
changed more than a predefined threshold.
This procedure can be executed under a coarse-to-fine
strategy that controls the precision of the solution (dis-
crete interval) and the permissible range. As one pro-
ceeds from coarse to fine, the range becomes smaller as
well as the discrete solution steps. The dimension of the
accumulator array may remain constant.
So far we have determined the transformation param-
eters iteratively, one by one; we have yet to solve the
surface matching problem. For explicitly labeling the
correct point to surface patch correspondence we sim-
ply repeat the procedure described above. This time
we already know the correct transformation parameters,
however. Hence, whenever a correspondence is found
with the correct solution (correct accumulator cell), the
point is labeled accordingly. Now, as a mandatory final
step we could determine the transformation parameters
simultaneously, for example by the adjustment proce-
dure described in Schenk (19992). Like every non-linear
adjustment problem, reasonable approximations are re-
quired. Of course, the iteratively determined transfor-
mation parameters are excellent approximations.
International Archives of Photogrammetry and Hemote Sensing, Vol. 32, Part 3W14, La Jolla, CA, 9-11 Nov. 1999
An important aspect in comparing surfaces is concerned
with detecting blunders in the data. It is well known that
undetected blunders that participate in a least-squares
adjustment may greatly influence the solution. How ro-
bust is our proposed approach in this respect? Step 3
of the procedure computes values for parameter tj, with
point q; and all surface patches. The values are entered
into the accumulator array. Suppose now point q; is
wrong (blunder). As a result, wrong parameter values
are computed and cells in the accumulator array are in-
cremented which are separated from the peak. It fol-
lows that blunders have no impact on the solution—an
important property of our approach that can be applied
to detect blunders.
Let us again analyze the final step, involving the explicit
labeling of matches. Points that remain unlabeled have
never contributed to the correct solution of a transfor-
mation parameter. Such points are obviously not part
of a consistent surface description; they can be labeled
as blunders. This allows for change detection. Here, we
would analyze the spatial distribution of blunders and
signal a significant difference between the two surfaces
whenever blunders are locally concentrated.
determine transformation parameters
by following steps 1 through 7
surface matching
blunder detection
Y
simultaneous adjustment of
transformation parameters
error analysis
Y
applications: change detection,...
Figure 3: Schematic diagram of surface matching, blun-
der and change detection. The iterative determination
of the transformation parameters is accomplished by a
voting scheme in the parameter space, described above
by steps 1-9. Surface matching is obtained by repeating
the procedure, but now with known parameters. At the
same time, blunders are detected and labeled accord-
ingly. A mandatory step is the simultaneous adjustment
of the transformation parameters, using the previous re-
sults as approximations. Other steps may follow, for
example error analysis and applications such as change
detection.
In order to te
proposed surf
several exper
section briefly
5.1 Tests wi
Fig. 4 depicts
tation used ir
sists of the p
the other han
SP,» SPs.
the surface p:
as the transfo
purpose of re
spondences.
amined as a fi
Se
Z o
of?
Figure 4: Synt
the proposed
by the five su
is represente
correct corres
The initial val
for the angle:
and 40% for
termined corr
for the scale f.
the accumula
respondences
(every point q
peak with a v
correct corres
Not all param
examination :
along the Y-
mined from a
normals have
array has a |
corresponder
Finally, Fig. 6
tion of numb