Loading...
Please wait, while we are loading the content...
Similar Documents
Gaussian mean shift is an EM algorithm (2005)
| Content Provider | CiteSeerX |
|---|---|
| Author | Carreira-Perpiñán, Miguel Á. |
| Abstract | The mean-shift algorithm, based on ideas proposed by Fukunaga and Hostetler (1975), is a hill-climbing algorithm on the density defined by a finite mixture or a kernel density estimate. Mean-shift can be used as a nonparametric clustering method and has attracted recent attention in computer vision applications such as image segmentation or tracking. We show that, when the kernel is Gaussian, mean-shift is an expectationmaximisation (EM) algorithm, and when the kernel is non-gaussian, mean-shift is a generalised EM algorithm. This implies that mean-shift converges from almost any starting point and that, in general, its convergence is of linear order. For Gaussian mean-shift we show: (1) the rate of linear convergence approaches 0 (superlinear convergence) for very narrow or very wide kernels, but is often close to 1 (thus extremely slow) for intermediate widths, and exactly 1 (sublinear convergence) for widths at which modes merge; (2) the iterates approach the mode along the local principal component of the data points from the inside of the convex hull of the data points; (3) the convergence domains are nonconvex and can be disconnected and show fractal behaviour. We suggest ways of accelerating mean-shift based on the EM interpretation. |
| File Format | |
| Volume Number | 29 |
| Journal | IEEE Trans. on Pattern Analysis and Machine Intelligence |
| Language | English |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | Em Algorithm Gaussian Mean Shift Data Point Generalised Em Algorithm Image Segmentation Gaussian Mean-shift Sublinear Convergence Linear Order Kernel Density Estimate Intermediate Width Superlinear Convergence Recent Attention Nonparametric Clustering Method Finite Mixture Starting Point Mean-shift Converges Hill-climbing Algorithm Em Interpretation Convergence Domain Wide Kernel Fractal Behaviour Computer Vision Application Convex Hull Local Principal Component Linear Convergence Approach Mean-shift Algorithm |
| Content Type | Text |
| Resource Type | Article |
