American Institute of Mathematical Sciences

Advanced
August  2020, 3(3): 141-155. doi: 10.3934/mfc.2020021

A fast matching algorithm for the images with large scale disparity

Shichu Chen 1,, , Zhiqiang Wang 2, and  Yan Ren 2,

1. 

Computer Science Department, Curtin University, Perth, Australia
2. 

Automation College, Shenyang Aerospace University, Liaoning, China

* Corresponding author: Shichu Chen

Received  October 2019 Revised  March 2020 Published  June 2020

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: Shichu Chen, Zhiqiang Wang, Yan Ren. A fast matching algorithm for the images with large scale disparity. Mathematical Foundations of Computing, 2020, 3 (3) : 141-155. doi: 10.3934/mfc.2020021
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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

R. Dong, M. Liu and F. Li, Multiplayer convolutional feature aggregation algorithm for image retrieval, Mathematical Problems in Engineering, 2019 (2019), 1-12.   Google Scholar

[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.  Google Scholar

[7]

H. Jan, B. Rodrigo and S. Bernt, Learning Non-maximum Suppression, Conference on Computer Vision and Pattern Recognition, (2017), 6469–6477. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

R. Dong, M. Liu and F. Li, Multiplayer convolutional feature aggregation algorithm for image retrieval, Mathematical Problems in Engineering, 2019 (2019), 1-12.   Google Scholar

[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.  Google Scholar

[7]

H. Jan, B. Rodrigo and S. Bernt, Learning Non-maximum Suppression, Conference on Computer Vision and Pattern Recognition, (2017), 6469–6477. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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

Download full-size image

Download as 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
Figure Options

Download full-size image

Download as 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)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  Filters and octaves permutation
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  Scale space
Figure Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

Figure 8.  A sliding sector to find out dominant orientation
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 9.  Descriptor and sub-region divisions
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 10.  Different local characteristics
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 11.  Flowchart of fast matching algorithm
Figure Options

Download full-size image

Download as 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
Figure Options

Download full-size image

Download as 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
Figure Options

Download full-size image

Download as 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
Figure Options

Download full-size image

Download as 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
Figure Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

Figure 17.  The matching results for Image B with rotations
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 18.  The matching results for Image C with rotations
Figure Options

Download full-size image

Download as 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.
Table Options

Download as excel

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.
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
Table Options

Download as excel

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
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
Table Options

Download as excel

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
[1]

Dandan Cheng, Qian Hao, Zhiming Li. Scale pressure for amenable group actions. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021008
[2]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[3]

Shahede Omidi, Jafar Fathali. Inverse single facility location problem on a tree with balancing on the distance of server to clients. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021017
[4]

Stefan Siegmund, Petr Stehlík. Time scale-induced asynchronous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1011-1029. doi: 10.3934/dcdsb.2020151
[5]

Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004
[6]

Ömer Arslan, Selçuk Kürşat İşleyen. A model and two heuristic methods for The Multi-Product Inventory-Location-Routing Problem with heterogeneous fleet. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021002
[7]

Editorial Office. Retraction: Xiaohong Zhu, Zili Yang and Tabharit Zoubir, Research on the matching algorithm for heterologous image after deformation in the same scene. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1281-1281. doi: 10.3934/dcdss.2019088
[8]

Vadim Azhmyakov, Juan P. Fernández-Gutiérrez, Erik I. Verriest, Stefan W. Pickl. A separation based optimization approach to Dynamic Maximal Covering Location Problems with switched structure. Journal of Industrial & Management Optimization, 2021, 17 (2) : 669-686. doi: 10.3934/jimo.2019128
[9]

Hyung-Chun Lee. Efficient computations for linear feedback control problems for target velocity matching of Navier-Stokes flows via POD and LSTM-ROM. Electronic Research Archive, , () : -. doi: 10.3934/era.2020128

 Impact Factor: 

Tools

Metrics

  • PDF downloads (104)
  • HTML views (254)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences