Rank-1 tensor approximation for high-order association in multi-target tracking. (English) Zbl 1477.68423
Summary: High-order motion information is important in multi-target tracking (MTT) especially when dealing with large inter-target ambiguities. Such high-order information can be naturally modeled as a multi-dimensional assignment (MDA) problem, whose global solution is however intractable in general. In this paper, we propose a novel framework to the problem by reshaping MTT as a rank-1 tensor approximation problem (R1TA). We first show that MDA and R1TA share the same objective function and similar constraints. This discovery opens a door to use high-order tensor analysis for MTT and suggests the exploration of R1TA. In particular, we develop a tensor power iteration algorithm to effectively capture high-order motion information as well as appearance variation. The proposed algorithm is evaluated on a diverse set of datasets including aerial video sequences containing ariel borne dense highway scenes, top-view pedestrian trajectories, multiple similar objects, normal view pedestrians and vehicles. The effectiveness of the proposed algorithm is clearly demonstrated in these experiments.
Keywords:
multi-target tracking; multi-dimensional assignment; rank-1 tensor approximation; data associationSoftware:
KITTIReferences:
| [1] | Andriluka, M., Roth, S., & Schiele, B. (2008). People-tracking-by-detection and people-detection-by-tracking. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [2] | Bae, S.-H., & Yoon, K.-J. (2014). Robust online multi-object tracking based on tracklet confidence and online discriminative appearance learning. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [3] | Ban, Y., Ba, S., Alameda-Pineda, X., & Horaud, R. (2016). Tracking multiple persons based on a variational bayesian model. In Proceedings of European conference on computer vision. |
| [4] | Bar-Shalom, Y., & Fortmann, T. (1988). Tracking and data association. London: Academic Press. · Zbl 0634.93001 |
| [5] | Benfold, B., & Reid, I. (2011). Stable multi-target tracking in real-time surveillance video. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [6] | Berclaz, J., Fleuret, F., Turetken, E., & Fua, P. (2011). Multiple object tracking using k-shortest paths optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(9), 1806-1819. · doi:10.1109/TPAMI.2011.21 |
| [7] | Bernardin, K., & Stiefelhagen, R. (2008). Evaluating multiple object tracking performance: The clear mot metrics. EURASIP Journal on Image and Video Processing, 2008, 246309. · doi:10.1155/2008/246309 |
| [8] | Black, J., Ellis, T., & Rosin, P. (2002). Multi view image surveillance and tracking. In Workshop motion and video computing: Proceedings . |
| [9] | Blackman, S., & Popoli, R. (1999). Design and analysis of modern tracking systems. Norwood, MA: Artech House. · Zbl 0933.93002 |
| [10] | Breitenstein, M. D., Reichlin, F., Leibe, B., Koller-Meier, E., & Van Gool, L. (2011). Online multi-person tracking-by-detection from a single, uncalibrated camera. IEEE Transactions on Pattern Analysis and Machine Interlligence, 33(9), 1820-1833. · doi:10.1109/TPAMI.2010.232 |
| [11] | Butt, A., & Collins, R. T. (2012). Multiple target tracking using frame triplets. In Proceedings of Asian conference computer vision. |
| [12] | Butt, A., & Collins, R. T. (2013). Multi-target tracking by lagrangian relaxation to min-cost network flow. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [13] | Chari, V., Julien, S. L., Laptev, I., & Sivic, J. (2015). On pairwise costs for network flow multi-object tracking. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [14] | Collins, R. T. (2012). Multitarget data association with higher-order motion models. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [15] | Cox, I. (1993). A review of statistical data association techniques for motion correspondence. International Journal Computer Vision, 10(1), 53-66. · doi:10.1007/BF01440847 |
| [16] | Dalal, N., & Triggs, B. (2005). Histograms of oriented gradients for human detection. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [17] | Deb, S., Yeddanapudi, M., Pittipati, K., & Bar-Shalom, Y. (1997). A generalized S-D assignment algorithm for multi-sensor multi-target state estimation. IEEE Transactions Aerospace and Electronic Systems, 33(2), 523-538. · doi:10.1109/7.575891 |
| [18] | Dehghan, A., Modiri, S., & Shah, M. (2015). GMMCP tracker: Globally optimal generalized maximum multi clique problem for multiple object tracking. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [19] | De Lathauwer, L., De Moor, B., & Vandewalle, J. (2000). On the best rank-1 and rank-\[(R_1\] R \[1, R_2\] R2,., \[R_N\] RN) approximation of higher-order tensors. SIAM Journal on Matrix Analysis and Applications, 21(4), 1324-1342. · Zbl 0958.15026 · doi:10.1137/S0895479898346995 |
| [20] | Dicle, C., Sznaier, M., & Camps, O. (2013). The way they move: Tracking multiple targets with similar appearance. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [21] | Duchenne, O., Bach, F., Kweon, I., & Ponce, J. (2011). A tensor-based algorithm for high-order graph matching. IEEE Transactions on Pattern Analysis and Machine Interlligence, 33(12), 2383-2395. · doi:10.1109/TPAMI.2011.110 |
| [22] | Felzenszwalb, P., Girshick, R., McAllester, D., & Ramanan, D. (2010). Object detection with discriminatively trained part-based models. IEEE Transactions on Pattern Analysis and Machine Interlligence, 32(9), 1627-1645. · doi:10.1109/TPAMI.2009.167 |
| [23] | Fortmann, T. E., Bar-Shalom, Y., & Scheffe, M. (1980). Multi-target tracking using joint probabilistic data association. In Proceedings of the IEEE conference on decision and control (Vo. 19, pp. 807-812). |
| [24] | Ge, W., Collins, R. T., & Ruback, R. (2012). Vision-based analysis of small groups in pedestrian crowds. IEEE Transactions on Pattern Analysis and Machine Interlligence, 34(5), 1003-1016. · doi:10.1109/TPAMI.2011.176 |
| [25] | Geiger, A., Lenz, P., & Urtasun, R. (2012). Are we ready for autonomous driving?. In Proceedings of the IEEE conference on Computer vision and pattern recognition: The KITTI vision benchmark suite. |
| [26] | Huang, C., Wu, B., & Nevatia, R. (2008). Robust object tracking by hierarchical association of detection responses. In Proceedings of European conference on computer vision. |
| [27] | Jiang, H., Fels, S., & Little, J. (2007). A linear programming approach for multiple object tracking. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [28] | Kumar, K. C. A., & Vleeschouwer, C. (2013). Discriminative label propagation for multi-object tracking with sporadic appearance features. In Proceedings of IEEE conference on computer vision. |
| [29] | Le, N., Heili, A., & Odobez, J. (2016). Long-term time-sensitive costs for crf-based tracking by detection. In Proceedings of European conference on computer vision. |
| [30] | Leal-Taixé, L., Canton-Ferrer, C., & Schindler, K. (2016). Learning by tracking: Siamese CNN for robust target association. In Proceedings of IEEE conference on computer vision and pattern recognition workshops. |
| [31] | Leal-Taixé, L., Milan, A., Reid, I., Roth, S., & Schindler, K. (2015). MOTChallenge 2015: Towards a benchmark for multi-target tracking. arXiv:1504.01942 [cs]. |
| [32] | Lenz, P., Geiger, A., & Urtasun, R. (2015). FollowMe: Efficient online min-cost flow tracking with bounded memory and computation. In Proceedings of IEEE international conference on computer vision. |
| [33] | Li, Y., Huang, C., & Nevatia, R. (2009). Learning to associate: Hybridboosted multi-target tracker for crowded scene. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [34] | Luo, W., Xing, J., Zhang, X., Zhao, X., & Kim, T.-K.(2014). Multiple object tracking: A review. arXiv:1409.7618. |
| [35] | Milan, A., Rezatofighi, S., Dick, A., Reid, I., & Schindler, K. (2017). Online multi-target tracking using recurrent neural networks. In Proceedings of AAAI. |
| [36] | Milan, A., Roth, S., & Schindler, K. (2014). Continuous energy minimization for multitarget tracking. IEEE Transactions on Pattern Analysis and Machine Interlligence, 36(1), 58-72. · doi:10.1109/TPAMI.2013.103 |
| [37] | Milan, A., Schindler, K., & Roth, S. (2016). Multi-target tracking by discrete-continuous energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(10), 2054-2068. · doi:10.1109/TPAMI.2015.2505309 |
| [38] | Oh, S., Russell, S., & Sastry, S. (2009). Markov chain monte carlo data association for multi-target tracking. IEEE Transactions on Automatic Control, 54(3), 481-497. · Zbl 1367.93655 · doi:10.1109/TAC.2009.2012975 |
| [39] | Okuma, K., Taleghani, A., Freitas, O. D., Little, J. J., & Lowe, D. G. (2004). A boosted particle filter: Multitarget detection and tracking. In Proceedings of European conference on computer vision. · Zbl 1098.68832 |
| [40] | Pirsiavash, H., Ramanan, D., & Fowlkes, C. (2011). Globally-optimal greedy algorithms for tracking a variable number of objects. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [41] | Poore, A. (1994). Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking. Computational Optimization and Applications, 3(1), 27-57. · Zbl 0818.93070 · doi:10.1007/BF01299390 |
| [42] | Possegger, H., Mauthner, T., Roth, P. M., & Bischof, H. (2014). Occlusion geodesics for online multi-object tracking. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [43] | Regalia, P., & Kofidis, E. (2000). The higher-order power method revisited: Convergence proofs and effective initialization. In Proceedings of IEEE international conference on acoustics speech and signal processing. |
| [44] | Reid, D. (1979). An algorithm for tracking multiple targets. IEEE Transactions on Automatic Control, 24(6), 843-854. · doi:10.1109/TAC.1979.1102177 |
| [45] | Ricardo, S., Fabio, P., & Andrea, C. (2016). Online multi-target tracking with strong and weak detections. In Computer vision: European conference. |
| [46] | Schulter, S., Vernaza, P., Choi, W., & Chandraker, M. (2017). Deep network flow for multi-object tracking. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [47] | Shafique, K., Lee, M., & Haering, N. (2008). A rank constrained continuous formulation of multi-frame multi-target tracking problem. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [48] | Shafique, K., & Shah, M. (2005). A noniterative greedy algorithm for multiframe point correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(1), 51-65. · doi:10.1109/TPAMI.2005.1 |
| [49] | Shi, X., Ling, H., Blash, E., & Hu, W. (2012). Context-driven moving vehicle detection in wide area motion imagery. In Proceedings of IEEE International conference on pattern recognition. |
| [50] | Shi, X., Ling, H., Xing, J., & Hu, W. (2013). Multiple target tracking by rank-1 tensor approximation. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [51] | Sinkhorn, R. (1964). A relationship between arbitrary positive matrices and doubly stochastic matrices. The Annals of Mathematical Statistics, 35, 876-879. · Zbl 0134.25302 · doi:10.1214/aoms/1177703591 |
| [52] | Son, J., Baek, M., Cho, M., & Han, B. Y. (2017). Multi-object tracking with quadruplet convolutional neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition. |
| [53] | Tang, S., Andres, B., Andriluka, M., & Schiele, B. (2015). Subgraph decomposition for multitarget tracking. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [54] | Tang, S., Andres, B., Andriluka, M., & Schiele, B. (2016). Multi-person tracking by multicut and deep matching. In Computer vision: European conference. |
| [55] | The CLIF dataset. (2006). www.sdms.afrl.af.mil/index.php?collectionHrB=clifHrB. |
| [56] | Wang, B., Wang, L., Shuai, B., Zhen, Z., Liu, T., Chan, K. C., et al. (2016). Joint learning of convolutional neural networks and temporally constrained metrics for tracklet association. In Proceedings of IEEE conference on computer vision and pattern recognition workshops. |
| [57] | Wang, S., & Fowlkes, C. (2016). Learning optimal parameters for multi-target tracking with contextual interactions. In International journal of computer vision. |
| [58] | Wen, L., Li, W., Yan, J., Lei, Z., Yi, D., & Li, S. Z. (2014). Multiple target tracking based on undirected hierarchical relation hypergraph. In Proceedings of IEEE conference on computer vision and pattern recognition. |
| [59] | Yang, B., & Nevatia, R. (2012a). Multi-target tracking by online learning of non-linear motion patterns and robust appearance models. In Proceedings of IEEE conference on computer vision and pattern recognition. · Zbl 1294.68138 |
| [60] | Yang, B., & Nevatia, R. (2012b). An online learned crf model for multi-target tracking. In Proceedings of IEEE conference on computer vision and pattern recognition. · Zbl 1294.68138 |
| [61] | Yu, Q., & Medioni, G. (2009). Multiple target tracking by spatiotemporal monte carlo markov chain data association. IEEE Transactions on Automatic Control, 31(12), 2196-2210. |
| [62] | Zamir, A., Dehghan, A., & Shah, M. (2012). GMCP-tracker: Global multi-object tracking using generalized minimum clique graphs. In Proceedings of European conference on computer vision. |
| [63] | Zhang, L., Li, Y., & Nevatia, R. (2008). Global data association for multi-object tracking using network flows. In Proceedings of IEEE conference on computer vision and pattern recognition. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
