Mean shift

Mean shift is a non-parametric feature-space analysis technique for locating the maxima of a density function, a so-called mode-seeking algorithm. Application domains include cluster analysis 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—the modes—of a density function given discrete data sampled from that function. This is an iterative method, and we start with an initial estimate formula_1. Let a kernel function formula_2 be given. This function determines the weight of nearby points for re-estimation of the mean. Typically a Gaussian kernel on the distance to the current estimate is used, formula_3. The weighted mean of the density in the window determined by formula_4 is
where formula_6 is the neighborhood of formula_1, a set of points for which formula_8.
The difference formula_9 is called "mean shift" in Fukunaga and Hostetler. 
The "mean-shift algorithm" now sets formula_10, and repeats the estimation until formula_11 converges.
Although the mean shift algorithm has been widely used in many applications, a rigid proof for the convergence of the algorithm using a general kernel in a high dimensional space is still not known. Aliyari Ghassabeh showed the convergence of the mean shift algorithm in one-dimension with a differentiable, convex, and strictly decreasing profile function. However, the one-dimensional case has limited real world applications. Also, the convergence of the algorithm in higher dimensions with a finite number of the (or isolated) stationary points has been proved. However, sufficient conditions for a general kernel function to have finite (or isolated) stationary points have not been provided.
Gaussian Mean-Shift is an Expectation–maximization algorithm.
Details.
Let data be a finite set formula_12 embedded in the formula_13-dimensional Euclidean space, formula_14. Let formula_15 be a flat kernel that is the characteristic function of the formula_16-ball in formula_14,
formula_18 
In each iteration of the algorithm, formula_19 is performed for all formula_20 simultaneously. The first question, then, is how to estimate the density function given a sparse set of samples. One of the simplest approaches is to just smooth the data, e.g., by convolving it with a fixed kernel of width formula_21,
formula_22
where formula_23 are the input samples and formula_24 is the kernel function (or "Parzen window"). formula_21 is the only parameter in the algorithm and is called the bandwidth. This approach is known as "kernel density estimation" or the Parzen window technique. Once we have computed formula_26 from equation above, we can find its local maxima using gradient ascent or some other optimization technique. The problem with this "brute force" approach is that, for higher dimensions, it becomes computationally prohibitive to evaluate formula_26 over the complete search space. Instead, mean shift uses a variant of what is known in the optimization literature as "multiple restart gradient descent". Starting at some guess for a local maximum, formula_28, which can be a random input data point formula_29, mean shift computes the gradient of the density estimate formula_26 at formula_28 and takes an uphill step in that direction.
Types of kernels.
Kernel definition: Let formula_14 be the formula_13-dimensional Euclidean space, formula_34. The norm of formula_35 is a non-negative number, formula_36. A function formula_37 is said to be a kernel if there exists a "profile", formula_38 , such that
formula_39
and 
The two most frequently used kernel profiles for mean shift are:
formula_43
formula_44
where the standard deviation parameter formula_45 works as the bandwidth parameter, formula_46.
Applications.
Clustering.
Consider a set of points in two-dimensional space. Assume a circular window centered at C and having radius r as the kernel. Mean shift is a hill climbing algorithm which involves shifting this kernel iteratively to a higher density region until convergence. Every shift is defined by a mean shift vector. The mean shift vector always points toward the direction of the maximum increase in the density. At every iteration the kernel is shifted to the centroid or the mean of the points within it. The method of calculating this mean depends on the choice of the kernel. In this case if a Gaussian kernel is chosen instead of a flat kernel, then every point will first be assigned a weight which will decay exponentially as the distance from the kernel's center increases. At convergence, there will be no direction at which a shift can accommodate more points inside the kernel.
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. The confidence map is a probability density function on the new image, assigning each pixel of the new image a probability, which is the probability of the pixel color occurring in the object in the previous image. A few algorithms, such as kernel-based object tracking, 
ensemble tracking, 
CAMshift 
expand on this idea.
Smoothing.
Let formula_23 and formula_48 be the formula_49-dimensional input and filtered image pixels in the joint spatial-range domain. For each pixel,
Availability.
Variants of the algorithm can be found in machine learning and image processing packages: