| |
|
| |
|
Miguel Carreira-Perpinan
CSEE, OGI, Oregon Health & Science University
Gaussian Mean-Shift Algorithms
July 5, 2006 12:00pm
Abstract:
I will describe theoretical and practical results of mean-shift, an algorithm for finding the modes of a kernel density estimate (eg a Gaussian mixture). This algorithm, based on ideas by Fukunaga & Hostetler (1975), has attracted considerable attention in recent years in computer vision applications such as image segmentation and tracking. In the first part of the talk I'll show that mean-shift is an EM algorithm for the Gaussian kernel and a generalised EM algorithm for other kernels. Gaussian mean-shift (GMS) converges from any starting point and its convergence rate is linear in general (superlinear or sublinear in particular cases), thus very slow. I will also show that the GMS convergence domains (which determine the clusters) can be fractal. I will then give several acceleration strategies based on spatial discretisation, sparse EM, and Newton's method, which can speed up GMS by two orders of magnitude with minimal alteration to the clustering. In the second part of the talk I'll focus on the original (and still neglected) version of Gaussian mean-shift that Fukunaga & Hostetler really proposed, Gaussian blurring mean-shift (GBMS). In GBMS the data set iteratively shrinks under the application of GMS steps. I'll show how to stop the iteration to achieve good clusterings; prove that its convergence rate for Gaussian clusters is cubic; give a relation with spectral clustering; and give an accelerated (but otherwise equivalent) version of GBMS. The resulting GBMS algorithm is much faster than GMS while achieving results of similar quality. All algorithms will be illustrated with image segmentation results.
If you have questions, or would like to meet the speaker, please contact Ponda at 4-1994 or pondabarnes@tti-c.org. For information on future TTI-C talks or events, please go to the TTI-C Events page.