Pattern Recognition Applet: Particle Filter

The particle filters are based on sequential Monte Carlo (SMC) technique. It is a technique for implementing a recursive Bayesian filter by MC simulations. Particles filters are used to model signals using sequential prediction techniques. A particle filter is represented by two state space equations:
state equation: x(k) = (Fx(k-1),u(k-1))
observation equation: y(k) = (Hx(k),v(k))
using basic matrix computation.

The process noise and observation noise can have either Gaussina or nonGaussian statistics. State transition model and observation model can be either linear or nonlinear and also both of this models can be time-varying. For the current implementation, the particle filters are modeled on kalman filter algorithm.

The algorithm is called "particle" filter as the probability distribution of an observation is represented in terms of finite number of samples (which are called particles). Hence, the probability statistics will define the average value of the samples. These particles individually are transformed with the help of the transition model and observation model. At a given time instant, the statistics governing the particles will define the effective (average or mean) state value. The algorithm implemented is based on the kalman filtering approach, with an probability ideology. It is similar to unscented Kalman filter in a way that an observation is defined in terms of a set of points. (for PF, particles while that for UKF, sigma points).

The algorithm can be described in two main steps that iterate through all the observations in a sequence similar to that seen for kalman filter. The implementation is specific to Gaussian statistics for noise and state evolution being modeled as AR signal.


Here is an example run through of the particle filtering algorithm:
  • First, the user must enter an input signal in the Input Display box. There is a random signal that can be used by selecting Random Signal from the Patterns menu. The user also can input data points on the input panel by clicking or dragging the mouse. The points must be clicked from left to right because the x-axis represents the time axis (time progression). Then, select Particle Filtering from the Algorithms menu.

    Particle Filtering

  • Next, the points need to be initalized. Under the Go menu click Initialize. If the points are not all from left to right along the time axis, an error message will appear. The points should then be cleared, re-entered, and re-initialized.

    To go through each step Next for each step. Step 1, after initialization, displays the input points in the Output Display box.

    The second step gives some basic information. The state and observation equations are given. Notice that the calculation of the next state is dependent on the previous state plus some noise term, and the next observation is dependent upon the previous state with some noise as well. Variables 'F' and 'H' represent the transition and observation model that in this case are both equal to one. Also, the noise variances are displayed along with the number of particles to be used.

    Particle Filtering

  • If the user opts to use the red data points, Input Class 0, the first two iterations will be given step by step. All the particles are shown for first time slot or sample. From the calculation of the weights of the particles, the prediction is made for that time.

    Particle Filtering

  • After the first two iterations, the remaining samples will be run at once. The predicted signal is left at each sample time and is continuously drawn by a line.

    Particle Filtering

    Once the algorithm finishes, the mean square error is calculated and shown. This completes the process.

    Particle Filtering



    Click here to go back to the main tutorial page.