A Fast Non-local Means Algorithm For Image Denoising

As one of the most basic problems in the field of digital image processing, imagedenoising has developed for decades and is constantly developing. According to theactual project needs, the thesis implements a denoising algorithm which has gooddenoising effect, low computational complexity and be commercially available. So farnon-local means filter denoising algorithm is the excellent denoising algorithms,which can effectively remove noise and well retain the detail of the image at the sametime. But the complexity of the non-local means filter algorithm is very high, the timeneeded for processing images of the single frame720P is minute’s level, which cannotbe adopted in the practical systems. The thesis hopes to optimize the non-local meansfilter denoising algorithm to achieve real-time processing level.The thesis first analyzes the proportion of each module taking time in thefiltering processing of Non-Local Mean filter algorithm. After the test we know theproportion of weight calculation part occupied the most part time, account for nearly70%of the entire filtering processing time, so the thesis focuses on the optimizationof weight calculation. The thesis puts forward five steps of optimization:(1) using thesymmetry of the pixel value and the memory for time optimization method to put theweight into memory temporarily, so that the time complexity halved;(2) reversing thepixel position and the traversal sequence of neighborhood, so the weight of each pixelis calculated without disturbing each other and it is convenient to parallel processingof pixels, which laid a foundation for the following algorithm using the subsampledprinciple to optimize;(3)optimizing the Gaussian function using approximatecalculation, approximating the bell-shaped curve of Gaussian function as a line, andreducing the computation time of the Gaussian function convolution;(4) using thesubsampled principle, only to calculate the weight of the sampled pixels, using thebilinear interpolation algorithm to interpolate the weight of not sampled pixels,reducing the calculation time of weight;(5) using ARM Neon instructions to optimizemachine instruction set. In the above five optimization strategy, there are theoptimization of the algorithm and the optimization of the project, where thesubsampled optimization has the largest contribution on the lower time complexity,and the greatest influence on the performance of the filter. The thesis needs search foran optimal range of the subsampled magnitude, so that the filter can reach a compromise between performance and the complexity of algorithm. Through theexperiment the optimal parameters of the sampling step length is4. After theoptimization of the above five steps, the non-local means filtering algorithm in thethesis on IPad4equipment for processing720P images can reach28ms per frame,achieve the real-time requirements.