An H∞-Filter-Based Turn-Prediction Algorithm For Tracking Of Manoeuvring Targets

Introduction

To design an efficient air surveillance system, the expected tracking performance should be considered in the worst case of limited and noisy input observations. An essential task in a tracking algorithm is the target motion estimation based on a chosen filter structure and a system dynamic model. The reduction of estimation errors is a problem that has received a lot of attention, particularly when the target manoeuvres [1−4]. To deal with the measurement uncertainty, useful information about the motion must be considered in the estimation task. However, this information cannot be measured directly at all times, or extracted easily from the observations. The most important information is whether a target is manoeuvring with a turn manoeuvre or performing a uniform motion in a straight-motion manoeuvre with longitudinal acceleration. This information is then either taken into account in the target dynamic models, or deduced in the tracking algorithm using specific techniques.

Most tracking models [3,4] are linear in the sense they consider targets are moving in a straight line and the acceleration process is accounted for as stochastic uncertainty. The corresponding tracking performance may be degraded if the model used does not fit the real target motion, particularly when the target begins a manoeuvring stage. In contrast to linear models, non-linear models [4−7] are developed to fit all possible target motions. Although the non-linear model-based tracking algorithms for manoeuvring targets have improved performance, little consideration was given to these algorithms because of their implementation complexity and sensitivity to disturbances affecting the motion estimation when the target straightens. As an alternative to alleviate these difficulties, several implementation strategies have been developed to meet the non-linear model performances without growing in computational complexity. Some of these strategies are based on adapting the tracking model to the actual manoeuvring motion using different manoeuvre detection techniques [8-10]. The problem with these strategies is the detection time-delay resulting in a manoeuvre model that does not match suitably the actual motion causing the target loss. Strategies combining two or several types of motion models have been proposed in the literature [11−14], where each model is associated with a manoeuvre type. We cite as examples the interacting multiple model filters [15−17].

To account for manoeuvres, several models have been developed to model acceleration process [18]. We cite as an example, the Singer acceleration model [19,20], which is generalized to model the Jerk process [21]. While it is considered as effective for describing different manoeuvring types, the Singer model is inadaptable for turn manoeuvres. As a consequence, the coordinated-turn models have been developed [22−24]. To account for different types of manoeuvres in a multiple model framework, the Semi-Markov models have been used to model the acceleration process [25−27]. The polynomial models [6,28] are not very attractive for tracking process because of the difficulty in proposing suitable methods for determining the polynomial coefficients. In addition, the computation requirements of the polynomial models grow with the polynomial’s order [18].

Based on aircraft dynamics parameters such as thrust T, lift L, roll rate, and target inertial angular velocity components (p,q,r), the coordinated turn can be described by a set of coupled non-linear differential equations, which are difficult to solve. This model has been then simplified in [29,30] to a kinematics problem described by a non-linear but simplified prediction equation with no need of the inertial parameters (T,L,p,q,r). Although these simplifications, the simplified non-linear model is still computationally costly to implement. Reoker [31] and Kawase [32,33] have developed a geometric approach for circular prediction where the target position is constrained to lie on a circle. This approach consists in defining, from previous measurements, the centre (central-point-approach, CPA) and the radius of a circle, and forcing the predicted position to lie on this circle. The CPA is then predicted in a polar-coordinate system. This approach is intractable because of the complexity of CPA computation, and the necessity of circle updates every new acquired measurement.

To overcome the above difficulties, Tenne [34,35] developed an approach for circular prediction that does not require CPA and radius calculation. This approach is averred to be well adapted to real-time applications with comparable performances to the Kawase approach [32,33]. An alternative approach for turn-angle estimation is the ellipsoidal prediction, presented in [36], which is based on a generalized Hough transform with the supposition that targets fly in an ellipse with a constant velocity. The generalized Hough transform is used to compute the ellipse parameters (centre coordinates x and y, and ellipse major and minor axes with the assumption that the major axis is oriented along the X-axis). While this approach allows improvement of tracking quality over the circular prediction approaches, it is still computationally costly due to the computation of ellipse parameters, which cannot be detected accurately. In addition, the major axis parallel to X-axis assumption is not always tractable.

The Hough transform is known for its capability of detecting segments in image processing [37]. It has been applied in target tracking by detecting segments formed by target positions along the target trajectory. In this paper, we developed a generalised turn-prediction technique based on a Hough transform to derive the turn angle formed by two adjacent segments, and use this angle to predict target position. A ${\gamma H}_{\infty }$ filter is applied to update the turn angle after receiving a new measurement. The derived filter is combined with a straight-motion filter in a hybrid scheme for manoeuvring target tracking. The proposed technique does not involve large amount of computation, and does not impose any restriction on the manoeuvre form.

The paper is organized as follows: after an overview of the existing circular prediction approach in Section II, we describe the proposed Hough-transform-based turn-prediction approach in Section III, and the ${\gamma H}_{\infty }$ filter for turn-angle estimation in Section IV. The application of the proposed approach for manoeuvring target tracking is presented in Section V. Simulation results, comparisons and performance analyses are presented in Section VI, and concluding remarks are made in Section VII.

Overview of the existing circular prediction approach

In this section, we present an overview of the existing circular prediction approach described by Tenne [34]. The principle of this approach is based on reconstituting a circle from previous target positions, and forcing (assuming) the future position to lie on this circle. For this end, we define three points P₁, P₂, and P₃ on the same arc and we seek to express the fourth point as a function of these three points (See Figure 1). We assume the fourth point P₄ to lie on this same arc. We define the angle φ₁ as the angle formed by the segments R₁₂ and R₁₃ in the triangle ∆₁₂₃, and the angle φ₂ as the angle formed by the segments R₁₃ and R₁₄ in the triangle ∆₁₃₄. R_ij indicates the distance between points P_i and P_j. We associate with the first point P₁ a relative Cartesian coordinate system (U, V). The segments R₂₄ and R₃₄ will be then expressed as follows:

where $(u_i,v_i)$are the relative coordinates of the point P_i, i=1,4. From (1) and (2), and with some manipulation, we obtain the following expressions:

By writing (3) and (4) in a matrix form, the fourth point relative coordinates $u_4$and $v_4$can be derived as:

The unknown parameters to get the forth point coordinates ($u_4$,$v_4$), are the angle φ₂ and the distance R₁₄. The angle φ₂ is estimated from the previous time step, while the distance R₁₄ is deduced from the triangle ∆₁₃₄ of Figure 1, as follows [34]:

According to the properties of points lying on a circle, angles constituted by segments begetting same arcs on a circle are equals. Thus, it can be shown that ₂=γ₁ and ₁=γ₂, and the distance R₃₄ is calculated as follows:

The distance R₁₄ can be obtained by replacing R₃₄ from (7) into (6). The problem we wish to solve, here, is the computation of the position P₄ coordinates based on the three previous target positions. Using the turn angle φ₂ predicted from the previous time step based on a linear filter such as Kalman or${\gamma H}_{\infty }$, the predicted position coordinates of P₄ expressed in (5), are returned to original system by performing the following transformation: $x_4=u_4+x_1$and $y_4=v_4+y_1$.

After receiving the P₄ position measurement, the turn angle φ₂ measurement is obtained from the triangle Δ₂₃₄ of Figure 1 as:

and thus:

After that, the turn angle φ₂ will be updated using a straight motion tracking filter such as a Kalman filter.

Description of the proposed approach

In this section, we extend the circular-prediction approach to a more general shape of turns by overcoming the restriction of circular assumption ₂=γ₁ and ₁=γ₂ (Figure 1) and we propose a Hough-transform-based approach, as an alternative for turn-angle prediction.

Approach description

A straight line represented by Cartesian coordinates (x, y) is represented in the Hough space as follows:

where ρ is the perpendicular from the origin to the axis passing by the point (x_i, y_i), and θ its azimuth. The problem to solve, here, is presented as follows: we have two points P₁ and P₂ with known Cartesian coordinates (x₁, y₁) and (x₂, y₂) respectively, and we would like to determine the coordinates of a third point P₃ (x₃, y₃), as shown in Figure 2. The Hough parameters of the segments P₁P₂ and P₂P₃ are defined by (ρ₁₂,θ₁₂) and (ρ₂₃,θ₂₃) respectively, where the angles θ₁₂ and θ₂₃ are also known. The points P₁ and P₂ are linked from the Hough space parameters (ρ₁₂,θ₁₂) as follows

The points P₂ and P₃ are linked from the Hough transform parameters $\left({\rho }_{\text{23}},{\theta }_{\text{23}}\right)$ as:

From (11) and (12) we can derive:

In addition, the Cartesian and polar coordinates of the segments P₁P₂ and P₂P₃ are linked as follows:

By replacing for (15) and (16) in (13) and (14), we obtain:

The equations above have as solutions ${\psi }_{\text{12}}-{\theta }_{\text{12}}=\pi /2$ and ${\psi }_{\text{23}}-{\theta }_{\text{23}}=\pi /2$, from which the expression of turn angle is given as follows:

Assuming the target has a constant velocity and the measurement sampling time is constant permits to write$R_{\text{12}}^2=R_{\text{23}}^2$. These assumptions do not affect significantly the turn-angle estimation and are valid since real target trajectories are approximated by straight lines with sudden turning manoeuvres. Then we can write $R_{\text{12}}^2=R_{\text{23}}^2={\left(x_3-x_2\right)}^2+{\left(y_3-y_2\right)}^2$, from which we derive:

Equation (14) can be rewritten in the form:

where the angle θ₂₃ is equal to ${\theta }_{\text{23}}={\theta }_{\text{12}}+{\varphi }_2$. By replacing (20) in (21), and with some manipulation, the coordinates of point P₃ are expressed as follows:

and:

The only unknown parameter is the turn angle φ₂ that will be estimated from the previous time step using a linear filter (such as a Kalman or ${\gamma H}_{\infty }$ filter). It will be updated after receiving the P₃ position measurement. The turn tangle φ₂ will be computed using the angle θ₁₂ inherited from previous time step and the angle θ₂₃ so that ${\varphi }_2={\theta }_{\text{23}}-{\theta }_{\text{12}}$and expressed as follows:

Characterization of the turn angle

We suppose that the turn angle ₂, defined by the measurements of the last three successive target positions, is positive in the counter clockwise direction and negative otherwise. If we suppose the measurements are independent random variables of a Gaussian distribution, the turn angle measurement is also an independent random variable of Gaussian distribution N(µ, σ²).

In the straight motion case, the measurements have a tendency to be aligned. Consequently, the mean of the turn angle is µ=0. If the target begins a turn manoeuvre, a bias superposes on the mean µ, which becomes non-zero. This property can be used to detect the beginning and end of turn manoeuvres.

From turn angle measurement in (24), and with some mathematical developments, the corresponding variance can be approximated by the following expression:

We note that the angle variance is inversely dependent on target velocity.

Application of h filtering to turn angle estimation

We present in this section a ${\gamma H}_{\infty }$filter solution to continuously estimating the turn angle. The ${\gamma H}_{\infty }$filter is a robust filter that can solve the tracking problem in highly changing processes. In terms of convergence of process covariance and estimation gain matrices; it is faster than the Kalman filter, particularly when the process change rate goes from constant to variable. The ${\gamma H}_{\infty }$filter employs the same system and measurement dynamic models as the Kalman filter [13]. Thus, the following dynamic model is valid for both filters.

We assume that the variation of  is given by a uniformly accelerated motion model, which may be described by the following equations [3]:

where φ is the turn angle,  is the variation rate of φ, $\dot{\omega }$ its acceleration and T is the target measurement-sampling period. We associate to this process a linear model expressed in state space representation by the following equations:

where Φ is the model transition matrix, Г is the input matrix, Η is the observation matrix, $\underset{\_}{\eta }$ is the state vector containing the turn angle and its change rate, and Z is the measurement vector. The parameter v_k is the error affecting the turn angle measurement, and w_k is the acceleration noise affecting the turn angle process. Both w_k and v_k are considered white, zero-mean noises with user-defined variances Q_ and R_ respectively. The measurement of  is given by (24) in case of proposed Hough-transform-based turn-prediction method (using (9) in the case of existing circular-prediction method). In addition to smoothing and noise rejection, the use of filtering technique in this section provides a prediction at all tracking instants of the turn angle and its properties that are essential to the target tracking operation. In the following, we summarise the ${\gamma H}_{\infty }$tracking filter equations [13] applied to system model given by (28) and (29):

If the parameter γ tends to zero then the gain K_k is equivalent to a Kalman filter gain. If γ is too big when the target is manoeuvring, then the system may diverge. In this work γ is changed, under the hybrid filter scheme, according to the likelihood ratio of both Kalman and ${\gamma H}_{\infty }$ filters, as ise explained later. At each time k, the following condition must be held:

The weighting matrix S_k is chosen so that $S_k<P_{k/k-1}^{-1}+H_{\varphi }^T{R}_{\varphi }^{-1}{H}_{\varphi }$, and the parameter γ is always taken in the interval [0,1]. The matrices Q_ and R_ are chosen to ensure a good performance of the filter.

Application to target tracking

The two turn-prediction approaches presented earlier in this paper can be applied to tracking of manoeuvring targets in two ways: the stand-alone one and the combined one. The derived turn prediction filter provides good tracking performance when targets exhibit a turn manoeuvre. However, as trajectories are formed of straight lines separated by curves, the performance of a stand-alone turn-prediction filter can be degraded. Therefore, it is convenient to integrate the proposed turn-prediction filter with straight-motion filters by means of a combination strategy. In the following, we present two combination approaches. The first is based on a turn-manoeuvre detector that allows switching between the straight-motion filter and the turn-prediction filter. The second approach consists of using a hybrid filter.

Turn detection approach

In this approach, a turn detector is used to apply the turn prediction algorithm to manoeuvring target tracking. It is a simple binary test that could be a Bayesian test or a Neyman-Pearson test. The decision is taken from the hypotheses H₀, stating that the target is flying in straight track, and H₁, stating that the target is performing a turn manoeuvre.

Under the hypothesis H₀ (straight track) the turn angle is a random variable that follows a normal distribution law with zero mean and variance σ. While under the hypothesis H₁ (turn manoeuvre), the turn angle is a normal random variable of non-zero mean and variance σ. The decision test can be then formulated as:

where ${ƒ}_{\varphi /H_i}\left(\varphi /{{\rm H}}_i\right)$ is the probability density function of angle  under the hypothesis H_i with i=0,1. The decision threshold η is determined by the user according to experimental results of correct detection probability. Following the test result in (39), the algorithm switches between the turn-prediction filter and the straight-motion filter. A block diagram of the turn-angle detection-based scheme is presented in Figure 3.

Hybrid filter approach

The main objective of a tracking algorithm is estimating target state and obtaining a smoothed trajectory. If the measurements are very noisy, then the predicted turn angles will not be accurate making the tracks obtained at the output of the turn-prediction filter fluctuate wildly. On the other hand, the tracks obtained at the output of the straight-motion filter will be smooth but not accurate if a sharp manoeuvre is performed. Suppose now that a target is performing a turn manoeuvre with moderate noisy measurements. In this case the trajectory obtained by the turn-prediction filter will be accurate. So what happens if we combine the outputs of the two filters? This question gives rise to the concept of the hybrid straight/turn-prediction filter. This concept is based on a heuristic but powerful, logic of combination.

Suppose we have a tracking system for which we want to estimate the target states S. We design a straight-motion filter for this system and obtain the state vector S_L. We, then, design a turn-prediction filter for the same system and obtain the target state vector denoted by S_C. The outputs of the two filters will be combined, based on mode probabilities, to obtain the ‘hybrid filter’ [13]. In fact, the predicted states by the two filters are fused using a weighting factor, which will be determined from the likelihood of the two filters. The output of the hybrid filter can be formulated by the following expression:

where the parameter α∈[0, 1], is the relative weight given to the straight-motion filter performance. If α = 0, the hybrid filter is equivalent to the turn-prediction filter, while if α = 1 the hybrid filter is equivalent to the straight-motion filter. The parameter α can be chosen based on the relative confidence given by the designer to the performance of the two filters, which may be expressed in terms of the state estimation errors. One way to do this is based on the likelihood of the two filters expressed as following:

where ν_i,k is the innovation vector and θ_j,k its covariance matrix. We denote by i=1 the straight-motion filter mode and by i=2 the turn-prediction filter mode. The transition between the two modes is modelled by a first order homogenous Markov process. By defining m_i,k as hypothesis for which the corresponding mode is correct, then the transition probability from mode i to mode j at time k can be written as

and the mode probabilities p_j,k can be expressed as

The parameter c is used as a normalized factor. The combined state prediction ${\widehat{x}}_{k/k}$ and its error covariance matrix P_k/k are then expressed as

This combined state prediction will be then updated using a linear-model-based estimator. An illustration of the hybrid approach is given in Figure 4.

To insure estimation accuracy when the turn gravity goes high, the parameter γ of the ${\gamma H}_{\infty }$filter is varying according to the likelihood ratio between the straight-motion filter and the turn-prediction filter as follows:

where the parameter a is a normalization factor used to ensure filter stability and guaranteed filter performance. If the likelihood of the straight-motion filter is greater than that of the turn-prediction filter, the straight-motion filter becomes dominant. Alternatively, if the likelihood of straight-motion filter is smaller than that of the turn-prediction filter, the turn-prediction filter becomes dominant. In practice, the real target trajectory can be approximated by piecewise segments which may be turns and straight lines. With the presence of measurement noises, the hybrid filter will maintain good performance when the trajectory goes from straight to turn and inversely.

Simulations and analysis

In this section, we present the simulation results to show the performance improvements of the Hough-transform-based turn-prediction tracker over the straight-motion Kalman tracker and the existing circular-prediction based tracker developed by Tenne [34]. The scenario considered in this section and presented in Figure 5, is a circular manoeuvring target trajectory within an x-y Cartesian plane and a sampling time of 5s.

All measurements are considered to be reported by the same sensor, which is located at the origin of the Cartesian system. The target is moving with a variable velocity growing from 300 m/s to 800 m/s and variable turn gravity growing from 2g to 4g. The measurement errors are considered zero mean white noise with standard deviation of 100 m and the system noise is zero mean with ${\sigma }_a$=1.5 m/s² as standard deviations on both axes X and Y. The initial estimation error covariance matrix, the system noise covariance matrix, and the measurement noise covariance matrix were initialized as follows:

$P_{0/0}=\left[{\sigma }_x^2{\sigma }_x^2/T& 0& 0& {\sigma }_x^2/T& 2{\sigma }_x^2/T^2& 0& 0\\ 0& 0& {\sigma }_y^2& {\sigma }_y^2/T\\ 0& 0& {\sigma }_y^2/T& 2{\sigma }_y^2/T^2\right]$,

$Q_k=\left[\begin{array}{c}1/2T^2\\ T\\ 0\\ 0& 0\\ 0\\ 1/2T^2\\ T\end{array}\right]{\sigma }_a^2$, $R_k=\left[{\sigma }_x^{2}0& 0& {\sigma }_y^2\right]$

The estimation error-weighting matrix for the ${\gamma H}_{\infty }$filter is initialized using the constraint given by (37). The performance evaluations of the proposed algorithms were made on the basis of a Monte Carlo simulation of 100 runs and the evaluation of the target position and velocity root mean square errors (RMSE) as:

where $x^i\left(k\right)$, $y^i\left(k\right)$ and ${\widehat{x}}^i\left(k\right)$,${\widehat{y}}^i\left(k\right)$ denote the true and estimated position (velocity) coordinates of the target at the k^th scan in the i^th simulation run and N is the total number of runs. Performance comparison of the presented algorithms is achieved by evaluating the RMSE and carrying out the following statistical test: Let $\Delta \left(k\right)$ be the average RMSE difference between two filters over the target life:

Then the statistical test is defined as follows:

Where $\overline{\Delta }\left(k\right)$ is the mean of $\Delta \left(k\right)$ and ${\sigma }_{\Delta }\left(k\right)$ is its standard deviation. If $\delta \left(k\right)$ exceeds a certain threshold ${\delta }_0$then we conclude that filter 2 performs trajectory estimation better than filter 1.

First, we consider the stand-alone Hough-transform-based turn angle prediction using Kalman filter for estimating the turn angle, and the straight-motion Kalman filter. The evaluation of RMSE of both position and velocity estimation (Figures 6 and 7) has demonstrated better performance of the proposed filter than the straight-motion Kalman filter, especially for high turn gravity. The straight-motion Kalman filter is unstable, as the corresponding position estimation RMSE increases and decreases periodically showing the difficulty of tracking strong curvature manoeuvres, while the proposed turn-angle-prediction filter shows a stable behaviour since its corresponding RMSE does not change for both position and velocity.

Tracking performance comparison results of the Hough-transform-based turn prediction method with the existing Tenne’s circular-prediction method are presented in Figures 8, 9, and 10. By using the Kalman filter to estimate the turn angle, the statistics test reveals that the Hough-transform-based turn-prediction filter achieves better turn-angle estimation effectiveness compared to existing Tenne’s circular-prediction method (0.08 mean value), although the angle estimate RMSE for the existing method is lower than the proposed Hough-transform-based method (Figures 8 and 9). In addition, the Hough-transform-based turn angle is better estimated with ${\gamma H}_{\infty }$filter than the Kalman filter as presented in Figure 9.

Figures 11 and 12 show the RMSE of position and velocity estimation comparison between Kalman and ${\gamma H}_{\infty }$filters based turn-angle estimation. For the Tenne’s circular-prediction method [34], the position RMSE is highly fluctuating, and the velocity RMSE grows significantly when the turn gravity increases while the proposed Hough transform-based turn-prediction tracker tends to smooth the trajectory position and velocity estimation, especially for the velocity, when the turn gravity grows too high. In the case of the Hough-transform-based turn-angle-prediction approach, the tracking is better performed if the turn angle is estimated by the ${\gamma H}_{\infty }$filter as the corresponding position RMSE is smaller, comparatively to Kalman-filter-based turn-angle estimation case.

Figure 13 and Figure 14 show the performance comparison results of the turn-angle-detector-based scheme and the hybrid scheme. Both schemes combine straight motion Kalman filter and the proposed Hough-transform-based turn-prediction filter with the turn angle estimated by ${\gamma H}_{\infty }$filter. In the case of the turn-detector-based scheme, as expected, the position and velocity estimation RMSE are similar to the ones of turn-prediction-based filter when the turn gravity goes high, and follow the RMSE of straight motion Kalman filter inversely.

In the case of the hybrid scheme, the simulation results show that the tracking performances are considerably improved especially during the high-turn manoeuvring motion. The RMSE of position and velocity estimation are considerably reduced. Also, the hybrid-scheme-based algorithm provides better stability of target tracking than the turn-detector-based algorithm. However, the two schemes offer good performance compared to the stand-alone straight-motion Kalman filter.

Matlab simulations have been carried out to evaluate and compare the execution time of the proposed turn-angle-prediction approach and the existing circular-prediction approach [34]. The results have demonstrated that, under the same simulation conditions, the running time (simulation execution time) of the proposed turn-angle-prediction approach has been improved about 70% compared to that of the existing Tenne’s circular-prediction approach.

Conclusions

To obtain better manoeuvre-following capability when the manoeuvre takes the form of a turn, an approach of turn prediction based on the Hough transform is proposed in this paper. The turn angle is estimated using a variable γH_ filter. The γH_ filter shows better performances over the Kalman filter. A hybrid implementation scheme is also proposed to combine the proposed method with a straight-motion linear filter. Compared to a turn-angle-detection-based scheme and a stand-alone linear-filter-based scheme, the hybrid combination has led to an improved performance with a stable estimation of the target trajectory. Simulation results has proved the capability of the proposed turn prediction based on the Hough transform to follow the turn manoeuvring trajectories with a good stability behaviour and reduced errors comparatively to the straight-motion Kalman filter and the existing circular-prediction-based filter. The running time of the proposed approach is very much reduced comparatively to the existing circular-prediction approach.

References

Authors

Mohamed Sadek Kemouche received the Engineer Diploma degree in electrical engineering/automation from Military Polytechnics School, Algiers, Algeria in 1990, and the ME and MSc in signal processing from the USTHB University, Algiers, Algeria in 1994 and 2001. From 1990 to 1992 he worked as a radar engineer, and from 1994 to1998 as a research associate in radar applications. From 2001 to 2006 he worked as a researcher at the Research and Development Center, Algiers, Algeria. He is currently working towards the PhD degree in Electronics Engineering at the Military Polytechnics School, Algiers, Algeria. His research interests include multi-target tracking, signal processing, and sensor networks.

Dr Nabil Aouf is a Lecturer at the Department of Informatics and Sensors, Cranfield University/Defence Academy, UK. His areas of interest are: aerospace and defence systems, information fusion and robust filtering, guidance, navigation, tracking and control, sensor networks, autonomy of systems and decision-making, security and surveillance systems. He is associate editor of the International Journal of Computational Intelligence in Control and has more than 40 publications of high calibre in his domains of interest.