快速非局部去噪算法

所需积分/C币:20 2013-11-30 13:46:11 449KB PDF

基于FFT和积分图的快速非局部去噪算法,作者来自浙大
for o>0, y0=0, It is well known that convolution becomes multiplication uin- der Fourier transform, thus only n- multiplications need to be SSI(xo,0)=SSI(xo-1,0)+12(xo,0); (9) taken for each pixel in the image in our algorithm. Further more, Fourier transform can be performed quickly by modern for 0=0, yo>0 hardware fft accelerator within a neglectable time, convolu tion can therefore be fast carried out. as for the summations SS0,yb)=S(0,0-1)+12(0,); (10) of squares, only addition operations are needed in this process which can also be neglected compared to the multiplications 0 In(4), computing the similarity of the two compare window SSI(a0,yo ))= SSI(o-1, yo)+ SSI(ao, yo 1) requires M2 pixel operations, while, in our algorithm, it is SSI(ao-1, yo-1)+I2(,W5, w figured out once which is achieved by means of FFT. Thus the total computational complexity is n, which is M times faster than the original algorithm Obviously, with above algorithm, each pixel in the origi- nal image is processed only once, so the computational com In theory, the neighborhood size M should be congruent plexity for computing p SSl is O(n2), in which n is the size of to the size of the repeated patterns in the image. In order to the image achieve convincing results, M should be set larger in higher By means of SSl, we can easily get the sum of squares resolution images, which leads to a significant slowdown in the original algorithm but no performance changing in ours for each pixel in any rectangles of the image within constant time. For example in Fig. 2, to calculate the sum of squares As suggested in Buades paper [4], M is set to be 7, and a 21s21 search window is used instead of the whole image. In in rectangle D, only 3 addition operations are required, such simplification, instead of requiring 49 pixel operations when computing the similarity of two windows in [4], we fig ure out the similarity once by FFT and Summed squares Im B age(sSi), thus the complexity of our algorithm is 441 *n (x,V0 (x2y) Clearly, comparing tO the original 49*441*7, our algorithm is about fifty times faster. This makes the performance of C D our algorithm acceptable to common users as is demonstrated (Xiv (xi,v) in Table 1. Experiments on a pc with a Pentium Iv 2.4G Image CPU and 512M ram demonstrate that it takes no more than 10 seconds to denoise a 50oMegabyte photo using our algo Fig. 2. Using SS! to compute the summed squared pixels in the rithm, while the original non-local algorithm requires nearly ectangle d 10 minutes Our denoising results are comparable to that of the origi nal non-local algorithm in terms of mean squared error (mse) D SauBUCUd+ SA- SAUC- SAUB Table 2 compares the mean squared error(mse for differ SSI(1, 1)+SSI(ao, yo ent standard deviation of the added noise between our ac 5SI(x0,y1)-SSI(x1,9) celerated method and the original algorithm, note that the slightly difference in mse is due to the use of the euclid Therefore, N2 and N2 can be computed quickly with equ. ean distance when comparing two neighborhood instead of a (11) once we get SS of the noised image. Accurate analy weighted Euclidean distance in original non-local algorithm sis in section 3 will show that our fast non-local algorithm is 14; Fig.3 visualizes the comparison. Fig. 4 compares the much faster than the original one denoising results of our acceleration method with that of non local [4 for noisy Lena in which the standard deviation of 3. DISCUSSIONS AND EXPERIMENTATIONS noise is 20; Fig. 5 gives our denoising result of Lena Table 1. performance results The most time-consuming part of the non-local algorithm [4] Image size Original nl Fast Nl algorithm Ratio is the calculation of the euclidian distance between similar 512*5122816secs. 0.35 secs 80.5 windows in the image. For each pixel in the image, it takes 1024*7688545secs 1, 44 secs 58.6 M=. n square calculations, and the whole computational 2592*1944 551.1 secs. 9.55 secs 57.7 omplexity is M2 n4(M2 denotes the size of similar win- dows and n- represents the number of pixels in the noised Table 2. MSE comparison Image Stand deviationσ 510152025 In our fast non-local algorithm, this process has been trans Our acceleration method.6 32 5581110 formed to computing convolution and summation of squares Original non -local 12305268106 1431 MSE 110 100 20 0 5 15 20 25 H Our acceleration method -i Original algorithm Fig 3. Comparison of the mean squared error(MSE) for different stand deviation of the noise between our acceleration method and ginal algorithm Avla Fig. 5. Our denoising result of noised lena (standard deviation 20 「5]P.Ⅴ iola and j. Michael,“ Rapid object detection using a boosted cascade of simple features In. Proc. IFFE CVPR,2001. Fig. 4. Comparison between non-local effect and our acceleration result. From left to right, original image, noised image, the result of non-local /4 (MsE 68) and our result (Mse 81) 4. CONCLUSIONS Exploiting Summed Square Image(SSn)and fast Fourier trans form(FFT), we proposed a fast non-local denoising algorithm in this paper. Theoretically and experimentally, the efficiency of our accelerated algorithm is about fifty times of the origi- nal algorithm, and the denoising results are still comparable to the results of the original algorithm both in MsE and per ception. Thus our accelerated algorithm is feasible to tackle with practical problens. 5. REFERENCES 1 M. Lindenbaum, M. Fischer, and A. Bruckstein,"On ga- bor contribution to image enhancement, ' Pattern recog- nition,vol 27. pp. 1-8, 1994 [2 L. Rudin, S Osher, and E Fatemi, " Nonlinear total vari- ation based noise removal algorithms, Physica D, vol 60,pp.259-268,1992 [3 C. Tomasi and R. Manduchi, ""Bilateral filtering for gray and color images, " In: PrOc. IEEE /CCV, pp. 839-846 1998. [4] A Buades, B. Coll, and J M. Morel, "A non-local algo ithm for image denoising In: Proc. IEEE CVPR. vol 2,pp.60-65,2005 1432

...展开详情

评论 下载该资源后可以进行评论 2

ly多啦a梦 写得很详细,要是能配代码讲解一下就更好了
2015-10-19
回复
apple_jiadi 是学习非局部去噪理论的基础,讲解的较为清楚
2014-11-06
回复
img

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源