GMMCP-Tracker: Globally Optimal Generalized Maximum Multi Clique Problem for Multiple Object Tracking
- Introduction
- GMCP vs GMMCP
- Qualitative Results
- Quantitative Results
- Full Presentation
- Tracking Output and Groundtruth
- Code
- Parking Lot Pizza
- Related Publications
Introduction

Data association is the backbone to many multiple object
tracking (MOT) methods. In this paper we formulate
data association as a Generalized Maximum Multi Clique
problem (GMMCP). We show that this is the ideal case of
modeling tracking in real world scenario where all the pairwise
relationships between targets in a batch of frames are
taken into account. Previous works assume simplified version
of our tracker either in problem formulation or problem
optimization. However, we propose a solution using
GMMCP where no simplification is assumed in either steps.
We show that the NP hard problem of GMMCP can be formulated
through Binary-Integer Program where for small
and medium size MOT problems the solution can be found
efficiently. We further propose a speed-up method, employing
Aggregated Dummy Nodes for modeling occlusion and
miss-detection, which reduces the size of the input graph
without using any heuristics. We show that, using the speedup
method, our tracker lends itself to real-time implementation
which is plausible in many applications. We evaluated
our tracker on six challenging sequences of Town Center,
TUD-Crossing, TUD-Stadtmitte, Parking-lot 1, Parking-lot
2 and Parking-lot pizza and show favorable improvement
against state of art.
GMCP vs GMMCP

There are core differenece between GMCP and GMMCP tracker: First GMCP tracker does not follow a joint
optimization for all the tracks simultaneously and finds the
tracks one by one while this is not the case in GMMCP tracker. In addition, the solver use in GMCP tracker follows
a greedy local neighborhood search which is prone to local
minima. On the other hand we propose to solve the NP hard problem of GMMCP directly through BIP without relaxing the original problem.
Finaly the heuristic line fitting approach for
removing outliers make the tracks prone to ID-switch especially
when people are walking close to each other. In this paper we propose a more efficient way of addressing the occlusiong thorugh our aggregated dummy nodes. We also show that
GMMCP lends itself to a real time implementation for small and medium size MOT problems.
Qualitative Results
Quantitative Results
For quantitative evaluation we used 30% overlap threshold.
Full Presentation
20-Minute presentation of the full paper by Afshin Dehghan
Tracking Output and Groundtruth
Download all
Parking Lot 1:
Tracking Output
Groundtruth
Parking Lot 2:
Tracking Output
Groundtruth
Parking Lot Pizza:
Tracking Output
Groundtruth
TUD Stadtmitte:
Tracking Output
Groundtruth
TUD Crossing:
Tracking Output
Groundtruth
Code
Please Contact AuthorPowerPoint
Click herePoster
Click hereParking Lot Pizza
The Parking Lot Pizza sequence can be downloaded here.Related Publications
Afshin Dehghan, Shayan Modiri Assari and Mubarak Shah, GMMCP-Tracker:Globally Optimal Generalized Maximum Multi Clique Problem for Multiple Object Tracking IEEE International Conference on Computer Vision and Pattern Recognition, 2015. [PDF], [BibTeX]Ergys Ristani, Carlo Tomasi, "Tracking Multiple People Online and in Real Time", ACCV2014
Amir Roshan Zamir, Afshin Dehghan, and Mubarak Shah, GMCP-Tracker: Global Multi-object Tracking Using Generalized Minimum Clique Graphs, European Conference on Computer Vision (ECCV), 2012. [PDF], [BibTeX]
Afshin Dehghan, Yicong Tian, Philip. H. S. Torr and Mubarak Shah, Target Identity-aware Network Flow for Online Multiple Target Tracking IEEE International Conference on Computer Vision and Pattern Recognition, 2015. [PDF], [BibTeX]
Afshin Dehghan, Haroon Idrees, Amir Roshan Zamir, and Mubarak Shah, (In alphabetical order) Keynote: Automatic Detection and Tracking of Pedestrians in Videos with Various Crowd Densities
In Proceedings of PED, June 2012, [PDF], [BibTeX]