# American Institute of Mathematical Sciences

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

* 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.

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:

show all references

##### References:
A region of intensities can be calculated in three additions on integral image
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
Filters $D_{yy}$ (above) and $D_{xy}$ (below) with two size: $9\times 9$ templates (left) and $15\times 15$ templates (right)
Filters and octaves permutation
Scale space
$3\times 3 \times 3$ neighbourhood non-maximum suppression
Haar wavelet templates in $x$ and $y$ directions
A sliding sector to find out dominant orientation
Descriptor and sub-region divisions
Different local characteristics
Flowchart of fast matching algorithm
(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
(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
(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
(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
Diagram of the angle between $\overline{AB}$ and Google map direction
The matching results for Image B with rotations
The matching results for Image C with rotations
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.
 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.
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
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 & Continuous Dynamical Systems - B, 2010, 13 (4) : 729-738. doi: 10.3934/dcdsb.2010.13.729 [2] Giuseppe Buttazzo, Serena Guarino Lo Bianco, Fabrizio Oliviero. Optimal location problems with routing cost. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1301-1317. doi: 10.3934/dcds.2014.34.1301 [3] Danilo Coelho, David Pérez-Castrillo. On Marilda Sotomayor's extraordinary contribution to matching theory. Journal of Dynamics & Games, 2015, 2 (3&4) : 201-206. doi: 10.3934/jdg.2015001 [4] Luigi Ambrosio, Federico Glaudo, Dario Trevisan. On the optimal map in the $2$-dimensional random matching problem. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 7291-7308. doi: 10.3934/dcds.2019304 [5] J. M. Mazón, Julio D. Rossi, J. Toledo. Optimal matching problems with costs given by Finsler distances. Communications on Pure & Applied Analysis, 2015, 14 (1) : 229-244. doi: 10.3934/cpaa.2015.14.229 [6] Paola B. Manasero. Equivalences between two matching models: Stability. Journal of Dynamics & Games, 2018, 5 (3) : 203-221. doi: 10.3934/jdg.2018013 [7] Charlene Kalle, Niels Langeveld, Marta Maggioni, Sara Munday. Matching for a family of infinite measure continued fraction transformations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (11) : 6309-6330. doi: 10.3934/dcds.2020281 [8] Jean-Michel Morel, Guoshen Yu. Is SIFT scale invariant?. Inverse Problems & Imaging, 2011, 5 (1) : 115-136. doi: 10.3934/ipi.2011.5.115 [9] Juan Campos, Rafael Ortega. Location of fixed points and periodic solutions in the plane. Discrete & Continuous Dynamical Systems - B, 2008, 9 (3&4, May) : 517-523. doi: 10.3934/dcdsb.2008.9.517 [10] Guowei Hua, Shouyang Wang, Chi Kin Chan, S. H. Hou. A fractional programming model for international facility location. Journal of Industrial & Management Optimization, 2009, 5 (3) : 629-649. doi: 10.3934/jimo.2009.5.629 [11] Maryam Esmaeili, Samane Sedehzade. Designing a hub location and pricing network in a competitive environment. Journal of Industrial & Management Optimization, 2020, 16 (2) : 653-667. doi: 10.3934/jimo.2018172 [12] Dandan Hu, Zhi-Wei Liu. Location and capacity design of congested intermediate facilities in networks. Journal of Industrial & Management Optimization, 2016, 12 (2) : 449-470. doi: 10.3934/jimo.2016.12.449 [13] Vesselin Petkov. Location of eigenvalues for the wave equation with dissipative boundary conditions. Inverse Problems & Imaging, 2016, 10 (4) : 1111-1139. doi: 10.3934/ipi.2016034 [14] Chanh Kieu, Quan Wang. On the scale dynamics of the tropical cyclone intensity. Discrete & Continuous Dynamical Systems - B, 2018, 23 (8) : 3047-3070. doi: 10.3934/dcdsb.2017196 [15] Julia Piantadosi, Phil Howlett, John Boland. Matching the grade correlation coefficient using a copula with maximum disorder. Journal of Industrial & Management Optimization, 2007, 3 (2) : 305-312. doi: 10.3934/jimo.2007.3.305 [16] V. Carmona, E. Freire, E. Ponce, F. Torres. The continuous matching of two stable linear systems can be unstable. Discrete & Continuous Dynamical Systems - A, 2006, 16 (3) : 689-703. doi: 10.3934/dcds.2006.16.689 [17] Angel Angelov, Marcus Wagner. Multimodal image registration by elastic matching of edge sketches via optimal control. Journal of Industrial & Management Optimization, 2014, 10 (2) : 567-590. doi: 10.3934/jimo.2014.10.567 [18] Pengwen Chen, Changfeng Gui. Alpha divergences based mass transport models for image matching problems. Inverse Problems & Imaging, 2011, 5 (3) : 551-590. doi: 10.3934/ipi.2011.5.551 [19] Sergei Avdonin, Pavel Kurasov, Marlena Nowaczyk. Inverse problems for quantum trees II: Recovering matching conditions for star graphs. Inverse Problems & Imaging, 2010, 4 (4) : 579-598. doi: 10.3934/ipi.2010.4.579 [20] Jean Dolbeault, Giuseppe Toscani. Fast diffusion equations: Matching large time asymptotics by relative entropy methods. Kinetic & Related Models, 2011, 4 (3) : 701-716. doi: 10.3934/krm.2011.4.701

Impact Factor:

## Tools

Article outline

Figures and Tables