×

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

ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS", Bangkok, May 23-25, 2001
142
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. . 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:
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  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  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