Region tracking algorithm

Echoview allows you to track 3D regions in a scene. The region tracking algorithm is based on the Echoview fish tracking algorithm. See Detecting region tracks for information on how to use this algorithm.

The region tracking algorithm consists of:

1. A point creation algorithm - for producing from each 3D region a single point. The remainder of the algorithm tracks these 3D points not regions.
2. A processing algorithm - for ordering and processing the points to be tracked (including the application of Track Acceptance criteria).
   
   The processing algorithm in turn calls upon:
   1. A predictive algorithm - for predicting the next position and velocity of a point on an existing track. The sensitivity to unpredicted changes in position and velocity is controlled by Alpha and Beta.
   2. A gating algorithm - for selecting candidate points for a track based on their proximity to the prediction. A gate volume, based on an exclusion distance (Exclusion distance), is calculated around the predicted point. Points become candidates for a track, if they lie within this volume.
   3. An auction algorithm - for allocating candidate points to tracks. A bidding matrix B is created. The rows of B correspond to open tracks, the columns to the candidate points. Each candidate point and track combination has a bid calculated for it. The bid is a function of the importance of certain variables to the relationship between a track and a point. The importance is expressed in terms of a weight (Weights) for each variable.

Point creation algorithm

A single 3D point is determined for each 3D region (in the specified class). The resulting points are observed, as opposed to predicted.

If possible, this is the calculated center of mass. This calculation requires the specification of an integration algorithm and a variable to integrate. The integration algorithm and variable are specified on the Analysis page of the Scene Properties dialog box.

If no integration algorithm or variable are specified then the calculated geometric center will be used instead.

Each observed point will also receive properties from the 3D region it represents, such that it ultimately has the following four properties:

• position - being the position of the center of mass or the geometric center of the region as described above.
• time - taken to be midway between the valid start time and valid finish time for the 3D region
• volume - being the volume (m3) of the 3D region
• mean Sv - being the mean Sv of the 3D region calculated according to the integration algorithm specified.

Processing algorithm

A list of open tracks is maintained which is initially empty. Each track has the following properties, initially 0 (because there are no points in the track) but kept current as the track grows:

• the position of the last point added to the track
• the time of last point added to the track
• the mean Sv mean of all points in the track (this is a simple arithmetic mean of the individual mean Sv values for each point)
• the mean volume of all points in the track

The observed points are sorted temporally and considered one by one from the earliest to the latest. If more than one point has the same time then these are treated together.

When considering an observed point (or points):

1. All tracks for which the time between the considered point(s) and the last point added exceeds the specified Maximum time gap between regions, are closed.
2. Any track which was closed and contains fewer points than the Minimum number of regions in a track are discarded.
3. If there are open tracks then:
   1. A prediction is made for each open track at the time of the point(s) - using the prediction algorithm. This yields predicted points against which the observed points are be compared.
   2. A gate volume is created around each of the predicted points - using the gating algorithm.
   3. Determine the candidate relationships (between observed points and open tracks). A candidate relationship exists if:
      1. a point lies within the gate volume of a track, and
      2. the  distance between the point and  the last point in the same track does not exceed the specified Maximum distance gap between regions.
   4. Allocate observed points to tracks (i.e. determine which of the candidate relationships will be honored) using the auction algorithm.
      Note: if there is only one candidate relationship then the auction algorithm is not needed, that relationship is honored (i.e. the point is assigned to the track).
4. If there are no open tracks then open a new track for (each of) the point(s).
5. If there are no more observed points, close all tracks and apply the Steps 1, 2 and 3 to all tracks.

Predictive algorithm

The predictive algorithm uses the history of points in an existing track to predict the position of the next point in the track. A prediction is called for whenever a new point is considered during processing and takes place at the time of that new point.

The prediction is made using an Alpha-Beta tracking algorithm as follows.

Positions and velocities are represented as vectors with three orthogonal components (choice of axes has no bearing upon the result).

The position of the predicted point - at the time of the observed point(s) being considered - is determined by calculating each of its three components as follows:

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 in the Track settings section of the Detect Region Tracks dialog
β is the value entered for Beta in the Track settings section of the Detect Region Tracks dialog

Gating algorithm

The gating algorithm defines a volume around any predicted point within which an observed point may lie and be considered acceptable. This volume is spherical with a radius specified by the Exclusion distance.

Auction algorithm

If more than one observed point lies within the gate around a predicted point then the auction algorithm is used to allocate the observed points to tracks most appropriately.

The auction algorithm can be considered to treat the tracks as goods for sale and the points as buyers (or equally well the reverse, if preferred, the outcome is the same).

It proceeds as follows:

1. Each point receives a new property for the purposes of auction management, identifying its last bid (identifying the track and the bid). The last bid is initially null.
2. Establish a list of current bids against each track. One current bid will be maintained for each track. Each current bid is initially zero.
3. Establish a table of maximum bids. Each point will have one maximum bid against each track, determined as follows:
   1. Determine the cost of each track to each point by calculating a weighted sum of normalized costs.
      
      The normalized costs are all between 0 and 1 and are defined as:
       

      Distance cost	=	The distance between the observed point and the predicted point divided by the exclusion distance.
      Time cost	=	The time between the observed point and the last point on the track divided by the maximum of all these differences (for all tracks and points).
      Mean Sv cost	=	The difference between the mean Sv of the point and the mean Sv mean of the track divided by the maximum of all these differences (for all tracks and points).
      Volume cost	=	The difference between the volume of the point and the mean volume of the track divided by the maximum of all these differences (for all tracks and points).

       
      The net cost then is the weighted sum of these costs:
       
      

      cost	=	Distance in space weight × |Distance cost|
      	+	Distance in time weight × |Time cost|
      	+	Mean Sv weight × |Mean Sv cost|
      	+	Volume weight × |Volume cost|

      
      where |x| is the absolute value of x.
   2. If the point is within the gate volume of the track, then
         the maximum bid that a point will place on the track is then the inverse of the cost (of that track to the point): maximum bid = 1 / cost
      otherwise,
         the maximum bid is 0.
4. The points take turns in placing bids on the tracks. The order in which they do this is inconsequential but each point can bid only once before all other points have bid (that is, all points bid once, then all points bid again, then again and so on).
   
   Each point on its turn may place a bid on one track as follows:
   1. Determined the margin on each track as the difference between the current bid on a track and the maximum bid that the point will place on that track: margin = maximum bid - current bid
   2. Determine the margin on the track this point last bid for. This is the last margin.
   3. Determine which track has the highest margin. This is the best margin.
   4. If (and only if) the best margin is significantly better than the last margin: best margin - last margin > epsilon
      then place a bid on the track with the best margin as follows:
      1. Determine which track has the second highest margin. This is the second best margin.
      2. Determine the incremental margin as the best margin minus the second best margin.
      3. Determine the bid by adding to the current bid the incremental margin plus epsilon.
5. The auction is over when all points have stopped bidding.
6. Each track now has added to it the point with the highest bid.

Notes:

• An auction is only required if:
  • there are two or more points with exactly the same time.
  • there are two or more open tracks to which a point may be allocated
• If there is only one point then it will be assigned to the track for which it has the highest maximum bid in step 2.
• If there is only one track it will receive the point which has the highest maximum bid on it in step 2.
• For there to be more than one point in an auction two points (3D regions in a scene) must have exactly the same time as calculated by the point creation algorithm. This is unlikely to happen if detected schools are tracked (it is most likely to occur when using target-locked data).
• Epsilon is an arbitrarily small number which serves only to ensure that there are no equal bids (ties). It is added to all bids when placed, hence the bid creeps up slightly by a factor of epsilon with every bid and margins decrease by the same factor with every bid placed. It is also the criterion for satisfaction - no more bids are placed if the margin cannot be increased by more than epsilon.
• When the Sv value can't be calculated, the Auction Sv cost component is not used.

See also

About region track detection
Detecting region tracks
Fish tracking algorithms
About 3D school detection
About region tracks