通过使用离散小波变换的积分直方图来进行高效的局部统计分析 (Efficient Local Statistical Analysis via Integral Histograms with Discrete Wavelet Transform)

从局部区域中计算直方图在很多可视化应用中都有广泛的使用,而且在特征识别和追踪中,允许用户在任意位置和尺寸的区域查询直方图是非常重要的。对于大数据集来说,由于涉及昂贵的I/O以及数据元素的扫描,这会变得非常耗费时间。在这篇文章中,作者提出了一种叫做WaveletSAT的新算法,这种算法利用了积分直方图,积分直方图是积分图(SAT)和离散小波变换(DWT)的扩展。WaveletSAT算法从存储效率,查询性能以及预处理耗费这几个方面来解决了问题,这种算法可以把积分直方图转换成一个稀疏的小波系数集,这样一个任意区域的直方图可以高效得从小波系数中得到重建,并且利用独立的时间复杂度来摒弃了在小波变换之前预先计算积分直方图的方法,由于每个网格点可以独立转换,所以WaveletSAT可以实现并行计算。

image1图1. 积分直方图,SAT容器和阶梯函数之间的关系

下图是一个二维区域中通过SAT计算面积总和的例子,一个二维数组的积分直方图和它的SAT很相似,不同在于每个积分直方图中的元素存储的不是一个标量而是由起点和所选点所围成的矩形的直方图。image3

图2.二维区域中通过SAT计算面积总和的例子

离散小波变换的递归过程可以理解成一个把向量f投射到N个基础向量上的线性转换过程,于是在WaveletSAT算法中,给一个点y,它的阶梯函数只能贡献1+logN个小波系数,所以在1D标准网格中,这种算法首先确定每个容器中的值,然后更新这个容器中的所有小波系数。根据小波系数,我们就可以通过下面的DWT反变换公式来重建位于x的积分直方图。

equation1

离散小波变换也可以扩展到D维度的网格中。对于多维度的体数据来说,我们可以把一维DWT单独应用到每个维度中。一旦一维DWT被应用到第一个维度上的所有扫描线,它就会被应用到第二个维度上的所有扫描线一直如此直到DWT被应用到所有维度上。这种方法叫做可分离的离散小波变换(Separable DWT)。

image2图3. D=2和N=8的小波基张量

作者还从编码时间,查询时间和压缩率这些角度来对WaveletSAT的性能以及GPU的影响进行了验证。可以发现和普通的积分直方图相比,WaveletSAT的性能有显著的提高。

这篇文章的主要贡献在于提出了一种支持用户在任意矩形域高效查询直方图的算法。这种算法取代了以往每个格点存储的是一个值,而是存储了一个积分直方图,并且实际上利用了离散小波变换来压缩积分直方图。但是有一个很大的局限就是只适用于标准网格。

 

参考文献

[1] Teng-Yok Lee, Member, IEEE, and Han-Wei Shen. “Efficient Local Statistical Analysis via Integral Histograms with Discrete Wavelet Transform”. Visualization and Computer Graphics, IEEE Transactions on, vol.19, no.12, pp.2693,2702, Dec. 2013

 

评论关闭。