c - 在 C 中实现二维卷积的快速方法

Question

我正在尝试实现一种视觉算法，其中包括一个带有 9x9 拉普拉斯高斯滤波器的预过滤阶段。你能指出一个简要解释快速过滤器实现的文档吗？我想我应该使用 FFT 进行最有效的过滤。

Answer 1

您确定要使用 FFT 吗？那将是一个整个数组的转换，这将是昂贵的。如果您已经决定使用 9x9 卷积滤波器，则不需要任何 FFT。

通常，在 C 中进行卷积的最便宜的方法是设置一个循环，在数组上移动一个指针，对每个点的卷积值求和并将数据写入一个新数组。然后可以使用您喜欢的方法(编译器矢量化、MPI 库、OpenMP 等)并行化此循环。

关于边界:

• 如果您假设值在边界外为 0，则向您的二维点数组添加 4 个元素为 0 的边界。这将避免需要 `if` 语句来处理昂贵的边界。
• 如果您的数据在边界处回绕(即它是周期性的)，则使用模数或添加一个 4 元素边界来复制网格的另一侧(abcdefg -> fgabcdefgab 用于 2 个点)。 **注意:这是您对任何类型的傅立叶变换(包括 FFT)隐式假设的内容**。如果不是这种情况，您需要在完成任何 FFT 之前考虑到这一点。

4个点是因为9x9核的最大边界重叠在主网格之外有4个点。因此，2n+1 x 2n+1 内核需要 n 个边界点。

如果您需要此卷积非常快，并且/或您的网格很大，请考虑将其分成更小的部分，这些部分可以保存在处理器的缓存中，从而可以更快地计算。这也适用于您可能想要执行的任何 GPU 卸载(它们非常适合此类浮点计算)。