Efficient Implementation of Non-Local Means Image Denoising Algorithm

Image acquisition has become a common feature in many consumer electronic devices. In processing the acquired images, denoising is a critical task in providing good quality images and non-local means (NLM) is one of the most effective approaches in currently available denoising algorithms. Using weights based on the similarity between image patches, NLM estimates the denoised pixel by the weighted sum of the neighboring pixels. Because the number of neighboring pixels needs to be sufficiently large so that the denoising effect of the weighted averaging operation can be fulfilled, NLM needs to calculate a large number of similarities between patches. This translates to extremely high computational cost and limits its application in consumer electronic devices. In this paper, we incorporate 3 strategies to speed up the computation. The first strategy is to use binary descriptors of patches to exclude dissimilar patches from computation. The second strategy is the pre-termination of similarity computation when the distance between patches exceeds a threshold. The third strategy is to apply a spiral trajectory instead of a zig-zag trajectory to search for similar patches. Experimental results show that applying these strategies can speed up the processing by 11.5 times and still enhance the denoising performance of NLM.