Image Restoration

Multi-Agent Consensus Equilibrium

alpha 

While foreground extraction is fundamental to virtual reality systems and has been studied for decades, majority of the professional softwares today still rely substantially on human interventions, e.g., providing trimaps or labeling key frames. This is not only time consuming, but is also sensitive to human error. In this paper, we present a fully automatic foreground extraction algorithm which does not require any trimap or scribble. Our solution is based on a newly developed concept called the Multi-Agent Consensus Equilibrium (MACE), a framework which allows us to integrate multiple sources of expertise to produce an overall superior result. The MACE framework consists of three agents: (1) A new dual layer closed-form matting agent to estimate the foreground mask using the color image and a background image; (2) A background probability estimator using color difference and object segmentation; (3) A total variation minimization agent to control the smoothness of the foreground masks. We show how these agents are constructed, and how their interactions lead to better performance. We evaluate the performance of the proposed algorithm by comparing to several state-of-the-art methods. On the real datasets we tested, our results show less error compared to the other methods.

Publication:

  1. Xiran Wang, Jason Juang, Stanley H. Chan, ‘‘Automatic Foreground Extraction using Multi-Agent Consensus Equilibrium’’, submitted.

Theory of Plug-and-Play ADMM

plugplaytheory 

The Plug-and-Play (PnP) ADMM algorithm is a powerful image restoration framework that allows advanced image denoising priors to be integrated into physical forward models to yield a provably convergent algorithm. However, despite the enormous applications and promising results, very little is known about why the PnP ADMM performs so well. This paper presents a formal analysis of the performance of PnP ADMM. By restricting the denoisers to the class of graph filters, or more specifically the symmetric smoothing filters, we offer three contributions: (1) We rigorously show conditions under which an equivalent maximum-a-posteriori (MAP) optimization exists, (2) we derive the mean squared error of the PnP solution, and provide a simple geometric interpretation which can explain the performance, (3) we introduce a new analysis technique via the concept of consensus equilibrium, and provide interpretations to general linear inverse problems and problems with multiple priors.

Publication:

  1. Stanley H. Chan, ‘‘Performance Analysis of Plug-and-Play ADMM: A Graph Signal Processing Perspective’’, submitted.

  2. Gregery T. Buzzard, Stanley H. Chan and Charles A. Bouman ‘‘Plug-and-Play Unplugged: Optimization Free Reconstruction using Consensus Equilibrium’’, submitted. [CODE]

Plug-and-Play ADMM

plugplay 

Alternating direction method of multiplier (ADMM) is a widely used algorithm for solving constrained optimization problems in image restoration. Among many useful features, one critical feature of the ADMM algorithm is its emph{modular} structure which allows one to plug in any off-the-shelf image denoising algorithm for a subproblem in the ADMM algorithm. Because of the plug-in nature, this type of ADMM algorithms is coined the name “Plug-and-Play ADMM”. Plug-and-Play ADMM has demonstrated promising empirical results in a number of recent papers. However, it is unclear under what conditions and by using what denoising algorithms would it guarantee convergence. Also, since Plug-and-Play ADMM uses a specific way to split the variables, it is unclear if fast implementation can be made for common Gaussian and Poissonian image restoration problems.

We propose a Plug-and-Play ADMM algorithm with provable fixed point convergence. We show that for any denoising algorithm satisfying an asymptotic criteria, called bounded denoisers, Plug-and-Play ADMM converges to a fixed point under a continuation scheme. We also present fast implementations for two image restoration problems on super-resolution and single-photon imaging. We compare Plug-and-Play ADMM with state-of-the-art algorithms in each problem type, and demonstrate promising experimental results of the algorithm.

MATLAB Implementation

Publication:

  1. Stanley H. Chan, Xiran Wang, and Omar Elgendy, ‘‘Plug-and-Play ADMM for image restoration: Fixed point convergence and applications’’, IEEE Trans. Comp. Imaging, vol. 3, no. 5, pp.84–98, Mar. 2017.

  2. Xiran Wang and Stanley H. Chan, ‘‘Parameter-free Plug-and-Play ADMM for image restoration’’, IEEE ICASSP, pp.1323-1327, New Orleans, Louisiana, Mar. 2017.

Total Variation Minimization

deconvtv 

In this project, we develop a fast numerical optimization method to solve total variation image restoration problems. The method transforms the original unconstrained problem to an equivalent constrained problem and uses an augmented Lagrangian method to handle the constraints. The transformation allows the differentiable and non-differentiable parts of the objective function to be separated into different subproblems where each subproblem may be solved efficiently. An alternating strategy is then used to combine the subproblem solutions.

MATLAB Implementation

Publication:

  1. Stanley H. Chan, Ramsin Khoshabeh, Kris B. Gibson, Philip E. Gill and Truong Q. Nguyen, An augmented Lagrangian method for total variation video restoration, IEEE Trans Image Process., vol. 20, no. 11, pp.3097-3111, Nov 2011.

  2. Stanley H. Chan, Ramsin Khoshabeh, Kris Gibson, Philip E. Gill and Truong Q. Nguyen, An augmented Lagrangian method for video restoration, IEEE ICASSP, pp.941-944, Prague, May 2011.

  3. Daniel Pipa, Stanley H. Chan, and Truong Q. Nguyen, Directional Decomposition Based Total Variation Image Restoration, EUSIPCO, pp.1558-1562, 2012.

Depth Estimation: Reconstruction and Sampling

disparity 

Acquiring depth information is the first and the most important step for 3D image processing. Existing depth acquisition methods either use expensive hardware devices and computationally intensive block matching algorithms. We propose a compressive sensing based method to estimate the depth using a few samples. Our solution is unique in the following sense:

  • We pick samples spatially without the need of mixing (a common setting in classical compressive sensing which often requires additional hardware devices);

  • Our method works for both hardware devices and block matching algorithms; Given a small subset of reliable depth measurement, we can recover the entire dense depth map;

  • Our optimization algorithm is based on an augmented Lagrangian method, which can be fully parallelized on GPU to achieve real time computation;

  • We provide practical sampling schemes to minimize the number of samples and optimize the sampling locations.

    MATLAB Implementation

    Publication:

  1. Lee-Kang Liu, Stanley H. Chan, and Truong Q. Nguyen, ‘‘Depth Reconstruction from Sparse Samples: Representation, Algorithm, and Sampling’’, IEEE Trans. Image Process., vol. 24, no. 6, pp. 1983-1996, Jun. 2015.

  2. Ramsin Khoshabeh, Stanley H. Chan and Truong Q. Nguyen, Spatio-temporal consistency in video disparity estimation, IEEE ICASSP, pp.885-888, Prague, May 2011.

Motion Estimation

Motion 

In conventional block matching motion estimation algorithms, subpixel motion accuracy is achieved by searching the best matching block in an enlarged (interpolated) reference search area. This, however, is computationally expensive as the number of operations required is directly proportional to the interpolation factor. For non video compression based applications, the interpolation process is even wasteful as the motion compensation frames are not needed. This project aims at developing a fast motion estimation algorithm that achieves subpixel accuracy without interpolation. We show that by fusing the existing integer block matching algorithm and a modified optical flow method, subpixel motion vectors can be determined at the cost of integer block matching plus solving a 2-by-2 systems of linear equations. Experimental results demonstrate that the proposed method is faster than conventional method by a factor of 2 (or more), while the motion vector quality is compatible to the benchmark full search algorithm.

MATLAB implementation

Publication:

  1. Stanley H. Chan, Dung Vo and Truong Q. Nguyen, Subpixel motion estimation withouth interpolation, IEEE ICASSP, pp.722-725, Dallas, March 2010.