Abstract
Solving the global method of Weighted Least Squares (WLS) model in image filtering is both time- and memory-consuming. In this paper, we present an alternative approximation in a time- and memory- efficient manner which is denoted as Semi-Global Weighed Least Squares (SG-WLS). Instead of solving a large linear system, we propose to iteratively solve a sequence of subsystems which are one-dimensional WLS models. Although each subsystem is one-dimensional, it can take two-dimensional neighborhood information into account due to the proposed special neighborhood construction. We show such a desirable property makes our SG-WLS achieve close performance to the original two-dimensional WLS model but with much less time and memory cost. While previous related methods mainly focus on the 4-connected/8-connected neighborhood system, our SG-WLS can handle a more general and larger neighborhood system thanks to the proposed fast solution. We show such a generalization can achieve better performance than the 4-connected/8-connected neighborhood system in some applications. Our SG-WLS is ~20 times faster than the WLS model. For an image of $M \times N$, the memory cost of SG-WLS is at most at the magnitude of $max\{1/M, 1/N\}$ of that of the WLS model. We show the effectiveness and efficiency of our SG-WLS in a range of applications.
Introduction
Edge-preserving smoothing is a fundamental operation in computer graphics and image processing, essential for tasks like HDR tone mapping, detail enhancement, and image colorization. Historically, researchers have relied on two main approaches: local filters and global filters. Local filters, such as the bilateral filter, are computationally efficient but often suffer from visual artifacts like halos and gradient reversals. Conversely, global filters like the Weighted Least Squares (WLS) model optimize a global objective function to avoid these artifacts. However, WLS requires solving massive linear systems, making it both time-consuming and memory-intensive, especially for high-resolution images.
To address these efficiency issues, fast approximations like the Fast Global Smoother (FGS) have been proposed. FGS decomposes the 2D WLS problem into independent 1D row and column passes. While fast, this separation discards critical 2D neighborhood context, leading to noticeable "blocky" artifacts in the final output. This paper introduces Semi-Global Weighted Least Squares (SG-WLS), a method that maintains the speed of 1D approximations while preserving the high-quality, artifact-free results of global 2D models.
Methods
The core innovation of SG-WLS lies in its ability to embed 2D context into a 1D solver. This is achieved through two primary technical contributions:
2D-Aware 1D Neighborhood Construction
Unlike traditional separable filters that process isolated rows or columns, SG-WLS extracts a band of $2r+1$ columns (or rows) and reshapes them into a single 1D vector. By connecting these elements head-to-tail, pixels that are neighbors in the 2D image remain neighbors in the 1D representation. This construction allows the 1D solver to account for 2D spatial relationships, effectively eliminating the blocky artifacts associated with simpler 1D methods.
Fast r-band LU Decomposition
To solve the WLS objective on the reshaped 1D vector, the authors developed a custom, exact $r$-band LU decomposition. This solver is highly efficient and allows for larger neighborhood radii ($r \ge 1$). This is a significant advancement over previous semi-global methods, which were typically restricted to immediate 4- or 8-connected neighbors. By increasing the radius, the filter can preserve sharp edges more effectively during tasks like depth upsampling.
Results and Discussion
The SG-WLS method was evaluated across various image processing tasks, including HDR tone mapping, detail enhancement, and guided depth upsampling.
Performance and Efficiency
SG-WLS demonstrates a significant performance boost, operating approximately 20 times faster than the original WLS model. For a 1-megapixel RGB image, SG-WLS takes roughly 0.35 seconds, whereas the standard WLS model requires over 8 seconds. Furthermore, the memory footprint is drastically reduced. By avoiding the storage of the massive $MN \times MN$ matrix required for global optimization, the memory cost is reduced to a fraction of the original model's requirements.
Visual Quality
Qualitative results show that SG-WLS produces images that are visually indistinguishable from the exact WLS model. Crucially, it avoids the pale colors and blocky artifacts seen in FGS results.
Quantitative Accuracy
In benchmarks for guided depth upsampling, SG-WLS with a larger radius ($r=4$) consistently outperformed Joint Bilateral Upsampling (JBU), Guided Filter (GF), and FGS, achieving the lowest Mean Absolute Difference (MAD). This highlights the importance of neighborhood radius over simple regularization for edge preservation.
Conclusion
Semi-Global Weighted Least Squares (SG-WLS) provides a powerful and efficient alternative to global WLS filtering. By cleverly reshaping 2D neighborhoods into 1D vectors and utilizing a fast $r$-band solver, it achieves high-quality results without the computational burden of global optimization. While slightly slower than purely 1D filters like FGS, the gain in visual quality and artifact suppression makes it a superior choice for high-fidelity image processing.
Summary updated