快速傅里叶变换算法适合图像梯度计算吗？

Question

我有一个大小为mXn的矩阵和我需要执行卷积的滤波器[-1 0 1]。我可以在O（n^2）步中做到这一点，但进一步的谷歌搜索快速傅里叶变换不断涌现。我想知道FFT是否适合这个问题。矩阵只有随机整数。但是如果我有浮动价值，它会有所作为吗？ FFT是否意味着像这样的问题？

Answer 1

如果你的过滤器只有两个非零元素，根据定义计算卷积将只需要O(n*m)步骤（这是你的数据的大小）。在这种情况下，FFT不会帮助你：2D FFT将采用类似O(n*m*(log n+log m))的东西。总结：当你有一个简单的本地化过滤器时，执行卷积的最好方法是直接计算总和。当您需要计算卷积或与更大数据的相关性（考虑与其他图像的相关性）或执行复杂的操作时，FFT可以为您提供帮助。