This is (finally) a follow-up to my latest post!

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.

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:

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.

The SNR situation is getting worse, or at the very least **more and more intriguing**.