TU Darmstadt / ULB / TUprints

Energy Minimization for Multiple Object Tracking

Milan, Anton (2013)
Energy Minimization for Multiple Object Tracking.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
milan-phd.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (29MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Energy Minimization for Multiple Object Tracking
Language: English
Referees: Roth, Prof. Dr. Stefan ; Schindler, Prof. Dr. Konrad ; Laptev, Dr. Ivan
Date: 4 April 2013
Place of Publication: Darmstadt
Date of oral examination: 16 May 2013
Abstract:

Multiple target tracking aims at reconstructing trajectories of several moving targets in a dynamic scene, and is of significant relevance for a large number of applications. For example, predicting a pedestrian’s action may be employed to warn an inattentive driver and reduce road accidents; understanding a dynamic environment will facilitate autonomous robot navigation; and analyzing crowded scenes can prevent fatalities in mass panics. The task of multiple target tracking is challenging for various reasons: First of all, visual data is often ambiguous. For example, the objects to be tracked can remain undetected due to low contrast and occlusion. At the same time, background clutter can cause spurious measurements that distract the tracking algorithm. A second challenge arises when multiple measurements appear close to one another. Resolving correspondence ambiguities leads to a combinatorial problem that quickly becomes more complex with every time step. Moreover, a realistic model of multi-target tracking should take physical constraints into account. This is not only important at the level of individual targets but also regarding interactions between them, which adds to the complexity of the problem. In this work the challenges described above are addressed by means of energy minimization. Given a set of object detections, an energy function describing the problem at hand is minimized with the goal of finding a plausible solution for a batch of consecutive frames. Such offline tracking-by-detection approaches have substantially advanced the performance of multi-target tracking. Building on these ideas, this dissertation introduces three novel techniques for multi-target tracking that extend the state of the art as follows: The first approach formulates the energy in discrete space, building on the work of Berclaz et al. (2009). All possible target locations are reduced to a regular lattice and tracking is posed as an integer linear program (ILP), enabling (near) global optimality. Unlike prior work, however, the proposed formulation includes a dynamic model and additional constraints that enable performing non-maxima suppression (NMS) at the level of trajectories. These contributions improve the performance both qualitatively and quantitatively with respect to annotated ground truth. The second technical contribution is a continuous energy function for multiple target tracking that overcomes the limitations imposed by spatial discretization. The continuous formulation is able to capture important aspects of the problem, such as target localization or motion estimation, more accurately. More precisely, the data term as well as all phenomena including mutual exclusion and occlusion, appearance, dynamics and target persistence are modeled by continuous differentiable functions. The resulting non-convex optimization problem is minimized locally by standard conjugate gradient descent in combination with custom discontinuous jumps. The more accurate representation of the problem leads to a powerful and robust multi-target tracking approach, which shows encouraging results on particularly challenging video sequences. Both previous methods concentrate on reconstructing trajectories, while disregarding the target-to-measurement assignment problem. To unify both data association and trajectory estimation into a single optimization framework, a discrete-continuous energy is presented in Part III of this dissertation. Leveraging recent advances in discrete optimization (Delong et al., 2012), it is possible to formulate multi-target tracking as a model-fitting approach, where discrete assignments and continuous trajectory representations are combined into a single objective function. To enable efficient optimization, the energy is minimized locally by alternating between the discrete and the continuous set of variables. The final contribution of this dissertation is an extensive discussion on performance evaluation and comparison of tracking algorithms, which points out important practical issues that ought not be ignored.

Alternative Abstract:
Alternative AbstractLanguage

Multi-target Tracking beschäftigt sich mit der Problemstellung, mehrere Objekte in einer dynamischen Szene zu verfolgen und ist für eine Vielzahl von Anwendungen relevant. Im Straßenverkehr kann beispielsweise die Absicht eines Fußgängers von einem Fahrzeug aus erkannt werden, um einen unachtsamen Autofahrer zu warnen und somit Verkehrsunfälle zu reduzieren. Ein weiteres Beispiel ist die Navigation autonomer Roboter, die ein Verständnis der dynamischen Umgebung voraussetzt. Schließlich können Todesopfer bei Massenpaniken durch eine automatisierte Analyse von Menschenmassen vermieden werden. Bei dieser Problemstellung gibt es jedoch zahlreiche Herausforderungen. Zunächst sind visuelle Daten oft mehrdeutig. Beispielsweise können Objekte aufgrund schlechter Kontrastverhältnisse oder bei Verdeckung unerkannt bleiben. Des Weiteren werden durch objektähnliche Strukturen im Hintergrund Fehldetektionen verursacht, die den Trackingalgorithmus stören. Eine zweite Herausforderung entsteht dann, wenn mehrere Messungen nahe beieinander liegen. Das Auflösen der Mehrdeutigkeiten führt zu einem kombinatorischen Problem, dessen Komplexität mit jedem Zeitschritt rasant ansteigt. Zusätzlich sollen physikalische Rahmenbedingungen erfüllt werden, welche sich nicht nur auf einzelne Trajektorien erstrecken, sondern auch auf deren Zusammenspiel. Diese Dissertation befasst sich mit dem Ansatz der Energieminimierung, um den oben genannten Herausforderungen zu begegnen. Ausgehend von einer Menge an Objektdetektionen wird eine Energiefunktion, welche das vorliegende Problem umschreibt, minimiert, um eine geeignete Lösung für eine vorgegebene Bildsequenz zu finden. Solche Tracking-by-Detection Ansätze haben erheblich zum Fortschritt des Multi-Target-Trackings beigetragen. Diese Arbeit baut auf diesen Grundideen auf und stellt drei neue Methoden vor, die den Stand der Technik wie folgt erweitern: Der erste Ansatz basiert auf der Arbeit von Berclaz et al. (2009) und formuliert die Energie im diskreten Raum. Die zulässigen Objektpositionen werden dabei auf ein regelmäßiges Gitter beschränkt und die Objektverfolgung wird als ganzzahlige lineare Programmierung formuliert. Im Gegensatz zu früheren Ansätzen beinhaltet die hier vorgestellte Methode ein dynamisches Modell sowie zusätzliche Zwangsbedingungen, die es erlauben, schwächere Hypothesen direkt auf der Ebene der Trajektorien zu unterdrücken. Diese Erweiterungen verbessern die Ergebnisse sowohl qualitativ als auch quantitativ hinsichtlich annotierter Ground-Truth-Daten. Der zweite technische Beitrag ist eine stetige Energiefunktion, die durch die Diskretisierung entstehende Einschränkungen überwindet. Die kontinuierliche Formulierung kann viele wichtige Aspekte des Multi-Target-Trackings, wie etwa Objektlokalisierung oder Bewegungsschätzung, exakter erfassen. Im Einzelnen werden der Datenterm und Phänomene wie gegenseitige Kollisionen und Verdeckung, das Aus- sehen, die Dynamik und die Langlebigkeit der Objekte als stetige, differenzierbare Funkionen modelliert. Das daraus resultierende nicht-konvexe Optimierungsproblem wird lokal mittels Verfahren der konjugierten Gradienten in Kombination mit speziell angepassten Sprün- gen minimiert. Die sorgfältigere Problembeschreibung stellt ein robustes Verfahren zur Verfolgung mehrerer Objekte dar und zeigt vielversprechende Ergebnisse auf besonders anspruchsvollen Videosequenzen. Die beiden oben genannten Ansätze fokussieren sich auf die Rekonstruktion der Trajektorien und lassen dabei die Zuweisungsaufgabe außer Acht. Um sowohl das Korrespondenzproblem als auch die Schätzung der Trajektorien in einem Optimierungsproblem zu vereinen, wird im dritten Teil dieser Dissertation eine diskret-kontinuierliche Energie präsentiert. Aktuelle Fortschritte in der diskreten Optimierung (Delong et al., 2012) ermöglichen es, Multi-Target-Tracking auf eine Art zu formulieren, bei der eine diskrete Zuordnung und eine kontinuierliche Repräsentation des Zustands in einer gemeinsamen Zielfunktion vereint werden. Um eine effiziente Optimierung zu ermöglichen, wird die Energie alternierend zwischen den beiden Variablenmengen lokal minimiert. Im abschließenden Teil werden wichtige Aspekte diskutiert, die beim Evaluieren und beim Vergleich unterschiedlicher Tracking-Methoden auftauchen, und die nicht vernachlässigt werden sollten.

German
Uncontrolled Keywords: Computer vision, surveillance, multi-target tracking
URN: urn:nbn:de:tuda-tuprints-34630
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Interactive Graphics Systems
Date Deposited: 04 Feb 2014 10:51
Last Modified: 09 Jul 2020 00:28
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/3463
PPN: 386311986
Export:
Actions (login required)
View Item View Item