Algorithmic and Arch itectural Optimizations for Computationally Efiicient Particle FilteringAswin C. Sankaranarayanan, Ankur Srivastava, and Rama Chellappa |
|
Abstract:
In this paper, we analyze the computational challenges in implementing particle
filtering especially to video sequences. Particle filtering is a technique used
for filtering non-linear dynamical systems driven by non-Gaussian noise
processes. It has found wide-spread applications in detection, navigation and
tracking problems. Although, in general, particle filtering methods yield
improved results, it is difficult to achieve real time performance. In this
paper, we analyze the computational drawbacks of traditional particle filtering
algorithms, and present a new method for implementing the particle filter using
the Independent Metropolis Hastings sampler. The proposed algorithm does not
suffer from any of the drawbacks of the traditional particle filter and is
highly amenable to pipelined implementations and parallelization. We analyze
the implementations of the proposed algorithm, and in particular concentrate on
implementations that have minimum processing times. It is shown that the design
parameters for the fastest implementation can be chosen by solving a set of
convex programs. The proposed computational methodology was verified over a
cluster of PCs for the application of visual tracking. We demonstrate a linear
speedup of the algorithm using the methodology proposed in the paper.
|
| IEEE Transactions on Image Processing (to appear in 2008) |
| A. C. Sankaranarayanan, R. Chellappa and A. Srivastava, "Algorithmic and Architectural Design Methodology for Particle Filters in Hardware", ICCD 2005(pdf) |