Bayesian Filtering

Bayesian filtering is the framework for estimating a hidden state that changes over time, such as the position and velocity of a tracked object or the pose of a moving camera, from a stream of noisy measurements. It maintains a probability distribution over the state and updates it recursively: predict how the state has evolved, then correct the prediction with the newest measurement using Bayes’ rule. The Kalman filter, particle filters, and grid-based filters are all ways of carrying out this one recursion under different assumptions, which is why the framework underlies most probabilistic object tracking and visual state estimation.

Definition

A Bayesian filter computes, at every time step $k$, the posterior distribution $p(\mathbf{x}_k \mid \mathbf{z}_{1:k})$ of the current state $\mathbf{x}_k$ given all measurements so far, $\mathbf{z}_{1:k} = (\mathbf{z}_1, \ldots, \mathbf{z}_k)$. It does so recursively: the posterior at step $k$ is computed from the posterior at step $k-1$ and the new measurement $\mathbf{z}_k$ alone, without revisiting earlier data. This posterior is often called the belief.

Point estimates, such as the posterior mean or mode, and uncertainty measures, such as its covariance, are derived from it.

Intuition

Picture a navigator without satellite positioning. Between landmarks, dead reckoning moves the estimated position forward while the uncertainty grows; a lighthouse sighting then narrows it to the positions consistent with both. A Bayesian filter does this with probability distributions. The predict step pushes the belief through the motion model, which moves it and spreads it out. The update step multiplies the belief by how well each possible state explains the new measurement, then renormalizes, which sharpens it. If the measurement is ambiguous, for example because several places look alike, the belief can keep several separate peaks until later measurements rule all but one out.

Formal Definition

State-space model

The filter assumes a probabilistic state-space model with three parts:

• an initial distribution $p(\mathbf{x}_0)$;
• a transition model $p(\mathbf{x}_k \mid \mathbf{x}_{k-1})$, describing how the state evolves;
• a measurement model, or likelihood, $p(\mathbf{z}_k \mid \mathbf{x}_k)$, describing how measurements are generated from the state.

Two conditional independence assumptions make recursion possible:

• First-order Markov dynamics. Given the previous state, the current state is independent of all earlier states and measurements: $p(\mathbf{x}_k \mid \mathbf{x}_{0:k-1}, \mathbf{z}_{1:k-1}) = p(\mathbf{x}_k \mid \mathbf{x}_{k-1})$.
• Conditionally independent measurements. Given the current state, a measurement is independent of all other states and measurements: $p(\mathbf{z}_k \mid \mathbf{x}_{0:k}, \mathbf{z}_{1:k-1}) = p(\mathbf{z}_k \mid \mathbf{x}_k)$.

A common way to specify these densities is with functions and noise, $\mathbf{x}_k = f(\mathbf{x}_{k-1}) + \mathbf{w}_k$ and $\mathbf{z}_k = h(\mathbf{x}_k) + \mathbf{v}_k$, with independent noise sequences $\mathbf{w}_k$ and $\mathbf{v}_k$. The state must be chosen so that the Markov assumption holds: a position-only state is not Markov for an object that moves with momentum, while position plus velocity can be.

Predict

Given the previous posterior $p(\mathbf{x}_{k-1} \mid \mathbf{z}_{1:k-1})$, the prediction for step $k$ follows from the Chapman–Kolmogorov equation, which marginalizes over the previous state:

$$p(\mathbf{x}_k \mid \mathbf{z}_{1:k-1}) = \int p(\mathbf{x}_k \mid \mathbf{x}_{k-1}) \, p(\mathbf{x}_{k-1} \mid \mathbf{z}_{1:k-1}) \, d\mathbf{x}_{k-1}$$

The Markov assumption is what allows $p(\mathbf{x}_k \mid \mathbf{x}_{k-1}, \mathbf{z}_{1:k-1})$ to be replaced by the transition model.

Update

When $\mathbf{z}_k$ arrives, Bayes’ rule combines the prediction, which acts as the prior, with the likelihood:

$$p(\mathbf{x}_k \mid \mathbf{z}_{1:k}) = \frac{p(\mathbf{z}_k \mid \mathbf{x}_k) \, p(\mathbf{x}_k \mid \mathbf{z}_{1:k-1})}{p(\mathbf{z}_k \mid \mathbf{z}_{1:k-1})}$$

with the normalizing constant

$$p(\mathbf{z}_k \mid \mathbf{z}_{1:k-1}) = \int p(\mathbf{z}_k \mid \mathbf{x}_k) \, p(\mathbf{x}_k \mid \mathbf{z}_{1:k-1}) \, d\mathbf{x}_k .$$

Conditional independence of the measurements is what allows $p(\mathbf{z}_k \mid \mathbf{x}_k, \mathbf{z}_{1:k-1})$ to be replaced by the measurement model. The normalizer is the predictive probability of the measurement; trackers use it to score how plausible a measurement is under a track. For a discrete state, the integrals become sums. If no measurement arrives at step $k$, the update is skipped and the prediction is the posterior.

Properties

Why the general recursion is intractable

The two equations are exact but, in general, only conceptual. For nonlinear dynamics or measurements, or non-Gaussian noise, the integrals have no closed form and the posterior has no fixed parametric shape: it can become skewed or multimodal. Representing it on a grid works in low dimensions, but the number of cells grows exponentially with the state dimension. Every practical Bayesian filter is therefore either an exact solution for a restricted model or an approximation (Arulampalam et al., 2002).

The family of filters

• Kalman filter: the exact linear-Gaussian case. If the transition and measurement models are linear with additive Gaussian noise, and the initial distribution is Gaussian, every prediction and posterior is Gaussian. The recursion then reduces to updating a mean and a covariance in closed form. Ho and Lee (1964) formulated estimation in these Bayesian terms and showed that, under linear-Gaussian assumptions, the recursion yields the Kalman filter.
• Extended and unscented Kalman filters. For nonlinear models, these filters keep a Gaussian belief but approximate how it propagates. The extended Kalman filter linearizes the models around the current estimate; the unscented Kalman filter passes a small, deterministically chosen set of points through the nonlinear functions and refits a Gaussian. Both can perform poorly when the true posterior is far from Gaussian, for example bimodal.
• Grid-based filters. If the state takes finitely many values, the recursion is computed exactly as sums over a table of probabilities. A continuous state can be discretized into cells, which approximates the posterior with a histogram of any shape, at a cost that grows quickly with dimension.
• Particle filters. Sequential Monte Carlo methods represent the posterior by a set of weighted samples: each sample is propagated through the transition model and reweighted by the likelihood, and samples are resampled so that computation concentrates where the probability is. The sampling importance resampling, or bootstrap, filter of Gordon, Salmond and Smith (1993) is the basic form. Particle filters handle arbitrary models and multimodal beliefs, but the number of samples needed can grow exponentially with the size of the problem, which limits them in high dimensions (Snyder et al., 2008).

Filtering, prediction, and smoothing

Filtering estimates the current state from measurements up to now, $p(\mathbf{x}_k \mid \mathbf{z}_{1:k})$. Prediction estimates a future state, $p(\mathbf{x}_{k+n} \mid \mathbf{z}_{1:k})$ with $n > 0$, by applying the predict step repeatedly without updates. Smoothing estimates a past state from measurements that include later ones, $p(\mathbf{x}_j \mid \mathbf{z}_{1:T})$ with $j < T$, typically by a backward pass after the forward filter. Smoothed estimates are usually more accurate because they use more data, but they are available only after the fact, which suits offline video analysis rather than online tracking (Särkkä, 2013).

Examples

Tracking a target’s position

With an object’s image position and velocity as the state, a constant-velocity transition model, and a detector’s position with Gaussian noise as the measurement, the problem is linear-Gaussian and the Kalman filter is the exact Bayesian filter. When the likelihood comes from appearance, such as a color-histogram or template score over the image, clutter and look-alike objects make it multimodal, and particle filters are used instead; CONDENSATION (Isard & Blake, 1998) is a classic instance in visual tracking.

A grid-based filter in one dimension

The example below tracks an object moving around a circular track of 60 cells. Each step it usually advances one cell, sometimes zero or two. The camera cannot measure position; it only reports whether the object is at one of seven identical markers, with a 5% false-detection rate and a 10% miss rate. A Kalman filter cannot represent this problem, because the belief is multimodal: seeing a marker means being near any one of seven places.

import numpy as np

n = 60                                    # cells on a circular 1D track
markers = np.zeros(n, dtype=bool)
markers[[4, 11, 19, 22, 34, 41, 52]] = True   # identical-looking markers

p_move = np.array([0.05, 0.9, 0.05])      # moves 0, 1 or 2 cells per step
p_hit, p_false = 0.9, 0.05                # P(marker seen | at marker / not)

def predict(bel):
    # Chapman-Kolmogorov sum: convolve the belief with the motion model.
    return sum(p * np.roll(bel, s) for s, p in enumerate(p_move))

def update(bel, seen):
    like = np.where(markers, p_hit, p_false)  # p(z_k | x_k) for "seen"
    if not seen:
        like = 1.0 - like
    post = like * bel
    return post / post.sum()                  # Bayes' rule, normalized

def peaks(bel, thresh=0.05):
    # Count separated regions of the belief holding at least `thresh` mass.
    mass = bel + np.roll(bel, 1) + np.roll(bel, -1)
    is_peak = (bel >= np.roll(bel, 1)) & (bel > np.roll(bel, -1))
    return int(np.sum(is_peak & (mass >= thresh)))

rng = np.random.default_rng(0)
x = 0                                     # true cell, unknown to the filter
bel = np.full(n, 1.0 / n)                 # uniform prior: no idea where
for k in range(1, 61):
    x = (x + rng.choice(3, p=p_move)) % n
    seen = rng.random() < (p_hit if markers[x] else p_false)
    bel = update(predict(bel), seen)
    if k in (1, 10, 20, 25, 40, 60):
        near = bel[[(x - 1) % n, x, (x + 1) % n]].sum()
        print(f"k={k:2d}  true={x:2d}  MAP={np.argmax(bel):2d}  "
              f"peaks={peaks(bel)}  P(within 1 cell of truth)={near:.2f}")

Output:

k= 1  true= 1  MAP= 0  peaks=0  P(within 1 cell of truth)=0.06
k=10  true= 9  MAP=14  peaks=6  P(within 1 cell of truth)=0.05
k=20  true=19  MAP=19  peaks=4  P(within 1 cell of truth)=0.33
k=25  true=24  MAP=24  peaks=2  P(within 1 cell of truth)=0.79
k=40  true=39  MAP=39  peaks=2  P(within 1 cell of truth)=0.90
k=60  true=58  MAP=59  peaks=1  P(within 1 cell of truth)=0.70

After the first sightings the belief has several peaks, one per hypothesis consistent with the observations, and the most probable cell is wrong. As the object passes more markers, only the hypothesis matching the spacing of sightings survives, and the belief collapses onto the true position. Between markers the motion noise spreads it again, which is why the probability near the truth drops at the end.

Visual odometry and SLAM

Filter-based visual odometry and SLAM take the camera pose and velocity, and sometimes map landmark positions, as the state; the transition model comes from a motion model or an inertial sensor, and the measurement model projects landmarks into the image. Because projection and rotation are nonlinear, these systems use the extended Kalman filter or related approximations, as in MonoSLAM (Davison et al., 2007) and the multi-state constraint Kalman filter for visual-inertial navigation (Mourikis & Roumeliotis, 2007).

Uncertain measurement origin

The update step assumes the filter knows which measurement belongs to its state. With several targets or clutter, that is not given, and the origin of each measurement becomes another unknown. Data association methods either commit to one assignment before the update, or, as in probabilistic data association, average the update over the possible origins weighted by their probabilities, which is itself a Bayesian computation over hypotheses.

Common Misconceptions

• “A Bayesian filter is a specific algorithm.” It is a recursion; the Kalman, particle, and grid filters are implementations of it under different belief representations.
• “The Kalman filter is an approximation of the Bayes filter.” For linear-Gaussian models it is the exact Bayes filter. It becomes an approximation only when applied to models that violate those assumptions, which is the setting of the extended and unscented variants.
• “The filter returns the state.” It returns a distribution. Reporting only its mean can be badly misleading when the belief is multimodal: the mean of two peaks can lie in a region of near-zero probability.
• “A narrow belief is a correct belief.” The posterior is only as good as the model. With a wrong motion model or underestimated noise, the filter becomes overconfident, effectively ignores measurements that disagree with it, and is confidently wrong.

Where It Is Used

• Object tracking. Motion models in object tracking and multi-object tracking, usually a Kalman filter, as in SORT; particle filters for cluttered, multimodal appearance likelihoods.
• Visual odometry, visual-inertial navigation, and SLAM. Recursive estimation of camera pose and map.
• Robot localization. Grid-based and particle-filter localization in a known map.
• Sensor fusion. Cameras combined with radar, LiDAR, or inertial sensors, each through its own measurement model.