优化的图像卷积算法

Question

我正在用 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 比条件跳转引起的延迟要快得多。

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

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 次。这是丑陋的，但方式更快。

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

接下来，可以将某一类内核分解为一维内核。例如，众所周知的 Sobel 核是由 [1,1,1] 和 [1,0,-1] ^T的卷积产生的。对于 3x3 内核来说，这不是什么大问题，但对于更大的内核来说却是。通常，对于 NxN 内核，您需要从 N ^{2 次}操作到 2N 次操作。

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

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

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