  Edge-preserving smoothing (EPS) can be formulated as minimizing an objective
function that consists of data and prior terms. This global EPS approach shows
better smoothing performance than a local one that typically has a form of
weighted averaging, at the price of high computational cost. In this paper, we
introduce a highly efficient splitting-based method for global EPS that
minimizes the objective function of ${l_2}$ data and prior terms (possibly
non-smooth and non-convex) in linear time. Different from previous
splitting-based methods that require solving a large linear system, our
approach solves an equivalent constrained optimization problem, resulting in a
sequence of 1D sub-problems. This enables linear time solvers for
weighted-least squares and -total variation problems. Our solver converges
quickly, and its runtime is even comparable to state-of-the-art local EPS
approaches. We also propose a family of fast iteratively re-weighted algorithms
using a non-convex prior term. Experimental results demonstrate the
effectiveness and flexibility of our approach in a range of computer vision and
image processing tasks.
