# Asymmetrical Gating with Application on Maneuvering Target Tracking

Authors: Farzad Hashemzadeh
Journal: Applied Computational Intelligence and Soft Computing
 (2012)

---

## Abstract

A new asymmetrical gate with application in target tracking is proposed. Proposed gate has asymmetric shape that has large probability of target detection in the gate and has more advantages compared with elliptical gate. The gate is defined as the region in which the tracked target is expected to exist and just observation vectors in the gate are used as target detection. An analytical method to compute optimal size of gate is proposed and recursive estimation of asymmetric parameters of gate are studied. Comparison between proposed gate and conventional elliptical gate showed the efficiency of the proposed method in maneuvering target tracking applications and simulation results showed the proficiency of the proposed method.


---

## Body

## 1. Introduction

Tracking is meant to be the estimation of the true values of specifications of target motion, such as the position and velocity, based on then-dimensional observational vector by the sensors [1–3]. One-dimensional observation vectors are obtained in a direction-finding setup observing just the azimuth angle [4]. Two-dimensional observation vectors are obtained in optical sensors observing the azimuth angle and elevation angle, or in radars observing the range and azimuth angle. Historically, PDA (Probabilistic Data Association) [5], JPDA (Joint PDA) [6], and MHT (Multiple Hypothesis Tracking) [7–9] have drawn attention as target tracking methods in an environment in which false signals from objects other than the target such as clutter exist [10, 11]. In target tracking in such an environment, just the region is considered for each target in which the target is expected to exist at the next sampling time [12]. This region is called the gate. The observation data within the gate are used for tracking. Various gate shapes are conceivable, such as a rectangle, circle, and ellipse. However, it is not known which shape of gate is optimum. If the gate is enlarged, many observation vectors from clutter or objects other than the target fall within the gate, resulting in some difficulties in target tracking. On the other hand, if the gate is made smaller, there is a danger that the observation data from the target to be tracked may not fall within the gate. It is more desirable that the position of the observation vector detected from the target be closer to the center of the gate compared with location of the false signals in the gate [13]. A method of determining the in-gate probability has been proposed in [10].In this paper, asymmetrical gaussian distribution is introduced. Cross-surface of asymmetrical gaussian distribution is considered as asymmetrical gate. Parameters of asymmetrical Gaussian distribution should be estimated to estimate parameters of asymmetrical gate. Kalman filter as a standard method to estimate parameters of symmetrical distribution is used to estimate parameters of asymmetrical distribution. Standard deviation of asymmetrical distribution in opposite to the movement direction is estimated using estimation of acceleration in movement direction in centric coordinate system. In this paper, analytical preference of asymmetrical gate compared with the elliptical gate is studied. In this analytical study, volumes of gates are considered as a comparison criteria subjected to the assumption that in-gate probability of distribution for both asymmetric and elliptical gates are equal.In the following of this paper, Section2 introduces asymmetrical gaussian distribution. Section 3 is about estimation of parameters of gate. In Section 4, analytical comparison between asymmetrical gate and elliptical gate is considered. In Section 5, optimal size of gate is calculated and in Section 6, preference of this new method is shown by simulation result.


## 2. Asymmetric Gaussian Gate

Maneuvering target that has nonzero acceleration in direction of movement could be modeled with almost-constant-acceleration target motion model in which process and measurement noise on direction of movement have asymmetric distribution and process and measurement noises on orthogonal to the movement direction have gaussian distribution.In this paper, it is assumed that distribution of location of maneuvering target in the next time is asymmetric gaussian in centric coordinate system. Center of centric coordinate system is in the location of target and directions of axis of it are in the movement direction and orthogonal to the movement direction.One-dimensional asymmetric Gaussian distribution in direction of movement is illustrated as follows:(1)f(xt)={1kexp⁡⁡(-12(xt-m)2σx12)xt>m,1kexp⁡⁡(-12(xt-m)2σx22)xt<m,
where k is normalization factor and can be calculated as follow:(2)k=∫-∞mexp⁡(-12(xt-m)2σx12)+∫m+∞exp⁡(-12(xt-m)2σx22)=2πσx122+2πσx222=2π(σx1+σx22).In (2),  σx1 and  σx2  are standard deviation of distribution of xt in positive and negative directions, respectively, and m is median of distribution of xt.Considering (2) and (1), one-dimensional asymmetric gaussian distribution of xt can be achieved as follows:(3)f(xt)={12π((σx1+σx2)/2)exp⁡⁡(-12(xt-m)2σx12)xt>m,12π((σx1+σx2)/2)exp⁡⁡(-12(xt-m)2σx22)xt<m.Forxt>m,  f(xt) is same as typical Gaussian distribution with standard deviation σx1 and for xt<m, it is the same as typical Gaussian distribution with standard deviation σx2.Ifσx1=σx2, (3) is standard Gaussian distribution and if σx1≠σx2, (3) is asymmetrical Gaussian distribution. It means that distribution is not symmetrical around median m, and dampings of distribution are different around of the median.In Figure1, distribution of f(xt) with zero median and two different standard deviations is shown.Figure 1
Distribution off(xt) with zero mean and two variant variances.It is assumed that Probability Distribution Function (PDF) of target in orthogonal to the direction of movement is zero mean gaussian with standard deviation as follows:(4)f(yt)=12πσyexp⁡⁡(-12(yt)2σy2).In this paper,zt=[xtyt]T is defined in centric coordinate system, in which xt and yt are measured values of target in centric coordinate system.Probability distribution ofzt in centric coordinate system is illustrated as follows:(5)f(xt,yt)={1kexp⁡⁡(-12(zt-mz)Σ1-1(zt-mz)T)xt>m,1kexp⁡⁡(-12(zt-mz)Σ2-1(zt-mz)T)xt<m,
where(6)mz=[m0],Σ1=[σx1200σy2],Σ2=[σx2200σy2].In (5), k is normalization factor and can be calculated as(7)k=∫-∞m∫-∞+∞exp⁡(-12((x-m)2σx22+y2σy2))dydx+∫m+∞∫-∞+∞exp⁡(-12((x-m)2σx12+y2σy2))dydx=2πσx1σy2+2πσx2σy2=2πσy(σx1+σx22)=π|Σ11/2+Σ21/2|.Considering (5) and (7), probability distribution of f(xt,yt) in centric coordinate system can be achieved as follows:(8)f(xt,yt)={12πσy((σx1+σx2)/2)×exp⁡(-12(zt-mz)Σ1-1(zt-mz)T)xt>m,12πσy((σx1+σx2)/2)×exp⁡(-12(zt-mz)Σ2-1(zt-mz)T)xt<m.Probability distributions off(xt,yt) in (8) with surfaces of distribution are illustrated in Figure 2.(a) Probability distribution off(xt,yt) for m=7, σy=5, σx1=10, σx2=4, (b) probability distribution of f(xt,yt) for m=7, σy=5, σx1=4, σx2=10.
(a)(b)As it can be shown from Figures2(a) and 2(b), with variation of ratio of σx1 and σx2, it is easy to stretch distribution surface in movement direction or opposite of movement direction. Application of tuning of variances is that, for maneuvering targets that have positive or negative accelerations on direction of movement, it is possible to modify surface of distribution, optimally.If maneuvering target has positive acceleration in direction of movement, it is better to selectσx1>σx2 to stretch gate in positive direction of movement as Figure 2(a) and if maneuvering target has been negative acceleration in direction of movement, it is better to select σx1<σx2 to stretch gate in the negative direction of movement as Figure 2(b). Therefore, with appropriate choosing of σx1 and σx2, it is possible to stretch the gate in direction that probability of target detection inside of the gate increases, whereas volume of gate remains constant.


## 3. Gate’s Parameters Estimation

In this section, parameter estimation of target position distribution is considered. If process and measurement noise have Gaussian distribution, Kalman filter would be optimal recursive method to estimate parameters of distribution. Therefore, typical elliptical gate would be optimal tracking gate in such cases [14].In this paper, maneuvering target with positive or negative acceleration in movement direction is considered. Kalman filter as a standard recursively estimation method is used to recursively estimate of asymmetrical gate’s parameters.Let us assumed that parameters of asymmetrical gate on timet-1 are mt-1, σx1,t-1, σx2,t-1, σy,t-1, θt-1, where mt-1 is center of gate, σx1,t-1, σx2,t-1 shows asymmetric stretching of gate in the direction of movement, σy,t-1 is the stretching parameter of gate in orthogonal to the movement direction and θt-1 is rotation angle of centric coordinate system. The goal is to estimate parameters of gate at time t.Using Kalman filter as a standard method in parameter estimation, median and covariance matrixes could be calculated as follows:(9)mt∣t-1=Amt-1∣t-1,Σt∣t-1=AΣt-1∣t-1AT+Q,mt∣t=mt∣t-1+Kt(zt-Cmt∣t-1),Σt∣t=Σt∣t-1-KtCΣt∣t-1,St=CΣt∣t-1CT+R,Kt=Σt∣t-1CTSt-1.Typical elliptical tracking gate at timet, could be formulated using median mt∣t and innovation covariance St as follows:(10)(zt-mt∣t)TSt-1(zt-mt∣t)≤γ,
where z is the validated measurement and γ is a parameter to adjust gate size.Diagonal terms of innovation covarianceSt are diameters of elliptical gate which are standard deviations of gaussian distribution on centric coordinate system. Off-diagonal terms of St represent rotation angle of centric coordinate system.Parameters of typical elliptical gate at timet are σx,t, σy,t and θt.In Figure3, elliptical gate in x1ox1 is represented as xTΣ2-1x=1 and in X1OX1 is represented as XTΣ1-1X=1, where(11)Σ2=[σx,t200σy,t2],Σ1=St,X=[X1X2]T,x=[x1x2]T.Figure 3
Elliptical gate in coordinate systemsx1ox2 and X1OX2.Coordinate systemsx1ox1 is transferred to the X1OX1 using simple transfer matrix T as follows:(12)X=TxwhereT=[cos⁡⁡θ-sin⁡⁡θsin⁡⁡θcos⁡⁡θ].In the following, relation between parameters ofΣ2 and Σ1 are shown:(13)xTΣ2-1x=XTΣ1-1X,Σ2-1=TTΣ1-1T.After some simplification, relations between parameters of elliptical gate and elements of innovation covariance could be achieved as follows:(14)θt=12tg-1(2S12,tS11,t-S22,t),σx,t2=-S11,tcos⁡2⁡θt-1+S22,tsin⁡2⁡θt-1,σy,t2=S11,tsin⁡2⁡θt-1-S12,tsin⁡2⁡θt-1+S22,tcos⁡2⁡θt-1,
where S11,t, S12,t, S21,t, S21,t and S22,t are elements of matrix St.In this paper, Klaman filter is used to estimate parameters of asymmetric gate. The median that is achieved from Kalman filter is set as median of asymmetric Gaussian distribution which is the center of asymmetrical gatemt. Using (14), S11,t, S12,t, S21,t, S21,t, and S22,t are used to estimate θt, σx,t, and σy,t. It is assumed that σx1,t=σx,t as a standard deviation of asymmetrical gate on movement direction. To calculate parameter σx2,t, estimated acceleration in movement direction, âx,t is used which could be estimated from constant acceleration model and Kalman filter.Ifâx,t=0, probability of existence of target in both side of median in movement direction are equal. Therefore, σx1,t is set equal to σx2,t and asymmetrical gate is converted to elliptical gate.Ifâx,t>0, probability of target existence in movement direction is greater than negative side. It means that σx1,t should be greater than σx2,t which is resulted to following proposed equation:(15)σx1,tσx2,t=1+12âx,tT2,
where T is sampling time and âx,t is estimation of acceleration in movement direction.Ifâx,t<0, probability of existence of target in negative side of movement direction is greater than positive sight. So σx2,t should be greater than σx1,t which is resulted to following proposed equation:(16)σx2,tσx1,t=1-12âx,tT2.In proposed estimation method, the ratio of standard deviations in direction of movement is proportional to sampling time and estimated acceleration in movement direction.


## 4. Analytical Comparison between Asymmetrical and Elliptical Gate

In this part, analytical comparison between asymmetrical gate and typical elliptical gate in tracking of targets with nonzero acceleration are studied. Volumes of gates are considered as a proper criterion in comparison. To compare volumes of gates, it is assumed that in-gate probabilities of distributions are equal for both gates.In tracking with elliptical gate, probability of distribution in centric coordinate system is Gaussian as following:(17)f1(zt)=12πσx0σy0×exp⁡(-12(zt-m0)T[σx000σy0]-1(zt-m0)),
where m0 is median, σx0 is standard deviation of distribution on movement direction, and σy0 is standard deviation of distribution on orthogonal to movement direction.In tracking with asymmetric gate, it is assumed that probability of target distribution in centric coordinate system is asymmetric gaussian as follows:(18)f2(zt)=12πσy1((σx1+σx2)/2)×exp⁡(-12(zt-m1)T[σxi00σy1]-1(zt-m1))i=1,2,
where m1 is median, σx1 and σx2 are standard deviations of distribution on movement direction, and σy1 is standard deviation of distribution on orthogonal to movement direction.Because of the fact that probability distributions in (17) and (18) are represented in centric coordinate system, off-diagonal elements of covariance matrixes are zero.To compare between asymmetric gate and elliptical gate, it is assumed that the target has positive acceleration in movement direction. Parameters of distributions (17) and (18) could be estimated using Kalman filter and the proposed method in (15) and (16). Therefore, the relation between parameters of asymmetric gate and elliptical gate are achieved as follows:(19)σx≜σx0=σx1,σy≜σy0=σy1,m≜m0=m1,σx2<σx1.In-gate symmetric and asymmetric probability of distribution could be calculated as follows, respectively [14],(20)P1Gt=∬Gtf1(zt)dxdy=∫0d1/2exp⁡⁡(-u)du=1-exp⁡⁡(-d12),P2Gt=∬Gtf2(zt)dxdy=∫0d2/2exp⁡⁡(-u)du=1-exp⁡⁡(-d22).Symmetric gate volumeV1Gt and asymmetric gate volume V2Gt are considered as follows:(21)V1Gt=d1πσy0σx0,V2Gt=d2πσy1(σx1+σx22).It is assumed that, gate probabilities are equal in symmetric and asymmetric gate. Therefore, regarding (19), the following relation could be achieved:(22){P1Gt=P2Gt⟹d1=d2}σy0=σy1(σx1+σx22)<σx0}⟹V2Gt<V1Gt.Using the above equation, we get that with equal in-gate probability for symmetric and asymmetric gates, volume of asymmetric gate would be smaller than volume of symmetric gate. It means that with equal probability for asymmetric and elliptical gate, computational complexity to find target inside asymmetrical gate would be less than computational complexity inside of elliptical gate. It is because of the fact that volume of asymmetrical gate is smaller than volume of elliptical gate with equal in-gate probability of distribution.


## 5. Optimal Size of Gate

Elliptical gates in [14] are represented as follows:(23)(zt-mz)TSt-1(zt-mz)≤d,
where zt=[xtyt], mz is center of gate, and St is innovation covariance matrix that has information about rotation direction of gate and ratio of diameters of gate. Asymmetrical gate that is proposed in this paper could be represented similar to (23) as(24)(zt-mz)TSt-1(zt-mz)≤d,
where zt=[xtyt], mz=[mt0], and(25)St=[σxi,t200σy,t2]i∈{1,2}.Ifxt>mt, we choose i=1 and if xt<mt, we choose i=2.zt would be inside the gate if two following constraints are satisfied.(a)
Ifxt>mt, then
(26)(zt-mz)T[σx1,t200σy,t2]-1(zt-mz)<d.(b)
Ifxt<mt, then(27)(zt-mz)T[σx2,t200σy,t2]-1(zt-mz)<d.
Otherwise, zt is out of the gate.It is easy to see from (24) that shape of the gate could be determined by mz, σx2,t2, σx1,t2, and σy,t2, whereas the size of the gate could be smaller or larger using just d.As the gate is made larger, more clutter or observation vectors other than the tracked target are included within it, so that tracking becomes more difficult. On the other hand, if the gate is made smaller, there is an increasing danger that the observation vector from the tracked target may no longer fall within the gate.So, in this paper, we define a cost function to find optimum size of gate using the cost function for elliptical gates that is proposed in [14]. In this paper, using the method proposed in [14], optimum size of asymmetrical proposed gate is calculated.Suppose that whole points inside of the gate are defined as follows:(28)Gt={zt∣(zt-mz)TSt-1(zt-mz)≤d}.In-gate probability could be calculated by:(29)PGt=∬Gtf(xt,yt)dxdy,
where f(xt,yt) is asymmetrical Gaussian distribution.After some simplifications, in-gate probability simplifies as follows:(30)PGt=∫0d/2e-udu.From (30), it is visible that in-gate probability is independent from the shape of the gate which is defined using parameters mz, σx2,t2, σx1,t2, and σy,t2, and it is just function of the gate size d.Volume of gate could be considered as(31)VGt=∬Gtdxdy.After simplification, volume of gate reduced to(32)VGt=dπσy,t-1(σx1,t-1+σx2,t-12).Assuming that probability of false alarm observation at timet is a constant value Bft, mean number of false observed signals inside of the gate are BftVGt:(33)BftVGt=Bftdπσy,t-1(σx1,t-1+σx2,t-12).With the assumption that target observation probability is constantPD, the probability that target is observed inside of the gate is PDPGt. In other side, mean number of false signals inside of the gate is BftVGt. The goal is to find optimum size of the gate so that PDPGt is maximum and BftVGt is minimum. With respect to the fact that PDPGt and BftVGt are function of d, so it is possible to define h(d) in such a way that, with maximizing it, optimum value of d is calculated:(34)h(d)=PDPGt-cBftVGt,h(d)=PD∫0d/2e-udu-cBftdπσy,t-1(σx1,t-1+σx2,t-12),
where c is a constant value:
(35)∂h(d)∂d=0⟹dopt=-2ln⁡⁡c-2ln⁡⁡2π-2ln⁡⁡Bft-2ln⁡⁡(σy,t-1(σx1,t-1+σx2,t-12))+2ln⁡⁡PD.Largerc increase emphasis on BftVGt and number of false observed signals inside of the gate decreases.


## 6. Simulation Result

To simulate the preferences of the new method, in first we generate samples of a track using model (36). In this model, let rx(t) be position, let sx(t) be velocity, let ax(t) be acceleration of the target in movement direction, let ry(t) be position, let sy(t) be velocity, and let ay(t) be acceleration of the target in orthogonal to movement direction at time t in centric coordinate system, where t stands for continues time index. Dynamics of the target is described by system model that could be written in stochastic differential equation:(36)Ẋ(t)=AX(t)+Bn(t),
where X(t) is state vector(37)X(t)=[rx(t)sx(t)ax(t)ry(t)sy(t)ay(t)]T.A is state transition matrix:(38)A=[010000001000000000000010000001000000],
vector B is defined as(39)B=[001000000001]T,
vector n(t) is defined as(40)n(t)=[n1(t)n2(t)]T,
where n1(t) is random noise with uniform distribution between zero and one and n2(t) is zero mean white gaussian noise.By applying time discretization to (36) with sampling time T, we have a discrete time system model:(41)Xk=AdXk-1+Bdnk.State transition matrixAd is(42)Ad=[1TT2200001T0000010000001TT2200001T000001],
and vector Bd is(43)Bd=[T33T22T000000T33T22T]T.Measured position of the target in centric coordinate system is denoted byzk and is assumed to be obtained by observation model:(44)zk=CXk+wk,
where C is(45)C=[100000000100],
and wk is defined as(46)wk=[w1kw2k]T,
where w1k is random noise with uniform distribution between zero and one and w2k is zero mean white gaussian noise.In Figure4, target positions are shown that is generated using the above model. Monte Carlo simulation is used to approximate probability distribution of target position in next time step. Approximated probability of distribution is shown in Figure 4.Figure 4
Target track and estimation of probability of distribution in next time step using Monte Carlo simulation.It is easy to understand from Figure4 that probability distribution in next time could be illustrated using asymmetric distribution that formulated previously.Kalman filter is used to estimate parameters of asymmetric gate that are considered in part 3. Actual and estimated values ofrx(t), sx(t), and ax(t) in centric coordinate system are shown in Figure 5.Figure 5
Actual (blue solid) and estimated (red dash) values ofrx(t), sx(t), and ax(t) in centric coordinate system.To show proficiency of the proposed asymmetrical gating method in comparison with previous gating methods such as circular gating, elliptical gating, and rectangular gating, similar simulation scenarios are studied for circular, elliptical, and rectangular gates. The volumes of gates in each simulation are equal and the location of the target in the next time step is important in the comparison between different gates. The number of times that the target falls in a gate in the next time step is a comparison index between gates. In Table1, comparison results between circular gate, elliptical gate, rectangular gate, and proposed asymmetrical gate are shown for different gate volumes.Table 1
Comparison results between circular gate, elliptical gate, rectangular gate and asymmetrical gate for different gate volumes.
Gate volumeRectangular gateCircular gateElliptical gateAsymmetrical gate0.002551%65%73%92%0.00568%78%84%96%0.0190%98%100%100%In Table1, percent falls of the target inside each gate are shown for different volumes of gate. For example, for volume of gate 0.0025, percent fall of the target inside rectangular gate is 51%, inside circular gate is 65%, inside elliptical gate is 73% and inside asymmetrical gate is 92%.For different volumes of gates, it could be seen from Table1 that proposed asymmetrical gate has more in-gate probability than other gating methods and the number of target falls inside of the asymmetrical gate in the next step is more than others. It is because of the asymmetrical gate ability to shape itself to have more percent falls of the target inside the gate. Although parameters of other gates can be updated in each step to have more percent falls inside the gates, the ability of shape changing in other gates is less than asymmetrical gate specially in maneuvering target tracking applications. Not that the percent falls of the target inside of the gates increases by increasing gate volume that could be seen easily from Table 1.


## 7. Conclusion and Future Remarks

In this paper, we introduced asymmetric gating technique for tracking maneuvering targets that have nonzero acceleration in movement direction. Asymmetric gate is defined as a cross-surface of asymmetric Gaussian distribution. Standard Kalman filter is used to estimate some parameters of asymmetrical gate. Standard deviation of asymmetrical distribution in opposite to the movement direction is estimated using a proposed method in which sampling time and estimated acceleration are used. Preference of asymmetrical gate to the elliptical gate is proved analytically subject to constant in-gate probability of distribution for both gates, in which volumes of gates are used as a comparison criterion. We derived an optimization method to finding optimum size of asymmetrical gate. Optimum size of asymmetrical gate is obtained as a function of some parameters such as probability of target observation and probability of false alarms that should be tune manually in each special applications.As a future remarks, it could be assumed that probability of distribution in orthogonal to the movement direction in centric coordinate system is considered asymmetric. Also, estimation of gate parameters could be studied in typical coordinate system, after enough research, and proves on generalization of Kalman filter for linear systems with asymmetric gaussian probability of distributions for both process and measurement noise.



---

*Source: 670485-2012-05-15.xml*