使用FFT优化二维小波变换
本文关键字：二维 小波变换 FFT 优化 使用 | 更新日期: 2023-09-27 18:28:54
我目前的目标是优化2D信号（图像）的快速小波变换（FWT）算法。它的工作原理如下：
- 1D FWT的一次迭代将1D输入数据与选定的1D滤波器（长度从2到大约60）进行卷积，并对结果进行下采样
- 2D变换的算法在输入图像的所有行和所有列上进行1D FWT
- 如果需要更多级别，它会迭代
变换是演示小波及其使用的交互式应用程序的一部分。它的工作速度相当快，通常会实时响应用户的交互。但是，如果过滤器很长，就会出现一些性能问题。我读到使用快速傅立叶变换（FFT）代替卷积对于足够长的滤波器是有效的。
我已经实现了1D FFT，但问题是如何使用它来获得最大效率？我应该在单个1D FWT之前对输入数据进行变换，然后执行卷积（对应于频域中的乘法），然后使用逆FFT将数据变换回来吗还有，乘法到底是怎么做的？例如，长度为256的输入数据和长度为4的滤波器都使用FFT进行变换，然后在将数据变换回之前只乘以输入数据的前4个值我在细节上有点纠结，如果能深入了解，我将不胜感激。
编辑：我已经发现，在我的情况下，我在进行循环卷积，所以滤波器应该是零填充的，这样它的长度和输入数据的长度相同。但我关于效率的问题仍然存在。我应该如何使用FFT进行FWT计算才能获得好处？
第2版：此问题已在dsp.stackexchange.com.
有一种非常优雅的方法可以做到这一点。如果你感兴趣的话，我可以为此挖掘我的代码，它是很久以前制作的（关于非冗余（FWT）情况（图3）和移位不变情况，请参阅这两篇出版物）。移位不变的情况可能不是你想要的，但它使用了相同的技巧。在附录B中对其进行了更全面的描述。