Non-Local Means

Every digital photo carries noise — tiny random fluctuations in brightness added by the camera sensor. The classic remedy is to blur: average a pixel with its immediate neighbors and the random spikes cancel out. The trouble is that edges and fine textures blur right along with the noise.

Non-local means (NLM), introduced by Antoni Buades, Bartomeu Coll, and Jean-Michel Morel in 2005, flips the logic. Instead of asking "who are my neighbors?", each pixel asks "which other pixels in the whole image look like me?" It then averages their values, weighted by how closely their surrounding patches match.

The key insight is that natural images are full of repeated texture: a patch of sky here, a patch of sky there; a brick here, the same brick three meters left. Noise is random, so it differs across repetitions. The true signal is consistent, so it survives the average. Blur smears across space; non-local means smears across similarity — and that makes all the difference.

The canvas below shows a synthetic image — geometric shapes with clean edges and uniform regions. Click Add noise to corrupt it with Gaussian grain, then click Denoise (NLM) to watch the algorithm sweep through every pixel, find similar patches anywhere in the image, and vote the grain away.

<!-- {{c_html_comment}} -->
<p class="hint">{{hint_para}}</p>
<div class="canvas-wrap">
  <canvas id="cnv" width="200" height="200"></canvas>
</div>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="btn-noise" type="button">{{btn_noise}}</button>
  <button id="btn-denoise" type="button">{{btn_denoise}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_comment}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.canvas-wrap { display: inline-block; border: 1px solid #cdd9e3; border-radius: 6px; overflow: hidden; margin-bottom: .5rem; }
canvas { display: block; image-rendering: pixelated; width: 200px; height: 200px; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.busy { color: #775500; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-top: .3rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .5; cursor: not-allowed; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice what survives: the edges between shapes stay crisp because pixels on one side of an edge only find similar patches on the same side — they never blend across the boundary. Uniform regions recover almost perfectly because they have abundant matching patches. The price is speed: every pixel searches every other pixel, making the naive algorithm $O(n^2)$ per pixel.

The formula is compact but powerful. For a noisy image $u$, the denoised value at pixel $i$ is:

$$\hat{u}(i) = \frac{1}{C(i)} \sum_{j} w(i,j)\, u(j)$$

where the weight $w(i,j)$ measures how similar the patch around $j$ is to the patch around $i$:

$$w(i,j) = \exp\!\left(-\frac{\|P_i - P_j\|^2}{h^2}\right)$$

Here $P_i$ is the vector of pixel values in a small window around $i$, $\|\cdot\|$ is the Euclidean distance between those two patches, and $h$ is the filter parameter — roughly the expected noise level. $C(i)$ normalizes the weights to sum to one.

Three things make this elegant:

• Self-similarity: a pixel always has weight 1 for itself, so the estimate never drifts far from the observed value.
• Locality is irrelevant: $j$ can be anywhere in the image; only patch similarity decides the weight.
• One knob: increasing $h$ trusts more patches and smooths more aggressively; decreasing $h$ stays close to the noisy image.

The naive cost is $O(N^2 \cdot p^2)$ where $N$ is the number of pixels and $p$ is the patch radius. In practice the search is restricted to a search window of fixed size around each pixel, dropping cost to $O(N \cdot s^2 \cdot p^2)$ with search-window radius $s$ — still far slower than a simple blur, but fast enough for photos with modern hardware. See dimensionality reduction for how related ideas compress the search space.

The "find similar patches anywhere" idea turned out to be far more general than image denoising:

• Medical imaging: MRI and CT scans are expensive to acquire at high signal-to-noise ratio. NLM and its descendants (BM3D, deep-learning variants) let clinicians use shorter scan times without sacrificing detail, which matters enormously for patient comfort and throughput.
• Astrophotography: long-exposure sky images share the same sky background everywhere. NLM-style stacking cleans up faint nebulae that would otherwise drown in sensor noise.
• Video denoising: frames of the same scene are patches of each other displaced by motion. NLM extended to the temporal axis — searching across frames — produces remarkably clean video from noisy footage.
• Computational photography: the "multi-frame" denoising in modern smartphone cameras is a direct descendant. Your phone silently shoots several frames, aligns patches across them, and averages — NLM logic running in milliseconds.
• Texture synthesis and inpainting: once you know how to find matching patches you can copy them to fill in missing regions, powering photo-restoration tools.

The conceptual thread also runs through sequence alignment: finding similar subsequences anywhere in a long string is the string analog of finding similar patches anywhere in an image.

Non-local means is a lesson in thinking globally. The pixel you want to fix is not just a dot on a grid — it is part of a texture that likely repeats elsewhere in the same image. By finding those repetitions and letting them vote, you can strip away the random noise that corrupts each repetition individually while leaving the shared signal intact.

The price — quadratic search — is real, but it inspired two decades of faster algorithms, learned patch descriptors, and ultimately the multi-frame pipelines inside every modern camera. The next time your phone quietly takes five shots of a dimly lit room and hands you one clean photo, you are holding the practical descendant of a 2005 formula small enough to fit on a single line.