离散余弦变换

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

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

一个类似的变换, 改进的离散余弦变换被用在高级音频编码，Vorbis和MP3音频压缩当中。

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

形式上来看，离散余弦变换是一个线性的可逆函数${\displaystyle F:R^{n}\rightarrow R^{n}}$ 其中R是实数集，或者等价的说一个${\displaystyle n\times n}$ 的方阵。离散余弦变换有几种变形的形式， 它们都是根据下面的某一个公式把${\displaystyle n}$ 个实数${\displaystyle x_{0},\ldots ,x_{n-1}}$ 变换到另外${\displaystyle n}$ 个实数${\displaystyle f_{0},\ldots ,f_{n-1}}$ 的操作。

DCT-I

${\displaystyle f_{m}={\frac {1}{2}}(x_{0}+(-1)^{m}x_{n-1})+\sum _{k=1}^{n-2}x_{k}\cos \left[{\frac {\pi }{n-1}}mk\right]}$ 

有些人认为应该将${\displaystyle x_{0}}$ 和${\displaystyle x_{n-1}}$ 乘以${\displaystyle {\sqrt {2}}}$ ，相应的将${\displaystyle f_{0}}$ 和${\displaystyle f_{n-1}}$ 乘以${\displaystyle {\frac {1}{\sqrt {2}}}}$ 。这样做的结果是这种DCT-I矩阵变为了正交矩阵（再乘一个系数的话），但是这样就不能直接和一个实偶离散傅里叶变换对应了。

一个${\displaystyle n=5}$ 的对实数abcde的DCT-I型变换等价于一个8点的对实数abcdedcb（偶对称）的DFT变换，结果再除以2（对应的，DCT-II~DCT-IV相对等价的DFT有一个半个抽样的位移）。需要指出的是，DCT-I不适用于${\displaystyle n<2}$ 的情况（其它的DCT类型都适用于所有的整数n）。

所以，DCT-I暗示的边界条件是：${\displaystyle x_{k}}$ 相对于${\displaystyle k=0}$ 点偶对称，并且相对于${\displaystyle k=n-1}$ 点偶对称； 对${\displaystyle f_{m}}$ 的情况也类似。

DCT-II

${\displaystyle f_{m}=\sum _{k=0}^{n-1}x_{k}\cos \left[{\frac {\pi }{n}}m\left(k+{\frac {1}{2}}\right)\right]}$ 

DCT-II大概是最常用的一种形式，通常直接被称为DCT。

有些人更进一步的将${\displaystyle f_{0}}$ 再乘以${\displaystyle {\frac {1}{\sqrt {2}}}}$ （参见下面的DCT-III型的对应修改）。这将使得DCT-II成为正交矩阵（再乘一个系数的话），但是这样就不能直接和一个有半个抽样位移的实偶离散傅里叶变换对应了。

所以，DCT-II暗示的边界条件是：${\displaystyle x_{k}}$ 相对于${\displaystyle k=-{\frac {1}{2}}}$ 点偶对称，并且相对于${\displaystyle k=n-{\frac {1}{2}}}$ 点奇对称； 对${\displaystyle f_{m}}$ 相对于${\displaystyle m=0}$ 点偶对称，并且相对于${\displaystyle m=n}$ 点奇对称。

DCT-III

${\displaystyle f_{m}={\frac {1}{2}}x_{0}+\sum _{k=1}^{n-1}x_{k}\cos \left[{\frac {\pi }{n}}\left(m+{\frac {1}{2}}\right)k\right]}$ 

因为这是DCT-II的逆变换（再乘一个系数的话），这种变形通常被简单的称为逆离散余弦变换。

有些人更进一步的将${\displaystyle x_{0}}$ 再乘以${\displaystyle {\sqrt {2}}}$ （参见上面的DCT-II型的对应修改），这将使得DCT-III成为正交矩阵（再乘一个系数的话），但是这样就不能直接和一个结果有半个抽样位移的实偶离散傅里叶变换对应了。

所以，DCT-III暗示的边界条件是：${\displaystyle x_{k}}$ 相对于${\displaystyle k=0}$ 点偶对称，并且相对于${\displaystyle k=n}$ 点奇对称； 对${\displaystyle f_{m}}$ 相对于${\displaystyle m=-{\frac {1}{2}}}$ 点偶对称，并且相对于${\displaystyle m=n-{\frac {1}{2}}}$ 点偶对称。

DCT-IV

${\displaystyle f_{m}=\sum _{k=0}^{n-1}x_{k}\cos \left[{\frac {\pi }{n}}\left(m+{\frac {1}{2}}\right)\left(k+{\frac {1}{2}}\right)\right]}$ 

DCT-IV对应的矩阵是正交矩阵（再乘一个系数的话）。

一种DCT-IV的变形，将不同的变换的数据重叠起来，被称为改进的离散余弦变换。

DCT-IV暗示的边界条件是：${\displaystyle x_{k}}$ 相对于${\displaystyle k=-{\frac {1}{2}}}$ 点偶对称，并且相对于${\displaystyle k=n-{\frac {1}{2}}}$ 点奇对称；对${\displaystyle f_{m}}$ 类似。

DCT V~VIII

上面提到的DCT I~IV是和偶数阶的实偶DFT对应的。原则上，还有四种DCT变换（Martucci, 1994）是和奇数阶的实偶DFT对应的，它们在分母中都有一个${\displaystyle n+{\frac {1}{2}}}$ 的系数。但是在实际应用中，这几种变型很少被用到。

最平凡的和奇数阶的实偶DFT对应的DCT是1阶的DCT（1也是奇数），可以说变换只是乘上一个系数${\displaystyle a}$ 而已，对应于DCT-V的长度为1的状况。

DCT-I的反变换是把DCT-I乘以系数${\displaystyle {\frac {2}{n-1}}}$ 。 DCT-IV的反变换是把DCT-IV乘以系数${\displaystyle {\frac {2}{n}}}$ 。 DCT-II的反变换是把DCT-III乘以系数${\displaystyle {\frac {2}{n}}}$ ，反之亦然。

和离散傅里叶变换类似，变化前面的归一化系数仅仅是常规而已，改变这个系数并不改变变换的性质。例如，有些人喜欢在DCT-II变换的前面乘以${\displaystyle {\sqrt {\frac {2}{n}}}}$ ，这样反变换从形式上就和变换更相似，而不需要另外的归一化系数。

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

以下简单介绍两种利用DFT来计算DCT-II的方法

方法一^[1]

令输入信号为${\displaystyle x(n)\,,n=0,1,...,N-1}$ 

并将${\displaystyle y(n)}$ 以${\displaystyle x(n)}$ 在${\displaystyle (2N-1)/2}$ 处对称表示

即${\displaystyle y(n)=\left\{{\begin{matrix}x(n),&{\mbox{if }}n=0,1,...,N-1\\x(2N-n-1),&{\mbox{if }}n=N,N+1,...2N-1\end{matrix}}\right.}$ 

此时令${\displaystyle W_{2N}}$  表示 ${\displaystyle e^{\frac {-j2\pi }{2N}}}$ 

则${\displaystyle y(n)}$ 之DFT为

${\displaystyle Y(m)=\Sigma _{n=0}^{2N-1}y(n)W_{2N}^{nm}}$ 

将${\displaystyle Y(m)}$  做以下化简

${\displaystyle {\begin{aligned}Y(m)&=\sum _{n=0}^{N-1}y(n)W_{2N}^{nm}+\sum _{n=N}^{2N-1}y(n)W_{2N}^{nm}\\&=\sum _{n=0}^{N-1}y(n)W_{2N}^{nm}+\sum _{n=N}^{2N-1}x(2N-n-1)W_{2N}^{nm}\\&=\sum _{n=0}^{N-1}y(n)W_{2N}^{nm}+\sum _{n=0}^{N-1}x(n)W_{2N}^{(2N-n-1)m}\\&=\sum _{n=0}^{N-1}x(n)[W_{2N}^{nm}+W_{2N}^{-(n+1)m}],\,\,\,\,m=0,1,...,2N-1\end{aligned}}}$ 

此时两侧同乘 ${\displaystyle {\frac {1}{2}}W_{2N}^{m/2}}$ 

可得${\displaystyle {\frac {1}{2}}W_{2N}^{m/2}Y(m)=\sum _{n=0}^{N-1}x(n)\cos {[(2n+1){\frac {m\pi }{2N}}]},\,\,\,\,\,\,m=0,1,...,N-1}$ 

此时右式即为欲求之DCT转换，而左式可借由2N点数的DFT来计算，使用快速算法的情况下，运算之时间复杂度为${\displaystyle O(NlogN)}$ 

方法二 ^[2]

第二个方法由Narasimha与Peterson在1978年提出，此方法系借由巧妙的编排${\displaystyle y(n)}$ 来达成，首先令

${\displaystyle y(n)=x(2n)}$  并且 ${\displaystyle y(N-1-n)=x(2n+1),\,\,\,\,\,\,n=0,1,...,{\frac {N}{2}}-1}$ 

此时X(m)可化简为

${\displaystyle X(m)=\sum _{n=0}^{N/2-1}y(n)\cos {[{\frac {(4n+1)m\pi }{2N}}]}+\sum _{n=0}^{N/2-1}y(N-n-1)\cos {[{\frac {(4n+3)m\pi }{2N}}]},\,\,\,\,\,\,\,m=0,1,...,N-1}$ 

令第二项之${\displaystyle n}$ 改为 ${\displaystyle n'=N-1-n}$ ，则两式可合并为

${\displaystyle X(m)=\sum _{n=0}^{N-1}y(n)\cos {[{\frac {(4n+1)m\pi }{2N}}]},\,\,\,\,\,\,m=0,1,...,N-1}$ 

右侧为对${\displaystyle y(n)}$ 之N点的scaled DFT

因此，${\displaystyle X(m)=Re[Z(m)]}$ ，其中

${\displaystyle Z(m)=W_{4N}^{m}Y(m)=W_{4N}^{m}\sum _{n=0}^{N-1}y(n)W_{N}^{nm},\,\,\,\,\,\,\,m=0,1,...,N-1}$ 

其中${\displaystyle Y(m)}$  是对${\displaystyle y(n)}$ 之N点的DFT，并且可以简单的验证${\displaystyle Z(m)}$ 具有如下性质

${\displaystyle Z(N-m)=-jZ(m)^{*}}$ 

而因${\displaystyle y(n)}$  为实数输入，

因此欲求之${\displaystyle X(m)=Re[Z(m)]}$  ，${\displaystyle X(N-m)=-Im[Z(m)],\,\,\,\,\,\,\,m=0,1,...,{\frac {N}{2}}}$ 

在使用FFT快速算法的情况下，运算之时间复杂度同样为${\displaystyle O(NlogN)}$ 

但此方法较方法一直接运算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 （页面存档备份，存于互联网档案馆）

• 离散余弦变换 （页面存档备份，存于互联网档案馆）

1. ^ Rao, R. K., & Yip, P. (1990). Discrete Cosine Transform: Algorithms, Advantages, Applications (1st ed.). Academic Press.
2. ^ On the Computation of the Discrete Cosine Transform. (1978, June 1). IEEE Journals & Magazine | IEEE Xplore. https://ieeexplore.ieee.org/document/1094144 （页面存档备份，存于互联网档案馆）