DCT(离散余弦变换(DiscreteCosineTransform))

xpp02

浏览: 1048917 次

最近访客更多访客>>

xutao2811

andylao62

u012363178

prestlhh

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

离散余弦变换（Discrete Cosine Transform，简称DCT变换）是一种与傅立叶变换紧密相关的数学运算。在傅立叶级数展开式中，如果被展开的函数是实偶函数，那么其傅立叶级数中只包含余弦项，再将其离散化可导出余弦变换，因此称之为离散余弦变换。

离散余弦变换(Discrete Cosine Transform)

离散余弦变换（DCT）是N.Ahmed等人在1974年提出的正交变换方法。它常被认为是对语音和图像信号进行变换的最佳方法。为了工程上实现的需要，国内外许多学者花费了很大精力去寻找或改进离散余弦变换的快速算法。由于近年来数字信号处理芯片（DSP）的发展，加上专用集成电路设计上的优势，这就牢固地确立离散余弦变换（DCT）在目前图像编码中的重要地位，成为H.261、JPEG、MPEG 等国际上公用的编码标准的重要环节。在视频压缩中，最常用的变换方法是DCT,DCT被认为是性能接近K-L变换的准最佳变换，变换编码的主要特点有：　　（1）在变换域里视频图像要比空间域里简单。　　（2）视频图像的相关性明显下降，信号的能量主要集中在少数几个变换系数上，采用量化和熵编码可有效地压缩其数据。　　（3）具有较强的抗干扰能力，传输过程中的误码对图像质量的影响远小于预测编码。通常,对高质量的图像，DMCP要求信道误码率，而变换编码仅要求信道误码率。　　DCT等变换有快速算法，能实现实时视频压缩。针对目前采用的帧内编码加运动补偿的视频压缩方法的不足, 我们在Westwater 等人提出三维视频编码的基础上, 将三维变换的结构应用于视频图像压缩, 进一步实现了新的视频图像序列的编码方法。

离散余弦变换（英语：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 音频压缩当中。

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

正式定义

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

DCT-I

$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} m k \right]$

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

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

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

DCT-II

$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。

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

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

DCT-III

$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的逆变换(再乘一个系数的话)，这种变形通常被简单的称为逆离散余弦变换。

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

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

DCT-IV

$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暗示的边界条件是： $x_k$ 相对于 $k=-\frac{1}{2}$ 点偶对称，并且相对于 $k=''n''-1/2$ 点奇对称；对 $j$ 类似。

DCT V~VIII

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

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

反变换

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

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

计算

尽管直接使用公式进行变换需要进行 $O(n^2)$ 次操作，但是和快速傅里叶变换类似，我们有复杂度为 $O(n \log(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. 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).

应用