Speeding up the patch ordering method for image denoising

Smooth ordering of local patches (patch ordering) has been shown to give state-of-the-art results for image denoising. However, use of very large TSPs (Traveling Salesman Problem) makes it computationally intensive. The patch ordering method forms two large TSPs and employs their approximate solutions in a filtering process to perform denoising. On average, 84% of patch ordering’s execution time was found to be spent on solving TSPs. A variation of the patch ordering method is proposed with two changes. First, numerous smaller TSPs are formed instead of two large ones. Second, the filtering process is modified to perform denoising with solutions of numerous smaller TSPs instead of two large TSPs. Compared to the patch ordering method, the proposed method can denoise images 3.34 times faster. In terms of PSNR, the proposed method’s denoising performance differed by only 0.06 dB on average. Moreover, the proposed method is highly amenable to parallelization. By solving TSPs in parallel, the proposed method’s parallel implementation denoised images 4.89 times faster using four CPU cores which reduced denoising time by 80%. Also shown is that given the same computing resources (CPU cores), the proposed method shall attain speedups higher than those by a similarly parallelized version of the patch ordering method. The proposed approach can be used to speed up patch ordering for other image processing tasks.