Object Tracking Based on Markov Chain and MAP Estimation

Object Tracking Based on Markov Chain and MAP Estimation

International Journal of Engineering Research & Technology (IJERT)

ISSN: 2278-0181

Vol. 3 Issue 5, May – 2014

Sikha Das C K Mr. Yadhu R. B.

Final year MTech dsp Assistant Professor, AE&I

KMCT College of Engineering, Calicut, India KMCT College of Engineering, Calicut, India

Abstract-The human visual system observes and understands a scene or image by making a series of fixations at important locations in the scene. This fixation point lies inside a particular region of arbitrary shape and size, which can either be an entire object or a part of it. Using that fixation point as an identification marker on the object, here propose a method to track the object of interest. Using this new object tracking method the computation time reduction is possible and also it is very useful for high definition videos. And also it is possible to trace the object even if it is moving or changes to stands still from movement and then again moving. Another important attraction of this paper is automatic fixation. All these features that are computation time reduction and automatic fixation are done using k-means clustering, markov chain and maximum a posteriori (MAP) estimation. This is an efficient object tracking method.

Index TermsFixation based segmentation, markov chain, K- means clustering, MAP Estimation

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. 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. The aim of an object tracker is to generate the trajectory of an object over time by locating its position in every frame of the video. Object tracker may also provide the complete region in the image that is occupied by the object at every time instant. In other words we can say it is a method of following an object through successive image frames to determine how it is moving relative to other objects. Object tracking, in general, it is a challenging problem. Difficulties in tracking objects can arise due to abrupt object motion, changing appearance patterns of the object and the scene, non-rigid object structures, object-to-object and object-to-scene occlusions, and camera motion .Object tracking problems have been studied for several years and many different approaches have been proposed. Most of these object tracking algorithms are based on block processing [6], and image differencing method

   [5].Computational complexity is the general problem in all of these cases that is most of these algorithm take more time for execution.

   This paper proposes a new method for object tracking or moving object detection that is based on real time segmentation with fixation. For that incorporate Mishra et al active visual segmentation with fixation [1] with markov chain and MAP estimation approach to obtain efficient object tracking result. That is it is a fixation based object tracking algorithm. Every fixation point lies inside a particular region of arbitrary shape and size, which can either be an entire object or a part of it. This system is very use full in high definition videos where contain large number of pixels. When using normal tracking algorithm for high definition videos computation time is large. So here introduce a new method using that computation time is reduced also fixation point can set automatically. All these are that is automatic fixation and computation time reduction is possible with K-means clustering and markov chain concept and MAP (maximum a posteriori) estimation methods. This system is very useful when object is moving or changes to stands still from the movement and then again moving. We get lower computation time when using general Bayesian estimation like MMSE (minimum mean square estimator) for Gaussian distribution. But the problem regarding that estimation algorithm is that which gives better results only when the system follows Gaussian distribution. But when the observed system follows other than Gaussian distribution that basic estimation process cannot give better result (Computation time reduction is not properly obtained) .So here develop a new object tracking algorithm based on MAP estimation. This estimator is used for all types of system which follows any type of probability distributions. And also computation time obtained is less than that of the existing object tracking algorithms.

   The proposed method is a three step process. In first, finding the probabilistic boundary edge map of the image which is generated using all available visual cues [1].It is done only for first frame. Second step is forming clustered structure for the first frame using k-means clustering algorithm [2] .New cluster mean and centroid point is calculated for clustered image. This centroid value is updated to next frame. Third method is finding new centroid position (fixation point) using MAP estimation equation.

2. RELATED WORK

   There is a huge literature on various methods to segment images and videos into regions. Most segmentation algorithms depend upon some form of user input, without which the definition of the optimal segmentation of an image is ambiguous. There are two broad categories: first, the algorithms [4], [7], that need various user specified global parameters such as the number of regions and thresholds to stop the clustering; second, the interactive segmentation algorithms [8], that always segment the entire image into only two regions: foreground and background. There are some hierarchical approaches [9] that do not require user input and they work well, especially for the image with a single object in prominence. Mart´nez et al. [10] correctly identifies the problems with the Normalized-Cut-based method [4] and proposes a solution to automatically select the global parameter for the segmentation process. But, since the cost of a cut is still computed in the Cartesian space, the short- cut problem, (scaling problem) [1] might still be an issue.

   In all of existing segmentation algorithms, it can see that entire scene must be segmented instead of segmenting single object of interest. Active visual segmentation which is one of the best tool for segmentation applicable for both video and still image. Which is a fixation based segmentation. In that we give fixation as an input to the image and output is the optimal closed contour around that fixated region. Active visual segmentation (fixation based) is one of the efficient segmentation algorithms, which have greater advantages. That is using this we can eliminate general segmentation based problem that is scaling problem, lightening effect, texture effect etc. These are achieved by combining different type of cues and Cartesian to polar edge map formation. But when this segmentation is used for video images there is some problem arises. The computation time is large and also this method is applicable only when moving object is moving with a particular speed. That is when moving object is moving and stands still from the movement and then again moving; this type of moving object cannot be tracking using this segmentation algorithm. So develop new algorithm for object tracking based on clustering and conditioal expectation. For computation time reduction we want to know about the location of the centroid in the next frame using the information from the previous frame. That is we want to get estimate of the parameter in the next frame. For this estimation process we use prior probability based estimation algorithm that is Bayesian estimation concept. In Bayesian estimation concept we can estimating the values of the parameter (which is a random variable) based on measured data. When using MMSE Bayesian estimation concept for object tracking algorithm computation time reduction is obtained. But this reduction in computation time is correctly achieved only when the input system follows Gaussian distribution. So to avoid that problem here develop a new object tracking algorithm which is applicable for all types of probability distributions.

3. PROPOSED METHOD

Here propose a fixation based tracking algorithm. Automatic fixation and computation time reduction are attractiveness of this algorithm. And also it can use for all type of object tracking problems. Here using markov chain concept (Next state depends on present state and not the state preceding it) and for automatic fixation, use MAP estimation. Estimation process is used here for next frame fixations point localization. And computation time reduction is achieved by k-means clustering. The steps involved are represented using a block diagram in Figure1.

We know video is consists number of frames. In this proposed method for the first frame do the active visual segmentation algorithm. That is formation of probabilistic boundary edge map by combining cues [1], [3], [13]. And then k-means clustering is done then finding cluster new mean value. Fixation point is given as the centroid of moving object, and then finds the optimal closed contour around the fixation. This centroid location of the moving object is updated for next frame. Using that value find the new centroid value.

Figure1.Blockdiagram representation of proposed method

Consider a frame, it had mean value and centroid point (here fixation point) then we can calculate estimate of centroid value of the moving object in + 1 when frame centroid position is given, using MAP estimation technique. These procedures are continued for successive frames. And we can see that when going to frame to frame the expected value of the centroid location is converges to observed value that is true value when number of observation increases. That is automatic fixation is achieved. Here the automatic fixation point is achieved using markov chain concept [11]. That is frame fixation point location can be computated using 1 frame fixation point value, using MAP estimation. For that calculation we assume the displacement of moving object follows a particular probability distribution with particular mean and variance value.

K-means clustering plays its own role in computation time reduction, computation time is considerably reduced in compare with all of the previous algorithms .In active visual segmentation based method pixel to pixel scanning is done for finding the moving object. But in new method,

for first frame moving object is finding using boundary edge map formation and then clustering is done using k- means clustering algorithm .This clustered mean value is updated for next frame. That is new cluster is formed without compare with entire frame. This process is continued for all other frames.

A. K-Means Clustering

Clustering of data is a method by which large sets of data are grouped into clusters of smaller sets of similar data. A clustering algorithm attempts to find natural groups of components (or data) based on some similarity. Initially, the number of clusters must be known, or chosen, to be K say. Next, the algorithm considers each instance and assigns it to the cluster which is closest. The cluster centroids are recalculated either after each instance assignment, or after the whole cycle of re-assignments. This process is iterated [2]

B Markov chain and MAP Estimation

A Markov chain is a stochastic process with the Markov property. It is characterized as memory less. The next state depends only on the current state .That is

+1 = \1 = 1 , 2 = 2, . . = =

( +1 = \ = ) (1)

Estimation theory is a branch of statistics that deals with estimating the values of parameters based on measured or empirical data that has a random component. The parameters describe an underlying physical setting in such a way that their value affects the distribution of the measured data. An estimator attempts to approximate the unknown parameters using the measurements.

The entire purpose of estimation theory is to arrive at an estimator preferably an easily implementable one. In statistics, an estimator is a rule for calculating an estimate of a given quantity based on observed data. Suppose there is a fixed parameter that needs to be estimated. An estimator of is usually denoted by the symbol . There are commonly two types of estimation approaches, classical and Bayesian estimation approaches.

In classical approach to statistical estimation, in which the parameter is assumed to be deterministic but unknown constant. But in Bayesian approach the parameter , whose realization must be estimate is considered as a random variable. Bayesian approach is named like that because its implementation is based directly on Bayes theorem. Also in that approach prior knowledge about is also available. That is in Bayesian approach, the parameter whose realization must be estimate is a random variable with given prior PDF. So Bayes estimator or a Bayes action is an estimator or decision rule that minimizes the posterior expected value of a loss functions.

Maximum a posteriori (MAP) is a Bayes estimator, which is usually easy to determine. It does not involve any integration, but only maximization. A maximum a posteriori probability (MAP) estimate is a mode of the distribution. In the MAP estimation [12] we choose to maximize the posteriorPDF

= max /

= max /

/ = F and P () =prior PDF

is the parameter to be estimated and x is the observed data.

Consider the displacement of the moving object follow a particular probability distribution and then = is the estimate of the centroid location when n observations are given. And also P (/x) = is the posterior pdf of centroid of cluster at frame, given correct observed centroid up to (k-1) frame

P(x/) = is the pdf of observed centroid at k+1 frame when the centroid at + 1 frame is known or given.

P () = prior pdf of centroid location

IV EXPERIMENTS AND RESULTS

Proposed method is able to apply on different traffic system video which consists of large number of different vehicles. The videos used for the experiment is dynamic scene captured with a stationary camera .Here for experimentations we take a traffic system video taken from Dhera city at Dubai. In this video consists of 3 types of vehicles. One type is continuously moving with a particular speed, other one is firstly moving then stand still from the movement then again moving. And last one is not moving. We done algorithm for tracking moving objects only. When applied 3 types of algorithms that is old algorithm (active visual segmentation algorithm), markov chain and general Bayesian estimation (MMSE estimation) based algorithm and proposed algorithm (markov chain and MAP estimator based algorithm), different results are obtained. Using fixation based segmentation algorithm it is seen that it trace the moving object only when it is contiously moving, when object is stand still from the movement it become failure to trace the trajectory of the moving object. But using basic Bayesian estimator equation and MAP based algorithm it can see that that are success full in trace the moving object when it is continuously moving or stand still from the moving and thenagain moving. MAP based algorithm gives lesser computation time compared with other 2 methods. .MAP method is applied for different probability distributions and we make a conclusion that given video follows uniform distribution, which give lesser computation time. Using new method we can see that the

computation time obtained is15seconds less than compared with active visual segmentation algorithm and more than 3seconds less than compared with MMSE estimation using method ,for this particular video. Output is depending upon type of video used.

Input video (180th frame)

Out put using AVS (180th frame)

Out put using MAP (180th frame)

From the output figures we can say that AVS based tracking method track moving object only when it is continuously moving. When it is going to stand still from movement this method is unable to trace the path. Proposed method is solving this problem.

V CONCLUSION

Here propose a novel formulation of object tracking in conjunction with fixation .This method is applicable for when object is continuously moving and stand still from the movement. Using this MAP based tracking method computation time can be reduced and automatic fixation is possible .It is one of the efficient method for object tracking.

REFERENCES

1. Active visual segmentation , ajay K. Mishra, yiannis aloimonos, loong-fah cheong, and ashraf A. Kassim, member, IEEE. ieee transactions on pattern analysis and machine intelligence, vol. 34, no. 4, april 2012

2. A Comparative Analysis of Fuzzy C-Means Clustering and K Means Clustering Algorithms Mrs. Bharati R.Jipkate and Dr.Mrs.V.V.Gohokar SSGMCE, Shegaon, Maharashtra-443101 (India) . IJCER | May-June 2012 | Vol. 2 | Issue No.3 |737-739

3. Aalborg University Department of Architecture, Design and Media Technology Master Thesis Real-Time Image Segmentation Using a Fixation-Based Approach submitted by Bjarne Großmann May 30, 2012

4. J. Shi and J. Malik, Normalized Cuts and Image Segmentation,IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888-905, Aug. 2000.

5. An Improved Moving Object Detection Algorithm Based on Frame Difference and Edge Detection .Zhan Chaohui ; Duan Xiaohui ; Xu Shuoyu ; Song Zheng ; Luo Min Fourth International Conference on Digital Object Identifier: 10.1109/ICIG.2007.153 Publication Year: 2007 , Page(s): 519 523.IEEE conferences

6. Fast object tracking using adaptive block matching Hariharakrishnan, K. ; Schonfeld,D. Multimedia, IEEE Transactions on Volume: 7 , Issue: 5 Digital Object Identifier: 10.1109/TMM.2005.854437 Publication Year: 2005 , Page(s): 853

   859

7. P.F. Felzenszwalb and D.P. Huttenlocher, Efficient Graph-Based Image Segmentation, Intl J. Computer Vision, vol. 59, no. 2, pp. 167-181, 2004.

8. Y.Y. Boykov and M.P. Jolly, Interactive Graph Cuts for Optimal Boundary and Region Segmentation of Objects in n-d Images, Proc. Eighth IEEE Intl Conf. Computer Vision, pp. 105-112, 2001.

9. S. Alpert, M. Galun, R. Basri, and A. Brandt, Image Segmentation by Probabilistic Bottom-Up Aggregation and Cue Integration, Proc. IEEE Conf. Computer Vision and Pattern Recognition, June 2007.

10. A.M. Mart´nez, P. Mittrapiyanuruk, and A.C. Kak, On Combining Graph-Partitioning with Non-Parametric Clustering for Image Segmentation, Computer Vision and Image Understanding, vol. 95, pp. 72-85, July 2004.

11. Probability, Statistics and Queueing Theory V.Sndarapandian

12. Fundamentals of Statistical Signal Processing Volume I, Estimation Theory Steven M. Kay

13. Digital image Processing Rafael C.Gonzalez and Richard E.Woods