DonNTU
Masters Portal

• Summary

Algorithms for tracking objects in video streams on parallel computing systems

• Introduction
• Aims
• Research in DonNTU
• Research in the world
• Methods for tracking objects
• Conclusion
• Literature

Introduction

Soccer is the most popular sport worldwide. There has been a growing interest in using computers to improve the convenience of viewing soccer matches on television. In addition to displaying the time of the match, score, information about players and teams statistics, there is a need for data needed for better understanding some moments of the game. For this various systems analysis of sports competitions have been developed. They help in the following situations:

• definition of correctness of the decision of the referee;
• simulations for further mining in training;
• analysis of the game from different perspectives for better understanding what is happening on the field.

The main task of these systems is to track objects in video. Tracking objects in the video stream is meant to obtain a set of visible objects and their coordinates in each frame.

Tracking objects in video has a large computational complexity. Providing speed enough to track a large number of objects in real time requires the development of methods and algorithms for tracking on parallel computer systems.

The main problem of tracking multiple objects in the video is the objects, partly overlapped by other objects. The most common approach to solving this problem is to submit the tracking object as a set of its parts, which allows to reproduce the trajectory of an object during the overlap on the basis of the trajectories of its parts are not overlapped. At the same time, this approach will be ineffective, if several objects intersect most of the time.

Attention given to the problem of tracking objects in videos, as well as the existence of unsolved problems, suggests that the research topic is relevant.

Aims

Analysis of methods for tracking objects showed that nowadays there is the problem of tracking non-breaking one or more objects in the automatic analysis of sports events, video surveillance and security systems [1]. For more precise observation of the object, the object can be represented as a collection of smaller objects.

An additional problem is to speed enough to track objects in real time. Many works devoted to the development of fast sequential algorithms for tracking, but attention should be paid to the development of methods for tracking objects using parallel computer systems. To resolve this problem, we can use parallel systems with MIMD architecture or multi-threaded architecture graphics processor with CUDA technology.

Thus, the purpose is to develop a method for tracking multiple objects in the video stream and to ensure its performance in real time. The main application of the new method is a system for automatic analysis of football matches.

Accordingly, the assumptions made and limitations:

1. The main targets are the figures of people in an upright position.
2. Signs of the objects on which they can be uniquely identified, such as human faces or the numbers on the form the players are not counted.
3. Objects move in the plane of the earth, known for their top speed and acceleration.
4. The camera is fixed, an angle of it not less than 30 º to the plane of the earth, known to its position in space.
5. Video is in color and has a frequency of at least 10 FPS.

To achieve this goal it is necessary to accomplish the following tasks:

1. Develop a new method to track objects in the video stream, basing on existing methods for tracking objects.
2. Investigate the quality of the track, provided by a new method to determine optimal parameters for its functioning.
3. Develop the new tracking method on a parallel architecture, ensuring that the speed is enough to track objects in real time.
4. Accelerate the search for fragments of objects in the scene through the development of efficient parallel search algorithms.
5. Develop a subsystem to automatically detect and track people in the video stream, which can be used in computer-aided analysis of a soccer match.

Research in DonNTU

In DonNTU dealt with the subject Sereda Andrey, defended in 2011 his thesis on tracking objects in video streams. Research methods for tracking objects in a distributed surveillance system is engaged Larin Borislav.

Research in the world

In the CIS countries, the topic is new and scantily explored, but nowadays there appears a large number of publications and development related to the tracking of objects in the video. In Europe and the U.S. the subject is engaged in a large number of specialists. There are a lot of designed commercial security systems, monitoring traffic, the analysis of sporting events, used in many spheres of our life and applicable in a variety of organizations.

Methods for tracking objects

Consider the problem of tracking objects in the video stream and the main approaches to its solution. Let the image represented as a matrix of pixels. Each pixel is a vector, all the pixels have the same dimension. Pixel elements are the components of its color in the format of RGB. Pixel elements may contain additional features, such as the use of the gradient, in addition to brightness which allows to raise the quality of tracking in a monochrome image [3]. The video stream can be regarded as an ordered set of images (frames). As the object we mean a body which changes its position in time.

Experts identify two general approaches to the construction methods for automatic detection and tracking of multiple objects in a video:

1. Independent identification and selection of objects in each frame and determining correspondences between objects that are found in different frames.
2. Identification and selection of objects in one or some frames initiates the process of tracking objects.

The most common method of detecting objects in the picture, is keeping track of "blobs"[4]. This concept refers to the set of linked or closely spaced points of the frame, highlighted by some algorithm of image segmentation, for example, by subtracting the background. Tracking "blobs" is relatively simple to implement, has low computational complexity and can reliably track the isolated objects, in particular, those that strongly change their shape.

Tracking the object that is fully covered by another object, is impossible. Most methods are designed to provide tracking of objects when it is impossible to carry out the selection of individual objects in each frame of the presence of:

• Partial crossing images of objects.
• Dynamic background scene, which can be classified as an object.

Classification of existing methods for detection and selection of objects in the video stream is shown in fig. 2.

The problem of detection and recognition of objects in the picture is more complicated than the problem of image recognition, but can be reduced to it.

To select objects it could be applied to revelation of differences between frames. An assumption: if there is a difference between pixels of two adjacent frames, then there is a movement, and these pixels belong to moving objects, otherwise — to the background [6]. Advantages of the method: it is simple to implement and requires no prior information about the form of tracked objects. Disadvantages of the method:

• Can not detect objects that move slowly.
• Area of found pixels in the image of a moving object is always different shape from the image of the object.
• Background scene must be static.

The most common method of selecting objects is the method of Background Subtraction[7]. It is based on constructing a model of the background represents the static part of the frame that contains no moving objects(fig. 3).

To improve the quality and speed of selection of objects, we can use a combination of several techniques, for example, a comparison with the background[8] and the previous frame.

Finding objects and their trajectories can be executed only once after the completion of analysis of the entire video (off-line tracking) or to perform in each frame after it is processed (on-line tracking). In the first case, having more information (in the analysis of the frame information available not only on past frames, but also about the future), can admit fewer errors [9]. However, in many cases necessary to obtain the coordinates of objects in real time. Despite considerable efforts to improve the tracking of objects in the video, none of the above methods does not ensure error-free tracking in case of the presence of many moving objects in the frame.

Monitoring is a complex task, which consists of a large number of stages. Individual steps associated with performing a large number of transactions over the elements of matrices (eg, background subtraction and allocation units) and can be efficiently implemented on parallel architectures. To solve the whole problem of tracking objects there is appropriate to use parallel systems. To reduce the time and cost of developing a system for tracking objects looks promising use of existing distributed parallel computer systems, computers with multicore processors, cluster and multi-GPU CUDA architecture[10].

Conclusion

A review of algorithms for tracking and analysis system architecture were identified, classified and analyzed the main methods of identifying and selecting objects in the video stream. System, developed on the basis of these methods should work in real time and accurately identify the objects and their parts. Identified the need to develop new algorithms for tracking, which will speed up the system and improve the quality of object recognition.

Literature

1. Середа А. А. , Ладыженский Ю. В. . "Разработка автоматизированной системы анализа видеозаписей спортивных соревнований." Доклад на региональной студенческой научно-технической конференции "Інформатика та комп'ютерні технології", ДонНТУ, Донецк, 2005.
2. Ладиженський Ю.В. А.О. Середа "Відстежування об’єктів у відеопотоці на основі відстежування переміщення фрагментів об’єктів", Наукові праці Донецького національного технічного університету. Серія: "Обчислювальна техніка та автоматизація". Випуск 17 (148). – Донецьк : ДонНТУ, 2009. – 127-134 сс.
3. Avidan, Shai. Ensemble Tracking / S. Avidan // IEEE Transactions on Pattern Analysis And Machine Intellignence. – 2007. – Volume 29, № 2. – c. 261-271.
4. Osama, Masoud. Tracking and Analysis of Articulated Motion with an Application to Human Motion / M. Osama // A Thesis Submitted to the Faculty of the Graduate School of the University of Minnesota in Partial Fulfillment of the Requirements for the Degree of Doctr of Philosophy. – 2000. – 75 c.
5. Xu. M. Partial Observation vs. Blind Tracking through Occlusion / M. Xu, T. Ellis // Information Engineering Centre City University, London. – 10 c.
6. Khan S. Tracking People in Presence of Occlusion / S. Khan, M. Shah // Asian Conference on Computer Vision. – 2000. – c. 1132-1137.
7. Doshi, Anup. People Counting and Tracking for Surveillance/A. Doshi// CSE 252C Project Report Draft. – 2005. – 5 c.
8. Kim J.W. Robust real-time people tracking system for security / J.W. Kim, K.S. Choi, W.S. Park та ін. // Department of Electronics Engineering, Korea University, Anam-dong, Sungbuk-ku, Seoul, Korea. – 6 c.
9. Cucchiara R. Track-based and object-based occlusion for people tracking refinement in indoor surveillance / R. Cucchiara, C. Grana, G. Tardini // Proceedings of the ACM 2nd international workshop on Video surveillance & sensor networks. – New York, NY, USA, 2004. – c. 81-87.
10. NVIDIA CUDA Programming Guide Version 2.3 / NVIDIA Corporation // 2009. – 147 c. – Режим доступа: http://developer.download. nvidia.com/compute/cuda/2_3/toolkit/docs/NVIDIA_CUDA_Programming_Guide_2.3.pdf.

Important note

At the time of writing this abstract master work is still not complete. Expected completion date: December 2011, thus giving the full text of the work, as well as materials on the subject can be obtained from the author or his manager after that date.