Tracking System for Living Beings and Objects: Integration of Accessible Mathematical Contributions and Graph Theory in Tracking System Design
DOI:
https://doi.org/10.56294/dm2024.376Keywords:
Tracking, Tracking System, Graph, Graph Learning, HypergraphAbstract
This paper presents a theoretical framework for a tracking system, wherein we generalize the formulation of a tracking system de- signed for living beings and objects. Many tracking systems are typically developed within specific frameworks, either for tracking in limited or unlimited space. The latter often relies on technical tools dedicated to tracking living beings or objects. In this study, we propose a system theory that formulates the task of tracking both living beings and ob- jects. Graphical modeling is widely employed in tracking to establish correct connections between the elements to be tracked and other com- ponents in the system. However, basing a tracking system on graphs in both its theoretical and practical aspects remains the optimal method for achieving a high-performing, relevant, and adaptable system in vari- ous situations. This paper introduces a tracking system based on graph learning and hypergraphs, fully leveraging direct and indirect relations while considering the order between multiple system links. Tracking is thus formulated as a search problem on graphs and hypergraphs, with vertices representing the elements of the system (living beings or ob- jects), and edges representing the types of connections between these elements. We define a law governing the relationships between the ver- tices, managing the shared data between the elements of the system and other processes. Furthermore, examples of single and multi-context track- ing situations demonstrate that the proposed system, in its theoretical foundation, outperforms existing systems.
References
1. K. Okuma, A. Taleghani, N. De Freitas, J. J. Little, and D. G. Lowe. A boosted particle filter: Multitarget detection and tracking. In Computer Vision-ECCV 2004, pages 28–39. Springer, 2004.
2. B. Leibe, K. Schindler, N. Cornelis, and L. Van Gool. Coupled ob- ject detection and tracking from static cameras and moving vehi- cles. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 30(10):1683–1698, 2008.
3. A. Alahi, K. Goel, V. Ramanathan, A. Robicquet, L. Fei-Fei, and
S. Savarese. Social lstm: Human trajectory prediction in crowded spaces. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 961–971, 2016.
4. C. Huang, B. Wu, and R. Nevatia. Robust object tracking by hierarchical association of detection responses. In Computer Vi- sion–ECCV 2008, pages 788–801. Springer, 2008.
5. Y. Xiang, A. Alahi, and S. Savarese. Learning to track: On- line multi-object tracking by decision making. In Proceedings of the IEEE International Conference on Computer Vision, pages 4705–4713, 2015.
6. S. Ali and M. Shah. Floor fields for tracking in high density crowd scenes. In Computer Vision–ECCV 2008, pages 1–14. Springer, 2008.
7. A. Robicquet, A. Sadeghian, A. Alahi, and S. Savarese. Learning so- cial etiquette: Human trajectory understanding in crowded scenes. In European Conference on Computer Vision, pages 549–565. Springer, 2016.
8. M. D. Breitenstein, F. Reichlin, B. Leibe, E. Koller-Meier, and L. Van Gool. Robust tracking-by-detection using a detector confidence particle filter. In Computer Vision, 2009 IEEE 12th International Conference on, pages 1515–1522. IEEE, 2009.
9. S. Pellegrini, A. Ess, K. Schindler, and L. Van Gool. You’ll never walk alone: Modeling social behavior for multi-target tracking. In Computer Vision, 2009 IEEE 12th International Conference on, pages 261–268. IEEE, 2009.
10. W. Choi and S. Savarese. Multiple target tracking in world co-
ordinate with single, minimally calibrated camera. In Computer Vision–ECCV 2010, pages 553–567. Springer, 2010.
11. [11] C. Dicle, O. I. Camps, and M. Sznaier. The way they move:
Tracking multiple targets with similar appearance. In Proceedings of the IEEE International Conference on Computer Vision, pages 2304–2311, 2013.
12. K. Yamaguchi, A. C. Berg, L. E. Ortiz, and T. L. Berg. Who are
you with and where are you going? In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, pages 1345–1352. IEEE, 2011.
13. P. Scovanner and M. F. Tappen. Learning pedestrian dynamics
from the real world. In Computer Vision, 2009 IEEE 12th Inter- national Conference on, pages 381–388. IEEE, 2009.
14. S. Pellegrini, A. Ess, and L. Van Gool. Improving data association
by joint modeling of pedestrian trajectories and groupings. In Eu- ropean Conference on Computer Vision, pages 452–465. Springer, 2010.
15. Z. Wu, A. Thangali, S. Sclaroff, and M. Betke. Coupling detection
and data association for multiple object tracking. In Computer Vi- sion and Pattern Recognition (CVPR), 2012 IEEE Conference on, pages 1948–1955. IEEE, 2012.
16. S. Oron, A. Bar-Hillel, and S. Avidan. Real-time trackingwith-
detection for coping with viewpoint change. Machine Vision and Applications, 26(4):507–518, 2015.
17. S. Tang, B. Andres, M. Andriluka, and B. Schiele. Multiperson
tracking by multicut and deep matching. In European Conference on Computer Vision, pages 100–111. Springer, 2016.
18. N. Le, A. Heili, and J.-M. Odobez. Long-term time-sensitive costs
for crf-based tracking by detection. In European Conference on Computer Vision, pages 43–51. Springer, 2016.
19. H. Izadinia, V. Ramakrishna, K. M. Kitani, and D. Huber. Multi-
pose multi-target tracking for activity understanding. In Applica- tions of Computer Vision (WACV), 2013 IEEE Workshop on, pages 385–390. IEEE, 2013.
20. A. R. Zamir, A. Dehghan, and M. Shah. Gmcp-tracker: Global
multi-object tracking using generalized minimum clique graphs. In Computer Vision–ECCV 2012, pages 343– 356. Springer, 2012.
21. B. Y. S. Khanloo, F. Stefanus, M. Ranjbar, Z.-N. Li, N. Saunier,
T. Sayed, and G. Mori. A large margin framework for single cam- era offline tracking with hybrid cues. Computer Vision and Image Understanding, 116(6):676– 689, 2012.
22. D. Helbing and P. Molnar. Social force model for pedestrian dy-
namics. Physical review E, 51(5):4282, 1995.
23. D. Held, S. Thrun, and S. Savarese. Learning to track at 100 fps with deep regression networks. In European Conference on Com- puter Vision, pages 749–765. Springer, 2016.
24. S. Hong and B. Han. Visual tracking by sampling treestructured graphical models. In European Conference on Computer Vision, pages 1–16. Springer, 2014.
25. M. Hu, S. Ali, and M. Shah. Detecting global motion patterns in complex videos. In Pattern Recognition, 2008. ICPR 2008. 19th International Conference on, pages 1–5. IEEE, 2008.
26. X. Zhao, D. Gong, and G. Medioni. Tracking using motion patterns for very crowded scenes. In Computer Vision–ECCV 2012, pages 315–328. Springer, 2012.
27. P. Mordohai and G. Medioni. Dimensionality estimation, manifold learning and function approximation using tensor voting. Journal of Machine Learning Research, 11(Jan):411–450, 2010.
28. L. Kratz and K. Nishino. Tracking with local spatio-temporal mo- tion patterns in extremely crowded scenes. In Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on, pages 693–700. IEEE, 2010.
29. L. Kratz and K. Nishino. Tracking pedestrians using local spatio-temporal motion patterns in extremely crowded scenes. IEEE transactions on pattern analysis and machine intelligence, 34(5):987–1002, 2012.
30. M. Rodriguez, S. Ali, and T. Kanade. Tracking in unstructured crowded scenes. In 2009 IEEE 12th International Conference on Computer Vision, pages 1389–1396. IEEE, 2009.
31. E. Ristani and C. Tomasi. Tracking multiple people online and in real time. In Asian Conference on Computer Vision, pages 444–459. Springer, 2014.
32. H. Nam and B. Han. Learning multi-domain convolutional neural networks for visual tracking. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4293–4302, 2016.
33. M. Zhai, M. J. Roshtkhari, and G. Mori. Deep learning of appearance models for online object tracking. arXiv preprint arXiv:1607.02568, 2016.
34. A. Milan, S. Roth, and K. Schindler. Continuous energy minimiza- tion for multitarget tracking. IEEE transactions on pattern analysis and machine intelligence, 36(1):58–72, 2014.
35. K. Shafique, M. W. Lee, and N. Haering. A rank constrained con- tinuous formulation of multi-frame multi-target tracking problem. In Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, pages 1–8. IEEE, 2008.
36. Q. Yu, G. Medioni, and I. Cohen. Multiple target tracking using spatio-temporal markov chain monte carlo data association. In 2007 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8. IEEE, 2007.
37. B. Zhan, D. N. Monekosso, P. Remagnino, S. A. Velastin, and L.-
Q. Xu. Crowd analysis: a survey. Machine Vision and Applications, 19(5-6):345–357, 2008.
38. L. Leal-Taixe, C. Canton-Ferrer, and K. Schindler. Learning ´ by tracking: Siamese cnn for robust target association. arXiv preprint arXiv:1604.07866, 2016.
39. L. Wen, Z. Lei, S. Lyu, S. Z. Li, and M.-H. Yang. Exploiting hier- archical dense structures on hypergraphs for multi-object tracking. IEEE transactions on pattern analysis and machine intelligence, 38(10):1983–1996, 2016.
40. B. Yang and R. Nevatia. Multi-target tracking by online learning of non-linear motion patterns and robust appearance models. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on, pages 1918–1925. IEEE, 2012.
41. S. Oron, A. Bar-Hille, and S. Avidan. Extended lucaskanade track- ing. In European Conference on Computer Vision, pages 142–156. Springer, 2014.
42. B. Yang and R. Nevatia. An online learned crf model for multi- target tracking. In Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on, pages 2034–2041. IEEE, 2012.
43. F. Solera, S. Calderara, E. Ristani, C. Tomasi, and R. Cucchiara. Tracking social groups within and across cameras. IEEE Transac- tions on Circuits and Systems for Video Technology.
44. Dawei Du, Honggang Qi, Longyin Wen, Qi Tian, Qingming Huang, and Siwei Lyu. 2017. Geometric hypergraph learning for visual tracking. IEEE TC 47, 12 (2017), 4182–4195.
45. Idir Filali, Mohand Sa¨ıd Allili, and Nadjia Benblidia. 2016. Multi- scale salient object detection using graph ranking and global–local saliency refinement. Elsevier Signal Proc. Image 47 (2016), 380–401.
46. Meng Li and Howard Leung. 2016. Multiview skeletal interaction recognition using active joint interaction graph. IEEE TM 18, 11 (2016), 2293–2302.
47. H. K. Meena, K. K. Sharma, and S. D. Joshi. 2017. Improved facial expression recognition using graph sig. pro. IET EL 53, 11 (2017), 718–720.
48. H. Nam, M. Baek, and B. Han. 2016. Modeling and propagating CNNs in a tree structure for visual tracking. CoRR. Retrieved from abs/1608.07242.
49. Tao Wang and Haibin Ling. 2018. Gracker: A graph-based planar object tracker. IEEE TPAMI 40, 6 (2018), 1494–1501.
50. D. Yeo, J. Son, B. Han, and J. H. Han. 2017. Superpixel-based tracking-by-segmentation using Markov chains. In Proceedings of the CVPR. IEEE, 511–520.
51. Dawei Du, Honggang Qi, Wenbo Li, Longyin Wen, Qingming Huang, and Siwei Lyu. 2016. Online deformable object tracking based on structure-aware hyper-graph. TIP 25, 8 (2016), 3572–3584.
52. W. Hu, T. Tan, L. Wang, S. Maybank, A survey on visual surveil- lance of object motion and behaviors, IEEE Trans. Syst. Man Cy- bern., Part C, Appl. Rev. 34 (3) (2004) 334–352.
53. X. Wang, Intelligent multi-camera video surveillance: a review, Pat- tern Recognit. Lett. 34 (1) (2013) 3–19.
54. J. Candamo, M. Shreve, D.B. Goldgof, D.B. Sapper, R. Kas- turi, Understanding transit scenes: a survey on human behavior- recognition algorithms, IEEE Trans. Intell. Transp. Syst. 11 (1) (2010) 206–224.
55. B. Zhan, D.N. Monekosso, P. Remagnino, S.A. Velastin, L.-Q. Xu, Crowd analysis: a survey, Mach. Vis. Appl. 19 (5–6) (2008) 345–357.
56. I.S. Kim, H.S. Choi, K.M. Yi, J.Y. Choi, S.G. Kong, Intelligent visual surveillance-a survey, Int. J. Control. Autom. Syst. 8 (5) (2010) 926–939.
57. D.A. Forsyth, O. Arikan, L. Ikemoto, J. O’Brien, D. Ramanan, et al., Computational studies of human motion: part 1, tracking and motion synthesis, Found. Trends Comput. Graph. Vis. 1 (2–3) (2006) 77–254.
58. A. Yilmaz, O. Javed, M. Shah, Object tracking: a survey, ACM Comput. Surv. 38 (4) (2006) 13.
59. X. Li, W. Hu, C. Shen, Z. Zhang, A. Dick, A.V.D. Hengel, A survey of appearance models in visual object tracking, ACM Trans. Intell. Syst. Technol. 4 (4) (2013) 58.
60. Y. Wu, J. Lim, M.-H. Yang, Online object tracking: a benchmark, in: Proc. IEEE Comput. Soc. Conf. Comput. Vis. Pattern Recog- nit., Anchorage, AL, USA, 2013, pp. 2411–2418.
61. L. Leal-Taix´e, A. Milan, I. Reid, S. Roth, K. Schindler, MOTChal- lenge 2015: towards a benchmark for multi-target tracking, arXiv:1504.01942, http:// arxiv.org/abs/1504.01942.
62. Z.-Q. Zhao, P. Zheng, S.-t. Xu, X. Wu, Object detection with deep learning: a review, IEEE Trans. Neural Netw. Learn. Syst. 30 (11) (2019) 3212–3232.
63. S. Ren, K. He, R. Girshick, and J. Sun, “Faster R-CNN: To- wards Real-Time Object Detection with Region Proposal Net- works,” IEEE TPAMI, vol. 39, no. 6, pp. 1137–1149, 2017.
64. D. Impiombato, S. Giarrusso, T. Mineo, O. Catalano, C. Gargano,
G. La Rosa, F. Russo, G. Sottile, S. Billotta, G. Bonanno, S. Garozzo, A. Grillo, D. Marano, and G. Romeo, “You Only Look Once: Unified, Real-Time Object Detection Joseph,” Nuclear In- struments and Methods in Physics Research, Section A: Accelera- tors, Spectrometers, Detectors and Associated Equipment, vol. 794, pp. 185–192, 2015.
65. J. Redmon and A. Farhadi, “YOLO9000: Better, Faster, Stronger,” 2016.
66. P. Felzenszwalb, D. McAllester, and D. Ramanan, “A discrimina- tively trained, multiscale, deformable part model,” in Proc. CVPR, 2008.
67. Y. Tian, A. Dehghan, and M. Shah, “On detection, data association and segmentation for multi-target tracking,” IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1–1, 2018.
68. L. Wen, D. Du, S. Li, X. Bian, and S. Lyu, “Learning nonuniform hypergraph for multi-object tracking,” arXiv preprint arXiv:1812.03621, 2018.
69. H. Sheng, Y. Zhang, J. Chen, Z. Xiong, and J. Zhang, “Hetero- geneous association graph fusion for target association in multiple object tracking,” IEEE Transactions on Circuits and Systems for Video Technology, 2018.
70. K. Shafique and M. Shah, “A noniterative greedy algorithm for multiframe point correspondence,” IEEE transactions on pattern analysis and machine intelligence, vol. 27, no. 1, pp. 51–65, 2005.
71. D. Reid et al., “An algorithm for tracking multiple targets,” IEEE transactions on Automatic Control, vol. 24, no. 6, pp. 843–854, 1979.
72. G. Shu, A. Dehghan, O. Oreifej, E. Hand, and M. Shah, “Part- based multiple-person tracking with partial occlusion handling,” in Proc. CVPR. IEEE, 2012, pp. 1815–1821.
73. A. Roshan Zamir, A. Dehghan, and M. Shah, “GMCP-tracker: Global multi-object tracking using generalized minimum clique graphs,” in Lecture Notes in Computer Science, 2012.
74. B. Wu and R. Nevatia, “Detection and tracking of multiple, par- tially occluded humans by bayesian combination of edgelet based part detectors,” International Journal of Computer Vision, vol. 75, no. 2, pp. 247–266, 2007.
75. A. Dehghan, S. Modiri Assari, and M. Shah, “Gmmcp tracker: Globally optimal generalized maximum multi clique problem for multiple object tracking,” in Proc. CVPR, 2015, pp. 4091–4099.
76. H. Pirsiavash, D. Ramanan, and C. C. Fowlkes, “Globally-optimal greedy algorithms for tracking a variable number of objects,” Proc. CVPR, pp. 1201–1208, 2011.
77. A. A. Butt and R. T. Collins, “Multi-target tracking by lagrangian relaxation to min-cost network flow,” in Proc. CVPR, 2013, pp. 1846–1853.
78. J. Berclaz, F. Fleuret, E. Turetken, and P. Fua, “Multiple ob- ¨ ject tracking using k-shortest paths optimization,” IEEE TPAMI, vol. 33, no. 9, pp. 1806–1819, 2011.
79. H. B. Shitrit, J. Berclaz, F. Fleuret, and P. Fua, “Multi-commodity network flow for tracking multiple people,” IEEE TPAMI, vol. 36, no. 8, pp. 1614–1627, 2014.
80. Tutte, William Thomas, and William Thomas Tutte. Graph theory. Vol. 21. Cambridge university press, 2001.
81. West, Douglas Brent. Introduction to graph theory. Vol. 2. Upper Saddle River: Prentice hall, 2001.
82. Gould, Ronald. Graph theory. Courier Corporation, 2012.
83. Bollob´as, B´ela. Modern graph theory. Vol. 184. Springer Science Business Media, 1998.
84. Bondy, John Adrian, and Uppaluri Siva Ramachandra Murty. Graph theory with applications. Vol. 290. London: Macmillan, 1976.
85. Hallinan, Maureen T. ”Tracking: From theory to practice.” Sociol- ogy of education 67.2 (1994): 79-84.
86. Yilmaz, Alper, Omar Javed, and Mubarak Shah. ”Object tracking: A survey.” Acm computing surveys (CSUR) 38.4 (2006): 13-es.
87. McKenna, Stephen J., et al. ”Tracking groups of people.” Computer vision and image understanding 80.1 (2000): 42-56.
88. Zhou, Xingyi, Vladlen Koltun, and Philipp Kr¨ahenbu¨hl. ”Tracking objects as points.” Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part
IV. Cham: Springer International Publishing, 2020.
89. Bretto, Alain. ”Hypergraph theory.” An introduction. Mathemati- cal Engineering. Cham: Springer (2013).
90. Hopkins, Brian, and Robin J. Wilson. ”The truth about K¨onigsberg.” The College Mathematics Journal 35.3 (2004): 198- 207.
91. Bretto, Alain. ”Hypergraph theory.” An introduction. Mathemati- cal Engineering. Cham: Springer (2013).
92. Hallinan, Maureen T. ”Tracking: From theory to practice.” Sociol- ogy of education 67.2 (1994): 79-84.
Published
Issue
Section
License
Copyright (c) 2024 Anass Ariss, Imane Ennejjai, Jamal Mabrouki, Asmaa Lamjid, Nassim Kharmoum, Soumia Ziti (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
The article is distributed under the Creative Commons Attribution 4.0 License. Unless otherwise stated, associated published material is distributed under the same licence.
