优化的图像卷积算法

Question

我正在努力实现用C++进行图像卷积的操作，已经根据给定的伪代码编写了一个基础版本：

Image convolution

for each image row in input image:
   for each pixel in image row:

      set accumulator to zero

      for each kernel row in kernel:
         for each element in kernel row:

            if element position  corresponding* to pixel position then
               multiply element value  corresponding* to pixel value
               add result to accumulator
            endif

      set output image pixel to accumulator

当处理大型图像和内核时，这可能是一个很大的瓶颈，我想知道是否存在其他方法来加快处理速度？即使有额外的输入信息，如：稀疏图像或内核，已知内核等...

我知道这可以并行处理，但在我的情况下无法实现。

- Pierre Baret

---

一些核可以进行线性分离（谷歌搜索此内容）。这提供了巨大的加速（数量级）。 - MFisherKDX

不知道要在哪个平台上运行的情况下进行优化是不可能的，我们怎么知道它的能力或者什么更快或更慢（当你根本没有指定它时）？当并行化不可能时，还有其他手段，如SIMD、自动生成的硬编码卷积、重复使用子结果以及可能有很多其他技术... - Spektre

@Spektre，这是因为我在谈论算法，也就是编写代码的更好方法/途径。 - Pierre Baret

请查看这篇和那篇论文。 - Amiri

Answer 1

if element position  corresponding* to pixel position then

我认为这个测试是为了避免乘以0。跳过测试吧！与由条件跳转引起的延迟相比，乘以0要快得多。

另一种选择（最好是发布实际代码而不是伪代码，这里让我猜测你实现了什么！）是你正在测试越界访问。这也非常昂贵。最好将循环分开，这样你就不需要为大多数像素做这个测试：

for (row = 0; row < k/2; ++row) {
   // inner loop over kernel rows is adjusted so it only loops over part of the kernel
}
for (row = k/2; row < nrows-k/2; ++row) {
   // inner loop over kernel rows is unrestricted
}
for (row = nrows-k/2; row < nrows; ++row) {
   // inner loop over kernel rows is adjusted
}

当然，对于列循环也是同样的道理，会导致内部循环重复9次kernel值。这很丑陋，但速度要快得多。

为了避免代码重复，您可以创建一个更大的图像，将图像数据复制过去，并在所有侧面填充零。现在循环不需要担心访问越界，您有更简单的代码。

---

接下来，某些内核类别可以分解为一维内核。例如，著名的Sobel内核是由[1,1,1]和[1,0,-1]^T卷积得出的。对于3x3内核，这并不是什么大问题，但对于更大的内核来说就不同了。通常情况下，对于NxN内核，操作次数从N²变为2N。

特别地，高斯内核是可分离的。这是一个非常重要的平滑滤波器，也可以用于计算导数。

除了显而易见的计算成本节省外，对于这些1D卷积来说，代码也更简单了。我们之前有9个重复的代码块，现在只需要一个1D滤波器就可以了。水平滤波器的相同代码也可以重复使用于垂直滤波器。

---

最后，如MBo的答案中所提到的，您可以通过DFT计算卷积。 DFT可以使用FFT在O（MN log MN）中计算（对于大小为MxN的图像）。 这需要将内核填充到图像的大小，将两者转换为傅里叶域，将它们相乘，并将结果反向变换。总共3次变换。这是否比直接计算更有效取决于内核的大小以及它是否可分离。

- Cris Luengo

---

优秀而全面的回答。对于小型和中等大小的内核，我对FFT解决方案持怀疑态度。 - user1196549

@YvesDaoust：我同意。你需要计时来确定它是否更快。然后你需要决定你需要什么边界条件，DFT的周期性假设并不总是有用的。 - Cris Luengo

非常感谢您提供这个非常有趣和完整的答案，正是我正在寻找的提示类型！ - Pierre Baret

Answer 2

对于小的内核大小，简单方法可能更快。此外，如上所述，可分离内核（例如，高斯内核是可分离的）允许通过行和列进行滤波，结果为O(N^2 * M)复杂度。

对于其他情况：存在基于FFT的快速卷积（快速傅里叶变换）。它的复杂度为O(N^2*logN)（其中N是图像的大小），而朴素实现的复杂度为O(N^2*M^2)。

当然，在应用这些技术时有一些特殊情况，例如边缘效应，但在朴素实现中也需要考虑它们（尽管程度较小）。

 FI = FFT(Image)
 FK = FFT(Kernel)
 Prod = FI * FK (element-by-element complex multiplication)
 Conv(I, K) = InverseFFT(Prod)

请注意，您可以使用一些专用于图像过滤的快速库，例如 OpenCV 可以在 5-30 毫秒内将内核应用于 1024x1024 图像。

- MBo

---

对于小内核，M²胜过Log N，不计算隐藏常数对于朴素实现来说更好。 - user1196549

@Yves Daoust 好的，我已经将这些信息添加到答案中（虽然我认为作者理解并不是所有情况都有万能的解决方案）。 - MBo

那个PDF链接无法阅读（可能是一些奇怪的字体），如何处理N和M的不同分辨率（当它们没有相同的分辨率时如何逐块相乘）？非2的幂分辨率是否会成为问题（如果零填充改变结果，如何处理）？顺便说一下，在这里如何计算离散傅里叶变换？有一些我用C++实现的DFT/DFFT/DCT/DFCT的链接。 - Spektre

@MBo，这很奇怪，我刚刚再试了一次，突然所有的文本都正常了，在此之前（25分钟前）所有的文本都是重叠在一起的，以至于无法阅读，现在我看到了一页页的文本，而不仅仅是几个单词（就像所有的单词都印在同一个位置上）。 - Spektre

@Spektre 官方网站（也许 pdf 是一样的）：http://www.nrbook.com/a/bookcpdf.php 所有章节在一个单独的 pdf 中：https://www2.units.it/ipl/students_area/imm2/files/Numerical_Recipes.pdf - MBo

Answer 3

一种加速的方法是，根据目标平台，在内存中明确获取内核中的每个值，为内核中的每个不同值存储图像的多个副本，并将每个图像副本乘以其不同的内核值，最后将所有图像副本乘以不同的内核值、移位、求和并分成一个图像。例如，可以在图形处理器上执行此操作，该处理器具有充足的内存并更适合进行紧密重复的处理。图像的副本需要支持像素溢出，或者可以使用浮点值。

- Aaron Murgatroyd