×

You are using an outdated browser that does not fully support the intranda viewer.
As a result, some pages may not be displayed correctly.

We recommend you use one of the following browsers:

# Full text

Title
The 3rd ISPRS Workshop on Dynamic and Multi-Dimensional GIS & the 10th Annual Conference of CPGIS on Geoinformatics
Author
Chen, Jun

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:
£(^) =
/=! a=l
This is known as the assignment problem, a classic problem in
combinatorial optimization . 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. .
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: 
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.
. 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)
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

exp(
dm
Q,
Begin D Do D until M
iteration > /1
converges or of
Update M by normalizing across all rows
/ » 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 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