BookNotesSlidesP-sets Syllabusdraft · v0.2.49.1
◀▲⌂▶
💬Comments welcome. To leave a note, select any text and click the note / highlight button that pops up — or open the panel with the tab at the top-right (‹). Notes are visible only inside our private review group.

10.2 Non-local means⧉

A noisy pixel value is an unreliable guide to similarity. Two samples from the same surface can differ because of noise, while unrelated surfaces can have the same intensity. Non-local means compares the neighborhoods around candidate pixels before averaging their center values Buades et al. 2005.

For example, repeated bricks can supply similar patches even when their noisy center values differ. The comparison checks corresponding offsets in a small window. It averages evidence across the patch, but noise still corrupts the distance; severe noise and a large search can produce false matches.

The search may cover a generous window or the whole image. Proximity is no longer required, but the patch comparison is not automatically invariant to rotation, reflection, scale, or illumination. A mirrored eye does not necessarily match under an offset-by-offset distance. Larger searches cost more and admit more accidental matches.

Mechanically it is the bilateral, with the single-pixel difference swapped for a patch distance. The dissimilarity between the patches around $p$ and $q$ is a sum of squared value differences taken offset by offset,

$$ d^2(p,q) = \sum_{k} g_a(k)\,\lVert I(p+k) - I(q+k)\rVert^2, $$

where $k$ ranges over the patch offsets and $g_a$ is a nonnegative patch kernel normalized to sum to one. A Gaussian gives the central offsets more weight. Read it back in words: lay the two patches on top of each other, walk them in lockstep, and add up how different they are point by point. The affinity is then the same exponential falloff we have used since the bilateral,

$$ w(p,q) = \exp\!\left(-\frac{d^2(p,q)}{h^2}\right), $$

Here $h$ controls match tolerance in the units of this distance. Increasing it admits less similar patches and generally increases smoothing. There is no universal setting $h^2=2\sigma^2$: the convention for channel and patch normalization, noise model and any noise-bias correction matter. The denoised value averages candidate centers:

$$ \widehat{I}(p) = \frac{\sum_q w(p,q)\,I(q)}{\sum_q w(p,q)}. $$

The weights use complete patches, while the pixelwise estimator averages only their center values. Similar clean structures can reduce noise when pooled. However, the weights are estimated from the noisy data, and overlapping patches share samples. This is not an average of known independent copies. Unique details have few useful matches. Chapter 13.6, Non-local means and BM3D develops patch aggregation and the denoising comparison; the authors’ implementation article specifies practical distance and noise conventions.

The affinity lesson L10.1, at higher resolution

Non-local means is not a new principle; it is the affinity lesson (L10.1, from Chapter 10.1, Bilateral filtering) applied at patch scale. The bilateral's slogan was average neighbors of a similar value. Non-local means rewrites it as average pixels whose surroundings look alike, two swaps and nothing else: the single-pixel difference $\lvert I_p-I_q\rvert$ becomes the whole-patch distance $d(p,q)$, and the local window becomes the whole image. The exponential affinity and the normalized weighted average are identical. So non-local means is a bilateral filter in patch space Tomasi & Manduchi 1998. That is why image self-similarity is such a strong denoising prior, and why it matches texture and structure, not just brightness.

fig-nlmeans-patches
Figure 10.2.1. Non-local means: compare patches, not pixels. The pixel being denoised sits at the center of a small reference patch (highlighted); several other patches scattered across the image (a repeated texture, another instance of the same structure) match it closely, each carrying a similarity weight $w(p,q)=\exp(-d^2(p,q)/h^2)$ computed from the whole patch but spent on the patch's center pixel. NL-means averages those centers, pooling many independent noisy measurements of the same underlying value. The matches need not be nearby: the search is non-local, any patch may vote, which is exactly why self-similarity is such a strong prior.
fig-nlmeans-demo
Figure 10.2.2. Patch-similarity weights. Click any pixel in the noisy image and the middle panel lights up every other pixel whose surrounding patch resembles the clicked one: bright means a close match, and a close match means that pixel gets averaged in. The point the map makes is that the bright pixels are scattered, not just clustered around the click: NL-means pools matches from across the search window, the non-local idea in one picture. The reference patch is the red box, the search window the blue box; the right panel is the full NL-means result with its PSNR. Tune the input noise, the patch radius (how much context defines "similar"), the search radius, and the decay h (larger h averages more neighbors, smoother, but it starts blurring real differences).

The thing to hold onto is which pixel each weight delivers. The weight is computed from the whole patch, but what we average in is only the center value $I(q)$: the patch determines the weight, and the center supplies the sample. Pooling sufficiently similar samples can reduce noise while retaining their shared structure. The analogy is frame averaging: instead of seeking copies across frames, non-local means seeks repeated structure within one image. The analogy is imperfect because noisy matching affects the weights and overlapping patches share samples. The catch is plain. The matches are approximate, not exact repeats, so the cancellation is imperfect, and a unique structure (a one-off blemish, a lone corner) has few partners and denoises least.