考虑用正方形、可分离的图像。$n\times n$$m\times m$

1. 给出以下方法的计算时间的一般方程：

   • 使用 FFT 过滤
   • 二维卷积
   • 两个一维卷积

使用大写字母表示依赖于实现的常量。

2. 对于第 1 部分中过滤方法的特定实现）记录了以下计算时间：

   n=64 m=3 FFT=2,498,561 2-D 卷积=73,829 两个 1-D 卷积=245,761
   n=256 m=5 FFT=53,084,161 二维卷积=1,179,649 两个一维卷积=3,932,161
   n=1024 m=3 FFT=1,059,061,761 二维卷积=18,874,369 两个一维卷积=62,914,561
   n=1024 m=11 FFT=1,059,061,761 二维卷积=471,859,201 两个一维卷积=314,572,801
   

   将与实现相关的常量的值估计为 1)

3. 对于 2) 中的实现，给出预期 FFT 实现最快和$m$$n$

关于我的观点：

• FFT 是：首先对每一列分别应用 FFT，然后对每一行应用 FFT。个数据点的FFT大约需要次乘法，对于图像，它将是次乘法。其次，逆 FFT 以恢复合理的图像。另一个。第三，乘以核的 FT，就是复数乘法，即实数乘法。因此，FFT 的计算时间为。那是对的吗？$N$$2N\log N$$n\times n$$2n\cdot 2n\cdot\log n$$2n\cdot 2n\cdot \log n$$n^2$$4\cdot n^2$$\mathcal O_1\left(8\cdot n^2\log n +4\cdot n^2\right)$
• 二维卷积：我对此感到困惑。它可能是。这是正确的吗？$\mathcal O_2\left(n^2\cdot m^2\right)$
• 两个一维卷积：首先，每行卷积。它应该是。其次，转置图像的矩阵。这个过程会包括计算时间吗？第三，再次对行进行卷积。另一个。第四，第二次转置，将图像恢复到原来的方向。计算方程为。$(n+m-1)^2$$(n+m-1)^2$$\mathcal O_3\left(2\cdot\left(n+m-1\right)^2\right)$

但是，根据我的计算方程，我不能将我的方程与记录的计算时间妥协。这样，我认为我需要修正我的方程来解决第 3 部分中的问题）。