低复杂度DCT

Question

我成功地计算了一幅图像的二维离散余弦变换( dct )，使用了经典的算法，并将其作为一维阵列的组合。这两种方法的时间复杂度分别为n^4和n^3。在图像上实现时，需要很长时间才能计算。使用n^3复杂度的图像，就像对512 x 512图像的7分钟。

还有其他算法可以计算最小时间复杂度的DCT吗？

但是matlab是如何这么快做到这一点的呢？

Answer 1

快速离散余弦变换有两种常用的方法。

1. DFT中的离散余弦变换 一维离散余弦变换可以从O(n)中的1D DFT中导出，所以当应用FFT算法时，可以得到1D<代码>E 215和O(n^2.log(n))用于E 1172D<代码>E 218的O(n.log(n))。有关更多信息，请参见：

- [I am looking for a simple algorithm for fast DCT and IDCT of matrix [NxM]](https://stackoverflow.com/a/22779268/2521214)

由于该方法更易于实现，因此使用得更多。关于如何从DFT导出DFT有更多的方法，有些使用相同的数组大小，而另一些则使用双大小的DFT。

1. 快速离散余弦变换 还有快速的，离散余弦变换，方程，但它们不常用，因为它们不是很出名，也没有很好的记录在网上。另一个更重要的要点是递归分解涉及到、DCT、和DST，通常将其拆分为3，而不是2，这使得实现更加困难。此外，我们还需要快速的DST实现，它类似于DCT，因此它也可以分解为三个温度，并且使用DCT和DST。好的一面是它不涉及复杂的域，但是可以想象，与#1相比，需要更多的代码。 通过快速搜索，我找到了这个

- [The fast DCT-IV/DST-IV computation via the MDCT](http://www.sciencedirect.com/science/article/pii/S0165168403001099)

但是要在实际域中找到有关快速、DCT、的相关信息是一个问题，因为大多数文章要么是硬连线(常数n)实现，要么是使用#1的方法。当你发现某件事时，它通常会产生错误，而且不起作用。这种方法的最佳选择是找到一些关于计算机图形学或离散数学的旧论文或书籍。