- 1 -
中国科技论文在线
A Subpixel Precision Image Matching-Aided Navigation
Method#
Leng Xuefei , Wang Bihui , Wu Songsen , Mao Xingyun * 5
(College of Astronautics, Nanjing University of Aeronautics and Astronautics,Nanjing )
Foundations: he Research Fund for the Doctoral Program of the Ministry of Education under Grant
()
Brief author introduction:Leng Xuefei,who was born in 1978-5 and now works at Nanjing University of
Aeronautics and Astronautics as an associate professor,is good at the research fields like Control, Navigation and
Precision Instruments. E-
Abstract: Image matching-aided navigation system has broad application prospects, according to its
prominent advantages in autonomy and high precision. In order to meet the demands of real time and
accuracy of image aided navigation system, the paper propose a subpixel precision image matching 10
algorithm by using a method called the four-dimension real matrix. At first this paper converts the
transformation of aircraft's position and attitude to transformation of two images. Then an optimal
transform matrix which is called a four-dimension real matrix can be obtained by the least square
algorithm to fit the two images. At last, the deviations of aircraft‟s position and attitude are derived
according to the proposed model. Experiments have been conducted and the results show that the time 15
consumption is within a second, translation deviations are within a pixel, and angle deviations are
within a degree, which illustrates the good performance of the algorithm and the model. As a
conclusion, the algorithm satisfies the requirements of real-time situation and accuracy of the image
matching-aided navigation system.
Key words: image matching-aided navigation; four-dimension real matrix; least square algorithm; 20
subpixel precision
0 Introduction
The image matching-aided navigation technology, which is a kind of tech designed for the
Unmanned Aircraft Vehicles‟ (UAVs) navigation process, makes use of two images to match with 25
each other and to obtain the necessary parameters of navigation[1]. One of this two images called
„the reference image‟ is stored previously in the computer by human, and another called „the
real-time image‟ is acquired in real-time situation during the flight by the equipments on board
such as high-resolution radars and photoelectric image sensors. Because of its advantages of full
autonomy, resistance to electromagnetic interference and high accuracy, the image matching-aided 30
navigation technology has been widely paid attentions and researches, and makes it one of the
most prospective navigation methods[2].
Since the real-time image used in image matching progress exists transformations of rotations,
translations and scales with respect to the reference image, and this kind of matching between
images is non-similar, the key to improve the efficiency of a navigation system is to improve the 35
precision of image matching algorithm. Otherwise, the precision of most proposed algorithms is
pixel level, which is tolerable for coarse image matching, but too low to give effective booster
actions for the demands of increasing high accuracy of positioning[3].
So far, A large number of image matching algorithms have been put forward all around the
world. Generally, the proposed algorithms are divided into four classes— model-based 40
algorithms[4], feature-based algorithms[5], algorithms based on transform domain[6] and algorithms
based on gray correlation[7]. Specially, image matching algorithms can be classified as pixel level
and subpixel level[8] according to accuracy of matching results. To apply these algorithms to
navigation system of the UAVs, the authors in [9] use sequential aerial image matching for a
UAV‟s position estimation. They employed a vision-based technique to estimate a UAV 45
- 2 -
中国科技论文在线
displacement. Based on stereo modeling, they estimate the UAV‟s displacement between two
successive aerial images. In [10] the authors use image matching for flight position calibration.
They propose an algorithm based on special landmark information for precise positioning of
aircraft. According to the transformation relation of camera and aircraft body coordinate, the
precise location of aircraft was calibrated. A similar work presents a vision system using aerial 50
image matching for UAV landing in [2], they adopt a simplification of the camera model in order
to estimate UAV position by measuring image geometry. Linear features of the runway are used.
The method of 4-D real matrix is used to set up the model of 3-D transformation of an UAV which
is connected with the transformation between two images. The least square method is applied to
calculate the optimal 4-D real matrix. Then the position and attitude are figured out with the 55
relationships of transformation. Simulation experiments are conducted on both 3-D data generated
randomly by computer and 2-D images. And results demonstrate that the algorithm is fast and
accurate, and can meet the demands of real-time situation and accuracy of an image
matching-aided navigation system.
1 Principle of the 4-D real matrix 60
A UAV can be treated as a rigid body, and movements of the UAV can be expressed as a
combination of rotations and translations. Assuming the initial position and the final position are
( , , )Tr x y z and ' ' ' '( , , )Tr x y z respectively, the UAV‟s movement from initial position to final
position can be expressed in a traditional vector equation, as shown in equation (1).
'r R r t (1) 65
Where R is a direction cosine matrix represents the rotational motion, and 1 2 3( , , )
Tt t t t is a
vector which represents the translational motion in Cartesian coordinate system.
Although the Equation(1) is a mathematical presentation of space motion of a UAV, it can be
found that space motion is divided into two parts— rotates first and translates next—which
apparently does not comply with the law of nature that rigid body rotates and translates 70
simultaneously.
To figure out this problem, homogeneous coordinates of the 4-D space which can account for
the position in 3-D space are taken into consideration in this paper. In order to use
point ' ' ' '( , , , )X Y Z W in 4-D homogeneous coordinate to express the point ( , , )X Y Z , the relation-
ship shown in equation (2) is applied. 75
' ' '
'
' ' '
, , , 0
X Y Z
X Y Z W
W W W
(2)
Usually, the value of 'W is 1. Thus, equation (1) can be replaced by equation (3).
'r P r (3)
Where ( , , ,1)Tr x y z and ' ' ' '( , , ,1)Tr x y z represents initial position and final position of a
UAV in the form of 4 dimensions, respectively. Extend the equation (3) and we will get another 80
equation.
'
11 12 13 14
'
21 22 23 24
'
31 32 33 34
x a x a y a z a
y a x a y a z a
z a x a y a z a
(4)
Let 14 1 24 2 34 3, ,a t a t a t , remaining parameters ija of equation(4) are the elements of direction
cosine matrix. Finally, we need to rewrite the equation(4) and obtain the form of matrix
multiplication shown in equation (5). 85
- 3 -
中国科技论文在线
11 12 13 1
21 22 23 2'
31 32 33 3
0 0 0 1
a a a t
a a a t
r r
a a a t
(5)
We conclude that the four dimensional real matrix can be structured easily. All we need to do is
to add the translation vector t at the right of the matrix R and a constant vector (0,0,0,1) at the
bottom of the matrix R . No matter how many times the UAV changes its position and attitude, we
just apply the equation (3) and multiply each transform matrix P orderly. Thus, the transformation 90
shown in the fig (1) can be expressed as follows.
'
, , ,S S Sr P P P r P r (6)
Where , , are the attitudes of the UAV, S , S , S are the translations along the , ,X Y Z axis,
respectively.
S
S
S
X
2O
2Y
2Z
2X
1O
1Z
1Y
O
1X
Z
Y
bZ
bX
bY
bO
S
S
S
X
2O
2Y
2Z
2X
1O
1Z
1Y
O
1X
Z
Y
bZ
bX
bY
bO
95
transformations fromOXYZ to b b b bO X Y Z
If we compute the 4-D real matrix whose elements follow the relationships shown in equation
(6), all parameters will be calculated by mathematical express- ions shown below.
2 2
23 21 22
13 33
21 22
3 1
1 3
2
arctan( )
arctan( )
arctan( )
( cos sin ) cos
cos sin
sin
m
m
m
a a a
a a
a a
S t t
S t t
S t S
(7)
2 Principle of the Least Square Algorithm 100
Assume that we are given two corresponding point sets
1 2{ , , , }nA a a a and 1 2{ , , , }nB b b b ,
we need to figure out a 4-D real matrix ( , )P R t that minimizes the objective function which
evaluates the similarity of the given point sets[11,12]. If the matrix ( , )P R t is successfully calculated,
let‟s say that the given point set A and B fit optimally. Guided by this theory, the objective
function can be defined as follows: 105
22
1
1
( , )
n
i i
i
e a P R t b
n
(8)
Each pair of corresponding points i ia b in point set A and B must follow the relationship
shown in equation(9).
( , )i ia P R t b (9)
Then the error vector of i ia b can be defined as ( , , , )
T
i ix iy iz iwe e e e e . 110
- 4 -
中国科技论文在线
11 12 13 1
21 22 23 2
31 32 33 3
( )
( )
( )
0
i i i i
i i i i
i i i i
a b b bix
a b b biy
iz a b b b
iw
x a x a y a z te
y a x a y a z te
e z a x a y a z t
e
(10)
Now we calculate each ie from 1i to i n , and equation(8) should be rewritten in the form of
equation(11).
2 2 2 2
1 1 1 1
1 1
( )
n n n n
T
i i ix iy iz
i i i i
e e e e e e
n n
(11)
In order to minimize the value of objective function 2e , we just need to minimize every item in 115
the equation (11). Here the item 2 2
1
1 n
x ix
i
e e
n
is taken as an example to illustrate the principle in
detail.
2 2 2
11 12 13 1
1 1
1 1
[ ( )] ( )
i i i i i i
n n
x a b b b a b x
i i
e x a x a y a z t x C r
n n
(12)
Where 1
i i i ib b b b
C x y z , 11 12 13 1
T
xr a a a t .Let
1 2 n
T
b b bC C C C , 1 2 n
T
x a a aa x x x .
Then we simplify the equation (12). 120
2 2
1
1 1 1
( ) ( ) ( 2 )
n
T T T T T
x ix x x x x x x x x x x
i
e e a Cr a Cr r C Cr a Cr a a
n n n
(13)
Then the partial differential equation of equation (13) should be computed, and the optimal
solution can be calculated when the differential equation equals to zero.
2 1( ) (2 2 ) 0T Tx x x
x
d
e C Cr C a
dr n
Now we obtain the final solution xˆr which minimizes the term
2 2
1
1 n
x ix
i
e e
n
. 125
1
ˆ T T
x xr C C C a
(14)
With same method, solutions of the remaining two terms in equation(11) also can be figured out.
And the solutions are provided straightway.
1
1
ˆ
ˆ
T T
y y
T T
z z
r C C C a
r C C C a
where
1 2
1 2
21 22 23 2
31 32 33 3
ˆ
n
n
T
y
T
y a a a
T
z
T
z a a a
r a a a t
a y y y
r a a a t
a z z z
(15)
In the end, the 4-D real matrix used in this paper can be acquired by equation (14) and (15), 130
which is optimal between the given point sets A and B .
3 Simulations and Experiments
The proposed image matching algorithm is tested on a computer equipped with the VC++
software, a CPU of Intel CORE(TM) i7-2670QM with dominant frequency and
memory storage. Since we have no access to stereo images of real scene and our fundamental 135
purpose is to prove the validity of the proposed algorithm, the 3-D data used as the characteristic
points of the reference image are generated randomly and the character points of the real image
are obtained by a kind of transform operation on the previous data. Furthermore, experiments on
- 5 -
中国科技论文在线
the 2-D images (values in Z axis are zero) are conducted both by the proposed model and partial
hausdorff distance algorithm. 140
As shown in , (a) represents character points of reference image A which contains 50
points with red symbol „o‟. (b) represents character points of real- time image B which are
acquired with certain rotations and translations( , S S ) with respect
to the points in (a) and is shown with blue symbol „+‟. (c) shows the character points of
image A and image B in the same figure before matching and (d) shows the result after 145
matching. The transform parameters are also calculated through image matching process with a
total time consumption of and these numerical parameters are , ,
, , , .
(a) image A (b) image B 150
(c) before matching (d) result of matching
3-D image matching process
In order to demonstrate the performance of the proposed algorithm, another four experiments
have been conducted with the same method, the raw parameters and the calculated parameters are 155
listed in Table 1.
Tab. 1 parameters of conducted experiments
No given , , / and , ,S S S obtained , , / and , ,S S S max abs deviations and time
consumption
1 (,,) (,,) (, , ) (,,) °, ,
2 (,,) (,,) (,,) (,,) °, ,
3 (,,) (,,) (,,) (,,) °, ,
4 (,,) (,,) (,,) (,,) °, ,
From the we can get the information that the maximum absolute deviations of angles
- 6 -
中国科技论文在线
and translations are less than a degree and a pixel respectively, and time consumption of running
the algorithm is about one second. A conclusion that the performance of the algorithm has already 160
met the demands of the UAVs‟ navigation system can be reached.
Furthermore, another group of experiments have been conducted on the 2-D images based on the
theory to support the conclusion. Firstly, an image Lena is chosen as an experimental subject. As
shown in , (a) is a raw image of Lena. (b) and (c) are the edge character
image of raw image of Lena and that edge character image with artificial transformations of 165
rotations ( , 0 ) and translations ( 0S , S )respectively. (d)
shows the character points of (b) and (c) with red symbol „*‟ and blue symbol „+‟
respectively. (e) shows the result of partial hausdorff distance algorithm whose threshold is 8
and fractions are , and the translational parameters computed are -1 and 7. (f) shows the
result of matching. The transform parameters are calculated with a total time consumption of 170
and these numerical parameters are 0 , 0S ,
,
, .
(a) image of Lena (b) edge character image of Lena (c) image of Lena after transformation
(d) before matching (e) result of Partial Hausdorff Distance (f) matching result 175
image matching process of Lena
As shown in , (a) and (b) are two images of real scene taken by a same camera.
Since the problem of camera shake exists, there are uncertain relationships between (a) and
(b), and we consider these relationships to be rotations and translations. Then our method can
be applied to this situation. (c) and (d) are the edge character images of (a) and 180
(b) respectively, which are both extracted by canny operator. (e) shows the character
points of (c) and (d) while (f) and (g) show the result of matching. All of
them use the red symbol “*” to indicate points of (c) and the blue symbol “+” to indicate
points of (d). Obviously, result shown in (g) is much better than (f). The
translational parameters computed by partial hausdorff algorithm are -1 and 4, while transform 185
parameters computed by the proposed model are 0 , 0S ，
, ,
, and the time consumption is .
(a) image of real scene (b) another image of real scene (c) edge character of (a) (d) edge character of (b)
- 7 -
中国科技论文在线
190
(e) before matching (f) result of Partial Hausdorff Distance (g) matching result
image matching process with real scene images
4 Conclusion
In this paper an image matching algorithm in subpixel level has been proposed, which mainly
includes two portions—a space transformation model of a rigid body is established based on a 195
mathematical method named the 4-D real matrix, and the least square method is implemented. The
results of all of conducted experiments show that the time consumption of image matching process
is about one second or less, the deviations of translations in all directions are within a pixel, and
deviations of rotations are within a degree. Finally, a conclusion can be reached certainly that the
algorithm performs well and can satisfy the requirements of real-time situation and accuracy of the 200
image matching-aided navigation system.
References
[1] Zhang Tao, Yang Li-Mei. Research on Real-time Matching Algorithm of Airborne Image Aided Navigation[J].
Computer Measurement & Control, 2010, page 2596-2598.
[2] SHEN Ning, TANG Da-quan, LI Fei. Image Processing, Position and Attitude Estimating of Visual Navigation 205
on UAV[J]. Electro-optic Technology Application, December, 2012, page 60-64.
[3] Xiong Zhi, Liu Jian-ye, Leng Xue-fei. Research on Precise Image Matching Algorithm of Scene Image Aided
Navigation System[J]. Journal of Astronautics, July, 2006,page 680-685.
[4] Hail Mallouche, Jacques De Guise, Yves Goussard. Model-Based Multiple Active Contours Matching for
Radiographic Images[C]. IEEE-EMBC and CMBEC, Theme2: Imaging, 1995,page 415-416. 210
[5] Ann Theja Alex, Vijayan K. Asari, Alex Mathew. Gradient Feature Matching for Expression Invariant Face
Recognition using Single Reference Image[C]. 2012 IEEE International Conference on Systems, Man, and
Cybernetics, October 14-17, 2012, page 851-856.
[6] Yang Xidong,Location Algorithm for Image Matching Based on Frequency Domain Analysis[J].Telecom
Power Technology, July 25,2012,page 20-43. 215
[7] GAO Xiaofeng, SHI Zhaohui,An Improved Image Matching Algorithm Based on Gray Value
Projection[J].Aeronautical Computing Technique,Nov. 2012,page 85-91.
[8] Mamoru Miura, Shuji Sakai, Shoichiro Aoyama, Jumpei Ishii, et al. High-Accuracy Image Matching Using
Phase-Only Correlation and Its Application[C]. SICE Annual Conference 2012, August 20-23, 2012, page
307-312. 220
[9] Andrea Canhoto, Elcio Hideiti Shiguemori, Marco Antonio Pizani Domiciano. Image Sequence Processing
Applied to Autonomous Aerial Navigation[C]. 2009 IEEE International Conference on Signal and Image
Processing Applications,2009,page 496-499.
[10] WANG Mingang, SUN Chuanxin. Algorithm and Simulation of Flight Position Calibration Based on Image
Matching[J]. Computer Simulation, May 2012, page 86-89. 225
[11] Steven Gold, Anand Rangarajan, Chienping LU, et al. New Algorithms for 2D and 3D Point Matching: Pose
Estimation and Correspondence[J]. Pattern Recognition, 1998,page 1019-1031.
[12] SHIH-CHANG, FANG-HSUAN CHENG, WEN-HSING HSU and GUO-ZUA WU. Fast Algorithm For
Point Pattern Matching Invariant to Translations, Rotations And Scales Changes[J].Pattern Recognition,1997,page
311-320. 230
一种亚像素精度图像匹配辅助导航方
法
冷雪飞，王碧辉，吴松森，毛星云 235
（南京航空航天大学航天学院）
摘要：图像匹配辅助导航系统具有自主性和高精度的突出优点，具有广泛的应用前景。针对
- 8 -
中国科技论文在线
图像匹配辅助导航系统的实时性和精确性要求，本文研究了一种基于四维实数矩阵的亚像素
级精确图像匹配算法。首先将飞行器的位置和姿态变换转换成两幅图像之间的阵变换，再通
过最小二乘算法拟合得到两幅图像之间的最优的四维实数变换矩阵，最后根据模型推导的关240
系推算出飞行器的姿态角和位置偏移量。实验结果表明，本文研究的图像精确匹配辅助导航
方法匹配耗时在 秒内，匹配获得的平移误差在 1 个像素以内，旋转角度误差在 度以
内，能满足图像匹配辅助导航系统对图像匹配的实时性和准确性要求。
关键词：图像匹配辅助导航；四维实数矩阵；最小二乘算法；亚像素精度
中图分类号：T P391. 41 245
