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

Funding Information:
Manuscript received December 1, 2016; revised April 17, 2017; accepted May 23, 2017. Date of publication June 1, 2017; date of current version June 23, 2017. This work was supported in part by the Institute for Information and communications Technology Promotion Grant through the Korea Government (MSIP) under Grant 2016-0-00197 and in part by the National Research Foundation of Korea through the MSIP under Grant 2017R1C1B2005584. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Xudong Jiang. (Corresponding author: Kwanghoon Sohn.) Y. Kim, B. Ham, and K. Sohn are with the School of Electrical and Electronic Engineering, Yonsei University, Seoul 120–749, South Korea (e-mail:;;

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