# A Filtering Algorithm for Maneuvering Target Tracking Based on Smoothing Spline Fitting

Authors: Yunfeng Liu; Jidong Suo; Hamid Reza Karimi; Xiaoming Liu
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Maneuvering target tracking is a challenge. Target’s sudden speed or direction changing would make the common filtering tracker divergence. To improve the accuracy of maneuvering target tracking, we propose a tracking algorithm based on spline fitting. Curve fitting, based on historical point trace, reflects the mobility information. The innovation of this paper is assuming that there is no dynamic motion model, and prediction is only based on the curve fitting over the measured data. Monte Carlo simulation results show that, when sea targets are maneuvering, the proposed algorithm has better accuracy than the conventional Kalman filter algorithm and the interactive multiple model filtering algorithm, maintaining simple structure and small amount of storage.


---

## Body

## 1. Introduction

In modern society, radar plays an increasingly important role, where the sea target detection and tracking is a very important aspect and has great practical value. Low-speed objects such as sea ice and others bring great danger to the ship sailing on the sea, and the performance of sea target detection directly affects the safety of navigation. Tracking is an important part of radar system. Especially the maneuvering target tracking is more complex in clutter environment.In conventional target tracking, the most common method is the standard Kalman filter algorithm [1]. When the target state and observation equations are linear equations and the observation noise is Gaussian white noise, the Kalman filter algorithm is the optimal algorithm in the sense of minimum variance. When the target maneuver occurs, Kalman filtering accuracy will be reduced or even diverged due to the model mismatch and noise characteristics that cannot be known exactly. In view of the limitations of the Kalman filter algorithm, the multimodel filtering algorithm [2–8] and the adaptive Kalman filter algorithm [9–12] emerged. The multiple-model algorithm is the algorithm using the weighted sum of multiple models to approximate the actual motion model of the target. Subsequently, the interacting multiple model algorithm emerged [5, 6]. It is the fusion result of multimodel by updating probability of models. It has better performance than multimodel filtering algorithm.During maneuvering, target maneuver has still regularity which is reflected in the measured values and cannot be properly represented by the Kalman filter algorithm. Therefore, this paper proposes a filtering algorithm based on the smoothing spline fitting. The proposed algorithm fits through the measured values​
​reflecting the movement regularity. The difference between the proposed algorithm and the standard Kalman filter algorithm is that the latter calculates estimations through the sum of the predicted values and the measured values ​
​weighted and the former algorithm fits values individually ​
​from the measured values to ​
​determine the estimations.The paper is organized as follows. In Section2, Kalman filter algorithm is proposed. In Sections 3 and 4, interacting multiple model algorithm and spline fitting filtering algorithm are introduced, respectively. In Section 5, simulation results are given to illustrate the effectiveness of the proposed algorithms. Finally, concluding remarks are provided in Section 6.


## 2. Kalman Filtering (KF) Algorithm

The Kalman filtering (KF) flowchart is shown in Figure1.Figure 1
The Kalman filter algorithm flowchart.As can be seen from Figure1, the weighted predicted values and the weighted measured values ​
​determine the estimate value of the KF; the predicted value is generated from the motion model. However, a single model cannot meet all the maneuvering of the target; the covariance plays a link between the model and the weighting. When filtering, the weighting of the measured value tends to be a constant value and contribution to the estimate becomes smaller. So the KF algorithm cannot escape from the shackles of a single model.Application of the KF algorithm to real-time problem depends on a priori knowledge of the mean square error of the state and the observation process [13]. Moreover the optimal estimation of covariance matrix for the state and observation processes does not exist. In order to solve this problem, some research proposed suboptimal solutions, they estimate one or more parameters of mean variance matrix of the state and the observe process [14–16], or estimate the gain adaptively [17, 18]. Also, the authors [19, 20] proposed algorithms with the divergence criterion and forgetting factor preventing filter divergence, but the divergence criterion cannot reflect filter divergence exactly.The KF algorithm uses a single model which cannot meet every maneuver, only suitable for the steady situation. When the model does not suit the motion model, the gain coefficient or the covariance will be adjusted to remedy the motion model. These methods do not get rid of the computing framework of the Kalman system, nothing more than a feedback loop [21].


## 3. Interacting Multiple Model (IMM) Algorithm

The IMM algorithm has become a standard tool for maneuvering target tracking [5, 6, 22]. It has a recursive algorithm structure, which using finite state model represents the entire system to try to solve the problem of a single target motion model mismatch. The IMM approximates nonlinear systems by finite linear model and estimates the system state by the sum of weighted estimation of models. The IMM requires models to represent the entire state of the system, usually this is difficult to achieve.While maneuvering occurs, the accuracy of the IMM is superior to the KF. However, the shortcomings of the IMM are more models more calculation, the competition between models. All of these affect performance of the IMM. The IMM has multiple models to remedy the motion model when the model does not suit the motion model. The similarity of the standard Kalman filter algorithm and the IMM algorithm is using motion model to predict movement position; filtering results are decided by the weighted values​
​of predicted and measured. When maneuvering, the measured values ​
​reflect better regularity of motion, but the weight of the measured values does not increase more in both algorithms.The IMM flowchart is shown in Figure2.Figure 2
The IMM algorithm flowchart.WhereX
^
(
k
∣
k
) represents the output estimate of time k, Z
(
k
) represents the measurement data of time k, Λ
k
j represents the possibility vector of model j, u
(
k
) represents the model probability vector, p
(
i
,
j
) represents transition probability for model i to model j, X
^
(
k
∣
k
)
j represents state estimate of model j at time k, and X
^
(
k
-
1
∣
k
-
1
)
o
j is the result of the interaction of X
^
(
k
-
1
|
k
-
1
)
j
(
j
=
1,2
,
…
,
N
).As can be seen from Figure2, IMM algorithm has four steps.Step 1 (input interact).
At timek
-
1, set state estimation and covariance matrix value are X
^
(
k
-
1
|
k
-
1
)
j and P
j
(
k
-
1
k
-
1
),    j
=
1,2
,
…
,
N.
After the interaction, at timek, the input of filter is
(1)
X
^
(
k
-
1
∣
k
-
1
)
o
j
=
∑
i
=
1
N
X
^
(
k
-
1
∣
k
-
1
)
i
u
(
k
-
1
∣
k
-
1
)
(
i
∣
j
)
,
p
o
j
(
k
-
1
∣
k
-
1
)
=
∑
i
=
1
N
{
[
X
^
(
k
-
1
∣
k
-
1
)
i
-
X
^
(
k
-
1
∣
k
-
1
)
o
j
]
T
p
i
(
k
-
1
∣
k
-
1
)
+
[
X
^
(
k
-
1
∣
k
-
1
)
i
-
X
^
(
k
-
1
∣
k
-
1
)
o
j
]
×
[
X
^
(
k
-
1
∣
k
-
1
)
i
-
X
^
(
k
-
1
∣
k
-
1
)
o
j
]
T
}
u
(
k
-
1
|
k
-
1
)
(
i
∣
j
)
,
where
(2)
u
k
-
1
∣
k
-
1
(
i
∣
j
)
=
P
(
i
,
j
)
u
k
-
1
(
i
)
C
j
¯
,
C
j
¯
=
∑
i
=
1
N
p
(
i
,
j
)
u
k
-
1
(
i
)
,Step 2 (filtering predict).
The first step result is the model input at timek. We get the output from KF filter as follows:(3)
X
^
(
k
∣
k
)
j
,
p
j
(
k
∣
k
)
.Step 3 (probability update).
Update probability of modeln as follows:
(4)
u
k
(
j
)
=
Λ
k
j
C
j
¯
C
,
where
(5)
C
=
∑
i
=
1
N
Λ
k
i
C
i
¯
.Step 4 (data fusion).
The interact outputs, at timek, will be obtained, respectively, after getting output and probability of every model:
(6)
X
^
(
k
∣
k
)
=
∑
i
=
1
N
X
^
i
(
k
∣
k
)
u
k
(
i
)
,
P
(
k
∣
k
)
=
∑
i
=
1
N
u
k
(
i
)
(
(
X
^
i
(
k
∣
k
)
-
X
^
(
k
∣
k
)
)
T
P
i
(
k
∣
k
)
+
(
X
^
i
(
k
∣
k
)
-
X
^
(
k
∣
k
)
)
×
(
X
^
i
(
k
∣
k
)
-
X
^
(
k
∣
k
)
)
T
)
,
where P
(
k
∣
k
) is the state covariance.
Then we perform the first interactive multiple model algorithm recursive process.


## 4. Spline Fitting Filtering (SFF) Algorithm

The KF algorithm requires the system model to be linear, which greatly limits the scope of application of the KF algorithm. The IMM increases the number of model to close the motion model. And predicted and measured​
​weighted values decide the estimate values in both algorithms. When the target maneuver occurs, the predicted value cannot immediately react because both algorithms did not accurately and rapidly adjust the weight of the measured values. However, the measured values can give faster and more sensitive response. To improve on this, the paper proposes, in the filtering process, the measured value that contains the true information of the motion. The measured value reflects the regularity of target maneuvering more promptly than the predicted value, and the regularity reflects from a certain smoothing of the curve. Therefore, the estimated value of the filter should be closely linked to the measured value. When sea targets maneuver, they still have regularity of motion despite the measurement errors and systematic errors. The cubic spline is used to approximate the mathematical model of targets maneuvering, and the smoothing spline function reflects the regularity of maneuvering. Therefore, the novel point of SFF is the using of spline function to reflect sea targets maneuvering, abandonment of the motion model. The advantage of SFF can be seen in Figures 4 and 5. The SFF is closer to the true value than the KF and IMM. When the target maneuver occurs, the error of the SFF is the smallest one in three algorithms.Assumed measured point(
x
(
j
)
,
y
(
j
)
)
,
j
=
1,2
,
…, here f is a cubic spline function. The problem is to find a function f that minimizes
(7)
ρ
∑
j
=
1
n
|
y
(
j
)
-
f
(
x
j
)
|
2
+
(
1
-
ρ
)
∫
|
d
2
f
(
x
)
d
x
2
|
2
d
x
,
where x
(
j
), y
(
j
) represent the horizontal and vertical coordinates of the measured value, respectively, n represents the number of nodes, d
2
f
(
x
)
/
d
x
2 represents the second derivative of f
(
x
), ρ is a smoothing parameter, and ρ
∈
[
0,1
]. When ρ
=
0, f
(
·
) is a spline function to fit the data in the least squares sense; when ρ
=
1, f is the cubic spline interpolation. Formula (7) is a least-squares problem, where the first term quantifies the error between the measured data points y
(
j
) and the model f
(
x
j
). The second term imposes a smoothness constraint on the solution. In practice, we set ρ
=
0.8 for better reflecting the regularity of maneuvering by smoothing spline curve.The SFF algorithm is as follows: suppose the measured value isz
(
n
)
=
(
x
(
n
)
,
y
(
n
)
).First, mean the measured valuesz
(
n
-
1
)
=
(
z
(
n
-
2
)
+
z
(
n
)
)
/
2
(
n
≥
3
). Second, the filtering estimate results are fitted by the spline function from n filtered measured values. So the cycle continues. Taking into account the experimental results and the complexity of the algorithm, three points are used for the spline fitting.The SFF flowchart is shown in Figure3.Figure 3
The SFF algorithm flowchart.Figure 4
Point track.(a) Average point track. (b) Mean error. (c) Root-mean-square error.
(a)
(b)
(c)


## 5. Simulation Results

The simulation environment is Intel CPU 2.53 GHz, 1 GB Memory, and MATLAB R2009b. Assume sea target departures at coordinates (8000 m and 8000 m):(1)
0–49 s, the target uniform linear motion (30 m/s atx-axis direction, 40 m/s at y axis direction);
(2)
50–90 s, the target turning movement at the turn rate 3°/s, 50 m/s speed;
(3)
91–119 s, the target uniform linear motion at 50 m/s speed;
(4)
120–160 s, the target turning movement at the turn rate 3°/s, 50 m/s speed;
(5)
161–210 s, the target uniform linear motion at 50 m/s speed.The results of three filtering algorithms are shown in Figure4. And the results of Monte Carlo of 100 times are depicted in Figures 5(a), 5(b), and 5(c).As can be seen from Figure4, the KF motion model meets the target motion model during the uniform linear motion and filtering results converge; as other periods, the filtering results of the KF will increase errors or divergence. The reason is the weight of the measured values is much smaller that cannot influence the filtering results. The filtering results determined by the ​
​weighted sum of the prediction values and the measured values. As the target maneuvers, the algorithm model mismatches the uniform linear motion model, and the predictive value is still the main content of the filtering value. It cannot keep up with the change of motion, which leads to increasing error and even divergence. For the same set of data, the IMM has three corresponding models.The filtering result of the IMM is better than the KF during the turning movement, but the filter effect of the IMM is reduced or even diverged as the IMM model mismatch. The SFF filtering effects is the same with the IMM. When the target maneuvers, the SFF is superior to the former algorithms.As can be seen from Figure5(a), the filtering trajectory of the SFF is closer to the true value than the KF and IMM; when the target maneuver occurs, the average error of the SFF is smaller than that of the KF and IMM as can be seen from Figure 5(b); from Figure 5(c), there is a large fluctuation of standard deviation for the KF and IMM as target motion, while the standard deviation of the SFF has small change.When selecting the type of steering ratio, the conclusion is consistent and uniform.In the three algorithms, the KF is optimal in uniform linear motion when its model meets the motion model. On the other movement, the accuracy of the SFF is better than the accuracy of the KF and IMM because the impact of the measured value of the SFF​
​is more prominent in filtering and measurements reflect the movement regularity in time.


## 6. Conclusion

The paper proposed a target tracking filtering algorithm based on spline function fitting the measured value. For the same set of data, the estimation error of the proposed algorithm compares with the estimation error of KF algorithm and IMM algorithm. Monte Carlo results clearly show that the SFF has higher estimation accuracy. Particularly it has obvious advantages to the standard Kalman filter algorithm and maintains a simple structure and small amount of storage.



---

*Source: 127643-2014-02-06.xml*