优化的图像卷积算法

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

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

对于其他情况：存在fast convolution based on FFT（快速傅里叶变换）。它的复杂性是 O(N^2*logN)（其中 N 是 image 的大小），与 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 图像。

Answer 2

if element position  corresponding* to pixel position then

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

快得多

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

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

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

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

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

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

最后，正如 , you can compute the convolution through the DFT. The DFT can be computed using the FFT 中已经提到的，O(MN log MN)（对于大小为 MxN 的图像）。这需要将内核填充到图像的大小，将两者转换到傅立叶域，将它们相乘，然后 inverse-transforming 结果。一共3个变身。这是否比直接计算更有效取决于内核的大小以及它是否可分离。

Answer 3

提高速度的一种方法可能是，根据目标平台，明确获取内核中的每个值，然后在内存中存储图像的多个副本，每个副本对应内核中的每个不同值，并将图像的每个副本乘以其不同的内核值，然后在最后，乘以不同的内核值，移位，求和并将所有图像副本分成一个图像。这可以在内存充足且更适合这种紧密重复处理的图形处理器上完成。图像的副本需要支持像素溢出，或者您可以使用浮点值。

优化的图像卷积算法

Optimized image convolution algorithm

c++

algorithm

math

image-processing

convolution