Frame By Frame Linkers

Base class for frame by frame linkers. The current implementation follows the tracks handling strategy proposed in KOFT [9].

class byotrack.implementation.linker.frame_by_frame.base.AssociationMethod(value)

Bases: Enum

Association methods (Greedy or Jonker-Volgenant)

  • GREEDY

    Select the best match between tracks and detections iteratively until no match can be selected below the cost limit eta. It is usually not optimal for tracking but it is much faster.

  • OPT_HARD

    Solve the linear association problem (see pylapy). Hard threshold the association matrix with the cost limit eta.

  • OPT_SMOOTH

    Solve a cost_limit extended association problem (see pylapy) It relaxes the linear association problem, allowing to not link a node for the cost limit eta.

solve(cost: Tensor, eta: float = inf) → Tensor

Solve tracks-to-detections association

Parameters:

  • cost (torch.Tensor) – Cost matrix Shape: (N, M), dtype: float

  • eta (float) – Cost limit Default: inf (No thresholding)

Returns:

Links (i, j)

Shape: (L, 2), dtype: int32

Return type:

torch.Tensor

class byotrack.implementation.linker.frame_by_frame.base.TrackHandler(n_valid: int, n_gap: int, start: int, identifier: int)

Bases: object

Handle a track during the tracking procedure

It accumulates the track data at each new association and store the optional motion model data.

A TrackHandler is created for each unlinked detections in the linking process and then updated with the following associated detections. At the beginining, the track is considered HYPOTHETICAL. For a track to be considered valid, it requires n_valid consecutive associated detections after the track creation (state: HYPOTHETICAL => VALID). It a miss detection occurs during this time interval, then the track is deleted and considered invalid (state: HYPOTHETICAL => INVALID).

Once confirmed, a VALID track is resilient to miss detections, waiting n_gap frames before ending the track (VALID => FINISHED).

n_valid

Number of frames with a correct association required to validate the track at its creation.

Type:

int

n_gap

Number of frames with no association before the track termination.

Type:

int

start

Starting frame of the track

Type:

int

identifier

Identifier of the track handler (and of the track)

Type:

int

track_state

Current state of the handler

Type:

TrackState

last_association

Number of frames since the last association

Type:

int

detection_ids

Identifiers of the associated detection (-1 if None)

Type:

List[int]

track_ids

Index of the track at each frame in the linker.active_tracks list. It allows the linker to store data as tensor and be able to rebuild tracks at the end.

Type:

List[int]

class TrackState(value)

Bases: IntEnum

TrackState of a TrackHandler

  • HYPOTHETICAL

    Initial state before validation of the track.

  • VALID

    The track has been validated and is still active

  • FINISHED

    The track is valid and finished

  • INVALID

    The track is not valid and deleted

update(frame_id: int, detection_id: int) → None

Update track handler. It stores the detection_id and update the track state.

It should be called for each time frame and each active track.

Parameters:

  • frame_id (int) – The current frame. This is given for safety checks to ensure that the Linker and TrackHandler agree.

  • detection_id (int) – Detection id in the Detections object. -1 if not associated to a particular detection.

register_track_id(track_id: int) → None

For still active tracks, it registers the track id after the update step.

Parameters:

track_id (int) – The index of the track in linker.active_tracks at this time frame.

class byotrack.implementation.linker.frame_by_frame.base.OnlineFlowExtractor(optflow: OpticalFlow)

Bases: object

Extract optical flow maps online from a video

reset() → None

Reset the flow extractor

update(frame: ndarray) → None

Extract the flow for a new given frame

It will compute and register the flow map between the last given frame and the current frame.

Parameters:

frame (np.ndarray) – Current frame of the video

class byotrack.implementation.linker.frame_by_frame.base.FrameByFrameLinkerParameters(association_threshold: float, n_valid=3, n_gap=3, association_method: str | AssociationMethod = AssociationMethod.OPT_SMOOTH)

Bases: object

Parameters of the abstract FrameByFrameLinker

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.

Type:

float

n_valid

Number of frames with a correct association required to validate the track at its creation. Default: 3

Type:

int

n_gap

Number of frames with no 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) Default: OPT_SMOOTH

Type:

AssociationMethod

class byotrack.implementation.linker.frame_by_frame.base.FrameByFrameLinker(specs: FrameByFrameLinkerParameters, optflow: OpticalFlow | None = None, features_extractor: FeaturesExtractor | None = None, save_all=False)

Bases: OnlineLinker

Links detections online using frame-by-frame association

Abstract class for frame-by-frame linker. It decomposes the update step in 5 parts:

  1. Optional optical flow computations (Handled by this class)

  2. Motion modeling to predict track positions (motion_model)

  3. Track-to-detection cost computation (cost)

  4. Solving the linear association problem (Handled by this class)

  5. Post matching update to handle tracks (post_association)

The association relies on the AssociationMethod enum and tracks handling is done with TrackHandler.

It follows the tracks handling strategy describe in KOFT [9].

specs

Parameters specifications of the algorithm. See FrameByFrameLinkerParameters.

Type:

FrameByFrameLinkerParameters

optflow

Optional wrapper around the given optional OpticalFlow that will extract flow maps of the video online. (The underlying OpticalFlow object is accessible in self.optflow.optflow) Default: None

Type:

Optional[OnlineFlowExtractor]

features_extractor

Optional features extractor that will extract features for the detections, which could be useful for tracking. Default: None

Type:

Optional[FeaturesExtractor]

save_all

Save metadata useless for the final building of tracks but that could be useful for analysis. For instance, it will keep invalid tracks. Or the computed features inside the Detections objects.

Type:

bool

frame_id

Current frame id of the linking process

Type:

int

inactive_tracks

Terminated tracks

Type:

List[TrackHandler]

active_tracks

Current track handlers

Type:

List[TrackHandler]

all_positions

Positions of the active tracks at each seen frames. Using the valid track handlers track_ids, it allows the reconstruction of tracks.

Type:

List[torch.Tensor]

reset() → None

Reset the linking algorithm

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

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]

abstract 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.

abstract cost(frame: ndarray, detections: Detections) → Tuple[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: float32

float: The association threshold to use.

It can be different than self.association_threshold depeding on the dist build here

Return type:

torch.Tensor

abstract post_association(frame: ndarray, detections: Detections, links: Tensor)

Update the tracks and the internal variables of the tracker

It should call the update method of each active tracks and update any internal model/data. It should also create new track handlers for each extra detection. Finally, 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

  • links (torch.Tensor) – The links made between active tracks and the detections Shape: (L, 2), dtype: int32

update_active_tracks(links: Tensor) → Tensor

Calls update for active tracks and return a boolean mask that indicates which track is still active

Tracks that are terminated are stored inside inactive_tracks and dropped from active_tracks.

It can be called inside post_association to simplify the code.

Parameters:

links (torch.Tensor) – The links made between active tracks and the detections Shape: (L, 2), dtype: int32

Returns:

Boolean tensor indicating True for still active tracks

Return type:

torch.Tensor

handle_extra_detections(detections: Detections, links: Tensor) → Tensor

Handle extra detections by creating new track handlers

It can be called inside post_association to create track handlers from extra detections. It will return the extra detections positions and ids to be further used by post_association.

Parameters:

  • detections (byotrack.Detections) – Detections for the given frame

  • links (torch.Tensor) – The links made between active tracks and the detections Shape: (L, 2), dtype: int32

update(frame: ndarray, detections: Detections) → None

Progress in the linking step by one frame

Will update the internal algorithm by a single frame and its detections.

Parameters:

  • frame (np.ndarray) – Frame of the video Shape: (H, W, C), dtype: float

  • detections (byotrack.Detections) – Detections for the given frame

byotrack.implementation.linker.frame_by_frame.greedy_lap.greedy_assignment_solver(dist: ndarray, eta: float = inf)

Solve assignement problem in a greedy way

Iteratively select the minimum cost, then deleting its row/column.

Stops when the cost matrix is empty (no more rows or columns) or if the selected cost is higher than eta

Parameters:

  • dist (np.ndarray) – Distance matrix Shape: (N, M), dtype: float

  • eta (float) – Hard thresholding Default: inf (No thresholding)

Returns:

Links (i, j)

Shape: (L, 2), dtype: uint16

Return type:

np.ndarray