Example of Mouse Tracking utilizes Particle Filter
Mouse Tracker
Abstract
In this page, a simple Particle Filter is implemented to track the movements of a mouse. This problem can also be viewed as tracking a single target in a room (given that we have the observations of the target at each time instance). Now, lets think of the largest rectangle (window) as a room, while the mouse position represents the person's coordinate in that room. The room is monitored by a camera (top-down) and the task is to track the person's movement. This is a trivial tracking example and it is intended to present the reader how the classical Particle Filter can be used to predict the movement of the person (mouse). This is related to my honours project on Particle Filter (in real environment using real cameras), which can be found in the following link
Problem formulation
The problem of tracking can be formulated as follows:
The above figure shows a target (person) who is walking inside an environment (room), which is monitored by a camera. In this tutorial, we assume that the Segmentation is done, i.e. the system is able to preprocess the frame and obtain the object interest, what is normally called as ForegroundObj. Hence, we narrow down our focus to track the target. In this example, we will merely use the location (In this moment, we disregard the appearance of the target). The above figures clearly visualize what we have covered so far. (Left) Figure shows a real images of the target, whereas (Right) Figure is the current position of the target in real world (x, y, z=0) coordinate.
Sampling
Recall that Particle Filter is three-phased algorithm: Sampling, Importance, and Resampling (SIR). The following figures depicts how the Sampling algorithm works.
|
Sampling is a process of locating all particles randomly to predict the next target's location. This is done using a Probability Density Function (pdf) distribution. Mathematically, the sampling technique can expressed as:
where x denotes the State of a particle, i.e. the position of the person, z is the measurement (observation), and k is the time index. $q(x_k|x_{k-1}^i,z_k)$ is the pdf. In the context of tracking, the above equation can be worded as: how can the system predicts the target's position, at current time period k, given a knowledge of where the target might be at an instant before k-1?. The answer is: given an input particle at (x,y) coordinate, the posterior distribution is equal to the addition of some random numbers with the particle's position of (x,y) coordinate. This implies that the target may move randomly, but still be found by a number of particles.
|
Importance
In order to measure the wellness of the state's prediction, all the particles are weighted based on how close they are to the observation. The weighting function refers to the computation on the previous weight times the probability of the real observation to the states divided by the sampling factor and normalised:
In other words, both equations are expressed in the following sentences: Given what the system can see, update my belief about where the target is. The 'closest' blob is chosen as the current observation measurement. If there exists such observation, then all particles are weighted proportional to their distance from the target. Otherwise, all the particles are assigned with the same weight. This implies that the target is not under the camera field-of-view (FOV), for example, the target is out of view or under occlusion.
The importance can be expressed as: Given what I observed, update my current belief. The states closer to the observation will have higher weights than those far away. This is done through the use of an exponential function, $e^{(-x)}$ (for $x \le 0$). In the implementation, first, we calculate the Distance between each particles' position with comparison to the observed location. Then, the current weight of a particle is derived from the previous weight multiplied by the exponential function of the distance (for x greater than 0).
The exponential function with respect to $(x \le 0)$ will behave as follow: from the above figure, and we can see that the $y$ value gives a number between 0 and 1. When we implement the $x$ as the distance between the particles to the observation, this indicates the further the distance, the smaller the weight (as $y$ value reaches 0). As a result, only particles that are close to the observation blob will have high weight, i.e. the $y$ value is close to 1.
Resampling
Resampling procedure maintains large weight particles while removing small weight particles. Over time, the weight of a number of particles will become very large while the remaining particles have value that is relatively small, which are negligible. Thus, the resampling stage ensures of keeping the larger-weighted particles. A suitable way to measure the need of resampling is to compute the effective sample size, $\widehat{N_{eff}}$, expressed in equation \ref{eq:Neff}.
The need of resampling is computed through the effective sample size, $N_{eff}$. The equation of the effective sample size can be expressed as $\widehat{N_{eff}} = \frac{1}{\sum_{i=1}^{N_s}{(w_i^k)^2)}}$. From this equation, we observe that the value of $\widehat{N_{eff}}$ gets larger when the particles are of equal size. On the other hand, $\widehat{N_{eff}}$ will employ a small value when all particles are scattered, which implies that the particles need to be resampled. To prove that, we present table \ref{tbl:Experiment_Neff} which consists of observation on three particles with two different sets of their corresponding weights. The first set of weight illustrates roughly equal number of weights for all particles, which implies all the particles' predictions are equally correct. Whereas, the second set of weight represents one heavy-weighted particle, while the remaining has very small weights. In the end, we obtain a bigger value in $\widehat{N_{eff}}$ for set 1 as compared to set 2. This has proved the previous explanation. In the second set, only a small number of particles are of important, while the rest are neglectgible, which means the particles need to be resampled.
| _ |
Set 1 |
Set 2 |
| Weight of particle 1 |
0.33 |
0.9 |
| Weight of particle 2 |
0.33 |
0.05 |
| Weight of particle 3 |
0.34 |
0.05 |
| Neff value = |
2.994 |
1.227 |
As can be seen from algorithm \ref{algo:Resample_}, $u_j$ increment linearly with a factor of $\frac{1}{N_s} * (j-1)$, while the $c_i$ is a cumulative density function (CDF) that represented by $c_i = c_{i-1} + w_k^i$. Hence the comparison of ($u_j \le c_i$) will determine whether the weight of particle $j$ is a dominant weight (heavy-weighted particle). If a dominant particle $i$ is found, we then move all the particles with smaller weight, that is of index $j$ to contain the state of particle $i$. Hence this statement ``Particle with higher weight get resample more often than those who has negligible small weight'' is implemented through this procedure. The observation on the resampling algorithm is shown in figure \ref{fig:resampleAlgo}:
Conclusion
In this page, we have shown that Particle Filter is a technique that can be used to track mouse's movements. That is, first, given the current position of a target, we randomly generated points (particles) around that position as prediction to the next target's movement. Secondly, we check our 'random guessing' particles with the real observation and particles that are closer to the real measurement will employ a higher weight than those far away. Finally, we use resample to move the small weighted particles to larger weight, in other words we are taking all the 'random guessing' to the correct measurement.
In the second applet example, KeyboardTracker, we will show a more extended Particle Filter to handle multi targets tracking. (And probably show the non-overlapped region tracking using Particle Filter).
References
Maskell, S. and Gordon, N. (2001), A Tutorial on Particle Filter for On-line Nonlinear/Non-Gaussian Bayesian Tracking. IEE Target Tracking: Algorithms and Applications (Ref. No. 2001/174), 2, 2/1-2/15.
This page is maintained by Wilson Suryajaya Leoputra
