Multitarget Tracking Algorithm Based on Adaptive Network Graph Segmentation in the Presence of Measurement Origin Uncertainty
Abstract
:1. Introduction
2. Problem Formulation
3. Description of the A* Search Algorithm
- Step 1
- Initialization:Set , ; , , ; , .
- Step 2
- Node Selection:Choose , , .
- Step 3
- Stop Rule:If , then stop. otherwise, continue.
- Step 4
- Update and :For each : If , then ;.If , . Go back to Step 2.
4. Multitarget Tracking Algorithm Based on Adaptive Network Graph Segmentation
4.1. Adaptive Spectral Clustering
4.2. k-Short Paths Algorithm
4.3. Track Mosaic
4.4. Rauch–Tung–Striebel Smoother
4.5. Time Complexity
5. Experimental Results
5.1. Clustering Quality Evaluation
5.2. Performance Analysis
5.3. Run Time
6. Conclusions
Author Contributions
Funding
Acknowledgments
Conflicts of Interest
References
- Challa, S.; Morelande, M.R.; Mušicki, D.; Evans, R.J. Fundamentals of Object Tracking; Cambridge University Press: Cambridge, UK, 2011. [Google Scholar]
- Mallick, M.; Arulampalam, S.; Yan, Y.; Ru, J. Three-Dimensional Tracking of an Aircraft Using Two-Dimensional Radars. IEEE Trans. Aerosp. Electron. Syst. 2018, 54, 585–600. [Google Scholar] [CrossRef]
- Rodriguez, D.; Aceros, C.; Valera, J.; Anaya, E. A Framework for Multiple Object Tracking in Underwater Acoustic MIMO Communication Channels. J. Sens. Actuator Netw. 2017, 6, 2. [Google Scholar] [CrossRef]
- Hoak, A.; Medeiros, H.; Povinelli, R.J. Image-Based Multi-Target Tracking through Multi-Bernoulli Filtering with Interactive Likelihoods. Sensors 2017, 17, 501. [Google Scholar] [CrossRef] [PubMed]
- Banfi, J.; Guzzi, J.; Amigoni, F.; Flushing, E.F.; Giusti, A.; Gambardella, L.; Caro, G.A.D. An integer linear programming model for fair multitarget tracking in cooperative multirobot systems. Auton. Robots 2018, 1–16. [Google Scholar] [CrossRef]
- Beard, M.; Vo, B.T.; Vo, B.N. A Solution for Large-scale Multi-object Tracking. arXiv, 2018; arXiv:1804.06622. [Google Scholar]
- Chen, H.; Li, X.R.; Bar-Shalom, Y. On joint track initiation and parameter estimation under measurement origin uncertainty. IEEE Trans. Aerosp. Electron. Syst. 2004, 40, 675–694. [Google Scholar] [CrossRef] [Green Version]
- Huang, Y.; Zhang, Y.; Shi, P.; Wu, Z.; Qian, J.; Chambers, J.A. Robust Kalman Filters Based on Gaussian Scale Mixture Distributions with Application to Target Tracking. IEEE Trans. Syst. Man Cybern. Syst. 2017, 1–15. [Google Scholar] [CrossRef]
- Oh, S.; Russell, S.; Sastry, S. Markov Chain Monte Carlo Data Association for Multi-Target Tracking. IEEE Trans. Autom. Control 2009, 54, 481–497. [Google Scholar]
- Vo, B.N.; Ma, W.K. The Gaussian Mixture Probability Hypothesis Density Filter. IEEE Trans. Signal Process. 2006, 54, 4091–4104. [Google Scholar] [CrossRef] [Green Version]
- Vo, B.N.; Vo, B.T.; Phung, D. Labeled Random Finite Sets and the Bayes Multi-Target Tracking Filter. IEEE Trans. Signal Process. 2014, 62, 6554–6567. [Google Scholar] [CrossRef] [Green Version]
- Bar-Shalom, Y.; Li, X.R. Multitarget-Multisensor Tracking: Principles and Techniques. IEEE Aerosp. Electron. Syst. Mag. 1995, 11, 41–44. [Google Scholar]
- Jia, B.; Pham, K.D.; Blasch, E.; Chen, G. Multiple space object tracking via a space-based optical sensor. In Proceedings of the 2016 IEEE Aerospace Conference, Big Sky, MT, USA, 5–12 March 2016; pp. 1–10. [Google Scholar]
- Wang, F.; Man, Y.; Man, L. Intelligent optimization approach for the k shortest paths problem based on genetic algorithm. In Proceedings of the International Conference on Natural Computation, Xiamen, China, 19–21 August 2014; pp. 219–224. [Google Scholar]
- Chong, C.Y. Graph approaches for data association. In Proceedings of the International Conference on Information Fusion, Singapore, 9–12 July 2012; pp. 1578–1585. [Google Scholar]
- Ren, X.; Huang, Z.; Sun, S.; Liu, D. An Efficient MHT Implementation Using GRASP. IEEE Trans. Aerosp. Electron. Syst. 2014, 50, 86–101. [Google Scholar] [CrossRef]
- Goldberg, A.V. An efficient implementation of a scaling minimum-cost flow algorithm. J. Algorithms 1997, 22, 1–29. [Google Scholar] [CrossRef]
- Zhang, L.; Li, Y.; Nevatia, R. Global data association for multi-object tracking using network flows. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, AK, USA, 23–28 June 2008; pp. 1–8. [Google Scholar]
- Pirsiavash, H.; Ramanan, D.; Fowlkes, C.C. Globally-optimal greedy algorithms for tracking a variable number of objects. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Springs, CO, USA, 20–25 June 2011; pp. 1201–1208. [Google Scholar]
- Xi, Z.; Liu, H.; Liu, H.; Yang, B. Multiple Object Tracking Using the Shortest Path Faster Association Algorithm. Sci. World J. 2014, 2014, 481719. [Google Scholar] [CrossRef] [PubMed]
- Zhenghao, X.I.; Hongbo, L.I.; Liu, H.; Sun, F. Multiple object tracking using A* algorithm optimization. Qinghua Daxue Xuebao/J. Tsinghua Univ. 2014, 54, 1549–1554. [Google Scholar]
- Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B. Network Flows: Theory, Algorithms, and Applications; Prentice Hall: Upper Saddle River, NJ, USA, 1993. [Google Scholar]
- Russell, S.J.; Norvig, P. Artificial Intelligence: A Modern Approach, 3rd ed.; Pearson: London, UK, 2010. [Google Scholar]
- Chabini, I.; Lan, S. Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks. IEEE Trans. Intell. Transp. Syst. 2002, 3, 60–74. [Google Scholar] [CrossRef]
- Kim, J.; Min, J.; Kweon, I.S.; Lin, Z. Fusing Multiple Independent Estimates via Spectral Clustering for Robust Visual Tracking. IEEE Signal Process. Lett. 2012, 19, 527–530. [Google Scholar] [CrossRef]
- Wang, X.; Qian, B.; Davidson, I. On constrained spectral clustering and its applications. Data Min. Knowl. Discov. 2014, 28, 1–30. [Google Scholar] [CrossRef]
- Vautard, F.; Xu, L.; Drzal, L.T. Study on the Determination and Application of the Cluster Number of the Images Based on the Spectral Graph Theory. Gongcheng Shuxue Xuebao/Chin. J. Eng. Math. 2012, 29, 27–50. [Google Scholar]
- Zhang, F. Matrix Theory; Springer: New York, NY, USA, 2011. [Google Scholar]
- Särkkä, S. Continuous-time and continuous-discrete-time unscented Rauch–Tung–Striebel smoothers. Signal Process. 2010, 90, 225–235. [Google Scholar] [CrossRef]
- Huang, Y.; Zhang, Y.; Zhao, Y.; Mihaylova, L.; Chambers, J. A Novel Robust Rauch–Tung–Striebel Smoother Based on Slash and Generalized Hyperbolic Skew Student’s T-Distributions. In Proceedings of the 2018 21st International Conference on Information Fusion (FUSION), Cambridge, UK, 10–13 July 2018; pp. 369–376. [Google Scholar]
- Schuhmacher, D.; Vo, B.T.; Vo, B.N. A Consistent Metric for Performance Evaluation of Multi-Object Filters. IEEE Trans. Signal Process. 2008, 56, 3447–3457. [Google Scholar] [CrossRef]
- Kristan, M.; Matas, J. A Novel Performance Evaluation Methodology for Single-Target Trackers. IEEE Trans. Pattern Anal. Mach. Intell. 2016, 38, 2137–2155. [Google Scholar] [CrossRef] [PubMed]
- Zhang, Y.; Brady, M.; Smith, S. Segmentation of brain MR images through a hidden Markov random field model and the expectation-maximization algorithm. IEEE Trans. Med. Imaging 2001, 20, 45–57. [Google Scholar] [CrossRef] [PubMed] [Green Version]
- Li, X.R.; Jilkov, V.P. Survey of maneuvering target tracking. Part I. Dynamic models. IEEE Trans. Aerosp. Electron. Syst. 2003, 39, 1333–1364. [Google Scholar]
- Garcia-Fernandez, A.F.; Morelande, M.R.; Grajal, J. Bayesian Sequential Track Formation. IEEE Trans. Signal Process. 2014, 62, 6366–6379. [Google Scholar] [CrossRef] [Green Version]
© 2018 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
Share and Cite
Ma, T.; Gao, S.; Chen, C.; Song, X. Multitarget Tracking Algorithm Based on Adaptive Network Graph Segmentation in the Presence of Measurement Origin Uncertainty. Sensors 2018, 18, 3791. https://doi.org/10.3390/s18113791
Ma T, Gao S, Chen C, Song X. Multitarget Tracking Algorithm Based on Adaptive Network Graph Segmentation in the Presence of Measurement Origin Uncertainty. Sensors. 2018; 18(11):3791. https://doi.org/10.3390/s18113791
Chicago/Turabian StyleMa, Tianli, Song Gao, Chaobo Chen, and Xiaoru Song. 2018. "Multitarget Tracking Algorithm Based on Adaptive Network Graph Segmentation in the Presence of Measurement Origin Uncertainty" Sensors 18, no. 11: 3791. https://doi.org/10.3390/s18113791
APA StyleMa, T., Gao, S., Chen, C., & Song, X. (2018). Multitarget Tracking Algorithm Based on Adaptive Network Graph Segmentation in the Presence of Measurement Origin Uncertainty. Sensors, 18(11), 3791. https://doi.org/10.3390/s18113791