Fast Patch-based Denoising Using Approximated Patch Geodesic Paths

Xiaogang Chen[1,3,4], Sing Bing Kang[2], Jie Yang[1,3], Jingyi Yu[4]

1 Shanghai Jiao Tong University, Shanghai, China. {cxg,jieyang}

2 Microsoft Research, Redmond, WA, USA.

3 Key Laboratory of System Control and Information Processing, Ministry of Education, China

4 University of Delaware, Newark, DE, USA.


Fragments of noisy (sigma = 25, PSNR 20.18dB) grayscale images and the corresponding BM3D and PatchGP estimates




Patch-based methods such as Non-Local Means (NLM) and BM3D have become the de facto gold standard for image denoising. The core of these approaches is to use similar patches within the image as cues for denoising. The operation usually requires expensive pair-wise patch comparisons. In this paper, we present a novel fast patch-based denoising technique based on Patch Geodesic Paths (PatchGP). PatchGPs treat image patches as nodes and patch differences as edge weights for computing the shortest (geodesic) paths. The path lengths can then be used as weights of the smoothing/denoising kernel.

We first show that, for natural images, PatchGPs can be effectively approximated by minimum hop paths (MHPs) that generally correspond to Euclidean line paths connecting two patch nodes. To construct the denoising kernel, we further discretize the MHP search directions and use only patches along the search directions. Along each MHP, we apply a weight propagation scheme to robustly and efficiently compute the path distance. To handle noise at multiple scales, we conduct wavelet image decomposition and apply PatchGP scheme at each scale. Comprehensive experiments show that our approach achieves comparable quality as the state-of-the-art methods such as NLM and BM3D but is a few orders of magnitude faster.


Following the principle of reproducible research, we make our software routines available for non-profit scientific research, enabling others researchers to understand, reproduce and extend our work. Unauthorized use of the routines for industrial or profit-oriented activities is expressively prohibited.

Download PatchGP software here.

Download PatchGP paper here.

Patch Geodesic Paths

We define the Minimum Hop Path (MHP) as the path with the minimal number of hops connecting two nodes. Left: The MHP between p and q (red). Right: MHPs under 8 search directions.

Minimum Hop Paths (MHP) vs. Patch Geodesic Paths (PatchGP). We randomly select 200 images from Berkeley image segmentation database and add white Gaussian noise (sigma_n=5 and sigma_n=15). For each configuration (patch size, window size, noise variance), we find PatchGP between every pair of patches and verify if it is an MHP. The percentage of PatchGP being MHP is shown in (a) 5×5 patch size and (b) 7×7 patch size.


Patch Geodesic Distance. (a) shows the cameraman image and two central patches (5x5) we aim to denoise. For each patch, we use a spatial support (window size) of 13×13. For each patch within the window, we find its PatchGP to the central patch and compute the actual path distance. (b) and (e) show the closeup views of the two patches. (c) and (f) show the patch distance map.(d) and (g) show the color-coded path hop maps for the corresponding PatchGPs.



Figure 1.

Quality comparison between PixelGP, PatchGP, FPatchGP, and FM-PatchGP. (a) and (b) show the latent and the noisy images.

Figure 2.

Denoising results on the ’man’ image with Gaussian noise sigma =15. Our result is comparable state-of-the-art but is one to three orders of magnitude faster.



Figure 3.

Quality comparisons on denoising quality using FM-PatchGP and state-of-the-art algorithms: NLM, FOE, BM3D, PixelGP, and F-BL. Gaussian noise at different levels (sigma ranges from 5 to 30) is added 8 images.


Figure 4.

Quality and time comparisons between NLM, FMPatchGP and BM3D on a high resolution image. The noise level sigma ranges from 10 to 30. The processing time, independent of the noise level, are shown in the middle column.


Figure 5.

Comparisons between FM-PatchGP and two commercial denoising tools Noise Ninja and Neat Image on real images.



Shanghai Jiao Tong University, Xiaogang Chen, Jie Yang

Microsoft Research, Sing Bing Kang

University of Delaware, Jingyi Yu


This project was partially supported by the National Science Foundation (US) under grants IIS-CAREER- 0845268 and IIS-RI-1016395; NSFC China (No:61273258, 61105001, 61075012); Ph.D. Programs Foundation of Ministry of Education of China (No.20120073110018) and Committee of Science and technology, Shanghai (No:11530700200). Most of this work was done while the first author was a visiting scholar at the University of Delaware.