Fast, Exact and Multi-Scale Inference for Semantic Image Segmentation with Deep Gaussian CRFs

Siddhartha Chandra; Iasonas Kokkinos

Source-linked AI summary

Fast, Exact and Multi-Scale Inference for Semantic Image Segmentation with Deep Gaussian CRFs

Siddhartha Chandra, Iasonas Kokkinos

arXiv:1603.08358v4Mar 28, 2016cs.CVcs.LG

TL;DR

Semantic segmentation needs structured prediction that captures label interactions without the approximation and memory costs of recurrent inference. The paper combines deep networks with G-CRFs and quadratic optimization to obtain exact inference, analytic gradients, learned pairwise terms, and end-to-end training. Multi-resolution inference improves results over single-scale baselines, while the method is competitive on VOC PASCAL 2012 with substantially simpler inference.

Problem
Existing deep structured-prediction methods commonly rely on approximate inference and back-propagation-through-time, creating computation and memory demands and offering only local-optimum guarantees.
Method
The paper uses a quadratic G-CRF-based module whose positive-definite energy is solved exactly through linear systems, with learned unary and pairwise terms and analytic gradients for end-to-end training.
Results
0.02 seconds per image in the general setting and 0.003 seconds for Potts-type pairwise terms; the method is competitive on VOC 2012 and outperforms CRF-RNN by 0.8%.
Takeaways & Limitations
Multi-resolution structured prediction couples information across scales and yields substantially improved results over single-scale baselines while preserving exact, efficient inference.

Abstract

from arXiv · show

In this work we propose a structured prediction technique that combines the virtues of Gaussian Conditional Random Fields (G-CRF) with Deep Learning: (a) our structured prediction task has a unique global optimum that is obtained exactly from the solution of a linear system (b) the gradients of our model parameters are analytically computed using closed form expressions, in contrast to the memory-demanding contemporary deep structured prediction approaches that rely on back-propagation-through-time, (c) our pairwise terms do not have to be simple hand-crafted expressions, as in the line of works building on the DenseCRF, but can rather be `discovered' from data through deep architectures, and (d) out system can trained in an end-to-end manner. Building on standard tools from numerical analysis we develop very efficient algorithms for inference and learning, as well as a customized technique adapted to the semantic segmentation task. This efficiency allows us to explore more sophisticated architectures for structured prediction in deep learning: we introduce multi-resolution architectures to couple information across scales in a joint optimization framework, yielding systematic improvements. We demonstrate the utility of our approach on the challenging VOC PASCAL 2012 image segmentation benchmark, showing substantial improvements over strong baselines. We make all of our code and experiments available at {https://github.com/siddharthachandra/gcrf}

1 Introduction

The paper addresses limitations of approximate structured prediction for semantic segmentation by combining fully convolutional networks with G-CRFs, enabling exact inference and learning through linear systems. It further develops efficient and multi-scale variants that improve segmentation over single-scale baselines and competitive benchmarks.

Motivation: FCNs provide strong pixelwise predictions, but structured prediction is used to capture interactions between neighboring labels and sharpen segmentation boundaries.Prior work combines FCNs with DenseCRFs, including recurrent end-to-end approximations.
Motivation: Approximate mean-field methods typically use fixed iteration counts, while more iterations increase computation and memory demands and still guarantee only local optima.Back-propagation-through-time must store intermediate unrolled-inference results.
Approach: G-CRFs provide exact MAP inference because their quadratic energy has a unique global minimum when the system matrix is positive definite.The minimum is obtained by solving a system of linear equations.
Approach: The proposed method obtains both MAP solutions and gradients through linear systems, avoiding back-propagation-through-time while retaining expressive learned pairwise terms.Unary and pairwise terms are produced by deep network streams and trained end-to-end.
Extensions: Potts-type pairwise structure reduces memory and computation with competitive results, while multi-scale neighborhoods substantially improve performance over single-scale baselines.The framework supports arbitrary neighborhoods beyond common 4-connected graphs.
Experiments: Experiments report consistent improvements over well-known baselines and state-of-the-art results on the VOC PASCAL test set.The paper also presents efficient linear-system solvers and a multi-resolution structured prediction algorithm.

2 Quadratic Optimization Formulation

The formulation represents pixel-label scores with a continuous quadratic energy whose learned unary and pairwise terms admit exact inference and end-to-end training. A shared Potts-style simplification reduces computation while retaining competitive results.

2 Quadratic Optimization Formulation: Each pixel-label pairing receives a continuous score x(p, l), rather than a directly inferred discrete label.The score is proportional to log-odds when followed by a softmax unit.
2 Quadratic Optimization Formulation: The inferred hypothesis is a real-valued vector x ∈ R^N with N = P × L, and inference is posed as energy minimization.The ground-truth labeling is represented separately as a discrete-valued vector y.
2.1 Energy of a hypothesis: The energy uses a symmetric pairwise matrix A and unary vector B, both learned from data by fully convolutional network streams.A and B are combined by the quadratic-optimization module to produce final per-class pixel scores.
2.1 Energy of a hypothesis: Adding λI makes A strictly positive definite, giving the energy a unique global minimum and enabling exact inference.The parameter λ is set empirically in the experiments.
2.3 Learning A and B: Training uses backpropagation with closed-form gradient expressions for the unary and pairwise terms, obtained through linear-system calculations.The derivative with respect to B is expressed as a linear system, while the gradient with respect to A uses a Kronecker-product expression.
2.4 Softmax Cross-Entropy Loss: Softmax cross-entropy converts per-pixel scores into label probabilities and supplies the loss derivatives used during training.For each label, the derivative with respect to the input score is p_l − y_l.
2.5 Quadratic Optimization with Shared Pairwise Terms: The shared Potts formulation makes pairwise terms depend on whether labels match, reducing learned pairwise parameters from P L × P L to P × P.It shares pairwise terms across different class pairs rather than conditioning them on particular labels.
2.5 Quadratic Optimization with Shared Pairwise Terms: The shared formulation solves L + 1 systems with a P × P matrix and reduces inference time 6× and overall training time 3× when L = 21.The authors report competitive results relative to the general formulation.

3 Linear Systems for Efficient and Effective Structured Prediction

The paper recasts Gaussian CRF inference and gradient computation as linear-system problems, enabling exact inference with efficient numerical solvers. It further couples multiple image resolutions in a block-structured system so within-scale and cross-scale consistency are optimized jointly.

Fast Linear System Solvers: Inference and pairwise-gradient computation both reduce to solving linear systems, enabling numerical-analysis techniques for structured prediction.The computational cost depends on the matrix A's size and sparsity pattern.
Fast Linear System Solvers: Conjugate-gradient-based solvers can be up to 2.5 faster than naive GPU implementations of parallel mean-field inference.Figure 2 compares Jacobi, Gauss-Seidel, conjugate-gradient, and GMRES convergence to residual tolerance 10^-6.
Fast Linear System Solvers: Parallel and sequential mean-field inference correspond to Jacobi and Gauss-Seidel linear-system solvers, respectively.For Gaussian CRFs, these methods provide weaker solver baselines than the proposed conjugate-gradient alternatives.
Multiresolution graph architecture: The multi-resolution formulation uses block-structured linear systems to jointly model within-resolution neighborhoods and corresponding regions across resolutions.Within-resolution interactions can encourage same or different labels, while cross-resolution interactions encourage corresponding regions to share labels.
Multiresolution graph architecture: Coupling scale-specific systems allows information to flow across resolutions and experimentally outperforms a simpler multi-resolution architecture.The inter-resolution terms connect spatially corresponding pixels or image regions at different resolutions.
Implementation: The GPU implementation reports inference times of approximately 0.02 seconds in the general setting and 0.003 seconds in the simplified formulation.Testing time per image for the methods is reported as 0.4–0.7 seconds per image.

4 Experiments

Experiments on VOC PASCAL 2012 evaluate the G-CRF networks across connectivity, weight-sharing, multi-resolution, DenseCRF post-processing, and a ResNet-101 setting. The multi-resolution and Potts-pairwise variants improve segmentation performance while enabling efficient structured prediction.

The VOC PASCAL 2012 benchmark contains 1464 training, 1449 validation, and 1456 test images across 20 foreground classes plus background, evaluated using mean pixel IOU.
The baseline is a three-resolution Deeplab-LargeFOV network with tied weights, whose fused activations provide a strong feedforward comparison.
Weight sharing is significantly faster than the unconstrained QO network and performs better, while multi-resolution QO outperforms the other tested variants.The comparison includes QO, shared-weight QO, separate per-resolution QO units, and unified multi-resolution QO.
DenseCRF post-processing consistently boosts all methods, and its improvement is complementary to the improvement from the proposed method.
The proposed method outperforms the previous state-of-the-art CRF-RNN system by 0.8% on directly comparable VOC PASCAL 2012 benchmarks.The authors note that the CRF module stacked on their QO network was not trained end-to-end and anticipate further gains from integrating that training.
With a Deeplab-V2 ResNet-101 backbone, learned Potts-type pairwise terms refine object boundaries and improve segmentation performance.The pairwise terms are learned from a parallel ResNet-101 network operating at the original image scale.

5 Conclusions and Future Work

The paper concludes that quadratic optimization enables exact, efficient structured prediction and end-to-end learning for deep networks. It reports GPU inference times of 0.02 seconds generally and 0.003 seconds for the Potts-type case, while identifying broader connectivity and positive-definiteness guarantees as future directions.

The proposed quadratic optimization method predicts continuous vector-valued variables in deep networks with exact inference.
Inference takes 0.02 seconds per image on the GPU generally and 0.003 seconds for Potts-type pairwise terms using conjugate gradients.
The framework learns features and model parameters simultaneously through an end-to-end fully convolutional training algorithm.
Experiments indicate that pairwise terms boost image-segmentation performance while remaining competitive with state-of-the-art methods and substantially simpler.
Future work includes fully connected graphical models, general methods guaranteeing positive definiteness, and applications to other regression and classification tasks.The current work focused on simple 4−12-connected neighbourhoods and empirically used a constant λ to obtain positive definiteness.