PaperlayerView exact revision on arXiv

Source-linked AI summary

Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking

Jiawei He, Zehao Huang, Naiyan Wang, Zhaoxiang Zhang

arXiv:2103.16178v1cs.CV

TL;DR

MOT association research has often omitted within-frame context, separated feature learning from graph optimization, or relied on features learned independently of assignment. GMTracker represents tracklets and detections as graphs and learns their matching through a differentiable quadratic-programming layer; it reports state-of-the-art association performance on a large-scale benchmark.

  • Problem

    Existing MOT methods often omit relationships among tracklets and within-frame detections, while feature learning and optimization-based association are not fully integrated.

    Source: §1 · p. 2

  • Method

    GMTracker models tracklets and detections as graphs and integrates graph matching with deep feature learning through a differentiable quadratic-programming layer.

    Source: §1 · p. 2, §4.3 · p. 6

  • Results

    GMTracker is reported to advance state-of-the-art performance on a large-scale benchmark for association metrics such as IDF1.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper concludes that its second-order edge-to-edge matching is more accurate and robust, especially in crowded videos.

    Source: §6 · p. 8

Abstract

from arXiv · show

Data association across frames is at the core of Multiple Object Tracking (MOT) task. This problem is usually solved by a traditional graph-based optimization or directly learned via deep learning. Despite their popularity, we find some points worth studying in current paradigm: 1) Existing methods mostly ignore the context information among tracklets and intra-frame detections, which makes the tracker hard to survive in challenging cases like severe occlusion. 2) The end-to-end association methods solely rely on the data fitting power of deep neural networks, while they hardly utilize the advantage of optimization-based assignment methods. 3) The graph-based optimization methods mostly utilize a separate neural network to extract features, which brings the inconsistency between training and inference. Therefore, in this paper we propose a novel learnable graph matching method to address these issues. Briefly speaking, we model the relationships between tracklets and the intra-frame detections as a general undirected graph. Then the association problem turns into a general graph matching between tracklet graph and detection graph. Furthermore, to make the optimization end-to-end differentiable, we relax the original graph matching into continuous quadratic programming and then incorporate the training of it into a deep graph network with the help of the implicit function theorem. Lastly, our method GMTracker, achieves state-of-the-art performance on several standard MOT datasets. Our code will be available at https://github.com/jiaweihe1996/GMTracker .

1. Introduction

MOT association methods have largely separated graph optimization from deep feature learning and often omit relationships within a frame. GMTracker models tracklets and detections as graphs, learns their matching through a differentiable optimization layer, and reports state-of-the-art association performance.

1. Introduction

  • The graph formulation uses second-order edge-to-edge similarity to represent group activity, and allows tracklet vertices to remain unmatched when they disappear from the current frame.The figure caption describes this relationship as more robust under heavy occlusion.Source: Figure 1 · p. 1
  • Earlier approaches commonly emphasized either graph-based optimization or deep appearance learning, while recent end-to-end methods remained largely isolated from graph partitioning.The introduction identifies these as distinct approaches to association.Source: §1 · pp. 1–2
  • Traditional online bipartite matching is simple but lacks trajectory history, making it less robust to occlusion than association using multiple frames.The paper motivates adding within-frame context to matching.Source: §1 · p. 2
  • The method represents intra-frame relationships as a general graph and formulates association as graph matching between tracklets and detections.Past relationships with neighborhood objects can help match an occluded object to its tracklet.Source: §1 · p. 2
  • A differentiable quadratic-programming layer uses continuous relaxation, KKT conditions, and the implicit function theorem to derive gradients for joint feature and assignment learning.This connects the matching optimization to deep feature learning.Source: §1 · p. 2
  • GMTracker is reported to advance state-of-the-art performance on a large-scale benchmark for association metrics such as IDF1.The introduction gives no specific benchmark values.Source: §1 · p. 2

2. Related Work

Prior MOT work spans probabilistic filtering, combinatorial assignment, learned appearance models, and efforts to combine graph optimization with deep learning. This paper distinguishes its approach by explicitly using neighborhood context in association and guiding feature learning with the optimization problem.

2. Related Work

  • Prior context-aware methods modeled neighborhood information as motion priors or enhanced appearance features, but did not explicitly use it in cross-frame association.This paper instead incorporates neighborhood context through differentiable graph matching.Source: §2 · p. 2
  • Pairwise graph matching considers second-order edge-to-edge relations beyond vertex-to-vertex assignment, but the resulting quadratic assignment problem is NP-hard.Relaxations have been studied to make the problem tractable.Source: §2 · p. 3
  • Earlier graph matching in MOT used features from an off-the-shelf network, whereas this work guides feature learning with the optimization problem.The authors state that joint training eliminates inconsistencies between training and inference.Source: §2 · p. 3
  • Approaches to combining graph matching and deep learning include direct assignment prediction and convex optimization with gradients derived using KKT conditions and the implicit function theorem.The paper derives its graph-matching layer in the latter spirit.Source: §2 · p. 3

3. Graph Matching Formulation for MOT

The formulation represents detections and tracklets as graphs and casts their association as graph matching. It relaxes the matching problem to a convex quadratic program and extends edge comparisons from scalar weights to learned edge features.

3. Graph Matching Formulation for MOT

  • The method relaxes graph matching to a convex QP, enabling differentiable joint learning of feature representations and combinatorial optimization.The formulation uses edge features in place of scalar edge weights.Source: §3 · p. 3, §3.4 · p. 4

3.1. Detection and Tracklet Graphs Construction

  • Each frame's detections and existing tracklets form complete detection and tracklet graphs for online association.A detection includes image pixels and bounding-box geometry; tracklets collect detections with the same identity.Source: §3.1 · p. 3

3.2. Basic Formulation of Graph Matching

  • Graph matching seeks vertex matches that maximize vertex affinity while aligning the edges connecting matched vertices, formulated as a Quadratic Assignment Problem.The permutation matrix represents the matching, and the vertex affinity matrix scores candidate vertex pairs.Source: §3.2 · p. 3

3.3. Reformulation and Convex Relaxation

  • The QAP objective balances vertex affinities against differences between the weights of corresponding edges.The permutation constraint is relaxed to a doubly stochastic matrix, yielding the stated tightest convex relaxation.Source: §3.3 · pp. 3–4

3.4. From Edge Weights to Edge Features

  • The formulation replaces scalar edge weights with L2-normalized edge features and compares corresponding features by their L2 distance.The feature dimensions are concatenated into weighted adjacency tensors for the graphs.Source: §3.4 · p. 4
  • Cosine similarities between edge features in the detection and tracklet graphs populate the edge affinity matrix Me.Each entry compares one detection-graph edge with one tracklet-graph edge.Source: §3.4 · p. 4
  • The edge affinity matrix Me is mapped to a symmetric quadratic affinity matrix M over possible edge matches.Figure 2 illustrates this derivation.Source: §3.4 · p. 4, Figure 2 · p. 4

4. Graph Matching Network and GMTracker

GMTracker encodes detections and tracklets as graphs, enhances their features with a cross-graph GCN, and matches them through a differentiable graph-matching layer. At inference, it rounds the continuous scores and applies additional tracklet-management steps.

4. Graph Matching Network and GMTracker

  • The network encodes detection and tracklet graphs, enhances their features with a cross-graph GCN, then applies a differentiable graph-matching layer.The tracker integrates these components into its association pipeline.Source: §4 · p. 5

4.1. Feature Encoding in Two Graphs

  • A pretrained ReID network and MLP produce detection appearance features, while each tracklet feature averages the features of its past detections.These features initialize the detection and tracklet graphs.Source: §4.1 · p. 5

4.2. Cross-Graph GCN

  • The cross-graph GCN aggregates features using appearance similarity and bounding-box IoU, but uses appearance similarity alone when the camera moves.The implementation applies one GCN layer and L2-normalizes its final features before constructing edge features.Source: §4.2 · pp. 5–6

4.3. Differentiable Graph Matching Layer

  • The matching layer solves a QP using quadratic and vertex affinities, with gradients derived from KKT conditions and the implicit function theorem.Training uses weighted binary cross-entropy on matching scores, with a temperature-scaled softmax to sharpen the score distribution.Source: §4.3 · p. 6

4.4. Inference Details

  • At inference, greedy rounding converts continuous matching scores into a permutation matrix, followed by filtering, unmatched-tracklet association, and tracklet birth and deletion rules.The filtering criteria include low appearance similarity, distance from tracklets, or no bounding-box overlap.Source: §4.4 · p. 6

5. Experiments

Experiments on MOT16 and MOT17 assess GMTracker through component ablations, design-choice studies, and comparisons with state-of-the-art trackers. The reported results favor graph matching and show strong IDF1 performance across the test benchmarks.

5.1. Datasets

  • Experiments use MOT16 and MOT17, whose videos span varied scenes, lighting, and frame rates and include occlusion, motion blur, camera motion, and distant pedestrians.The study emphasizes IDF1 because MOTA is mostly dominated by detection false positives and false negatives.Source: §5.1 · p. 6

5.2. Implementation Details

  • The ablation study uses a three-fold MOT17 validation split and tests graph matching, appearance refinement, cross-graph GCN with or without geometry, and interpolation.Implementation follows Tracktor for public-detection refinement and DeepSORT-style inference, with linear interpolation for comparisons to offline methods.Source: §5.2 · pp. 6–7, §5.3 · p. 7

5.3. Ablation Study

  • Against DeepSORT, graph matching gains 1.9 IDF1 without interpolation and 2.7 IDF1 plus 1.1 MOTA with interpolation.The authors attribute these results to the effectiveness of second-order edge-to-edge information.Source: §5.3 · p. 7, Table 1 · p. 7
  • The differentiable graph matching layer adds 1.3 IDF1 versus removing it during training and 2.0 IDF1 versus removing it during both training and inference.The authors interpret this as evidence for the layer and jointly training all tracker components.Source: §5.3 · p. 7, Table 2 · p. 7

5.4. Discussions

  • Using only the last frame for tracklet appearance aggregation lowers IDF1 by 0.9; larger max age improves IDF1, while at 150 frames Hungarian matching loses 0.8 IDF1.GMTracker can match tracklets that disappeared about five seconds earlier; mean and moving-average aggregation using all frames have no significant impact difference.Source: §5.4 · pp. 7–8, Table 3 · p. 8, Table 4 · p. 8

5.5. Comparison with State-of-the-Art Methods

  • GMTracker achieves 63.8 IDF1 on MOT17 and 63.9 IDF1 on MOT16, outperforming other online trackers; CenterTrack detections yield 66.9 IDF1 on MOT17 and 68.6 IDF1 on MOT16.With linear interpolation, the paper reports outperforming other offline state-of-the-art trackers on IDF1; GMTCT simInt improves the state of the art on both datasets.Source: §5.5 · p. 8, Table 5 · p. 8

6. Conclusion

The paper presents GMTracker, a learnable graph-matching method for multiple object tracking. It incorporates second-order edge-to-edge similarity through a differentiable graph-matching layer, and reports that ablations and state-of-the-art comparisons support its effectiveness.

6. Conclusion

  • GMTracker models relationships between tracklets and detections using second-order edge-to-edge similarity, with graph matching relaxed to a convex QP and implemented as a differentiable layer.The conclusion reports greater accuracy and robustness, especially in crowded videos, and says ablation and state-of-the-art comparisons show the method's effectiveness.Source: §6 · p. 8

A. Gradients of the Graph Matching Layer

The appendix describes deriving gradients for the graph-matching layer and gives the GMTracker algorithm's inputs and output. The gradient derivation uses KKT conditions and the implicit function theorem.

A. Gradients of the Graph Matching Layer

  • Backward gradients for the graph-matching layer are derived from KKT conditions using the implicit function theorem.The appendix frames the optimal primal and dual variables through the KKT conditions and expresses gradients using Jacobians of the defining function.Source: A. Gradients of the Graph Matching Layer · p. 9

B. Pseudo-code of Our Algorithm

  • The GMTracker algorithm takes the current detection and tracklet sets as input and outputs the tracklet set for association in the next frame.The pseudocode passage also specifies a motion gate of 9.4877, camera-dependent feature-similarity thresholds, and a 100-frame max age.Source: B. Pseudo-code of Our Algorithm · p. 9

C.1. Comparison with the Oracle Tracker

The comparison with an Oracle tracker on MOT17 validation reports a remaining association gap. Detection-sensitive metrics show relatively small gaps among the baseline, GMTracker, and Oracle.

C.1. Comparison with the Oracle Tracker

  • Online GMTracker remains 5.7 IDF1 and about 1000 ID Switches from the Oracle tracker.The comparison is presented as an upper-bound exploration for association.Source: §C.1 · p. 9
  • Gaps among the baseline, GMTracker, and Oracle are relatively small for MOTA, FP, and FN, so the authors emphasize IDF1 and ID Switch for association.Source: §C.1 · pp. 9–10

C.2. Discussions

The discussion examines GMTracker’s tracklet-birth strategies, which mostly follow DeepSORT with some approach-specific improvements. It identifies the threshold σ as the most sensitive hyperparameter and evaluates its influence on several tracking measures.

C.2. Discussions

  • GMTracker’s tracklet-birth strategies mostly follow DeepSORT, with improvements described in the main paper.The passage does not specify those improvements.Source: §C.2 · p. 10
  • The threshold σ is the most sensitive hyperparameter among the three criteria for creating a new tracklet.Source: §C.2 · p. 10
  • Figure A examines how different σ values influence IDF1, FP, FN, and ID Switch.Source: §C.2 · p. 10

C.3. Detailed Performance

The detailed comparison covers MOT16 and MOT17 test sets and reports additional tracking metrics. Its table distinguishes online and near-online methods.

C.3. Detailed Performance

  • The detailed comparison includes HOTA, AssA, DetA, LocA, MT, and ML alongside other tracking metrics.Source: §C.3 · pp. 10–11
  • Table B provides detailed comparisons on the MOT16 and MOT17 test sets, distinguishing online and near-online methods.The caption defines (O) as online and (O*) as near-online.Source: §C.3 · p. 11

Related papers

Loading 2103.16178v1…