目录
Jacobsen E. and Lyons R. An update to the sliding DFT. SPM, 2004.
Kober V. Fast algorithms for the computation of sliding discrete sinusoidal transforms. TSAP, 2004.
概
在一个滑动窗口上的信息处理的快速算法.
滑动窗口上的快速算法
-
在实际中, 我们常常会遇到一批一批的数据:
\[[\cdots, \underbrace{x_p, x_{p+1}, \cdots, x_{p + N-1}}_{W_p}, x_{p + N}, \cdots], \]\(W_p\) 是其中一个长度为 \(N\) 的窗口.
-
一般的信号处理, 关注的是所有数据的一个处理, 但是这里我们仅考虑 \(W_p\) 上数据的一个处理. 当然, 一般的信号处理可以无碍地应用在 \(W_p\) 之上, 但是如果在 \(W_p\) 已经处理过的信号基础上, 更快速地得到 \(W_{p+1}, W_{p+2}\) 上的结果, 是参考文献所关注的问题.
-
上面的参考文献, 关注的是如下一个更加特殊的情况:
\[\tag{1} X_k(p) = \sum_{n=0}^{N-1} x_{p+n} \cdot f_{k, n}, \]其中 \(\{f_k = [f_{k, 0}, \ldots, f_{k, N-1}]^T: k \in 0, 1, \ldots, N-1\}\) 往往构成正交基. 比如, 当 \(f_{k, n} = e^{-i 2 \pi kn / N}\) 的时候, (1) 就是熟知的离散傅里叶变换.
-
显然, 来一个新的样本 \(x\) 就重新计算 (1) 是动态更新 \(X_k(p)\) 的一个法子, 但是极其消耗代价. 上述文章, 大体利用 \(f_{k, n}\) 的一个周期性, 从而得到形如如下的一个迭代算法:
\[X_k(p + 1) = a X_k(p) - b x_p + cx_{p+N}. \] -
下面是傅里叶变换下的一个特殊例子, 其它情况 (DCT, DST, WHT) 会有比较类似的结果:
\[\begin{array}{ll} X_k(p + 1) &= \sum_{n=0}^{N-1} x_{p + 1 + n} \cdot e^{-i2\pi kn / N} \\ &= \sum_{n=0}^{N-1} x_{p+n} \cdot e^{-i2\pi k (n - 1) / N} \\ &\quad \quad - x_{p} e^{i2\pi k / N} + x_{p + N} e^{-2\pi k (N-1) / N} \\ &= \sum_{n=0}^{N-1} x_{p+n} \cdot e^{-i2\pi k (n - 1) / N} \\ &\quad \quad - x_{p} e^{i2\pi k / N} + x_{p + N} e^{i2\pi k / N} \\ &= e^{i2\pi k / N} \bigg \{ \sum_{n=0}^{N-1} x_{p+n} \cdot e^{-i2\pi k n/ N} - x_{p} + x_{p + N} \bigg\} \\ &= e^{i2\pi k / N} \bigg \{ X_k(p) - x_{p} + x_{p + N} \bigg\}. \end{array} \] -
遗憾的是, 这种方式, 似乎依旧必须保存整个 \(W_p\) 的数据.