143 
ISPRS, Vol.34, Part 2W2, "Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
m„ 
/ A. TI 
2>l 
k+i ¿v+1 
Q w , such that =1 and V„^ m al =1. The aim is to 
0=1 i=l 
find the matrix M that minimizes the following:[7] 
£(^) = 
/=! a=l 
This is known as the assignment problem, a classic problem in 
combinatorial optimization [11]. This problem usually has two 
good solutions: softmax and softassign. Softassign has clear 
advantages in accuracy, speed, parallelizabllity and algorithmic 
N K 
simplicity over softmax and a penalty term ( * '^ 22 m ™ ) in 
/=1 a=l 
optimization problem with two-way constraints. [12]. 
End D 
End C 
Begin E (Update pose parameters by coordinate 
descent) 
Y=MX (calculate current correspondence 
points)( Pay attention to this) 
Update (d, t) using Least squares for affine 
transformation with Y and V 
End E 
End B 
T <-T*T r 
End A 
Putting everything together, the final energy function that is 
actually minimized by our algorithm is as follows: [7][9] 
E{M,d,t) = YY.m ai \\x i -v a d-t\\ 2 
i=l <3=1 
+ 1 2 2 log m *i~ (10 7 2 m * (2) 
/=1 a= I /=1 a=1 
+ Atrace[(d -I) 1 (d — /)] 4- g(d) 
Where m a , e[0,l] satisfies: 
jV+1 
2 m ai = f° r a = K ’ 
/=1 
and 
K+i 
2 m ai = hfori = 1,2,..., N. 
a-1 
Let’s briefly go through all the components of the energy function. 
The first term is just the error measure term .The second term is 
an xlogx entropy barrier function with the temperature 
parameter T. The entropy barrier function ensures positivity of M. 
[7]. The third term with a parameter (1.0/T) is used to guard 
against null matches. The fourth term is to constrain the affine 
mapping d by penalizing the residual part .The fourth term is 
serving to regularize the affine transformation by penalizing large 
value of the scale and shear components. 
2.3 Pseudocode for the Algorithm 
The pseudocode for the adaptive algorithm is as follows (using 
the variables and constants defined below)[7][9] 
Variable and constant definition can be found as following 
X the coordinate of fiducial mark in the pixel coordinate system, 
N number of fiducial mark in the pixel coordinate system 
\/the coordinate of fiducial mark in the image coordinate system 
K number of fiducial mark in the image coordinate system 
T control parameter of the deterministic annealing method 
T 0 initial value of the control parameter T 
Tf minimum value of the control parameter T 
T r rate at which the control parameter T decreases (annealing 
rate) 
E (M, d, t) point matching objective function ( EQ.(2)) 
m ai matching matrix variables 
Q ai partial derivative of E (M, d, t) with respect to m ai 
lo Maximum of iterations allowed at each value of the control 
parameter T 
/, Maximum of iteration allowed row and column normalizations 
The criterion for convergence for step D is 
N K 
22i ~^ £] ' and £] is a constant c,ose to zer ° 
/=1 a=l 
The criterion for convergence for step B is Vd |< e 2 , and 
e 2 is also a constant close to zero. 
3.EXPERIMENTS 
3.1 A Real Image Examples 
The algorithm is tested on some close-range photographs. 
These photographs are 6000 pixels x 4500 pixels taken by a P31 
metric camera. The fiducial marks’ distribution is showed in Fig.3. 
The image window of four fiducial marks of this camera are 
depicted in Fig.4(a,b,c,d). It can be seen these fiducial marks are 
not all good. Two of them merge in the objects; one of them is 
very bad. In this experiment, 12 points (Table 3) are found as 
candidates of fiducial marks. 
Initialize d, t, T 0t M, X, V, N, K, T r 
Begin A: Do A until (T>T f ) 
Begin B: Do B until d converges or of iteration >l 0 
Begin C (update correspondence parameters 
softassign): 
dE(M,d,t) 
by 
0« 
exp( 
dm 
Q, 
Begin D Do D until M 
iteration > /1 
converges or of 
Update M by normalizing across all rows 
/<v+i 
» 1 „ * 0 / V' 1 » 0 
m ai 2^ m cu 
Update m by normalizing across all columns 
The Self-Adaptive Algorithm is set up in the following manner. 
The T 0 is set so that it is slightly more than twice as long as the 
longer border of the film to allow all possible matching. T r 
(annealing rate) is 0.93. T is half of the longer length of the film. 
The correspondence matrix M is set to zero, and the outliers row 
and column are endowed with a value proximate to zero, our 
transformation variables d is a unit matrix and t is zero. The 
alternating updating of correspondence M and transformation d 
is repeated for 5 times, which is usually sufficient for 
convergence after which the temperature (7) decreases with T r . 
After T<T f , the correspondence matrix got is listed in Table 4. 
A clean-up heuristic is necessary because the algorithm does not 
always converge to a permutation matrix. In the test, a very 
simple heuristic is used. We just set the maximum element in 
each row to 1 and all others to 0. From table 4, it can be seen 
that a correct one-to-one correspondence is got with the 
algorithm. 
3.2 Example with Similar Objects Near the Fiducial Mark