The Fast Bilateral Solver

Introduction

• 50% error reduction is achieved by processing a state-of-the-art stereo depth map with the bilateral solver and a reference RGB image.The output is described as smooth with respect to the reference image.Source: §1 · p. 1
• The bilateral solver is 10–1000× faster than existing domain-specific approaches with comparable accuracy, and produces higher-quality output than lightweight filters at comparable runtimes.The introduction cites applications in global stereo, depth superresolution, colorization, and semantic segmentation.Source: §1 · p. 2
• The solver efficiently minimizes a regularized least-squares objective to produce an output that is bilateral-smooth and close to the input.Its bilateral-space formulation builds on Barron et al..Source: §1 · p. 2
• The solver is a single abstraction applicable to many problems, matching or beating specialized state-of-the-art algorithms and generalizing to different loss functions through M-estimation.Source: §1 · p. 2
• The backward pass is as simple and fast as the forward pass, enabling integration into deep learning architectures without expensive unrolling.The passage contrasts this with other edge-aware smoothing approaches that require complicated, expensive unrolling.Source: §1 · p. 2
• The bilateral solver is linear least-squares rather than the nonlinear optimization used in, enabling a hierarchical preconditioner, faster-converging initialization, and efficient joint solution of multiple problems.Source: §1 · p. 2

2 Problem Formulation

• The objective balances confidence-weighted squared error to the target against image-dependent smoothness, so the output follows reliable observations while smoothing along reference-image edges.The target and confidence are per-pixel quantities, and the reference is an RGB image.Source: §2 · pp. 2–3
• A bistochastized bilateral affinity matrix measures pixel similarity in reference-image YUV space, with parameters controlling spatial, luma, and chroma support.Source: §2 · p. 3
• Reformulating the objective in bilateral space yields a quadratic form whose minimization is equivalent to solving a sparse linear system.The paper characterizes the direct pixel-space optimization as intractably expensive, while the bilateral-space formulation can be optimized quickly.Source: §2 · p. 4
• The solver builds a simplified bilateral grid from the reference, constructs the system’s matrix and right-hand side, solves it, and slices the solution into an output image.For multiple targets sharing a reference and confidence image, it can solve their channels simultaneously using the same matrix; low-rank right-hand sides can accelerate optimization.Source: §2 · p. 4
• Unlike weighted least-squares filtering, bilateral-space optimization permits large spatial support efficiently, and its least-squares formulation enables standard optimization and backpropagation.The formulation also supports preconditioning and initialization techniques, correctness guarantees, and robust and multivariate generalizations.Source: §2 · p. 4

3 Backpropagation

• For symmetric positive-definite A, the implicit-function-theorem derivation requires only one least-squares solve to backpropagate a loss gradient onto A and b.The diagonal of A admits a more efficient gradient computation.Source: §3 · p. 5
• Given target t and confidence c, the solver builds a linear system, slices its bilateral-space solution into pixel-space output, and propagates the output-loss gradient through the system to t and c.Only A's diagonal gradient is needed because its off-diagonal elements do not depend on t or c.Source: §3 · pp. 5–6
• The backward pass costs no more than the forward pass because its dominant computation is the least-squares solve for the gradient with respect to b.Unlike unrolled optimization networks, it uses small, iteration-independent memory, storing only the bilateral-space output during training, and its backward pass can adapt to the output error gradient.Source: §3 · p. 6

4 Preconditioning & Initialization

• The prior hierarchical approach cannot transfer directly because linear solvers require same-dimensional preconditioners, while this solver’s linear structure enables more effective techniques.Image-pyramid methods also do not apply directly to optimization in sparse 5-dimensional bilateral space; the proposed bilateral pyramid adapts the hierarchy locally.Source: §4 · pp. 6–7
• The hierarchical preconditioner lifts bilateral-space vectors into pyramid space, scales pyramid coefficients, then projects them back.Its scaling combines vertex counts per coefficient, inverse diagonal values of A, and exponential level weights; experiments use α = 2 and β = 5, with stronger coarse-level downweighting tending toward Jacobi.Source: §4 · pp. 7–8
• Pyramid preconditioning and initialization significantly improve convergence over Jacobi preconditioning and flat initialization, with preconditioning critical.Figure 2 summarizes normalized loss across 20 4-megapixel images, plotting the 25th–75th percentiles.Source: §4 · p. 7, Figure 2 · p. 8
• Hierarchical initialization applies a confidence-guided push-pull filter to the input target, with α = 4 and β = 0 in all experiments.As α and β increase, it naturally degrades to the non-hierarchical initialization.Source: §4 · pp. 8–9
• The proposed solver has lower mean and variance runtime than, and the optimization and initialization improvements also apply to its backward pass.The runtime comparison averages results over the same 20 4-megapixel images on one workstation; the passage reports a substantial speedup but supplies no numerical values.Source: Table 1 · p. 9, §4 · p. 9

5.1 Stereo

• RBS halves test- and training-set absolute and RMS errors, has little negative effect on bad-1%, and achieved the lowest published Middlebury test MAE and RMSE at submission time.The improvement is smaller on non-occluded pixels, where state-of-the-art stereo algorithms already perform well.Source: §5.1 · p. 10

5.2 Depth Superresolution

• Third-lowest error, the solver is 600×, 1200×, and 3000× faster than the three most accurate methods; comparably fast methods have 25–40% greater error.The two methods with lower error use large amounts of external training data, while this experiment uses no learning.Source: §5.2 · p. 11, Table 3 · p. 11

5.3 Colorization

• 95× faster, the solver produces colorization nearly indistinguishable from Levin et al..Levin et al. take 80.99 seconds per megapixel, compared with 0.854 seconds per megapixel for the solver.Source: §5.3 · pp. 12–13

5.4 Semantic Segmentation

• The solver improves CNN segmentations but is slightly less accurate than CRF-based methods, while running 8–10× faster on the same inputs.It smooths per-class probability maps with uniform confidence; exploiting often-low-rank linear systems yields nearly identical output with a 5× average speedup.Source: §5.4 · pp. 13–14, Table 4 · p. 13

6 Conclusion

• The bilateral solver is a flexible and fast technique for inducing edge-aware smoothness.Source: §6 · p. 14
• The solver produces or improves state-of-the-art results across computer vision tasks while being faster or more accurate than other approaches.Its speed and generality make it useful for constructing computer vision algorithms and deep learning pipelines.Source: §6 · p. 14

Section 5

• Section 5 adds evaluation of the bilateral solver and comparisons with existing and novel baseline techniques.Source: arXiv:1511.03296v2 [cs.CV] 22 Jul 2016 · p. 17

Section 1

• Section 1 derives the bilateral-space quadratic objective at the solver’s core.Source: arXiv:1511.03296v2 [cs.CV] 22 Jul 2016 · p. 17

Section 2

• Section 2 details a bilateral-space pyramid representation for faster initialization and preconditioning.Source: arXiv:1511.03296v2 [cs.CV] 22 Jul 2016 · p. 17

Section 3

• Section 3 extends the solver with a robust error function to cope with outliers.Source: arXiv:1511.03296v2 [cs.CV] 22 Jul 2016 · p. 17

Section 4

• Section 4 improves solver performance when applied to multiple output channels.Source: arXiv:1511.03296v2 [cs.CV] 22 Jul 2016 · p. 17

1 Derivation

• The per-pixel objective balances a smoothness term with a data term that encourages agreement with observed targets according to per-pixel confidence.Source: §1 · p. 17
• Using the simplified bilateral grid and variable substitution from, the pixel-space smoothness and data terms are rewritten in terms of bilateral-space vertices.The derivation applies the substitution to both terms and combines them into a bilateral-space objective.Source: §1 · p. 18
• Because the resulting optimization is quadratic, its minimizer is equivalent to solving a sparse linear system, which the method solves with preconditioned conjugate gradients.The PCG implementation uses initialization and preconditioning tricks and is reproduced from.Source: §1 · p. 19

2 Bilateral-Space Pyramids

• Following, dividing the simplified grid’s XYLUV vertex coordinates by an arbitrary factor of 2 and rebuilding the grid at each scale forms a pyramid whose top level has one vertex.The number of levels K is set so the coarsest level contains a single vertex.Source: §2 · p. 20
• The pyramid operator P(y) applies the pyramid’s splat matrices to lift a bilateral-space vector y into representations at successive scales, and its transpose collapses pyramid-space back to bilateral-space.The lift is defined as P(y) = [S_{K−1}…S_0y, …, S_0y, y].Source: §2 · p. 20
• P(y) and P^T(z) are computed efficiently bottom-up and top-down, respectively, by reusing information from the previous scale.Source: §2 · p. 20

Robustness

• The RBS addresses the standard solver’s outlier sensitivity by minimizing a robust loss for applications with non-Gaussian target noise.The standard solver’s quadratic data term is sensitive to outliers unless they have low confidence.Source: §3 · p. 20
• IRLS repeatedly linearizes the robust loss and solves least-squares problems, replacing the input confidence with updated weights at each iteration.The linearized problem has the same form as the standard solver’s least-squares formulation.Source: §3 · pp. 20–21
• The RBS supports standard M-estimation losses; the implementation uses the Geman-McClure loss, a smooth approximation to the ℓ0-norm.Its non-convex loss makes the solver sensitive to initialization.Source: §3 · p. 21
• For Middlebury stereo, initial confidence reflects edge-aware depth variance, and the leftmost 80 columns are set to zero to ignore poorly estimated depths.The variance heuristic uses the domain transform and assigns higher confidence to contiguous, low-variance depth regions.Source: §3 · pp. 21–22

• For n-channel targets, the solver decomposes the problem into independent optimizations sharing the same A matrix but using different b vectors.Concatenating the y and b vectors rewrites these optimizations as one large linear system.Source: §4 · p. 23
• For wide, low-rank B, a rank-revealing QR reduction reduces right-hand sides before solving and expansion, often speeding convergence by an order of magnitude.The approach is similar to a simplified, approximate version of “block” conjugate gradient.Source: §4 · p. 23
• The approximation orders components by row mass and truncates them to a tolerated residual fraction before solving a smaller system and expanding its solution.Mass is the squared Euclidean norm of each row; the reduced system is solved with Q̃ and its solution is mapped back with R̃.Source: §4 · pp. 23–24
• At ϵ = 0.01, semantic-segmentation output is often indistinguishable from the exact solution despite being ≈5× faster on average.Source: §4 · p. 24

5.2 Stereo-based Defocus

• A simple reparameterization of interval depths as target and confidence lets the bilateral solver handle the stereo-based defocus task, running roughly 3.5× faster than.The target is the average of the interval endpoints, and confidence is the exponentiated negative interval length.Source: §5.2 · pp. 26–27

5.3 Depth Superresolution

• 600–3000× faster than the three most accurate methods, the solver achieves comparable depth-superresolution accuracy to all but; faster methods have 25–40% greater errors.Its performance is most competitive at 16× upsampling; runtime comparisons span different hardware platforms, so some runtimes should be interpreted accordingly.Source: §5.3 · pp. 27–28, Table 2 · p. 28

5.4 Colorization

• The colorization results compare the solver with Levin et al.’s exact least-square still-image method, but do not provide an exhaustive evaluation because the task traditionally lacks ground truth.Source: §5.4 · p. 32

5.5 Semantic Segmentation

• On well-isolated objects, the bilateral solver produces more edge-aware semantic-segmentation results than CRF-based techniques.Source: §5.5 · p. 32

5.1 Stereo

• About 50% lower MAE and RMSE, with bad-1% relatively unchanged, the solver improves stereo depth maps across input algorithms and outperforms the tested post-processing baselines on MAE and RMSE.The reported test-set metrics come from the Middlebury website; runtimes are omitted because MC-CNN dominates runtime for all compared methods.Source: §5.1 · p. 25, Table 1 · p. 26, Figure 2 · p. 33

5.5 Semantic Segmentation

• The robust bilateral solver produces much higher-quality Middlebury stereo depth maps than the input or baseline techniques, especially at discontinuities.Additional examples are shown in the same format.Source: Figure 9 · p. 40, Figure 10 · p. 41
• 3.5× faster, the solver produces depth maps and defocused renderings of comparable quality to [2] when given that method’s reparametrized input.Additional stereo defocus results are also shown.Source: Figure 11 · p. 42, Figure 12 · p. 43
• Depth superresolution results are presented with algorithms ordered by average benchmark error, and a dagger marks methods using external training data.Additional results are shown in Figures 14 and 15.Source: Figure 13 · p. 44, Figure 14 · p. 45, Figure 15 · p. 46
• 95× faster, the algorithm produces colorizations nearly indistinguishable from [17].Source: Figure 16 · p. 47
• On Pascal VOC12 validation images, the CRF-augmented DeepLab and CRF-RNN models perform best overall, while the bilateral solver improves results on isolated objects at a fraction of the cost.The examples are shown in additional semantic segmentation results.Source: Figure 17 · p. 48