# Design and implementation of a new vision-based navigation for Unmanned Aerial Vehicle.

Nima Ziaei, Géraldine Guerri

► To cite this version:

Nima Ziaei, Géraldine Guerri. Design and implementation of a new vision-based navigation for Unmanned Aerial Vehicle. 2023. hal-04482426

HAL Id: hal-04482426

https://hal.science/hal-04482426v1

Submitted on 28 Feb 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
<figure><img src="image_2.png" /></figure>

# Design and implementation of a new vision-based navigation for Unmanned Aerial Vehicle. Optimization of the descriptor matching algorithm

N. ZIAEI, G. GUERRI, ASTEK Group

**Abstract**— The use of GPS is the most efficient way to locate a drone. However, problems with GPS signal reception is an obstacle to estimate drone positioning. This paper presents another process of geolocation, without GPS, which will allow the drone to locate itself on long routes, by vision-based absolute matching. The purpose of this paper is to introduce the development of a robust program ensuring the real-time geolocation of a drone in cruise flight on any type of topography. The aim of this operation is to develop algorithmic architectures that allow improving the geolocation performance by using image-matching method based on the selection of correct descriptors matchings. The challenge is to have generic models to predict the performance of a computing architecture for an algorithm. This study shows how to optimize this matching process to limit inaccuracies and drifts while keeping a correct position calculation time. This algorithm is based on a new approach, totally absent in the literature, using the closed geometric envelope, formed by descriptors of points of interest in images. A geometric envelope comparison method is applied between any taken image of the ground by the camera of the drone and images of a database (DB), beforehand embedded, to select correct descriptors matchings. Therefore, the number of descriptor matching should not exceed 6, with the execution time of the order of 140ms. Nevertheless, to consider images with many descriptors, such as those detected on cities, it is necessary to upgrade this original algorithm to associate a known "similarities between transformations" mathematical method which is explained afterwards. So, for the number of descriptors matching over 6, the method by similarities succeeded in eliminating the false matches and thus rectifying the drift in 98% of the cases in about 5ms. Finally, this study measures impacts of seasonal changes, fog, contrast, and blur; between image taken by the camera of the drone and the images in the DB; on the performance of geolocation.

**Index Terms**—Unmanned aerial vehicles, Vision-based autonomous navigation, Processes of matching descriptors of image, SURF, Matching algorithm, Closed

envelope comparison method, Similarities between transformation

## I. INTRODUCTION

DRONES have become a real focus. Over the past few years, their use has increased considerably. Today, they are used to perform many tasks such as surveillance, navigation or even transportation. Nevertheless, the success of these tasks would not be possible without a very accurate position.

GPS geolocation is currently the most efficient way to position a drone in flight. However, this technique is not foolproof. Under some circumstances, the reception of the GPS signal is not guaranteed (jamming of the signal, hacking, failure of satellites, etc.), justifying the need to provide a robust alternative to the current position systems.

The objective of this article is to propose a geolocation technique based only on aerial images captured by the drone, using image-matching techniques. Given that, the drone flying over long distances, absolute matching (i.e. Comparison of the calculated descriptors in a current image, namely the image taken by the camera of the drone, with those in images of a beforehand embedded DB) is essential. Indeed, the drift of a relative matching (i.e. Comparison of the calculated descriptors in a current image with those in a previous current image) diverges over the iterations, since the drift is cumulative. In fact, the result of each iteration depends on the previous result. Finally, absolute matching is much more accurate over long distances, and it is impossible to rely only on a relative matching. In this article, the study deals only with the absolute matching. For this, we will develop a new algorithm by applying closed envelope comparison method that will be merged with a known algorithm by applying similarities between transformations method.

The drone considered in this work is an aircraft with a wingspan of several meters. Its speed can reach 200km/h and its altitude is limited to avoid any visual occlusions (clouds, fog). Nevertheless, this technology can be adapted very well to other types of drones. The aircraft is equipped with an on-board system ensuring the processing of the images, which are acquired
<figure><img src="image_3.png" /></figure>

thanks to a ventral camera directed towards the ground. A gyro-stabilization system can be integrated to reduce the effect of vibrations on the quality of the images.

First, the device must be able to operate in case of loss of GPS signal, thus ensuring more security. For example, if a breakdown occurs, the system will allow the aircraft to return to its starting place. Moreover, and far from being a simple safety measure, this technology could provide a real alternative to conventional GPS systems, especially with the increasing development of machines and their computing power. Finally, it is quite likely that this technology could surpass GPS systems in terms of performance given its low cost, unlike GPS technology in aviation.

This paper starts by presenting the current state of the art regarding the guidance limitation of drone. To circumvent this problem, we present, in chapter III the new strategy implemented, lacking from the literature. For images with few descriptors, we applied envelope comparison methods. These methods are discussed in the chapters IV to VII. For images with many descriptors, we adapted similarity transformation method. This is covered in the chapter VIII. Finally, we presented in chapter IX, an original algorithm merging envelops comparison and similarity transformation method, The last chapter allows to verify the robustness of this algorithm on any type of topography and on environmental conditions.

## II. CRITICAL ANALYSIS OF THE STATE OF THE ART

Before addressing the modeling strategy used in this study, this chapter presents a review of the work already done in the scientific literature. We focus on the real-time aspect, on the correct geo-positioning with respect to any type of topography and flight conditions (speed and altitude), and on the robustness with respect to the differences between acquired images and images from the DB.

The article [1] has the particularity to address almost the same problem as ours. Indeed, the authors propose a geolocation technique for a UAV based on computer vision, using only absolute registration. To match the acquired images with those in the DB, they use a correlative approach based on similarity transformation method. However, the experiments are conducted on a hexa-rotor flying at 150 meters altitude, at low speed, and over a short distance of 700 meters, in an urban environment. At the end of the experiment, the authors obtain a drift not exceeding 10 meters. The article does not highlight the limitations of this approach. Indeed, correlative approaches are known to be very sensitive to changes in luminance or illumination, and are not robust enough to landscape redundancy, in this case in forest or rural environments.

The paper [2] deals with the localization of UAVs by real-time computer vision and proposes a technology

based on a coupling between two registration modes, absolute and relative. The UAV localization is largely based on relative registration and the position calculation is done by homography between the two consecutive images. With these coupling modes, the calculated drift does not exceed 10 meters after 140 seconds of flight. However, the conditions of use are completely different from ours. Indeed, the objective was to ensure a geolocation only in urban environment, and no tests or experiments were carried out on rural or forest topography. Moreover, the flight parameters (speed and altitude) and the image resolution are also different from ours.

The paper [3] addresses the topic of helicopter localization using a coupling between the two kinds of registration methods. The authors propose new descriptor computation and matching techniques that give good results. However, the assumptions made in this work differ greatly from our operating conditions. The experiments are carried out over short distances, at quasi-static speeds, on not very varied types of topography and in conditions of image taking (season, luminosity, angle, etc.) identical to those of the DB. The article [4] focuses on the topic of absolute registration applied to aerial images. It proposes a registration technique based on the matching of descriptors. After the matching, the position is computed by homography. The author highlights the limitations of this approach, particularly in the face of perspective problems that can degrade the image or even create occlusions, given that the altitude considered is relatively low and does not exceed 120 meters, and that the images captured do not undergo any preliminary digital processing. Finally, only 65% of the images are correctly aligned. The article shows that the matching of descriptors is problematic when they are very dense in a small region of the image.

Each of these articles is close in one way or another to our problem. However, they do not allow us to remove all the uncertainties related to our problem. Some of them do not consider the real time aspect of geolocation or the speed of the drone, others are limited to short paths or do not cover certain topographies. Otherwise, articles [6], [7], [8] and [9] are either not considering movement of the drone or, are not measuring performance of drone geopositioning for different topographies flown over or even are not corresponding to our operational context of drone flight preferring focusing on proposed high mathematical methods to match points of interest or geometric shapes without considering topographies 'constraints' (blur, fog, seasonal changes etc.).

Finally, none of these studies really answers our problem since the operational context is always different. The critical analysis of existing knowledge and techniques shows that the treatment of the problem, mentioned in the introduction, is quite original. Some knowledge is missing from the
<figure><img src="image_4.png" /></figure>

literature, such as the impact of different descriptor matching processes, their influence on the quality of the absolute registration and the effect of external changes (fog, blur, seasonal changes) for the geographical positioning of a drone.

### III. EXPERIMENTATION STRATEGY

To increase the accuracy of the matching and position calculation, in the presence of few descriptors in an image, we will test two closed geometric envelope comparison methods and then we will evaluate the performance of each one according to well-defined criteria. As a result, it becomes important to eliminate any risky matching, even if it means keeping only two correctly matched descriptors in the image. These original approaches are based on the geometric distribution of the points.

These envelopes are obtained by linking the geographically closest and already matched descriptors in the current image and in the embedded DB. This approach is particularly adapted to our case since we consider that the drone flies at a constant height, nearly 300 meters and that the camera is always oriented towards the ground so that there are no perspective changes between the acquired images and the images in the embedded DB. This implies that the distribution of points does not change between DB and the acquired image. We can then assume that for two sets of correctly matched descriptors, both sets generate the same geometric shape.

We have chosen to evaluate and compare the performances of the following methods: the proposed convex envelope method:

- Approach by comparison of angles

- Approach by comparison of relative lengths

To challenge our two methods, in case of many descriptors detection, we integrated an adapted version of the method proposed in the article [1] based on the similarity between transformations.

These two convex envelope methods are discussed in the chapters IV to VII. This similarity transformation method is presented in the chapters VIII. Finally, we presented in chapter IX, an original method merging convex envelop method and similarity method.

To evaluate the performance of each method, we will proceed as follows. We simulate the images acquired by the camera positioned under the belly of the drone, from the 992 images in 2500\*2500 pixels of resolution 1.19 m/pixel (the compilation of these images, from the IGN DB, called in the rest of the article useful DB) representing different topographies (forest, rural, urban) of the region of Eastern France.

From each of the images we crop a centered thumbnail of size 256x256 pixels. This thumbnail will represent the acquired image. Then, we apply a rotation of an angle whatsoever such that the two

images do not have the same orientation. Indeed, this rotation might increase the probability of false matching and corresponds well to the reality where the DB images and those acquired do not have the same orientation.

After matching, the drift is calculated by representing the distance between the center of the useful DB image and the center of the current image. The drift is originally obtained in pixels before being converted into meters.

The existing techniques for calculating descriptors such as SIFT, SURF, ORB can identify the points of interest and generally give more or less similar results. This study relies only on algorithm SURF.

For each image, we will perform the matching by the method to be tested as well as by the classical approach, which consists in computing the position from the $N_{max}$ best matches in terms of Euclidean distances of their feature vectors. The Euclidean distance between two descriptors d1 and d2 is therefore the average of the distance between each component of the vectors of descriptors. We will thus calculate the number of matched descriptors in each image, the number of eliminated descriptors, the execution time of the selected algorithm and finally the drifts measured by each approach.

The 992 images used represent squares of about 9km². Assuming that the maximum speed of the drone is 200km/h and that the position calculation lasts at most about ten seconds, we obtain a disc of diameter 1.1 km, given an area of 3,8 km². Moreover, if in our case we take a larger surface (9km²), it is in order to increase the risk of false matchings and thus testing the limit of the methods. Eventually, by taking an extended search area, we should expect that the false matches introduce larger drifts.

To evaluate the performance of each method, we will only focus on images with three or more than three matches. Then, we will look at the execution time as a function of the number of eliminated matchings aiming to know the performance of each approach. This benchmarking strategy is presented in the figure 1.

<figure><img src="image_5.png" /></figure>
<figure><img src="image_6.png" /><figcaption>Fig.1. Benchmarking strategy between the classical method and the proposed method</figcaption></figure>

The experimental strategy to know the performance of each envelope comparison approach versus the classical method is based on the following two criteria: the reduction of the drift and the execution times as a function of the number of eliminated matchings.

## IV. NEW ENVELOPE COMPARISON APPROACH

In this chapter, we will see a new practical approach to improve the matching: this is a new comparison method that improves the geo-positioning accuracy of the drone by eliminating mismatches.

Two methods can be derived from this approach. We will explain them in the rest of this chapter. The idea is therefore to generate a closed envelope passing once through all the descriptors and having no intersection, it is basically a simple polygon generated by all the points.

A simple polygon is a polygon whose sides never intersect and contains no holes. This generated envelope constitutes a solid comparative element between two-point clouds and facilitates the comparison process.

The result is that if all the matchings are correct, the points of interest will form the same geometric envelope in both images. Thus, to compare the two envelopes, one can proceed either by comparing the angles of the polygon or the lengths of its sides.

The three methods are briefly described hereinafter, as well as the choice of the major parameters.

### A. The angle comparison method

The angle comparison method is based on two essential parameters, the number of input matchings $N_{max}$ as well as the angle disparity $\sigma_a^2$. This angle disparity allows to characterize the resemblance of angles $\theta_i$ from $i^{th}$ vertex of the two formed polygons, establishing each of both envelopes $C$ and $C'$, according to $N$ descriptors.

$$ \sigma_a^2 = \frac{1}{N} \sum_{i=1,N} (\theta_i^{C'} - \theta_i^C)^2 $$

We definite subjectively a value of the angle disparity threshold $\sigma_a^2_{threshold}$. For the choice of threshold, we first determined by $\sigma_a^2_{threshold} \ge \sigma_a^2$, corresponding to the threshold below which both envelopes are considered as similar.

We apply the angle comparison method on several matchings that we know beforehand are all correct, and then we decrease the threshold until we reach a value where we start to reject correct matchings, we found $\sigma_{lim}^2 = 4$. Then, we performed several tests on images with false matches to adjust the threshold. Finally, we chose $\sigma_{threshold}^2 = 10$ in the first instance, Concerning the choice of $N_{max}$, we based ourselves, in this phase of comparison, on the execution time in

the worst case and we fixed an arbitrary limit of 1 second. For $N_{max} = 8$ the algorithm never exceeds the duration of 0.9 seconds, but for $N_{max} = 9$ the algorithm exceeds 1 second in some cases, so we chose $N_{max} = 8$ for this simulation.

### B. Relative length comparison method

Another way to evaluate the similarity between the two envelopes is to calculate the disparity of respectively relative lengths, $e_i, e_{i+1}$ and $e'_i, e'_{i+1}$, between the two envelopes. To do this, the lengths of the polygons 'sides are normalized compared to the greatest one, generating a set of relative lengths $d_r$.

$$ \sigma_d^2 = \frac{1}{N} \sum_{i=1,N} (d_r^{e'_i, e'_{i+1}} - d_r^{e_i, e_{i+1}})^2 $$

As with the angle comparison method, we will choose $N_{max}=8$, to compare the performance of each method with the same criterion of maximum execution time of 1s.

The disparity threshold allows to characterize the resemblance of lengths, and condition $\sigma_d^2_{threshold} \ge \sigma_d^2$, corresponding to relative length disparity for which both envelopes are considered as similar.

### C. Decision model optimization

First, we compare the two envelopes generated by the $N_{max}$ best matchings in terms of Euclidean distance between descriptors. Indeed, a SURF descriptor is a vector of 64 components, describing the characteristics of the corresponding point of interest. If the number of matched descriptors $N$ is higher than this threshold $N_{max}$, we take the $N_{max}$ best matchings in terms of Euclidean distance ($N_{max} = N$).

If the $N_{max}$ best matches are correct, the envelopes will be identical, so the algorithm will stop at the first iteration, and the $N_{max}$ points will be used for the position calculation.

If the two envelopes are different, it means that there is at least one false matching among the $N_{max}$ chosen points. So, we choose randomly $n = N_{max} - 1$ points among the $N_{max}$ best matches and we compare the envelopes. If all the $n$ combinations are tested and none of them is conclusive, this means that we have at least two false matches among the $N_{max}$ best matches. In the same way, we choose this time $n = N_{max} - 2$ among the $N_{max}$, and so on until we compare all the possible combinations among the $N_{max}$. If the algorithm still fails, this means that there are at most two correct matches among the $N_{max}$. In this case, it is possible to compute the position directly from the two best matches, except that after several tests, it turned out that the best matches in terms of Euclidean distance are not necessarily the right matches. Indeed, in several images, the best matching happens to be a false one. We also noticed that the false matches are randomly distributed in the image and are generally very spaced, so we decided that it would be better in
this case to choose the two matches whose descriptors are closest to each other in terms of geographical distance in the DB. In the case where only two descriptors are matched, the angle comparison method cannot work. Only a length comparison method can work. We can always compare the disparity of lengths even for two matchings.

The algorithm can therefore be modeled as follows with:

N: total number of detected matching (no limit)

$N_{max}$: Number of matchings as input to the algorithm

$\sigma$: Disparity of angles or lengths

$\sigma_{threshold}$: Disparity threshold

<figure><img src="image_7.png" /><figcaption>Fig.2. Innovative simulation algorithm</figcaption></figure>

### D. Number of detected matchings

Among the 992 images used for the simulation, 14 of them did not have any matching and 42 of them contained 1 or 2 matched descriptors. That's why we excluded the results from these images because the methods to be tested are relevant only for 3 or more matchings. We are only interested in the results of the remaining 936 images.

<figure><img src="image_8.png" /><figcaption>Fig.3. Number of detected matchings per image</figcaption></figure>

After defining the criteria characterizing each method, the following chapter presents the results obtained in identical simulation configurations, for both approaches (angle and relative length approaches).

## V. RESULTS

### A. Results of the angle comparison method

Among the 936 images, the selection algorithm successfully eliminated at least one matching in 288 images. The figure 4, below, shows the distribution of the number of eliminated matchings in these 288 images.

<figure><img src="image_9.png" /><figcaption>Fig.4. Angle comparison method: Number of eliminated matchings per image</figcaption></figure>

We can see that in half of the cases, only one matching is eliminated, and only very rarely do we reach 6 eliminated matchings.

At this stage, we can divide the results into two categories. On the one hand, the 288 images on which the algorithm has acted by eliminating matches, and on the other hand the 648 remaining images where all matchings are kept, and where the result remains identical to the classical method.

<figure><img src="image_10.png" /><figcaption>Fig.5. Histogram of the distribution of drifts on the 288 images with at least 1 eliminated matching</figcaption></figure>

<figure><img src="image_11.png" /></figure>
<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /><figcaption>Fig.6. Histogram of the distribution of the drifts on the 648 images on which the algorithm does not improve drift compared to classical method</figcaption></figure>

In the histogram of the figure 5, we see that with the classical method, 163 recalculations end up with large drifts greater than 100m, this is obviously due to the false matchings used for the position calculation. The selection algorithm manages to eliminate these false matches and thus corrects the drift in most cases. Indeed, with the selection method, only 10 re-matches result in drifts over 100m, this is probably due to the lack of correct matchings.

We also notice that in 71 images, the algorithm eliminates a matching while it is correct; this is probably related to the choice of the threshold $\sigma_a^2$ threshold.

The table below represents the execution time increasing with the number of eliminated matches.

<table><caption>Fig.7. Median time for each number of eliminated matches</caption><thead><tr><th>Number of eliminated matchings</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><th>Median execution time</th><td>7ms</td><td>50ms</td><td>130ms</td><td>320ms</td><td>400ms</td><td>550ms</td></tr></tbody></table>

## B. Results of the “Relative length comparison approach” method

Among 936 images used for the simulation, the selection algorithm successfully eliminated at least one matching in 215 images. The figure below shows the distribution of the number of eliminated matchings in these 215 images. In half of the cases, only one matching is eliminated.

<figure><img src="image_14.png" /><figcaption>Fig.8. Relative length comparison: Number of eliminated matching</figcaption></figure>

per image

Likewise, we can divide the results into two categories. Then we represent the histograms of the drifts calculated for each category.

<figure><img src="image_15.png" /><figcaption>Fig.9. Histogram of the distribution of drifts on the 215 images with at least 1 eliminated matching</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>Fig.10. Histogram of the distribution of drift on the 721 images on which the algorithm does not improve drift compared to classical method</figcaption></figure>

The relative length comparison has the advantage of being robust to scale differences.

The execution time evolves in the same way as for the angle approach, depending on the eliminated matchings. The represents table below the medians of the execution time for each number of eliminated descriptors.

<table><caption>Fig.11. Median time for each number of eliminated matchings</caption><thead><tr><th>Number of eliminated matchings</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><th>Median execution time</th><td>10ms</td><td>80ms</td><td>190ms</td><td>470ms</td><td>620ms</td><td>730ms</td></tr></tbody></table>

In the first iteration we have $n = N_{max} = 8$, so the algorithm, presented in figure 2, has only one combination to test, it is the envelope generated by the $N_{max}$ descriptors, if the algorithm succeeds, no descriptor is eliminated. Otherwise, it will be necessary to choose $n = 7$, the algorithm has this time 8 possibilities to test and so on. The number of combinations to test is thus different at each iteration; the table below represents the number of possibilities
<figure><img src="image_17.png" /></figure>

to test at each iteration.

<table><caption>Fig.12. Number of possibilities to test for each iteration</caption><thead><tr><th>Iteration n°</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr></thead><tbody><tr><th>Number of combinations to test</th><td>1</td><td>8</td><td>28</td><td>56</td><td>70</td><td>56</td><td>28</td></tr><tr><th></th><td>c<sub>8</sub><sup>8</sup></td><td>c<sub>8</sub><sup>7</sup></td><td>c<sub>8</sub><sup>6</sup></td><td>c<sub>8</sub><sup>5</sup></td><td>c<sub>8</sub><sup>4</sup></td><td>c<sub>8</sub><sup>3</sup></td><td>c<sub>8</sub><sup>2</sup></td></tr></tbody></table>

The number of eliminated descriptors indicates us at which iteration the algorithm has stopped. When the algorithm reaches the n-th iteration, it is possible to say that the execution time then follows an evolution law equivalent to:

$$t(n) = \sum_{k=0}^{n-1} c_8^{8-k}$$
$$\text{Where } c_8^{8-k} = \frac{8!}{k!(8-k)!}$$

Therefore, the time is proportional to the total number of combinations tested, with *n* the number of the iteration.

We will therefore plot, on the figure 13, the evolution of the observed and the theoretical of the execution time normalized compared to its maximum value as function of the iteration where the algorithm stopped.

<figure><img src="image_18.png" /><figcaption>Fig.13. Comparison of median normalized execution time (no unit) and the theoretical normalized execution time as a function of the iteration where the algorithm stopped</figcaption></figure>

The analysis of the figure above shows that the execution time should be closely related to the number of combinations tested by the algorithm; this is confirmed by the great similarity between the two curves.

## VI. COMPARATIVE STUDY BETWEEN THE TWO METHODS

In view of the results of the previous section, we can conclude that the approaches based on the comparison of the lengths are a little more efficient than that of the angles in term of precision since as we saw, the choice of the threshold is problematic concerning the approach of the angles.

The execution time is relatively the same for the three approaches and evolves in the same way according to the number of iterations carried out where the algorithm is stopped. We have therefore chosen the

"relative length comparison" approach to study the evolution of the performances (drift and execution time) for different values of $N_{max}$.

For the comparison of the 2 approaches, we set $N_{max}$ to 8. To observe the influence of the choice of $N_{max}$ on the matching performance, we performed several simulations with different values of $N_{max}$ ranging from 6 to 12. We note that increasing $N_{max}$ has no impact on the number of images with large drifts. But, on the other hand, the maximum execution time increases exponentially (from 140ms for $N_{max}$ = 6 to 17.4s for $N_{max}$ = 12), which makes the algorithm unsuitable for a real time use beyond $N_{max}$ = 10. Note that $N_{max}$ = 12 corresponds to the worst case where there would be the maximum number of mismatches removed.

This strong significant increase of the computational cost is explained by the number of possibilities to be tested that each additional matching adds.

<figure><img src="image_19.png" /><figcaption>Fig.14. Maximum execution time as a function of $N_{max}$</figcaption></figure>

Thus, the choice of $N_{max}$ follows the trade-off between accuracy and computation time. This choice of $N_{max}$ is based on the algorithm, optimized during this study, to remove false matchings.

## VII. PRESENTATION OF THE "SIMILARITY TRANSFORMATION METHOD"

The selection of features by the comparison of the lengths is efficient in the case where the image contains few descriptors, for example in the countryside. However, its computational cost is not appropriate for images with a large number of descriptors, such as cities. In this case, we applied a well-known method based on the similarity between transformations [5]. This method is part of the state of the art for image matching. This method consists in estimating a transformation *T* between the matching of two descriptors. All transformations are compared two by two based on what is called transformation similarity.

The reference image is characterized by the SURF descriptors, in the form of a vector of 64 components
<figure><img src="image_20.png" /></figure>

including coordinates, scale, and orientation as represented by a radiant angle. It is then only necessary to find a transformation allowing to match the descriptors of the reference image to those of the acquired image. This rigid transformation T relies on rotations (θ) and translations $\vec{t}$ (definite by coordinates $t_x$ and $t_y$) between coordinates of a two matched points $P = (P_x, P_y)$ and $Q = (Q_x, Q_y)$ defined as

$$T = \begin{cases} t_x = Q_x - (P_x \cos \theta - P_y \sin \theta) \\ t_y = Q_y - (P_x \sin \theta + P_y \cos \theta) \end{cases}$$

Considering two transformations (T, T') from two different matchings, the similarity between those can be defined as:

$$S(T, T') = \begin{cases} 0 & \text{if } |t_x - t'_x| > \alpha \text{ or } |t_y - t'_y| > \beta \text{ or } |\theta - \theta'| > \delta \\ 1 - \frac{1}{3} \left( \frac{|t_x - t'_x|}{\alpha} + \frac{|t_y - t'_y|}{\beta} + \frac{|\theta - \theta'|}{\delta} \right) & \text{else} \end{cases}$$

Where α, β and δ are three threshold values. The values α and β are the thresholds for the translational components along the X and Y axes, and δ is the threshold for rotation. Since there is no reason to favor one of the two axes in terms of tolerance, we always take $α = β$.

For each matching, we compute the sum $W_S(i)$, called the score, of the normalized similarities $S(T_i, T_j)$ of $T_i$ with all other transformations $j < N$ provided that $i \neq j$:

$$W_S(i) = \sum_{j < N, j \neq i} S(T_i, T_j)$$

This sum is then normalized and thresholded to extract the good matches. The false matches generally have a null similarity with all the other matchings, except in the case where a possible false match has about the same transformation as the good matchings, which should be extremely rare and would not influence the position calculation. Eventually, we select only $n < N$ matchings whose score value $W_S$ is higher than a threshold called $W_{threshold}$.

The algorithm can be modeled as follows on the figure 15.

<figure><img src="image_21.png" /><figcaption>Fig.15. Selection algorithm by the similarity method</figcaption></figure>

To evaluate the performance of this method, we will

apply the selection algorithm to all detected matches without any sorting and then compare the drift computed from the saved matches with the one computed from all the matches with the classic method. For each image, in addition to the drifts, we will calculate the number of descriptors eliminated and the execution time.

<figure><img src="image_22.png" /><figcaption>Fig.16. Performance comparison strategy between classical and similarity transformation methods</figcaption></figure>

## VIII. RESULTS OF THE “SIMILARITY TRANSFORMATION METHOD”

To determine the optimal thresholds, we performed several unit tests on images for different values of α (from 10m to 100m) and δ (from 5° to 40°), and we find that above $α = β = 30m$ and $δ = 15°$. The results were almost the same, but below these values, the number of kept matches starts to decrease, and several correct matches are eliminated, we finally chose $α = β = 35m$ and $δ = 15°$.

At first glance, these tolerance thresholds seem very high. However, this is due to the uncertainty on the orientation provided by the SURF descriptors as this is only an approximation computed from the neighborhood of the point of interest, and the distortion caused by the rotation of the images influences this approximation.

$W_{threshold}$ is another threshold to set. As previously defined, it is a threshold without unit aiming to determine if a matching is correct according to its sum of computed normalized similarities. We performed several simulations with different values ranging from 0.05 to 0.9, and we notice eventually that the more we increase the threshold, the more the number of correct eliminated matches increases. We estimate that as soon as $W_S \neq 0$ it would be a correct matching, hence we have chosen a low value $W_{threshold} = 0.05$. The
<figure><img src="image_23.png" /></figure>

selected pairings are those for which $W_s > W_{threshold}$.

As for the previous simulation, among the 992 images we will analyze the results of the 936 images having 3 or more matchings. On these 936 images, the distribution of the number of detected matchings is shown in the figure 17.

<figure><img src="image_24.png" /><figcaption>Fig.17. Number of detected matchings per image</figcaption></figure>

In these 936 images, the number of eliminated matchings per image is distributed as follows:

<figure><img src="image_25.png" /><figcaption>Fig.18. Number of eliminated matchings per image</figcaption></figure>

The algorithm eliminated at least one matching in almost all but one image, the histogram below shows the distribution of the drift in both approaches, namely, the classical method and similarities between transformations.

<figure><img src="image_26.png" /><figcaption>Fig.19. Histogram of the drift distribution in both approaches</figcaption></figure>

We can observe that the method by similarities succeeded in eliminating the false matches and thus rectifying the drift in 98.5% of the cases. Nevertheless, we notice that the algorithm has eliminated some correct matches in 147 images, although it is not very

problematic, because the number of matches as input to the selection algorithm is not limited.

The median execution time is about 5ms, and the execution time very rarely reaches 20ms, which is very impressive, especially since the algorithm takes all the detected matchings as input.

The 10 images with a drift over 100m, in the figure 19, have all several matchings less than 6 and we notice that the algorithm becomes less efficient when the number of correct matchings is low.

In conclusion, the selection approach based on the similarity between transformations has several advantages. Indeed, besides offering very good results concerning the drift correction, it allows us to process all the detected matchings at once. Another advantage of this approach is the execution time, which is extremely small and does not exceed 20ms.

However, this method is not very efficient when an image has few descriptors (less than 6 matching).

## IX. CONCEPTION OF THE HYBRID ALGORITHM

It has been shown that the “relative length comparison” method proved to be efficient when an image has few descriptors. As a result, we decided to design a hybrid algorithm, represented on the figure 20, which is based on both approaches, namely similarities between transformations, for images, such as cities, with many descriptors and comparison of the relative length for images, such as countryside, with few descriptors.

We define a threshold *k*, representing the number of descriptors per image, beyond which the approach by similarities between transformations will be privileged. Below this threshold, the “relative length comparison” method is used.

<figure><img src="image_27.png" /><figcaption>Fig.20. Algorithm of the hybrid method</figcaption></figure>

The histogram of the figure 21 shows the distribution of the drift with the hybrid method. For *k* varying from 2 to 4, we get almost the same results. This means that setting the value of *k* to 2, 3 or 4 does not change the hybridization results. Finally, we choose to fix *k* = 8 for the hybrid method which is a good compromise between accuracy and execution time. The results of detected/eliminated matching remain like those of the previous method, except that the number of images with large drifts decreases (over 100m) and with at most one correct matching remains.
<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /><figcaption>Fig.21. Histogram of the drift distribution with hybrid method</figcaption></figure>

The median execution time is about 5ms. Nevertheless, for this time, the maximum value goes from 20ms to 1.5s with several values exceeding 250ms. This significant increase concerns obviously the cases where the “relative length comparison” method is favored.

We have finally given up the speed criterion in favor of the accuracy, while remaining within a reasonable margin of time and adapted to a real-time use.

## X. IMPACT OF THE SHIFT BETWEEN THE ACQUIRED IMAGES AND THOSE OF THE DB

After optimizing the descriptor matching and position calculation process, this second and last phase concerns the study of the performance limits of absolute registration on different topographies. It is certain that changes in the environment or in the shot may strongly degrade the performance of the registration. To study the influence of these changes, the acquired images will be modified to generate disturbances such as seasonal changes, fog, blur and decrease in contrast and brightness.

### A. Impact of seasonal changes

This numerical simulation is based on the recovery of two image DBs covering the same geographical area but photographed in different seasons. Thus, one DB will serve as a reference and will generate the descriptors (previously called DB) and the other will provide the images acquired by the drone. This type of seasonal change has a strong influence on rural and forest topography, which have few descriptors.

The histogram of the figure 22 shows the drift distribution on a panel of 768 images of rural topography. This histogram shows a performance degradation beyond 100 meters of about 68%.

<figure><img src="image_30.png" /><figcaption>Fig.22. Histogram of drift distribution for the 768 images (rural topography)</figcaption></figure>

Histogram of the figure 23 illustrates that seasonal change has an influence and degrades the number of matches identified per image.

<figure><img src="image_31.png" /><figcaption>Fig.23. Histogram of the distribution of the number of matches detected per image (rural topography)</figcaption></figure>

The DB contains only 246 images representing forest topology. The histogram of the figure 24 shows a degradation of 24% for this type of topology.

<figure><img src="image_32.png" /><figcaption>Fig.24. Histogram of drift distribution for the 246 images (forest topography)</figcaption></figure>

According to these results, rural topography is more affected by seasonal changes than forest topography. This is due to the strong changes in rural landscapes in terms of the colors of agricultural fields from one season to another.

One of the possible solutions, but very expensive, to circumvent this problem would be to have a DB per
<figure><img src="image_33.png" /></figure>

season. The other solution, applied in this study, is to extract one of the three RGB layers (Red, Green, Blue) when converting the images to gray scale, to calculate the SURF descriptors. It appears that the green layer is the most impacted by seasonal changes. Removing the green layer before converting the images to grayscale significantly reduces the differences between the two images from different seasons.

## B. Impact of fog

Fog is a very common meteorological phenomenon, which may degrade the quality of the acquired images and affect the registration and position calculation. To simulate fog, we use a PNG mask representing fog, which we apply to the acquired image. The variation of opacity of this mask allows simulating different intensities of fog.

Simulations were performed on 512 images mixing rural and forest topographies. The histogram of the figure 25 shows the influence of fog opacity on the number of matches identified per image.

<figure><img src="image_34.png" /><figcaption>Fig.25. Histogram of the distribution of the number of matches for different fog opacities</figcaption></figure>

We can see that the number of matches decreases as the fog opacity increases and that for an opacity of 80%, it is no longer possible for most images to be matched. The corollary of this is that, for 80% opacity, locating the drone becomes almost impossible, as illustrated in the histogram of the figure 26.

<figure><img src="image_35.png" /><figcaption>Fig.26. Histogram of drift distribution for different fog opacities</figcaption></figure>

## C. Impact of contrast and brightness

The images in the DB are taken under optimal weather conditions where the brightness is maximum, and the sky is clear (no cloud shadows). However, the images acquired by the UAV may have low brightness and contrast values compared to the DB depending on the position of the sun and the weather conditions.

To study the effect of such conditions on the quality of the registration, the acquired images will undergo changes in brightness and contrast at different degrees before performing the position calculation. Three decreasing levels of brightness and contrast, respectively 1 to 3, are defined, with level zero being the original image.

Simulations were performed on 768 images mixing rural and forest topographies. Histogram of the figure 27 shows the influence of the decrease in contrast and brightness on the number of matches identified per image.

<figure><img src="image_36.png" /><figcaption>Fig.27. Histogram of the distribution of the number of matches for different levels of brightness and contrast</figcaption></figure>

We can see that the number of matches decreases as a function of the level of darkening of the image, so that for levels 2 and 3, it is almost impossible for most images to be matched. This has the corollary that, for these levels, the localization of the UAV becomes almost impossible, as illustrated in the histogram of the figure 28.

<figure><img src="image_37.png" /><figcaption>Fig.28. Histogram of the distribution of drifts for different levels of brightness and contrast</figcaption></figure>
<figure><img src="image_38.png" /></figure>

The solution consists in correcting the images presenting weak levels of contrasts, by using a digital treatment based on the technique of the equalization of the histograms. Indeed, the histogram of an image represents the distribution of the intensities of colors or levels of gray. In an image with a low contrast, the histogram is distributed over a small range of values. The equalization consists in better distributing these intensities by spreading the histogram, which makes it possible to increase the contrast.

### D. Impact of blur

The drone in flight undergoes vibrations caused by the weather conditions. These vibrations can cause blurring on the acquired image. In numerical simulations, the blur is produced by applying a Gaussian filter, by varying its standard deviation $σ$. The blur is all the more pronounced as the value of the standard deviation of the Gaussian function increases. We define three increasing levels of this standard deviation.

Simulations were performed on 768 images mixing rural and forest topographies. Histogram of the figure 29 shows the influence of the blur intensity on the number of matches identified per image.

<figure><img src="image_39.png" /><figcaption>Fig.29. Histogram of the distribution of the number of matches for different blur intensities</figcaption></figure>

As the blur becomes larger, fewer descriptors are detected. In such a way that, for $σ = 3$, descriptors become so rare that there is no longer the possibility, for 175 images, to detect matches. The drift is directly related to the blur intensity as shown in the histogram of the figure 30.

<figure><img src="image_40.png" /><figcaption>Fig.30. Histogram of the drift distribution for different blur intensities</figcaption></figure>

## XI. CONCLUSION

This study allowed evaluating the influence of false matchings on the accuracy of position calculation, especially for topographies with few descriptors, such as rural and forest images which are more representative of the topographies of Western Europe. This algorithm is based on an original approach totally absent in the literature, using the “relative length comparison” mathematical method. Moreover, this method is limited on the number of matches to be processed between two images. This limit corresponds to the compromise between accuracy and processing time. Therefore, the number of descriptor matching should not exceed 6, with the execution time of the order of 140ms.

However, this method is not adapted to process images with many descriptors, such as cities. In this case, to eliminate false matchings, the chosen method is inspired by one of the articles [5] studied in the state of the art. This algorithm is based on approach on “similarities between transformations” mathematical method. For the number of descriptors matching over 6, the method by similarities succeeded in eliminating the false matches and thus rectifying the drift in 98% of the cases. The median execution time is about 5ms. By combining these two mathematical approaches, to improve the matching process, we were able to implement one original algorithm, named in this study, hybrid method. The use of this original algorithm has significantly reduced the number of false matchings. The robustness of this algorithm has been tested on different extreme configurations such as on any type of topography and on environmental conditions. Seasonal changes are the most common and most problematic, especially for rural topography. In fact, for two different seasons, there is a performance degradation of about 67%. Opacity higher than 80% in fog conditions implies that nearly 80% of images almost no longer have any descriptors with matching with those of the DB. Contrast, brightness, and blur have less impact on matching detection and drift and their impacts can be limited in non-extreme situations by post treatment or by camera gyrostabilization. As a
<figure><img src="image_41.png" /></figure>

result of this study, some limitations of absolute
registration were identified with respect to the
differences between the acquired images and the DB.
The results of this study should be used to choose an
optimal relative and absolute coupling mode.

BIBLIOGRAPHY

[1] Aurelien Yol, B. D.-E. (2014). Vision-based Absolute Localization for Unmanned.

[2] Zhao Chunhui, W. R (2014), Visual odometry and scene matching intéfrated navigation system in UAV

[3] Andrea Cesetti, E. F. (2011). A Visual Global Positioning System for Unmanned Aerial Vehicles Used in Photogrammetric Applications.

[4] Lucier, J. W. (2018). Automatic UAV Image Registration Using Feature Detection and Matching with Satellite Imagery.

[5] Xiao Liu, Congying Han, Tiande Guo (2014). A Robust Point Sets Matching Method

[6] Dragos Costea, M. L. (2016). Aerial image geolocalization from recognition and matching of roads and intersections.

[7] Isabelle Cléri, B. V. (2014). Automatic georeferencing of a heritage of old analog aerial photographs.

[8] Ouk Choi, I. S. (2009). Robust feature point matching by preserving local geometric consistency.

[9] Yefeng Zheng, D. D. (2006). Robust point matching for nonrigid shapes by preserving local neighborhood structures.