Report

Transform-based Non-local Methods for Image Restoration IT530, Lecture Notes Non-local Techniques Natural images have a great deal of redundancy: patches from different regions can be very similar NL-Means: a non-local pixelbased method (Buades et al, 2005) •Awate and Whitaker (PAMI 2007) •Popat and Picard (TIP 1998) •De-Bonet (MIT Tech report 1998) •Wang et al (IEEE SPL 2003) Difference between patches 2 Transform-based Techniques DCT coefficients of a “typical” natural image Observed property of natural images: Sparse coefficients in Fourier/DCT/ Wavelet domain 3 Transform-based Techniques DCT Coefficients Manipulate coefficients of (absolute value) coefficients noisy patch of filtered patch Get filtered patch by inversion of the transform from Noisyfiltered Patch coefficients Repeat for all patches in sliding window fashion: final filtered Project Patch onto image obtained by averaging Transform Basis overlapping filtered patches. (DCT/Wavelet Clean Patch etc.) Transform basis Patch matrix Transform Coefficients 4 Non-local transform based techniques • Machine learning approach. • Make use of non-local self-similarity at the patch level to learn good transform bases for denoising. Non-local PCA • PCA is the most basic transform to learn! • Assume Gaussian noise (mean zero, known variance). • Given a patch (called “reference patch”) in a noisy image, search for similar patches elsewhere in the image. • Given such a collection of patches, compute their PCA bases. • Compute the eigen-coefficients of the reference patch. Non-local PCA • Manipulate these eigen-coefficients (by hardthresholding or Wiener filter). • Reconstruct the reference patch. • Repeat the procedure for every patch in the noisy image in sliding window fashion. • Average the multiple hypotheses that appear at a pixel. Ref: Muresan and Parks, “Adaptive principal components for image denoising”, ICIP 2003. Criterion: Patch Similarity P1 Pref z ~ N ( 0 , ) 2 Two patches: identical || P1 P 2 || 2 2 ~ ( n ) modulo noise 2 2 P2 Pref z ~ N ( 0 , ) Cumulative of chi-squared is incomplete gamma function. 2 x n ( , ) 2 2 2 F ( x ; n ) GammaInc 2 2 2 2 n 3 n 1 || P1 PP2 || if their 3 nsquared patch F ( 0A. 99 ; P1) is considered similar to patch ref 2 2 2 difference is less than or2 equal to 2 2 3n 2 8 Non-local PCA y i xi ni , ni ~ N ( 0, ) Noisy patch The l-th coefficient of yi – computed by projection onto the l-th local PCA bases (obtained from similar patches) l We are modelling x i as zero-mean Gaussian random variable with variance l Two-stage non-local PCA Ref: Zhang et al, Two stage image denoising by principal components analysis with local pixel grouping KSVD BM3D PCA KSVD BM3D PCA KSVD BM3D PCA Time complexity • The patches of size p x p are treated as vectors of size p2 x 1. • Hence the covariance matrices are of size p2 x p2. • Eigen-analysis will have a time complexity of O(p6) per patch (not counting the time to search for similar patches). • This is quite expensive. Non-local collaborative filtering: Block Matching in 3D (BM3D) • The state of the art method today. • Based on the idea of non-local similarity at the patch-level. • Given a reference patch in the noisy image, this method again collects similar patches. • But this time, the similar patches and the reference patch are arranged in the form of a 3D stack (of say some K patches in all). Non-local collaborative filtering: Block Matching in 3D (BM3D) • The stack is projected onto 3D transform bases (typically 3D DCT, or tensor product of 2D DCT and 1D Haar wavelets). • The 3D transform coefficients are manipulated – usually by hard thresholding using the universal threshold 2 log( p 2 K ). • All the patches in the entire stack are reconstructed using an inverse 3D transform. • This is repeated for every patch in the image. The multiple answers appearing at any pixel are averaged. BM3D – second stage • The preceding steps form the first stage of BM3D. • The output image of the first step is used to compute patch similarities (this will be more robust than computing the similarities in the noisy image). • Patches from the first-stage image are then appropriately assembled into a stack. • Corresponding patches from the noisy image are assembled into a second stack. BM3D – second stage • 3D transform coefficients of both the stacks are computed. • The second stack is denoised using Wiener filtering as follows: 2 c second stage c stage one c 2 stage one 2 c noisy • This is again repeated in sliding-window fashion with averaging. Note: BM3D does allow individual patches from the patch to be independently filtered. It filters the similar patches from the stack collectively, assuming a dependence between them! This is the reason for its superior performance. Results • State of the art denoising method. • Impressive results even at high noise levels. • Residual images produced are very noisy. • Preserves textures and fine details/edges very well. Noisy PSNR: 22.13 NL-SVD: PSNR 30.88 SSIM 0.882 BM3D1: PSNR 31.02 SSIM 0.884 BM3D2: PSNR 31.66 SSIM 0.903 HOSVD: PSNR 31.53 SSIM 0.897 NLMeans: KSVD: PSNR 30.762 29.42 SSIM 0.877 0.821 24 KSVD HOSVD BM3D2 BM3D1 NL-SVD 25 Noisy PSNR: 22.13 NL-SVD: PSNR 30.187 SSIM 0.801 BM3D1: PSNR 30.395 SSIM 0.809 BM3D2: PSNR 30.8 SSIM 0.824 HOSVD: PSNR 30.491 SSIM 0.814 NLMeans: KSVD: PSNR 30.36 28.91 SSIM 0.803 0.753 26 KSVD HOSVD BM3D2 BM3D1 NL-SVD 27 Gaussian Noise sigma = 15 28