Learning a Neural Solver for Multiple Object Tracking

Introduction

Multiple object tracking (MOT) is the task of determining the trajectories of all object instances in a video. It is a fundamental problem in computer vision, with applications such as autonomous driving, biology, and surveillance. Despite its relevance, it remains a challenging task and a relatively unexplored territory in the context of deep learning.

In recent years, tracking-by-detection has been the dominant paradigm among state-of-the-art methods in MOT. This two step approach consists in first obtaining frame-by-frame object detections, and then linking them to form trajectories. While the first task can be addressed with learning-based detectors , the latter, data association, is generally formulated as a graph partitioning problem . In this graph view of MOT, a node represents an object detection, and an edge represents the connection between two nodes. An active edge indicates the two detections belong to the same trajectory. Solving the graph partitioning task, i.e., finding the set of active edges or trajectories, can also be decomposed into two stages. First, a cost is assigned to each edge in the graph encoding the likelihood of two detections belonging to the same trajectory. After that, these costs are used within a graph optimization framework to obtain the optimal graph partition.

Previous works on graph-based MOT broadly fall into two categories: those that focus on the graph formulation, and those that focus on learning better costs. In the first group, numerous research has been devoted to establishing complex graph optimization frameworks that combine several sources of information, with the goal of encoding high-order dependencies between detections . Such approaches often use costs that are handcrafted to some extent. In the second group, several works adopt a simpler and easier to optimize graph structure, and focus instead on improving edge cost definition by leveraging deep learning techniques . By exploiting siamese convolutional neural networks (CNN), these approaches can encode reliable pairwise interactions among objects, but fail to account for high-order information in the scene. Overall, these two lines of work present a dilemma: should MOT methods focus on improving the graph optimization framework or the feature extraction?

We propose to combine both tasks into a unified learning-based solver that can: (i) learn features for MOT, and (ii) learn to provide a solution by reasoning over the entire graph. To do so, we exploit the classical network flow formulation of MOT to define our model. Instead of learning pairwise costs and then using these within an available solver, our method learns to directly predict final partitions of the graph into trajectories. Towards this end, we perform learning directly in the natural MOT domain, i.e., in the graph domain, with a message passing network (MPN). Our MPN learns to combine deep features into high-order information across the graph. Hence, our method is able to account for global interactions among detections despite relying on a simple graph formulation. We show that our framework yields substantial improvements with respect to state of the art, without requiring heavily engineered features and being up to one order of magnitude faster than some traditional graph partitioning methods.

To summarize, we make the following contributions:

We propose a MOT solver based on message passing networks, which can exploit the natural graph structure of the problem to perform both feature learning as well as final solution prediction.

We propose a novel time-aware neural message passing update step inspired by classic graph formulations of MOT.

We show significantly improved state-of-the-art results of our method in three public benchmarks.

Related Work

Most state-of-the-art MOT works follow the tracking-by-detection paradigm which divides the problem into two steps: (i) detecting pedestrian locations independently in each frame, for which neural networks are currently the state-of-the-art , and (ii) linking corresponding detections across time to form trajectories.

Tracking as a Graph Problem. Data association can be done on a frame-by-frame basis for online applications or track-by-track . For video analysis tasks that can be done offline, batch methods are preferred since they are more robust to occlusions. The standard way to model data association is by using a graph, where each detection is a node, and edges indicates possible link among them. The data association can then be formulated as maximum flow or, equivalently, minimum cost problem with either fixed costs based on distance , including motion models , or learned costs . Both formulations can be solved optimally and efficiently. Alternative formulations typically lead to more involved optimization problems, including minimum cliques , general-purpose solvers, e.g., multi-cuts . A recent trend is to design ever more complex models which include other vision input such as reconstruction for multi-camera sequences , activity recognition , segmentation , keypoint trajectories or joint detection .

Learning in Tracking. It is no secret that neural networks are now dominating the state-of-the-art in many vision tasks since showed their potential for image classification. The trend has also arrived in the tracking community, where learning has been used primarily to learn a mapping from image to optimal costs for the aforementioned graph algorithms. The authors of use a siamese network to directly learn the costs between a pair of detections, while a mixture of CNNs and recurrent neural networks (RNN) is used for the same purpose in . More evolved quadruplet networks or attention networks have lead to improved results. In , authors showed the importance of learned reID features for multi-object tracking. All aforementioned methods learn the costs independently from the optimization method that actually computes the final trajectories. In contrast, incorporate the optimization solvers into learning. The main idea behind these methods is that costs also need to be optimized for the solver in which they will be used. rely on structured learning losses while proposes a more general bi-level optimization framework. These works can be seen as similar to ours in spirit, given our common goal of incorporating the full inference model into learning for MOT. However, we follow a different approach towards this end: we propose to directly learn a solver and treat data association as a classification task, while their goal is to adapt their methods to perform well with non-learnable solvers. Moreover, all these works are limited to learning either pairwise costs or additional quadratic terms but cannot incorporate higher-order information as our method. Instead, we propose to leverage the common graph formulation of MOT as a domain in which to perform learning.

Deep Learning on Graphs. Graph Neural Networks (GNNs) were first introduced in as a generalization of neural networks that can operate on graph-structured domains. Since then, several works have focused on further developing and extending them by developing convolutional variants . More recently, most methods were encompassed within a more general framework termed neural message passing and further extended in as graph networks. Given a graph with some initial features for nodes and optionally edges, the main idea behind these models is to embed nodes (and edges) into representations that take into account not only the node’s own features but also those of its neighbors in the graph, as well as the graph overall topology. These methods have shown remarkable performance at a wide variety of areas, ranging from chemistry to combinatorial optimization . Within vision, they have been successfully applied to problems such as human action recognition , visual question answering or single object tracking .

Tracking as a Graph Problem

Our method’s formulation is based on the classical min-cost flow view of MOT . In order to provide some background and formally introduce our approach, we start by providing an overview of the network flow MOT formulation. We then explain how to leverage this framework to reformulate the data association task as a learning problem.

In tracking-by-detection, we are given as input a set of object detections $\mathcal{O}=\{o_{1},\dots,o_{n}\}$, where $n$ is the total number of objects for all frames of a video. Each detection is represented by $o_{i}=(a_{i},p_{i},t_{i})$, where $a_{i}$ denotes the raw pixels of the bounding box, $p_{i}$ contains its 2D image coordinates and $t_{i}$ its timestamp. A trajectory is defined as a set of time-ordered object detections $T_{i}=\{{o_{i_{1}}},\dots,{o_{i_{n_{i}}}}\}$, where $n_{i}$ is the number of detections that form trajectory $i$. The goal of MOT is to find the set of trajectories $\mathcal{T}_{*}=\{T_{1},\dots,T_{m}\}$, that best explains the observations $\mathcal{O}$.

The problem can be modelled with an undirected graph $G=(V,E)$, where $V:=\{1,\dots,n\}$, $E\subset V\times V$, and each node $i\in V$ represents a unique detection $o_{i}\in\mathcal{O}$. The set of edges $E$ is constructed so that every pair of detections, i.e., nodes, in different frames is connected, hence allowing to recover trajectories with missed detections. Now, the task of dividing the set of original detections into trajectories can be viewed as grouping nodes in this graph into disconnected components. Thus, each trajectory $T_{i}=\{{o_{i_{1}}},\dots,{o_{i_{n_{i}}}}\}$ in the scene can be mapped into a group of nodes $\{i_{1},\dots,i_{n_{i}}\}$ in the graph and vice-versa.

2 Network Flow Formulation

In order to represent graph partitions, we introduce a binary variable for each edge in the graph. In the classical minimum cost flow formulationWe present a simplified version of the minimum cost flow MOT formulation . Specifically, we omit both sink and source nodes (and hence their corresponding edges) and we assume detection edges to be constant and 1-valued. We provide further details on our simplification and its relationship to the original problem in Appendix A. , this label is defined to be 1 between edges connecting nodes that (i) belong to the same trajectory, and (ii) are temporally consecutive inside a trajectory; and 0 for all remaining edges.

A trajectory $T_{i}=\{{o_{i_{1}}},\dots,{o_{i_{n_{i}}}}\}$ is equivalently denoted by the set of edges $\{(i_{1},i_{2}),\dots,(i_{n_{i}-1},i_{n_{i}})\}\subset E$, corresponding to its time-ordered path in the graph. We will use this observation to formally define the edge labels. For every pair of nodes in different timestamps, $(i,j)\in E$, we define a binary variable $y_{(i,j)}$ as:

An edge $(i,j)$ is said to be active whenever $y_{(i,j)}=1$. We assume trajectories in $\mathcal{T}$ to be node-disjoint, i.e., a node cannot belong to more than one trajectory. Therefore, $\hat{y}$ must satisfy a set of linear constraints. For each node $i\in V$:

These inequalities are a simplified version of the flow conservation constraints . In our setting, they enforce that every node gets linked via an active edge to, at most, one node in past frames and one node in upcoming frames.

3 From Learning Costs to Predicting Solutions

In order to obtain a graph partition with the framework we have described, the standard approach is to first associate a cost $c_{(i,j)}$ to each binary variable $y_{(i,j)}$. This cost encodes the likelihood of the edge being active . The final partition is found by optimizing:

which can be solved with available solvers in polynomial time .

We propose to, instead, directly learn to predict which edges in the graph will be active, i.e., predict the final value of the binary variable $y$. To do so, we treat the task as a classification problem over edges, where our labels are the binary variables $y$. Overall, we exploit the classical network flow formulation we have just presented to treat the MOT problem as a fully learnable task.

Learning to Track with Message Passing Networks

Our main contribution is a differentiable framework to train multi-object trackers as edge classifiers, based on the graph formulation we described in the previous section. Given a set of input detections, our model is trained to predict the values of the binary flow variables $y$ for every edge in the graph. Our method is based on a novel message passing network (MPN) able to capture the graph structure of the MOT problem. Within our proposed MPN framework, appearance and geometry cues are propagated across the entire set of detections, allowing our model to reason globally about the entire graph.

Our pipeline is composed of four main stages:

1. Graph Construction: Given a set of object detections in a video, we construct a graph where nodes correspond to detections and edges correspond to connections between nodes (Section 3.2).

2. Feature Encoding: We initialize the node appearance feature embeddings from a convolutional neural network (CNN) applied on the bounding box image. For each edge, i.e., for every pair of detections in different frames, we compute a vector with features encoding their bounding box relative size, position and time distance. We then feed it to a multi-layer perceptron (MLP) that returns a geometry embedding (Section 4.3).

3. Neural Message Passing: We perform a series of message passing steps over the graph. Intuitively, for each round of message passing, nodes share appearance information with their connecting edges, and edges share geometric information with their incident nodes. This yields updated embeddings for node and edges containing higher-order information that depends on the overall graph structure (Section 4.1 and 4.2).

4. Training: We use the final edge embeddings to perform binary classification into active/non-active edges, and train our model using the cross-entropy loss (Section 4.4).

At test time, we use our model’s prediction per edge as a continuous approximation (between 0 and 1) of the target flow variables. We then follow a simple scheme to round them, and obtain the final trajectories.

For a visual overview of our pipeline, see Figure 1.

𝑡1t+1. In this case, we have $N_{3}^{past}=\{1,2\}$ and $N_{3}^{fut}=\{4,5\}$. 2a shows the starting point after an edge update has been performed (equation 3), and the intermediate node update embeddings (equation 4) have been computed. 2b shows the standard node update in vanilla MPNs, in which all neighbors’ embeddings are aggregated jointly. 2c shows our proposed update, in which embeddings from past and future frames are aggregated separately, then concatenated and fed into an MLP to obtain the new node embedding. 4.1 Message Passing Networks In this section, we provide a brief introduction to MPNs based on the work presented in . Let $G=(V,E)$ be a graph. Let $h_{i}^{(0)}$ be a node embedding for every $i\in V$, and $h_{(i,j)}^{(0)}$ an edge embedding for every $(i,j)\in E$. The goal of MPNs is to learn a function to propagate the information contained in nodes and edge feature vectors across $G$.

The propagation procedure is organized in embedding updates for edges and nodes, which are known as message passing steps . In , each message passing step is divided, in turn, into two updates: one from from nodes to edges $(v\rightarrow e)$, and one from edges to nodes $(e\rightarrow v)$. The updates are performed sequentially for a fixed number of iterations $L$. For each $l\in\{1,\dots,L\}$, the general form of the updates is the following :

Where $\mathcal{N}_{e}$ and $\mathcal{N}_{v}$ represent learnable functions, e.g., MLPs, that are shared across the entire graph. $[.]$ denotes concatenation, $N_{i}\subset V$ is the set of adjacent nodes to $i$, and $\Phi$ denotes an order-invariant operation, e.g., a summation, maximum or an average. Note, after $L$ iterations, each node contains information of all other nodes at distance $L$ in the graph. Hence, $L$ plays an analogous role to the receptive field of CNNs, allowing embeddings to capture context information.

2 Time-Aware Message Passing

The previous message passing framework was designed to work on arbitrary graphs. However, MOT graphs have a very specific structure that we propose to exploit. Our goal is to encode a MOT-specific inductive bias in our network, specifically, in the node update step.

Recall the node update depicted in Equations 4 and 5, which allows each node to be compared with its neighbors and aggregate information from all of them to update its embedding with further context. Recall also the structure of our flow conservation constraints (Equations 1 and 2), which imply that each node can be connected to, at most, one node in future frames and another one in past frames. Arguably, aggregating all neighboring embeddings at once makes it difficult for the updated node embedding to capture whether these constraints are being violated or not (see Section 5.2 for constraint satisfaction analysis).

More generally, explicitly encoding the temporal structure of MOT graphs into our MPN formulation can be a useful prior for our learning task. Towards this goal, we modify Equations 4 and 5 into time-aware update rules by dissecting the aggregation into two parts: one over nodes in the past, and another over nodes in the future. Formally, let us denote the neighboring nodes of $i$ in future and past frames by ${N}^{fut}_{i}$ and ${N}^{past}_{i}$, respectively. Let us also define two different MLPs, namely, $\mathcal{N}^{fut}_{v}$ and $\mathcal{N}^{past}_{v}$. At each message passing step $l$ and for every node $i\in V$, we start by computing past and future edge-to-node embeddings for all of its neighbors $j\in{N}_{i}$ as:

Note, the initial embeddings $h_{(i)}^{(0)}$ have been added to the computationThis skip connection ensures that our model does not forget its initial features during message passing, and we apply it analogously with initial edge features in Equation 3.. After that, we aggregate these embeddings separately, depending on whether they were in future or past positions with respect to $i$:

Now, these operations yield past and future embeddings $h_{i,past}^{(l)}$ and $h_{i,fut}^{(l)}$, respectively. We compute the final updated node embedding by concatenating them and feeding the result to one last MLP, denoted as $\mathcal{N}_{v}$:

We summarize our time-aware update in Figure 2c. As we demonstrate experimentally (see Section 5.2), this simple architectural design results in a significant performance improvement with respect to the vanilla node update of MPNs, shown in Figure 2b.

3 Feature Encoding

The initial embeddings that our MPN receives as input are produced by other backpropagatable networks.

Appearance Embedding. We rely on a convolutional neural network (CNN), denoted as $\mathcal{N}_{v}^{enc}$, to learn to extract a feature embeddings directly from RGB data. For every detection $o_{i}\in\mathcal{O}$, and its corresponding image patch $a_{i}$, we obtain $o_{i}$’s corresponding node embedding by computing $h_{i}^{(0)}:=\mathcal{N}_{v}^{enc}(a_{i})$.

Geometry Embedding. We seek to obtain a representation that encodes, for each pair of detections in different frames, their relative position size, as well as distance in time. For every pair of detections $o_{i}$ and $o_{j}$ with timestamps $t_{i}\neq t_{j}$, we consider their bounding box coordinates parameterized by top left corner image coordinates, height and width, i.e., $(x_{i},y_{i},h_{i},w_{i})$ and $(x_{j},y_{j},h_{j},w_{j})$. We compute their relative distance and size as:

We then concatenate this coordinate-based feature vector with the time difference $t_{j}-t_{i}$ and relative appearance $\lVert\mathcal{N}_{v}^{enc}(a_{j})-\mathcal{N}_{v}^{enc}(a_{i})\rVert_{2}$ and feed it to a neural network $\mathcal{N}_{e}^{enc}$ in order to obtain the initial edge embedding $h_{(i,j)}^{(0)}$.

4 Training and Inference

Training Loss. To classify edges, we use an MLP with a sigmoid-valued single output unit, that we denote as $\mathcal{N}_{e}^{class}$. For every edge $(i,j)\in E$, we compute our prediction $\hat{y}_{(i,j)}^{(l)}$ by feeding the output embeddings of our MPN at a given message passing step $l$, namely $h_{(i,j)}^{(l)}$, to $\mathcal{N}_{e}^{class}$. For training, we use the binary cross-entropy of our predictions over the embeddings produced in the last message passing steps, with respect to the target flow variables $y$:

where $l_{0}\in\{1,\dots,L\}$ is the first message passing step at which predictions are computed, and $w$ denotes a positive scalar used to weight 1-valued labels to account for the high imbalance between active and inactive edges.

Inference. During inference, we interpret the set of output values obtained from our model at the last message passing step as the solution to our MOT problem, i.e., the final value for the indicator variables $y$. Since these predictions are the output of a sigmoid unit, their values are between 0 and 1. An easy way to obtain hard or $1$ decisions is to binarize the output by thresholding. However, this procedure does not generally guarantee that the flow conservation constraints in Equations 1 and 2 are preserved. In practice, thanks to the proposed time-aware update step, our method will satisfy over $98\%$ of the constraints on average when thresholding at 0.5. After that, a simple greedy rounding scheme suffices to obtain a feasible binary output. The exact optimal rounding solution can also be obtained efficiently with a simple linear program. We explain both procedures in Appendix B.

Experiments

In this section, we first present an ablation study to better understand the behavior of our model. We then compare to published methods on three datasets, and show state-of-the-art results. All experiments are done on the MOTChallenge pedestrian benchmark.

Datasets and Evaluation Metrics. The multiple object tracking benchmark MOTChallenge The official MOTChallenge web page is available at https://motchallenge.net. consists of several challenging pedestrian tracking sequences, with frequent occlusions and crowded scenes. The challenge includes three separate tracking benchmarks, namely 2D MOT 2015 , MOT16 and MOT17 . They contain sequences with varying viewing angle, size and number of objects, camera motion and frame rate. For all challenges, we use the detections provided by MOTChallenge to ensure a fair comparison with other methods. The benchmark provides several evaluation metrics. The Multiple Object Tracking Accuracy (MOTA) and ID F1 Score (IDF1) are the most important ones, as they quantify two of the main aspects of multiple object tracking, namely, object coverage and identity preservation.

Network Models. For the network $\mathcal{N}_{v}^{enc}$ used to encode detections appearances (see section 4.3), we employ a ResNet50 architecture pretrained on ImageNet , followed by global average pooling and two fully-connected layers to obtain embeddings of dimension 256.

We train the network for the task of ReIdentification (ReID) jointly on three publicly available datasets: Market1501, CUHK03 and DukeMTMC. Note that using external ReID datasets is a common practice among MOT methods . Once trained, three new fully connected layers are added after the convolutional layers to reduce the embedding size of $\mathcal{N}_{v}^{enc}$ to 32. The rest of the encoder and classifier networks are MLPs and their exact architectures are detailed in Table 5 in the supplementary material.

Data Augmentation. To train our network, we sample batches of 8 graphs. Each graph corresponds to small clips of 15 frames sampled at 6 frames per second for static sequences, and 9 frames per second for those with a moving camera. We do data augmentation by randomly removing nodes from the graph, hence simulating missed detections, and randomly shifting bounding boxes.

Training. We have empirically observed that additional training of the ResNet blocks provides no significant increase in performance, but carries a significantly larger computational overhead. Hence, during training, we freeze all convolutional layers and train jointly all of the remaining model components. We train for 15000 iterations with a learning rate $3\cdot 10^{-4}$, weight decay term $10^{-4}$ and an Adam Optimizer with $\beta_{1}$ and $\beta_{2}$ set to $0.9$ and $0.999$, respectively.

Batch Processing. We process videos offline in batches of $15$ frames, with $14$ overlapping frames between batches to ensure that the maximum time distance between two connected nodes in the graph remains stable along the whole graph. We prune graphs by connecting two nodes only if both are among the top-$K$ mutual nearest neighbors (with $K=50$) according to the ResNet features. Each batch is solved independently by our network, and for overlapping edges between batches, we average the predictions coming from the all graph solutions before the rounding step. To fill gaps in our trajectories, we perform simple bilinear interpolation along missing frames.

Baseline. Recently, has shown the potential of detectors for simple data association, establishing a new baseline for MOT. To exploit it, we preprocess all sequences by first running on public detections, which allows us to be fully comparable to all methods on MOTChallenge. One key drawback of is its inability to fill in gaps, nor properly recover identities through occlusions. As we will show, this is exactly where our method excels. In Appendix D, we show additional results without .

Runtime. We build our graph on the output of . Hence, we take also its runtime into account. Our method, on its own, runs at 35fps, while without the added re-ID head runs at 8fps, which gives the reported average of 6.5fps.

2 Ablation Study

In this section, we aim to answer three main questions towards understanding our model. Firstly, we compare the performance of our time-aware neural message passing updates with respect to the time-agnostic vanilla node update described in 4.1. Secondly, we assess the impact of the number of message passing steps in network training to the overall tracking performance. Thirdly, we investigate how different information sources, namely, appearance embeddings from our CNN and relative position information, affect different evaluation metrics.

Experimental Setup. We conduct all of our experiments with the training sequences of the MOT15 and MOT17 datasets. To evaluate our models, we split MOT17 sequences into three sets, and use these to test our models with 3-fold cross-validation. We then report the best overall MOT17 metrics obtained during validation. See Appendix C.3 for more details. In order to provide a fair comparison with configurations that show poor constraint satisfaction, we use exact rounding via a linear program in all experiments (see Section 4.4).

Time-Aware Message Passing. We investigate how our proposed time-aware node update affects performance. For a fair comparison, we perform hyperparameter search for our baseline. Still, we observe a significant improvement in almost all metrics, including close to 3 points in IDF1. As we expected, our model is particularly powerful at linking detections, since it exploits neighboring information and graph structure, making the decisions more robust, and hence producing significantly less identity switches. We also report the percentage of constraints that are satisfied when directly thresholding our model’s output values at 0.5. Remarkably, our method with time-aware node updates is able to produce almost completely feasible results automatically, i.e., 98.8% constraint satisfaction, while the baseline has only 82.1% satisfaction. This demonstrates its ability to capture the MOT problem structure.

Number of Message Passing Steps. Intuitively, increasing the number of message passing steps $L$ allows each node and edge embedding to encode further context, and gives edge predictions the ability to be iteratively refined. Hence, one would expect higher values to yield better performing networks. We test this hypothesis in Figure 3 by training networks with a fixed number of message passing steps, from 0 to 18. We use the case $L=0$ as a baseline in which we train a binary classifier on top of our initial edge embeddings, and hence, no contextual information is used. As expected, we see a clear upward tendency for both IDF-1 and MOTA. Moreover, we observe a steep increase in both metrics from zero to two message passing steps, which demonstrates that the biggest improvement is obtained when switching from pairwise to high-order features in the graph. We also note that the upwards tendency stagnates around six message passing steps, and shows no improvement after twelve message passing steps. Hence, we use $L=12$ in our final configuration.

Effect of the Features. Our model receives two main streams of information: (i) appearance information from a CNN, and (ii) geometry features from an MLP encoding relative position between detections. We test their usefulness by experimenting with combinations of three groups of features for edges: time difference, relative position and the euclidean distance in CNN embeddings between the two bounding boxes. Results are summarized in Table 2. We highlight the fact that relative position seems to be a key component to overall performance since its addition yields the largest relative performance increase. Nevertheless, CNN features are powerful to reduce the number of false positives and identity switches and hence, we use them in our final configuration.

3 Benchmark Evaluation

We report the metrics obtained by our model on the MOT15, MOT16 and MOT17 datasets in Table 3. Our method obtains state-of-the-art results by a large margin on all challenges, improving especially the IDF1 measure by 11, 6.4, and 6.6 percentage points, respectively, which demonstrates our method’s strong performance in identity preservation. We attribute this performance increase to the ability of our message passing architecture to collect higher-order information. Taking into consideration neighbors’ information when linking trajectories allows our method to make globally informed predictions, which leads inevitably to less identity switches. Moreover, we also achieve more trajectory coverage, represented by an increase in Mostly Tracked (MT) trajectories of up to 9 percentage points. It is worth noting the big performance improvement with respect to previous graph partitioning methods (shown as (G) in Table 3), which often use expensive optimization schemes. Not only do we surpass them by a large margin, but we are also up to one order of magnitude faster than some of them, e.g. . In Appendix D, we show a more detailed comparison.

Conclusion

We have demonstrated how to exploit the min-cost flow formulation of MOT to treat the entire tracking problem as a learning task. We have proposed a fully differentiable pipeline in which both feature extraction and data association can be jointly learned. At the core of our algorithm lies a message passing network with a novel time-aware update step that can capture the problem’s graph structure. In our experiments, we have shown a clear performance improvement of our method with respect to previous state-of-the-art. We expect our approach to open the door for future work to go beyond feature extraction for MOT, and focus, instead, on integrating learning into the overall data association task.

Acknowledgements. This research was partially funded by the Humboldt Foundation through the Sofja Kovalevskaja Award.

References

Appendix A Network Flow Formulation

In this section, we detail how the network flow-based formulation we present in the main paper is related to the original one proposed in . See Figure 4 for an overview.

Let $G=(V,E)$ be a graph representing a multiple object tracking (MOT) problem. In our method’s graph formulation, we use nodes and edges to represent, respectively, detections and possible links forming trajectories among them. Moreover, we assign a binary variable $y_{(i,j)}$ to every edge $(i,j)\in E$ to represent whether the link between detections $i$ and $j$ is active or not. Nodes, i.e., detections, do not have any variable assigned to them, and we assume that all detections in the graph are correct. That is, we assume that there are no false positives in the graphWe can make this assumption because we can easily filter false positives from our graphs during pre-processing and post-processing (see Appendix C)..

In the general min-cost flow formulation, instead, detections are also represented with edges and they are assigned, in turn, another binary variable that indicates whether the detection is a true or false positive. Formally, for the $i$th input detection this binary variable is denoted as $y_{i}$, and its value is one if the detection is a true positive, i.e., it is active, and zero otherwise, i.e., it is inactive.

By allowing nodes to be inactive, the flow conservation constraints 1 and 2 we described in the main paper:

are no longer sufficient. Instead, these constraints need to capture that, if a detection is inactive, both its incoming and outgoing flows need to be zero. This is achieved by replacing the right-hand-side of these inequalities with the binary variable $y_{i}$:

Observe that whenever $y_{i}=0$, all edges entering and leaving detection $i$ need to be inactive. In contrast, when $y_{i}=1$, i.e., the detection is active, these constraints are equivalent to the ones we use.

A.2 Source and Sink Nodes

In the classical min-cost flow formulation of MOT , there are two special nodes: source and sink. Every detection $i$ is connected to both of them, and the resulting edge receives a binary variable denoted as $y_{en,i}$ and $y_{ext,i}$, respectively. These are used to indicate whether a trajectory starts or ends at $i$. Observe that $y_{en,i}=1$ if, and only if, there is no detection $j$ in a past frame such that $y_{i,j}=1$, and analogously for $y_{ext,i}=1$. Hence, these variables can be used to transform inequalities 11 and 12 into equalities as:

which yield the flow conservation constraints introduced in . In the original min-cost flow formulation, these edges are assigned a handcrafted cost indicating the price of starting or ending a trajectory. If this cost is set to zero, one can think about $y_{en,i}$ and $y_{ext,i}$ as slack variables.

A.3 Overview of our Simplification

To summarize, in our method we simplify the min-cost flow formulation by eliminating two elements of the classical one: detection edges and sink and source nodes. The first choice allows us to decouple the data association problem from the identification of incorrect detections. Since the latter task can be easily tackled in our pre-processing and post-processing routines (see Appendix C), we can simplify our graph formulation and allow our network to focus on the task of edge classification. As for not using sink and source nodes, in our method there is no need for such special variables. Instead, the start (resp. end) of a trajectory is naturally indicated by the absence of active incoming (resp. outgoing) edges to a node. Overall, we simplify the min-cost flow MOT formulation and reduce it to its most essential component: association edges. As a result, we obtain a setting that is suited for our message passing network to operate and effectively learn our task at hand.

Appendix B Rounding Solutions

As explained in the main paper (Section 4.4), a forward pass through our model yields a fractional solution to the original flow problem with values between 0 and 1. Thanks to our time-aware message passing network, binarizing this solution directly by setting a threshold at 0.5 will yield a solution that satisfies close to 99% of the flow conservation constraints on average over test sequences (see Section 5.2 in the main paper). In order to guarantee that all of them are satisfied, we propose two simple schemes, and describe them in this section. See Figure 5 for a summary of our procedure.

In our setting, having a violated incoming (resp. outgoing) flow conservation constraint means that, for some node, there is more than one incoming (resp. outgoing) edge classified as active. Hence, a simple way to obtain a binary solution satisfying all constraints is to only set as active the incoming (resp. outgoing) edge with the maximum classification score, for every node.

Let $G=(V,E)$ a MOT graph. Observe that, by following this simple policy, we are guaranteed to obtain a binary feasible solution after $o(\Delta(G)|V|)$ steps, where $\Delta(G)$ indicates the maximum degree of any vertex in $G$. Indeed, observe that we have a total of $2|V|$ constraints, since for each node, there are two flow conservation inequalities. Evaluating each of these requires computing a sum of $o(\Delta(G))$ terms, and picking the edge with maximum score among all neighbors in past / future frames has, again, complexity $o(\Delta(G))$. Further observe that, by picking the edge with the highest classification score no new constraints can be violated. Indeed, setting all non-maximum incoming (resp. outgoing) edges in a node to zero will make all remaining left hand sides in inequalities 1 and 2 for other nodes become smaller or equal. Hence, it is clear that, at most, $2|V|$ iterations with $o(\Delta(G))$ operations each will be necessary, which yields a total complexity of $o(\Delta(G)|V|)$. See Algorithm 1 for a summary of this procedure.

B.2 Exact Rounding

As we show in Table 4, the greedy rounding scheme we just introduced works very well in practice. This is due to the fact that our method’s output solutions already satisfy almost all constraints and hence, there is little margin for our rounding scheme to affect performance. However, in general, greedy rounding is not guaranteed to be optimal. We now explain how exact rounding can be performed via linear programming.

However, the quadratic cost can be equivalently written as a linear function. Indeed:

Moreover, matrix $A$, is totally unimodular , which implies that the integrality constraints can be relaxed to box constraints $y_{int}\in^{|E|\times 1}$. Therefore, we can relax our original quadratic integer program to a linear program, and solve it in polynomial time while still being guaranteed integer solutions.

In general, this optimization problem shows a straightforward connection between our setting and the general min-cost flow problem. When naively rounding our solutions with linear programming, we could view our model’s output as edge costs in a min-cost-flow problem instance. The key difference is that, in practice, we do not need to solve the entire problem. Since our model’s output is almost feasible, when rounding, we can obtain binary solutions for almost all edges by directly thresholding their classification scores. With the remaining edges in which flow conservation constraints are violated, we consider their corresponding subgraph, which typically consists of less than $5\%$ of edges in the graph, and either solve the linear program we have described or use the greedy procedure explained in Subsection B.1.

B.3 Performance Comparison

In Table 4, we compare the runtime and performance of both rounding schemes with our model’s final configuration. Both exact and greedy rounding show almost equal performance, with greedy rounding having slightly lower IDF1 (0.2 percentage points), equal MOTA and equal speed. Overall this shows, that given the high constraint satisfaction of our model’s solutions, the method for rounding has little effect on the tracking results. This is to be expected: since there are few edges in which the rounding procedure needs to be applied, there is little room to affect overall results. Instead, the key element driving performance in our model is our message passing network formulation.

Appendix C Further Implementation Details

In this section, we extend the information provided in the main article about the implementation of our method.

In Table 5, we specify the configuration of each of the network’s components. Observe that our model is composed of a total of 6 networks. The first two, $\mathcal{N}_{v}^{enc}$ and $\mathcal{N}_{e}^{enc}$, are used for feature encoding of nodes and edges, respectively (see section 4.3 in the main paper). For neural message passing, we use one network to update edge embeddings, $\mathcal{N}_{e}$, and three networks to update node embeddings $\mathcal{N}_{v}^{past}$, $\mathcal{N}_{v}^{fut}$ and $\mathcal{N}_{v}$ (see sections 4.1 and 4.2 in the main paper). Lastly, to classify edges, we use another network, $\mathcal{N}_{e}^{class}$ (see section 4.4 in the main paper).

C.2 Batch Processing

As explained in the main paper, we process videos by sequentially feeding overlapping batches of 15 frames to our model. In the MOTChallenge, different sequences show great variability regarding (i) number of frames per second at which videos are recorded (ii) presence of camera movement and (iii) number of detections per frame. To account for (i) and (i), we sample a fixed and number of frames per second for static and dynamic sequences, which we set to 6 and 9, respectively. To tackle (iii), we restrict the connectivity of graphs by connecting two nodes only if both are among the top-50 reciprocal nearest neighbors according to the ResNet features. This ensures that our model scales to crowded sequences with no significant overhead, and that the topology of our graphs is comparable among different videos.

C.3 Cross-Validation Splits

We conduct all of our experiments with 3-fold cross-validation on the MOT17 benchmark training data. To do so, we split the sequences into three subsets. For each experiment configuration we train a total of 3 networks: one for each possible validation set. Since our splits cover all training sequences of MOT17, we obtain metrics over the whole dataset which allow us to choose the best network configuration and set of hyperparameters.

In Table 6, we report the validation sequences corresponding to each split. For each of the splits, the sequences not contained in its validation set are used for training, together with those of the MOT15 dataset.

When deciding which sequences to include in each split, we made sure that each subset contains both moving and static camera sequences. Furthermore, we balance the number of tracks and sequence length in seconds (recall that fps is normalized during processing) in each split, in order to ensure that all validation settings are comparable.

C.4 Preprocessing and Postprocessing

As we explain in the next section we use to preprocess public detections. As an alternative, for the results in Section D, we follow a similar detection preprocessing scheme to the one applied by other methods . We use both the bounding box regressor and classifier heads of a Faster-RCNN trained on the MOT17 Detection challenge. We filter out all bounding boxes whose confidence score is smaller than 0.5, and correct the remaining with the bounding box regressor. After that, we apply standard Non-Maxima-Supression to the resulting boxes, by using each box’ confidence score, and setting an IoU threshold of 0.85. For post-processing, if using we fill gaps in our trajectories by matching our output trajectories to the ones in , and then using the latter to fill the detections in missing frames. For the remaining missing gaps in our trajectories, we use bilinear interpolation. Finally, we drop all trajectories that consist of a single detection. This allows our model to identify false positives as isolated nodes in the graph (i.e. nodes with neither incoming nor outgoing active edges).

C.5 Baseline

As explained in the main paper, we use as a baseline. More specifically, we preprocess all sequences by first running on public detections. After that, we discard the pedestrian ID assigned by , and simply treat the resulting boxes as raw detections for our neural solver. uses the regression head of a Faster-R-CNN in order to predict the next locations of objects in neighboring frames

Other graph approaches resort to low-level image features and work with raw (i.e. non-maxima suppressed) detections to approach this challenge . Observe that using raw detections has indeed, more potential than just adding neighboring detections with , as it yields a greatly increased number of object hypothesis. Hence, it allows tracking methods to have the capacity to track more objects. However, reduces computational times significantly, and provides more precise boxes, which improves the efficiency of our method.We perform a detailed comparison with graph-based methods in the next section.

Appendix D Additional Comparison with Graph Methods

We provide an extended comparison of our methodWe made a slight change in the configuration of our method for these results. Since we do not have access to and, hence, we have to rely heavily on linear interpolation for postprocessing (see Appendix C.4), we augment the frame sampling rate at which we process sequences, and also the size of graphs we process proportionally, in order to cover time intervals of the same size of those of our main configuration. Specifically, we increase the sampling rate of frames for static sequences from 6 to 9, and from 9 to 15 for those with a moving camera. As for the number of frames corresponding to each processed graph, we increase it from 15 to 25. with top-performing offline graph-based methods. The results are summarized in Table 7. For each method, we highlight the additional features and sources of information that it has access to. Additionally, we provide the results obtained by our method when we do not use our baseline for preprocessing detections, and we denote it with Ours*. We show that, even in that case, our method still surpasses previous works by a significant margin even though it has access to significantly less information. Hence, these results further confirm the superiority of our approach.

Even without , in the MOT15 dataset we observe an improvement of 19.8 points in MOTA and 15.6 points in IDF1 with respect to , which uses the same underlying Min-Cost Flow graph formulation, but a simpler learning scheme. Moreover, in all three datasets, our method consistently improves significantly upon multi-cut based methods , which use a more involved graph formulation, have access to a significantly larger number of boxes due to not using Non-Maximum Suppression, and either employ low-level image features or use a hierarchical scheme. Thus, we clearly demonstrate that our method shows very strong performance and surpasses previous work, even when it cannot leverage low-level image information via . Furthermore, when our method is given access to additional features as other methods, it shows its full potential and outperforms all previous works by an even larger margin.