Improved fast gauss transform and efficient kernel density estimation
Improved fast gauss transform and efficient kernel density estimation
复制标题
DOI：
10.1109/iccv.2003.1238383
复制
发表时间：
2003-10
期刊：
影响因子：
--
通讯作者：
Changjiang Yang;R. Duraiswami;N. Gumerov;L. Davis
中科院分区：
文献类型：
--
作者：
Changjiang Yang;R. Duraiswami;N. Gumerov;L. Davis
在计算机视觉和模式识别中，多变量高斯和的求值是一项常见的计算任务，包括通用的、功能强大的核密度估计技术。求和的二次计算复杂度是制约该算法在实际应用中的可扩展性的一个重要障碍。快速高斯变换（FGT）成功地将低维问题的核密度估计缩短到线性运行时间。不幸的是，将FGT直接扩展到高维问题的代价随着维数的增加呈指数增长，使得它对于3维以上的问题变得不切实际。我们开发了一种改进的快速高斯变换来有效地估计高维高斯和，其中一个新的多元展开方案和自适应空间细分技术显着提高了性能。将改进后的FGT应用于均值移位算法，实现了线性计算复杂度。实验结果证明了该算法的有效性和有效性。
Evaluating sums of multivariate Gaussians is a common computational task in computer vision and pattern recognition, including in the general and powerful kernel density estimation technique. The quadratic computational complexity of the summation 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. Experimental results demonstrate the efficiency and effectiveness of our algorithm.