用C语言实现二维卷积的一种快速方法

Question

我正在尝试实现一个视觉算法，其中包括一个带有9x9拉普拉斯高斯滤波器的预滤波级。你能指出一个简单解释快速过滤器实现的文档吗？我认为我应该利用FFT来实现最有效的过滤。

Answer 1

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

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

关于边界：

• 如果假设边界外的值为0，则将4元素边界0添加到二维点数组中。这将避免需要if语句来处理边界，这是昂贵的。
• 如果你的数据在边界处换行(即它是周期性的)，那么使用一个模或添加一个4元素边界来复制网格的另一边(abcdefg -> fgabcdefgab表示2个点)。**注意:这是您使用任何类型的傅立叶变换(包括FFT)所隐含的假设**。如果情况并非如此，则需要在进行任何快速傅立叶变换之前对其进行说明。

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

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

Answer 2

这是一个理论链接http://hebb.mit.edu/courses/9.29/2002/readings/c13-1.pdf

这里有一个指向fftw的链接，这是一个我过去使用过的非常好的FFT库(检查许可证以确保它是合适的) http://www.fftw.org/

您所要做的就是对图像和内核( 9x9矩阵)进行快速傅立叶变换。相乘，然后反向变换。

然而，对于9x9矩阵，你可能仍然可以在真实的坐标下做得更好(只需在图像像素和矩阵上进行双重循环)。两种方法都试一下！

Answer 3

实际上，您不需要使用足够大的FFT大小来容纳整个图像。你可以做很多更小的重叠的2dfft。你可以搜索“快速卷积”“重叠保存”“重叠添加”。

然而，对于9x9内核。在速度方面，您可能看不到太多优势。