图像卷积的fft实现验证（python）
１、Caffe的卷积操作时间主要在矩阵乘法，假设一个m*n卷积核，且输入通道数为１，输出特征图大小为h*w，则乘法个数m*n*h*w,这里的优化仅限于对矩阵的乘法优化，因此，只要选择适合的矩阵计算库就可以了。
２、若使用FFT来计算图像卷积。其主要步骤如下。
假设输入图像的大小为len=h*w，卷积核大小k_len＝m*n；通常len>>k_len；
-
对输入图像A做FFT，其算法的时间复杂度为o(lenlglen)；
-
对卷积核B做FFT，但是由于卷积核与输入图像尺寸不一样，需要将卷积核扩展，即将卷积核倒置后，补len-k_len个０。
-
将A、B傅里叶变换的结果相乘，即对应位相乘获得结果C。乘法个数为len，时间复杂度为o(len)
-
对C做IFFT，得到结果D，在D中每隔k_len的值实部取出来，就是图像卷积的结果。因为图像卷积其实就是对应位相乘，所以需要每隔k_len取值，时间复杂度为o(len)
假设卷积核个数>1，需要对卷积核重新扩展后重复２）３）４）步骤，并与上一个卷积核图像卷积的值对应位相加就能获得。
验证正确性：
输入图像的卷积顺序-1,1,3,8 2,43,1,3 1,3,1,3 54,-2,-3,-1
卷积核1,2,-1,3
图像卷积结果：22,96,15,50.
此处注意，计算结果是用卷积核与输入图像进行乘法累加。
使用FFT结果：22,96,15,50。
此处注意，将卷积核逆置。
结果正确
暂时未能看出此方法的优越性，从空间上看，需要对卷积核进行扩展，其空间大小与输入图像的尺寸大小一样。时间上分析，仅二者FFT对应相乘的时间的乘法个数就和矩阵乘法个数的数量级是一样的了（当len>>k_len时）。适用于卷积核尺寸较大的情景。
图２出处：https://core.ac.uk/download/pdf/24989291.pdf
虽然没理解为什么性能提升这么多，但是该论文所做的实验证明了FFT性能很好，虽然复杂度推导跟我推导的差不多～此论文用了cuFFT库
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
至于多通道，多卷积核的，经python验证，卷积结果正确，其大概步骤如下：
水平有限，出错之处，希望得到各位的指正。