Introduction

Every photograph is a cloud of colored dots. Somewhere in that cloud, pixels group naturally: the blue sky clusters together, the green grass forms its own crowd, the red barn stands apart. Segmentation is the task of finding those groups without being told how many there are.

Mean-shift — introduced for image analysis by Dorin Comaniciu and Peter Meer in 2002 — solves segmentation the way a ball rolls downhill in reverse. Instead of falling to a valley, each pixel climbs toward the nearest density peak in color space. Pixels that share the same peak end up in the same segment.

The method needs no preset number of clusters. It estimates the local density at each point using a kernel (typically a Gaussian bell), then shifts each point toward the center of mass of its neighborhood. After enough steps, nearby points converge to the same mode. The result is a posterized image: regions of uniform color, as if the palette had been reduced to its most popular shades.

This is closely related to non-convex optimization: the algorithm climbs a surface riddled with local maxima, and different starting points may reach different peaks. Understanding which peaks it finds — and how many — is the heart of the problem.

Try It

The demo below generates a synthetic set of color patches drawn from a handful of cluster centers. Mean-shift then climbs from each patch toward the nearest density peak and repaints everything at that peak color — posterizing the palette.

<!-- Mean-shift segmentation demo — two canvas panels (original vs posterized) -->
<p class="hint">Mean-shift climbs toward density peaks in color space. Each color patch is assigned the color of its nearest peak — <b>posterizing</b> the image. Wider bandwidth merges peaks; narrower bandwidth preserves more detail.</p>
<div class="controls">
  <label for="bw-slider">Bandwidth: <strong id="bw-val">40</strong></label>
  <input type="range" id="bw-slider" min="5" max="120" value="40" step="1">
  <button id="btn-run" type="button">Run Mean-Shift</button>
  <button id="btn-reset" type="button" class="ghost">New Image</button>
</div>
<div class="canvases">
  <div class="canvas-box">
    <div class="canvas-label">Original</div>
    <canvas id="canvas-orig" width="240" height="180"></canvas>
  </div>
  <div class="canvas-box">
    <div class="canvas-label">Posterized</div>
    <canvas id="canvas-out" width="240" height="180"></canvas>
  </div>
</div>
<div class="status" id="status">Ready — click Run Mean-Shift.</div>

/* Layout and colors for the mean-shift 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; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .5rem; margin-bottom: .7rem; }
.controls label { font-size: .9rem; white-space: nowrap; }
#bw-slider { flex: 1; min-width: 120px; max-width: 240px; }
.canvases { display: flex; gap: 12px; flex-wrap: wrap; margin-bottom: .6rem; }
.canvas-box { display: flex; flex-direction: column; align-items: center; gap: 4px; }
.canvas-label { font-size: .78rem; color: #555; font-weight: 600; text-transform: uppercase; letter-spacing: .04em; }
canvas { border: 1px solid #cdd9e3; border-radius: 6px; display: block; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; padding: .1rem 0; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Mean-shift segmentation: repeatedly shift each color point toward the weighted
// mean of its neighbors within bandwidth h until convergence (a local density mode).

const W = 240, H = 180;
// Ground-truth cluster centers in RGB space (not exposed to the algorithm)
const CLUSTER_COLORS = [
  [220, 60, 60],   // warm red
  [60, 160, 220],  // sky blue
  [80, 180, 80],   // leaf green
  [230, 180, 40],  // sunflower yellow
  [180, 80, 200],  // violet
];
const NOISE_STD = 22; // Gaussian noise std-dev added to each patch to simulate real variation

// Array of synthetic color patches (each is one cell in the grid)
let origPixels = [];

function randGauss() {
  // Box-Muller transform — converts two uniform samples to one standard normal
  let u = 0, v = 0;
  while (u === 0) u = Math.random();
  while (v === 0) v = Math.random();
  return Math.sqrt(-2 * Math.log(u)) * Math.cos(2 * Math.PI * v);
}

function generateImage(ctx) {
  // Fill the canvas with random color patches drawn from the cluster centers
  origPixels = [];
  const rows = Math.ceil(H / 12), cols = Math.ceil(W / 12);
  for (let gy = 0; gy < rows; gy++) {
    for (let gx = 0; gx < cols; gx++) {
      const ci = Math.floor(Math.random() * CLUSTER_COLORS.length);
      const [br, bg, bb] = CLUSTER_COLORS[ci];
      const px = gx * 12, py = gy * 12;
      const bw = Math.min(12, W - px), bh = Math.min(12, H - py);
      const r = Math.max(0, Math.min(255, Math.round(br + randGauss() * NOISE_STD)));
      const g = Math.max(0, Math.min(255, Math.round(bg + randGauss() * NOISE_STD)));
      const b = Math.max(0, Math.min(255, Math.round(bb + randGauss() * NOISE_STD)));
      ctx.fillStyle = `rgb(${r},${g},${b})`;
      ctx.fillRect(px, py, bw, bh);
      origPixels.push({ r, g, b, px, py, bw, bh });
    }
  }
}

// Epanechnikov kernel — linear falloff, zero outside bandwidth h
function epanechnikovWeight(distSq, hSq) {
  const u = distSq / hSq;
  return u <= 1 ? (1 - u) : 0;
}

// One mean-shift step: shift (r,g,b) toward the kernel-weighted mean of all points
function meanShiftPoint(r, g, b, pixels, h) {
  const hSq = h * h;
  let wr = 0, wg = 0, wb = 0, wsum = 0;
  for (const p of pixels) {
    const dSq = (p.r - r) ** 2 + (p.g - g) ** 2 + (p.b - b) ** 2;
    const w = epanechnikovWeight(dSq, hSq);
    if (w > 0) { wr += w * p.r; wg += w * p.g; wb += w * p.b; wsum += w; }
  }
  if (wsum === 0) return { r, g, b };
  return { r: wr / wsum, g: wg / wsum, b: wb / wsum };
}

// Iterate mean-shift steps until the point stops moving (convergence to a mode)
function findMode(r, g, b, pixels, h, maxIter) {
  let cr = r, cg = g, cb = b;
  for (let i = 0; i < maxIter; i++) {
    const next = meanShiftPoint(cr, cg, cb, pixels, h);
    const dSq = (next.r - cr) ** 2 + (next.g - cg) ** 2 + (next.b - cb) ** 2;
    cr = next.r; cg = next.g; cb = next.b;
    if (dSq < 0.25) break; // Converged when movement is less than 0.5 units in color space
  }
  return { r: Math.round(cr), g: Math.round(cg), b: Math.round(cb) };
}

function runMeanShift(h) {
  const maxIter = 40;
  const modes = origPixels.map(p => findMode(p.r, p.g, p.b, origPixels, h, maxIter));
  // Merge modes that are within half a bandwidth of each other into one segment
  const snapH = h * 0.5;
  const snapHSq = snapH * snapH;
  const merged = modes.map(m => {
    const dSq = (m.r - m.r) ** 2; // self-comparison placeholder (always 0) — real merging happens in the seed loop
    return m;
  });
  // Collect unique mode seeds — any two modes within snapH of each other share a segment
  const seeds = [];
  for (const m of merged) {
    let found = false;
    for (const s of seeds) {
      if ((m.r - s.r) ** 2 + (m.g - s.g) ** 2 + (m.b - s.b) ** 2 < snapHSq) {
        found = true; break;
      }
    }
    if (!found) seeds.push({ r: m.r, g: m.g, b: m.b });
  }
  return { modes, numSegs: seeds.length };
}

function drawOutput(outCtx, modes) {
  // Paint each patch with the color of its converged mode (posterized output)
  origPixels.forEach((p, i) => {
    const m = modes[i];
    outCtx.fillStyle = `rgb(${m.r},${m.g},${m.b})`;
    outCtx.fillRect(p.px, p.py, p.bw, p.bh);
  });
}

const origCanvas = document.getElementById('canvas-orig');
const outCanvas = document.getElementById('canvas-out');
const origCtx = origCanvas.getContext('2d');
const outCtx = outCanvas.getContext('2d');
const slider = document.getElementById('bw-slider');
const bwVal = document.getElementById('bw-val');
const statusEl = document.getElementById('status');
const btnRun = document.getElementById('btn-run');
const btnReset = document.getElementById('btn-reset');

function setStatus(msg, cls) {
  statusEl.textContent = msg;
  statusEl.className = 'status ' + (cls || '');
}

function init() {
  // Initialize with a fresh random image and clear the output canvas
  outCtx.clearRect(0, 0, W, H);
  generateImage(origCtx);
  setStatus('Ready — click Run Mean-Shift.', '');
}

slider.addEventListener('input', () => { bwVal.textContent = slider.value; });

btnRun.addEventListener('click', () => {
  const h = parseInt(slider.value, 10);
  btnRun.disabled = true;
  setStatus('Running mean-shift, please wait…', 'info');
  // Use setTimeout so the browser renders the 'running' status before the heavy loop
  setTimeout(() => {
    try {
      const { modes, numSegs } = runMeanShift(h);
      drawOutput(outCtx, modes);
      setStatus(i18nFmt('Done — %n% color segment(s) found.', { n: numSegs }), 'ok');
    } catch (e) {
      setStatus('An error occurred. Try a different bandwidth.', 'bad');
    }
    btnRun.disabled = false;
  }, 20);
});

btnReset.addEventListener('click', init);

init();
Result
Console

Drag the bandwidth slider to change the radius of the kernel. A narrow bandwidth finds many small peaks (many segments). A wide bandwidth merges peaks together until the whole palette collapses into one or two dominant modes. Notice that no cluster count is set in advance: the number of segments emerges entirely from the data and the bandwidth you choose.

The Real Complexity

Mean-shift is elegantly simple to state, but its computational and theoretical properties are nuanced.

  • Cost per step. Each pixel must compare itself to every other pixel inside its kernel window. With nn pixels this is O(n2)O(n^{2}) per iteration, which is too slow for large images naively. In practice, spatial data structures such as kk-d trees or ball trees reduce the neighborhood lookup to roughly O(nlog⁡n)O(n \log n).
  • Convergence is guaranteed — to a local mode. Fukunaga and Hostetler proved in 1975 that the basic mean-shift iteration always converges, but only to a local maximum of the density. Different initializations can reach different peaks, so the final segmentation depends on where you start (i.e., on the pixel positions and colors).
  • The bandwidth hh is everything. The kernel radius hh controls the number of modes the algorithm finds. Too small and noise becomes its own cluster; too large and semantically different regions merge. Choosing hh well is an unsolved problem in general — cross-validation or pilot estimation are used in practice.
  • No NP-completeness, but no optimality either. Mean-shift does not solve an NP-hard problem; it is a heuristic gradient ascent on a smooth density surface. Unlike non-convex optimization in general, the surface here is always smooth (as long as the kernel is smooth), so convergence is assured — just not to the global maximum.
  • Number of segments is data-driven. The algorithm produces as many segments as there are modes. This is a strength (no guessing required) and a weakness (you cannot ask for exactly kk clusters without an extra step, unlike k-means).

Where It Matters

"Find natural groups without knowing how many there are" is a recurring need across computer vision and beyond, and mean-shift is one of the cleanest answers:

  • Object tracking in video: mean-shift tracks a color histogram window frame by frame (the CAMSHIFT extension). It is real-time and robust to partial occlusion.
  • Medical image analysis: MRI and CT scans contain tissues whose boundaries are not known beforehand. Mean-shift segments them without a fixed class count.
  • Background subtraction: pixels whose color drifts away from the background mode are flagged as foreground — a direct application of mode detection.
  • Texture and feature clustering: any feature descriptor (not just color) can be embedded in a feature space and clustered the same way, making mean-shift a general unsupervised learning primitive.
  • Pre-processing for object detection: over-segmenting an image into coherent color blobs (superpixels) reduces the search space for later detection steps.

The key insight mean-shift teaches: when you do not know the structure of your data in advance, let the data's own density tell you where the clusters are — a philosophy shared by Bayesian inference and kernel density estimation alike.

Conclusion

Mean-shift turns image segmentation into a landscape exploration problem: every pixel is a hiker that climbs toward the nearest color peak, and all hikers reaching the same summit belong to the same segment. No map of how many peaks to expect is needed — the terrain speaks for itself.

The price is sensitivity to the bandwidth parameter and quadratic cost when implemented naively. The reward is a method grounded in nonparametric statistics, proven to converge, and powerful enough to track objects in video and delineate tissues in MRI scans.

The next time you look at a photograph and instinctively group it into sky, ground, and subject, you are running a version of mean-shift in your head — and now you know the algorithm that does the same with arithmetic.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/mean-shift-segmentation/Content licensed under CC BY-NC 4.0.