离散余弦变换

天下维客，你可以修改的网络知识库

离散余弦变换(dct for discrete cosine transform)是与傅里叶变换相关的一种变换，它类似于离散傅里叶变换(dft for discrete fourier transform),但是只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换，这个离散傅里叶变换是对一个实偶函数进行的(因为一个实偶函数的傅里叶变换仍然是一个实偶函数)，在有些变形里面需要将输入或者输出的位置移动半个单位(dct有8种标准类型，其中4种是常见的)。

最常用的一种离散余弦变换的类型是下面给出的第二种类型，通常我们所说的离散余弦变换指的就是这种。它的逆，也就是下面给出的第三种类型，通常相应的被称为"反离散余弦变换"，"逆离散余弦变换"或者"idct"。

有两个相关的变换，一个是离散正弦变换(dst for discrete sine transform),它相当于一个长度大概是它两倍的实奇函数的离散傅里叶变换；另一个是改进的离散余弦变换(mdct for modified discrete cosine transform),它相当于对交叠的数据进行离散余弦变换。

应用

离散余弦变换，尤其是它的第二种类型，经常被信号处理和图像处理使用，用于对信号和图像(包括静止图像和运动图像)进行有损数据压缩。这是由于离散余弦变换具有很强的"能量集中"特性:大多数的自然信号(包括声音和图像)的能量都集中在离散余弦变换后的低频部分，而且当信号具有接近马尔科夫过程(markov processes)的统计特性时，离散余弦变换的去相关性接近于k-l变换(karhunen-loève 变换--它具有最优的去相关性)的性能。

例如，在静止图像编码标准jpeg中，在运动图像编码标准mjpeg和mpeg的各个标准中都使用了离散余弦变换。在这些标准制中都使用了二维的第二种类型离散余弦变换，并将结果进行量化之后进行熵编码。这时对应第二种类型离散余弦变换中的n通常是8，并用该公式对每个8x8块的每行进行变换，然后每列进行变换。得到的是一个8x8的变换系数矩阵。其中(0,0)位置的元素就是直流分量，矩阵中的其他元素根据其位置表示不同频率的交流分类。

一个类似的变换, 改进的离散余弦变换被用在高级音频编码(aac for advanced audio coding)，vorbis 和 mp3 音频压缩当中。

离散余弦变换也经常被用来使用谱方法来接偏微分方程，这时候离散余弦变换的不同的变量对应着数组两端不同的奇/偶边界条件。

计算

尽管直接使用公式进行变换需要进行o(n2)次操作，但是和快速傅里叶变换类似，我们有复杂度为o(nlog(n))的快速算法，这就是常常被称做蝶形变换的一种分解算法。另外一种方法是通过快速傅里叶变换来计算dct，这时候需要o(n)的预操作和后操作。

参考

k. r. rao and p. yip, 离散余弦变换 : 算法、优点和应用 (discrete cosine transform: algorithms, advantages, applications) (academic press, boston, 1990).

a. v. oppenheim, r. w. schafer, and j. r. buck, 时间离散信号处理 (discrete-time signal processing), second edition (prentice-hall, new jersey, 1999).

s. a. martucci, 对称卷积和离散正弦余弦变换 (symmetric convolution and the discrete sine and cosine transforms), ieee trans. sig. processingsp-42, 1038-1051 (1994).

matteo frigo and steven g. johnson: fftw, 1 一个免费的c语言库gpl，可以计算dct-i~iv的1维到多维的任意大小的变换

m. frigo and s. g. johnson, "fftw3的设计和实现," proceedings of the ieee93 (2), 216–231 (2005).