↑ arvau

Wikipedia / Mean shift

Mean shift is a non-parametric feature-space mathematical 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 is usually credited to work by Fukunaga and Hostetler in 1975. It is, however, reminiscent of earlier work by Schnell in 1964.

Overview

Mean shift is a procedure for locating the maxima—the modes—of a density function given discrete data sampled from that function.. Let a kernel function be given. This function determines the weight of nearby points for re-estimation of the mean. Typically a Gaussian kernel is

.

is called mean shift in Fukunaga and Hostetler. The mean-shift algorithm 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 stationary (or isolated) points has been proved. However, sufficient conditions for a general kernel function to have finite stationary (or isolated) points have not been provided.

Gaussian Mean-Shift is an Expectation–maximization algorithm.

Details

,

,

is the kernel function (or Parzen window is the only parameter in the algorithm and is called the bandwidth. This approach is known as kernel density estimation over the complete search space. Instead, mean shift uses a variant of what is known in the optimization literature as multiple restart gradient descent and takes an uphill step in that direction.

Types of kernels

is said to be a kernel if there exists a profile , such that

and

  • k is non-negative.

  • .

The two most frequently used kernel profiles for mean shift are:

  1. Flat kernel

  1. Gaussian kernel

.

Applications

Clustering

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

-dimensional input and filtered image pixels in the joint spatial-range domain. For each pixel,

  • .

  • .

Strengths

  1. Mean shift is an application-independent tool suitable for real data analysis.

  2. Does not assume any predefined shape on data clusters.

  3. It is capable of handling arbitrary feature spaces.

  4. The procedure relies on choice of a single parameter: bandwidth.

  5. The bandwidth/window size 'h' has a physical meaning, unlike k-means.

Weaknesses

  1. The selection of a window size is not trivial.

  2. Inappropriate window size can cause modes to be merged, or generate additional "shallow" modes.

  3. Often requires using adaptive window size.

Availability

Variants of the algorithm can be found in machine learning and image processing packages:

  • ELKI. Java data mining tool with many clustering algorithms.

  • ImageJ. Image filtering using the mean shift filter.

  • mlpack. Efficient dual-tree algorithm-based implementation.

  • OpenCV contains mean-shift implementation via cvMeanShift Method

  • Orfeo toolbox. A C++ implementation.

  • scikit-learn Numpy/Python implementation uses ball tree for efficient neighboring points lookup

See also

References