ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS", Bangkok, May 23-25, 2001 
142 
2.SELF-ADAPTIVE ALGORITHM 
Firstly, we demonstrate how we determine the searching area of 
the fiducial marks by the relationship of fiducial marks in details. 
Secondly we review affine transformation with an eye toward 
integrating it with the softassign correspondence engine and 
deterministic annealing technology proposed by Rangarajan A. 
et al. [7][8][9]. At last, we develop the full-blown Self-Adaptive 
Algorithm from the correspondence energy function based on the 
second step. 
2.1 Determining the Searching Area and Candidates 
Illustrated in Fig1, we can obtain the smallest rectangle area that 
contains all the fiducial marks according to camera calibration 
data. Normally, the rectangle is smaller than the image. When 
the rectangle is moved along the border of image, the traces of 
fiducial marks determine the searching range of fiducial marks. 
Suppose the width and height of the rectangle are a and b in mm; 
the width and height of the image are A, B in pixel. Then for 
fiducial mark whose coordinates are (x,y), its searching range 
are: 
A A 
[—hot ■ X - dx,—I- oc ■ X + dx] 
2 2 
B B 
[-■hay-dy,— + a-y+ dy] 
for x direction 
for y direction 
where. 
dx = (A - a ■ a)/2 
dy = (B - a b)/2 
a is pixel per mm 
• . r- 
1 1 • 
t 4 ! if 
« i i 
• i • 
• t • 
' . ' 
“1“ it 
i 
I 
1 
« 
1 
1 
1 i 1 
1 i • 
■ i 1 
Fig. 1 Fiducial and image 
Fig.2 Searching Range 
When the searching areas are determined, we can select several 
points whose correlation coefficients are locally maximal as 
candidates of the fiducial marks. And to determine fiducial from 
the candidates becomes a combination optimization problem. 
2.2 Establishment of the Energy Function with Affine 
Transformation Combining Softassign and 
Deterministic Annealing Technology 
Now the problem is: Given two point-sets {x,, ¡=1,2 N } and { v a , 
a=1,2,...,K}, where {V} denotes the coordinate of fiducial in the 
image coordinate system and {X} denotes the coordinate of 
fiducial in the pixel coordinate system. V and X are related by an 
affine transformation {d, t}. The task is to find the 
correspondence in the two point-sets. We can define a 
correspondence matrix {mai} between the two point-sets at first, 
such as following:[7][9] 
I I if point Xj corresponds to point v a 
0 otherwise 
To ensure one-to-one correspondence, each row and each 
column of M should sum to one. In the case of interior orientation, 
some candidates have no correspondence. We also put in an 
extra row and an extra column in M to take care of the outliers so 
that the row and column summation constraints still work. An 
example of the correspondence matrix is shown as following: 
Table 2. Points v, v 2 and v 4 correspond to Xi, x 2 and x 3 
respectively, and the other points are outliers. 
m ai 
x 2 
*3 
x 4 
*5 
Outlier 
h 
1 
0 
0 
0 
0 
0 
V 2 
0 
1 
0 
0 
0 
0 
Vj 
0 
0 
0 
0 
0 
1 
v 4 
0 
0 
1 
0 
0 
0 
Outlier 
0 
0 
0 
1 
1 
The energy function with both the correspondence M and the 
affine transformation (d, t) is the following: 
N K 2 
E 2D (M,d,t) = ^ Yj m ai \\ x a ~ v ad-t\\ +g(d) (1) 
1=1 u=I 
Subject to g(d) = y(a 2 +b 2 + c 2 ) 
Where M always satisfies^ 
=l./orV f e{l,2 N) 
and m ai e {0,1}. 
= \,forV a e {1,2,...,K} 
The v a is mapped as closely as possible to the x, by minimizing 
the first error measurement term, {d} (Composed of four 
separate parameters { u,Q,b,c }) is decomposed into scale, 
rotation, and two components of shear as follows: 
d = s(A)R(6)Sh l (b)Sh 2 {c) 
Where 
s(a) = 
Shfb) = 
( e h 
Sh 2 (c) = 
0 e , 
cosh(c) 
sinh(c) 
sinh(c) ^ 
cosh(c)J 
R(Q) is the standard 2x2 rotation matrix. g(d) serves to 
regularize [10] the affine transformation by penalizing large value 
of the scale and shear components, /is a constant to adjust 
regularization effect. 
Now the major problem in finding good optimal solutions to the 
point matching objective (energy function in EQ.1) is to satisfy 
the two-way constraints, i.e. the row and column constraints on 
the correspondence matrix together with the constraints that the 
individual M be either zero or one. Firstly we use deterministic 
annealing [7][8] methods to turn our discrete problem into a 
continuous one in order to reduce the chances of getting trapped 
in local minima. Deterministic annealing is closing related to 
simulated annealing except that all operations are deterministic. 
This method consists of minimizing a series of objective function 
indexed by a control parameter (temperature parameter). As the 
temperature is decreased the correspondence matrix 
approaches a permutation matrix, (with binary outlier). An 
entropy term T'V m ut log m ai is added to the energy function to 
serve this purpose. The major problem now is the point-matching 
objective subject to the usual two-way constraints on the 
matching matrix and the new constraint that the individual entries 
of M lie in the interval [0,1]. 
With the deterministic annealing technology, our two-way 
constraints is that: We are given a set of variables {Q a i} where 
Q w e R l . Then we associate a variable m ai e {0,1} with each