Mean-shift

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Mean shift is a non-parametric feature-space analysis technique for locating the maxima of a density function, a so-called mode seeking algorithm.[1] Application domains include cluster analysis in computer vision and image processing.[2]

History[edit]

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

Overview[edit]

Mean shift is a procedure for locating the maxima of a density function given discrete data sampled from that function.[1] It is useful for detecting the modes of this density.[1] 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 a Gaussian kernel on the distance to the current estimate is used,  K(x_i - x) = e^{-c||x_i - x||^2} . 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.

Mean shift for visual tracking[edit]

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,[4] CAMshift, [5] expand on this idea.

See also[edit]

References[edit]

  1. ^ a b c 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. 
  2. ^ 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. 
  3. ^ 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. 
  4. ^ 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. 
  5. ^ Emami, Ebrahim (2013). "Online failure detection and correction for CAMShift tracking algorithm". 2013 Iranian Conference on Machine Vision and Image Processing (MVIP) (IEEE) 2: 180–183. 

Code implementations[edit]

  • 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.

Short lessons[edit]

  • Here a lesson is available from prof. M.Shah on this topic;