A, 9-11 Nov. 1999
comparison problem by
ts S, and S» are in dif-
assume that there is a
between the two sets but
1 example would be the
re related by a 3-D simi-
seven parameters should
al points. This situation
sets that may be affected
errors. Calibrating laser
e the surface defined by
ted system is compared
urface). The expected er-
an affine transformation,
of that model—the cali-
ermined with the method
and Csathó (1999)).
any functional relation-
be used in our proposed
-D similarity transforma-
llowing discussions. The
be extended by subject-
. With the example of a
ave
q; +1 (3)
e translation vector, and
iatrix. We can solve the
'rocedure using Eq. 2 as
ak (19992) for details).
mine transformation pa-
stances d; according to
is implies that the differ-
s are assumed to be ran-
tances after establishing
are residuals.
m, however. To compute
ence between the points
Ast be established. This
r trivial because the two
systems. The proposed
m is based on searching
pace by a voting scheme.
irst introduce the notion
scheme by way of an ex-
er Space and Voting
ne
parameters by a voting
lough (1962). Variants of
ugh technique or Hough
the notion of parameter
/ay of an example. Sup-
cting points that happen
ius. Fig. 2(top) depicts a
ite cumbersome to solve
nain. Instead, we repre-
sent it in the parameter space, motivated by the follow-
ing considerations.
50 T T T
1 1 | 1 ! 1 1 | 1
1 | | ! 1 1 | ! |
mt mdm bed ee de ee dee (Ym fe
1 ! | ! 1 ! ! qi
| ! | 1 1 1 i 1
ld si b NN rS RIT | 1
40 1 i i eo | 1 [a EET
1 1 ! | 1 1 1 ! !
| 1 | 1 1 1 | | 1
Bo mmm of me mm ef a fn me a ef fm fn fe ee fe
1 1 ! 1 1 1 1 ! 1
0 1 1 i | 1 I 1 ! 1
Eh ee ALL ALL LE
AA Tr
| 1 ! 1
x pa iA ! i
i 1 i T 1 T ATTE
1 | : 1 1 | | ! !
1 1 ! | ! 1
> BO UN AT E
| ! i 1
1 ! | 1 | i 1 1 1
ee eg]
1 ! 1 ! | 1 1
| 1 1 1 ! | 1 1
| ! ! ! i | !
10 FO m=]
! | | 1 1 | ! 1 1 1
! 1 ! 1 1 ! 1 ! 1
HA AA
1 ! ! ! | | 1 !
! ! | 1 ! ! | | |
0 L L L 1 J J
0 10 20 30 40 50
v - axis
Figure 2: Illustration of finding circles through data
points. À point in the spatial domain (top) corresponds
to a circle in the parameter space (bottom) and vice
versa. Here, the intersection of circles determines the
center of the sought circles in the spatial domain. The
intersection of four circles at u = 20,v = 25 identifies
points 1,2,3 and 5 as belonging to circle whose center c
in the spatial domain is c = [20,25]".
A circle of radius r can be defined by
(x —1u) +(y-u 1 -0 (4)
with x, y the spatial variables and u,v the parameters
of the circle (center) in the spatial domain. Let us now
introduce the parameter space, represented by the coor-
dinate system u, v. After a moment's thought we real-
ize that in this representation, variables and parameters
switch roles; u,v are now variables and x,y become
parameters. A point x;, y; in the spatial domain corre-
sponds to a circle in the parameter space, centered at
Xi, Vj. What do we gain? For every point in the spatial
domain there exists a circle in the parameter space and
vice versa. The intersection of circles define centers of
circles in the spatial domain—a simple solution of our
International Archives of Photogrammetry and Remote Sensing, Vol. 32, Part 3W14, La Jolla, CA, 9-11 Nov. 1999
original problem. The number of intersecting circles in
the parameter space is directly related to the number of
points that lie on this circle.
The Hough method is usually implemented by a so called
accumulator array which is an n-dimensional, discrete
space where n is identical to the number of parameters.
In our example with circles of known radii, the accumu-
lator array is two-dimensional. Each circle is discretely
represented in the parameter space. To keep track of all
the circles, we simply increment the cells that are turned
on by every circle. After having processed all points in
this fashion, we analyze the accumulator array and de-
termine the number of hits per cell. Every hit casts one
vote for a point lying on that particular circle. The cell
with the maximum number of hits, located at Umax, Vmax,
yields the center of a circle in the spatial domain that
passes through max points. Similarly, other peaks in
the accumulator identify additional circle centers.
In order to identify the points belonging to the circles
found by analyzing the accumulator array, the procedure
is repeated. This time we already know which accumu-
lator cells yielded a circle. Whenever a point happens to
turn a peak cell on, it is immediately labeled.
4 Surface Matching in Parameter Space
in this section we apply the concept of determining
the parameters by a voting scheme to solve the sur-
face matching problem as stated in Sec. 2.2. To deter-
mine the seven parameters of the similarity transforma-
tion, seven equations of the type of Eq. 2 are required.
Since there is no redundancy, we introduce the condition
d; = 0. That is, Eq. 2 becomes the coplanarity condi-
tion. Theoretically, we can select seven points q in set S»
and match them with all possible surface patches of S;.
For every such combination, a set of seven equations is
found and solved. The discretized solution yields those
cell addresses of the 7-D accumulator array that need
to be incremented. Once all possible combinations are
explored, we select again seven points q and repeat the
procedure. The correct solution will emerge as a peak
in the accumulator array.
Of course, this trial and error approach is not practical at
all. To explore all combinations leads quickly to combi-
natorial explosion. The maximum number of combina-
tions of points q with surface patches is roughly n - m.
We need seven independent combinations with repeti-
tions allowed. Thus the total number of solutions s is
num!
pi ELIO 5
Sr THIS Nn) G)
With a modest number of n = m = 100 we get = 10!! so-
lutions, a vivid impression of the combinatorial problem
indeed!
The memory request of the 7-D accumulator array cre-
ates another problem. Even restricting the solution
space to plausible solutions, the size of the parame-
ter space may get astronomical, depending on the dis-
cretization size. Take ten arc second for the three ro-
tation angles and a range of +10°, for example. Each
of the three parameter axes would require 7,200 units.