algorithm - 快速傅立叶变换算法是否适合图像梯度计算？

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 可以帮助您。