AI.Cruz - Learn AI Through Interactive Visualizations

COMPUTER VISION

Mean Shift: Non-Parametric Clustering for Segmentation

Mean shift finds cluster centres by iteratively shifting each point towards the local density maximum. No number of clusters required — bandwidth alone controls granularity.

1The Density Estimation Idea

Mean shift is a mode-finding algorithm. Every clustering algorithm needs a notion of what a "cluster" is. K-Means defines clusters as regions around centroids; DBSCAN defines them as high-density regions. Mean shift defines clusters as the modes (peaks) of an underlying probability density function. Given a set of points, mean shift estimates where the data is densest, then assigns each point to the nearest density peak.

The key insight: instead of assuming a fixed number of clusters (K-Means) or a fixed density threshold (DBSCAN), mean shift lets the data itself reveal how many clusters exist. You only set one hyperparameter — the bandwidth h — which controls the size of the neighbourhood kernel. Large bandwidth: fewer, bigger clusters. Small bandwidth: many fine-grained clusters.

Flat (Circular) Kernel
k(x) = 1 if ||x|| <= r, else 0. All neighbours within radius r get equal weight. Simple but creates sharp cluster boundaries.

Gaussian (RBF) Kernel
k(x) = exp(-(x/2σ²)). Points near the centre get high weight; distant points get exponentially less. Produces smoother convergence and is the default choice in practice.

Bandwidth h
The single hyperparameter. Controls the size of the neighbourhood. Too large: everything merges into one cluster. Too small: each point becomes its own cluster.

2The Mean Shift Algorithm

The algorithm iterates until convergence. For each data point x, compute the weighted mean of all neighbours using the kernel, then shift x to that mean. Repeat until x stops moving. Formally, the shift vector is: m(x) = [∑ k(x−xᵢ) xᵢ] / [∑ k(x−xᵢ)] − x. Each update moves x towards the region of highest local density. After convergence, all points that converged to the same mode belong to the same cluster.

Step-by-step: (1) Pick any point x. (2) Compute the kernel-weighted mean of all points within bandwidth h. (3) Shift x to that mean. (4) Repeat until convergence — x has found a mode. (5) Repeat for all points. (6) Points that converged to the same location belong to the same cluster. The algorithm is deterministic — no random initialisation, always the same result.

3Convergence and Modes

Mean shift is guaranteed to converge for kernel functions satisfying a mild smoothness condition (Gaussian always qualifies). Each point's trajectory traces a hill-climbing path through the density landscape until it reaches a local maximum — a mode. The number of modes found depends entirely on bandwidth: with bandwidth=60 in colour space, an image might converge to 6 distinct colour modes; with bandwidth=130, only 2.

Advantages

✓ No need to specify K — number of clusters discovered automatically
✓ Can find non-spherical, arbitrarily shaped clusters
✓ Deterministic — no random initialisation issues
✓ Embarrassingly parallel — each point's shift is independent

Limitations

✗ O(n²) per iteration — slow on large datasets
✗ Bandwidth selection is non-trivial in high dimensions
✗ Not suitable when clusters have very different densities

4Mean Shift vs K-Means and DBSCAN

K-Means
Requires K. Assumes spherical clusters. Fast O(nKd). Sensitive to initialisation. Good when you know K and clusters are roughly equal in size.

DBSCAN
No K needed. Finds arbitrary shapes. Marks outliers explicitly. Requires epsilon and min_samples. Struggles with varying density clusters.

Mean Shift
No K needed. Finds arbitrary shapes. No outlier concept — every point converges to a mode. One parameter (bandwidth). Dominant in colour-based image segmentation.

K-Means Clustering →DBSCAN →Semantic Segmentation →

Mean shift in 1D: discover modes of a bimodal distribution

import numpy as np

def gaussian_kernel(dist, bandwidth):
    return np.exp(-0.5 * (dist / bandwidth) ** 2)

def mean_shift_1d(points, bandwidth=0.5, max_iter=50, tol=1e-4):
    centroids = points.copy().astype(float)
    for _ in range(max_iter):
        new_centroids = np.zeros_like(centroids)
        for i, c in enumerate(centroids):
            weights = gaussian_kernel(np.abs(points - c), bandwidth)
            new_centroids[i] = np.sum(weights * points) / np.sum(weights)
        if np.max(np.abs(new_centroids - centroids)) < tol:
            break
        centroids = new_centroids
    return centroids

np.random.seed(42)
cluster1 = np.random.normal(2.0, 0.3, 10)
cluster2 = np.random.normal(6.0, 0.3, 10)
points = np.concatenate([cluster1, cluster2])

final_positions = mean_shift_1d(points, bandwidth=0.8)
rounded = np.round(final_positions, 1)
modes = sorted(set(rounded.tolist()))

print("Points (first 5 from each cluster):")
print("  Cluster 1:", [round(x, 2) for x in cluster1[:5]])
print("  Cluster 2:", [round(x, 2) for x in cluster2[:5]])
print()
print("After mean shift (bandwidth=0.8):")
print("  Final positions (first 5):", [round(x, 2) for x in final_positions[:5]])
print("  Discovered modes:", modes)
print()
print("Clusters specified: 0   (bandwidth controls granularity)")
print("Modes found:", len(modes))
print()
# Show effect of different bandwidths
for bw in [0.3, 0.8, 2.5]:
    fp = mean_shift_1d(points, bandwidth=bw)
    m = sorted(set(np.round(fp, 1).tolist()))
    print("bandwidth=" + str(bw) + "  ->  " + str(len(m)) + " modes: " + str(m))