E¢cient Kernel Density Estimation Using the Fast Gauss Transform with Applications to Segmentation and Tracking
Ahmed Elgammal, Ramani Duraiswami, Larry Steven Davis · 2001
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 signi...cant 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 ofM Gaussians atN evaluation points inO(M+N) time as opposed toO(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.