Wolfram Language & System Documentation Center

MeanShift

MeanShift[list,d]

replaces each element in list by the mean of the values of all elements that differ by less than d.

MeanShift[list,d,{p₁,p₂,…}]

returns the list where only the specified parts p_i are replaced with mean-shifted values.

MeanShift[image,…]

mean shift of the pixel values in image.

Details and Options

MeanShift is also known as mode seeking and is typically used to smooth data arrays and images.
MeanShift preserves the ordering of the input elements.
In MeanShift[image,d,parts], parts can be a marker image or a list of {row,column} positions.
The following options can be given:

DistanceFunction	EuclideanDistance	distance metric function
MaxIterations	1	maximum number of iterations to perform
Tolerance	0	allowed tolerance to assume convergence
Weights	Automatic	weights to use for computing the mean

With Tolerance->t, mean-shift iterations stop if no point changes by more than t.
By default, unit weights are used. Using Weights->f, function f applied to rescaled distances between elements is used to compute and return a weighted mean of the values. Distances between 0 and d are rescaled to be in the range from 0 and 1.
Typical settings for Weights include:

	UnitStep	unit weights (default)
	UnitTriangle	linearly decreasing weight
	"Gaussian"	weights based on a Gaussian window with sigma
	{"Gaussian",σ}	Gaussian window with sigma σ

Common settings for the DistanceFunction option are:

	ManhattanDistance	Manhattan or "city block" distance
	EuclideanDistance	Euclidean distance
	SquaredEuclideanDistance	squared Euclidean distance
	NormalizedSquaredEuclideanDistance	normalized squared Euclidean distance
	CosineDistance	angular cosine distance
	CorrelationDistance	correlation coefficient distance
	f	use an arbitrary function f

Examples

open all close all

Basic Examples (3)

Mean shift of a list of integers:

Wolfram Language code: MeanShift[{0, 10, 1, 11}, 1]

Mean shift of a list of vectors:

Wolfram Language code: MeanShift[{{0, 1}, {2, 3}, {10 , 11}, {12, 13}}, 3]

Mean shift of an image's pixels after multiple iterations:

Wolfram Language code: MeanShift[[image], .15, MaxIterations -> 15]

Scope (4)

Remove uniform noise from a dataset:

Wolfram Language code: data = Table[1 + RandomReal[{-0.1, 0.1}], {10}]

Wolfram Language code: MeanShift[data, 0.1, MaxIterations -> 10]

Mean-shift algorithm applied to symbolic expressions:

Wolfram Language code: MeanShift[{1, 2, a + 5, a + 6}, 1]

Mean-shift algorithm applied to a subset of the points:

Wolfram Language code: MeanShift[{10, 20, 30, 45, 50}, 10, {1, 3}]

Precision of the input is preserved:

Wolfram Language code: MeanShift[{1.0000000000000000000, 2.0000000000000000000, 3.0000000000000000000, 4.0000000000000000000}, 2]

Options (8)

DistanceFunction (3)

By default, EuclideanDistance is used:

Wolfram Language code: MeanShift[{0, 1, 10, 11}, 2]

Wolfram Language code: MeanShift[{{0, 0}, {1, 1}, {0, 10}, {0, 11}}, 1]

Specify the distance function:

Wolfram Language code: MeanShift[{{0, 0}, {1, 1}, {0, 10}, {0, 11}}, 1, DistanceFunction -> ChessboardDistance]

Use a custom distance function:

Wolfram Language code: MeanShift[{{0, 0}, {1, 1}, {0, 10}, {0, 11}}, 1, DistanceFunction -> (Min[#1 - #2]&)]

MaxIterations (2)

By default, only one iteration of mean shift is applied to input:

Wolfram Language code: MeanShift[{1, 2, 3, 4, 5}, 1]

Use MaxIterations to specify the number of iterations:

Wolfram Language code: MeanShift[{1, 2, 3, 4, 5}, 1, MaxIterations -> 5]

Use MaxIterations->Infinity to run until convergence:

Wolfram Language code: MeanShift[{1, 2, 3, 4, 5}, 1, MaxIterations -> Infinity]

Use MaxIterations to iteratively smooth data:

Wolfram Language code:

BlockRandom[SeedRandom[0];
	data = Table[1. + RandomReal[{-0.1, 0.1}], {1000}]];
{Table[ListLinePlot[{data, MeanShift[data, 0.05, MaxIterations -> iter]}], 
{iter, {1, 5, 10}}]}//Grid

Tolerance (1)

By default, zero tolerance is used:

Wolfram Language code: MeanShift[{1, 2, 3, 4, 5}, 1, MaxIterations -> Infinity]

Specify the accepted tolerance:

Wolfram Language code: MeanShift[{1, 2, 3, 4, 5}, 1, MaxIterations -> Infinity, Tolerance -> .25]

Weights (2)

By default, uniform weights are used:

Wolfram Language code: MeanShift[{0, 1, 3}, 2]

Weigh neighbors linearly, based on their distance from each sample:

Wolfram Language code: MeanShift[{0, 1, 3}, 2, Weights -> UnitTriangle]

Weigh neighbors exponentially, based on their squared distance from each sample:

Wolfram Language code: MeanShift[{0, 1, 3}, 2, Weights -> {"Gaussian", 1 / 2}]

By "Gaussian" weights for color segmentation:

Wolfram Language code: i = [image];

Wolfram Language code: MeanShift[i, .3, MaxIterations -> Infinity, Weights -> "Gaussian"]

With default uniform weights:

Wolfram Language code: MeanShift[i, .3, MaxIterations -> Infinity]

Applications (9)

Smoothing (2)

Find large-scale features in a noisy dataset:

Wolfram Language code: data = ({Sin[#], Cos[#]} + RandomReal[{-0.1, 0.1}, 2])& /@ RandomReal[{0, 2 Pi}, 2000];

Wolfram Language code: ListPlot[data]

Wolfram Language code: ListPlot[MeanShift[data, 0.1, MaxIterations -> 3]]

Image smoothing using mean shift of 5D features in the joint spatial-range domain:

Wolfram Language code:

img = [image];
{w, h} = ImageDimensions[img];

Use LABColor values, suitable for computing color distances:

Wolfram Language code: pix = Flatten[ImageData[ColorConvert[img, "LAB"]], 1];

Compute spatial location features normalized to the range 0 to 1:

Wolfram Language code: pos = Flatten[N@Array[{#1, #2}&, {h, w}], 1];

Construct 5D features from color and location of pixels:

Wolfram Language code: data = Join[pix, pos / Max[{h, w}], 2];

Perform one iteration of mean-shift filtering using "Gaussian" weights and EuclideanDistance, which is equivalent to multiplying Gaussian-weighted spatial and range features:

Wolfram Language code: ms = MeanShift[data, 0.1, Weights -> "Gaussian"];

Create the output image using the filtered color values:

Wolfram Language code: Image[ArrayReshape[ms[[All, ;; 3]], {h, w, 3}], ColorSpace -> "LAB"]

Perform 10 iterations:

Wolfram Language code: AbsoluteTiming[ms = MeanShift[data, 0.1, Weights -> "Gaussian", MaxIterations -> 10];]

Wolfram Language code: Image[ArrayReshape[ms[[All, ;; 3]], {h, w, 3}], ColorSpace -> "LAB"]

Mean-Shift Displacement (2)

Compute a 1D mean-shift vector:

Wolfram Language code:

list = {1, 2, 3, 4};
ms = MeanShift[list, 1]

Wolfram Language code: msvector = ms - list

Generate unimodal 2D data:

Wolfram Language code:

BlockRandom[
	SeedRandom[0];
	list = Join[RandomVariate[BinormalDistribution[{0, 0}, {1, 1 / 2}, 0], 2000], {{2., -1.}}]];

Wolfram Language code: Histogram3D[list]

Compute the trajectory of a point as it iteratively ascends toward the mode:

Wolfram Language code:

index = {Length[list]};
radius = 1 / 2;
pos = Flatten[
	FixedPointList[
	Part[MeanShift[ReplacePart[list, Thread[index -> #]], radius, index], index]&, 
	Part[list, index], SameTest -> (Max@Abs[#1 - #2] < 10 ^ -10&)
	], 1];

Visualize the norm and direction of the successive mean-shift vectors:

Wolfram Language code: msvectors = Differences[pos];

Wolfram Language code:

ListLinePlot[Norm /@ msvectors, PlotRange -> All, Filling -> Axis, FillingStyle -> Automatic, ColorFunctionScaling -> False, ColorFunction -> Function[{x, y}, Hue[Rescale[ArcTan[Sequence@@msvectors[[x]]], {-Pi, Pi}]]]]

Visualize the ascent:

Wolfram Language code:

pdf = Function[{x, y}, Evaluate[PDF[SmoothKernelDistribution[list], {x, y}]]];
point3D[{x_, y_}] := Point[{x, y, pdf[x, y] + .005}];

Wolfram Language code:

Show[Plot3D[pdf[x, y], {x, -4, 4}, {y, -2, 2}, PlotRange -> All, ImageSize -> 300], Graphics3D[{Red, PointSize[Medium], point3D /@ pos}]]

Find Modes of Estimated Distribution (1)

Get sample data from some distribution with three modes: 0, 2, and 4:

Wolfram Language code:

dist = MixtureDistribution[{1, 1, 2}, {NormalDistribution[0, 1 / 4], NormalDistribution[2, 1 / 3], NormalDistribution[4, 1 / 2]}];

Wolfram Language code:

n = 10000;
BlockRandom[SeedRandom[0];data = RandomVariate[dist, n]];

Wolfram Language code: Show[Histogram[data, Automatic, "PDF", PlotRange -> {{-1, 6}, {0, .5}}], Plot[PDF[dist, x], {x, -1, 6}]]

Apply mean shift until convergence for samples that tessellates the data:

Wolfram Language code: idx = Flatten[Position[data, #, 1, 1]& /@ Quantile[data, Range[1, n, n / 100] / n]];

Wolfram Language code:

radius = 0.25;
ms = Part[MeanShift[data, radius, idx, MaxIterations -> ∞, Weights -> "Gaussian", Tolerance -> 10 ^ -10], idx];

Prune points that are not local maxima of the underlying PDF by restarting mean shift from a perturbed position:

Wolfram Language code: perturbed = ReplacePart[data, Thread[idx -> ms + radius * RandomChoice[{-1, 1}, Length[idx]]]];

Wolfram Language code:

msperturb = Part[MeanShift[perturbed, radius, idx, MaxIterations -> ∞, Weights -> "Gaussian", Tolerance -> 10 ^ -10], idx];

Wolfram Language code: peaks = Extract[ms, Position[ms - msperturb, x_ /; Abs[x] < 10 ^ -2]]

Find modes by gathering the nearby peaks:

Wolfram Language code: modes = Mean /@ Gather[peaks, Abs[#1 - #2] ≤ radius&]

Wolfram Language code:

Show[Histogram[data, Automatic, "PDF", PlotRange -> {{-1, 6}, {0, .5}}], Plot[PDF[dist, x], {x, -1, 6}], Epilog -> {Red, Line[{{#, 0}, {#, 1}}]& /@ modes}]

Clustering (2)

Generate data from some distribution:

Wolfram Language code:

list = Join[
	({Cos[#], Sin[#]} + RandomReal[{-0.1, 0.1}, 2])& /@ RandomVariate[NormalDistribution[Pi, 1], 1000], 
	RandomVariate[BinormalDistribution[{1, -1}, {.3, .5}, 0], 1000], 
	RandomVariate[BinormalDistribution[{1, 1}, {.3, .5}, 0], 1000]
	];

Wolfram Language code: ListPlot[list]

Apply mean shift until all data points have converged:

Wolfram Language code:

res = MeanShift[list, .4, MaxIterations -> ∞, DistanceFunction -> SquaredEuclideanDistance, Weights -> UnitTriangle, Tolerance -> 10 ^ -10];

Gather the result into clusters:

Wolfram Language code:

c = ArrayComponents[res, 1];
clust = GatherBy[Transpose[{list, c}], Last];
clust = #[[All, 1]]& /@ clust;

Visualize the clustering:

Wolfram Language code: ListPlot[clust]

Generate a large amount of data from some distribution:

Wolfram Language code:

n = 10000;
dist = MixtureDistribution[{1, 1}, {BinormalDistribution[{-3 / 2, 0}, {1, 1}, 0], BinormalDistribution[{3 / 2, 0}, {1, 1}, 0]}];
BlockRandom[SeedRandom[1];data = RandomVariate[dist, n]];

Wolfram Language code: {ListPlot[data], Plot3D[PDF[dist, {x, y}], {x, -6, 6}, {y, -4, 4}, PlotRange -> All]}

Compute trajectories for a fraction of the data samples:

Wolfram Language code:

indices = RandomSample[Range[n], 100];
radius = .2;

Wolfram Language code:

paths = Transpose@FixedPointList[
	Part[MeanShift[ReplacePart[data, Thread[indices -> #]], 1, indices, Weights -> "Gaussian"], indices]&, 
	Part[data, indices], 
	∞, SameTest -> (Max@Abs[#1 - #2] < 10 ^ -10&)];

Wolfram Language code: ListLinePlot[paths, PlotRange -> {{-4, 4}, {-3, 3}}]

Merge paths that end within radius of each other:

Wolfram Language code: groups = Gather[Range[Length@indices], EuclideanDistance[paths[[#1, -1]], paths[[#2, -1]]] ≤ radius&];

Label each trajectory and compute the corresponding nearest function:

Wolfram Language code:

l = Table[Position[groups, i, 2][[1, 1]], {i, Length[indices]}];
Short[l]

Wolfram Language code:

labels = ConstantArray[0, n];
labels[[indices]] = l;

Wolfram Language code: nf = Nearest[Flatten[Table[# -> l[[i]]& /@ paths[[i]], {i, Length[indices]}]]];

Each unlabeled sample is assigned the label of the closest trajectory:

Wolfram Language code:

Table[
	labels[[i]] = First@nf[data[[i]]], 
	{i, Complement[Range[n], indices]}];

Visualize the clustering:

Wolfram Language code:

clust = GatherBy[Transpose[{data, labels}], Last];
clust = #[[All, 1]]& /@ clust;
ListPlot[clust]

Computing the mean shift until convergence for the entire dataset would take much longer:

Wolfram Language code: AbsoluteTiming[res = MeanShift[data, 1, MaxIterations -> ∞, Weights -> "Gaussian", Tolerance -> 10 ^ -10];]

Image Segmentation (2)

Iterate mean-shift filtering in the 3D feature space of the "LAB" color components:

Wolfram Language code: img = [image];

Wolfram Language code:

radius = 0.15;
ms = MeanShift[ColorConvert[img, "LAB"], radius, MaxIterations -> 10]

Perform mean-shift filtering in the 5D spatial-range feature domain:

Wolfram Language code:

img = [image];
{w, h} = ImageDimensions[img];

Wolfram Language code:

pix = Flatten[ImageData[ColorConvert[img, "LAB"]], 1];
pos = Flatten[N@Array[{#1, #2} / Max[{h, w}]&, {h, w}], 1];
data = Join[pix, pos, 2];

Wolfram Language code:

radius = 0.25;
AbsoluteTiming[ms = MeanShift[data, radius, Weights -> "Gaussian", MaxIterations -> 10];]

Merge components whose feature values are apart by less than the radius:

Wolfram Language code:

comp = SortBy[Tally[ms], -Last[#]&];
groups = SortBy[#, Function[c, -Last[c]]]& /@ Gather[comp, EuclideanDistance[First[#1], First[#2]] ≤ radius&];
Length[groups]

Wolfram Language code:

d = ms;
rules = Table[
	Map[#[[1]] -> g[[1, 1]]&, Rest[g]], 
	{g, Cases[groups, x_ /; Length[x] > 1]}];
d = d /. Dispatch[Flatten[rules]];

Compute the final segments and quantized image:

Wolfram Language code:

segments = ArrayReshape[ArrayComponents[d, 1], {h, w}];
resimg = Image[ArrayReshape[d[[All,  ;; 3]], {h, w, 3}], ColorSpace -> "LAB"];

Wolfram Language code: Image[#, ImageSize -> 200]& /@ {Colorize[segments], resimg}

Properties & Relations (3)

Perform mean shift on some parts of a list:

Wolfram Language code:

list = {10, 20, 30, 40, 55};
parts = {4, 1};
ms = MeanShift[list, 10, parts]

Extract the mean-shifted elements:

Wolfram Language code: Part[ms, parts]

Perform mean shift on some parts of an image:

Wolfram Language code: i = [image];

Create a mask for the first detected bright component:

Wolfram Language code: mask = SelectComponents[Binarize[i], #Label == 1&]

Perform the smoothing:

Wolfram Language code: ms = MeanShift[i, .15, mask, MaxIterations -> 10]

Extract the mean-shifted pixel values:

Wolfram Language code: PixelValue[ms, PixelValuePositions[mask, 1]]//Shallow

The mean-shift vector is proportional to the gradient density estimate normalized by the density estimate:

Wolfram Language code:

dist = BinormalDistribution[{0, 0}, {1, 2}, 0];
radius = 1;

Wolfram Language code:

BlockRandom[
	SeedRandom[1];
	data = RandomVariate[dist, 10 ^ 4]
	];

Wolfram Language code: msvector = MeanShift[data, radius] - data;

Wolfram Language code:

pdf = Function[{x, y}, Evaluate[PDF[dist, {x, y}]]];
grad = Function[{x, y}, Evaluate[{D[pdf[x, y], x], D[pdf[x, y], y]}]];

Wolfram Language code: δ = MapThread[CosineDistance[#1, grad[Sequence@@#2] / pdf[Sequence@@#2]]&, {msvector, data}];

Wolfram Language code: {Min[δ], Median[δ], Max[δ]}

Neat Examples (1)

Show multiple iterations of mean shift:

Wolfram Language code: NestList[MeanShift[#, 12]& , Sort[RandomReal[{0, 100}, 1000]], 6] // ListPlot

Top

More Learning

Tech Support

Wolfram Solutions

Wolfram Solutions For Education

Get Started

Grow Your Skills

Work with Us

Educational Programs for Adults

Educational Programs for Youth

Read

MeanShift

Details and Options

Examples

Basic Examples (3)

Scope (4)

Options (8)

DistanceFunction (3)

MaxIterations (2)

Tolerance (1)

Weights (2)

Applications (9)

Smoothing (2)

Mean-Shift Displacement (2)

Find Modes of Estimated Distribution (1)

Clustering (2)

Image Segmentation (2)

Properties & Relations (3)

Neat Examples (1)

Text

CMS

APA

BibTeX

BibLaTeX

MeanShift

Details and Options

Examples

Basic Examples (3)

Scope (4)

Options (8)

DistanceFunction (3)

MaxIterations (2)

Tolerance (1)

Weights (2)

Applications (9)

Smoothing (2)

Mean-Shift Displacement (2)

Find Modes of Estimated Distribution (1)

Clustering (2)

Image Segmentation (2)

Properties & Relations (3)

Neat Examples (1)

See Also

Related Guides

History

Text

CMS

APA

BibTeX

BibLaTeX