---
title: "Online Multi-Object Tracking by Quadratic Pseudo-Boolean Optimization"
authors:
  - "Long Lan"
  - "Dacheng Tao"
  - "Chen Gong"
  - "Naiyang Guan"
  - "Zhigang Luo"
doi: ""
url: "https://ijcai.org/proceedings/2016/480"
pdf: "https://ijcai.org/proceedings/2016/0480.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "3396-3401"
track: ""
keywords:
---

# Online Multi-Object Tracking by Quadratic Pseudo-Boolean Optimization

Long Lan, Dacheng Tao, Chen Gong, Naiyang Guan, Zhigang Luo

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 3396-3401.

## Abstract

Online multi-object tracking (MOT) is challenging: frame-by-frame matching of detection hypotheses to the correct trackers can be difficult. The Hungarian algorithm is the most commonly used online MOT data association method due to its rapid assignment; however, the Hungarian algorithm simply considers associations based on an affinity model. For crowded scenarios, frequently occurring interactions between objects complicate associations, and affinity-based methods usually fail in these scenarios. Here we introduce quadratic pseudo-Boolean optimization (QPBO) to an online MOT model to analyze frequent interactions. Specifically, we formulate two useful interaction types as pairwise potentials in QPBO, a design that benefits our model by exploiting informative interactions and allowing our online tracker to handle complex scenes. The auxiliary interactions result in a non-submodular QPBO, so we accelerate our online tracker by solving the model with a graph cut combined with a simple heuristic method. This combination achieves a reasonable local optimum and, importantly, implements the tracker efficiently. Extensive experiments on publicly available datasets from both static and moving cameras demonstrate the superiority of our method.