Source-linked AI summary
Efficient Inference in Fully Connected CRFs with Gaussian Edge Potentials
Philipp Krähenbühl, Vladlen Koltun
TL;DR
Pixel-level CRFs have been limited by sparse connectivity and the impractical cost of inference in fully connected models. The paper introduces efficient approximate inference using Gaussian filtering, and shows that dense pixel-level connectivity improves segmentation and labeling accuracy while processing images in a fraction of a second.
Problem
Pixel-level CRFs lack long-range connectivity, while fully connected models offer refined labeling but make inference impractical because they contain billions of edges.
Method
The paper uses mean field approximate inference with Gaussian filtering to reduce message-passing complexity from quadratic to linear in the number of variables.
Results
Dense pixel-level connectivity significantly outperforms competing CRF models on benchmark segmentation and labeling evaluations.
Takeaways & Limitations
Fully connected pixel-level CRFs can deliver more accurate classification while processing benchmark images in a fraction of a second.
Abstract
from arXiv · showhide
Most state-of-the-art techniques for multi-class image segmentation and labeling use conditional random fields defined over pixels or image regions. While region-level models often feature dense pairwise connectivity, pixel-level models are considerably larger and have only permitted sparse graph structures. In this paper, we consider fully connected CRF models defined on the complete set of pixels in an image. The resulting graphs have billions of edges, making traditional inference algorithms impractical. Our main contribution is a highly efficient approximate inference algorithm for fully connected CRF models in which the pairwise edge potentials are defined by a linear combination of Gaussian kernels. Our experiments demonstrate that dense connectivity at the pixel level substantially improves segmentation and labeling accuracy.
1 Introduction
The paper motivates fully connected pixel-level CRFs as a way to improve semantic segmentation and labeling by modeling long-range interactions, while addressing their prohibitive inference cost. It introduces an efficient mean-field algorithm for Gaussian-kernel pairwise potentials in arbitrarily defined feature spaces.
- Motivation: Basic adjacency CRFs inadequately model long-range image connections and generally oversmooth object boundaries.
- Motivation: Fully connected CRFs place pairwise potentials on every pixel pair, enabling more refined segmentation but creating tens of thousands of nodes and billions of edges.
- Results: 0.2 seconds: the proposed algorithm produced fully connected pixel-level classifications, whereas MCMC ran for 36 hours and graph-cut inference failed to converge within 72 hours.
- Method: The proposed inference algorithm uses mean-field approximation and iterative message passing for pairwise potentials expressed as linear combinations of Gaussian kernels in arbitrary feature spaces.
2 The Fully Connected CRF Model
The model is a fully connected pairwise CRF over pixel labels, combining independently computed unary potentials with Gaussian-kernel pairwise potentials. For image segmentation, its contrast-sensitive kernels use pixel colors and positions, while label compatibility can follow the Potts model or be learned generally.
- Model definition: The CRF represents an image as N pixel variables, with each X_j assigned a label from a finite label set based on image I.I_j is the color vector of pixel j, while X_j is its assigned label.
- Model definition: The fully connected pairwise model uses the complete graph over pixels and includes all unary and pairwise cliques.Its labeling is evaluated through the corresponding Gibbs energy.
- Potential functions: Unary potentials are computed independently per pixel by a classifier using shape, texture, location, and color descriptors.The independent unary classifier outputs a label-assignment distribution for each pixel.
- Potential functions: Pairwise potentials are linear combinations of Gaussian kernels over pixel features, weighted by a label compatibility function.Each kernel has a symmetric positive-definite precision matrix that determines its shape.
- Potential functions: For segmentation, contrast-sensitive two-kernel potentials use colors and positions: the appearance kernel models nearby similarly colored pixels, while the smoothness kernel removes small isolated regions.Their nearness and color-similarity effects are controlled by θα and θβ, with parameters learned from data.
- Label compatibility: The Potts compatibility function penalizes differently labeled nearby similar pixels, whereas a general symmetric compatibility function can learn label-specific relationships.The Potts model treats “sky”–“bird” and “sky”–“cat” disagreements equally.
3 Efficient Inference in Fully Connected CRFs
The method uses mean field inference, reformulating message passing as Gaussian filtering in feature space. Efficient high-dimensional filtering reduces message-passing complexity from quadratic to linear in the number of variables.
- Efficient message passing: Gaussian filtering in feature space reduces message-passing complexity from quadratic to linear in the number of variables.The message-passing operation is expressed as a convolution with a Gaussian kernel in feature space.
- Mean field inference: Mean field approximates P(X) with independent marginals Q(X), minimizing D(Q∥P) over product distributions.Inference proceeds through iterative updates derived by minimizing the KL-divergence under valid-distribution constraints.
- Mean field inference: Each iteration performs message passing, a compatibility transform, and a local update, with message passing as the quadratic-complexity bottleneck.The other two operations run in linear time, whereas naive message passing sums over all other variables for each variable.
- Efficient message passing: Truncating the Gaussian beyond two standard deviations makes each sample aggregate only a constant number of neighboring samples.Sample spacing is proportional to the filter’s standard deviation, so the truncated kernel has constant support.
- Efficient message passing: The permutohedral lattice reduces high-dimensional convolution complexity to O(Nd) by exploiting separable whitened Gaussian kernels.A Cholesky-derived whitening transform enables one-dimensional convolutions along the lattice axes.
4 Learning
The model is learned piecewise, combining boosted unary training, kernel-parameter estimation, and compatibility optimization. High-dimensional filtering makes key computations efficient, yielding a final learning runtime linear in the number of variables.
- Piecewise training: Piecewise training first fits boosted unary classifiers with JointBoost, then learns appearance-kernel parameters for the Potts model.The appearance parameters are w(1), θα, and θβ; w(1) is obtained using expectation maximization and high-dimensional filtering.
- Smoothness parameters: The smoothness parameters w(2) and θγ have little effect on classification accuracy but provide a small visual improvement.The authors found w(2) = θγ = 1 to work well in practice.
- Compatibility parameters: Compatibility parameters µ(a, b) = µ(b, a) are optimized with L-BFGS by maximizing validation-set loglikelihood.Because the exact gradient requires the intractable partition-function gradient, mean field approximations estimate it instead.
- Computational efficiency: High-dimensional filtering computes the expensive sums in the learning algorithm efficiently, making its runtime linear in the number of variables N.The filtering approach is reused as in Section 3.2.
5 Implementation
The implementation uses extended TextonBoost unary potentials and efficient high-dimensional filtering via the permutohedral lattice. Pixelwise normalization was found to work better in practice despite violating CRF symmetry.
- Unary potentials: Unary potentials use TextonBoost features, including a 17-dimensional filter bank plus color, HOG, and pixel-location features.MSRC-21 uses this extended TextonBoost version; VOC 2010 additionally includes bounding-box detector responses for each object class.
- High-dimensional filtering: Efficient high-dimensional filtering uses a publicly available implementation of the permutohedral lattice with a downsampling rate of one standard deviation.This rate worked best across all experiments.
- Normalization: Pixelwise normalization handles regional sampling errors and worked better in practice, although it violates the CRF symmetry assumption ψp(xi, xj) = ψp(xj, xi).Global normalization corrects constant error, whereas pixelwise normalization handles regional errors as well.
6 Evaluation
Evaluation on MSRC-21 and PASCAL VOC 2010 shows that fully connected CRFs improve pixel-level segmentation accuracy, including around object boundaries, while remaining computationally efficient. Accuracy also increases with longer-range connections up to a reported kernel setting, although misleading propagation can produce failure cases.
- Evaluation datasets: The algorithm was evaluated on MSRC-21 and PASCAL VOC 2010, standard benchmarks for multi-class image segmentation and labeling.MSRC-21 contains 591 images and 21 object classes; PASCAL VOC 2010 contains 1928 images, 20 object classes, and one background class.
- MSRC-21: The algorithm outperforms previous work across all evaluated trimap widths for segmentation accuracy around object boundaries.The trimap measure counts relative misclassified pixels within a narrow band surrounding accurately annotated object boundaries.
- PASCAL VOC 2010: 30.2% average classification accuracy was achieved on PASCAL VOC 2010, compared with 29.1% for the fully connected Potts model and 28.3% for the grid CRF.The unary potentials alone yielded 27.6%; training took 2.5 hours and inference took 0.5 seconds.
- Long-range connections: Accuracy steadily increases as longer-range connections are added, peaking at θα = 61 pixels and θβ = 11.This experiment held w(1) constant and set w(2) to 0.
- Efficiency: The single-threaded implementation processes benchmark images in a fraction of a second, and the algorithm can be parallelized for further performance gains.The reported PASCAL VOC 2010 inference time was 0.5 seconds.
- Failure cases: Long-range connections can propagate misleading information, eroding a bird wing and corrupting a cat’s legs in reported failure cases.These failure cases were shown on PASCAL VOC 2010 and MSRC-21 images.