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

Question

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

Answer 1

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

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

关于边界:

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

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

如果你需要这个卷积非常快,和/或你的网格很大,可以考虑将它分成更小的部分,这些部分可以保存在处理器的缓存中,因此计算得更快.这也适用于您可能想要执行的任何GPU卸载(它们非常适合此类浮点计算).