c++ - 优化的图像卷积算法

Question

我正在努力实现 Image convolution在 C++ 中，我已经有了一个基于给定伪代码的简单工作代码:

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

因为这可能是大图像和内核的大瓶颈，我想知道是否有其他方法可以使事情变得更快？即使有额外的输入信息，如:稀疏图像或内核，已知内核等......

我知道这可以并行化，但在我的情况下不可行。

Answer 1

if element position  corresponding* to pixel position then

我认为这个测试是为了避免乘以 0。跳过测试!乘以 0 比 delays caused by a conditional jump 快得多.

另一种选择(发布实际代码总是比伪代码更好，在这里你让我猜测你实现了什么!)是你正在测试越界访问。那也是非常昂贵的。最好打破你的循环，这样你就不需要对大多数像素进行这种测试:

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 次。它很难看，但方式更快。

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

---

接下来某类内核可以是decomposed into 1D kernels .例如，著名的 Sobel 核是 [1,1,1] 和 [1,0,-1]^T 卷积的结果。对于 3x3 内核，这不是什么大问题，但对于更大的内核来说，这就是大问题。通常，对于 NxN 内核，您从 N² 到 2N 操作。

特别是，the Gaussian kernel is separable .这是一个非常重要的平滑滤波器，也可用于计算导数。

除了明显的计算成本节省外，这些一维卷积的代码也简单得多。对于 1D 滤波器，我们之前的 9 个重复代码块变成了 3 个。水平过滤器的相同代码可以重新用于垂直过滤器。

---

最后，正如MBo's answer中已经提到的那样，您可以通过 DFT 计算卷积。可以使用 FFT 计算 DFT在 O(MN log MN) 中(对于大小为 MxN 的图像)。这需要将内核填充到图像的大小，将两者转换到傅立叶域，将它们相乘，并对结果进行逆变换。一共3个变身。这是否比直接计算更有效取决于内核的大小以及它是否可分离。