Skip to main content

GMMCP-Tracker: Globally Optimal Generalized Maximum Multi Clique Problem for Multiple Object Tracking


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.


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

Parking Lot 2:
Tracking Output

Parking Lot Pizza:
Tracking Output

TUD Stadtmitte:
Tracking Output

TUD Crossing:
Tracking Output


Please Contact Author


Click here


Click here

Parking 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 GraphsEuropean 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]