Video Object Tracking Using Particle Filtering

Video Object Tracking Using Particle Filtering

Ritesh R. Singh,

P.G student, Mumbai University,

Dr.Manali J. Godse, Professor & HOD, Biomedical engineering D.J.S.C.O.E.

Mumbai University

Tanaji D. Biradar, Assistant Professor, EXTC department D.J.S.C.O.E.

Mumbai University

Abstract

Tracking in videos is an important field of research since the new generations of computer processors can process more and more data. These researches are useful for the fields of surgery assisted by computer and robotics since they rely mostly on video processing to implement new devices. Usually, the video based object tracking deal with non-stationary images that change over time. Robust and Real time moving object tracking is a tricky issue in computer vision research area. Most of the existing algorithms are able to track only in predefined and well controlled environment. Some cases fail to consider the non-linearity issues. Particle filtering has proven to be very successful for non- Gaussian and non-linear estimation problems. In our system we are implementing particle filter to track an object in a video sequence and analyzing its advantages and disadvantages over other filters.

1. Introduction

   Object tracking is an important task within the field of computer vision. The proliferation of high-powered computers, the availability of high quality and inexpensive video cameras, and the increasing need for automated video analysis has generated a great deal of interest in object tracking algorithms.

   There are three key steps in video analysis:

   Detection of interesting moving objects, tracking of such objects from frame to frame, and analysis of object tracks to recognize their behavior.[1]

   Use of object tracking is pertinent in the tasks of:

   1. motion-based recognition, that is, human identification based on gait, automatic object detection, etc;

   2. automated surveillance, that is, monitoring a scene to detect suspicious activities or unlikely events;

   3. video indexing, that is, automatic annotation and retrieval of the videos in multimedia databases;

   4. Human-computer interaction, that is, gesture recognition, eye gaze tracking for data Input to computers, etc.;

   5. Traffic monitor, that is; real time gathering of traffic statistics.

   6. Vehicle Navigation ie; video based path planning and obstacle avoidance capabilities.

      Without dynamic performance of the system, it cannot be applied in real time. Our goal is to make a real time tracking system and in which we carefully consider the color, shape and non-linearity. Tracking objects is performed in a sequence of video frames and its process mainly consists of two main stages: firstly, isolation of objects from background in each frame and secondly, the association of objects in successive frames in to trace them. According to the most of existing system, they are able to track object in an image sequence, either viewed or not or based on some extra trained data, in dumpy period and in well controlled environment. These algorithms usually fail to perfectly observe the deform-able object shape changing in video images and in the bulky lighting (illumination) variations. In our developed algorithm we all consider these kinds of problems. To start object tracking, generally the trackers need to be initialized by an external module. Object model for tracking in image processing is usually based on reference image of the object, or properties of the objects. Once an object model is initiated the tracking algorithms will conduct based on high correlations of the object motion, shape, color or appearance from the model between consecutive video frames. But, unfortunately robust and efficient object tracking is still an open research issue and in this paper our approach also to present an efficient system to make a robust tracker. In our case, we use HSV histogram-based object model and particle filter to make a robust color based probabilistic model.

2. Review and Motivation Stage

   Object tracking is required in many vision applications such as human-computer interfaces, video communication/compression, road traffic control, and security and surveillance systems. Often the goal is to obtain a record of the trajectory of the moving single or multiple targets over time and space, by processing information from distributed sensors. Object tracking in video sequences requires on-line processing of a large amount of data and is time-expensive. Additionally, most of the problems encountered in visual tracking are nonlinear, non-Gaussian, multi-modal or any combination of these. Different techniques are available in the literature for solving tracking tasks in vision and can be divided in general into two groups:

   (i) Classical applications, where targets do not interact much with each other, behave independently such as aircrafts that do not cross their paths, and ii)Applications in which targets do not behave independently (ants, bees, robots, people), their identity is not always very well distinguishable.

   Tracking multiple identical targets has its own challenges when the targets pass close to each other or merge. [2]

   In this paper we concentrate the attention on particle filtering techniques, which have recently proven to be a powerful and reliable tool for tracking nonlinear systems. Particle filtering is a promising technique because it allows fusion of different sensor data, to incorporate constraints and to account for different uncertainties. Furthermore, it is able to cope with missing data, circumvent possible occlusions and solve data association problems when multiple targets are tracked with multiple sensors. The observations may come synchronously or asynchronously in time from one sensor or many sensors, static or moving.

   1. Object Tracking: A Background

      In its simplest form, tracking can be defined as the problem of estimating the trajectory of an object in the image plane as it moves around a scene. In other words, a tracker assigns consistent labels to the tracked objects in different frames of a video. Additionally, depending on the tracking domain, a tracker can also provide object-centric information, such as orientation, area, or shape of an object. Tracking objects can be complex due to:

      • complex object shapes,

      • scene illumination changes, and

      • real-time processing requirements.\\

   One can simplify tracking by imposing constraints on the motion and/or appearance of objects. Almost all tracking algorithms assume that the object motion is smooth with no abrupt changes. One can further limit the object motion to be of constant velocity or constant acceleration based on a priori information. Prior knowledge about the number and the size of objects, or the object appearance and shape, can also be used to simplify the problem.

   Numerous approaches for object tracking have been proposed. These primarily differ from each other based on the way they approach the following questions: Which object representation is suitable for tracking? Which image features should be used? How should the motion, appearance, and shape of the object be modeled? The answers to these questions depend on the context/environment in which the tracking is performed as well as on the end use for which the tracking information is being sought. A large number of tracking methods have been proposed which attempt to answer these questions for a variety of scenarios.

3. Particle Filtering

   Usually, for any video based tracking system, our goal is to track object through a sequence of video. Tracking objects in video involves the modeling of non-linear and non-Gaussian systems. If we have to consider these two phenomena, then how can we get solution for dynamic moving object tracking? One solution can be employed by using a probabilistic framework which formulates tracking as interference in a Hidden Markov Model (HMM).This frame is like as shown in fig1. In order to model accurately the underlying dynamics of a physical system, it is important to include elements of non-linearity and non-Gaussianity in many application areas. Particle Filters can be used to achieve this. They are sequential Monte Carlo methods based on point mass representations of probability densities, which are applied to any state model [3]

   • loss of information caused by projection of the 3D world on a 2D image,

   • noise in images,

   • complex object motion,

   • non-rigid or articulated nature of objects,

   • partial and full object occlusions,

   In the literature, target tracking and detection problems are usually formulated using linear state space models with additive Gaussian noise. The complete statistics of linear Gaussian problems can be computed with Kalman filtering technique [4].However in reality, problems involving target and object tracking require non-linear models with non-Gaussian noise. Non-linear non-Gaussian models would necessitate the adoption of a particle filtering technique. In recent years, particle filtering techniques have been used for numerous applications in coding, communications, and signal processing.

   Particle Filter is a hypothesis tracker, which approximates the filtered posterior distribution by a set of weighted particles. It weights particles based on a likelihood score and then propagates these particles according to a motion model.

   The basic idea behind particle filtering is to sample a continuous posterior density function of interest into a set of weighted particles.if appropriately weighted, then this weighted approximation can very closely resemble the posterior density function. The main function of a particle filter is to assign appropriate weights and update the weights as time progresses. Weight of each particle should be changed depending on observation for current frame.

   The basic Particle Filter algorithm consists

   of 2 steps:

   • Sequential importance sampling (SIS)

   • Selection step

   In SIS step it uses Sequential Monte Carlo Simulation. For each particle at time t, transition priors are sampled. For each particle we then evaluate and normalize the importance weights. In selection steps (Resampling), we multiply or discard particles with respect to high or low importance weights to obtain a predefined number of particles. This selection step is what allows us to track moving objects efficiently.

   Particle filter consists of essentially two steps which are

   1. Prediction

   2. Update

   Given all available observations

   up to time t1, the prediction stage uses the probabilistic system transition model p(xt | xt-1) to predict the posterior at time t as

   At time t , the observation yt is available, the state can be updated using Bays rule where

   is described by the observation equation

   In the particle filter, the posterior is

   approximated by a finite set of N samples for i=1…N,with importance weights and the

   weight samples are

   The samples are resampled to generate an un-weighted particle set according to their importance weights to avoid degeneracy.

   1. Monte-Carlo Framework

      The generic objective is to track the state of a specified object or region of interest in a sequence of images captured by a camera. Different techniques are available in the literature for solving tracking problems in vision. We are focusing our attention mainly on Monte Carlo techniques (particle filters) because of their power and versatility. The Monte Carlo techniques are based on computation of the state posterior density function by samples, and are known under different names: particle filters (PFs), bootstrap methods or the condensation algorithm which was the first variant applied to video processing. The abbreviation condensation stems from Conditional Density propagation. [2]

      The Monte Carlo approach relies on a sample-based representation of the state PDF. Multiple particles (samples) of the state are generated, each one associated with a weight which characterizes the quality of a specific particle. An estimate of the variable of interest is obtained by the weighted sum of particles. The two major steps are: prediction and update. During the prediction each particle is modified according to the state model of the region of interest in the video frame, including the addition of random noise in order to simulate the noise in the state. In the update stage, each particle's weight is re-evaluated with the new data.

   2. Re-Sampling

   An important feature of particle filtering is re-sampling, in which the weights that have a very low value are eliminated and replaced with weights that have a higher

   value. Resampling the particles allows the particles to represent the probability density function with greater accuracy. This step allows more particles or samples to focus on the areas of interest, or high-probability areas, and less on the low-priority regions. The overall effect of the resampling step is that the particles with high relative weights after the observation have a high probability of remaining in the set, possibly multiple times, and the particles with low weights have a high probability of being removed from the set .Hence,[2] are-sampling procedure eliminates particles that have small weights and replicates the particles with larger weights.

4. Tracking Using Particle Filtering.

   1. Target Tracking

      Over the past 40 years many techniques have been developed for target tracking in a clutter environment, which include classical Kalman filtering,unscented Kalman filtering, and extended Kalman filtering .

      Target tracking has always been a challenging problem in image/signal processing. Although significant work has been done in this area by the research community, the problem is still considered challenging. Recent growth in ad-hoc wireless communications and sensor technology has given a new dimension to the sensor- based tracking problem. Current applications of sensor- based tracking include tracking of climatic conditions in remote places such as mountain slopes, activity tracking across sensitive areas such as state and national borders, and surveillance applications such as airport security.

      The classical approach for tracking involves radar sonar technologies using Doppler shift for measuring the velocity and location of moving targets. With the growth in sensor technology, simple and efficient low- end sensors have come into existence. Parallel growth in adhoc wireless communication systems changed the way sensors communicate with each other and with the base station. Various energy-aware and energy conserving-protocols are being developed by researchers to address tracking using a network of sensors. Sensors basically measure physical quantities such as temperature, pressure, speed of moving objects, etc. The tracking task can be formulated as a state estimation problem consisting of a state transition model, which relates the target position and velocity at every time step, and an observation model, which relates the current target state with the current target observations.

   2. Object Tracking

      With advancements in compression and video coding, image and video over wireless channels or sensor

      networks are gaining popularity. Image and video sensors include web-cams, pan-zoom-tilt cameras, inra-red cameras, etc. These sensors capture the information from the environment where they are deployed. Visual data provides very rich information compared to other types of sensor data. Since image data is highly correlated, efficient correlation-based tracking algorithms may be employed to increase the overall efficiency of the sensor network. The numerous advantages involved in using image and video sensors along with advances in adhoc network systems form the motivation for this thesis.

      Object tracking is one of the most important and challenging problems in video processing, mainly due to the number of applications in which it plays a significant role. Such applications include video surveillance and monitoring, and video-based tracking, to mention a few. One approach to object tracking is to track the features (such as edges and corners) of objects appearing in the video sequence. The first step in this approach is to identify features of interest. Next, a prediction model must be formed such that the features can be predicted over time from one frame to the next. Although significant work has been done in this area of research, the tracking problem is still considered challenging due to the difficulties involved in applying image feature extraction and prediction techniques for practical applications.

   3. Concept of Tracking Using Particle Filter Below given images help us concentrate on the basics of tracking and use of particle filtering. Figure below demonstrates basic prediction method.

      We might think that a good measurement would solve this problem. But a single measurement of the rocket trajectory is not enough. If neither perfect prediction nor a perfect measurement exists then we could combine this 2 methods into one method which is called as the process of Data Assimilation. From above figure we can say that by taking the mean of measurements wouldn't serve the purpose. We need more accurate and precise measurements. Particle filter is state estimation using a lot of particles and prediction methods in state models.

      The prediction method used can be calculated in two steps as below:

      • Get the color of the pixel on which particle exists.

      • Compare the RGB value with specific threshold.

   The Filtering process along with re-sampling is carried out further.

5. System Flow Diagram

   We want to apply a particle filter in a colour model based framework. This system depends on the deterministic search of a window, whose colour content matches a reference histogram colour model. We use principle of colour histogram distance. The overall working flow diagram is shown in figure.

   In the figure 4, the complete implemented system is explained.

   1. Implemented System

      In our implemented system,We are trying to track the red object in a video sequence.For understanding purposes,we have used a prototype.the steps carried out can be described grammatically as follows:

      • Track the red object by many particles.

      • Prediction: Using the theory of particle filtering, we calculate the maximum likelihood of particles.

      • Filtering: Following to prediction, the process of Filtering is carried out as per the Maximum Likelihood Theory.

      • Prediction and Re-Sampling: The final process is completed by Re-Sampling and updating particles as shown below.

      1. Track the red object

      2. Prediction

      3. Filtering process

      4. Re-Sampling and update

6. Implemented Results

   In this section we will demonstrate some experimental results on several real-world video sequences captured by pan/tilt/zoom video camera in indoor, outdoor environment. Figures show the effectiveness of our system.

   As shown in figure 5 the mean deviation in pixels, even after 40 iterations in 40 frames does not differ more than 36 pixels maximum. In ideal case it should have been zero but it is very close to observed motion. The figure 6 shows the output of our implemented system where person wearing red T shirt is covered with blue colour particles and few shades of red near the object like skin tone also being tracked with an accuracy of 88 percent.

7. Conclusion

   Particle filtering is a technique that is very suitable for object tracking in video sequences. There are several challenges in solving tracking problems in image/ video applications. The first of them is

   the nonlinear character of the object of interest and of the observation model. The algorithms must often run at high update rates. In many applications the prior information available for the environment is limited. How to handle clutter in the background is also of considerable importance, especially with multiple targets. From the point of view of implementations this domain is wide open and challenging.

8. Acknowledgements

   The authors would like to thank Dr. Hari vasudevan for his continuous help and support. I would also like to thank our head of the department Dr. Amit deshmukh for his continuous encouragement and support without which this would have not been possible.

9. References

1. Alper Yilmaz,Ohio State University, Omar Javed, Object Video.Inc and Mubarak shah, University of central Florida ,Object tracking :A survey, ACM Computing Surveys, Vol. 38, No. 4, Article 13, Publication date: December 2006.

2. Lyudmila MIHAYLOVA,Paul BRASNETT, Nishan CANAGARAJAH and David BULL, Department of Electrical and Electronic Engineering, University of Bristol, UK, Object Tracking by Particle Filtering Techniques in Video Sequences.

3. Md. Zahidul Islam, Chi-Min Oh and Chil-Woo Lee,Chonnam National University, Gwangju, South Korea,Video Based Moving Object Tracking by Particle Filter, International Journal of Signal Processing, Image Processing and Pattern Vol. 2, No.1, March, 2009

4. Srisumakanth kambhampati, Department of Electrical and Computer Engineering, Object Tracking using particle filtering.