DESC:TECHNICAL FIELD
The present invention relates generally to a novel coarse gating method to speed up gating for radar target tracking. The invention more specifically relates to a method to overcome high computational load of gating.
BACKGROUND
In radar target tracking, gating play important role in selecting measurements for the track-to-measurement association and tentative track formation. The main idea of gating is to find measurements that fall within the gate. The purpose of gating is the preselection of suitable measurements which is essential for reducing the computational load of the track initiation and the track maintenance module in the tracker. In radar target tracking, the shape of the gate can be any closed contour depending on the type of stochastic system modelling and estimation filter used. For a linear stochastic system, the shape of the gate is ellipsoidal. The ellipsoidal gate is defined using mean (center of ellipsoid) and covariance (orientation and size of ellipsoid) and the gating procedure is called ellipsoidal gating. The naïve ellipsoidal gating for track-to-measurement association works as follows,
Given a predicted value (mean) of the measurement y ^_i of the i^th track and the associated covariance S_i (also called as innovation covariance), to verify that the j^th measurement y_j is satisfying ellipsoidal gating condition, first the Mahalanobis distance d_M is calculated as,

d_M^2=(y_j- (y_i ) ^ )^T S_i^(-1) (y_j-(y_i ) ^ ) (1)

Only if d_M meets the requirement
d_M^2=? (2)
with ? being the gate size, then the j^th measurement y_j is considered to fall within the ellipsoidal gate of the i^th track.
In naive gating each track-to-measurement combination (i,j) has to be gated, i.e., m·n individual gating processes are to be conducted, with m being the number of tracks and n being the number of measurements. Hence, the computation time of the naïve gating procedure is T_NG?O(m·n) which implies that as the number of measurements may be high due to clutter, the number of combinations to be gated increases.
US6239740B1 discloses an efficient gating in data association with multivariate gaussian distributed states. It describes a general method for determining, from the covariance matrix, minimal d-dimensional ellipsoids for the overlap when a gating criterion is satisfied. Then, a circumscribing box for the ellipsoid is found and a multidimensional search tree method is used to reduce the overall scaling of the gating process.
CA2138855 discloses an efficient multi-target tracking method. It assumes gate region is square with sides parallel to the axes. The measurements data are scaled so that the gate width is one, then the measurements are replicated and grouped based on the computation of the integer parts of the measurement data. To access the measurements near a predication, the nearest coordinates to the predication are taken and the contiguous set of data with these integerized measurements is examined.
V.D. Nguyen and T. Claussen disclose a reducing computation complexity of gating procedures using sorting algorithms. It is a proceeding of the 16th international Conference on Information Fusion, Istanbul, 2013, pp. 1707-1713, which describes a Gating-by-Sorting approach to accelerate the gating procedure. It uses sorting algorithms and binary search to carry out coarse gating in first step using fixed gate size followed by a second ellipsoidal gating step. Only the second step uses the variable gate size depending on the covariance of the measurements and the predication. The usage of these fixed gate size disadvantageous in certain scenarios. The Gating-by-Sorting approach include calculation of the intersection set which takes more time as the number of measurement increases.
R. G. Sea discloses an efficient suboptimal decision procedure for associating sensor data with stored tracks in real-time surveillance systems. It is a paper of 1971 IEEE Conference on Decision and Control, Miami Beach, FL, USA, 1971, pp. 33-37, DOI: 10.1109/CDC.1971.270945, in which rectangular gate circumscribing the ellipsoid gate is considered for coarse gating. In case of more than one measurement is within the gate, rectangular gating is followed by more precise ellipsoid gating.
Nguyen V. D. discloses a small-target radar detection and tracking within the pitas hard- and software environment, in Future Security 2012 Communication in Computer and Information Science Springer, Berlin, Heidelberg, vol. 318, pp. 347-358, 2012, which describes a two-step-gating (2SG) to accelerate the gating procedure. In the first step box gating is used as coarse gating to reduce the number of Mahalanobis distance calculations and also matrix inversions for second step. The first gating step is implemented by using Quicksort. To assure that the first step does not influence the gating result but only accelerate the gating procedure, the limits for length of each box size must be set sufficiently large.
Therefore, there is still a need of a technical solution which solves the above defined problems and provide a method to overcome high computational load of gating.
SUMMARY
This summary is provided to introduce concepts related to a novel coarse gating method to speed up gating for radar target tracking. The invention more specifically relates to a method to overcome high computational load of gating.
In an embodiment of the present invention, a coarse gating method for speeding up gating for radar target tracking is disclosed. This method includes storing the measurements in the polar bins, said polar bins includes range and azimuth bins; computing intersection bins based on radial vector intersection procedure, said intersection bins are polar bins between the intersection points of the gate and the radial vector in each azimuth bin direction; computing boundary bins based on gate boundary bins procedure, said boundary bins are polar bins corresponding to the points uniformly distributed on boundary of gate; computing gate bins based on gate binning procedure, said gate bins encompasses the gate and is union of intersection bins and boundary bins; collecting the measurements stored in gate bins as the final outcome of coarse gating method.

BRIEF DESCRIPTION OF ACCOMPANYING DRAWINGS
The detailed description is described with reference to the accompanying figures.
Figure 1 describes the principle of gating, in accordance with an exemplary embodiment of the present invention.
Figure 2 illustrates the storage of the measurements in polar bins which is the first step (1001 in Fig. 10) of disclosed coarse gating method, in accordance with an exemplary embodiment of the present invention.
Figure 3 illustrates the outcome of the gate binning procedure which is the fourth step (1004 in Fig. 10) of disclosed coarse gating method, in accordance with an exemplary embodiment of the present invention.
Figure 4 illustrates the intersection of gate not enclosing origin and the radial vector in an azimuth bin direction, in accordance with an exemplary embodiment of the present invention.
Figure 5 illustrates the intersection of gate enclosing origin and the radial vector in an azimuth bin direction, in accordance with an exemplary embodiment of the present invention.
Figure 6 illustrates the intersection bins obtained by repeating radial vector intersection procedure for each azimuth bin direction which is the second step (1002 in Fig. 10) of disclosed coarse gating method, in accordance with an exemplary embodiment of the present invention.
Figure 7 illustrates the outcome of gate boundary bins procedure which is the third step (1003 in Fig. 10) of disclosed coarse gating method, in accordance with an exemplary embodiment of the present invention.
Figure 8 illustrates the flowchart of radial vector intersection procedure which is the second step (1002 in Fig. 10) of disclosed coarse gating method, in accordance with an embodiment of the present invention.
Figure 9 illustrates the flowchart of gate boundary bins procedure which is the third step (1003 in Fig. 10) of disclosed coarse gating method, in accordance with an embodiment of the present invention.
Figure 10 illustrates a flowchart of a coarse gating method for speeding up gating for radar target tracking, in accordance with an embodiment of the present invention.
It should be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative methods embodying the principles of the present invention. Similarly, it will be appreciated that any flow charts, flow diagrams, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computer or processor, whether or not such computer or processor is explicitly shown.
DETAILED DESCRIPTION
The various embodiments of the present invention describe about a novel coarse gating method to speed up gating for radar target tracking, more specifically relates to a method to overcome high computational load of gating.
In the following description, for purpose of explanation, specific details are set forth in order to provide an understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these details. One skilled in the art will recognize that embodiments of the present invention, some of which are described below, may be incorporated into a number of systems.
However, the apparatuses and methods are not limited to the specific embodiments described herein. Further, structures and devices shown in the figures are illustrative of exemplary embodiments of the presently invention and are meant to avoid obscuring of the present invention.
Furthermore, connections between components and/or modules within the figures are not intended to be limited to direct connections. Rather, these components and modules may be modified, re-formatted or otherwise changed by intermediary components and modules.
The appearances of the phrase “in an embodiment” in various places in the specification are not necessarily all referring to the same embodiment.
It should be noted that the description merely illustrates the principles of the present invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described herein, embody the principles of the present invention. Furthermore, all examples recited herein are principally intended expressly to be only for explanatory purposes to help the reader in understanding the principles of the invention and the concepts contributed by the inventor to furthering the art and are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the invention, as well as specific examples thereof, are intended to encompass equivalents thereof.
In an embodiment of the present invention, a coarse gating method to speed up gating for radar target tracking comprises the steps of storing the measurements in the polar bins, said polar bins includes range and azimuth bins; computing intersection bins based on radial vector intersection procedure, said intersection bins are polar bins between the intersection points of the gate and the radial vector in each azimuth bin direction; computing boundary bins based on gate boundary bins procedure, said boundary bins are polar bins corresponding to the plurality of points uniformly distributed on boundary of gate; computing gate bins based on gate binning procedure, said gate bins encompasses the gate and is union of intersection bins and boundary bins; collecting the measurements stored in gate bins as the final outcome of coarse gating.
In another embodiment, the method includes narrowing down the spatial extension of measurements to be considered for gating by first conducting coarse gating and only measurements as the outcome of coarse gating to be gated later by conducting gating condition checks as in naïve gating.
In another embodiment, the method includes storing the measurements in polar bins having controllable plurality of range and azimuth bins.
In another embodiment, the plurality of points on boundary of gate is a controllable parameter.
In another embodiment, the method which is applicable to gate having shape of any closed contour (e.g., circle, rectangle, ellipsoid, etc.) defined using explicit function, implicit function, parameter function and tabular method.
In another embodiment, the method is extended to 3D radar by incorporating additional elevation dimension into disclosed invention and storing 3D radar measurements into spherical bins having controllable plurality of range, azimuth and elevation bins.
In another embodiment, the method which can be used in plot-to-plot fusion, plot-to-track association, track-to-track association.
Figure 1 describes the principle of gating, in accordance with an exemplary embodiment of the present invention. A measurement 101 is considered to pass the gating condition if it inside the gate. The ellipsoidal gate 102 is depicted in Fig. 1 as an example gate. The orientation and size of ellipse depends on the innovation covariance S and gate size ?. The semi-axes of the ellipsoid 103 are the square roots of the eigenvalues of ?S. The spatial extension of the gate 102 is usually much smaller than the spatial extension of all measurement 104 i.e., radar coverage area. Hence, computation of gating condition check (for example, calculation of Mahalanobis distance (1) as in ellipsoidal gating) is actually unnecessary for most of the track-to-measurement pairings, as most pairings could be first gated by less precise but fast gating procedure.
Figure 2 illustrates the storage of the measurements in polar bins which is the first step (1001 in Fig. 10) of disclosed coarse gating method, in accordance with an exemplary embodiment of the present invention. It illustrates the storage of 2D radar measurements 201 in polar bins 202. The complete coverage area of 2D radar having r_min,r_max minimum and maximum range coverage (0 Km, 250 Km is depicted in Fig. 2 as an example) and ?_min,?_max minimum and maximum azimuth (0°, 360° is depicted in Fig. 2 as an example) can be divided into N_(r_bin ) number of bins in range (10 is depicted in Fig. 2 as an example) and N_(?_bin ) number of bins in azimuth (36 is depicted in Fig. 2 as an example) which result in polar bins having width ?r_bin=(r_max- r_min)/N_(r_bin ) in range 203 (25Km is depicted in Fig. 2 as an example) and ??_bin=(?_max- ?_min)/N_(?_bin ) in azimuth 204 (10° is depicted in Fig. 2 as an example). If the measurements are stored in polar bins, one can first do a coarse gating by collecting the measurements stored in the polar bins which encompass gate. A procedure which we call Gate Binning (GB) is proposed to find polar bins which encompass gate.
Figure 3 illustrates the outcome of the gate binning procedure which is the fourth step (1004 in Fig. 10) of disclosed coarse gating method, in accordance with an exemplary embodiment of the present invention. It is a procedure to find polar bins 303 encompassing given gate 302 (ellipsoid gate is depicted in Fig. 3 as an example), which we termed as gate bins. The outcome of the disclosed coarse gating method is the collection measurements stored in these gate bins 303 encompassing given gate 302 which are then gated by conducting gating condition checks as in naïve gating. The main idea of gate binning procedure is to use intersection of the gate and radial vector in an azimuth bin direction. Using start and end range of intersection one can find subset of polar bins encompassing a portion of the gate.
Figure 4 illustrates the intersection of gate not enclosing origin and the radial vector in an azimuth bin direction, in accordance with an exemplary embodiment of the present invention. It illustrates the intersection 402, 403 of gate 404 (ellipsoid gate is depicted in Fig. 4 as an example) not enclosing origin 405 and radial vector 406 in the azimuth bin direction corresponding to 60°. The subset of polar bins 407 between to the intersection points 402, 403 encompass a portion of gate 404. If the gate is enclosing origin of the coordinate system, then the start range of intersection is zero.
Figure 5 illustrates the intersection of gate enclosing origin and the radial vector in an azimuth bin direction, in accordance with an exemplary embodiment of the present invention. It illustrates the intersection 502, 503 of gate 504 (ellipsoid gate is depicted in Fig. 5 as an example) enclosing origin 505 and the radial vector 506 in the azimuth bin direction corresponding to 120°. In the case of gate 504 enclosing origin 505, start range of intersection 502 is zero. The subset of polar bins 507 between the intersection points 502, 503 encompass a portion of gate 504.
Figure 6 illustrates the outcome of repeating radial vector intersection procedure for all azimuth bin direction which is the second step (1002 in Fig. 10) of disclosed coarse gating method, in accordance with an exemplary embodiment of the present invention. It illustrates the outcomes 604 of repeating radial vector intersection procedure for each azimuth bin direction 602 and taking union gives required polar bins which we call “Radial Vector Intersection Bins” encompassing given gate 606 (ellipsoid gate is depicted in Fig. 6 as an example). Since the number of azimuth bin directions 602 are finite, some polar bins 605 on boundary of gate 606 may be missed by radial vector intersection 603. However, these missing polar bins on boundary of gate can be found by considering number of points uniformly distributed on boundary of gate and finding corresponding polar gate bins which we call as “Gate Boundary Bins”. Hence, required gate bins which encompasses the gate are union of 1) Radial Vector Intersection Bins and 2) Gate Boundary Bins.
Figure 7 illustrates the outcome of gate boundary bins procedure which is the third step (1003 in Fig. 10) of disclosed coarse gating method, in accordance with an exemplary embodiment of the present invention. It illustrates polar bins 702 corresponding to N_gb number of points (36 points are depicted in Fig. 7 as an example) 703 on boundary of gate 704 (ellipsoid gate is depicted in Fig. 7 as an example) by taking union of polar bin corresponding to each point on the boundary of gate 704.
Figure 8 illustrates the flowchart of radial vector intersection procedure which is the second step (1002 in Fig. 10) of disclosed coarse gating method, in accordance with an exemplary embodiment of the present invention. The input data 802 contains,
1. Radar Coverage Parameters (e.g. In case of 2D radar it includes, a) r_min,r_max: minimum and maximum range coverage in meters b) ?_min,?_max: minimum and maximum azimuth coverage in radians).
2. Grid Parameters (e.g. In case of polar bins it includes, N_(r_bin ) number of bins in range and N_(?_bin ): number of bins in azimuth) to store measurements of one radar scan.
3. Gate Parameters (e.g., center µ, orientation and shape S, gate size ? in case of ellipsoidal gating)
Given input data 802, width of a range bin in meters ?r_bin=(r_max- r_min)/N_(r_bin ) , width of an azimuth bin in radians ??_bin=(?_max- ?_min)/N_(?_bin ) are calculated and set of radial vector intersection bins rvi_bins, azimuth bin counter n are set to empty set and zero respectively in parameter initialization 803. Next, find the start range bin r_(s_bin ) and the end range bin r_(e_bin ) for intersection points of gate and radial vector in the azimuth bin direction ?_bin=?_min+n*??_bin 804. If gate encloses origin of coordinate system 805, then the gate and radial vector intersect at only one point. In this case origin of coordinate system is starting point of intersection, hence start range bin r_(s_bin ) is set to zero 806. The set of polar bins encompassing a portion of gate in ?_bin azimuth bin direction is set polar bin of the form (?_bin,r_bin ) where r_binvaries from r_(s_bin ) to r_(e_bin ) which can be denoted succinctly as {(?_bin,r_(s_bin ):r_(e_bin ) ) } 807. Next append the set {(?_bin,r_(s_bin ):r_(e_bin ) ) } to the set rvi_bins 808 and increment the azimuth bin counter n 809. Repeat the same procedure till n