在二维图像处理中，为什么用FFT求卷积的速度比依照卷积定义直接计算要快
在二维图像处理中，为什么用FFT求卷积的速度比按照卷积定义直接计算要快？
比如说，求一个5*5和11*11矩阵的卷积，要先把两个矩阵扩充成16*16，再各自进行二维傅里叶变换，然后做点乘，将得到的16*16矩阵再进行一次逆傅里叶变换，得到二维卷积矩阵。可是光这三次傅里叶变换的计算复杂度就很高了，所需要的乘法次数差不多是256（点乘部分）+3*（16*16log(16)+16*16log(16)), 3为三次傅里叶变换，16log16是单行或者单列的一维傅里叶变换的复杂度，一个矩阵有16行，16列，所以又要各自乘以16，还不包括位倒序等各种运算。
但是，如果直接按照卷积定义计算的话，只需要25*121次乘法运算，比FFT来得要快得多。所以用FFT求卷积是不是有点得不偿失？
------解决思路----------------------
考虑一下高分辨率图像
1024×1024
甚至更高。
比如说，求一个5*5和11*11矩阵的卷积，要先把两个矩阵扩充成16*16，再各自进行二维傅里叶变换，然后做点乘，将得到的16*16矩阵再进行一次逆傅里叶变换，得到二维卷积矩阵。可是光这三次傅里叶变换的计算复杂度就很高了，所需要的乘法次数差不多是256（点乘部分）+3*（16*16log(16)+16*16log(16)), 3为三次傅里叶变换，16log16是单行或者单列的一维傅里叶变换的复杂度，一个矩阵有16行，16列，所以又要各自乘以16，还不包括位倒序等各种运算。
但是，如果直接按照卷积定义计算的话，只需要25*121次乘法运算，比FFT来得要快得多。所以用FFT求卷积是不是有点得不偿失？
------解决思路----------------------
考虑一下高分辨率图像
1024×1024
甚至更高。