FastTrack: A Highly Efficient and Generic GPU-Based Multi-object Tracking Method with Parallel Kalman Filter

Abstract

The Kalman Filter based on uniform assumption has been a crucial motion estimation module in trackers. However, it has limitations in non-uniform motion modeling and computational efficiency when applied to large-scale object tracking scenarios. To address these issues, we propose a novel Parallel Kalman Filter (PKF), which simplifies conventional state variables to reduces computational load and enable effective non-uniform modeling. Within PKF, we propose a non-uniform formulation which models non-uniform motion as uniform motion by transforming the time interval $\Delta t$ from a constant into a variable related to displacement, and incorporate a deceleration strategy into the control-input model of the formulation to tackle the escape problem in Multi-Object Tracking (MOT); an innovative parallel computation method is also proposed, which transposes the computation graph of PKF from the matrix to the quadratic form, significantly reducing the computational load and facilitating parallel computation between distinct tracklets via CUDA, thus making the time consumption of PKF independent of the input tracklet scale, i.e., O(1). Based on PKF, we introduce Fast, the first fully GPU-based tracker paradigm, which significantly enhances tracking efficiency in large-scale object tracking scenarios; and FastTrack, the MOT system composed of Fast and a general detector, offering high efficiency and generality. Within FastTrack, Fast only requires bounding boxes with scores and class ids for a single association during one iteration, and introduces innovative GPU-based tracking modules, such as an efficient GPU 2D-array data structure for tracklet management, a novel cost matrix implemented in CUDA for automatic association priority determination, a new association metric called HIoU, and the first implementation of the Auction Algorithm in CUDA for the asymmetric assignment problem. Experiments show that the average time per iteration of PKF on a GTX 1080Ti is only 0.2 ms; Fast can achieve a real-time efficiency of 250FPS on a GTX 1080Ti and 42FPS even on a Jetson AGX Xavier, outperforming conventional CPU-based trackers. Concurrently, FastTrack demonstrates state-of-the-art performance on four public benchmarks, specifically MOT17, MOT20, KITTI, and DanceTrack, and attains the highest speed in large-scale tracking scenarios of MOT20.

Appendices

Appendix A Naive Auction

Algorithm Algorithm 4 indicates the naive Auction Algorithm. For a cost matrix ${\textbf{C}}$ generated by n persons and m items where m must be greater than or equal to n, we define the following variables to execute the algorithm: a positive scaler $\epsilon$ equal to $\frac{1}{n}$; a bids table ${\textbf{b}}$ initialized to a 2D-array with 0 values and shape $(n + 1, m)$ where ${\textbf{b}}[n,:]$ denotes the flag vector; a person2item mapping $\textbf{p2i}$ initialized to a 1D-array with -1 values and length n; an item2person mapping $\textbf{i2p}$ initialized to a 1D-array with -1 values and length m; a price vector ${\textbf{p}}$ initialized to a 1D-array with 0 values and length m. The algorithm is based on a bidding-assignment loop to solve the best match, and the loop terminates when there is no value − 1 in $\textbf{p2i}$.

Algorithm 4

Pseudo-code of Naive Auction.

In the bidding phase (line 7–14), a temporary vector ${\textbf{t}}$ with length m is first calculated via ${\textbf{C}}[i,:]- {\textbf{p}}$ where $\textbf{p2i}[i] == -1$. For each ${\textbf{t}}$, $bid(\cdot )$ is employed to obtain the max value $x_1$ with its index $x_{idx}$ and the second max value $x_2$. Then the biding increment is computed and set into ${\textbf{b}}[i, x_{idx}]$ (line 11); the flag in ${\textbf{b}}[n, x_{idx}]$ is set to 1 (line 12).

In the assignment phase (line 15–25), for each vector ${\textbf{b}}[:n, j]$ where ${\textbf{b}}[n, j] == 1$, $assign(\cdot )$ is employed to obtain the max value $x_1$ with its index $x_{idx}$. Then $x_1$ is added into ${\textbf{p}}[j]$ (line 18) and a new mapping is established between the $x_{idx}$ person and the j item (line 19–23).

Next, all positions in ${\textbf{b}}$ are reset to 0 values for the next iteration (line 26).

Computation In the CUDA implementation, the bidding phase and the assignment phase are established into two separate kernel functions.

In the bidding kernel function, the grid includes n blocks to obtain the $x_{1/2/idx}$ of different rows in ${\textbf{C}}$ simultaneously. Each block contains $\lceil \frac{m}{2} \rceil$ threads and within each thread, two different values are read from ${\textbf{t}}$ and the CUDA built-in function atomicMax() is employed to obtain the $x_{1/2/idx}$.

In the assignment kernel function, the grid includes m blocks to obtain the $x_{1/idx}$ of different columns in ${\textbf{b}}$ simultaneously. Each block contains $\lceil \frac{n}{2} \rceil$ threads and within each thread, two different values are read from ${\textbf{b}}[:n, j]$ and atomicMax() is also employed to obtain the $x_{1/idx}$.

Appendix B MOT17-val

Table 15 Basic information about the ablation dataset

Fig. 10

Illustration of MOT17-02 in Val Half. FrameXXX denotes the frame number in the video (start from 299 to 600). The solid boxes with same color in different images represent the ground truth of the same trajectory; the small pedestrians in the dashed boxes are also marked as the ground truth even if they are completely invisible (Color figure online)

MOT17 (Milan et al., 2016) contains a train set with the ground truth and a test set without the ground truth. For the ablation study, we define the first half of each video in the original MOT17 train set as the train set of the ablation dataset and the last half as the validation set of the ablation dataset called MOT17-val following (Zhang et al., 2022; Zhou et al., 2020). Table 15 shows the basic information about the ablation dataset. There are seven videos with 5316 images and the detector YOLOX performs both high recall and precision on the seven videos except MOT17-02. As illustrated in Fig. 10, the validation video of MOT17-02 in MOT17-val has a total of 300 images (numbered from Frame299 to Frame469) and the pedestrians in the green dashed boxes are obscured most of the time from Frame299 to Frame469 (a total of 170 frames) while they are stilled labeled as the ground truth even if they are completely invisible. This is the reason why the validation video of MOT17-02 has the lowest recall among all the seven videos. MOT17 has a tendency to label pedestrians that are not visible at all as the ground truth. This is reflected in all seven videos, with MOT17-02 being the most severe, which explains why all recalls in Table 15 are lower than precisions, i.e., the detector cannot detect fully obscured pedestrians who have all ready been labeled as the ground truth. Fortunately, this situation is not serious in the other six validation videos. For this reason, the metric number obtained on video MOT17-02 in the ablation studies would be considered less meaningful and we only use the remaining six videos as MOT17-val in our ablation studies.