如何在R中执行*快速* DCT（离散余弦变换）？ [英] How to perform a *Fast* DCT (Discrete Cosine Transform) in R?

问题描述

使用Rprof揭示了dtt包中的dct是运行缓慢的R代码中的主要犯罪者。将它交换到stats包中的fft中（这不是相同的转换，但是应该花费相同的时间来计算），我的运行时间大大提高了。实际上，我的Rprof行中的2/3以前是dct调用，而切换后只有3条约600条是fft调用。

Using Rprof revealed the dct in the dtt package to be the main offender in a piece of R code that was running quite slowly. Swapping it out for fft in the stats package (which is not the same transformation, but should take the same time to compute) my run time improved dramatically. In fact 2/3 of my Rprof lines were dct calls previously and a mere 3 lines of about 600 were fft calls after making the switch.

dtt软件包不使用快速离散傅立叶变换完成吗？如果是这样，是否有一个包含一个包装？ （我知道可以将数据加倍，然后从这些fft系数中提取dct的系数，但是直接的快速dct肯定会更好，并且确实应该在某个地方是一个）。

Is the dct implementation in the dtt package not done using the fast discrete fourier transform? If so, is there a package that does have one? (I know one could double ones data, then extract coefficients for the dct from those fft coefficients, but a straight fast dct would certainly be nicer, and there really ought to be one somewhere).

推荐答案

似乎没有快速dct，但是统计数据包中有一个fft（快速傅立叶变换），所以这是您的方法可以使用fft获得快速dct。

There appears to be no fast dct, but there is an fft (fast fourier transform) in the stats package, so here is how you could go about getting the fast dct using fft.

使用此方法需您自担风险。我还没有做任何认真的检查。我在几个不同大小的向量上进行了检查，结果与软件包dtt中的函数dct相同。如果有人想通过将其与dct的输出进行比较来仔细检查我，则可以随意进行这样，然后发布结果。

Use this at your own risk. I haven't done any serious checking of it. I checked it on a couple of vectors of different sizes and it gave the same results as function dct in package dtt on those. If anyone wants to double check me by comparing it to the output from dct then feel free to do so and post your results.

取向量并将其扩展为向量的时间是以下情况的两倍：如果向量为v =（1,2,3），则将条目加倍至w =（1,2,3,3,2,1）。 请注意顺序。如果向量为v =（1,2,4,9），则将输入项翻倍至w =（1,2,4,9,9,4,2,1）

Take your vector and extend it to a vector twice as long as follows: If your vector is v=(1,2,3) then double the entries to w=(1,2,3,3,2,1). Note the ordering. If your vector is v=(1,2,4,9) then double the entries to w=(1,2,4,9,9,4,2,1)

让N为原始向量的长度（在将其长度加倍之前）。

Let N be the length of your ORIGINAL vector (before you doubled its length).

然后第一个N个系数
.5 * fft（w）/ exp（complex（imaginary = pi / 2 / N）*（seq（2 * N）-1））
应该与计算$ b $一致b dct（v）
，但在几乎所有情况下都应该更快。

Then the first N coefficients of .5 * fft(w)/exp(complex(imaginary=pi / 2 / N)*(seq(2*N)-1)) should agree with computing dct(v) except it should be dramatically faster in almost all cases.

速度注意事项。如果您使用质数N，那么计算快速dct所花费的时间就好比对每个这些质因数进行缓慢dct所花费的时间。因此，如果N为2 ^ K，就好比对长度为2的向量进行K个不同的慢速dct转换，因此其 really 很快。如果N是素数（最坏的情况），则根本不会加快速度。向量的最大加速是长度为2的幂。

Speed considerations. If you prime factor N then the time it takes to compute the fast dct is like the time it takes to do a slow dct for each of those prime factors. So if N is 2^K it is like doing a K different slow dct transforms on a vector of length two, so its really fast. If N is prime (worst case scenario) then there is no speed up at all. The greatest speedup is on vectors that are a power of two in length.

注意：上面的R代码看起来非常不友好，所以让我说说这是怎么回事以正确的方式将长度加倍后，得到的fft的前N个系数几乎是正确的。但是，系数需要进行一些调整。令P代表e ^（pi * i / 2 / N）。不理会第一个系数。将第二个系数除以P，将第三个系数除以P ^ 2，将第四个系数除以P ^ 3，依此类推...然后将 all 系数除以2（包括第一个系数）以与R用于dct的归一化。

Note: The R code above looks incredibly unfriendly, so let me say what is going on. After doubling the length in the right way, the first N coefficients of the fft you get are almost the right thing. However the coefficients need to be tweaked a bit. Let P stand for e^(pi * i / 2 / N). Leave the first coefficient alone. Divide the second coefficient by P, divide the third by P^2, divide the fourth by P^3, etc... Then divide all the coefficients by 2 (including the first one) to agree with the normalization R uses for the dct.

此应该具有与在dtt包中使用dct函数相同的功能，但在几乎所有情况下都更快。

This should give the same thing as using the dct function in package dtt but be dramatically faster in almost all cases.

这篇关于如何在R中执行*快速* DCT（离散余弦变换）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！