Higher-Order Multiple Object Tracking

Produktbeschreibung

This dissertation deals with camera-based offline multiple object tracking and explores higher-order data association models. Due to their extensive exploitation of the available information, such models are promising approaches in current research. However, they commonly represent NP-hard optimization problems so that their application in practice is challenging.
The first part of this thesis proposes a binary quadratic program that enables to globally fuse signals within a higher-order data association model. This enables to overcome weaknesses of the individual signals. An approximate solver based on the Frank-Wolfe algorithm is presented and analyzed. Its benefit is demonstrated in two setups: fusion of two detectors and combining signals coming from a video and body-worn inertial measurement units. The second part of this thesis proposes an extension of the disjoint path model by higher-order information and connectivity priors, resulting in a binary linear program. Efficient separation algorithms are proposed and integrated into a cutting-plane algorithm, making it possible for the first time to solve higher-order data association globally in practice.

Contents

1 Introduction 1
1.1 Applications . . . . . . . . 1
1.2 The Multiple Object Tracking Problem . . . . . . 3
1.2.1 Video-based Multiple Object Tracking (MOT) . . . . . . 4
1.2.2 Tracking-by-detection . . . . . . . 7
1.3 Challenges of Multiple Object Tracking . . . . . . 11
1.3.1 Errors caused by the object detector . . . . . . 12
1.3.2 Challenges in discriminative features .. . . . . 13
1.3.3 Combinatorial challenges . . . . . . . . . . . . 16
1.4 Related Work . . . . . . 18
1.5 Contributions .. . . . . . . 21
1.6 List of Publications . . . . 26
1.7 Outline . . . . . . . . . . 30
2 Fundamentals 33
2.1 Sets, Maps, and Matrices . . . . . . . 33
2.2 Probability Theory . . . . . . . . . . 34
2.3 Graph Theory . . . . . . . . . . . . . 34
2.3.1 Important graph classes . . . . . . . 36
2.3.2 Computations on graphs . . . . . . . 37
2.4 Machine Learning . . . . . . . . . . . 38
2.4.1 Supervised learning . . . . . . . . . 39
2.4.2 Logistic regression . . . . . . . . . 40
2.4.3 Neural networks . . . . . . . . . . . 41
2.5 Computational Complexity Theory . . . . 47
2.6 Optimization Theory . . . . . . . . . . 52
2.6.1 Linear programming . . . . . .. . . . 52
2.6.2 Binary linear programming . . . . . . 54
2.6.3 Quadratic programming . . . . . . . . 59
2.6.4 Binary quadratic programming .. . . . 60
2.6.5 Non-linear optimization . . . . . . . 61
2.7 Multi-Object Tracking . . . . . . . . . 61
2.7.1 Object detectors . . . . . . .. . . . 61
2.7.2 Appearance features . . . . . . . . . 66
2.7.3 Datasets . . . . . . . . . . . . .. . 75
2.7.4 MOT metrics . . . . . . . . . . . . . 76
3 HO-MOT with Signal Fusion 80
3.1 Introduction . . . . . . . . . . . . .. 81
3.2 Signal Fusion as Weighted Graph Labeling Problem . . . . . . . 83
3.2.1 Related work . . . . . . . . . . . . 84
3.2.2 Data association model for signal fusion . . . . . . . . . . 84
3.3 Frank-Wolfe Optimizer for Weighted Graph Labeling Problems . . 89
3.3.1 Related work . . . . . . . . . . . . 90
3.3.2 Frank-Wolfe Optimizer for Binary Solutions . . . . . . .. . . 91
3.4 Multiple People Tracking by Fusing Head and People Detections . . . 98
3.4.1 Data association model . . . . . . . 99
3.4.2 Experimental results . . . . . . . . 102
3.5 Simultaneous Identification and Tracking of Multiple People using Video and IMUs . . . . . 106
3.5.1 Related work . . . . . . . . . . . . 110
3.5.2 Method . . . . . . . . . . . . . . . 112
3.5.3 Evaluation . . . . . . . . . . . . . 117
3.6 Conclusion . . . . . . . . . . . . . . 127
4 Lifted Disjoint Paths 130
4.1 Introduction . . . . . . . . . . . . . 131
4.2 Related Work . . . . . . . . . . . . . 132
4.3 Problem Formulation . . . . . . . . . 134
4.4 Constraints . . . . . . . . . . . . . 135
4.5 Separation . . . . . . . . . . . . . . 144
4.6 Complexity . . . . . . . . . . . . . . 146
4.7 Experiments . . . . . . . . . . . . . 150
4.7.1 Graph construction. . . . . . . . . 150
4.7.2 Pre-processing and post-processing . . . . 151
4.7.3 Cost learning . . . . . . . . . . . . . . . 152
4.7.4 Implementation details on the lifted disjoint paths solver . . . . 156
4.7.5 Experiment setup . . . . . . . . . . . . . 156
4.7.6 Benefit of long-range edges . . . . . . . . 157
4.7.7 Ablation study on post-processing methods. . . . . . . . 157
4.7.8 Accuracy of the fusion network . . . . . . 159
4.7.9 Qualitative evaluations . . . . . . . . . . 159
4.7.10 Benchmark evaluations . . . . . . . . . . 160
4.8 Conclusion . . . . . . . . . . . . . . . . . 161
5 Conclusions 165
Bibliography 172

Keywords: Verfolgung Mehrerer Objekte, Binäres Lineares Programm (BLP), Binäres Quadratisches Programm (BQP), Datenassoziationsmodel Höherer Ordnung, Globale Optimierung, Video, Sensorfusion, Inertiale Messeinheit, Multiple Object Tracking, Binary Linear Programming (BLP), Binary Quadratic Programming (BQP), Higher-Order Data Association Model, Global Optimization, Video, Sensor Fusion, Inertial Sensors