AutoTrajectory: Label-free Trajectory Extraction and Prediction from Videos using Dynamic Points

Classical model-based approaches for trajectory prediction [25, 2, 18, 28] focus on the inherent motion regularities of objects themselves. However, the motion of dynamic objects in the real world is diverse and can be governed by many factors, like neighboring objects’ motion states and the environment. These methods are limited in modeling complex scenarios. Recently, RNN and its variant LSTM have achieved great success in modeling sequence prediction tasks [31, 6]. Based on these basic networks, many prediction approaches have outperformed classical methods in real-world benchmarks [1, 17, 24, 33, 29, 9, 8, 43, 39, 7, 38, 48, 32, 44]. However, these supervised methods require large-scale, well-annotated trajectory data. Two main ways to generate the data are labeling moving instances from fixed-view videos and LiDAR point clouds. Both ways are expensive and time-consuming. Even though there are a lot of videos captured by street or commodity cameras, they cannot be used to improve the prediction performance without annotation. We try to solve this problem by using unsupervised manners.

Except for manual labeling, another possible solution for getting trajectories from videos is using current SOTA trackers. However, most modern trackers follow the tracking-by-detection paradigm [5, 4, 13, 40, 42, 49, 46]. The performance depends largely on the detector used to find the objects as the tracking targets and the detector requires large-scale labeled data. Besides, the tracker is always trained for fixed-categories, which is hard to adapt to other domains. Recent trend in multi-object tracking is combining both detection and tracking in one framework[15, 37, 3]. However, they do not overcome the above limitations. Our approach focuses on exploring the nature of video, i.e., the dynamic information, which is naturally category-free and works well on all domains.

To extract trajectories from sequential frames, a crucial step is learning the motion dynamics of the video. Many works have explored unsupervised methods for dynamic modeling for videos to solve different problems [27]. Based on keypoint-based representation [20], the video prediction approach [30] could decouple pixel generation from dynamic prediction.  [21] combines keypoints and extra action classes to help generate action conditioned image sequences. Inspired by the function of keypoint on video prediction and generation, we designed dynamic point. For unsupervised tracking, unsupervised single object tracking is the mainstream [36, 47, 45]. However, they cannot handle the scenes with multiple objects. For unsupervised multi-object tracking, the pioneering work AIR [12] proposes a VAE-based framework to detect objects from individual images through inference, which is followed by [22, 19].  [11] makes use of spatially invariant computations and representations to exploit the structure of objects in videos. In our initial attempts, we applied these unsupervised methods to locate dynamic instances on pedestrian videos directly but got poor results. The primary reason is that the above methods rely on structure and appearance features of objects, which are not applicable for trajectory extraction from bird’s-eye view videos, where the these features are not very obvious.

Given raw videos without any annotations, our task is to obtain a trajectory predictor in an unsupervised manner. We solve this problem by two main steps: trajectory extraction and trajectory prediction. For trajectory extraction, the input is raw videos captured by street cameras, and the output is $R=\left\{r_{1},r_{2},...,r_{n}\right\}$, where $R$ denotes all trajectories of moving objects in the videos. The trajectory for the $i$th object is defined as a set of discrete positions in the real-world coordinate system: $r_{i}=\left\{p_{i}^{t_{start}},p_{i}^{t_{start}+1},...,p_{i}^{t_{end}}\right\}$, where $[t_{start},t_{end}]$ denotes the time interval when the object occurs in the video. For the trajectory prediction, the extracted trajectories $R$ acts as the dataset for training and validating the prediction network. The predictor observes objects’ trajectories of an time interval and predicts their trajectories in the following period, like observing trajectory of 3s and predicting the trajectory for the next 5s. Without any label, we finally compute a trajectory prediction predictor.

We propose a label-free pipeline to generate the trajectory and then train the trajectory predictor. Specifically, our approach consists of four components: Dynamic-Point Modeling, Dynamic-to-Instance Aggregation, Instance Matching, and Trajectory Prediction. The first three parts form the unsupervised trajectory extraction. We show the pipeline in Fig. 1. In what follows, we will present these components in details.

This part performs the unsupervised discovery of the dynamic points. Given a sequence of images, including Image₁ ($I_{1}$), Image_t-1 ($I_{t-1}$), Image_t ($I_{t}$), and Image_t+1 ($I_{t+1}$), our objective is to capture $K$ pixel locations, namely dynamic points $\Phi\in\mathbb{R}^{K\times 2}$, which correspond to the locations of moving regions in $I_{t}$.

The detailed networks are shown in Fig. 1(1). The first image provides the background and layout features. Two pairs of consecutive images are used to capture the dynamic points in $I_{t}$. Both background features and the dynamic-point gaussian heatmaps are used to reconstruct the image ($I_{t}$). The learning objective $\mathcal{L}$ then consists of two parts, consistency loss $\mathcal{L}_{C}$ and reconstruction loss $\mathcal{L}_{R}$, to regularize the dynamic points extraction and image reconstruction, respectively. The total objective is formulated as $\mathcal{L}=\mathcal{L}_{R}+\beta\mathcal{L}_{C}$.

Dynamic points could detect dynamic locations on images, while trajectories originate from instances. After acquiring the well-trained dynamic-point extractor in the previous step, we aim to group these dynamic points to get the instance-level location information. Intuitively, the solution is to cluster the dynamic points to instance points directly. However, the dynamic points have some characteristics: it shows better instance-level information (distinguishing different objects well) when multiple objects are close to each other while shows loose when solo object occurs.

We tackle this problem by introducing the optical flow into the instance-level information collection. An example of the dynamic points and optical flow is shown in Fig. 2. We can observe that the dynamic points correspond to a better instance-level representation, when multiple objects are in close proximity (solid green circles in (b)). The optical flow shows the compact representation for solo objects (solid green circle in (c)). It shows that that dynamic points and optical flow are complementary.

Specifically, we use a pair of consecutive images ($I_{t}$ and $I_{t-1}$) to extract the dynamic point representation and optical flow, training the dynamic-point extractor in step 1 and applying unsupervised optical flow method [14]. The gaussian heatmaps are upsampled to the original image size via bilinear interpolation. Then both gaussian heatmaps and optical flow are concatenated as the input to the clustering method, i.e. mean-shift, to get the cluster centers, which are the coordinates of objects.

The instance points obtained from the clustering method are independent across time. To obtain the trajectory, we perform cross-time instance matching. The basic idea is to establish a cost matrix between two consecutive images where each entry indicates the distance between two instance points across two images. Then we apply the Kuhn-Munkres (KM) algorithm ^††http://software.clapper.org/munkres/ to calculate the minimum-cost matching. To better incorporate the appearance feature, we also use the RGB information as a part of distance. The final distance function is designed as $\mathcal{D}_{ij}=dist(P_{i},Q_{j})+\lambda rgb(P_{i},Q_{j})$, where $P_{i}$ and $Q_{j}$ are two instance points from two images. $dist(\cdot)$ is the Euclidean distance and $rgb(\cdot)$ is the L1 distance.

Specifically, the cost matrix $\mathcal{C}\in\mathbb{R}^{M\times N}$ is defined as the all-to-all distance between two images, where $M$ and $N$ indicate the number of instance points in two images. We use the KM algorithm with the cost matrix $\mathcal{C}$ to get the minimum-cost matching. The workflow is shown in Fig. 3. The matching pair from the KM algorithm is specified as a true pair if its distance is less than the pre-defined threshold $\mathbb{D}$, otherwise it is a false pair. Note that there exist some outliers that do not match any point. We label these outliers with blue circles. To handle these points, we apply some specific methods to filter them. For the points in image $T$, if we cannot find the former matching points in image $T-1$ but can find the matching points in image $T+1$, we label these points as the starting points of the sequence, otherwise we label them as outliers. This bidirectional filter benefits the precision of cross-time matching.

After extracting the trajectories in the pixel coordinate system, we transfer them to the real-word coordinate system and use them as the dataset to train and validate the prediction network in the last stage. At any time $t$, the status for the $i$th dynamic instance can be represented as the location $p_{i}=(x_{i}^{t},y_{i}^{t})$. The task for the prediction network is to observe the status of all the dynamic instances in the time interval $[1:T_{obs}]$ and then predict their discrete positions at $[T_{obs}+1:T_{pred}]$. We have highlighted many learning-based works in Section 2.1 and these methods can be directly used in our approach. Because the datasets we use are human crowd videos, we utilize some classical LSTM-based approaches for pedestrian trajectory prediction in our experiments to verify the effectiveness of our unsupervised method.

In the proposed approach, dynamic-point modeling and trajectory prediction stages have trainable parameters, and the other two stages are non-parametric. The whole workflow is stage-by-stage. We first train the dynamic-point modeling part. An ADAM optimizer with learning rate = 1e-4 is used for optimization. $\beta$ is 0.5, $\sigma$ is 0.1 and $\lambda$ = 0.2. Then we apply the well-trained dynamic-point extractor to access the dynamic points. After dynamic-to-instance and instance matching, we get the extracted trajectories. For the trajectory prediction part, we follow the settings in the original paper to train the network optimizer, including the observation and prediction length.

For trajectory prediction, we use several LSTM-based models, including Vanilla-LSTM, Occupancy-LSTM (O-LSTM), and Social LSTM (S-LSTM) [1]. They are trained by ground truth data before. In our approach, we use our extracted trajectories to train these models. Following the original setting in S-LSTM, we filter our extracted trajectories by removing the trajectories with lengths less than 20 frames (8 seconds). We set $K$=180 so that the dynamic points could distribute all moving objects.

We introduce recall and precision to test the quality of instance points extracted from Dynamic-to-Instance Aggregation. We give the detailed explanation as follows. (1) True-Positive instance points: instance points where the distance between detected instance points and the ground-truth points is less than the threshold $\mathcal{D}$. (2) Recall: the ratio of True-Positive points to all ground-truth points. (3) Precision: the ratio of True-Positive points to all detected instance points. We term them Ins-Recall and Ins-Precision, respectively.

We also apply recall and precision to test qualities of extracted trajectories. The True-Positive trajectories are defined as: trajectories where the average distance between extracted trajectories and ground truth trajectories across timesteps is less than the threshold $\mathcal{E}$. The definition of recall and precision is similar to the statement above. We term them Gen-Recall and Gen-Precision, respectively. Note that there exist some conditions where one detected instance point (or trajectory) corresponds to several ground truth points (or trajectories), or vice versa. We use the KM algorithm to get the minimum cost matching. Both precision and recall are calculated on average. We set $\mathcal{E}$ = 1.5 and $\mathcal{D}$ = 1.5.

Similar to prior work [1], we use two popular evaluation metrics for predicted trajectory evaluation: (1) Average Displacement Error (ADE): Average L2 distance between predicted trajectory and the ground truth over all timesteps. (2) Final Displacement Error (FDE): The distance between the predicted final destination and the true final destination in the ground truth. Besides the comparison between our unsupervised method and supervised methods, we also conduct semi-supervised experiments by using our extracted trajectories as extra data to train supervised models.

For the dynamic-point modeling part, we use two publicly available datasets: ETH [34] and UCY [23] as the training data. These two datasets are captured by fixed-cameras. Although there are some other datasets containing videos of traffic scenarios such as KITTI [16] and Argoverse [10], the videos are all captured in drivers’ view. The camera is moving and and they do not provide the homograph matrix for each frame, which is not infeasible for our method.

We follow Social LSTM [1] to split the video to frames at every 0.4 seconds. For the trajectory prediction stage, we need to convert pixel coordinates to real-world coordinates to train these LSTM-based methods. Therefore, the extrinsic matrix is required to transfer the pixel coordinates to the real-world coordinates. From the open-source codebase ^††https://github.com/trungmanhhuynh/Scene-LSTM, it can be found that only three scenes (UCY-Zara01, UCY-Zara02, and UCY-University) have complete transform matrixes. We thus use these three scenes for trajectory prediction.

In this section, we perform several ablation studies to investigate the effectiveness of different components of the proposed approach. We train the dynamic-point modeling part with all five scenes and test the performance on Zara1 and Zara2.

Although the proposed method works in an unsupervised manner, there also exist some limitations. 1) The whole framework is not end-to-end. We train these learnable components one by one. 2) There are some hyper-parameters, which need fine-tuning when training with different datasets. 3) Since there is no target category, our method might focus on the dynamic part of non-target category, such as a car in the pedestrian trajectory dataset. We visualize some badcases in the supplementary materials. In the future work, we aim to incorporate the category-aware memory and template into the dynamic modeling to further distinguish different categories. And we will also explore dynamic point-based approach on drivers’ view videos.