GSM: Graph Similarity Model for Multi-Object Tracking

1 Introduction

Multi-object tracking (MOT) aims at estimating the locations of multiple objects in the video sequence and maintaining their identities consistently, which has various applications such as video surveillance and autonomous driving. Benefiting from the advances of object detection [Felzenszwalb et al., 2010; Ren et al., 2015; Yang et al., 2016], the trackingby-detection paradigm has become popular for MOT in the past decade. Methods following this paradigm focus on associating object detections across frames, namely data association problem.

Generally, a robust similarity model is the key to the success of data association based trackers. Most existing methods build similarity model only based on the feature of the individual object while ignoring the relations among objects.

∗Corresponding Author

Despite the progress, using the feature of the individual object alone would be problematic in some complex scenarios. For example, since the objects usually belong to the same category (e.g. pedestrians or vehicles) in MOT scenarios, different objects are prone to share similar appearance. Using the individual feature alone is not sufficient to discriminate these objects well. Besides, objects in MOT scenarios usually suffer from frequent occlusions, especially in crowded scenes, which would be a great challenge for building a robust similarity model using only the feature of the individual object.

In contrast to the individual feature, the relations among objects indicate the topological structure of multiple objects, which can be utilized as an important cue for facilitating the robustness of the similarity model. As shown in Figure 1, in the case of occlusion and different objects sharing similar appearance, similarity scores based on individual feature representation are unreliable. While the consistent relations among objects across frames can help to improve the reliability of the similarity scores, since the simultaneous consideration of multiple objects and their topological structure is more robust to the variants of individual objects.

In this paper, we propose a novel graph representation that utilizes the merits of both the individual feature and the relations among objects to improve the robustness of the similarity model. Specifically, for each object, regarded as a anchor, we build a directed graph of which the vertexes represent appearance feature of the anchor object and its neighbors respectively. Each vertex has a edge directed to the anchor object, which represents the relative position feature. Thus, the individual information and relations among objects are encoded by the vertexes and edges respectively.

The graph representation may introduce some unreliable neighbors and corresponding relations due to imperfect detections such as false alarms and missing detections, which would cause the problem of misalignment when calculating the similarity score of two graph representations. To handle this problem, we design a graph matching module. Specifically, we first align the two graph representations by solving the linear assignment problem among neighbors of two anchor objects and then use the aligned graph representations to calculate the similarity score. Thus, the impact of unreliable detections could be effectively suppressed.

To sum up, the contributions of this work are as follows:

First, we propose a novel graph representation that integrates the individual feature and relations among objects to improve the robustness of the similarity model.

Second, we design a graph matching module which can effectively alleviate the impact of unreliable detections.

Third, we apply the proposed graph similarity model (GSM) to Tracktor [Bergmann et al., 2019], the current stateof-the-art online MOT tracker, and achieve the best performance on MOT benchmarks [Milan et al., 2016] in most metrics including MOTA and IDF1.

2 RelatedWork

2.1 Tracking-by-Detection Paradigm

Thanks to the advances of object detectors [Felzenszwalb et al., 2010; Ren et al., 2015; Yang et al., 2016], numerous methods based on tracking-by-detection paradigm have been developed for MOT. These methods focus on associating object detections provided by a pre-defined detector across frames, namely the data association problem. Generally, the existing works can be categorized into online methods [Sadeghian et al., 2017; Zhu et al., 2018; Xu et al., 2019; Bergmann et al., 2019] and offline methods [Li et al., 2009; Maksai and Fua, 2019]. Online methods process video sequences frame-by-frame and generate trajectories only using information up to the current frame, which are suitable for causal applications. While offline methods process video sequences in a batch way and can utilize the whole video information including the future frames to better handle the data association problem.

The proposed method is also based on the tracking-bydetection paradigm and focuses on improving the robustness of the similarity model for more accurate association. Although the proposed method is applicable to both online and offline trackers, we only use the simpler online setting for better comparison in this paper.

2.2 SimilarityModel

A robust similarity model is crucial for data association based MOT trackers. Most existing works utilize the feature of individual object including appearance and motion to measure similarity.

Appearance is an important cue to discriminate different objects, which is widely used in MOT. Many early works extracted hand-craft appearance feature such as raw pixel template [Yamaguchi et al., 2011; Pellegrini et al., 2009], color histogram [Izadinia et al., 2012; Xiang et al., 2015], HOG [Izadinia et al., 2012; Kuo et al., 2010] and so on. Recently, deep networks have been adopted to MOT for modeling appearance of objects [Zhu et al., 2018]. In this work, we also utilize deep networks to extract appearance feature. Different from previous methods that directly use appearance feature to compute the similarity score, appearance feature is used together with the feature of relations among objects to build a graph representation for each object in our work.

Motion is also a commonly used cue in MOT. Most methods assumed that the objects move smoothly in the image space and designed different motion models to capture the dynamic behaviour of individual objects such as linear motion model [Milan et al., 2013; Breitenstein et al., 2009] and nonlinear motion model [Yang and Nevatia, 2012]. However, the movement of object is not always smooth and thus may not be predictable, especially when the camera moves. In this paper, instead of modeling the movements of individual objects, we utilize the relative positions among objects which are more robust to the camera motion.

Besides these individual features, relations among objects are also helpful for measuring similarity. However, due to its complexity, only a few works successfully encoded the relations among objects. The pioneering works [Helbing and Molnar, 1995; Pellegrini et al., 2009; Yamaguchi et al., 2011] modeled a few interactions among objects such as collision avoidance or group attraction with the hand-designed patterns. Recently, [Sadeghian et al., 2017] modeled the relations among objects using the occupancy map where the neighborhood of object are treated as a fixed size occupancy grid. However, the representation of the occupancy grids only models the rough distribution of objects' location, without differentiating individual objects. [Xu et al., 2019] utilized relation network to encode the relations information, which makes the individual object differentiable. Specifically, the relations information was encoded as the attention weights for aggregating appearance information from other objects to strengthen the input appearance feature. However, representing the relations information in such a implicit way can not take full use of the topological structure among objects. Besides, both the representation of occupancy grids and the attention weights are sensitive to the unreliable relations due to imperfect detections such as false alarms and missing detections. Different from these methods, we integrate the appearance of individual objects and the relations among objects into a unified graph representation which can make them both differentiable. What's more, we also design a graph matching module to alleviate the impact of unreliable relations.

3 Method

In this paper, we focus on improving the robustness of the similarity model. To this end, we propose a Graph Similarity Model (GSM) that can be applied to any data association based MOT method. To better understand the proposed GSM, we first introduce the general data association procedure.

3.1 Data Association

Let Dt = {dti }It i=1 denotes the set of detections in the tth frame, where It is the number of detections. Each detection dti is denoted as dti = (bti , pti ), where pti is the image patch cropped from frame t, and bti = (xti , yt i , wt i , hti ) is the bounding-box represented by the center coordinate, width and height.

The data association procedure between frame t - 1 and t can be solved by some linear assignment algorithms, such as Hungarian algorithm, while providing a cost matrix M ∈ RIt-1×It . The element mi,j in M:

is the cost between dt-1 i and dtj , where C(·, ·) is the function to compute the cost based on individual representations of dt-1 i and dtj .

Most existing methods focus on the learning of representation of object detections or the design of C(·, ·) without taking the relations among objects into consideration, which results in an un-robust cost mi,j , as shown in Figure 2 (a), detections dt-1 1 (heavily occluded) and dt1 are the same object, but it's hard to get a proper cost between them based on Eq. (1).

To take advantage of the relations among objects, we propose:

where Gdti is the directed graph constructed for dti , CG(·, ·) is the graph matching function to get the cost based on two graphs. The relations among objects (topological structure of objects) are embedded into the directed edges of graph.

3.2 Graph SimilarityModel

In order to build a graph for detection dti , we first get its top K neighbors intra the same frame t. In this paper, we use the Euclidean distance between the center coordinates of boundingboxes as the default measurement to get the neighbors. Let Ndti = {dti } ∪ {dtik }Kk=1 be the ordered set of anchor dti and its K neighbors, where dtik is the k-th neighbor of dti . To simplify the notation, we define dti as its 0-th neighbor, i.e. Ndti = {dtik }Kk=0 . Taking the detections in Figure 2 (a) for example, when K = 2, Ndt1 = {dt10 , dt11 , dt12 } = {dt1 , dt2 , dt3 } and Ndt2 = {dt20 , dt21 , dt22 } = {dt2 , dt3 , dt1 }.

Graph Representation

The directed graph Gdti = (Vdti ,Edti ), which is constructed upon Ndti , consists of K + 1 vertexes and K + 1 directed edges (see Figure 2 (b), (c) and (d)).

The set of vertexes Vdti are defined as:

where fCNN(·) denotes the forward function of a Convolutional Neural Network (CNN) and vt ik is the appearance feature vector extracted from the image patch ptik of detection dtik .

In order to embed the relation between dti and one of its neighbors dtik , we define the relative position between them as:

where wt and ht are the width and height of frame t respectively, and fRP (·, ·) denotes the function to get relation position rt ik when given two bounding-boxes. This 8-d relative position is encoded to a high-dimensional (64-d in default) representation by the method in [Vaswani et al., 2017], which is denoted as ˆ rt ik . The set of directed edges Edti are defined as:

where fRPE(·) denotes the forward function of Relative Position Embedder (RPE), as shown in Figure 3.

Graph Matching Module

Given two graphs Gdt-1 i and Gdtj , we first get a similarity matrix Si,j ∈ R(K+1)×(K+1) , the element in k-th row and k′ -th column is:

where ⊖ is element-wise substraction between two feature vectors, | · |2 denotes element-wise square operation, [·, ·] denotes the concatenation of two feature vectors, and BC(·) denotes the Binary Classifier, as shown in Figure 3.

Intuitively, the similarity between graph Gdt-1 i and Gdtj can be defined as:si,j = 1

We call this matching method hard graph matching. Due to the false positive and false negative in the provided detections, the similarity si,j in Eq.(7) is unreliable when dt-1 i and dtj are the same object. As shown in Figure 4 (a), both the first and second neighbors of dt-1 3 and dt3 are different objects. However, the first neighbor of dt3 and the second neighbor of dt-1 3 are the same object. To alleviate such misalignment between the neighbors, we propose another soft graph matching method:

where ˆ Si,j ∈ RK×K is the matrix by removing the first row and column of Si,j, and fLA(·) is a modified linear assignment function, which solves the linear assignment problem and returns the maximum total similarity. Compared with hard graph matching, soft graph matching is positive to the case that two graphs are built for the same object, but be negative to the case that two graphs are built for different objects since it gets a higher similarity score for all different pair of graphs. Nevertheless, the negative effect to the later case is negligible thanks to the effective representation of graphs.

Finally, Eq.(2) can be rewritten as:

Finding Lost Objects based on GSM

In the field of MOT, an object may be occluded severely by others which is undetectable for detectors. As shown in Figure 4 (b), the object within green dashed box is lost in frame t while tracking online. However, its position can be estimated by the proposed GSM since its neighbors are detected and tracked.

Suppose dt-1 i is lost in frame t. For each tracked neighbor dt-1 ik , let dtik be the corresponding detection in frame t. A bounding-box ¯bt,k i in frame t can be estimated for dt-1 i based on btik :

where f -1 RP (·, ·) denotes the inverse function of fRP (·, ·) in Eq.(4). By averaging all estimated ¯bt,k i , we can get the final estimated bounding-box ¯bti for dt-1 i .

We further sample several candidate bounding-boxes for dti based on ¯bti . Let ˆbti be one of the sampled bounding-boxes, and ˆ dti = (ˆbti , pt-1 i ) be the candicate detection for dt-1 i in frame t. A graph Gˆ dti can be built based on Nˆ dti = { ˆ dti } ∪ {dtik }Kk=1 . Then a similarity score is computed between Gˆ dti and Gdt-1 i . Among all these candidate detections, the one with the highest similarity score is chosen as the tracked state for dt-1 i in frame t if the similarity score is high enough.

4 Experiments

The proposed Graph Similarity Model is implemented based on PyTorch library. Evaluation is on a workstation with 2.6 GHz CPU and Nvidia TITAN Xp GPU.

4.1 Datasets

Experiments are conducted on MOT Benchmarks, including MOT16 and MOT17 [Milan et al., 2016]. The MOT17 dataset contains 14 sequences each of which is provided with three sets of public detections. The detections produced by different object detectors each with increasing performance, namely DPM [Felzenszwalb et al., 2010], FRCNN [Ren et al., 2015] and SDP [Yang et al., 2016]. Seven of these 14 sequences are used for training and the remains are for testing. The MOT16 dataset also contain the same sequences as MOT17 but only provided with one set of public detections produced by DPM.

4.2 EvaluationMetrics

We adopt the standard metrics of MOT Benchmarks: MultiObject Tracking Accuracy (MOTA) [Bernardin and Stiefelhagen, 2008], Multi-object Tracking Precision (MOTP), [Bernardin and Stiefelhagen, 2008], how often an object is identified by the same ID (IDF1), Mostly Tracked objects (MT), Mostly Lost objects (ML), number of False Positives (FP), number of False Negatives (FN), number of Identity Switches (IDS) [Li et al., 2009] and number of Fragments (Frag).

4.3 Implement Details

All image patches are resized to 64 × 128. The CNN used to extract the appearance features from image patches is modified fromResNet-34 [He et al., 2016]. Particularly, the last fclayer is removed, producing a 256 channel feature map with spatial size 2 × 4. The feature map is reshaped to a 2048-d feature vector followed by another fc-layer, which produces a 256-d appearance feature vector. The relative position is also embedded into a 256-d feature vector by RPE.

The appearance CNN, RPE and binary classifer are trained end-to-end with binary cross entropy loss for 30 epochs. The input [|vt-1 ik ⊖vt jk′ |2 , |et-1 ik ⊖etjk′ |2 ] (see Eq. (6)) of the classifier is a positive sample only when the following two conditions are met: (1) dt-1 i and dtj are the same object, (2) dt-1 ik and dtjk′ are also the same object. The learning rate is initialized as 0.002 and decades every 10 epochs with exponential decay rate 0.5. Online hard example mining (OHEM) was adopted to address the imbalance of positive/negative issue.

4.4 Ablation Study

The 7 sequences in MOT16 train split are divided into train set and validation set to conduct ablation study. Validation set: MOT16-09 and MOT16-10. Training set: the rest sequences in MOT16 train split.

In order to show the effectiveness of our proposed GSM model, a Naive model, which consists of an appearance CNN and a binary classifier, was also designed. The classifier in naive model predicts the similarity score of two detections based on the individual appearance feature vectors. Then two simple trackers (denoted as GSM and Naive) are designed. Note that the only difference between them is the similarity model they used. Both trackers track objects by performing data association procedure between two frame.

The study was carried out on the validation set with public DPM [Felzenszwalb et al., 2010] detections. The detections were directly used without any processing.

Quantitative Results

Quantitative results are shown in Table 1. The first two rows compare the Naive and GSM models without neighbors. Two models achieve almost the same performance. Recall the 8-d relative position in Eq.(4), the relative position of one detection to itself is all zeros, which means that only appearance features are used in GSM when K = 0.

The following four rows compare the hard and soft graph matching (indicated by the subscripts of model names) when

5 neighbors are used for Naive and GSM models. For Naive models, the graph are constructed without edges. Both hard and soft graph matching methods have a negative impact on the performance and there are obvious reasons for that: (1) Two graphs that are built for two different objects are much similar to each other if the same objects are used as the neighbors. (2) The negative effect to the case that two graphs are built for two different objects can not be negligible since only appearance features are used. For GSM models, hard graph matching decades the tracking performance when comparing GSM5h with GSM0 . The reason is that two graphs built for the same object possess a much lower similarity score if the neighbors are not all the same, as shown in Figure 4 (a). Compared with Naive0 and GSM0 , GSM5s achieves a 5.9% higher IDF1 and a much lower IDS, demonstrating that GSM5s tracks one object with the same ID more often.

The last row shows the effectiveness of finding lost objects with the help of graph matching, denoted as GSM5s+f . 64 candidate bounding-boxes are sampled for each lost object. The one that best matches the graph is used as the tracked position if the similarity score is high enough. As shown in Table 1, GSM5s+f possesses a 1.0% higher MOTA and a 2.0% higher IDF1 compared with GSM5s . In addition, GSM5s+f achieves a better FN, which means some lost objects are re-find successfully. However, re-findinging some lost objects also leads to a higher FP.

Extensive experiments are also conducted to find the best value of K, as shown in Figure 5. Over all, the tracker achieves a slightly higher MOTA but almost the same IDF1 when K ≥ 5. Here we try to give an explanation. With the increase of K, the similarity score of two graphs obtained by Eq.(8) that built for the same object should be more reliable. On the contrary, the similarity score of two graphs that are built for different objects is more unreliable. The positive and negative impact on the similarity score are offset by each other to further improve the tracking performance. A larger value of K takes more time to align the neighbors. We set K as 5 in default to trade off the time consumption and tracking performance. The time consumption for constructing a graph and matching two graphs are about 0.15 ms and 0.03 ms, respectively. On our validation set, replacing the baseline similarity model with the proposed GSM leads to the tracking speed dropping from 93.7 fps to 61.5 fps.

Qualitative Results

Qualitative results are also shown in Figure 6 to demonstrate the effectiveness of graph matching and the finding of lost object. At frame 27, there are two objects (denoted as object-2 and object-8) in the yellow dashed box. At frame 29, object-2 is occluded by object-8, leading to un-detected by the detector. However, the position of object-2 at frame 29 can be well estimated by GSM5s+f . At frame 49, object-2 is totally occluded by object-8. The Naive0 model recognizes object-8 as object-2 erroneously. However, both GSM5s and GSM5s+f track objects successfully.

4.5 Results onMOT Benchmarks

We apply the proposed Graph Similarity Model to the stateof-the-art method Tracktor [Bergmann et al., 2019], denoted as GSMTracktor, and compare the integrated tracker with other online methods. Results are shown in Table 2.

MOT16. GSMTracktor achieves the best results in all metrics except MOTP, FP and IDS. In terms of IDS, GSMTracktor takes the second place, only a little higher (475 than 473) than the first. Compared with Tracktor, MOTA and IDF1 are greatly improved by 5.7% and 3.6% respectively. What's more, IDS is also significantly reduced by 30.4%. The better results of IDF1 and IDS achieved by GMSTracktor demonstrates the effectiveness of the proposed graph representation and matching.

MOT17. Overall, the integrated tracker GSMTracktor achieves the state-of-the-art results. Compared with Tracktor, GSMTracktor performs better in most metrics. Specifically, MOTA and IDF1 are improved by 2.9% and 5.5%, and IDS is reduced by more than 20%, which demonstrates that the similarity score obtained by graph representation and matching is much more reliable.

5 Conclusion

In this paper, a Graph Similarity Model (GSM) is proposed to improve the accuracy of data association for MOT. Based on the designed graph representation, the proposed GSM model takes both the individual representation and the relations among objects into consideration. Besides, we build a graph matching module that can effectively alleviate the impact of the unreliable detections. With the help of the graph representation and the graph matching module, the proposed GSM can effectively improve the robustness of the similarity model, especially on the case where occlusion happens and different objects share the similar appearance. In addition, the proposed GSM can be applied to any MOT trackers based on data association. Experimental results on challenging MOT benchmarks demonstrate the effectiveness of our GSM.

Acknowledgments

This work is partly supported by the Major Scientific Research Project of Zhejiang Lab (No. 2019DB0ZX01), the Key Laboratory Foundation of the Chinese Academy of Sciences (CXJJ-17S044) and the Fundamental Research Funds for the Central Universities (WK2100330002, WK3480000005).