World Library  
Flag as Inappropriate
Email this Article


Article Id: WHEBN0010999922
Reproduction Date:

Title: Mean-shift  
Author: World Heritage Encyclopedia
Language: English
Subject: K-nearest neighbors algorithm, Kernel density estimation, Lloyd's algorithm
Publisher: World Heritage Encyclopedia


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


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


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

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, expand on this idea.

See also


Code implementations

  • Scikit-learn library Numpy/Python implementation uses ball tree for efficient neighboring points lookup
  • 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.
  • 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

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

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.