Semi-Global Weighted Least Squares in Image Filtering

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 neigh-borhood 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 similar to 20 times faster than the WLS model. For an image of M x 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.