Signal Processing 83 (2003) 169180
Alphabeta-tracking index () tracking %lter
Jae-Chern Yooa ;, Young-Soo Kimb
aPOSTECH Information Research Lab., Pohang University of Science and Technology, San 31, Hyojadong, Namgu, Pohang,Kyungpook 790-784, South Korea
bElectrical and Computer Engineering Division, Pohang University of Science and Technology, San 31, Hyojadong, Namgu, Pohang,Kyungpook 790-784, South Korea
Received 12 November 2001
An alphabeta-tracking index () tracking %lter for the single target tracking is proposed for maneuver-followingcapability. The tracking %lter incorporates an estimation technique of the tracking index in the gain approximation algorithm(IEEE Trans. Aerospace Electron. Systems AES-20 (March 1984) 174) and uses a gate-growing method to measure thedegree of the targets maneuver. It involves a changeover algorithm which switches over to the conventional %lter whenthe tracking target reaches stationarity, and switches over to the gain approximation algorithm when the tracking target beginsto maneuver. The data association algorithm based on comparing matching score makes the gate-growing process reliable inclutter environment and at the same time has the ability of identifying the target, not requiring a separate step. Simulationresults show that it is more robust in terms of its ability to minimize the prediction error irrespective of whether the targetis in maneuver or not, and whether the target trajectory is linear or not. The proposed %lter can realize the accuracyof the Kalman %lter with an algorithm as simple as the well-known %lter.? 2002 Elsevier Science B.V. All rights reserved.
Keywords: Target tracking; Kalman %lter; Data association; Radar signals
In the recent years, much interest has centeredaround the study and application of automatic dataprocessing in track while scan (TWS) radar systemsused in air and sea surveillance.This has been so because modern surveillance sys-
tems using radar as sensors require location, velocityand identi%cation of each target of interest with an ac-curacy and reliability greater than that available froma single-look radar report.
Corresponding author. Tel.: +82-54-279-5624; fax:+82-54-279-5699.
E-mail addresses: firstname.lastname@example.org (J.-C. Yoo),email@example.com (Y.-S. Kim).
The Kalman %lter or %lter is used for the sin-gle target tracking. The Kalman %lter performs almostperfect tracking in cases where the target model %tsthe real target trajectory, and when the statistical char-acteristics of the target maneuver and measurementnoise such as mean and variance are known . Inpractice, it is diEcult to know the statistical charac-teristics of the target in advance.To overcome the problems associated with the guess
of the statistical characteristics, adaptive algorithms,choosing one of the %lters, each tuned for a particularmaneuver, have been considered where the Kalman%lter gains are changed according to the target maneu-ver .However, the Kalman %lter requires a growing
memory and computational requirements.
0165-1684/03/$ - see front matter ? 2002 Elsevier Science B.V. All rights reserved.PII: S0165 -1684(02)00388 -2
170 J.-C. Yoo, Y.-S. Kim / Signal Processing 83 (2003) 169180
2r ; 2 the variances of measurement errors on
the polar coordinatesr; tracking index on the polar coordinatesk the number of radar scangij range pro%le corresponding to a track-
ing track (the suEces i and j representthe class and the aspect angles of thetrack, respectively)
xs(k) smoothed positionVs(k) smoothed velocityVp(k) predicted velocityxp(k) predicted positionxm(k) measured positionT scan period
The %lter is a simpli%ed version of the Kalman%lter, so that it can realize real-time tracking. The tracking process with proper parameter providesoptimal solution of the Kalman %ltering process forthe stationary target tracking problem.However, when the target maneuvers, the quality
of the position and velocity estimates provided by the %lter can be degraded signi%cantly, and the tar-get may be lost since the %lter uses only the linearprediction .To cope with these problems, many methods have
been developed, and they are usually based on a non-linear prediction such as the tracking %lter com-bined with maneuver-driven circular prediction andthe generalized Hough transform for detecting ellip-soidal curves [9,10].These schemes consider the turn direction of a target
and could show the maneuver-following capability.However, they are calculated on the assumption thatthe target moves with a constant angular or ellipticalvelocity on the curves.Kalata realized the accuracy of the Kalman %lter
with a gain approximation algorithm as simple as the %lter when an optimal tracking index parameteris given [7,11]. However, the tracking index is noteasy to be known a priori when a target maneuversirregularly.
In this paper, the tracking %lter using thetracking index (), named tracking %lter, isproposed.This method incorporates an estimation technique
of the tracking index in the gain approximation algo-rithm. The estimation of the tracking index is basedon analytical results of the relationships between thevalidated gate size and tracking index .The tracking index is obtained by the size of the
validated gate representing the degree of the targetsmaneuver. When a paring is not made during data as-sociation, the association is continued with growingthe size of gate till a paring is made. From the %nalvalidated gate size, the tracking index and the corre-sponding optimal alphabeta gain are obtained.The data association algorithm by the gate-growing
process is based on the matching score of range pro%leand uses the range pro%les stored in the database asthe reference for data association.Using Kalman %lter and the conventional %l-
ter as benchmarks, the performance of the proposed tracker is evaluated. Simulation results showthat it is more robust in terms of its ability to mini-mize the prediction error irrespective of whether thetarget is in maneuver or not, and whether the targettrajectory is linear or not.The proposed %lter can realize the accuracy
of the Kalman %lter with an algorithm as simple as thewell-known %lter. Also, the target can be identi-%ed as a by-product of the tracking process, not re-quiring a separate step for target identi%cation.
2. Validated gate and the tracking index
The validated gate size is given by 
Gr = r(1 +
2(2k + 1)k(k + 1)
G = (1 +
2(2k + 1)k(k + 1)
where 2r ; 2 are the variances of measurement errors
on the polar coordinates, r; the tracking indexin polar coordinates, the parameter that de%nesthe validation region, is chi-square distributed withnumber of degrees of freedom equal to the dimension
J.-C. Yoo, Y.-S. Kim / Signal Processing 83 (2003) 169180 171
Fig. 1. Data association using a gate-growing process. The growing direction is decided by the predicted velocity, Vp =V 2px + V 2py .
of the measurement and probability which the truetarget is falling in the gate , and k the number ofradar scans.It can be noted that the gate size reduces as the num-
ber of radar scans increases (gate-decreasing process).The tracking index, on the polar coordinates, corre-sponding to a given gate size, can be easily obtainedfrom Eq. (1):
r = 2
)2 1 2(2k + 1)
k(k + 1)
)2 1 2(2k + 1)
k(k + 1):
Mis-track will occur when the measured value is farfrom the predicted value. In this case, a larger vali-dated gate is required to associate with the track.Whena paring is not made during association, the associa-tion is continued with a growing gate until a paringconforming to criterion (3) is made (see Fig. 1):
C(gij; m)THmc; (3)
where C(gij; m) is the normalized correlation coeE-cient between gij and m, gij the range pro%le corre-sponding to a tracking track, and it is assumed that thetrack is initially identi%ed through comparing it withthe range pro%les stored in the database (the suEcesi and j represent the class and the aspect angles of
the track, respectively), and m the range pro%le of anew measurement introduced into the validated regionduring the gate-growing process.The THmc is a constant that controls the false-alarm
rate, and there is a trade-oK between the false-alarmrate and the missing target rate.However, the number of false alarms may grow
with the validated gate. In this case, the track-ing %lter should be coupled with the existing data as-sociation algorithms for multi-target tracking (MTT)such as global nearest neighbor (GNN) , joint prob-abilistic data association (JPDA)  and multiple hy-pothesis tracking (MHT) methods .The allowable maximum gate size depends on the
targets attributes such as the maximum speed andturn-rate. From the %nal gate size, it is possible todetermine not only the degree of the targets maneuver(tracking index: ) using Eq. (2), but also the optimalalphabeta gain, as will be shown later.
3. Conventional -- tracking lter and gainapproximation algorithm
The conventional tracking process is givenby 
xp(0) = xm(0); Vp(1) = xm(0) xm(1)T ;
172 J.-C. Yoo, Y.-S. Kim / Signal Processing 83 (2003) 169180
(0) = 1; (0) = 1:
xs(k) = xp(k) + [xm(k) xp(k)];Vs(k) = Vp(k 1) + =T [xm(k) xp(k)];xp(k + 1) = xs(k) + Vs(k)T;
Vp(k + 1) = Vs(k);
where xs(k) is the smoothed position, Vs(k) thesmoothed velocity, Vp(k) the predicted velocity, xp(k)the predicted position, xm(k) the measured position,T the scan period, the 2(2k 1)=k(k + 1), and the 6=k(k + 1)T .Based on the %rst-order time constants, the gain
approximation algorithm in recursive form is givenby [7,11]Initial condition:
xp(0) = xm(0); Vp(1) = xm(0) xm(1)T ;
(0) = 1; (0) = 1:
(k + 1) = (k) + G( (k));(k + 1) = (k) + G( (k));
where ; are the optimal steady-state param-eters, and
G = 1 exp(1=k);G = 1 exp(1=k);
(1 ) ;(6)
=2 + 8 (+ 4)2 + 8
=2 + 4 2 + 8
4:20 4:20 for 0:506 1:0;5:90 7:56 for 0:184 0:506;7:14 14:29 for 0 0:184;
5:397 5:397 for 0:931 1:0;2:047 1:797 for 0:270 0:931;1:672 0:407 for 0 0:270:
If an optimal tracking index parameter is given, thisalgorithm realizes the accuracy of the Kalman %lterwith an algorithm as simple as the general %lterduring initiation process .
4. ---- tracking lter algorithm
The proposed tracking %lter is based on therelationship between the validated gate size and thetracking index, on the gain approximation algorithmgiven in Section 3, and on a changeover algorithm.Fig. 2 summarizes the Mowchart of the track-
ing %lter algorithm.In order to diKerentiate the gain by the gain ap-
proximation algorithm from that by the conventional tracking %lter, they are, respectively, denoted asG(G) and C(C):
G(k + 1) = G(k) + G( G(k));G(k + 1) = G(k) + G( G(k));
C = 2(2k 1)=k(k + 1);C = 6=k(k + 1)T:
The mis-track will occur when target is maneuvering.To detect the degree of the targets maneuver, theassociation is continued with a growing gate until aparing is made and then a maneuver is declared.Next, by using the %nal validated gate size, deter-
mine the tracking index from Eq. (2), the optimal; parameters from Eq. (7), and the %rst-order gaintime constant (k; k) from Eq. (8).Finally, k, k, and with k = 1 are applied to
Eq. (5). After this, the tracking information based onthe gain approximation algorithm is recursively up-dated to produce re%ned estimates of the position andthe velocity.
4.1. Changeover algorithm
When a maneuver is detected, the conventional tracking algorithm (Eq. (4)) together with thegain approximation algorithm is simultaneously ini-tialized with k=1. And from this time, the process ofcomparing G with C continues. When the diKerencebetween G and C is greater than a threshold (GAP)which would mean that the tracking target reaches
J.-C. Yoo, Y.-S. Kim / Signal Processing 83 (2003) 169180 173
Fig. 2. Flowchart of the tracking %lter algorithm.
174 J.-C. Yoo, Y.-S. Kim / Signal Processing 83 (2003) 169180
Fig. 3. Gain versus the number of radar scans for 2 = 0:01, = 0:001.
stationarity, the change from the gain approximationalgorithm to the conventional tracking algorithm ismade.Note that the changeover prevents the tracking gains
and gate size from decreasing slowly in spite of reach-ing straight line trajectory after maneuvering. Fig. 3shows the gain versus the number of radar scans. Evenwhen the target goes into a stationary zone, the gainsG and G very sluggishly decrease while the gainsC and C rapidly converge to zero.Considering that the tracking process is the
optimal solution of the Kalman %ltering process forthe stationary target tracking problem; it is intuitiveto switch over to the conventional %lter from thegain approximation algorithm when the target reachesstationarity.The gain approximation is well suited during the
initial process for a given optimal tracking index pa-rameter, but even if the targets reaches stationarity,the gain remains large so that there is a large gate size.Therefore, it is important to make the changeover
so as to reduce the gate size when the targets reachstationarity.Fig. 4 shows the values of GAP (=G C) and
GAP (G C) as functions of tracking index for= 0:001. The starting point of the stationary zone is
G(k + 1) G(k)6 or
G(k + 1) G(k)6 ;(11)
where is a small number. The GAP (or GAP) canbe used to detect whether the target reaches station-arity or not. For example, when 2 = 0:01 the op-timal changeover point is approximately 0.21. UsingEqs. (9), (10) and assuming = 0:001 and T = 1, therelationship between tracking index and the optimalchangeover point can be approximately obtained bythe curve %tting as follows:
GAP(x) = 0:0005x5 0:0057x4 0:035x3
0:0982x2 0:0093x + 0:3788;GAP(x) = 0:0008x5 0:0065x4 0:0164x3
+ 0:0462x2 + 0:3159x + 0:4487;
where x = log10 2. Note also that the changeover is
not necessary any more when the value of log10(2)
is less than about 5.
J.-C. Yoo, Y.-S. Kim / Signal Processing 83 (2003) 169180 175
Fig. 4. GAP (GAP) versus tracking index for = 0:001.
5. Simulation results
In order to examine the eKectiveness of proposed tracking %lter for the single target tracking,computer simulation was performed. Some assump-tions used in this simulation are as follows:(i) Target dynamic model and measurement model.It was assumed that the target motion is modelled as[position : x(k + 1)
velocity : v(k + 1)
and the corresponding measurement model for posi-tion is given by
z(k) = x(k) + n(k); (14)
where T is the scan period, w(k) the unknown maneu-verability of target, and n(k) the radar measurementnoise. The w(k) and n(k) are zero-mean white Gaus-sian distributed.
(ii) Simulation parametersA tracking system is considered to measure a
target position every T = 1 s with errors of 20 mstandard deviation in range, and 30 mrad in azimuthdirection.It is also assum...