离散余弦变换(英語:discrete cosine transform, DCT)是与傅里叶变换相关的一种变换,类似于离散傅里叶变换,但是只使用实数。离散余弦变换相当于一个长度大概是它两倍的离散傅里叶变换,这个离散傅里叶变换是对一个实偶函数进行的(因为一个实偶函数的傅里叶变换仍然是一个实偶函数),在有些变形里面需要将输入或者输出的位置移动半个单位(DCT有8种标准类型,其中4种是常见的)。
最常用的一种离散余弦变换的类型是下面给出的第二种类型,通常我们所说的离散余弦变换指的就是这种。它的逆,也就是下面给出的第三种类型,通常相应的被称为「反离散余弦变换」,「逆离散余弦变换」或者「IDCT」。
有两个相关的变换,一个是离散正弦变换,它相当于一个长度大概是它两倍的实奇函数的离散傅里叶变换;另一个是改进的离散余弦变换,它相当于对交叠的数据进行离散余弦变换。
离散余弦变换,尤其是它的第二种类型,经常被信号处理和图像处理使用,用于对信号和图像进行有损数据压缩。这是由于离散余弦变换具有很强的「能量集中」特性:大多数的信号資訊(包括声音和图像)往往集中在离散余弦变换后的低频部分,而且当信号具有接近马尔可夫过程的统计特性时,离散余弦变换的去相关性接近于K-L变换(Karhunen-Loève变换——它具有最优的去相关性)的性能。
例如,在图像编码标准JPEG與視訊编码标准MJPEG和MPEG的各个标准中都使用了离散余弦变换。在这些标准制中都使用了二维的第二种类型离散余弦变换,并将结果进行量化之后进行熵编码。这时对应第二种类型离散余弦变换中的n通常是8,并用该公式对每个8x8块的每行进行变换,然后每列进行变换。得到的是一个8x8的变换系数矩阵。其中(0,0)位置的元素就是直流分量,矩阵中的其他元素根据其位置表示不同频率的交流分量。
一个类似的变换,改进的离散余弦变换被用在高级音频编码、Vorbis和MP3音频压缩当中。
离散余弦变换也经常被用来使用谱方法来解偏微分方程,这时候离散余弦变换的不同的变量对应着数组两端不同的奇/偶边界条件。
上面提到的DCT I~IV是和偶数阶的实偶DFT对应的。原则上,还有四种DCT变换(Martucci, 1994)是和奇数阶的实偶DFT对应的,它们在分母中都有一个的系数。但是在实际应用中,这几种变型很少被用到。
最平凡的和奇数阶的实偶DFT对应的DCT是1阶的DCT(1也是奇数),可以说变换只是乘上一个系数而已,对应于DCT-V的长度为1的状况。
尽管直接使用公式进行变换需要进行次操作,但是和快速傅里叶变换类似,我们有复杂度为的快速算法,这就是常常被称做蝶形变换的一种分解算法。另外一种方法是通过快速傅里叶变换来计算DCT,这时候需要的预操作和后操作。
以下簡單介紹兩種利用DFT來計算DCT-II的方法
令輸入信號為
並將以在處對稱表示
即
此時令 表示
則之DFT為
將 做以下化簡
此時兩側同乘
可得
此時右式即為欲求之DCT轉換,而左式可藉由2N點數的DFT來計算,使用快速演算法的情況下,運算之時間複雜度為
第二個方法由Narasimha與Peterson在1978年提出,此方法係藉由巧妙的編排來達成,首先令
並且
此時X(m)可化簡為
令第二項之改為 ,則兩式可合併為
右側為對之N點的scaled DFT
因此,,其中
其中 是對之N點的DFT,並且可以簡單的驗證具有如下性質
而因 為實數輸入,
因此欲求之 ,
在使用FFT快速演算法的情況下,運算之時間複雜度同樣為
但此方法較方法一直接運算2N點數的DFT快上約2倍。
- 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. Processing SP-42, 1038-1051 (1994).
- Matteo Frigo and Steven G. Johnson: FFTW, http://www.fftw.org/ (页面存档备份,存于互联网档案馆). 一个免费的C语言库GPL,可以计算DCT-I~IV的1维到多维的任意大小的变换
- M. Frigo and S. G. Johnson, "FFTW3的设计和实现 (页面存档备份,存于互联网档案馆)," Proceedings of the IEEE 93 (2), 216–231 (2005).
- On the Computation of the Discrete Cosine Transform. (1978, June 1). IEEE Journals & Magazine | IEEE Xplore. https://ieeexplore.ieee.org/document/1094144 (页面存档备份,存于互联网档案馆)
- ^ 引用错误:没有为名为
Luo
的参考文献提供内容
- ^ 4.0 4.1 引用错误:没有为名为
Stankovic
的参考文献提供内容
- ^ 引用错误:没有为名为
Britanak
的参考文献提供内容
- ^ 6.0 6.1 引用错误:没有为名为
Hersent
的参考文献提供内容
- ^ 7.0 7.1 引用错误:没有为名为
AppleInsider standards 1
的参考文献提供内容
Rao, R. K., & Yip, P. (1990). Discrete Cosine Transform: Algorithms, Advantages, Applications (1st ed.). Academic Press.