algorithm - 低复杂度的DCT

Question

我使用经典算法成功计算了图像的 2d dct，并结合使用了 1d 数组。这两种方法的时间复杂度分别为 n^4 和 n^3。在图像上实现时需要很长时间才能计算。例如使用复杂度为 n^3 的 512 x 512 图像需要 7 分钟。

是否有任何其他算法来计算具有最小时间复杂度的 DCT？

不过，matlab 是如何做到这么快的呢？

Answer 1

有两种常见的快速DCT方法。

1. DFT 的 DCT

   1D DCT 可以在 O(n) 中从 1D DFT 导出，因此当应用 FFT 算法时1D 的 O(n.log(n)) 和 的 O(n^2.log(n))二维。有关详细信息，请参阅:

   • I am looking for a simple algorithm for fast DCT and IDCT of matrix [NxM]

   这种方法被更多地使用，因为它更容易实现。关于如何从 DFT 导出 DCT 的方法有很多，一些使用相同的数组大小，另一些使用双倍大小的 DFT。

2. 快速 DCT

   还有一些快速的 DCT 方程，但它们并不常用，因为它们不是很出名，也没有很好的在线记录。另一个更重要的一点是，递归分解涉及DCT 和DST，并且通常拆分为 3 个而不是 2 个，这使得实现更加困难。而且我们还需要快速的 DST 实现，它类似于 DCT 因此它也分解为 3 个热量并且同时使用 DCT 和 夏令时。好的一面是它不涉及复杂的领域，但正如您可以想象的那样，与 #1 相比，它需要更多的代码。

   通过快速搜索我找到了这个

   • The fast DCT-IV/DST-IV computation via the MDCT

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