Abstract
We propose a new, filtering approach for solving a large number of regularized inverse problems commonly found in computer vision. Traditionally, such problems are solved by finding the solution to the system of equations that expresses the first-order optimality conditions of the problem. This can be slow if the system of equations is dense due to the use of nonlocal regularization, necessitating iterative solvers such as successive over-relaxation or conjugate gradients. In this paper, we show that similar solutions can be obtained more easily via filtering, obviating the need to solve a potentially dense system of equations using slow iterative methods. Our filtered solutions are very similar to the true ones, but often up to 10 times faster to compute.
Introduction
In computer vision, fundamental tasks such as optical flow estimation, image denoising, and depth map super-resolution are mathematically framed as inverse problems. The goal is to recover a "true" latent signal from an observed, noisy, or incomplete input. Traditionally, these problems are solved by defining an energy function and employing iterative optimization algorithms like Conjugate Gradients.
In their ICCV 2019 paper, Young et al. challenge this paradigm by asking: What if we stopped optimizing and just started filtering? They demonstrate that many regularized inverse problems can be solved non-iteratively using a fast filtering approach, achieving significant speedups with negligible loss in quality.
Addressing the Computational Tax of Regularization
Inverse problems are inherently "ill-posed," requiring regularization—mathematical constraints that encourage solutions to be smooth or edge-aware. Modern "non-local" regularizers, such as bilateral or geodesic filters, produce high-quality results but turn the problem into a massive, dense system of linear equations. Solving these systems requires slow iterative methods that are sensitive to numerical stability. The authors bridge the gap between high-quality non-local regularization and the speed of simple filtering.
Methodology: Filtering as an Optimizer
The core contribution is a Filtering Method based on the observation that the solution to a standard regularized least-squares problem can be approximated by a specific filtering operation.
- The Approximation: Instead of iteratively solving $(H^*H + \lambda L)u = H^*z$, the authors propose a closed-form filtering expression, treating the "solve" step as a normalized convolution.
- Splat-Blur-Slice: To maintain efficiency, they leverage the "splat-blur-slice" pipeline, keeping computational complexity constant regardless of kernel size.
- Vectorial Extension: The method generalizes to vectorial problems like optical flow, where horizontal and vertical components are coupled.
- Robustification: By augmenting the feature space (e.g., adding previous solution values to filter coordinates), the method can mimic robust loss functions like the Welsch loss.
Experimental Validation
The approach was validated across several benchmarks:
- Depth Super-resolution: Tested on the Middlebury dataset.
- Optical Flow: Evaluated using the MPI-Sintel training set.
- Image Deblurring: Conducted on the Kodak dataset.
A key insight is that the inverse of the system matrix in these optimization problems behaves like a low-pass filter. Proper normalization (e.g., Sinkhorn or random-walk) is essential to ensure the filter preserves the signal's average level.
Key Results
The filtering approach demonstrates remarkable performance in both speed and accuracy. For 16x depth super-resolution, the geodesic filtering method took only 0.44s, compared to 1.61s for the Bilateral Solver and 140s for traditional iterative methods. In optical flow tasks, it achieved an Average End-Point Error (EPE) comparable to the variational optimizer of EpicFlow while running significantly faster.
Qualitative results show that filtered solutions are virtually indistinguishable from "true" iterative solutions, avoiding artifacts common in other fast solvers.
Conclusion and Future Work
While this filtering approach is an approximation, it serves as an exceptionally effective substitute for iterative solvers in many practical scenarios. Future work may explore applying this formalism to more complex tasks like semantic segmentation or 3D reconstruction, where real-time performance is critical.
Summary updated