Speeding up the patch ordering method for image denoising

Badre Munir*, Syed Fawad Hussain, Adnan Noor

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)23639-23657
Number of pages19
JournalMultimedia Tools and Applications
Issue number16
Publication statusPublished - 30 Aug 2019

Bibliographical note

Publisher Copyright:
© 2019, Springer Science+Business Media, LLC, part of Springer Nature.


  • Denoising
  • Parallel processing
  • Patch-based processing
  • Pixel permutation
  • Speedup
  • Traveling salesman

ASJC Scopus subject areas

  • Software
  • Media Technology
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Speeding up the patch ordering method for image denoising'. Together they form a unique fingerprint.

Cite this