Efficient Non-Local Means Image Denoising Using Binary Descriptor Pre-Classification and Distance-Based Pre-Termination

Among currently available image denoising algorithms, non-local means (NLM) is one of the most effective methods. NLM calculates weights of neighboring pixels based on the similarity between two image patches. The denoised pixel is estimated by the weighted sum of the neighboring pixels. Because the number of neighboring patches needs to be sufficiently large so that enough similar patches can be covered, NLM incurs high computational cost. In this paper, we incorporate binary descriptor pre-classification and distance-based pre-termination to exclude dissimilar patches from the computation so that the performance of NLM can be enhanced. A binary descriptor produces a simple binary string to describe an image patch by comparing pixels with a given threshold. Before calculating the weight between two patches, their binary descriptors are compared and the patch is skipped if the binary descriptors are not the same. Although binary descriptor pre-classification can exclude a large number of dissimilar patches, some patches with large distance between them are still calculated. Therefore, after the pre-classification, during the process of calculating distance between two patches, the computation is pre-terminated if the accumulated distance is larger than a threshold and that patch is also excluded from the weight calculation. Experimental results show that combining these two approaches in excluding dissimilar patches can effectively increase the denoising performance of NLM and significantly reduce the execution time.