The Non-Local Means algorithm 1 is a very popular image denoising algorithm.
Besides its efficiency at denoising, it’s also one of the main causes to the non-locality trend that has arisen in Image Processing conferences ever since. Yet, there is this recent paper on Arxiv 2: Non-Local means is a local image denoising algorithm by Postec, Froment and Vedel.
Some background on NL-means NL-means is a very simple, yet highly efficient image denoising algorithm that preserves well image textures even with severe noise.
Disclaimer: I’ve been a reviewer for this book.
About the book Some context A few months ago, I was kindly asked to review a book to-appear that was entitled Instant OpenCV for iOS, that is now available (at least as an eBook). The book is edited by Packt Publishing, where I bought a few books before, in particular two previous books about OpenCV, an introductory one (by R.
Ca a pris un peu de temps1, mais mon manuscrit de thèse est accessible en ligne librement depuis quelques jours ! Bien évidemment, c’est un must si vous vous intéressez aux méthodes variationnelles non-locales :-p
Blague à part, le manuscrit (en Anglais) est donc disponible ici.
Au cours des semaines qui viennent, je rajouterai quelques notes pour décrire grossièrement les idées fortes de mon travail. N’hésitez donc pas à revenir !
Semi-nonlocal implementations As can be inferred from the description, NL-means is a greedy algorithm: for each pixel, the denoising pixel can explore the whole image. Thus, it is common practice to limit the nonlocal exploration stage at a limited window around each pixel1. However, since nonlocality is achieved only inside a subwindow around each pixel, I refer to these implementations as semi-nonlocal.
It is common for an implementation of NL-means to include an additional parameter for the size of the learning window.
In the previous episode, we have seen the main idea of NL-means:
A good denoising algorithm can be obtained by a simple weighted average of noisy pixels, at the condition that the weights depend on the content of patches around the pixels instead of their spatial distance.
In this post, we will put proper mathematical definitions behind those patches and weighted average. I will proceed in successive steps:
Achievement (almost) unlocked A quick note to say that I’ve fulfilled the first requirement towards graduation: my doctoral dissertation was accepted by the jury1 during a private oral exam. Wow ! And I have to say that I am really grateful to the jury, both for the kind comments and for their criticism about my work, that will help me deliver a better manuscript.
What’s coming next ? I still have to make up a public presentation to officially disclose the content of the thesis and graduate, which should happen in 2 or 3 months.
Non-locality and NL-Means Non-locality is a powerful recent paradigm in Image Processing that was introduced around 2005. Put in simple words, it consists in considering that an image is a collection of highly redundant patches. In this context, pixels get described by the surrounding patch instead of their sole value), and patch relationships are only deduced from their visual similarity (thus ignoring their spatial relationship).
Non-locality comes in two flavors: exemplar-based 1 or sparsity-based.