EE Systems Seminar

Wednesday August 28, 2013 11:00 AM

Monte Carlo Non-Local Means: Random Sampling for Large-scale Denoising

Speaker: Stanley Chan, School of Engineering and Applied Science and Department of Physics, Harvard University
Location: Moore B280

<!-- /* Font Definitions */ @font-face {font-family:Calibri; panose-1:2 15 5 2 2 2 4 3 2 4; mso-font-alt:Calibri; mso-font-charset:0; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:3 0 0 0 1 0;} @font-face {font-family:Cambria; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:3 0 0 0 1 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-parent:""; margin:0in; margin-bottom:.0001pt; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman"; mso-ascii-font-family:Cambria; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Cambria; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Cambria; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} p.Default, li.Default, div.Default {mso-style-name:Default; mso-style-parent:""; margin:0in; margin-bottom:.0001pt; mso-pagination:none; mso-layout-grid-align:none; text-autospace:none; font-size:12.0pt; font-family:Calibri; mso-fareast-font-family:Cambria; mso-fareast-theme-font:minor-latin; mso-bidi-font-family:Calibri; color:black;} @page Section1 {size:8.5in 11.0in; margin:1.0in 1.25in 1.0in 1.25in; mso-header-margin:.5in; mso-footer-margin:.5in; mso-paper-source:0;} div.Section1 {page:Section1;} -->


Non-local means (NLM) is a well-known and influential image denoising algorithm. Since its publication in 2005, the NLM algorithm has been widely cited and compared against many more advanced algorithms in the denoising literature. However, NLM's high computational complexity remains an open issue to the image processing community.

In this talk, I will present a scalable NLM algorithm, called the Monte-Carlo Non-local Means (MCNLM). Different from the classical NLM which computes the distances between every pair of pixel patches in the image, MCNLM computes only a subset of randomly selected pairs of patches. Two major analytical questions of MCNLM will be discussed. First, using the statistical large deviation theory, I will provide theoretical guarantees of MCNLM for any random sampling strategy. Second, I will discuss the optimal sampling pattern which maximizes the rate of convergence.

MCNLM has marginal memory and programming costs compared to the original NLM algorithm, yet it is scalable to large-scale problems. In our experiment, apart from the denoising images using the noisy image itself, we also applied MCNLM to denoise image patches using external databases. On a database containing 10 billion patches, we demonstrate 3 orders of magnitudes in speed up.

(Joint work with Todd Zickler and Yue Lu)

Series Electrical Engineering Systems Seminar Series

Contact: Shirley Slattery at 626-395-4715