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

## References

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

Changjiang Yang
2005-03-01