Next: Realtime Robust Object Tracking
Up: Research Summary
Previous: Improved Fast Gauss Transform
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.
- 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.
- 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.