优化的图像卷积算法

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

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

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

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内核，从N2到2N操作。

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

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

---

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

Answer 2

对于小内核大小，简单方法可能更快。还要注意，如上所述，可分离内核（例如，高斯内核是可分离的）允许按行然后按列进行过滤，从而产生O（N ^ 2 * M）复杂度。

对于其他情况：存在fast convolution based on 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图像。