Mean shift

Mean-shift is a non-parametric feature-space analysis technique. Application domains include clustering in computer vision and image processing.

History

The mean shift procedure was originally presented in 1975 by Fukunaga and Hostetler.

Overview

Mean shift is a procedure for locating the maxima of a density function given discrete data sampled from that function. It is useful for detecting the modes of this density.. This is an iterative method, and we start with an initial estimate $x$. Let a kernel function $K(x_{i}-x)$ be given. This function determines the weight of nearby points for re-estimation of the mean. Typically we use the Gaussian kernel on the distance to the current estimate, $K(x_{i}-x)=e^{c||x_{i}-x||}$. The weighted mean of the density in the window determined by $K$ is

$m(x)={\frac {\sum _{x_{i}\in N(x)}K(x_{i}-x)x_{i}}{\sum _{x_{i}\in N(x)}K(x_{i}-x)}}$

where $N(x)$ is the neighborhood of $x$, a set of points for which $K(x)\neq 0$.

The mean-shift algorithm now sets $x\leftarrow m(x)$, and repeats the estimation until $m(x)$ converges to $x$

Mean Shift for Tracking

The mean shift algorithm can be used for visual tracking. The simplest such algorithm would create a confidence map in the new image based on the color histogram of the object in the previous image, and use mean shift to find the peak of a confidence map near the object's old position. A few algorithms, such as Ensemble Tracking(Avidan, 2001), expand on this idea.

See also

• Medoidshift
• Mean-shift clustering
• CAMSHIFT

Code implementations

• EDISON library. C++ implementation of mean-shift-based image segmentation
• OpenCV contains mean-shift implementation via cvMeanShift Method
• Aiphial. Java-based mean-shift implementation for numeric data clustering and image segmentation
• Mathematica MeanShift function
• Mathematica MeanShiftFilter.