Fish tracking algorithm
Echoview's Alpha-Beta tracking algorithm
Acknowledgments and references
Tim Mulligan who provided us with algorithm information and copies of Polaris and ABTrack, which he and Peter Withler developed.
Blackman, S.S., Multiple-target tracking with radar applications, Artech House, 1986.
Bertsekas, D.P., "The auction algorithm for assignment and other network flow problems: A tutorial". Interfaces 20:4 July- August 1990 pp. 133-149.
Implementation
The implementation can be described by three consecutive processes:
-
Algorithm: the identification of single targets as candidates for appending to a track
-
Weights: the weighting and allocation of candidates to a track
-
Track acceptance: the acceptance of tracks against a set of track criteria
Candidature
Echoview's α-β Fish Tracker implements a fixed coefficient filtering method as presented in Blackman (1986). The filtering process selects out single targets as candidates for appending to a track. The algorithm is applied to either split or single beam data from a single target detection process. These are implemented as the 4D and 2D algorithms for split beam data (i.e. targets with range, angles and time) and single beam data (i.e. targets with range and time), respectively.
The sensitivity of the tracker to unpredicted changes in position and velocity is controlled by Alpha and Beta, respectively. These parameters are used in the prediction of a track's location at the time of the current ping. The filter gains are applied independently to the prediction of each of the spatial components (distance_minor_axis, distance_major_axis and range).
Processing is ping by ping and all open tracks (those that still may have targets appended to them) are used for determining candidates from the set of single targets in the ping being processed. A single target is considered as a candidate for appending to a track if it is within a volume or target gate ellipsoid centered about the predicted location of a track.
The exclusion distances from the predicted location along each axis define the gate. Since the target detection probability may be less than one, an expansion factor can be applied to the target gate - where no target from the echo of the previous ping was appended to the track. The expansion factor is repeatedly added to the gate when consecutive echoes contribute no targets to a track.
Echoview calculations use single target positions in transducer-relative coordinates; however, these are calculated from Earth-relative coordinates and therefore account for platform motion (as per the GPS fixes, heave, motion correction, etc).
Track detection parameters
Following Blackman, Alpha and Beta (as entered on the Algorithm page of the Track Detection Properties dialog box) are used to calculate a predicted point Xp such that:
Xpi = Xsi-1 + Vsi-1 (ti - ti-1) for i > 0 Xsi = Xpi + α (Xoi - Xpi) for i > 0 Vsi = Vpi + β (Voi - Vpi) for i > 0 Voi = (Xoi - Xsi-1) / (ti - ti-1) for i > 0 Vpi = (Xpi - Xsi-1) / (ti - ti-1) for i > 0 Xp0 = Xs0 = Xo0 Vp0 = Vs0 = Vo0 = 0 where:
i is the number of a point in the track, from 0 up.
Xpi is the predicted position component of point i in the track
Xsi is the smoothed (predicted) position component of point i in the track
Xoi is the observed position component of point i in the track
Vpi is the predicted velocity component of point i in the track
Vsi is the smoothed (predicted) velocity component of point i in the track
Voi is the observed velocity component of point i in the track
ti is the time of point i in the track
α is the value entered for Alpha on the Algorithm page of the Track Detection Properties dialog box
β is the value entered for Beta on the Algorithm page of the Track Detection Properties dialog box
Positions and velocities are represented as vectors with three orthogonal components (range, minor-axis and major axis directions), and α and β are specified independently for each of these components on the Algorithm page of the Track Detection Properties dialog box.
Target gate parameters
The parameters marked in bold below are all settings.
These parameters are used to calculate the gating volume within an ellipsoid (defined by the surface x,y,z) centered at the predicted point as follows:
where:
a = exclusion distance along the major-axis axis
b = exclusion distance along the minor-axis axis
c = exclusion distance along the range axis
x p is a component along the major axis of the predicted point
yp is a component along the minor axis of the predicted point
zp is a component along the range axis of the predicted point
The missed ping expansion enables you to apply an expansion percentage (0-100) to the gated volume when no single targets were allocated to a track from the echo of the previous ping or sequence of pings as follows:
In general, for a gate with n missed pings:
xn = xo (1 + n × missed ping expansion / 100)
where:
xn = the effective exclusion distance used after n missed pings (m)
xo = the exclusion distance - a, b, or c above (m)
Weighting and the allocation of candidate targets to a track
Once identified as a candidate, a target is assigned a measure which determines the track allocation process. The measure depends on weighted component distances from the predicted location, and the TS and ping gap difference to the last target in the track as entered into the Weights page of the Track Detection Properties dialog box. The weighted components are accumulated and used in the Auction algorithm, which then assigns targets to a track. Unallocated single targets are used to initiate new tracks.
The effect of the individual weights on the allocation process is determined by their relative magnitude, so the following two groups of settings, A and B, are equivalent:
|
Weight parameter |
Setting value Group A |
Setting value Group B |
|
|
Major axis |
Wx |
30 |
0.6 |
|
Minor axis |
Wy |
30 |
0.6 |
|
Range |
Wz |
40 |
0.8 |
|
TS |
WTS |
0 |
0 |
|
Ping gap |
WPG |
0 |
0 |
The weight parameters in the table above are all settings on the Weights page of the Track Detection Properties dialog box.
Calculation of the weights
A parameter d' 2 is calculated for each possible single target combination, and used to determine the allocation of single targets to tracks, as follows for non-zero valued weights:
if the weights are set to 1, 1, 1, 0 and 0 respectively then d' 2 is equivalent to the non-dimensional "distance squared" (d2) defined by Blackman such that:
where
a = exclusion distance along the major axis = σx
b = exclusion distance along the minor axis = σy
c = exclusion distance along the range axis (i.e., the acoustic axis) = σz
and d 2 = d' 2. The single target is allocated to the track which minimises the score function, d' 2.
Track acceptance
Once the allocation process is completed all tracks are filtered according to the track acceptance criteria entered on the Track acceptance page of the Track Detection Properties dialog box. A track is closed once the maximum ping gap is exceeded. Closed tracks are tested against the criteria for both the minimum number single targets and pings.
A track must contain at least the Minimum number of single targets and the Minimum number of pings, but may not contain ping gaps that exceed the Maximum gap between single targets.