我成功地使用经典算法计算了图像的2d-dct,并将其用作一维数组的组合。这2种方法的时间复杂度分别为n^ 4和n^ 3。
在图像上实现时,需要很长时间来计算。像一个512×512的图像使用7分钟,使用一个具有N ^ 3复杂度的图像。
有没有其他算法来计算具有最小时间复杂度的DCT?
但是,Matlab是怎么做到这么快的呢?
最佳答案
有两种常用的快速离散余弦变换方法。
离散余弦变换
1d dct可以从O(n)
中的1d dft导出,因此当应用fft算法时,1d中的O(n.log(n))
和2d中的O(n^2.log(n))
分别得到。有关更多信息,请参见:
I am looking for a simple algorithm for fast DCT and IDCT of matrix [NxM]
这种方法使用得更多,因为它更容易实现有更多的方法可以从DFT中得到DCT,有些使用相同的数组大小,而另一些使用双大小的DFT。
快速离散余弦变换
也有快速的离散余弦变换方程,但他们不常用,因为他们不是很有名,也没有很好的文件在线。另一个更重要的一点是递归分解涉及到DCT和DST,并且分割通常是3个therms而不是2个therms,这使得实现更加困难我们还需要快速的DST实现,它类似于DCT,所以它也可以分解为3therms,同时使用DCT和DST好的一面是它不涉及复杂的领域,但是正如您可以想象的那样,与1相比,需要更多的代码。
通过快速搜索我找到了这个
The fast DCT-IV/DST-IV computation via the MDCT
但是在实际领域中寻找快速dct的相关信息是一个问题,因为大多数文章要么是硬连线(constantn
)实现,要么是使用方法1。当你发现某样东西时,它通常包含错误而不起作用。这种方法的最佳选择是找到一些关于计算机图形学或离散数学的旧论文或书。
关于algorithm - 低复杂度的DCT,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/45545089/