How to pick base samples deterministically in the particle filter algorithm?

Question

The particle filter algorithm is known for its use in tracking objects in a video sequence: at each iteration, the algorithm generates hypotheses (or samples) about the motion of the object. In order to generate a new hypothesis, the first step of the condensation algorithm involves the selection of a sample: the example, provided in this web page, shows an implementation of the selection step, which uses the binary search in order to pick a base sample; the comment in support of the pick_base_sample() function explains that

The use of this routine makes Condensation O(NlogN) where N is the number of samples. It is probably better to pick base samples deterministically, since then the algorithm is O(N) and probably marginally more efficient, but this routine is kept here for conceptual simplicity and because it maps better to the published literature.

What it means to pick base samples deterministically? How to pick base samples deterministically?

Answer 1

The condensation algorithm makes use of multiple samples to represent the current estimated state, each sample has an associated weight (that estimates the probability that the sample is correct).

The selection step chooses N samples from this set (with replacement, so the same sample can appear multiple times).

To explain the selection step, imagine drawing the samples as a series of line segments. Let the width of each line segment equal the weight of that sample.

For example, suppose we had samples A (weight 0.1) B (weight 0.3) and C (weight 0.6).

We would draw:

ABBBCCCCCC

The normal random selection process involves drawing samples by picking a random point along this line and seeing which sample appears at that position. The perceived problem with this approach is that it takes O(logN) operations to work out which sample appears at a particular location when using a tree data structure to hold the weights. (Although in practice I would not expect this to be the main processing bottleneck in an implementation)

An alternative deterministic (basically think "repeatable" and "not involving random numbers") approach is to simply choose samples by picking N regularly spaced points along the same line. The advantage of this is that the algorithm to do this takes time O(N) instead of O(NlogN).

(The deterministic algorithm is to loop over all the samples keeping track of the total weight seen so far. Whenever the total weight reaches the next regularly spaced point you collect a new sample. This only requires a single pass over the samples so is O(N).)