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.
The mean shift procedure was originally presented in 1975 by Fukunaga and Hostetler.
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 . Let a kernel function 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, . The weighted mean of the density in the window determined by is
where is the neighborhood of , a set of points for which .
The mean-shift algorithm now sets , and repeats the estimation until converges.
Mean shift for visual 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 ensemble tracking, CAMshift, expand on this idea.
- Cheng, Yizong (August 1995). "Mean Shift, Mode Seeking, and Clustering". IEEE Transactions on Pattern Analysis and Machine Intelligence (IEEE) 17 (8): 790–799. doi:10.1109/34.400568.
- Comaniciu, Dorin; Peter Meer (May 2002). "Mean Shift: A Robust Approach Toward Feature Space Analysis". IEEE Transactions on Pattern Analysis and Machine Intelligence (IEEE) 24 (5): 603–619. doi:10.1109/34.1000236.
- Fukunaga, Keinosuke; Larry D. Hostetler (January 1975). "The Estimation of the Gradient of a Density Function, with Applications in Pattern Recognition". IEEE Transactions on Information Theory (IEEE) 21 (1): 32–40. doi:10.1109/TIT.1975.1055330. Retrieved 2008-02-29.
- Avidan, Shai (2005). "Ensemble Tracking". 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) (San Diego, California: IEEE) 2. ISBN 0-7695-2372-2.
- Scikit-learn library Numpy/Python implementation uses ball tree for efficient neighboring points lookup
- EDISON library. C++ implementation of mean-shift-based image segmentation. There is also a Matlab interface for EDISON.
- OpenCV contains mean-shift implementation via cvMeanShift Method
- Aiphial. Java-based mean-shift implementation for numeric data clustering and image segmentation
- Apache Mahout. An map-reduce based implementation of MeanShift clustering written on Apache Hadoop.
- CAMSHIFT project. A MATLAB implementation of CAMSHIFT algorithm.
- OTB MeanShift. A C++ implementation using the Orfeo Toolbox.
- ImageJ Plug-in. Image filtering using the mean shift filter.
- Mean-shift google code. An simple implementation of mean-shift as image filtering tool.
- Here a lesson is available from prof. M.Shah on this topic;