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.