Kalman and Optical Flow Tracking

Implementation of KOFT from [9]. It uses Optical-flow enhanced kalman filters to link detections through time. It usually outperforms the Kalman linker with optical-flow.

class byotrack.implementation.linker.frame_by_frame.koft.KOFTLinkerParameters(association_threshold: float = -1.0, *, detection_std: float | Tensor = 0.0, flow_std: float | Tensor = 0.0, process_std: float | Tensor = 0.0, kalman_order: int = 1, n_valid=3, n_gap=3, association_method: str | AssociationMethod = AssociationMethod.SPARSE_OPT_SMOOTH, anisotropy: tuple[float, float, float] = (1.0, 1.0, 1.0), cost: str | Cost = Cost.LIKELIHOOD, track_building: str | TrackBuilding = TrackBuilding.SMOOTHED, split_factor: float = 0.0, merge_factor: float = 0.0, extract_flows_on_detections=False, always_measure_velocity=True, online_process_std=0.0, initial_std_factor=5.0)

Bases: KalmanLinkerParameters

Parameters of KOFTLinker.

Note

Most parameters can be estimated automatically from the detections using estimate.

association_threshold

This is the main hyperparameter, it defines the threshold on the distance used not to link tracks with detections. A low threshold will typically reduce wrong assignments and ID-switches, but may increase track fragmentation. Higher values will reduce track fragmentation, but miss-detected tracks may be linked to a wrong detection. Depending on cost, it is either expressed the maximum Euclidean distance (pixels), or the maximum Mahalanobis distance, or the minimum likelihood (probability). Default: -1.0 (to be estimated, see estimate.)

Type:: float

detection_std

Expected measurement noise (in pixel) on the detection process. The detection process is modeled with a Gaussian noise with this given std. You may provide a different noise for each dimension. See torch_kf.ckf.constant_kalman_filter. Default: 0.0 (to be estimated, see estimate.)

Type:: float | torch.Tensor

flow_std

Expected measurement noise (in pixel) on the optical flow process. The optical flow process is modeled with a Gaussian noise with this given std. You may provide a different noise for each dimension. Default: 0.0 (to be estimated, see estimate)

Type:: float | torch.Tensor

process_std

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

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 of detections required to validate the track after its creation. If a track is missed during its first n_valid frames, it is dropped. This provides robustness to false positive detections. With no false positives, it can be set to 1 (a detection always belongs to a track). Highers values allow to remove non time-consistent false positives, but may prune real tracks that have been miss-detected. Default: 3

Type:: int

n_gap

Number of consecutive frames without any association (miss-detected) before the track termination. This provides robustness to false negative detections. Without any false negatives, it can be set to 0. Higher values allow to support larger gaps in the track, but may lead to wrong assignments. 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: SPARSE_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. Note that it will only impact EUCLIDEAN[_SQ] costs; for probabilistic cost, anisotropy should be already integrated within 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. See CostMethod. It can be provided as a string. Choice: EUCLIDEAN, EUCLIDEAN_SQ, MAHALANOBIS, MAHALANOBIS_SQ, LIKELIHOOD. This also defines the unit of association_threshold (in pixels for Euclidean, no units for Mahalanobis, and a probability for likelihood). Default: LIKELIHOOD

Type:: CostMethod

track_building

How the linker will build the final tracks. See TrackBuilding. Either from detections, or from filtered/smoothed positions computed by the Kalman filter. It can be provided as a string. Choice: DETECTION, FILTERED, SMOOTHED. Default: SMOOTHED

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

extract_flows_on_detections

If True it extracts the optical flow at the detection location if possible. Otherwise it extract the flow from the current estimate of the track position. Default: False

Type:: bool

always_measure_velocity

Update velocity for all tracks even non-linked ones. If set to False, it implements KOFT– from the paper. This is sub-optimal, you should keep it True. Default: True

Type:: bool

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. Typical values lies between 3.0 to 100.0. Default: 5.0

Type:: float

check(): Check the specification for invalid values.

estimate(detections_sequence: Sequence[byotrack.Detections]) → KOFTLinkerParameters

Estimate parameters from the given detections.

Estimation is triggered by providing negative dummy values for positive parameters. The dummy values are then replaced by their estimate.

Estimators:

detection_std: average_radius / 2 (i.e. localization is rarely predicted outside the target)
process_std: average_radius (i.e. unmodeled motion is ~the size of targets) (Consider using estimate_process_std_from_tracks)
flow_std: average_radius (i.e. the flow can be wrong up to twice the target size) (Consider using estimate_flow_std_from_tracks)
association_threshold: steady_state_covariance * 3 (See estimate_association_threshold).
anisotropy: Computed from statistics.anisotropy.
split_factor: 1.0 if the number of detection increase by more than 30% over the full sequence.
merge_factor: 1.0 if the number of detection decrease by more than 30% over the full sequence.

Parameters:: detections_sequence (Sequence[byotrack.Detections]) – Detections for the current sequence.
Returns:: self with updated parameters.
Return type:: KOFTLinkerParameters

estimate_flow_std_from_tracks(video: Sequence[np.ndarray] | np.ndarray, optflow: byotrack.OpticalFlow, tracks: Collection[byotrack.Track], quantile: float = 0.99993) → None

Estimate flow_std based on the errors made by the flow versus ground-truth tracks.

Modify in place flow_std. It sets the flow_std so that it fits with the maximum flow errors on the annotations.

NOTE: Without annotations, you may set the flow_std according to the following method:: Manually check how the flow moves over your targets (see InteractiveFlowVisualizer) and estimate a coarse maximum error (in pixel) between two consevutive frames. Then flow_std can be set as this maximum error divided by 4.

Parameters:

video (Sequence[np.ndarray] | np.ndarray) – Sequence of T frames (array) on which to measure the flow_std. Each array is expected to have a shape ([D, ]H, W, C).
optflow (byotrack.OptFlow) – Optical flow algorithm that will be used in KOFT. The flow_std will be measured for this optical flow.
tracks (Collection[byotrack.Track]) – Partial ground-truth tracks. If these are manually annotated tracks, consider using a RTSSmoother to reduce the annotation noise.
quantile (float) – Quantile to extract the maximum value. Can be reduced to ignore some false positive links. Default: 0.99993

build_filter(dim: int) → KalmanFilter

Build the Kalman filter used by the Linker.

See torch_kf.ckf.constant_kalman_filter.

class byotrack.implementation.linker.frame_by_frame.koft.KOFTLinker(specs: KOFTLinkerParameters, optflow: OpticalFlow | None = None, features_extractor: FeaturesExtractor | None = None, *, save_all=False)

Bases: KalmanLinker

Kalman and Optical Flow Tracking [9].

Motion is modeled with a Kalman filter of a specified order >= 1 (See torch_kf.ckf) Positions are measured through the detection process. A second update step is performed to measure the velocity of all tracks using optical flow.

Matching is done to optimize the given cost.

See KalmanLinker for the other attributes.

specs

Parameters specifications of the algorithm. See KOFTLinkerParameters.

Type:: KOFTLinkerParameters

last_detections

The last detections used in update. Optionally used to extract flows at the detection positions and not the track state. Required for motion_model

Type:: byotrack.Detections

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

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 | None, 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 | None) – The current optional 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 | None, 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 | None) – The optional 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