Kalman Linker

Implementation of SKT from [9]

class byotrack.implementation.linker.frame_by_frame.kalman_linker.Cost(*values)

Bases: Enum

The cost to use for association.

LIKELIHOOD
Build the cost matrix to maximize the likelihood of the association. The cost is defined as: the negative log likelihood that the detections j is from track i. C[i, j] = - log P(det_j | track_i) The cost limit is expected to be the smallest probability to accept.
MAHALANOBIS
Mahalanobis distance, using the track uncertainty to correct the euclidean distance. The cost limit is expected to be the largest Mahalanobis distance to accept.
MAHALANOBIS_SQ
Squared Mahalanobis distance. The cost limit is expected to be the largest Mahalanobis distance to accept. (not squared)
EUCLIDEAN
Euclidean distance. The cost limit is expected to be the largest Euclidean distance to accept.
EUCLIDEAN_SQ
Squared euclidean distance. The cost limit is expected to be the largest Euclidean distance to accept. (not squared)

class byotrack.implementation.linker.frame_by_frame.kalman_linker.TrackBuilding(*values)

Bases: Enum

How to build the final tracks.

DETECTION
Build tracks from detections without filtering nor filling gaps
FILTERED
Build tracks from the Kalman filter outputs
SMOOTHED
Add a backward run of the Kalman filter (RTS) to smooth tracks position

class byotrack.implementation.linker.frame_by_frame.kalman_linker.KalmanLinkerParameters(association_threshold: float = 5.0, *, detection_std: float | Tensor = 3.0, process_std: float | Tensor = 1.5, kalman_order: int = 1, n_valid=3, n_gap=3, association_method: str | AssociationMethod = AssociationMethod.OPT_SMOOTH, anisotropy: tuple[float, float, float] = (1.0, 1.0, 1.0), cost: str | Cost = Cost.EUCLIDEAN, track_building: str | TrackBuilding = TrackBuilding.FILTERED, split_factor: float = 0.0, merge_factor: float = 0.0, online_process_std: float = 0.0, initial_std_factor: float = 10.0)

Bases: FrameByFrameLinkerParameters

Parameters of KalmanLinker.

Note

The merging and splitting features is still experimental.

association_threshold

This is the main hyperparameter, it defines the threshold on the distance used not to link tracks with detections. It prevents to link with false positive detections. Default: 5 pixels

Type:: float

detection_std

Expected measurement noise on the detection process. The detection process is modeled with a Gaussian noise with this given std. (You can provide a different noise for each dimension). See torch_kf.ckf.constant_kalman_filter. Default: 3.0 pixels

Type:: float | torch.Tensor

process_std

Expected process noise. See torch_kf.ckf.constant_kalman_filter, the process is modeled as constant order-th derivative motion. This quantify how much the supposedly “constant” order-th derivative can change between two consecutive frames. A common rule of thumb is to use 3 * process_std ~= max_t(| dx^(order)(t+1) - dx^(order)(t)|). It can be provided for each dimension). Default: 1.5 pixels

Type:: float | torch.Tensor

kalman_order

Order of the Kalman filter to use. 0 for brownian motions, 1 for directed brownian motion, 2 for accelerated brownian motions, etc… Default: 1

Type:: int

n_valid

Number associated detections required to validate the track after its creation. Default: 3

Type:: int

n_gap

Number of consecutive frames without association before the track termination. Default: 3

Type:: int

association_method

The frame-by-frame association to use. See AssociationMethod. It can be provided as a string. (Choice: GREEDY, OPT_HARD, OPT_SMOOTH, SPARSE_OPT_HARD, SPARSE_OPT_SMOOTH) Default: OPT_SMOOTH

Type:: AssociationMethod

anisotropy

Anisotropy of images (Ratio of the pixel sizes for each axis, depth first). This will be used to scale distances. It will only impact EUCLIDEAN[_SQ] costs. For probabilistic cost, anisotropy should be already integrated in the stds of the kalman filter (providing one std for each dimension). Default: (1., 1., 1.)

Type:: tuple[float, float, float]

cost_method

The cost method to use. It can be provided as a string. See CostMethod. It also indicates what is the correct unit of association_threshold. Default: EUCLIDEAN

Type:: CostMethod

track_building

Tells the linker how to build the final tracks. Either from detections, or from filtered/smoothed positions computed by the Kalman filter. See TrackBuilding. It can be provided as a string. Default: FILTERED

Type:: TrackBuilding

split_factor

Allow splitting of tracks, using a second association step. The association threshold in this case is split_factor * association_threshold. Default: 0.0 (No splits)

Type:: float

merge_factor

Allow merging of tracks, using a second association step. The association threshold in this case is merge_factor * association_threshold. Default: 0.0 (No merges)

Type:: float

online_process_std

Recomputes the process std online following “A. Genovesio, et al, 2004, October. Adaptive gating in Gaussian Bayesian multi-target tracking. ICIP’04. (Vol. 1, pp. 147-150). IEEE.” Each track has its own process std depending on the errors made in the past. It automatically adjusts to process errors, allowing to increase the validation gate. Should be used in conjunction with MAHALANOBIS or LIKELIHOOD cost_method. As this may be detrimental, it is disabled by default. Default: 0.0 (Process_std is constant)

Type:: float

initial_std_factor

The uncertainties on initial velocities/accelerations are set to initial_std_factor * process_std. See KalmanLinker.build_initial_covariance. Having a small factor will prevent handling correctly starting tracks with large initial velocity on their first frames. But large values will lead to large uncertainty on the first prediction, making it hard to associate to a detection with MAHALANOBIS or LIKELIHOOD methods. Typical values lies between 3.0 to 10.0. Default: 10.0

Type:: float

class byotrack.implementation.linker.frame_by_frame.kalman_linker.KalmanLinker(specs: KalmanLinkerParameters, optflow: OpticalFlow | None = None, features_extractor: FeaturesExtractor | None = None, *, save_all=False)

Bases: FrameByFrameLinker

Frame by frame linker using Kalman filters.

Motion is modeled with a Kalman filter of a specified order (See torch_kf.ckf) Matching is done to optimize the given cost. If optical flow is provided, it is used online to warp the predicted state positions of the kalman filter. This will work, but it is sub-optimal: consider using KOFTLinker that exploits in a finer way optical flow inside Kalman filters.

This is an implementation of Simple Kalman Tracking (SKT) from KOFT [9].

See FrameByFrameLinker for the other attributes.

specs

Parameters specifications of the algorithm. See KalmanLinkerParameters.

Type:: KalmanLinkerParameters

kalman_filter

The Kalman filter.

Type:: torch_kf.KalmanFilter

active_states

The Kalman filter estimation for each track. Shape: mean=(N, D * (order + 1), 1), covariance=(N, D * (order + 1), dim * (order + 1)) dtype: float

Type:: torch_kf.GaussianState

projections

The Kalman filter projection for each track. Shape: mean=(N, D, 1), covariance=(N, D, D), precision=(N, D, D) dtype: float

Type:: torch_kf.GaussianState

process_noises

The Kalman filter process noise for each track. Only used when online_process_std > 0.0. It allows to compute an adaptative process_std and therefore gating for each track. Shape: (N, D, 1), dtype: float

Type:: torch.Tensor

all_states

The Kalman filter estimation for each track at each seen frame. States are only registered when save_all=True or if you build tracks from RTS smoothing. Shape: mean=(N, D * (order + 1), 1), covariance=(N, D * (order + 1), dim * (order + 1)) dtype: float

Type:: list[torch_kf.GaussianState]

reset(dim=2) → None

Reset the linking algorithm.

Flush all data stored from a previous linking and prepare a new linking.

Parameters:: dim (int) – The dimension of the data. Default: 2

collect() → list[Track]

Collect and build all the tracks up to the last given frame.

Returns:: Tracks from the last reset to the last given frame.
Return type:: Collection[byotrack.Track]

motion_model() → None

Optional modelisation of motion for tracks.

It can be used to update some internal state of the tracker after the optical flow computation and before the distance computation.

cost(frame: np.ndarray, detections: byotrack.Detections) → tuple[torch.Tensor, float]

Compute the association cost between active tracks and detections.

It also returns the threshold to use (Depending on the dist you use, association_threshold could be related to a more meaning full quantity than the cost itself). For instance, when using a squared Euclidean distance, the association threshold could be express as the distance in pixel, and this function could square it. For likelihood association, you could provide the association threshold as a probability and use -log(threshold) as the true threshold. (See KalmanLinker and NearestNeighborLinker)

Parameters:

frame (np.ndarray) – The current frame of the video Shape: (H, W, C), dtype: float
detections (byotrack.Detections) – Detections for the given frame

Returns:

The cost matrix between active tracks and detections: Shape: (n_tracks, n_dets), dtype: float
float: The association threshold to use.: It can be different than self.association_threshold depending on the dist build here

Return type:

torch.Tensor

post_association(frame: np.ndarray, detections: byotrack.Detections, active_mask: torch.Tensor) → None

Update the internal state of the tracker after update_active_tracks.

It should update any internal model/data. It is also responsible to register the position of each active track in all_positions for the current time frame.

Parameters:

frame (np.ndarray) – The current frame of the video Shape: (H, W, C), dtype: float
detections (byotrack.Detections) – Detections for the given frame
active_mask (torch.Tensor) – Boolean tensor indicating True for still active tracks Shape: (N_tracks), dtype: bool

build_initial_covariance(dim: int) → Tensor

Build the diagonal initial covariance matrix.

The position is initially unknown, leading to a belief (given by the first detection) set to the position of the first detection, with detection_std uncertainty.

The velocity (and higher order derivatives) are assumed to be 0.0 with a relatively high uncertainty: initial_std_factor * process_std.

Note that having a large initial_std_factor (>10) may decrease performances, as the first prediction will be impacted and largely uncertain, leading to low probabilities for every associations. In KOFT, as the velocity is measured before the first prediction, the initial_std_factor can be increased to reduce this bias toward a nul initial velocity. We found that initial_std_factor=0.0 is a good trade off in practice.