在 C 中实现 2D 卷积的快速方法 [英] Fast way to implement 2D convolution in C

问题描述

我正在尝试实现一种视觉算法，其中包括一个带有 9x9 Laplacian-of-Gaussian 滤波器的预过滤阶段.你能指出一份简要解释快速过滤器实现的文档吗?我想我应该使用 FFT 来实现最有效的过滤.

I am trying to implement a vision algorithm, which includes a prefiltering stage with a 9x9 Laplacian-of-Gaussian filter. Can you point to a document which explains fast filter implementations briefly? I think I should make use of FFT for most efficient filtering.

推荐答案

您确定要使用 FFT 吗?这将是一个完整的阵列变换，这将是昂贵的.如果您已经决定使用 9x9 卷积滤波器，则不需要任何 FFT.

Are you sure you want to use FFT? That will be a whole-array transform, which will be expensive. If you've already decided on a 9x9 convolution filter, you don't need any FFT.

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

Generally, the cheapest way to do convolution in C is to set up a loop that moves a pointer over the array, summing the convolved values at each point and writing the data to a new array. This loop can then be parallelised using your favourite method (compiler vectorisation, MPI libraries, OpenMP, etc).

关于边界:

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

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

The 4 points are because the maximum boundary overlap of a 9x9 kernel is 4 points outside the main grid. Thus, n points of border needed for a 2n+1 x 2n+1 kernel.

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

If you need this convolution to be really fast, and/or your grid is large, consider partitioning it into smaller pieces that can be held in the processor's cache, and thus calculated far more quickly. This also goes for any GPU-offloading you might want to do (they are ideal for this type of floating-point calculation).

这篇关于在 C 中实现 2D 卷积的快速方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！