The Fast Bilateral Solver

Jonathan T. Barron; Ben Poole

Source-linked AI summary

The Fast Bilateral Solver

Jonathan T. Barron, Ben Poole

arXiv:1511.03296v2Nov 10, 2015cs.CV

TL;DR

Challenging vision tasks need edge-aware smoothing that preserves image boundaries while supporting accurate optimization, but traditional filters and specialized methods face limitations in flexibility, speed, or integration. The paper introduces a bilateral solver based on bilateral-space linear least-squares optimization. Across stereo, depth superresolution, colorization, and semantic segmentation, it produces or improves state-of-the-art results while being faster or more accurate, and its speed and generality support computer-vision and deep-learning pipelines.

Problem
Traditional edge-aware filters are efficient and flexible but often insufficient for challenging tasks requiring optimization, while global smoothing operators are difficult to integrate into deep-learning frameworks.
Method
The bilateral solver reformulates edge-aware smoothing as a bilateral-space regularized least-squares problem solved through a sparse linear system.
Results
The solver produces or improves state-of-the-art results across several computer-vision tasks while being faster or more accurate than other approaches.
Takeaways & Limitations
Its speed and generality make the bilateral solver useful for constructing computer-vision algorithms and deep-learning pipelines.
Takeaways & Limitations
The quadratic data term makes the solver sensitive to outliers in input targets unless those outliers receive low confidence.

Abstract

from arXiv · show

We present the bilateral solver, a novel algorithm for edge-aware smoothing that combines the flexibility and speed of simple filtering approaches with the accuracy of domain-specific optimization algorithms. Our technique is capable of matching or improving upon state-of-the-art results on several different computer vision tasks (stereo, depth superresolution, colorization, and semantic segmentation) while being 10-1000 times faster than competing approaches. The bilateral solver is fast, robust, straightforward to generalize to new domains, and simple to integrate into deep learning pipelines.

1 Introduction

The paper targets edge-aware smoothing methods that are flexible and fast but insufficient for challenging vision tasks. It introduces a bilateral solver that combines bilateral-space optimization with linear least squares, generality, differentiability, and faster convergence.

Natural-image properties are correlated within smooth regions but differ across image discontinuities, motivating edge-aware signal propagation.
Traditional edge-aware filters are flexible and computationally efficient, but often insufficient for challenging computer vision tasks requiring iterative inference or optimization.
The bilateral solver uses bilateral-space optimization to produce outputs that are smooth within objects, not across edges, and close to the input.
A single bilateral-solver abstraction can apply across different problems while matching or beating specialized state-of-the-art algorithms.
The solver's backward pass is as simple and fast as its forward pass, enabling integration into deep learning architectures.
The linear least-squares formulation enables hierarchical preconditioning, improved initialization, faster convergence, and efficient simultaneous solution of multiple problems.

2 Problem Formulation

The solver recovers an output that stays close to confident target values while remaining smooth and aligned with reference-image edges. Bilateral-space reformulation converts the objective into a rapidly solvable sparse linear system.

The solver takes per-pixel target quantities, their confidences, and a reference RGB image, then seeks an improved output vector.
The objective combines a reference-dependent smoothness term with a confidence-weighted squared data-fidelity term.
The bilateral affinity matrix measures pixel similarity in reference-image YUV space, with parameters controlling spatial, luma, and chroma support.
Bilateral filtering blurs within regions but not across edges by adapting its filter to image content, and bilateral-space methods accelerate this operation through splat, blur, and slice steps.
Bistochastization and variable substitution reformulate the high-dimensional pixel-space problem using lower-dimensional bilateral-space vertices.
The bilateral-space loss becomes a quadratic form whose minimization is equivalent to solving a sparse linear system, producing a pixel-space solution by slicing.
The formulation supports standard preconditioned conjugate-gradient optimization, efficient backpropagation, faster convergence, correctness guarantees, and robust or multivariate generalizations.

3 Backpropagation

The paper makes the bilateral solver differentiable by backpropagating through the linear system that underlies its bilateral-space solution. The backward pass requires a least-squares solve and is no more costly than the forward pass.

Backpropagation is performed through the solver's least-squares system rather than by treating matrix inversion as a separate differentiable operation.
For a general linear system, differentiating the estimated vector with respect to the system requires gradients onto both the matrix and right-hand-side vector.
The implicit-function derivation requires a single least-squares solve for backpropagation, with a more efficient computation for the diagonal of A.
The solver maps an input target and confidence to a bilateral-space solution, then slices that solution into a pixel-space output.
Only the diagonal of A requires the relevant gradient because its off-diagonal elements do not depend on the input signal or confidence.
The paper shows how to backpropagate through the bilateral solver itself.
Because the backward pass is dominated by the solve for ∂f/∂b, its computational cost is no greater than the forward pass.

4 Preconditioning & Initialization

The solver begins with baseline Jacobi preconditioning and data-term initialization, then improves both through hierarchical bilateral-pyramid techniques designed for its linear system. These choices improve convergence over flat baselines while supporting efficient forward and backward optimization.

Baseline methods: The baseline Jacobi preconditioner is the inverse of the diagonal of the A matrix.Because the relevant matrices are diagonal, this baseline is straightforward to compute.
Baseline methods: The baseline initialization sets the optimization state to the value that minimizes the data term in closed form.This provides a simple non-hierarchical starting point before applying the pyramid-based initialization.
Hierarchical techniques: Pyramid-based hierarchical preconditioning is introduced because prior image-pyramid methods do not apply directly to sparse 5-dimensional bilateral-space optimization.The solver instead uses a bilateral-space multiscale representation to construct its preconditioner.
Hierarchical techniques: Hierarchical preconditioning lifts a bilateral-space vector into pyramid-space, applies element-wise coefficient scaling, and projects it back.The scaling incorporates coefficient support, the inverse diagonal of A, and exponential level weighting; coarser levels can be downweighted as α or β increases.
Empirical behavior: Figure 2 shows that hierarchical “Pyr” preconditioning and initialization improve convergence over naive Jacobi preconditioning and flat initialization.The loss is plotted for 20 normalized 4-megapixel images using percentile bands, with nonlinear y-axis and logarithmic x-axis scaling.
Hierarchical techniques: The same bilateral-pyramid approach initializes the state through a confidence-weighted push-pull filter, degrading to the non-hierarchical initialization as α and β increase.All experiments use α = 4 and β = 0 for initialization.

5 Applications

The bilateral solver is evaluated across stereo, depth superresolution, colorization, and semantic segmentation, delivering competitive quality with substantial speed advantages.

The solver is evaluated on stereo, depth superresolution, image colorization, and semantic segmentation.It serves as a complete algorithm for some tasks and as a building block in larger algorithms for others.
5.1 Stereo: The robust bilateral solver halves test- and training-set absolute and RMS stereo errors with little effect on bad 1% error.At submission time, it achieved lower test-set MAE and RMSE on Middlebury than any published technique.
5.2 Depth Superresolution: 600×, 1200×, and 3000× faster than the three most accurate depth-superresolution techniques, the solver produces the third-lowest error rate.Comparable-speed techniques produce error rates 25–40% greater, while the solver requires no training or learning.
5.3 Colorization: 95× faster while producing nearly indistinguishable output, the solver matches the colorization technique of Levin et al.The reported runtimes are 0.854 seconds per megapixel versus 80.99 seconds per megapixel.
5.4 Semantic Segmentation: 8–10× faster than CRF and CRF-RNN approaches, the solver improves CNN outputs but performs slightly worse than CRF-based methods.The resulting segmentations are more accurate and qualitatively smoother than the CNN outputs.

6 Conclusion

The paper concludes that the bilateral solver provides flexible, fast edge-aware smoothing across computer vision tasks. Its speed and generality support using it in computer vision algorithms and deep learning pipelines.

The bilateral solver is a flexible and fast technique for inducing edge-aware smoothness.
Across varied computer vision tasks, it produces or improves state-of-the-art results while being faster or more accurate than other approaches.
Its speed and generality suggest that the solver is useful for constructing computer vision algorithms and deep learning pipelines.

arXiv:1511.03296v2 [cs.CV] 22 Jul 2016

The supplement adds technical derivations, solver extensions, and extensive experiments and comparisons to prior work.

The supplement details the bilateral-space quadratic objective, pyramid representation, robust error extension, and experimental comparisons.

1 Derivation

The derivation reformulates the pixel-level objective in bilateral space, yielding a quadratic least-squares problem and a sparse linear system solved with PCG.

The objective uses smoothness and confidence-weighted data fidelity to recover an output resembling trusted target values.
The pixel optimization is rewritten using bilateral-space vertices through a variable substitution and equivalent smoothness and data terms.
Unlike the nonlinear formulation in, the resulting quadratic optimization can be written in standard matrix/vector form.
Setting the derivative to zero converts minimization into solving a sparse linear system.
Preconditioned conjugate gradients solves the system using initialization and preconditioning techniques described in prior work.

2 Bilateral-Space Pyramids

The bilateral-space pyramid builds a multiscale representation from simplified bilateral-grid vertices, then supports lifting vectors upward and transposing them back down. Both operations reuse information across scales for efficiency.

2 Bilateral-Space Pyramids: The pyramid is constructed on bilateral-grid vertices, using a multiscale representation required by hierarchical initialization and preconditioning.The vertex matrix V has m rows for simplified-grid vertices and five columns from the input-image bilateral grid.
2 Bilateral-Space Pyramids: The number of pyramid levels K is chosen so the top level contains a single vertex.Each level halves V before constructing the next simplified bilateral grid.
2 Bilateral-Space Pyramids: P(y) lifts a bilateral-space vector into pyramid-space by concatenating its representations across all pyramid levels.The operation includes progressively coarser products such as S1S0y and SK−1...S1S0y.
2 Bilateral-Space Pyramids: The transpose operation collapses pyramid-space vectors back into bilateral-space.It applies the transposed splat matrices in the reverse direction.
2 Bilateral-Space Pyramids: P(y) and P^T(z) are computed efficiently by reusing information from the previous scale during bottom-up and top-down passes.The two directions correspond respectively to constructing the pyramid representation and collapsing it.

3 Robustness

The robust bilateral solver extends the fast least-squares solver to non-Gaussian noise by replacing the quadratic treatment with robust loss optimization solved through IRLS. Its stereo initialization uses edge-aware depth variance to assign confidence.

3 Robustness: The quadratic data term makes the standard bilateral solver sensitive to input-target outliers unless those outliers receive low confidence.This motivates the robust bilateral solver for applications with non-Gaussian noise.
3 Robustness: The robust bilateral solver minimizes a robust error function ρ(·), which generally lacks a closed-form solution.The quadratic case is the exception because it preserves the fast least-squares formulation.
3 Robustness: IRLS repeatedly linearizes the robust loss around the current estimate and solves a least-squares problem using the resulting weights.Wrapping the standard bilateral solver in this loop produces the robust bilateral solver.
3 Robustness: The RBS uses the Geman-McClure loss, a smooth approximation to the ℓ0-norm, with σgm controlling its scale.Algorithm 3 initializes confidence, repeatedly solves for x, and updates weights from the residual.
3 Robustness: Because the robust loss is non-convex, RBS performance depends on initialization, so cinit is used for the first solve before IRLS weights replace it.For Middlebury stereo, cinit is derived from fast edge-aware depth variance, with low-variance contiguous regions receiving higher confidence.
3 Robustness: The Middlebury stereo initialization sets the leftmost 80 columns of cinit to 0 because those pixels generally have poorly estimated depths.Figure 1 pairs the input depth map with its estimated input confidence; the same procedure downweights inconsistent contiguous-depth regions.

4 Multiple Output Channels

For multiple output channels, the solver reuses one system matrix across independent right-hand sides and accelerates wide, low-rank systems through rank-revealing reduction. In semantic segmentation, the approximation is often nearly exact while being about 5× faster.

4 Multiple Output Channels: Multiple target channels are handled as independent optimization problems sharing the same A matrix but using different b vectors.Concatenating the channel-specific vectors produces one large linear system.
4 Multiple Output Channels: Semantic-segmentation probability matrices are often wide and low-rank because many categories have near-zero probabilities or strong correlations.This structure permits reducing the number of right-hand sides before solving.
4 Multiple Output Channels: Rank-revealing QR factorization reduces B while providing a stable and fast basis for the reduced system.The factorization uses a permutation matrix, an orthonormal basis Q, and an upper-triangular matrix R.
4 Multiple Output Channels: Rows of R′ are ordered by non-increasing Euclidean norm, and their squared norms define row masses used to retain important components.A tolerance ϵ determines how much residual energy may be discarded when dropping rows of R′ and columns of Q′.
4 Multiple Output Channels: ≈5× faster: with ϵ = 0.01, semantic-segmentation outputs are often indistinguishable from the exact solution.The reduced system is solved and then expanded back to approximate the original solution.

5 Results

Across stereo, depth superresolution, stereo-based defocus, and semantic segmentation, the bilateral solver delivers competitive or improved quality while emphasizing speed and broad applicability. Results also expose evaluation boundaries, including hardware differences and incomplete baseline reproducibility.

5.1 Stereo: The robust bilateral solver reduces stereo MAE and RMSE errors, usually by around 50%, while bad-1% remains relatively unchanged.The improvement is consistent across stereo techniques and exceeds the reductions achieved by evaluated baseline post-processing methods.
5.2 Stereo-based Defocus: The bilateral solver is roughly 3.5× faster than the specialized solver of on stereo-based defocus.The comparison supports applying the general-purpose solver to a task addressed by a much more specialized precursor.
5.3 Depth Superresolution: The solver produces competitive depth-superresolution accuracy despite using a simple, untrained model.It is roughly the second or third most accurate technique, behind dictionary-based methods trained on substantial data.
5.3 Depth Superresolution: 600-3000× faster than the three most accurate depth-superresolution techniques, the bilateral solver maintains comparable accuracy to all but.Methods with comparable or better runtimes produce error rates 25-40% greater than the bilateral solver.
Evaluation conditions: Runtime comparisons require caution because some baselines were measured on other hardware platforms, while the solver used a 2012 HP Z420 workstation.The benchmark also inherits or augments prior results because many techniques lack publicly available source code.
5.5 Semantic Segmentation: For semantic segmentation, the bilateral solver produces more edge-aware results than CRF-based techniques on well-isolated objects.This result concerns the visual quality of the segmentation outputs.