Mean Shift Analysis and Image Segmentation

The mean shift algorithm is a powerful technique for image segmentation. The algorithm recursively moves to the kernel smoothed centroid for every data point. The quadratic computational complexity of the algorithm is a significant barrier to the scalability of this algorithm to practical applications. The fast Gauss transform (FGT) has successfully accelerated the kernel density estimation to linear running time for low-dimensional problems. Unfortunately, the cost of a direct extension of the FGT to higher-dimensional problems grows exponentially with dimension, making it impractical for dimensions above 3. We develop an improved fast Gauss transform to efficiently estimate sums of Gaussians in higher dimensions, where a new multivariate expansion scheme and an adaptive space subdivision technique dramatically improve the performance. The improved FGT has been applied to the mean shift algorithm achieving linear computational complexity.

References

1. C. Yang, R. Duraiswami, N. Gumerov and L. Davis. Improved Fast Gauss Transform and Efficient Kernel Density Estimation, In IEEE International Conference on Computer Vision, pages 464-471, 2003.
2. C. Yang, R. Duraiswami, D. DeMenthon and L. Davis. Mean-Shift Analysis Using Quasi-Newton Methods. In IEEE International Conference on Image Processing, pages 447 - 450, vol.3, 2003.