Figure 1.
A region of intensities can be calculated in three additions on integral image
-
Previous Article
Summation of Gaussian shifts as Jacobi's third Theta function
- MFC Home
- This Issue
- Next Article
August
2020, 3(3): 141-155.
doi: 10.3934/mfc.2020021
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 |
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.
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. |
| [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. |
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. |
| [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. |
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 3.
Filters $ D_{yy} $ (above) and $ D_{xy} $ (below) with two size: $ 9\times 9 $ templates (left) and $ 15\times 15 $ templates (right)
Figure 4.
Filters and octaves permutation
Figure 5.
Scale space
Figure 6.
$ 3\times 3 \times 3 $ neighbourhood non-maximum suppression
Figure 8.
A sliding sector to find out dominant orientation
Figure 9.
Descriptor and sub-region divisions
Figure 10.
Different local characteristics
Figure 11.
Flowchart of fast matching algorithm
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 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 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 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 16.
Diagram of the angle between $ \overline{AB} $ and Google map direction
Figure 17.
The matching results for Image B with rotations
Figure 18.
The matching results for Image C with rotations
Table 1.
Pseudo-code of fast matching algorithm
| Algorithm: Fast matching algorithm for images with large scale disparity |
| Input: UAV aerial image |
| Output: Best matching tile |
| 1: |
| 2: Reduce |
| 3: Let |
| 4: for |
| 5: Double the size of |
| 6: Do the matching between the doubled |
| 7: Matching performance is valued by |
| 8: end for |
| 9: |
| Stop. |
| Algorithm: Fast matching algorithm for images with large scale disparity |
| Input: UAV aerial image |
| Output: Best matching tile |
| 1: |
| 2: Reduce |
| 3: Let |
| 4: for |
| 5: Double the size of |
| 6: Do the matching between the doubled |
| 7: Matching performance is valued by |
| 8: end for |
| 9: |
| 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 |
| 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 |
| 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] |
Philippe Bonneton, Nicolas Bruneau, Bruno Castelle, Fabien Marche. Large-scale vorticity generation due to dissipating waves in the surf zone. Discrete and Continuous Dynamical Systems - B, 2010, 13 (4) : 729-738. doi: 10.3934/dcdsb.2010.13.729 |
| [2] |
M. H. Shavakh, B. Bidabad. Time-optimal of fixed wing UAV aircraft with input and output constraints. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021023 |
| [3] |
Yi Cui, Xintong Fang, Gaoqi Liu, Bin Li. Trajectory optimization of UAV based on Hp-adaptive Radau pseudospectral method. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021201 |
| [4] |
Giuseppe Buttazzo, Serena Guarino Lo Bianco, Fabrizio Oliviero. Optimal location problems with routing cost. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1301-1317. doi: 10.3934/dcds.2014.34.1301 |
| [5] |
Charlene Kalle, Niels Langeveld, Marta Maggioni, Sara Munday. Matching for a family of infinite measure continued fraction transformations. Discrete and Continuous Dynamical Systems, 2020, 40 (11) : 6309-6330. doi: 10.3934/dcds.2020281 |
| [6] |
Luigi Ambrosio, Federico Glaudo, Dario Trevisan. On the optimal map in the $ 2 $-dimensional random matching problem. Discrete and Continuous Dynamical Systems, 2019, 39 (12) : 7291-7308. doi: 10.3934/dcds.2019304 |
| [7] |
Danilo Coelho, David Pérez-Castrillo. On Marilda Sotomayor's extraordinary contribution to matching theory. Journal of Dynamics and Games, 2015, 2 (3&4) : 201-206. doi: 10.3934/jdg.2015001 |
| [8] |
J. M. Mazón, Julio D. Rossi, J. Toledo. Optimal matching problems with costs given by Finsler distances. Communications on Pure and Applied Analysis, 2015, 14 (1) : 229-244. doi: 10.3934/cpaa.2015.14.229 |
| [9] |
Paola B. Manasero. Equivalences between two matching models: Stability. Journal of Dynamics and Games, 2018, 5 (3) : 203-221. doi: 10.3934/jdg.2018013 |
| [10] |
Jean-Michel Morel, Guoshen Yu. Is SIFT scale invariant?. Inverse Problems and Imaging, 2011, 5 (1) : 115-136. doi: 10.3934/ipi.2011.5.115 |
| [11] |
Juan Campos, Rafael Ortega. Location of fixed points and periodic solutions in the plane. Discrete and Continuous Dynamical Systems - B, 2008, 9 (3&4, May) : 517-523. doi: 10.3934/dcdsb.2008.9.517 |
| [12] |
Guowei Hua, Shouyang Wang, Chi Kin Chan, S. H. Hou. A fractional programming model for international facility location. Journal of Industrial and Management Optimization, 2009, 5 (3) : 629-649. doi: 10.3934/jimo.2009.5.629 |
| [13] |
Maryam Esmaeili, Samane Sedehzade. Designing a hub location and pricing network in a competitive environment. Journal of Industrial and Management Optimization, 2020, 16 (2) : 653-667. doi: 10.3934/jimo.2018172 |
| [14] |
Dandan Hu, Zhi-Wei Liu. Location and capacity design of congested intermediate facilities in networks. Journal of Industrial and Management Optimization, 2016, 12 (2) : 449-470. doi: 10.3934/jimo.2016.12.449 |
| [15] |
Vesselin Petkov. Location of eigenvalues for the wave equation with dissipative boundary conditions. Inverse Problems and Imaging, 2016, 10 (4) : 1111-1139. doi: 10.3934/ipi.2016034 |
| [16] |
Dandan Cheng, Qian Hao, Zhiming Li. Scale pressure for amenable group actions. Communications on Pure and Applied Analysis, 2021, 20 (3) : 1091-1102. doi: 10.3934/cpaa.2021008 |
| [17] |
Chanh Kieu, Quan Wang. On the scale dynamics of the tropical cyclone intensity. Discrete and Continuous Dynamical Systems - B, 2018, 23 (8) : 3047-3070. doi: 10.3934/dcdsb.2017196 |
| [18] |
Julia Piantadosi, Phil Howlett, John Boland. Matching the grade correlation coefficient using a copula with maximum disorder. Journal of Industrial and Management Optimization, 2007, 3 (2) : 305-312. doi: 10.3934/jimo.2007.3.305 |
| [19] |
V. Carmona, E. Freire, E. Ponce, F. Torres. The continuous matching of two stable linear systems can be unstable. Discrete and Continuous Dynamical Systems, 2006, 16 (3) : 689-703. doi: 10.3934/dcds.2006.16.689 |
| [20] |
Angel Angelov, Marcus Wagner. Multimodal image registration by elastic matching of edge sketches via optimal control. Journal of Industrial and Management Optimization, 2014, 10 (2) : 567-590. doi: 10.3934/jimo.2014.10.567 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]