使用 FFT 优化二维小波变换

信息处理 图像处理 fft 小波 优化
2022-01-29 19:53:53

我目前的目标是针对 2D 信号（图像）优化我的快速小波变换（FWT）算法。它的工作原理如下：

  • 1D FWT 的一次迭代使用选定的 1D 滤波器（长度从 2 到大约 60）对 1D 输入数据进行卷积，并对结果进行下采样
  • 2D 变换算法对输入图像的所有行和所有列进行 1D FWT
  • 如果需要更多级别，它会迭代

变换是演示小波及其使用的交互式应用程序的一部分。它的工作速度相当快，通常实时响应用户的交互。但是如果过滤器很长，就会出现一些性能问题。我读过使用快速傅里叶变换（FFT）而不是卷积对于足够长的滤波器是有效的。

我已经实现了 1D FFT，但问题是如何使用它来获得最大效率？我是否应该在单个 1D FWT 之前转换输入数据，然后执行卷积（对应于频域中的乘法），然后使用逆 FFT 将数据转换回来？另外，乘法是如何精确完成的？例如，长度为 256 的输入数据和长度为 4 的过滤器都使用 FFT 进行转换，然后只将输入数据的前 4 个值相乘，然后再将数据转换回来？我在细节上有点挣扎，非常感谢对此的任何见解。

编辑： 我发现在我的情况下，我在循环卷积之后，因此过滤器应该是零填充的，以便它的长度与输入数据的长度相同。但是我关于效率的问题仍然存在。我应该如何使用 FFT 进行 FWT 计算才能有益？

1个回答

我仍然不相信你正在以最佳方式度过你的时间。进行其他优化可能会获得更好的收益。对于我见过的大多数应用程序，10-15 个抽头已经被认为是非常长的小波滤波器。但没关系，我会尝试回答你的问题。

你可以做两种不同的方法

  1. 你可以一次做一个级别。
  2. 全部一起。

它们中的任何一个都有缺点和收益。我将从第一个开始。

如果你一次去一个级别：

  • 您将零填充过滤器与行和列的长度相等。还要确保你垫好过滤器在中间。
  • FFT 填充过滤器和相应的图像尺寸。如果宽度≠高度，您需要对每个尺寸长度的每个过滤器进行 2 次 FFT。
  • 滤波器和图像的 FFT 的逐点乘法。
  • 产品图像的逆 FFT。
  • 在您转换的维度中对产品图像进行下采样。
  • 重复下一个维度。
  • 对所有级别重复。

请注意，此方法将涉及每个级别的一组 iFFT 和 FFT。那将是双重糟糕的。

一次性方法：

  • 与上述相同，但不是 iFFT 并将每个级别抽取到仅对抽取的信号再次进行 FFT，您只需将滤波器乘以几次，然后执行 iFFT 并抽取 2、4、8 次等。然后你只需要做一组 FFT（在开始时），但仍然需要为每个级别做一套完整的 iFFT。

此外，在傅立叶域中的乘法将比普通乘法计算更昂贵，因为傅立叶分量将是∈C但滤波器和图像系数∈R（我猜）并且您可能还需要更高的数值精度才能获得相同的错误。

其它你可能感兴趣的问题
上一篇什么是在图像中定位蝴蝶的好方法 下一篇一组移动平均滤波器中的纹波和衰减是多少？