iccv iccv2013 iccv2013-200 iccv2013-200-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Chetan Arora, Amir Globerson
Abstract: This paper addresses the data assignment problem in multi frame multi object tracking in video sequences. Traditional methods employing maximum weight bipartite matching offer limited temporal modeling. It has recently been shown [6, 8, 24] that incorporating higher order temporal constraints improves the assignment solution. Finding maximum weight matching with higher order constraints is however NP-hard and the solutions proposed until now have either been greedy [8] or rely on greedy rounding of the solution obtained from spectral techniques [15]. We propose a novel algorithm to find the approximate solution to data assignment problem with higher order temporal constraints using the method of dual decomposition and the MPLP message passing algorithm [21]. We compare the proposed algorithm with an implementation of [8] and [15] and show that proposed technique provides better solution with a bound on approximation factor for each inferred solution.
[1] PSU HUB Dataset. Last visited: Feb 24, 2013. http : / / www . c s e .psu .edu / ˜ rco l ins / s o ftware .html . l
[2] M. Andriluka, S. Roth, and B. Schiele. People-tracking-bydetection and people-detection-by-tracking. In CVPR, 2008.
[3] G. Ausiello, M. Protasi, A. Marchetti-Spaccamela, G. Gambosi, P. Crescenzi, and V. Kann. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer-Verlag, 1st edition, 1999.
[4] J. Berclaz, F. Fleuret, E. Turetken, and P. Fua. Multiple ob- ject tracking using k-shortest paths optimization. 33(9), 2011. TPAMI, 9The source code of the implementation will be made available.
[5] D. P. Bertsekas. Nonlinear Programming. Athena Scientific, Belmont, MA, 1995.
[6] A. A. Butt and R. T. Collins. Multiple target tracking using frame triplets. In ACCV, 2012.
[7] A. A. Butt and R. T. Collins. Multi-target tracking by Lagrangian relaxation to min-cost network flow. In CVPR, pages 1846–1853, 2013.
[8] R. Collins. Multitarget data association with higher-order motion models. In CVPR, 2012.
[9] S. Deb, M. Yeddanapudi, K. Pattipati, and Y. Bar-Shalom. A generalized s-d assignment algorithm for multisensormultitarget state estimation. IEEE Trans. on Aerospace and Electronic Systems, 33(2):523–538, 1997.
[10] J. Duchi, D. Tarlow, G. Elidan, and D. Koller. Using combinatorial optimization within max-product belief propagation. In NIPS. 2007.
[11] A. Ess, B. Leibe, K. Schindler, , and L. van Gool. A mobile vision system for robust multi-person tracking. In CVPR, 2008.
[12] V. Jojic, S. Gould, and D. Koller. Accelerated dual decomposition for MAP inference. In ICML, pages 503–5 10, 2010.
[13] R. M. Karp. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, pages 85–103. 1972.
[14] N. Komodakis, N. Paragios, and G. Tziritas. MRF energy minimization and beyond via dual decomposition. TPAMI, 33(3):531–552, 2011.
[15] M. Leordeanu and M. Hebert. A spectral technique for cor-
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25] respondence problems using pairwise constraints. In ICCV, 2005. O. Meshi, T. Jaakkola, and A. Globerson. Convergence rate analysis of MAP coordinate minimization algorithms. In NIPS. MIT Press, 2012. I. Necoara and J. A. K. Suykens. Application of a smoothing technique to decomposition in convex optimization. IEEE Trans. on Automatic Control, 53(1 1):2674–2679, 2008. Y. Nesterov. Smooth minimization of non-smooth functions. Math. Prog., 103(1): 127–152, May 2005. A. B. Poore. Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking. Comput. Opt. Appl. , 3(1):27–57, Mar. 1994. A. M. Rush and M. Collins. A tutorial on dual decomposition and Lagrangian relaxation for inference in natural language processing. J. Artif. Int. Res., 45(1):305–362, Sept. 2012. D. Sontag, A. Globerson, and T. Jaakkola. Introduction to dual decomposition for inference. In Optimization for Machine Learning. MIT Press, 2011. B. Taskar, S. Lacoste-Julien, and M. I. Jordan. Structured prediction, dual extragradient and Bregman projections. JMLR, 7: 1627–1653, 2006. C. J. Veenman, M. J. T. Reinders, and E. Backer. Resolving motion correspondence for densely moving points. TPAMI, 23(1):54–72, 2001. A. R. Zamir, A. Dehghan, and M. Shah. GMCP-Tracker: global multi-object tracking using generalized minimum clique graphs. In ECCV, 2012. L. Zhang, Y. Li, and R. Nevatia. Global data association for multi-object tracking using network flows. In CVPR, 2008. 184