UAV Control on the Basis of 3D Landmark Bearing-Only Observations

The article presents an approach to the control of a UAV on the basis of 3D landmark observations. The novelty of the work is the usage of the 3D RANSAC algorithm developed on the basis of the landmarks’ position prediction with the aid of a modified Kalman-type filter. Modification of the filter based on the pseudo-measurements approach permits obtaining unbiased UAV position estimation with quadratic error characteristics. Modeling of UAV flight on the basis of the suggested algorithm shows good performance, even under significant external perturbations.


Introduction
Modern UAV's navigation systems use the standard elements of INS (inertial navigation systems) along with GPS, which permits correcting the bias and improving the UAV localization, which are necessary for resolving mapping issues, targeting and reconnaissance tasks [1]. The use of computer vision as a secondary or a primary method for autonomous navigation of UAVs has been discussed frequently in recent years, since the classical combination of GPS and INS systems cannot sustain autonomous flight in many situations [2]. UAV autonomous missions usually need so-called data fusion, which is a difficult task, especially for standard INS and vision equipment. It is clear that cameras provide visual information in a different form, inapplicable to UAV direct control, and therefore, one needs an additional on-board memory and special recognition algorithms.

Visual-Based Navigation Approaches
Several studies have demonstrated the effectiveness of approaches based on motion field estimation and feature tracking for visual odometry [3]. Vision-based methods have been proposed even in the context of autonomous landing management [2]. In [4], visual odometry based on geometric homography was proposed. However, the homography analysis uses only 2D reference points coordinates, though for the evaluation of the current UAV altitude, the 3D coordinates are necessary. All such approaches presume the presence of some recognition system in order to detect the objects nominated in advance. Examples of such objects can be special buildings, crossroads, tops of mountains, and so on. The principal difficulties are the different scale and aspect angles of observed and stored images, which leads to the necessity of huge template libraries in the memory of the UAV control system. Here, one can avoid this difficulty, because of the usage of another approach based on the observation of so-called feature points [5] that are scale and aspect angle invariant. For this purpose, the technology of feature points [6] is used. In [7], the approach based on the coordinate correspondence of the reference points observed by the on-board camera and the reference points on the map loaded into the UAV's memory before the mission start had been suggested. During the flight, these maps are compared to the frame of the land, directly observed with the help of an on-board video camera. As a result, one can detect the current location and orientation without time-error accumulation. These methods are invariant to some transformations, and they are noise-stable, so that predetermined maps can be different in scale, aspect angle, season, luminosity, weather conditions, etc. This technology appeared in [8]. The contribution of this work is the usage of a modified unbiased pseudo-measurements filter for bearing-only observations of some reference points with known terrain coordinates.

Kalman Filter
In order to obtain metric data from visual observations, one needs first to make observations from different positions i.e., triangulation and then use nonlinear filtering. However, all nonlinear filters either have unknown bias [9] or are very difficult for on-board implementation, like the Bayesian-type estimation [10,11]. Approaches for position estimation based on bearing-only observations had been analyzed long ago, especially for submarine applications [12] and nowadays for UAV applications [1].
A comparison of different nonlinear filters for bearing-only observations in the issue of ground-based object localization [13] shows that the EKF (extended Kalman filter), the unscented Kalman filter, the particle filter and the pseudo-measurement filter give almost the same level of accuracy, while the pseudo-measurement filter is usually more stable and simple for on-board implementation. This observation is in accordance with older results [12], where all of these filters were compared in the issue of moving object localization. It has been mentioned that all of these filters have bias, which makes their use in data fusion issues rather problematic [14]. The principle requirement for such filters in data fusion is the non-biased estimate with the known mean square characterization of the error. Among the variety of possible filters, the pseudo-measurement filter can be easily modified to satisfy the data fusion demands. The idea of such nonlinear filtering was developed by V.S. Pugachev and I. Sinitsyn in the form of so-called conditionally-optimal filtering [15], which provides the non-biased estimation within the class of linear filters with the minimum mean squared error. In this paper, we develop such a filter (the so-called pseudo-measurement Kalman filter (PKF)) for the UAV position estimation and give the algorithm for path planning along with the reference trajectory under external perturbations and noisy measurements.

Optical Absolute Positioning
Some known aerospace maps of a terrain in a flight zone are loaded into the aircraft memory before the start of a flight. During the flight, these maps are compared to the frame of the land, directly observed with the help of an on-board video camera. For this purpose, the technology of feature points [6] is used. As a result, one can detect the current location and orientation without time-error accumulation. These methods are invariant to some transformations and are also noise-stable, so that predetermined maps can vary in height, season, luminosity, weather conditions, etc. Furthermore, from the moment of the previous plane surveying, the picture of this landscape can be changed due to human and natural activity. All approaches based on the capturing of the objects assigned in advance presume the presence of some on-board recognition system in order to detect and recognize such objects. Here, we avoid this difficulty by using the observation of feature points [5] that are scale and aspect angle invariant. In addition, the modified pseudo-measurements Kalman filtering (PKF) is used for the estimation of UAV positions and the control algorithm.

Outline of the Approach and the Article Structure
One of the principal parts of this research is an approach to the estimation of the UAV position on the basis of the bearing-only observations. The original filter that uses the idea of pseudo-measurements had been suggested in reference [16] for the case of the azimuth bearing of the terrain objects nominated in advance. In reference [17], this approach had been extended to the case of two angle measurements, namely azimuth and elevation. However, the usage of this approach as a real navigation tool needs huge on-board memory and a sophisticated recognition algorithm, since the template and in-flight observed images, even of the same object, are rather different due to the changes of illuminance, the altitude of flight and the aspect angles. That is why the method based on the observation of feature points looks more attractive for in-flight implementation. In reference [7], an algorithm joining together the feature points approach and modified PKF had been suggested, though for 2D feature point localization, while the more advanced 3D localization had been suggested in references [18,19], which are the shortened versions of the methodology presented in this article.
In this work, we use a computer simulation of a UAV flight and on-board video camera imaging. The simulation program is written in MATLAB. The type of feature points is ASIFT, realized in OpenCV (Python) [20]. Feature points in this model work as in a real flight, because the images for the camera model and for the template images were transformed by projective mapping and created by observations from different satellites.
The next section presents the original RANSAC algorithm for 3D feature point localization. Sections 3 and 4 give the description of PKF, providing the unbiased estimation of the UAV position with the estimate of quadratic errors. Section 5 describes the locally optimal control algorithm for tracking the reference trajectory on the basis of PKF estimation of the UAV position. In Section 6, we give a new approach to the RANSAC robustness with the use of the UAV motion model. Section 7 presents the modeling results, and Section 8 is the conclusions.

Random Sample Consensus for Isometry
At every step, the algorithm deals with two images of a 3D landscape. An example of the landscape used for modeling is shown in Figure 1. The first image I c is obtained from the on-board UAV camera, the position of which is unknown and should be estimated. The second image I m was taken previously from a known position and uploaded into the UAV memory. The ASIFT method is used for both images to detect feature points, which are specified in pixels: and: and calculates their descriptors. The correspondence between images is constructed by using these descriptors, and thereby, the feature points are combined in pairs. However, many of these pairs are wrong, and therefore, these pairs are considered as outliers or they are not. The result of ASIFT correspondence is shown in Figure 2. The Earth coordinate system is the Cartesian coordinate system, which is rigidly connected with the Earth. Therefore, the algorithm uses a 3D terrain map of the area from which the image I m was taken and over which the UAV flies. Therefore, one can determine the coordinates of the points: which generated m i points in the Earth coordinate system. However, if i corresponds to the pair of points that is not an outlier, then the point r i also generates a point c i in the UAV camera. Another Cartesian coordinate system is rigidly connected with the UAV camera. The axis of the camera is parallel to the axis z. The transformation from the Earth coordinate system to the UAV coordinate system has the form: where b represents the coordinates of the camera in the Earth coordinate system and A is the orthogonal (AA T = I) rotation matrix defining the orientation of the UAV camera. Then, the points r i in the camera coordinate system are: To define the relation between r i and the feature points c i , one can use the model of the camera obscura. This model gives a central projection on the plane: where K is a known calibration matrix of the camera. Thus, the task is to estimate A and b on the basis of known c i , r i , K. The minimum number of feature point pairs needed to solve this task is three.
One can give the solution of the problem under the assumption that there are just three pairs: Points r i form a triangle in the space with the following sides: Meanwhile, due to the rectilinear propagation of light, each point r i lies on the beam r = a i t, where t is a scalar parameter, and: In order to find r i , we have to determine parameters t i , i = {1, 2, 3} that satisfy the system of quadratic equations: For the given t 1 , this system may be either solved analytically or has no solution. A determination of t 1 can be done numerically, for example by the bisection method.
Finally, one can obtain the coordinates of three points on the Earth's surface in the camera coordinate system r i and, at the same time, in the Earth coordinate system r i . The connection between them is: . Since A is the orthogonal matrix, then y = Ax implies ||y|| 2 = ||x|| 2 ; thereby: Therefore, we have eliminated A and obtained the problem of finding the intersection of three spheres, which can be solved analytically. This problem may have two solutions; one of them will be rejected later. When b has been found, solutions for A are as follows: Therefore, there are two options, and only one of them is correct: If the first one is correct, then the second one corresponds exactly to the turnover. As a result, A and b have been found by using three pairs of feature points and the height map. However, this approach alone is not suitable as the final solution, due to the following problems: 1. The method gives either knowingly false solution or no solution at all if among the three points there are outliers. 2. There is a strong dependence on the noise in the feature points' location.
Both problems may be solved with random sample consensus (RANSAC) [21,22]. From the general selection of points, one needs to select N times a subsample of size three. For each subsample j = {1, 2, · · · , N}, one can calculate A j and b j , which allows one to simulate the generation of all feature points on the UAV camera: Then, one can evaluate which points are the outliers by the threshold where d is the threshold. Here, s ji = 0 means that projection of the i-th point on the j-th point is counted as an outlier, otherwise s ji = 1. The answer will be the following: Therefore, we really solve the problem of outliers. Next, we find the required number of N subsamples of a size of three, such that among them, there will be at least one subsample without outliers with probability p. Let the proportion of outliers be 1 − w. It is easy to see that [21]: In the case when w = 1 2 : N(0.9999) ≈ 69, which shows the high efficiency of algorithm. After that, the points marked as outliers are removed from consideration. The clarification of the response is made by the numerical solution of the following optimization problem on the set of remaining points: Thereby, the second problem of noise reduction may be solved. However, one can use a more advanced procedure, which takes into account the motion model. A more stable solution may be obtained with the aid of so-called robust RANSAC [23]; the idea is to use predicted values of (A, b) for the preliminary rejection of outliers from the pairs of observed feature points. Therefore, if on the k-th step of the filtering procedure, the values (A k , b k ) have been obtained, one can use the following values on the (k + 1)-th step: whereb k+1 is the predicted estimate of the UAV attitude obtained on the basis of the PKF estimate. The filtering approach is described in Section 5.

Filtering Problem Statement
The problem of bearing-only filtering is considered to determine the coordinates of the UAV, which can observe some objects with known coordinates. These objects can be either the well recognizable objects or a network of radio-beacon stations with a well-specified frequency and known coordinates. In this work, the function of beacons is performed by the feature points determined with the aid of the RANSAC algorithm. The UAV has the standard set of INS devices, which enables it to perform the flight with some degree of accuracy, which, however, is not sufficient for mission completion.

Model of the UAV's Motion
We assume that a UAV motion is described by three coordinates (X(t k ), Y(t k ), Z(t k )) and velocities (V x (t k ), V y (t k ), V z (t k )). At times t k = k∆t, k = 1, 2, ..., these coordinates satisfy the following equations: where: is the vector of state-velocities, is the vector of accelerations, which we consider as controls, is the vector of current perturbations, modeling the turbulence components of the wind and the autopilot errors, as well. The matrices A and B are equal: and stochastic Equation (2) describes a controlled and perturbed UAV motion.

Measurements
Assume that (X i , Y i , Z i ) are the coordinates of the i-th reference point and φ i (t k ), λ i (t k ) are the bearing angles on that point. The measuring scheme is shown in Figure 3. At moment t k , these angles satisfy the relations: are uncorrelated random variables with zero means and variances σ 2 x , σ 2 y , σ 2 z , σ 2 φ , σ 2 λ , defined as errors in the measurement of the coordinates of the i-th reference point and of the tangents of angles φ i (t k ), λ i (t k ) and forming the white noise sequences.

Remark 1.
In the majority of works based on the method of pseudo-measurements, another model is used. It assumes the measurements of the angles with Gaussian errors (see [12,14] and most of the successive works). However, in the real definition of the object position in the image or in the matrix of sensors, the system measures the distance between the object image and the center of the sensor, that is the tangent of the bearing angle. This simple observation allows one to find the unbiased estimate of the UAV coordinates.
One can rewrite Equation (3) for angle λ i (t k ) as follows: Remark 2. The indicator function I i (t k ) = 1 if at t k the bearing of the i-th reference point occurs, and I i (t k ) = 0 otherwise. For convenience, we assume that I i (t k ) = 1.
Therefore, at the moment t k , the UAV control system determines the angles φ i (t k ) and λ i (t k ), related to the coordinates of the UAV (X(t k ), Y(t k ), Z(t k )) as follows:

Linear Measurements Model
The idea of the pseudo-measurement method is to separate in Equation (5) the observable and non-observable values, which gives the following observation equations: where X i , Y i , Z i represent the coordinates of the i-th feature point determined with the aid of the RANSAC algorithm and φ i , λ i are the corresponding observable bearing angles measured by the system. Thus, the left-hand side of Equation (6), that is (m φ k , m λ k ), corresponds to the observable values, whereas the right-hand side containing the coordinates of the UAV corresponds to the non-observable ones. The aim is to estimate the coordinates and velocities of the UAV on the basis of linear observation Equation (6) and the motion model Equation (2). Therefore, the measurement vector has the following form: Thereby, we obtain the system Equation (7) of linear measurement equations, though the noise variance depends on non-observable coordinates. By using V.S. Pugachev's method [15], one can obtain the unbiased estimate and the variance with the aid of a prediction-correction filter [24]. Moreover, we do not need to assume the Gaussian distribution of errors that is not valid in bearing observations with optical-electronic cameras with discrete image sensors.

Prediction-Correction Estimation
Assume that at the moment t k , we have unbiased estimatesX(t k ), such that: with the following matrix of the mean-square errors: Problem 1. Find the unbiased estimatesX(t k+1 ) and matrixP(t k+1 ) on the basis of estimates at the moment t k , m k , the known position of the i-th observable object (X i , Y i , Z i ) and the UAV's motion parameter Equation (2). These estimates must satisfy Equation (8) and give the matrix Equation (9) for the moment t k+1 .

Prediction
The prediction is obtained by assuming that at the moment t k+1 , the values of φ(t k+1 ), λ(t k+1 ) will be known: (10) Assuming that the motion perturbations and the UAV position are uncorrelated, we obtain: where the elements of this matrix are: Note that σ 2 X is not the same as σ 2 x and similarly for the other indices. Then, the following valuesP xm (t k+1 ),P ym (t k+1 ),P zm (t k+1 ),P V x m (t k+1 ),P V y m (t k+1 ),P V z m (t k+1 ), P mm (t k+1 ) should be calculated using the following relations: and the identities: where we consider that the position of the i-th object is known and use the non-correlatedness of ε x k+1 , ε y k+1 , ε z k+1 , ε φ k+1 , ε λ k+1 and differences (X(t k+1 ) −X(t k+1 )), (Y(t k+1 ) −Ỹ(t k+1 )) and (Z(t k+1 ) −Z(t k+1 )).
Finally, we get: In a similar way, we calculate: Therefore:

Correction
After getting the measurements at the moment t k+1 , one can obtain the estimate of the UAV position at this moment. Therefore, the solution of Problem 1 has the form: (20) and the matrix of the mean square errors is equal to: where:P (t k+1 ) = (P xm (t k+1 ),P ym (t k+1 ), ...,P V z m (t k+1 )) T

Robust Filtering on the Basis of the UAV Motion Model
The RANSAC method calculates the rotation matrix and the coordinates of the camera {A * , b * } in the Earth coordinate system with some minor error. However, the RANSAC method can give quite the wrong answer, called an outlier. It could happen, for example, if the frames I c and I m do not depict common objects. We provide further a method that makes a decision about whether {A * , b * } is an outlier or not. This problem has been considered in relation to the exclusion of outliers in the RANSAC-type procedures [25,26]. Here, we use the modification of the robust RANSAC [23] based on PKF for bearing-only observations [17].
After the prediction step of the Kalman filter, one can estimate the UAV (camera) position and the matrix of the mean square errors:X =X(t k+1 ),P =P(t k+1 ).
Like in [26], one can suppose that the corresponding probability density is Gaussian. The reason is that the PKF gives the best linear estimates obtained until the current time t. This estimate is the sum of uncorrelated random variables with almost the same variations, at least on the short intervals preceding the current time. It gives the opportunity to approximate the probability density distribution by the Gaussian one. Further extension of the robust RANSAC technique is based on the prior distribution of the UAV attitude. The approach has been developed in [23,27] on the basis of the extended Kalman filter (EKF). However, the estimate given by the EKF has an unknown bias and, of course, does not give the posterior Gaussian distribution. Therefore, the PKF, which gives an unbiased estimate, looks more preferable under the hypothesis of the posterior Gaussian distribution. Therefore, at the (k + 1)-th step, the posterior distribution of r i corresponding to an inlier is assumed to be Gaussian, that is according to Equation (1): where P rr is the covariance matrix of the landmarks localization. Further, in the estimation algorithm, the pair {A k ,X(t k+1 )} is considered as an outlier at the confidence level 95% if: Otherwise, the correction step is based on {A k ,X(t k+1 )}. Of course, all such nonlinear conjectures need confirmation on the basis of statistical modeling, which is one of the results of this article. One can observe the performance of robust filtering in the following figures. Figure 4 shows the correspondence between feature points obtained without a UAV motion model. Next, Figure 5 shows the correspondence established on the basis of the UAV motion model. The number of outliers reduces substantially.

Control of the UAV
Control of a UAV that ensures its motion along the reference trajectory may be determined on the basis of the standard deterministic linear-quadratic approach [28]. However, the problem of control on the basis of bearing-only observation is different from the standard one. It should be underlined that this problem is a non-linear one and cannot be solved by the standard way. The problem of the optimal control for the system Equation (2) is the stochastic one with incomplete information and does not have an explicit solution. However, for practical reasons, one can simplify it by considering the locally optimal control. Here, we discuss the following problem: Problem 2. Find the locally optimal controls a x (t k ), a y (t k ) and a z (t k ) aimed to keep the motion of the UAV along the reference trajectory.
Assume that we have some reference trajectory X nom (t k ). Therefore, at the moment t k+1 , we have to minimize the following expressions: Let us consider the components of the E 1 expression: Then, we square these components and take the derivative of the sum with respect to a x (t k ) given that some components are uncorrelated: Finally, we get: We take into account that the acceleration of the UAV has limitations [a x min , a x max ], so the control acceleration has the form: Similarly, we obtain the expressions for a c y (t k ) and a c z (t k ). Thus, we get the following solution of Problem 2 [19]:â where:â (t k ) = (a x (t k ), a y (t k ), a z (t k )) T X(t k ) = (X(t k ), Y(t k ), Z(t k )) T V(t k ) = (V x (t k ), V y (t k ), V z (t k )) T and similarly for the nominal trajectory components.

Experimental Results
In this section, we give the results of the algorithm's modeling. The UAV is virtually flying over the landscape shown in Figure 1. This image has been obtained from Google Maps, and for verification of the algorithm, the image of the same region obtained from another Bing satellite was used. Therefore, these two images modeled the preliminary downloaded template and the image obtained by the on-board camera. The result of virtual flight experiment is shown in Figure 6.

Results and Discussion
In the modeling of the control algorithm, we use the UAV moving approximately with a velocity of 50 m/s, though the change of the altitude is assumed to be rather substantial. The control algorithm takes into account the constraints imposed on linear acceleration and angular velocities. The software developed for modeling may be used in a real on-board navigation system, as well. Moreover, the filtering algorithm based on unbiased estimation may be easily incorporated with the INS, since it gives also the unbiased square error estimates, which opens the way to correct data fusion. The quality of tracking for x, y, z components is shown below in Figures 7-9, respectively. In all of these figures, blue dots correspond to the reference trajectory, black dots to the real path and red squares to the moments, where the estimates of the UAV positions have been obtained and assumed to be reliable according to the robust RANSAC algorithm. One can observe that in the "measurement" areas, the algorithm estimates the coordinates with high accuracy, and the control provides the tracking with high accuracy, as well.    The high accuracy is in accordance with the standard deviation (SD) theoretically calculated from the PKF. The value of the averaged standard deviation, which is the square root of P xx (t) + P yy (t) + P zz (t), is shown in Figure 10 below.

Conclusions
The main result of the work is the new algorithm of the UAV control based on the observation of the landmarks in a 3D environment. The new RANSAC based on the UAV motion model permits one to exclude the huge number of outliers and, by that, to provide the reliable set of data for the estimation of the UAV position on the basis of the novel non-biased PKF algorithm. This work is just the beginning of the implementation of this approach in the navigation of UAVs during long-term autonomous missions.