The algorithm first draws samples from the prediction density. In the second step, the samples are `moved' towards the modes of the observation likelihood function, but stay in the close vicinity of the drawn samples thanks to the compact support of the window function g. Hence the name of the procedure. In the next step, weights are calculated so that the particle set gives an unbiased estimation of the posterior.
Here is an MPEG (0.7Mb) showing the Local Likelihood Sampling algorithm tracking Japanese License Plates. The tracking works at 65 fps. Only 100 particles were used.
N-IPS, suffers from inefficiency problems if the observation density is uninformative and/or uniformly very small except in a small neighborhood of the true state since then particles which are not in this small vicinity of the ``true'' state will all have roughly equal observation likelihoods and the filter becomes effectively decoupled from the observations.
LS-N-IPS was designed to overcome the problem of N-IPS with peaky observation densities, therefore it is natural to consider it in visual tracking problems. LS-N-IPS combines local search with particle filtering and thus can be thought of as a combination of the two main streams of vision based tracking research mentioned above. As a consequence, the algorithm inherits the high precision of local search based object tracking methods and the robustness of the particle filter based methods, even when a small number of particles is used.
Here is an MPEG (0.7Mb) showing the LS-N-IPS algorithm tracking an object, in a cluttered room. The tracking is real time. Only 100 particles were used.
Here is an MPEG (0.5Mb) showing LS-N-IPS algorithm real-time tracking an hand, in a dark room with 100 particles.
Here is an MPEG (0.7Mb) showing LS-N-IPS algorithm tracking a face, in a dark room with 100 particles. Real time performance.
This MPEG (0.9Mb) shows tracking a hand moving in front of the face, in a cluttered room with only 50 particles. 73 frames can be processed in each seconds. The Local Search is done by an artificial neural network trained in advance.
This MPEG (5.8Mb) shows tracking a facial mask moving in 3D. The Local Search here is a local pose from shading algorithm. The left of the image is the original video, while the right hand side is the tracking result.
The Basic Sequential Importance Sampling algorithm can be very inefficient, and may require a large number of particles to achieve even a modest precision, as many weights can get small quickly. This is because the importance weight can be very small when the new state does not match the history. Since the new state is sampled independently of the past of the process, it can be "contradicting" with the history of the process.
Page maintained by tyus@stella.eotvos.elte.hu.
Last updated 31st May, 2004