Matlab/Octave 使用哪种方法来实现 conv2 函数？

Question

Matlab/Octave 使用哪种方法来实现

conv2

函数？

是吗：

• 快速傅里叶变换
• 3 个或更多 for 循环，例如经典迭代
• 其他？

我正在寻找最快的方法

conv2

。我要为其编写 C 代码。

Answer 1

conv2

实现直接方法（即 4 个循环）。这不是 O(n⁴)，而是 O(nk)，其中 n 是图像中的像素数，k 是内核中非零像素的数量。

FFT 实现是 O(n log n)，与 k 无关，但常数相当大，因此您需要一个大的 k 来使其比直接实现更高效。

您可以通过比较计算

fft2(img)

与

conv2(img,ones(3,3))

所需的时间来简单地测试这一点：

img = ones(1024,1024);
k = ones(3,3);
timeit(@()fft2(img))
timeit(@()conv2(img,k,'same'))

ans =
    0.0059

ans =
    0.0015

通过 FFT 计算卷积需要 3 倍的

fft2

调用，再加上复数值乘法，因此在这种情况下比直接实现慢 12 倍以上。

请注意，MATLAB 的卷积实现非常高效，很难将其与您自己的 C++ 代码相匹配。不过，除非您的内核非常大，否则您不想使用 FFT。

您还可以看到

conv2

时间随着内核大小的增加而增加：

>> k = ones(7,7); timeit(@()conv2(img,k,'same'))
ans =
    0.0066

>> k = ones(19,19); timeit(@()conv2(img,k,'same'))
ans =
    0.0152