A fast matching algorithm for the images with large scale disparity

Shichu Chen; Zhiqiang Wang; Yan Ren

doi:10.3934/mfc.2020021

Article Contents

2020, Volume 3, Issue 3: 141-155. Doi: 10.3934/mfc.2020021

This issue Previous Article Next Article Summation of Gaussian shifts as Jacobi's third Theta function

A fast matching algorithm for the images with large scale disparity

1.
Computer Science Department, Curtin University, Perth, Australia
2.
Automation College, Shenyang Aerospace University, Liaoning, China

^* Corresponding author: Shichu Chen
^* Corresponding author: Shichu Chen

Received: October 2019

Revised: March 2020

Published: August 2020

Abstract / Introduction Full Text(HTML) Figure(18) / Table(3) Related Papers Cited by

Abstract

With the expansion of application areas of unmanned aerial vehicle (UAV) applications, there is a rising demand to realize UAV navigation by means of computer vision. Speeded-Up Robust Features (SURF) is an ideal image matching algorithm to be applied to solve the location for UAV. However, if there is a large scale difference between two images with the same scene taken by UAV and satellite respectively, it is difficult to apply SURF to complete the accurate image matching directly. In this paper, a fast image matching algorithm which can bridge the huge scale gap is proposed. The fast matching algorithm searches an optimal scaling ratio based on the ground distance represented by pixel. Meanwhile, a validity index for validating the performance of matching is given. The experimental results illustrate that the proposed algorithm performs better performance both on speed and accuracy. What's more, the proposed algorithm can also obtain the correct matching results on the images with rotation. Therefore, the proposed algorithm could be applied to location and navigation for UAV in future.

Keywords:

UAV,
SURF,
matching,
location,
scale.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Full Text(HTML)

Figure 1. A region of intensities can be calculated in three additions on integral image

Download: Full-size image PowerPoint slide

Figure 2. Left to right: templates of Gaussian second order partial derivative $ L_{yy} $ and $ L_{xy} $ separately; Approximations of corresponding box filters $ D_{yy} $ and $ D_{xy} $ respectively

Download: Full-size image PowerPoint slide

Figure 3. Filters $ D_{yy} $ (above) and $ D_{xy} $ (below) with two size: $ 9\times 9 $ templates (left) and $ 15\times 15 $ templates (right)

Download: Full-size image PowerPoint slide

Figure 4. Filters and octaves permutation

Download: Full-size image PowerPoint slide

Figure 5. Scale space

Download: Full-size image PowerPoint slide

Figure 6. $ 3\times 3 \times 3 $ neighbourhood non-maximum suppression

Download: Full-size image PowerPoint slide

Figure 7. Haar wavelet templates in $ x $ and $ y $ directions

Download: Full-size image PowerPoint slide

Figure 8. A sliding sector to find out dominant orientation

Download: Full-size image PowerPoint slide

Figure 9. Descriptor and sub-region divisions

Download: Full-size image PowerPoint slide

Figure 10. Different local characteristics

Download: Full-size image PowerPoint slide

Figure 11. Flowchart of fast matching algorithm

Download: Full-size image PowerPoint slide

Figure 12. (b) and (d) is the UAV image A; (a) and (c) are the matched tiles with Image A via Ao' method and the proposed method respectively

Download: Full-size image PowerPoint slide

Figure 13. (b) and (d) is the UAV image B; (a) and (c) are the matched tiles with Image B via Ao' method and the proposed method respectively

Download: Full-size image PowerPoint slide

Figure 14. (b) and (d) is the UAV image C; (a) and (c) are the matched tiles with Image A via Ao' method and the proposed method respectively

Download: Full-size image PowerPoint slide

Figure 15. (b) and (d) is the UAV image D; (a) and (c) are the matched tiles with Image A via Ao' method and the proposed method respectively

Download: Full-size image PowerPoint slide

Figure 16. Diagram of the angle between $ \overline{AB} $ and Google map direction

Download: Full-size image PowerPoint slide

Figure 17. The matching results for Image B with rotations

Download: Full-size image PowerPoint slide

Figure 18. The matching results for Image C with rotations

Download: Full-size image PowerPoint slide

Table 1. Pseudo-code of fast matching algorithm

Algorithm: Fast matching algorithm for images with large scale disparity
Input: UAV aerial image $ I_{UAV} $, satellite tiles $ Tile_{i} $, $ i=1 $, 2, ..., n and $ C = 2 $.
Output: Best matching tile $ Tile_{b} $ with $ I_{scaled} $.
1: $ \alpha_{best} = \frac{D_{UAV}}{D_{Tile}} \times C $;
2: Reduce $ I_{UAV} $ with $ \alpha_{best} $ to get $ I_{scaled} $;
3: Let $ Value_{i} $ represent the corresponding matching performance between $ I_{scaled} $ and $ Tile_{b} $;
4: for $ i:=1 $ to $ n $ do
5: Double the size of $ Tile_{i} $;
6: Do the matching between the doubled $ Tile_{i} $ and $ I_{scaled} $;
7: Matching performance is valued by $ Value_{i} $
8: end for
9: $ b=argmax_{i} {Value_{i}} $ and $ Tile_{b} $ is the best matching tile with $ I_{scaled} $.
Stop.

| Show Table

DownLoad: CSV

Table 2. Comparisons on time-consuming and numbers of matched pairs

Image No.	Matching time (second)	Numbers of matched pairs
Image A using fast method	23.1	7
Image A using Ao's method	738.1	3
Image B using fast method	23.0	6
Image B using Ao's method	703.7	3
Image C using fast method	24.1	6
Image C using Ao's method	749.9	7
Image D using fast method	23.3	7
Image D using Ao's method	697.5	9

| Show Table

DownLoad: CSV

Table 3. Comparisons of real scene direction with calculated scene rotation direction

Image No.	Real image direction (degree)	Calculated image direction (degree)
	15	16.44
	30	29.57
Image B	45	49.10
	60	59.82
	75	76.25
	90	93.21
	110	109.07
	120	117.15
Image C	130	130.09
	140	138.96
	150	149.41
	160	159.54

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	W. An, R. Yu and Y. Wu, An image registration algorithm based on FAST, RANSAC and SURF, Information Technology and Applications, (2015), 329–333.
[2]	T. C. Ao, X. D. Liu, Y. Ren, R. Luo and J. Xi, An approach to scene matching algorithm for UAV autonomous navigation, Chinese Control and Decision Conference, (2018), 996–1001. doi: 10.1109/CCDC.2018.8407275.
[3]	F. Bulbul, F. Badsha and R. Islam, Object detection by point feature matching using Matlab, Advances in Image and Video Processing, 6 (2018). doi: 10.14738/aivp.66.5619.
[4]	M. B. Cohen, B. T. Fasy, G. L. Miller, A. Nayyeri, D. R. Sheehy and A. Velingker, Approximating nearest neighbor distances, Algorithms and Data Structures, Lecture Notes in Comput. Sci., Springer, Cham, 9214 (2015), 200-211. doi: 10.1007/978-3-319-21840-3_17.
[5]	R. Dong, M. Liu and F. Li, Multiplayer convolutional feature aggregation algorithm for image retrieval, Mathematical Problems in Engineering, 2019 (2019), 1-12.
[6]	A. S. Eltanany, M. Safy and A. S. Amein, Key point detection techniques, Advances in Intelligent Systems and Computing, 1058 (2019). doi: 10.1007/978-3-030-31129-2_82.
[7]	H. Jan, B. Rodrigo and S. Bernt, Learning Non-maximum Suppression, Conference on Computer Vision and Pattern Recognition, (2017), 6469–6477.
[8]	S. Katta, S. Pabboju, A. V. Babu and R. Akhila, CBIR using SIFT with LoG, DoG and PCA, Data Engineering and Communication Technology, (2020), 623–637.
[9]	X. Li, J. Luo, C. Duan and P. Yin, Portrait matching based on sift features, IOP Conference Series: Materials Science and Engineering, 612 (2019), 032162. doi: 10.1088/1757-899X/612/3/032162.
[10]	X. Li, X. Wang and C. Cheng, Application of scene recognition technology based on faster and surf algorithm in augmented reality, International Conference on Smart and Sustainable City, (2017), 23.
[11]	L. Liberti and C. Lavor, Euclidean Distance Geometry: An introduction, Springer Undergraduate Texts in Mathematics and Technology, Springer, Cham, 2017. doi: 10.1007/978-3-319-60792-4.
[12]	X. Liu, X. Tao and N. Ge, Fast remote-sensing image registration using priori information and robust feature extraction, Tsinghua Science and Technology, 21 (2016), 552-560.
[13]	Y. L. Liu, H. Zhang, H. L. Guo and N. N. Xiong, A FAST-BRISK feature detector with depth information, Sensors, 18 (2018), 3908. doi: 10.3390/s18113908.
[14]	L. Tong and X. Ying, 3D point cloud initial registration using surface curvature and SURF matching, 3D Research, 9 (2018). doi: 10.1007/s13319-018-0193-8.
[15]	C. Tsai and Y. Lin, An accelerated image matching technique for UAV orthoimage registration, ISPRS Journal of Photogrammetry and Remote Sensing, 128 (2017), 130-145. doi: 10.1016/j.isprsjprs.2017.03.017.
[16]	C. Y. Wang, Z. Zhang, Q. W. Li and X. Zhou, An image copy-move forgery detection method based on SURF and PCET, Institute of Electrical and Electronics Engineers, 7 (2019), 170032-170047. doi: 10.1109/ACCESS.2019.2955308.
[17]	D. Xiang, B. Zhong and K. Ma, A location-aware scale-space method for salient object detection, International Conference on Image Processing, (2015), 4195–4199. doi: 10.1109/ICIP.2015.7351596.
[18]	K. Yang, A. N. Pan, Y. Yang, S. Zhang, S. H. Ong and H. L. Tang, Remote sensing image registration using multiple image features, Remote Sensing, 9 (2017), 581. doi: 10.3390/rs9060581.
[19]	D. Zeng, L. D. Wu, B. Y. Chen and W. Shen, Slope-restricted multi-scale feature matching for geostationary satellite remote sensing images, Remote Sensing, 9 (2017), 576. doi: 10.3390/rs9060576.
[20]	L. Zhu, Y. Wang, B. Zhao and X. Z. Zhang, A fast image stitching algorithm based on improved SURF, International Conference on Computational Intelligence and Security, (2015), 171–175. doi: 10.1109/CIS.2014.67.