Translator Disclaimer
11 February 2020 An analysis of the influence of the correlation gate shape on the TBD algorithm effectiveness
Author Affiliations +
Proceedings Volume 11442, Radioelectronic Systems Conference 2019; 114420D (2020) https://doi.org/10.1117/12.2565751
Event: Radioelectronic Systems Conference 2019, 2019, Jachranka, Poland
Abstract
In the classical radar processing chain detection and tracking are separate, consecutive processes. In the case of the large amount of detection the number of false alarms and in consequence the number of false plot-to-track associations highly increase. In such case it can be used one of the Track-Before-Detect (TBD) algorithms that connects the detection and tracking into one process. An important part of such method is the plots preselection during the track forming process which is related to track constraints. One of the simplest method is gating that eliminates unlikely observation-to-track pairings. The basic gates in the two-dimensional space are the rectangular one and elliptical one. In the article the comparison of the use of both shapes is presented. The number of false associations and the gating computational complexity is considered.

1.

INTRODUCTION

The process of designing of the radar processing chain can be divided into some functional blocks. In the classic approach the stages of signal acquisition, automated object detection and tracking can be distinguished [1]. The problem arises when multiple targets should be tracked. In such case the measurements have to be associated with previously initiated tracks. This process requires the plots preselection to reject the associations having the smallest probability. The basic method of achieving it is the use of the specified area where the association can be made called the correlation gate [2],[3]. The obtained association should be verified in further process, but gating allows for the limitation of computation.

The classic approach could not deal with object of small radar cross section or moving with high linear velocity, which are called the dim targets. The received echo signals will have small amplitude and their detection will require the lowering of the Neyman-Pearson detector threshold, which is related to the increase of the probability of detection. The side effect of getting closer to the noise level is the increase of probability of false alarm. In consequence the false plot to track association will more often occur and the computational burden will increase.

To minimize the side effects, the track-before-detect (TBD) methods as an alternative approach should be used. As stated in [4], in this case, the detection of a target and the estimation of its state are an inseparable part of the same decision process. In general, the data obtained in consecutive frames (scans or antenna rotations) are correlated and the value of a some cost function is calculated, which is the base for the decisions about the target presence. Therefore the TBD algorithms are also described as multi-frame detectors. Their principle of operation enforce that the detection decision is delayed, but is more reliable than in classical approach.

The TBD algorithms may used to process either the raw radar signal or infrared image [2],[5], but in many application the two-stage approach with significantly lowered threshold are very common [6],[7]. There are many TBD methods [8], one of them is, used in this article, the dynamic programming (DP) algorithm, called also the Viterbi algorithm. The method was first proposed by Barniv in [9]. The principle of its operation bases on the state machine, in which the state transitions are charged with some cost, that should be minimized or maximized depending on the assumed cost function. In TBD approach the particular nodes of the state machine are candidate plots, which are connected by target dynamics. Despite the huge advantage of this class of algorithms, which is the ability of parallel computation [10], the search of correlation between all candidate plots will be highly inefficient due to the fact that the number of possible trajectories increases exponentially with the number of processed frames [6]. In effect, some track constrains basing on e.g. maximum allowable linear or radial velocity should be assumed. In practice this can be realized by gating as in classical tracking.

2.

CORRELATION GATES

The correlation gate should be understood as an area around the reference point called the middle point of the gate and with boundaries defined for every measurement space coordinate. In this article the object’s maximal linear speed is constrained. In effect, the gate’s middle point is located at the currently processed plot and the boundaries are determined by the object’s allowable dislocation in every direction of the adopted coordinate system.

There are many correlation gates shapes that are strictly matched to particular algorithms. Among the basic shapes most common are the rectangular one and elliptical one [2],[11]. More complicated shapes are dedicated to the tracking of, maneuvering targets and adaptive gates [12].

In this article only the basic shapes are compared. The considerations are limited to 2D space containing range and azimuth, but can be easily expanded into whole radar measurement space.

2.1

Rectangular gate

Because the maximal allowable linear speed is assumed, the size of the rectangular correlation gate is described as:

00462_psisdg11442_114420d_page_2_1.jpg

where:

  • Rmax – maximal allowable dislocation in range,

  • vmax – linear speed constraint,

  • Ts – duration of one scan,

  • αmax,i – maximal allowable dislocation in azimuth for i-th plot,

  • Ri – the radar to plot distance of i-th plot.

As it can be seen, the correlation gate’s size in range is independent on the plot location, but the width in azimuth is inversely proportional to the radar-plot distance. The plots are initially correlated if the inequality is satisfied:

00462_psisdg11442_114420d_page_2_2.jpg

where:

  • zkz-th coordinate of k-th examined plot,

  • ziz-th coordinate of the middle of correlation gate,

  • zmax – gate width in z-th coordinate,

  • γ – heuristic coefficient.

The above equations prove that the use of rectangular correlation gate is not computationally demanding. Unfortunately, there occurs a chance that plot will fall in the gate’s “corner”, i.e. the area where the constraint are not met. To eliminate such case the additional test should be used.

2.2

Elliptical gate

In the classic tracking approach the elliptical gate is widely used due to the best representation of Gaussian distribution. In this approach the statistical distance between observations and the association of plots is determined by the matrix of innovation [11]. In this article the association test is described as:

00462_psisdg11442_114420d_page_3_1.jpg

where:

  • xx-th plot coordinate,

  • yy-th plot coordinate,

  • δ – correlation gate semi-axis.

3.

THE COMPARISON OF CORRELATION GATES EFFECTIVENESS

In the article the correlation gate effectiveness is measured by the probability that the kinematic constraints are not met, what is further called the corner fitting, and the computational complexity is considered. To generate testing data the radar air picture simulator described in [13] was used. It allows to generate the list of plots detected by the radar in few consecutive scans. The targets plots are simulated basing on chosen objects model and false alarms are created accordingly to assumed radar parameters. In generator the antenna characteristic, measurement errors, time of antenna revolution and maximum range is taken into account. The maximum range was set to 600 km and maximum elevation seen by the radar antenna was 30°. The probability of false alarm 10-4 was set, thanks to which the large number of candidate plots was obtained. Every false candidate plot had a random location with uniform distribution within the covered area. Besides them, three determined trajectories of dim targets were simulated. All of them starts at the range of 100 km at the azimuth of 90° and moves into different directions. Two scans of scenario that was analyzed is presented in Figure 1.

Figure 1.

An example of generated plots

00462_psisdg11442_114420d_page_3_2.jpg

3.1

Monte Carlo test

The plots can be associated with each other if they fit into the gate boundaries. For example presented in Figure 2 5 plots fit into rectangular gate but to the only 3 elliptical one.

Figure 2.

The plots association using the rectangular and elliptical gates

00462_psisdg11442_114420d_page_4_1.jpg

To examine the gates effectiveness, 1000 different radar air picture situations were generated by earlier mentioned simulator to make the Monte Carlo test. Despite of using the same generation parameters, the simulator ensures that every scenario contained different location of plots. In every test correlations between plots in the first and the second scan were searched. At the beginning, the number of corner fittings in reference to all obtained fittings was examined. This number can be calculated as the difference between the number of fittings into elliptical and rectangular gate. The result of the test is presented in Figure 3.

Figure 3.

The number of corner fittings compared with number of all associations.

00462_psisdg11442_114420d_page_4_2.jpg

The same data in the form of histogram are presented in Figure 4. As shown, the average level of corner fittings occurrence is about 17%.

Figure 4.

Histogram of corner fittings occurrence

00462_psisdg11442_114420d_page_4_3.jpg

The assumed configuration of simulator causes that during one scan around 600 plots is generated. The obtained results shows that 17% of plot associations do not meet kinematic constraints. Thus, the use of rectangular gate is connected with unnecessary computational burden, despite its simplicity. Additional analysis of Figure 1 indicates that significant number of plots is concentrated in the neighborhood of radar, what is caused by the way of data generation. As mentioned before, the false alarms are generated accordingly to uniform distribution in range and azimuth. It was additionally assumed that in every resolution cell only one plot may occur, but the covered area increases with range. In effect, the more distant plots are wider spread than the closer ones. Thus in the neighborhood of the radar the chance for false plots associations increases. In consequence the division of the space of observation has been considered. Three equal range sectors have been distinguished and the number of association in every of them has been examined. The results are presented in Table 1

Table 1.

The average number of all associations of plots in selected range sectors.

all associations0-200 km200-400 km400-600 km
19311375353203

The test proved that the majority of plots associations occurs in the first sector, which in consequence may lead to the largest number of false plot correlations. Thus, among all the associations in every sector included in Table 1 the number of corner fittings occurrences was tested. The obtained results are presented in Figure 5 and Figure 6.

Figure 5.

The number of corner fittings in every range sector.

00462_psisdg11442_114420d_page_5_2.jpg

Figure 6.

Histogram of corner fittings occurrence in every range sector

00462_psisdg11442_114420d_page_5_1.jpg

As the absolute values show, the largest number of incorrect associations occurs within range up to 200 km, but when related to the number of all associations in every sector, the probability of incorrect associations has the lowest level there. In consequence it can be concluded that for the range up to 200 km the elliptical gate will be recommended and for further sectors application of the rectangular gate will be sufficient.

3.2

Computational complexity

According to presented considerations, the use of elliptical gate should be preceded by the rectangular gate, which leads automatically to the increased computational complexity. The quantitative difference of the number of required operations is dependent on the assumed cost function of DP-TBD algorithm. Its proper selection is the most difficult part of the design of algorithm of this class [14]. It can be based on the likelihood ratio or on the use of the information included in plots.

The second approach was implemented in [6], where the goal of algorithm is the maximization of the sum of plots amplitudes. In such case the transformation of plot coordinates into Cartesian system to use the equation (3) leads to increased number of required computations. It has to be noticed that with every plot on average three others are associated. To every plot three summation, eight multiplication and calculation operations of the values of 4 trigonometric functions will be required. The number of operations could be optimized if the set of information included in plot will be extended by its Cartesian coordinates. The gain of such solution is strictly dependent on the number of plots and possible correlations between them.

If DP algorithm uses the likelihood ratio as cost function, then a model of probability function of allowable transition between plots is required. According to [10], the cost function can be divided into the set of independent scalar functions. In effect only the distance between plots should be considered in a simplified case. This operation is made as the part of elliptical gate application and the use of the rectangular gate would only shift the calculation to another part of DP algorithm.

4.

SUMMARY

In the article the comparison of two correlation gates’ shapes applied in the dynamic programming TBD algorithm was presented. The statistical examination of meeting the kinematic constraints and considerations about the estimated computational complexity was included.

If only the measurement data are taken into account, the elliptical gate will cause the increase of computational burden. To optimize the number of operations it can be used only in limited range or the information included in plot can be extended at least temporary.

In another approach, where the algorithm bases on the likelihood ratio and the plot transition function is distance-dependent, the elliptical gate does not increase the number of operations significantly. The use of rectangular gate will only delay the necessity of additional calculations in Cartesian coordinate system.

In summary, the best correlation gate shape cannot be indicated unambiguously, due to dependence on the particular application of dynamic programming algorithm. Additionally, decision is correlated with the TBD algorithm quality rating, which can be the time of calculations or the minimization of the probability of false plots associations. To resolve the problem of creating false tracks and the influence on the true objects detection the further test should be made.

REFERENCES

[1] 

Richards M.A., Fundamentals of Radar Signal Processing, McGraw-Hill, Nowy Jork (2005). Google Scholar

[2] 

Blackamn S. and Popoli R., Design and Analysis of Modern Tracking Systems, Artech House, Norwood (1999). Google Scholar

[3] 

Mahafza B., Atef E., MATLAB Simulations for Radar Systems Design, Chapman & Hall/CRC Press, New York (2003). https://doi.org/10.1201/9780203502556 Google Scholar

[4] 

Gish H. and Mucci: R., “Target state estimation in a multi-target environments,” IEEE Trans. A. Elec. Sys., 23 (1), 60 –72 (1987). https://doi.org/10.1109/TAES.1987.313336 Google Scholar

[5] 

Davey S.J., Rutten M.G. and Cheung B., “A Comparison of Detection Performance for Several Track-before-Detect Algorithms,” EURASIP Journal on Advances in Signal Processing, 2008 (2008). Google Scholar

[6] 

Grossi E., Lops M. and Venturino L., “A Novel Dynamic Programming Algorithm for Track-Before-Detect in Radar System,” IEEE Transactions on Signal Processing, 61 (10), 2608 –2619 (2013). https://doi.org/10.1109/TSP.2013.2251338 Google Scholar

[7] 

Wang Z. and Sun J., “Maneuvering target tracking via dynamic-programming based Track-Before-Detect algorithm,” in 2016 CIE International Conference on Radar (RADAR), 1 –4 (2016). Google Scholar

[8] 

Okoń-Fafara M and Kawalec A., “High-speed object detection methods,” in Proc. SPIE 10715, 2017 Radioelectronic Systems Conference, (2018). Google Scholar

[9] 

Barniv Y., “Dynamic programming algorithm for detecting dim moving targets,” Multitarget-Multisensor Tracking: Advanced Application, Artech House, Norwood, USA (1990). Google Scholar

[10] 

Arnold J., Shaw S. W. and Pasternack H., “Efficient target tracking using dynamic programming,” IEEE Transactions on Aerospace and Electronic Systems, 29 (1), 44 –56 (1993). https://doi.org/10.1109/7.249112 Google Scholar

[11] 

Kosuge Y. and Matsuzaki T., “The optimum gate shape and threshold for target tracking,” in SICE 2003 Annual Conference, 2152 –2157 (2003). Google Scholar

[12] 

Park W. J. and Park C. G., “Multi-target Tracking Based on Gaussian Mixture Labeled Multi-Bernoulli Filter with Adaptive Gating,” in 2019 First International Symposium on Instrumentation, Control, Artificial Intelligence and Robotics (ICA-SYMP), 226 –229 (2019). Google Scholar

[13] 

Okoń-Fąfara M., Kawalec A. and Witczak A., “Radar air picture simulator for military radars,” in Proc. SPIE 11055, XII Conference on Reconnaissance and Electronic Warfare Systems, (2019). Google Scholar

[14] 

Yan B., Xu L., Li M. and Yan J. Z., “Track-before-detect algorithm based on dynamic programming for multiextended-targets detection,” IET Signal Processing, 11 (6), 674 –686 (2017). https://doi.org/10.1049/iet-spr.2016.0582 Google Scholar
© (2020) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
M. Okoń-Fąfara and A. Kawalec "An analysis of the influence of the correlation gate shape on the TBD algorithm effectiveness", Proc. SPIE 11442, Radioelectronic Systems Conference 2019, 114420D (11 February 2020); https://doi.org/10.1117/12.2565751
PROCEEDINGS
7 PAGES


SHARE
Advertisement
Advertisement
Back to Top