Introduction

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.

Watch the Grain Melt

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.

<!-- Main UI – hint paragraph, canvas, status line, action buttons -->
<p class="hint">Each pixel is denoised by averaging other pixels whose surrounding patch looks similar — anywhere in the image, not just next door. Add noise first, then run NLM to watch grain disappear while edges stay sharp.</p>
<div class="canvas-wrap">
  <canvas id="cnv" width="200" height="200"></canvas>
</div>
<div class="status" id="status">Draw a clean image and add noise to begin.</div>
<div class="btns">
  <button id="btn-noise" type="button">Add noise</button>
  <button id="btn-denoise" type="button">Denoise (NLM)</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Layout and visual styling for the NLM demo */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* Canvas dimensions: 200×200 pixels (scaled up 1× in CSS) */
const W = 200, H = 200;
const cnv = document.getElementById('cnv');
const ctx = cnv.getContext('2d');

/* Image state: clean | noisy | denoised */
let cleanPixels = null;
let currentPixels = null;
let state = 'clean'; // clean | noisy | denoised

/* Draw synthetic scene with geometric shapes and uniform regions */
function drawScene() {
  ctx.fillStyle = '#e8eef3';
  ctx.fillRect(0, 0, W, H);
  /* Blue rectangle — top-left */
  ctx.fillStyle = '#1d6fa3';
  ctx.fillRect(20, 20, 70, 70);
  /* Red rectangle — top-right */
  ctx.fillStyle = '#e63946';
  ctx.fillRect(110, 30, 70, 70);
  /* Green circle — bottom-left */
  ctx.fillStyle = '#2a9d45';
  ctx.beginPath();
  ctx.arc(70, 150, 35, 0, Math.PI * 2);
  ctx.fill();
  /* Orange diamond — bottom-right */
  ctx.fillStyle = '#f4a261';
  ctx.beginPath();
  ctx.moveTo(150, 110);
  ctx.lineTo(185, 150);
  ctx.lineTo(150, 190);
  ctx.lineTo(115, 150);
  ctx.closePath();
  ctx.fill();
}

/* Read current canvas pixels into a Uint8ClampedArray */
function snapshot() {
  const d = ctx.getImageData(0, 0, W, H);
  return new Uint8ClampedArray(d.data);
}

function putPixels(arr) {
  const d = ctx.createImageData(W, H);
  d.data.set(arr);
  ctx.putImageData(d, 0, 0);
}

/* Add Gaussian noise using the Box-Muller transform */
function addGaussianNoise(src, sigma) {
  const out = new Uint8ClampedArray(src);
  for (let i = 0; i < out.length; i += 4) {
    /* Box-Muller transform produces a standard-normal sample z */
    const u1 = Math.random() || 1e-10;
    const u2 = Math.random();
    const z = Math.sqrt(-2 * Math.log(u1)) * Math.cos(2 * Math.PI * u2);
    const n = Math.round(z * sigma);
    out[i]     = Math.max(0, Math.min(255, out[i]     + n));
    out[i + 1] = Math.max(0, Math.min(255, out[i + 1] + n));
    out[i + 2] = Math.max(0, Math.min(255, out[i + 2] + n));
    /* Alpha channel stays at 255 (fully opaque) */
  }
  return out;
}

/* Non-local means: for each pixel p, accumulate weighted average over all q in the search window. Weight = exp(-patch_distance^2 / h^2). */
function nlmDenoise(src, h, patchR, searchR) {
  const h2 = h * h;
  const out = new Uint8ClampedArray(src.length);

  /* Outer loop over every target pixel p */
  for (let py = 0; py < H; py++) {
    for (let px = 0; px < W; px++) {
      let wR = 0, wG = 0, wB = 0, wSum = 0;
      /* Inner loop over candidate pixels q within the search window */
      for (let qy = Math.max(0, py - searchR); qy <= Math.min(H - 1, py + searchR); qy++) {
        for (let qx = Math.max(0, px - searchR); qx <= Math.min(W - 1, px + searchR); qx++) {
          /* Squared Euclidean distance between patch around p and patch around q (all 3 channels) */
          let dist2 = 0;
          for (let dy = -patchR; dy <= patchR; dy++) {
            for (let dx = -patchR; dx <= patchR; dx++) {
              const sy = Math.min(H - 1, Math.max(0, py + dy));
              const sx = Math.min(W - 1, Math.max(0, px + dx));
              const ty = Math.min(H - 1, Math.max(0, qy + dy));
              const tx = Math.min(W - 1, Math.max(0, qx + dx));
              const ip = (sy * W + sx) * 4;
              const iq = (ty * W + tx) * 4;
              const dr = src[ip] - src[iq];
              const dg = src[ip + 1] - src[iq + 1];
              const db = src[ip + 2] - src[iq + 2];
              dist2 += dr * dr + dg * dg + db * db;
            }
          }
          /* Gaussian weight decays with patch distance */
          const w = Math.exp(-dist2 / h2);
          const qi = (qy * W + qx) * 4;
          wR += w * src[qi];
          wG += w * src[qi + 1];
          wB += w * src[qi + 2];
          wSum += w;
        }
      }
      /* Weighted average normalized by total weight */
      const oi = (py * W + px) * 4;
      out[oi]     = Math.round(wR / wSum);
      out[oi + 1] = Math.round(wG / wSum);
      out[oi + 2] = Math.round(wB / wSum);
      out[oi + 3] = 255;
    }
  }
  return out;
}

/* Initialize — draw scene and take the clean snapshot */
drawScene();
cleanPixels = snapshot();
currentPixels = new Uint8ClampedArray(cleanPixels);
setStatus('Draw a clean image and add noise to begin.', '');

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

function setButtons(busy) {
  document.getElementById('btn-noise').disabled = busy;
  document.getElementById('btn-denoise').disabled = busy;
  document.getElementById('btn-reset').disabled = busy;
}

document.getElementById('btn-noise').addEventListener('click', function () {
  if (state === 'denoised') {
    currentPixels = new Uint8ClampedArray(cleanPixels);
    putPixels(currentPixels);
  }
  /* Standard deviation of Gaussian noise (higher = more grain) */
  currentPixels = addGaussianNoise(currentPixels, 35);
  putPixels(currentPixels);
  state = 'noisy';
  setStatus('Noise added. Click Denoise (NLM) to clean it.', 'bad');
});

document.getElementById('btn-denoise').addEventListener('click', function () {
  if (state !== 'noisy') {
    setStatus('Add noise first, then denoise.', 'bad');
    return;
  }
  setStatus('Running NLM — this may take a moment...', 'busy');
  setButtons(true);
  /* Yield to the browser so the status text renders before the heavy computation */
  setTimeout(function () {
    /* NLM params: h=3000 (controls smoothing), patchR=2 (patch half-size), searchR=15 (search window half-size) */
    const denoised = nlmDenoise(currentPixels, 3000, 2, 15);
    currentPixels = denoised;
    putPixels(denoised);
    state = 'denoised';
    setStatus('Denoised! Edges sharp, grain gone.', 'ok');
    setButtons(false);
  }, 30);
});

document.getElementById('btn-reset').addEventListener('click', function () {
  drawScene();
  cleanPixels = snapshot();
  currentPixels = new Uint8ClampedArray(cleanPixels);
  state = 'clean';
  setStatus('Draw a clean image and add noise to begin.', '');
});
Result
Console

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(n2)O(n^2) per pixel.

The Math Behind It

The formula is compact but powerful. For a noisy image uu, the denoised value at pixel ii is:

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

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

w(i,j)=exp⁡ ⁣(−∥Pi−Pj∥2h2)w(i,j) = \exp\!\left(-\frac{\|P_i - P_j\|^2}{h^2}\right)

Here PiP_i is the vector of pixel values in a small window around ii, ∥⋅∥\|\cdot\| is the Euclidean distance between those two patches, and hh is the filter parameter — roughly the expected noise level. C(i)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: jj can be anywhere in the image; only patch similarity decides the weight.
  • One knob: increasing hh trusts more patches and smooths more aggressively; decreasing hh stays close to the noisy image.

The naive cost is O(N2⋅p2)O(N^2 \cdot p^2) where NN is the number of pixels and pp 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⋅s2⋅p2)O(N \cdot s^2 \cdot p^2) with search-window radius ss — 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/non-local-means/Content licensed under CC BY-NC 4.0.