Conditional Random Field

A conditional random field (CRF) is a Markov random field over the labels $\mathbf{y}$ of an input $\mathbf{x}$ in which every potential may depend on the whole input, and which is normalized separately for each input. It is therefore a model of the conditional distribution $p(\mathbf{y} \mid \mathbf{x})$ , not of the joint distribution of labels and image. In vision the labels are usually the classes of the pixels of one image, the graph is the pixel grid or, in the fully connected CRF, the complete graph on the pixels, and the input enters through a per-pixel classifier and through pairwise terms that depend on colour and position. Lafferty, McCallum and Pereira (2001) introduced CRFs for segmenting and labelling sequences; Krähenbühl and Koltun (2011) made a CRF with an edge between every pair of pixels practical by mean-field inference with Gaussian filtering, and DeepLab used their model to sharpen the boundaries of a network’s segmentation.

The difference from an MRF is where the image goes. A hidden-MRF model of segmentation puts a prior on the labels and a likelihood $p(\mathbf{x} \mid \mathbf{y})$ on the pixels, and Bayes’ rule makes the posterior an MRF; a CRF writes the posterior directly, with no model of how images are generated. This article covers the definition and its relation to logistic regression, the linear-chain CRF, learning, the grid and fully connected CRFs of segmentation and their mean-field inference, and an example that measures what the dense model adds near object boundaries.

Definition

Let $G$ be a graph (or factor graph) over output variables $\mathbf{y}$ , and let $\mathbf{x}$ be the observed input. Sutton and McCallum (2006, Definition 1.2) define $p(\mathbf{y} \mid \mathbf{x})$ to be a conditional random field if, for any fixed $\mathbf{x}$ , it factorizes according to $G$ . Murphy (2023, §4.4) describes it as a Markov random field on a set of label nodes whose joint distribution is predicted conditional on a fixed set of input nodes. For each image the labels form an MRF; which MRF it is depends on the image.

Krähenbühl and Koltun (2011, §2) state the vision case in the same way: a random field $\mathbf{X}$ of labels over the $N$ pixels and a random field $\mathbf{I}$ of colours, such that $(\mathbf{I}, \mathbf{X})$ is a CRF characterized by a Gibbs distribution $P(\mathbf{X} \mid \mathbf{I}) = \exp(-\sum_c \phi_c(\mathbf{X}_c \mid \mathbf{I})) / Z(\mathbf{I})$ , with the maximum a posteriori labelling as the output.

Intuition

A per-pixel classifier labels each pixel on its own, and the labelling it produces is, in Krähenbühl and Koltun’s words (2011, §2), generally noisy and inconsistent. A CRF adds terms that score whole labellings: a cost whenever two related pixels disagree. What “related” means can be read off the image itself. In a grid CRF two neighbouring pixels are related; in a contrast-sensitive one they are related less strongly across a colour edge; in a fully connected CRF any two pixels are related, by an amount that decays with their distance and with the difference of their colours. Because the model never has to explain where the colours came from, these terms can use any feature of the image, at any range.

Sutton and McCallum (2006, §1.2.3) give the general argument. Modelling $p(\mathbf{x})$ forces a choice between modelling the dependencies among many overlapping input features, which is hard, and assuming them away, which hurts accuracy; a conditional model does neither, and “CRFs make independence assumptions among $\mathbf{y}$ , but not among $\mathbf{x}$ ” (their wording, §1.2.3).

Formal Definition

Log-linear CRFs and logistic regression

With factors (cliques) $c$ and log-linear potentials, the model is

p(\mathbf{y} \mid \mathbf{x}, \theta) = \frac{1}{Z(\mathbf{x}, \theta)} \prod_c \psi_c(\mathbf{y}_c; \mathbf{x}, \theta), \qquad \psi_c(\mathbf{y}_c; \mathbf{x}, \theta) = \exp\!\big(\theta_c^{\mathsf T} \boldsymbol{\phi}_c(\mathbf{x}, \mathbf{y}_c)\big),

where the partition function $Z(\mathbf{x}, \theta) = \sum_{\mathbf{y}} \prod_c \psi_c$ depends on the input as well as on the parameters (Murphy, 2023, Eqs. 4.136–4.137). Murphy notes that the potentials need not be log-linear; they can be neural networks.

With a single output variable this is multinomial logistic regression, so CRFs can be viewed as logistic regression extended to arbitrary graphs (Sutton and McCallum, 2006, §1.4.5). Sutton and McCallum (§1.2.3) also make the generative–discriminative pairing precise: naive Bayes and logistic regression describe the same family of joint distributions, and training naive Bayes for conditional likelihood gives logistic regression; hidden Markov models and linear-chain CRFs stand in the same relation.

Linear-chain CRFs

For a sequence $\mathbf{y} = (y_1, \dots, y_T)$ with input $\mathbf{x}$ , a linear-chain CRF is

p(\mathbf{y} \mid \mathbf{x}) = \frac{1}{Z(\mathbf{x})} \exp\!\Big( \sum_{t=1}^{T} \sum_{k=1}^{K} \lambda_k f_k(y_t, y_{t-1}, \mathbf{x}_t) \Big), \qquad Z(\mathbf{x}) = \sum_{\mathbf{y}} \exp\!\Big( \sum_{t} \sum_{k} \lambda_k f_k(y_t, y_{t-1}, \mathbf{x}_t) \Big),

with real-valued feature functions $f_k$ and weights $\lambda_k$ (Sutton and McCallum, 2006, Eqs. 1.16–1.17; the tutorial’s Eqs. 1.16–1.17 leave the sum over $t$ implicit, and its Eq. 1.21 writes it out; this article takes its sequence equations from the tutorial, not from Lafferty et al.’s paper). The vector $\mathbf{x}_t$ holds whatever parts of the whole input the features at step $t$ need, so a feature can look at the next word, or the next column of a text-line image. If the joint distribution of labels and inputs is a hidden Markov model, its conditional $p(\mathbf{y} \mid \mathbf{x})$ is a linear-chain CRF whose features are indicators of transitions and of label–observation pairs (§1.3.1); a general linear-chain CRF lets transition scores depend on the observation too.

Because $Z(\mathbf{x})$ sums over every label sequence, the normalization is global. Lafferty et al. (2001, §1–2) contrast this with maximum entropy Markov models (MEMMs) and other models built from next-state classifiers, in which the transitions leaving a state are normalized against each other only. They call the result the label bias problem: the mass arriving at a state must be passed on to its successors whatever the observation says, which biases such models toward states with few outgoing transitions; in the extreme, a state with one outgoing transition ignores its observation. A CRF has one exponential model for the whole label sequence given the observations, so the weights of features at different states can be traded off against each other. Murphy (2023, §4.5.3) explains the same effect as blocked information flow: in a locally normalized directed chain, $y_{t-1}$ is independent of $\mathbf{x}_t$ given $y_t$ , so later evidence cannot change an earlier label. Probabilistic graphical models sets this local-against-global normalization in the wider comparison of directed and undirected models. Global normalization has a price that Murphy also names: no distribution over the labels exists until the whole sequence has been seen, which makes CRFs less suited to online inference.

Grid and fully connected CRFs for images

On an image, a pairwise CRF with node and edge potentials is

p(\mathbf{y} \mid \mathbf{x}) = \frac{1}{Z(\mathbf{x})} \prod_{i \sim j} \psi_{ij}(y_i, y_j) \prod_i p(y_i \mid \mathbf{x}_i)

(Murphy, 2023, Eq. 4.140), where $p(y_i \mid \mathbf{x}_i)$ is any discriminative classifier and $i \sim j$ runs over the edges. In energy form, with $Z(\mathbf{I})$ omitted, Krähenbühl and Koltun (2011, Eqs. 1–2) write

E(\mathbf{x}) = \sum_i \psi_u(x_i) + \sum_{i<j} \psi_p(x_i, x_j), \qquad \psi_p(x_i, x_j) = \mu(x_i, x_j) \sum_{m=1}^{K} w^{(m)} k^{(m)}(\mathbf{f}_i, \mathbf{f}_j),

where now $x_i$ is the label of pixel $i$ , the unary $\psi_u(x_i)$ is computed for each pixel by a classifier that produces a distribution over its label (Algorithm 1 initializes $Q_i \propto \exp\{-\psi_u\}$ , so the unary acts as a negative log-probability), each $k^{(m)}(\mathbf{f}_i, \mathbf{f}_j) = \exp(-\tfrac12 (\mathbf{f}_i - \mathbf{f}_j)^{\mathsf T} \Lambda^{(m)} (\mathbf{f}_i - \mathbf{f}_j))$ is a Gaussian kernel on feature vectors, and $\mu$ is a label compatibility function. In the fully connected (dense) CRF the sum runs over all pairs of the $N$ pixels. For segmentation they use two kernels on positions $p$ and colours $I$ (their Eq. 3):

k(\mathbf{f}_i, \mathbf{f}_j) = w^{(1)} \exp\!\Big( -\frac{|p_i - p_j|^2}{2\theta_\alpha^2} - \frac{|I_i - I_j|^2}{2\theta_\beta^2} \Big) + w^{(2)} \exp\!\Big( -\frac{|p_i - p_j|^2}{2\theta_\gamma^2} \Big).

The first, the appearance kernel, ties pixels that are near and similar in colour; the second, the smoothness kernel, removes small isolated regions. The simplest compatibility is the Potts model $\mu(x_i, x_j) = [x_i \ne x_j]$ ; they note that it penalizes “sky” next to “bird” as much as “sky” next to “cat”, and learn a general symmetric $\mu$ as an alternative (§2, §4). The appearance kernel is a bilateral filter’s weight, which is how the filtering literature enters.

Quantity	Krähenbühl and Koltun (2011)	The DeepLab article
Kernel weights	$w^{(1)}, w^{(2)}$	$w_1, w_2$
Spatial width, appearance kernel	$\theta_\alpha$	$\sigma_\alpha$
Colour width, appearance kernel	$\theta_\beta$	$\sigma_\beta$
Spatial width, smoothness kernel	$\theta_\gamma$	$\sigma_\gamma$
Unary	$\psi_u(x_i)$ from a boosted classifier	$-\log P(x_i)$ from a network’s softmax

A grid CRF keeps only the 4- or 8-neighbour pairs. Its energy has the form of the graph cuts labelling energy; what makes it conditional is that the pairwise weights may depend on the image, as in TextonBoost’s grid CRF with colour, location and edge terms, which semantic segmentation describes. Krähenbühl and Koltun (2011, §1) argue that such adjacency CRFs are limited in their ability to model long-range connections and generally oversmooth object boundaries, and that region-based extensions are limited by the unsupervised segmentation that defines their regions.

Properties

Inference on chains and trees

In a linear-chain CRF, the two inference problems, the marginals $p(y_t, y_{t-1} \mid \mathbf{x})$ with $Z(\mathbf{x})$ (for training) and the most likely labelling $\arg\max_{\mathbf{y}} p(\mathbf{y} \mid \mathbf{x})$ (for prediction), are solved exactly by the forward–backward and Viterbi recursions of hidden Markov models, in $O(TM^2)$ time for $M$ labels (Sutton and McCallum, 2006, §1.3.2–1.3.3). Connectionist temporal classification runs the same kind of recursion over a blank-extended label sequence, and tree-structured CRFs such as pictorial structures are solved exactly by dynamic programming (Murphy, 2023, §4.4.2.2).

Approximate inference on grids and dense graphs

For general graphs both problems are NP-hard, and CRF training calls inference at every gradient step; Sutton and McCallum (2006, §1.4.4) report that sampling has been unpopular for this reason and that variational methods, among them loopy belief propagation, have been most popular. The optimizers of the Markov random field article apply to the labelling energy of one image: graph cuts, loopy BP and others.

The fully connected CRF has $N(N-1)/2$ edges, billions for an image of tens of thousands of pixels. Krähenbühl and Koltun (2011, §1) report that MCMC inference in such a model ran for 36 hours and only partially converged on one of their images, and that graph-cut inference did not converge within 72 hours. Their algorithm uses the mean-field approximation instead: find the fully factorized $Q(\mathbf{X}) = \prod_i Q_i(X_i)$ that minimizes $\mathrm{KL}(Q \,\|\, P)$ (§3.1), which gives the update

Q_i(x_i = l) = \frac{1}{Z_i} \exp\Big\{ -\psi_u(x_i) - \sum_{l' \in \mathcal{L}} \mu(l, l') \sum_{m=1}^{K} w^{(m)} \sum_{j \ne i} k^{(m)}(\mathbf{f}_i, \mathbf{f}_j)\, Q_j(l') \Big\}

(their Eq. 4). Their Algorithm 1 initializes $Q_i$ from the unaries and then repeats four steps for all pixels at once: message passing ( $\sum_{j \ne i} k^{(m)} Q_j(l)$ ), a compatibility transform by $\mu$ , a local update adding the unary, and normalization. The minimized quantity is the variational free energy,

F(Q) = \sum_i \sum_l Q_i(l)\, \psi_u(l) + \sum_{i<j} \sum_{l, l'} Q_i(l)\, \mu(l, l')\, k(\mathbf{f}_i, \mathbf{f}_j)\, Q_j(l') + \sum_i \sum_l Q_i(l) \log Q_i(l) = \mathrm{KL}(Q \,\|\, P) - \log Z(\mathbf{I}),

the negative of the evidence lower bound that Evidence Lower Bound derives (our notation; the identity follows from the definitions). Updating one $Q_i$ at a time with Eq. 4 is coordinate ascent on the bound, for which Murphy (2023, §10.3.1) states that convergence is guaranteed because the bound is concave in each factor. Updating all pixels at once, as Algorithm 1 does, carries no such guarantee in that argument; Murphy (§10.3.2) uses parallel updates with damping in his Ising example and notes that without damping they tend to produce checkerboard artifacts. Krähenbühl and Koltun report convergence empirically, by the KL divergence (up to a constant) over iterations averaged over 94 MSRC-21 images (Fig. 2), and use 10 iterations in their experiments (§6).

Message passing as Gaussian filtering

The message step is the expensive one: for each pixel a sum over every other pixel, quadratic in $N$ . Krähenbühl and Koltun (2011, Eq. 5) observe that it is a convolution with a Gaussian in feature space, minus the pixel’s own term:

\tilde{Q}^{(m)}_i(l) = \big[ G_{\Lambda^{(m)}} \otimes Q(l) \big](\mathbf{f}_i) - Q_i(l).

The convolution is a low-pass filter, so it can be computed on a downsampled set of points and interpolated back, which makes approximate message passing $O(N)$ (§3.2). They use the permutohedral lattice of Adams et al., which needs unit-variance kernels and so whitens the features by a Cholesky factor of $\Lambda^{(m)}$ , with complexity $O(Nd)$ in the feature dimension $d$ . They downsample at one standard deviation, and normalize each pixel’s filtered value by its total kernel weight to correct the lattice’s underestimate of the kernel for similar points, which works better in practice but “slightly violates” the symmetry of the potentials (§5). A single-threaded implementation labelled an MSRC-21 image in 0.2 seconds (Fig. 1).

Learning

The parameters are fitted by maximizing the conditional log-likelihood $\ell(\theta) = \sum_n \log p(\mathbf{y}^{(n)} \mid \mathbf{x}^{(n)})$ , usually with a Gaussian penalty that can be read as MAP estimation under a Gaussian prior on $\theta$ (Sutton and McCallum, 2006, Eqs. 1.18–1.21). For log-linear potentials the gradient of the average $\ell / N$ over $N$ training pairs is

\frac{1}{N} \frac{\partial \ell}{\partial \theta_c} = \frac{1}{N} \sum_n \Big( \boldsymbol{\phi}_c(\mathbf{y}_{n,c}, \mathbf{x}_n) - \mathbb{E}_{p(\mathbf{y} \mid \mathbf{x}_n, \theta)}\big[ \boldsymbol{\phi}_c(\mathbf{y}, \mathbf{x}_n) \big] \Big)

(Murphy, 2023, Eq. 4.146): the features’ empirical value minus their expectation under the model, as for an MRF, and the objective is concave in $\theta$ , so every local optimum is global (Sutton and McCallum, §1.3.2). Unlike an MRF, the expectation has to be computed for every training input, because $Z(\mathbf{x}_n)$ differs from one input to the next (Murphy, §4.4.3.2; Sutton and McCallum, §1.3.2). Sutton and McCallum report that quasi-Newton methods (limited-memory BFGS) and conjugate gradient train much faster than the iterative scaling of Lafferty et al.’s paper. On grids the expectations are approximate, and Sutton and McCallum (§1.4.5) list pseudolikelihood and maximum-margin training among the alternative objectives.

Krähenbühl and Koltun (2011, §4) trained piecewise: first the boosted unary classifiers (JointBoost on TextonBoost-style features), then the CRF. Because the gradients with respect to the kernel widths are not Gaussian filters, they set $w^{(1)}$ , $\theta_\alpha$ and $\theta_\beta$ by grid search on a held-out validation set, fixed $w^{(2)} = \theta_\gamma = 1$ , which they found to affect accuracy little, and learned a general compatibility $\mu$ by L-BFGS, using the mean-field approximation to estimate the gradient of the partition function (their Eq. 6). DeepLab’s CRF was also trained piecewise, with the network fixed and $w_1$ , $\sigma_\alpha$ , $\sigma_\beta$ found by search on validation images, as DeepLab reports.

Results that motivated the dense model

On MSRC-21, with the same unaries for every model, Krähenbühl and Koltun (2011, Fig. 3, read from the page image) report global and average accuracy against the standard ground truth of 84.0% and 76.6% for the unaries, 84.6% and 77.2% for the grid CRF of Shotton et al. (1 s), 84.9% and 77.5% for Kohli et al.’s Robust $P^n$ CRF (30 s), and 86.0% and 78.3% for the fully connected CRF (0.2 s). Because the standard annotations leave regions around boundaries unlabelled, they hand-labelled 94 images accurately; against these, by 5-fold cross-validation, global accuracy was $83.2 \pm 1.5$ , $84.8 \pm 1.5$ , $86.5 \pm 1.0$ and $88.2 \pm 0.7$ for the same four. Following Kohli et al., they also measured the error in a narrow band (“trimap”) around true object boundaries, and the fully connected CRF had the lowest error at every trimap width they plotted (Fig. 4). On their own 40/15/45 split of the PASCAL VOC 2010 training and validation data the average accuracy was 27.6% for the unaries, 28.3% for the grid CRF, 29.1% for the dense CRF with Potts potentials and 30.2% with a learned compatibility, at 0.5 s per image (§6). With $w^{(2)} = 0$ , accuracy on the 94 images peaked at $\theta_\alpha = 61$ pixels and $\theta_\beta = 11$ ; their failure cases show long-range connections propagating wrong labels, eroding a bird’s wing and a cat’s legs (Figs. 6–7).

CRFs inside networks

Zheng et al. (2015) wrote each mean-field iteration of the dense CRF as a stack of network layers: Gaussian filtering for message passing, a $1 \times 1$ convolution for the compatibility transform (learned, and not required to be symmetric), the addition of the unaries and a softmax for normalization (§4). Repeating the iteration with shared parameters is a recurrent network, CRF-RNN, which they trained end to end with the segmentation network, using $T = 5$ iterations in training and 10 at test time (§5.1, §6). Murphy (2023, §4.4.2.1) notes that this unrolling avoids the partition function in training. DeepLab used the dense CRF as post-processing in its first two versions and dropped it in DeepLabv3, and its later decoder took over boundary recovery.

Examples

What dense connections add at object boundaries

The script labels a synthetic image with three CRFs and measures the error near the true boundaries with a trimap measure after Krähenbühl and Koltun’s, whose band definition is ours. It runs their model exactly: every pairwise weight is held in an $N \times N$ matrix and every message is an exact sum, with no permutohedral lattice and no normalization, which a $48 \times 48$ image ( $N = 2{,}304$ ) allows.

Scene: a $48 \times 48$ RGB image with colours in $[0, 1]$ and three labels. The background (label 0) is sky in the top half and ground in the bottom half, a colour edge inside one class. Class 1 is a body with two legs and an ear, each 2 pixels wide; class 2 is a disk with a pole 2 pixels wide, coloured $(0.40, 0.55, 0.85)$ , close to the sky’s $(0.55, 0.70, 0.90)$ . Gaussian colour noise of standard deviation 0.04 per channel.
Unaries: a simulated classifier at full resolution. Each class’s one-hot map is blurred by a Gaussian of 1.5 pixels, Gaussian noise of 0.15 is added to each class map, and $P = \mathrm{softmax}(\text{score}/0.1)$ ; the unary is $-\log P$ . Semantic segmentation’s example measures what a 1/8-stride prediction costs before any refinement; here the classifier is at full resolution and the measure is what a CRF adds to it.
Methods: the unary argmax; a 4-connected Potts grid CRF with weight $w_g$ (plain Potts, with no image-dependent weight); a dense CRF with the smoothness kernel only ( $w^{(2)}$ , $\theta_\gamma$ ); and the dense CRF of Eq. 3 with $w^{(2)} = \theta_\gamma = 1$ as in the paper ( $w^{(1)}$ , $\theta_\alpha$ , $\theta_\beta$ ). Positions are in pixels and colour differences in $[0, 1]$ units.
Inference: Algorithm 1 with Potts $\mu$ , from $Q = P$ , 10 parallel iterations, labels $\arg\max Q$ . For a check of the free energy, the same CRFs are also run with sequential updates, one pixel at a time in raster order, for 10 sweeps.
Parameter choice: as in the paper, by grid search on held-out images: three validation images (noise seeds 100–102) with the same layout as the test images, choosing the setting with the lowest mean overall pixel error. Grids: $w_g \in \{0.1, 0.3, 1, 3\}$ ; $w^{(2)} \in \{0.1, 0.3, 1, 3\}$ , $\theta_\gamma \in \{1, 2, 4, 8\}$ ; $w^{(1)} \in \{0.003, 0.01, 0.03, 0.1, 0.3\}$ , $\theta_\alpha \in \{3, 6, 12, 24\}$ , $\theta_\beta \in \{0.05, 0.1, 0.2\}$ . Test images use noise seeds 0–4.
Measures: the overall pixel error, and the trimap error, the fraction of misclassified pixels in a band of width 2, 4 or 8 pixels across the true boundaries. A boundary pixel is one with a 4-neighbour of another true label, and band( $w$ ) holds the pixels within Euclidean distance $w/2 - 1$ of one, so band(2) is the boundary pixels themselves, one row on each side of every boundary. This band definition is ours; Kohli et al.’s was not read. The free energy $F(Q)$ above is printed at the start and end of both schedules, with the number of iterations in which it rose and the largest change between iterations.

Seven checks test the data and code: the scene’s pixel counts (C1); the colour noise’s standard deviation within 0.002 of 0.04 on every image (C2); the unaries sum to one within $10^{-12}$ (C3); the unaries make no errors outside band(8) on the test images, and their band-2 error exceeds their overall error on the validation images (C4); on a $3 \times 3$ image with three labels, the matrix messages equal a brute-force double loop within $10^{-12}$ , and $F(Q)$ equals $\mathrm{KL}(Q \,\|\, P) - \log Z$ computed by enumerating all 19,683 labellings within $10^{-10}$ (C5); under sequential updates no sweep raises $F$ by more than $10^{-9}$ of its final magnitude, for every CRF and test image (C6); and with clean colours and one-hot unaries every method labels the image without error at its chosen parameters (C7). The three hypotheses were written before any script for the example ran: (H1) the appearance-and-smoothness dense CRF has the lowest band-2 error of the four methods, strictly, in the mean over the five test images and on at least four of them, after Krähenbühl and Koltun’s Fig. 4; (H2) the grid CRF’s reduction of band-2 error below the unaries is smaller than the dense CRF’s, in the mean and on at least four of the five images, after the same figure; (H3) in our reading, under parallel updates the dense CRF’s free energy rises at least once in its 10 iterations on at least one test image.

The script uses NumPy 2.3.5 and SciPy 1.16.3 and takes about 45 seconds.

# What dense connections add at object boundaries: grid and fully connected CRFs (Krähenbühl & Koltun 2011, Eqs. 1-4)
# on a synthetic 48 x 48 RGB image with three classes, exact O(N^2) mean field in NumPy.
import os
os.environ["OPENBLAS_NUM_THREADS"] = "1"; os.environ["OMP_NUM_THREADS"] = "1"; os.environ["MKL_NUM_THREADS"] = "1"
import itertools
import numpy as np
from scipy.ndimage import gaussian_filter, distance_transform_edt

H = W_ = 48; N = H * W_; L = 3
SIG_C, S_U, SIG_U, TAU = 0.04, 1.5, 0.15, 0.1      # colour noise, unary blur (px), unary noise, softmax temperature
SKY, GROUND = (0.55, 0.70, 0.90), (0.35, 0.55, 0.25)
COL1, COL2 = (0.80, 0.35, 0.20), (0.40, 0.55, 0.85)
MU = 1.0 - np.eye(L)                                  # Potts compatibility mu(l, l') = [l != l']
ITERS = 10                                            # mean-field iterations (KK, Sec. 6)
VAL, TEST = (100, 101, 102), (0, 1, 2, 3, 4)
GRID = {"grid CRF": [dict(wg=w) for w in (0.1, 0.3, 1, 3)],
        "dense, smoothness": [dict(w2=w, tg=t) for w in (0.1, 0.3, 1, 3) for t in (1, 2, 4, 8)],
        "dense, appearance+smooth": [dict(w1=w, ta=a, tb=b) for w in (0.003, 0.01, 0.03, 0.1, 0.3)
                                     for a in (3, 6, 12, 24) for b in (0.05, 0.1, 0.2)]}
METHODS = ["unary argmax"] + list(GRID)

# ---- scene and ground truth
yy, xx = np.mgrid[0:H, 0:W_]
gt = np.zeros((H, W_), int)
gt[14:26, 4:24] = 1; gt[26:40, 7:9] = 1; gt[26:40, 19:21] = 1; gt[6:14, 21:23] = 1      # body, two legs, ear
gt[(yy - 34) ** 2 + (xx - 36) ** 2 <= 42.25] = 2; gt[6:28, 35:37] = 2                    # disk and pole
clean = np.where((yy < 24)[..., None], np.array(SKY), np.array(GROUND))
clean[gt == 1] = COL1; clean[gt == 2] = COL2
P4 = np.pad(gt, 1, mode="edge")
bnd = (P4[:-2, 1:-1] != gt) | (P4[2:, 1:-1] != gt) | (P4[1:-1, :-2] != gt) | (P4[1:-1, 2:] != gt)
dist = distance_transform_edt(~bnd)
BANDS = {w: dist <= w / 2 - 1 for w in (2, 4, 8)}  # band of width w px across each true boundary
pos = np.stack([yy.ravel(), xx.ravel()], 1).astype(float)
D2 = ((pos[:, None] - pos[None]) ** 2).sum(-1)       # squared pixel distances, N x N

def softmax(s):
    s = s - s.max(-1, keepdims=True); e = np.exp(s); return e / e.sum(-1, keepdims=True)

def make(seed, clean_data=False):
    onehot = np.stack([(gt == k).astype(float) for k in range(L)], -1)
    if clean_data:
        return clean.copy(), softmax(onehot / TAU), np.zeros_like(clean)
    rng = np.random.default_rng(seed)
    img = clean + rng.normal(0, SIG_C, clean.shape)
    score = np.stack([gaussian_filter(onehot[..., k], S_U, mode="nearest") for k in range(L)], -1)
    score = score + rng.normal(0, SIG_U, score.shape)
    return img, softmax(score / TAU), img - clean

def weights(method, prm, img):
    if method == "grid CRF":
        Wm = np.where(D2 == 1, float(prm["wg"]), 0.0)
    elif method == "dense, smoothness":
        Wm = prm["w2"] * np.exp(-D2 / (2 * prm["tg"] ** 2))
    else:                                             # KK Eq. 3 with w(2) = theta_gamma = 1
        f = img.reshape(N, 3); C2 = ((f[:, None] - f[None]) ** 2).sum(-1)
        Wm = prm["w1"] * np.exp(-D2 / (2 * prm["ta"] ** 2) - C2 / (2 * prm["tb"] ** 2)) + np.exp(-D2 / 2)
    np.fill_diagonal(Wm, 0.0)                         # messages exclude j = i
    return Wm

def free_energy(Q, U, Wm):                            # F(Q) = KL(Q || P_crf) - log Z(I)
    return float((Q * U).sum() + 0.5 * ((Q @ MU) * (Wm @ Q)).sum() + (Q * np.log(Q)).sum())

def mean_field_parallel(U, Wm):                       # KK Algorithm 1: all pixels at once
    Q = softmax(-U); F = [free_energy(Q, U, Wm)]
    for _ in range(ITERS):
        Q = softmax(-U - (Wm @ Q) @ MU)               # message passing, compatibility transform, local update
        F.append(free_energy(Q, U, Wm))
    return Q, F

def mean_field_sequential(U, Wm):                     # coordinate ascent: one pixel at a time, raster order
    Q = softmax(-U); F = [free_energy(Q, U, Wm)]
    for _ in range(ITERS):
        for i in range(N):
            Q[i] = softmax(-U[i] - MU @ (Wm[i] @ Q))
        F.append(free_energy(Q, U, Wm))
    return Q, F

def errors(lab):
    e = lab != gt
    return [e.mean()] + [e[BANDS[w]].mean() for w in (2, 4, 8)]

print(f"scene: class 0 {int((gt == 0).sum())}, class 1 {int((gt == 1).sum())}, class 2 {int((gt == 2).sum())} px; "
      f"boundary px {int(bnd.sum())}; band px " + ", ".join(f"{w}: {int(b.sum())}" for w, b in BANDS.items()) +
      f"; thin widths {int((gt[30, 5:12] == 1).sum())}, {int((gt[30, 17:23] == 1).sum())}, "
      f"{int((gt[10, 18:26] == 1).sum())}, {int((gt[15, 32:40] == 2).sum())}")

# ---- component checks on a 3 x 3 image with 3 labels (19,683 labellings)
rng = np.random.default_rng(7)
n = 9; Ut = rng.normal(0, 1, (n, L)); pt = np.array([(i // 3, i % 3) for i in range(n)], float); ct = rng.random((n, 3))
d2 = ((pt[:, None] - pt[None]) ** 2).sum(-1); c2 = ((ct[:, None] - ct[None]) ** 2).sum(-1)
Wt = 0.7 * np.exp(-d2 / (2 * 1.5 ** 2) - c2 / (2 * 0.3 ** 2)) + 0.4 * np.exp(-d2 / 2); np.fill_diagonal(Wt, 0.0)
Qt = softmax(rng.normal(0, 1, (n, L)))
brute = np.array([[sum(Wt[i, j] * Qt[j, l] for j in range(n) if j != i) for l in range(L)] for i in range(n)])
labs = np.array(list(itertools.product(range(L), repeat=n)))
E = Ut[np.arange(n), labs].sum(1) + np.array([sum(Wt[i, j] * MU[a[i], a[j]] for i in range(n) for j in range(i + 1, n)) for a in labs])
logZ = np.log(np.exp(-(E - E.min())).sum()) - E.min()
logq = np.log(Qt[np.arange(n), labs]).sum(1)
KL = float((np.exp(logq) * (logq + E + logZ)).sum())
print(f"component: max |W@Q - brute-force message| {np.abs(Wt @ Qt - brute).max():.1e}; "
      f"|F(Q) - (KL(Q||P) - log Z)| {abs(free_energy(Qt, Ut, Wt) - (KL - logZ)):.1e}")

# ---- grid search on validation images (KK: holdout validation), criterion: mean overall pixel error
val = [make(s) for s in VAL]
for s, (img, P, nz) in zip(VAL, val):
    e = errors(P.argmax(-1))
    print(f"val seed {s}: colour noise std {nz.std():.4f}; unary error overall {e[0]:.4f}, band2 {e[1]:.4f}")
best = {}
for method, grid in GRID.items():
    scores = []
    for prm in grid:
        errs = []
        for img, P, _ in val:
            Q, _ = mean_field_parallel(-np.log(P).reshape(N, L), weights(method, prm, img))
            errs.append(errors(Q.argmax(-1).reshape(H, W_))[0])
        scores.append(np.mean(errs))
    k = int(np.argmin(scores)); best[method] = grid[k]
    edge = [key for key, v in grid[k].items() if v in (min(p[key] for p in grid), max(p[key] for p in grid))
            and len({p[key] for p in grid}) > 1]
    print(f"selected {method}: {grid[k]}, validation error {scores[k]:.4f}, at grid edge: {edge if edge else 'none'}")

def label(method, img, P):
    U = -np.log(P).reshape(N, L)
    if method == "unary argmax":
        return P.argmax(-1), None, None
    Wm = weights(method, best[method], img)
    Q, Fp = mean_field_parallel(U, Wm)
    _, Fs = mean_field_sequential(U, Wm)
    return Q.argmax(-1).reshape(H, W_), Fp, Fs

# ---- base check: clean colours, one-hot unaries
img, P, _ = make(None, clean_data=True)
print("base (clean colours, one-hot unaries): errors " +
      ", ".join(f"{m} {int((label(m, img, P)[0] != gt).sum())}" for m in METHODS))

# ---- test images
res = {m: [] for m in METHODS}
for s in TEST:
    img, P, nz = make(s)
    print(f"test seed {s}: colour noise std {nz.std():.4f}; max |sum P - 1| {np.abs(P.sum(-1) - 1).max():.1e}; "
          f"unary errors outside band8 {int((P.argmax(-1) != gt)[~BANDS[8]].sum())}")
    print(f"  {'method':<26}{'overall':>9}{'band2':>9}{'band4':>9}{'band8':>9}")
    for m in METHODS:
        lab, Fp, Fs = label(m, img, P)
        e = errors(lab); res[m].append(e)
        print(f"  {m:<26}" + "".join(f"{v:9.4f}" for v in e))
        if Fp is not None:
            dp = np.diff(Fp); ds = np.diff(Fs)
            print(f"    free energy, parallel: {Fp[0]:.6f} -> {Fp[-1]:.6f}, increases {int((dp > 0).sum())}, "
                  f"max step {dp.max():.3e}; sequential: {Fs[0]:.6f} -> {Fs[-1]:.6f}, max step {ds.max():.3e}, "
                  f"relative {ds.max() / abs(Fs[-1]):.3e}")

print("mean over test seeds 0-4 (overall, band2, band4, band8):")
for m in METHODS:
    print(f"  {m:<26}" + "".join(f"{v:9.4f}" for v in np.mean(res[m], 0)))
b2 = {m: np.array([r[1] for r in res[m]]) for m in METHODS}
ties = [sorted(m for m in METHODS if b2[m][k] == min(b2[q][k] for q in METHODS)) for k in range(len(TEST))]
print("lowest band2 error per seed:", ["/".join(t) for t in ties])
red_g = b2["unary argmax"] - b2["grid CRF"]; red_a = b2["unary argmax"] - b2["dense, appearance+smooth"]
print("band2 reduction below unaries, grid CRF:      ", " ".join(f"{v:.4f}" for v in red_g), f"mean {red_g.mean():.4f}")
print("band2 reduction below unaries, dense app+smth:", " ".join(f"{v:.4f}" for v in red_a), f"mean {red_a.mean():.4f}")

Output:

scene: class 0 1811, class 1 312, class 2 181 px; boundary px 416; band px 2: 416, 4: 715, 8: 1313; thin widths 2, 2, 2, 2
component: max |W@Q - brute-force message| 1.1e-16; |F(Q) - (KL(Q||P) - log Z)| 0.0e+00
val seed 100: colour noise std 0.0399; unary error overall 0.0473, band2 0.2620
val seed 101: colour noise std 0.0404; unary error overall 0.0499, band2 0.2764
val seed 102: colour noise std 0.0395; unary error overall 0.0482, band2 0.2668
selected grid CRF: {'wg': 0.1}, validation error 0.0480, at grid edge: ['wg']
selected dense, smoothness: {'w2': 0.1, 'tg': 1}, validation error 0.0486, at grid edge: ['w2', 'tg']
selected dense, appearance+smooth: {'w1': 0.3, 'ta': 24, 'tb': 0.05}, validation error 0.0019, at grid edge: ['w1', 'ta', 'tb']
base (clean colours, one-hot unaries): errors unary argmax 0, grid CRF 0, dense, smoothness 0, dense, appearance+smooth 0
test seed 0: colour noise std 0.0399; max |sum P - 1| 3.3e-16; unary errors outside band8 0
  method                      overall    band2    band4    band8
  unary argmax                 0.0482   0.2644   0.1552   0.0845
  grid CRF                     0.0490   0.2692   0.1580   0.0861
    free energy, parallel: 34.566092 -> 33.415318, increases 1, max step 2.842e-14; sequential: 34.566092 -> 33.415318, max step 0.000e+00, relative 0.000e+00
  dense, smoothness            0.0490   0.2692   0.1580   0.0861
    free energy, parallel: 52.385432 -> 50.747566, increases 1, max step 5.684e-14; sequential: 52.385432 -> 50.747566, max step 2.842e-14, relative 5.601e-16
  dense, appearance+smooth     0.0009   0.0048   0.0028   0.0015
    free energy, parallel: 4153.953252 -> 881.020441, increases 0, max step 0.000e+00; sequential: 4153.953252 -> 881.020441, max step 1.137e-13, relative 1.290e-16
test seed 1: colour noise std 0.0398; max |sum P - 1| 3.3e-16; unary errors outside band8 0
  method                      overall    band2    band4    band8
  unary argmax                 0.0473   0.2620   0.1524   0.0830
  grid CRF                     0.0477   0.2644   0.1538   0.0838
    free energy, parallel: 33.940710 -> 32.843332, increases 1, max step 2.842e-14; sequential: 33.940710 -> 32.843332, max step 5.684e-14, relative 1.731e-15
  dense, smoothness            0.0486   0.2692   0.1566   0.0853
    free energy, parallel: 51.708543 -> 50.082407, increases 1, max step 2.842e-14; sequential: 51.708543 -> 50.082407, max step 2.842e-14, relative 5.675e-16
  dense, appearance+smooth     0.0009   0.0048   0.0028   0.0015
    free energy, parallel: 4098.779862 -> 849.339221, increases 0, max step 0.000e+00; sequential: 4098.779862 -> 849.339221, max step 1.137e-13, relative 1.339e-16
test seed 2: colour noise std 0.0399; max |sum P - 1| 3.3e-16; unary errors outside band8 0
  method                      overall    band2    band4    band8
  unary argmax                 0.0456   0.2524   0.1469   0.0800
  grid CRF                     0.0447   0.2476   0.1441   0.0784
    free energy, parallel: 33.618874 -> 32.571163, increases 0, max step 0.000e+00; sequential: 33.618874 -> 32.571163, max step 2.842e-14, relative 8.726e-16
  dense, smoothness            0.0460   0.2548   0.1483   0.0807
    free energy, parallel: 52.356460 -> 50.788941, increases 1, max step 2.842e-14; sequential: 52.356460 -> 50.788941, max step 2.842e-14, relative 5.596e-16
  dense, appearance+smooth     0.0004   0.0024   0.0014   0.0008
    free energy, parallel: 4098.853551 -> 881.715523, increases 0, max step -1.968e-08; sequential: 4098.853551 -> 881.715523, max step 1.137e-13, relative 1.289e-16
test seed 3: colour noise std 0.0403; max |sum P - 1| 3.3e-16; unary errors outside band8 0
  method                      overall    band2    band4    band8
  unary argmax                 0.0456   0.2476   0.1469   0.0800
  grid CRF                     0.0456   0.2500   0.1469   0.0800
    free energy, parallel: 32.948403 -> 31.870460, increases 0, max step 0.000e+00; sequential: 32.948403 -> 31.870460, max step 0.000e+00, relative 0.000e+00
  dense, smoothness            0.0456   0.2500   0.1469   0.0800
    free energy, parallel: 50.845249 -> 49.197113, increases 1, max step 2.842e-14; sequential: 50.845249 -> 49.197113, max step 2.842e-14, relative 5.777e-16
  dense, appearance+smooth     0.0022   0.0120   0.0070   0.0038
    free energy, parallel: 3770.516854 -> 873.577428, increases 0, max step -3.360e-09; sequential: 3770.516854 -> 873.577428, max step 1.137e-13, relative 1.301e-16
test seed 4: colour noise std 0.0396; max |sum P - 1| 3.3e-16; unary errors outside band8 0
  method                      overall    band2    band4    band8
  unary argmax                 0.0460   0.2548   0.1483   0.0807
  grid CRF                     0.0456   0.2524   0.1469   0.0800
    free energy, parallel: 33.579357 -> 32.539738, increases 1, max step 5.684e-14; sequential: 33.579357 -> 32.539738, max step 2.842e-14, relative 8.734e-16
  dense, smoothness            0.0460   0.2548   0.1483   0.0807
    free energy, parallel: 51.676357 -> 50.172650, increases 1, max step 2.842e-14; sequential: 51.676357 -> 50.172650, max step 2.842e-14, relative 5.665e-16
  dense, appearance+smooth     0.0009   0.0048   0.0028   0.0015
    free energy, parallel: 4089.982286 -> 901.789503, increases 1, max step 1.137e-13; sequential: 4089.982286 -> 901.789503, max step 0.000e+00, relative 0.000e+00
mean over test seeds 0-4 (overall, band2, band4, band8):
  unary argmax                 0.0465   0.2562   0.1499   0.0816
  grid CRF                     0.0465   0.2567   0.1499   0.0816
  dense, smoothness            0.0470   0.2596   0.1516   0.0826
  dense, appearance+smooth     0.0010   0.0058   0.0034   0.0018
lowest band2 error per seed: ['dense, appearance+smooth', 'dense, appearance+smooth', 'dense, appearance+smooth', 'dense, appearance+smooth', 'dense, appearance+smooth']
band2 reduction below unaries, grid CRF:       -0.0048 -0.0024 0.0048 -0.0024 0.0024 mean -0.0005
band2 reduction below unaries, dense app+smth: 0.2596 0.2572 0.2500 0.2356 0.2500 mean 0.2505

All seven checks held. The scene has the planned counts and four thin parts 2 pixels wide (C1); every printed standard deviation of the colour noise is within 0.0005 of 0.04 (C2); the unaries sum to one within $3.3 \times 10^{-16}$ (C3); they make no errors outside band(8) on any test image, and on each validation image their band-2 error is more than five times their overall error (0.2620 against 0.0473, 0.2764 against 0.0499 and 0.2668 against 0.0482 on seeds 100–102) (C4); the messages and the free energy agree with brute force and enumeration to $1.1 \times 10^{-16}$ and with a printed difference of zero (C5); the largest rise of $F$ in any sequential sweep is $1.137 \times 10^{-13}$ , and no rise exceeds $1.731 \times 10^{-15}$ of its row’s final value (C6); and on clean data all four methods make no errors (C7).

Every selected parameter lies at the edge of its grid. The grid CRF chose its weakest weight, $w_g = 0.1$ ; the smoothness-only CRF its weakest weight and narrowest kernel, $w^{(2)} = 0.1$ and $\theta_\gamma = 1$ ; and the appearance CRF its strongest weight, widest spatial kernel and narrowest colour kernel, $w^{(1)} = 0.3$ , $\theta_\alpha = 24$ and $\theta_\beta = 0.05$ . The grids were fixed before any result was seen and were not extended, so these are the best settings within them, not optima. The scene favours the appearance kernel: each class differs from its neighbours in colour by much more than the noise of 0.04, and that is the setting the search pushed to its limit.

H1 held. The dense CRF with the appearance kernel has a band-2 error of 0.0048, 0.0048, 0.0024, 0.0120 and 0.0048 on the five test images, that is 2, 2, 1, 5 and 2 of the 416 band pixels, against 0.2644, 0.2620, 0.2524, 0.2476 and 0.2548 for the unaries, and it is strictly lowest on all five; its mean is 0.0058 against 0.2562 for the unaries, 0.2567 for the grid CRF and 0.2596 for the smoothness-only CRF. It also has the lowest error in band 4, in band 8 and overall, on every image.

H2 held. The grid CRF’s reduction of band-2 error below the unaries is $-0.0048$ , $-0.0024$ , $0.0048$ , $-0.0024$ and $0.0024$ (mean $-0.0005$ ), against $0.2596$ , $0.2572$ , $0.2500$ , $0.2356$ and $0.2500$ (mean $0.2505$ ) for the appearance CRF, smaller on all five images. On three images the grid CRF has more errors in band 2 than the unaries it started from, and the smoothness-only CRF’s band-2 error is equal to or higher than the unaries’ on every image. In our reading, from the construction: blurring a one-hot map symmetrically puts the two classes near equal scores at every boundary pixel, so the unary errors are a matter of where the boundary falls, while a pixel’s grid or short-range neighbours lie on both sides of the boundary, so they favour neither label strongly, and the search gave both local CRFs the weakest weight in their grids. The colour term can tell the two sides apart, because the colours of the classes differ and the noise is small. The example therefore shows the paper’s mechanism under conditions that suit it; it does not reproduce the size of the paper’s gains, which come from real images and a real classifier.

H3 held, by a rounding-level step. Under parallel updates the appearance CRF’s free energy rose in 0, 0, 0, 0 and 1 of its iterations on the five images; the single rise, on seed 4, is $1.137 \times 10^{-13}$ on $F = 901.79$ . The other CRFs’ printed parallel rises are at most $5.684 \times 10^{-14}$ . Steps of this size are at the level of floating-point rounding, so the output is no evidence that parallel updates failed to decrease the free energy here. In every row the parallel and sequential schedules end at the same free energy to the six printed decimals. In every row the appearance CRF’s free energy falls by more than 2,800 within its 10 iterations, and the local CRFs’ free energies by less than 2.

Process note. The plan for this example listed nine departures from the batch plan’s description, before the pilot: (1) the unaries were completed with a softmax at temperature 0.1; (2) message passing is exact $O(N^2)$ , without the permutohedral lattice and without Krähenbühl and Koltun’s pixelwise normalization; (3) the grid search was specified as above, with mean overall error as its criterion and validation images that share the test layout and differ only in noise; (4) the trimap band was defined by us; (5) the free-energy check and print were made for all three CRFs, not only the dense one; (6) the batch plan’s expectation that the grid CRF improves on the unaries less near boundaries was tested as a comparison of band-2 reductions (H2), and its expectation that parallel updates need not be monotone was made testable as H3; (7) the grid CRF is plain Potts; (8) checks C1–C7 were added, and colours are on a $[0, 1]$ scale; (9) the 2-pixel thin parts and the class-2 colour close to the sky’s were chosen from the construction. The bars of C1–C6 were written after a planning script had printed the values they test, and each of those values met its bar: C1’s counts (1811, 312 and 181 class pixels, 416 boundary pixels, bands of 416, 715 and 1313 pixels), which are exact properties of the construction; C2’s tolerance of 0.002; C3’s $10^{-12}$ ; C4’s two conditions; C5’s $10^{-12}$ and $10^{-10}$ ; and C6’s $10^{-9}$ bar, after the script ran sequential mean field on validation image 100 at one mid-grid setting per CRF ( $w_g = 1$ ; $w^{(2)} = 1$ , $\theta_\gamma = 2$ ; $w^{(1)} = 0.03$ , $\theta_\alpha = 6$ , $\theta_\beta = 0.1$ ). The word “strictly” in H1 was also added in the plan after that script ran. The script printed the unaries’ errors but no CRF’s labelling or trimap error, so H1–H3 are tests, not illustrations. The pilot printed the same output as the first run, and nothing was changed after it. NumPy warns of a logarithm of zero and an invalid product in the free-energy function; every printed free energy is finite, so the warnings come from calls whose values are not printed, and no label depends on them.

Common Misconceptions

“A CRF is an MRF with a different name.” Both are undirected models with Gibbs distributions. A CRF models only $p(\mathbf{y} \mid \mathbf{x})$ , its potentials may depend on the whole input, and its partition function is a function of the input; an MRF used in a generative model also accounts for the observations through a likelihood.
“Global normalization is only a technicality.” It is what removes the label bias of locally normalized next-state models (Lafferty et al., 2001), and it is also why CRF training must compute an expectation for every training input (Murphy, 2023, §4.4.3).
“The dense CRF is a different energy minimizer.” Krähenbühl and Koltun’s contribution is fast approximate inference, mean field with Gaussian filtering, for a model whose energy has the familiar unary-plus-Potts form; what is new is that every pair of pixels is connected.
“Mean field returns the MAP labelling.” It returns a factorized approximation $Q$ minimizing $\mathrm{KL}(Q \,\|\, P)$ ; the labels are each pixel’s most probable value under $Q$ , an approximation of the marginals’ maximizers, not the minimum-energy labelling. Evidence Lower Bound shows what such a factorized approximation misses on a model small enough to compare with the exact posterior.
“Every mean-field schedule decreases the free energy.” Coordinate ascent, one factor at a time, does (Murphy, 2023, §10.3.1); the all-at-once updates of Algorithm 1 have no such guarantee in that argument, although in the example their rises stayed at rounding level.
“Trimap” in this article is not the matting trimap. In Krähenbühl and Koltun’s evaluation it is a band around true object boundaries in which errors are counted; image matting uses the word for a user’s three-region map of foreground, background and unknown.
“CRF” does not always mean conditional random field. In HDR imaging’s code, crf is the camera response function.

Where It Is Used

Semantic segmentation. Grid CRFs over pixel classifiers in TextonBoost and other systems before deep learning, the fully connected CRF on boosted unaries, and then on network outputs in DeepLab v1 and v2 (semantic segmentation gives the history). CRF-RNN trained the CRF and the network together (Zheng et al., 2015).
Boundary refinement. Image segmentation describes DeepLab’s fully connected CRF as refining boundaries, and bilateral filtering supplies the appearance kernel and the fast filtering that make it practical.
Point clouds. Earlier point-cloud labelling combined point-wise features and a conventional classifier, with conditional random fields added in many methods to make the labels of neighbouring points consistent, as point cloud segmentation reports.
Sequences. Linear-chain CRFs label words and characters in text processing (Sutton and McCallum, 2006, §1.4.2); connectionist temporal classification uses the same forward–backward recursion for unsegmented sequences such as text lines.
Parts and structure. A tree-structured CRF over part locations is the pictorial structures model, and Murphy (2023, §4.4.2.2) describes deformable parts models in the same form.