Title: Semi-Global Weighted Least Squares in Image Filtering,
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 $\sim20$ 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\{\frac{1}{M}, \frac{1}{N}\}$ of that of the
WLS model. We show the effectiveness and efficiency of our SG-WLS in a range of
applications.