Fast Domain Decomposition for Global Image Smoothing

Youngjung Kim, Dongbo Min, Bumsub Ham, Kwanghoon Sohn

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


Edge-preserving smoothing (EPS) can be formulated as minimizing an objective function that consists of data and regularization terms. At the price of high-computational cost, this global EPS approach is more robust and versatile than a local one that typically has a form of weighted averaging. In this paper, we introduce an efficient decomposition-based method for global EPS that minimizes the objective function of L2 data and (possibly non-smooth and non-convex) regularization terms in linear time. Different from previous decomposition-based methods, which require solving a large linear system, our approach solves an equivalent constrained optimization problem, resulting in a sequence of 1-D sub-problems. This enables applying fast linear time solver for weighted-least squares and - L1 smoothing problems. An alternating direction method of multipliers algorithm is adopted to guarantee fast convergence. Our method is fully parallelizable, and its runtime is even comparable to the state-of-the-art local EPS approaches. We also propose a family of fast majorization-minimization algorithms that minimize an objective with non-convex regularization terms. Experimental results demonstrate the effectiveness and flexibility of our approach in a range of image processing and computational photography applications.

Original languageEnglish
Article number7937834
Pages (from-to)4079-4091
Number of pages13
JournalIEEE Transactions on Image Processing
Issue number8
StatePublished - Aug 2017

Bibliographical note

Publisher Copyright:
© 2017 IEEE.


  • Edge-preserving image smoothing
  • alternating minimization
  • joint image filtering
  • majorization-minimization algorithm
  • weighted-least squares


Dive into the research topics of 'Fast Domain Decomposition for Global Image Smoothing'. Together they form a unique fingerprint.

Cite this