giz*_*gok 2 algorithm fft image-processing
我有一个大小矩阵mXn和一个[-1 0 1]我需要执行卷积的滤波器.我能够在O(n ^ 2)步骤中做到这一点,但是进一步谷歌搜索快速傅里叶变换继续弹出到处.我想知道FFT是否适合这个问题.矩阵只有随机整数.但如果我有浮动值,它会有所作为吗？FFT是否适合这样的问题？
如果您的过滤器只有两个非零元素,按定义计算卷积只会采取O(n*m)步骤(这是您的数据的大小).在这种情况下,FFT不会对你有所帮助:2D FFT会采取类似的方式O(n*m*(log n+log m)).
总结一下:当你有一个简单的局部滤波器时,执行卷积的最佳方法是直接计算总和.当您需要使用更大的数据计算卷积或相关性(考虑与其他图像的相关性)或执行复杂的操作时,FFT可以帮助您.