代码之家 › 专栏 › 技术社区 › Pierre Baret

优化的图像卷积算法

convolution image-processing math algorithm c++

Pierre Baret · 技术社区 · 7 年前

我正在努力实施 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

由于这对于大图像和内核来说可能是一个很大的瓶颈,我想知道是否有其他方法可以加快速度?即使有其他输入信息,如:稀疏图像或内核、已知内核等。。。

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

3 回复 | 直到 7 年前

Cris Luengo 7 年前

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内核,可以从 ^2. 至2N次操作。

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

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

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

MBo 7 年前

对于较小的内核大小,简单的方法可能更快。还要注意的是 可分离核 (例如,高斯核是可分离的)如前所述,允许先按行再按列进行过滤,从而产生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 允许将内核应用于 1024x1024 5-30毫秒后拍摄图像。

Aaron Murgatroyd 5 年前

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