在C中实现2D卷积的快速方法

我正在尝试实现视觉算法,其中包括具有9×9拉普拉斯高斯滤波器的预滤波阶段。 您能指出一个简要解释快速filter实现的文档吗? 我想我应该利用FFT进行最有效的过滤。

你确定要使用FFT吗? 这将是一个全数组转换,这将是昂贵的。 如果您已经决定使用9×9卷积滤波器,则不需要任何FFT。

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

关于边界:

  • 如果假设边界外的值为0,则在2d点数组中添加一个0元素的0边框。 这将避免需要`if`语句来处理边界,这是昂贵的。
  • 如果你的数据包裹在边界(即它是周期性的),那么使用模数或添加一个复制网格另一侧的4元素边框(abcdefg – > fgabcdefgab 2点)。 **注意:这是您使用任何类型的傅立叶变换隐式假设的,包括FFT **。 如果不是这种情况,则需要在完成任何FFT之前对其进行说明。

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

如果你需要这个卷积非常快,和/或你的网格很大,可以考虑将它分成可以保存在处理器缓存中的较小部分,从而更快地计算出来。 这也适用于您可能想要进行的任何GPU卸载(它们非常适合这种类型的浮点计算)。

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

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

您所做的就是对图像和内核进行FFT(9×9矩阵)。 乘以一起,然后再变换。

但是,对于9×9矩阵,您可能仍然可以在实际坐标中更好地进行(仅在图像像素和矩阵上使用双循环)。 尝试两种方式!

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

但是,对于9×9内核。 你可能没有看到很多优势。