Efficient Computation of Kernel Density Estimation using Fast Gauss
Transform with Applications for Segmentation and Tracking
Ahmed Elgammal,
Ramani Duraiswami,
and Larry Davis
University of Maryland
The study of many vision problems is reduced to the estimation of a
probability density function from observations. Kernel density
estimation techniques are quite general and powerful methods for this
problem, but have a significant disadvantage in that they are
computationally intensive. In this paper we explore the use of kernel
density estimation with the fast gauss transform (FGT) for problems in
vision. The FGT allows the summation of a mixture of M Gaussians at N
evaluation points in O(M+N) time as opposed to O(MN) time for a naive
evaluation, and can be used to considerably speed up kernel density
estimation. We present applications of the technique to problems from
image segmentation and tracking, and show that the algorithm allows
application of advanced statistical techniques to solve practical vision
problems in real time with today's computers