(JBE Vol. 1, No. 1, January 016) (Regular Paper) 1 1, 016 1 (JBE Vol. 1, No. 1, January 016) http://dx.doi.org/10.5909/jbe.016.1.1.60 ISSN 87-9137 (Online) ISSN 16-7953 (Print) a), a) An Efficient Method to Compute a Covariance Matrix of the Non-local Means Algorithm for Image Denoising with the Principal Component Analysis Jeonghwan Kim a), and Jechang Jeong a) (noise) (non-local means, NLM) (principal component analysis, PCA). (covariance matrix),. (neighborhood patch),..,., floor. Abstract This paper introduces the non-local means (NLM) algorithm for image denoising, and also introduces an improved algorithm which is based on the principal component analysis (PCA). To do the PCA, a covariance matrix of a given image should be evaluated first. If we let the size of neighborhood patches of the NLM, and let the number of pixels, a matrix multiplication of the size is required to compute a covariance matrix. According to the characteristic of images, such computation is inefficient. Therefore, this paper proposes an efficient method to compute the covariance matrix by sampling the pixels. After sampling, the covariance matrix can be computed with matrices of the size floor. Keyword : image processing, denoising, non-local means, principal components analysis, covariance matrix
1 : (Jeonghwan Kim et al.: An Efficient Method to Compute a Covariance Matrix of the Non-local Means Algorithm for Image Denoising with the Principal Component Analysis)., (noise). (denoising). (non-local means, NLM) [5][6][7]. (pixel),,. (principal component analysis, PCA), PCA (covari- ance matrix)...,. 4, 5. a) (Department of Electronic and Computer Engineering, Hanyang University) Corresponding Author : (Jechang Jeong) E-mail: jjeong@hanyang.ac.kr Tel: +8--0-4369 ORCID: http://orcid.org/0000-000-3759-3116.[r0601-15-1063, ICT SW ] Manuscript received October 14, 015; Revised December 4, 015; Accepted December 10, 015.. (Non-local means algorithm) ( ) v( i). v( i) = u( i) + h( i) (1) u( i), h( i) (additive white Gaussian noise, AWGN). i (index) Q i { 1,,, Q} = L. v( i) [1] i S S (neighborhood patch) i u( i).. v( Ni )-v( N j ) - h 1 u( i) = å e v( j) Z( i) % jîwi Ni i S Wi i R S, R (searching window), u% ( i), v( i ) v( j ) h Z( i) = å e - N - N jîw (normalization) i. h (parameter). h. [1] s, h = 10 s, [] (peak signal-to-noise ratio, PSNR)
(JBE Vol. 1, No. 1, January 016). O Q S R ( ). Q S R. [1] R. R, [3], R ³ 15. S R 5 S 9 [3].. (Principal neighborhood dictionary non-local means) Q,. [] L, [4] (dimensions) L.. M Î R S Q. { } = { } pi ( k), i= 1,, L, Q, k 1,, L, S (column vector), pi p S S i. CÎ R. 1 T C = M M Q C (eigenvalues) (eigenvectors) { w :1 d d S }. N. (principal neighborhood dictionary non-local means, PND NLM) []., vd ( Ni )-vd ( N j ) - h 1 u% ( i) = å e v( j) Z ( i) jîwi d N vd ( i ) vd ( j ) h Zd ( i) = å e - N - N jîw. i,.. é p1 (1) - p1 p(1) - p L pq (1) - p ù Q ê ú ê p1 () - p1 p() - p L pq () - pq ú M = ê M M O M ú ê ú ê p1 ( S ) - p1 p( S ) - p pq ( S ) - p ú ë L Q û,.. []
1 : (Jeonghwan Kim et al.: An Efficient Method to Compute a Covariance Matrix of the Non-local Means Algorithm for Image Denoising with the Principal Component Analysis) 10%,.... 1. PSNR Table 1. PSNRs and computation time of the covariance matrix with increasing 51 51 Lena, s = 10, S = 7, R = 13, h = 4, d = 6 Distance PSNR (db) Computation time of the covariance matrix (%) Computation time of the algorithm (%) 1 34.6 100.00 100.00 34.6 38.14 97.15 4 34.6 8.58 96.84 8 34.60 1.16 96.67 16 34.60 0.44 96.38 3 34.57 0.7 96.70 64 34.70 0. 96.61 18 34.01 0.19 96.58 1. Fig. 1. Pixel sampling 1.,, M. M Î R l æwidth ö æ Height ö S floorç floorç è l ø è l ø floor ( ) (floor function),. 1 C. Intel i5-500, 4GB RAM, MATLAB R011a, 1,... (basis).. 1.. 1 ( ). Fig.. Comparison of subject results of the table 1 (From left to right, )
(JBE Vol. 1, No. 1, January 016) 3. PSNR ( ) Fig. 3. PSNRs for several standard images with varying noise level and distance between samples( ),. 3.,,.. ( )... (7).. l op ì 0 ( s 5) ï 19 = í- s + 39 (5 < s < 50) ï 5 ïî 1 ( s ³ 50)
1 : (Jeonghwan Kim et al.: An Efficient Method to Compute a Covariance Matrix of the Non-local Means Algorithm for Image Denoising with the Principal Component Analysis).. 1,. ( ).. (References) [1] A. Buades, B. Coll, and J.-M. Morel, A non-local algorithm for image denoising, CVPR, vol., pp. 60-65, June, 005. [] T. Tasdizen, Principal neighborhood dictionaries for nonlocal means image denoising, IEEE Trans., Image processing, vol. 18, no. 1, pp. 649-660, Sep, 009. [3] J. Salmon, On two parameters for denoising with non-local means, IEEE Signal processing letters, vol. 17, no. 3, pp. 69-7, Jan, 010. [4] L. I Smith, A tutorial on principal components analysis, Feb, 00, http://www.cs.otago.ac.nz/cosc453. [5] C. Tomasi and R. Manduchi, Bilateral filtering for gray and color images, ICCV, pp. 839-846, Jan, 1998. [6] K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, Image denoising by sparse 3D transform-domain collaborative filtering, IEEE Trans., Image processing, vol. 16, no. 8, pp. 080-095, Aug, 007. [7] S. G. Chang, B. Yu, and M. Vetterli, Adaptive wavelet thresholding for image denoising and compression, IEEE Trans. Image processing, vol. 9, no. 9, pp. 153-1546, Sep, 000. - 014 : - 014 3 ~ : - ORCID : http://orcid.org/0000-000-981-7338 - :, - 1980 : - 198 : KAIST - 1990 : - 1980 ~ 1986 : KBS ( ) - 1990 ~ 1991 : ( ) - 1991 ~ 1995 : (MPEG, HDTV, ) - 1995 ~ : ( ) - 1998 11 : - 1990 1 : - 007 : IEEE Chester Sall Award - 008 : ETRI Journal Paper Award - 011 5 : 46 - ORCID : http://orcid.org/0000-000-3759-3116 - :,, 3DTV