离散余弦变换(DCT)及其应用

•离散余弦变换（DiscreteCosineTransform，DCT）的变换核为余弦函数。DCT除了具有一般的正交变换性质外，它的变换阵的基向量能很好地描述人类语音信号和图像信号的相关特征。因此，在对语音信号、图像信号的变换中，DCT变换被认为是一种准最佳变换。近年颁布的一系列视频压缩编码的国际标准建议中，都把DCT作为其中的一个基本处理模块。除此之外，DCT还是一种可分离的变换。离散余弦变换（DCT）及其应用离散余弦变换（DCT）及其应用•1.1一维离散余弦变换一维CT的变换核定义为:NuxNuCuxg2)12(cos2)(),((1-1)式中，x,u=0,1,2,…,N－1；其他1021)(uuC(1-2)一维DCT定义如下：设{f(x)|x=0,1,…,N-1}为离散的信号列。离散余弦变换（DCT）及其应用102)12(cos)(2)()(NxNuxxfNuCuF(1-3)式中，u,x=0,1,2,…,N－1将变换式展开整理后，可以写成矩阵的形式，即F=Gf(1-4)其中)2/)12)(1cos(()2/3)(1cos(()2/)1cos((/2)2/)12cos(()2/6cos()2/cos(/2)2/)12cos(()2/3cos()2/cos(/2111/1NNNNNNNNNNNNNNNNNNNG(1-5)离散余弦变换（DCT）及其应用一维DCT的逆变换IDCT定义为102)12(cos)()(2)(NuNuxuFuCNxf式中，x,u=0,1,2,…,N－1。可见一维DCT的逆变换核与正变换核是相同的。(1-6)•1.2二维离散余弦变换考虑到两个变量，很容易将一维DCT的定义推广到二维DCT。其正变换核为离散余弦变换（DCT）及其应用NvyMuxvCuCMNvuyxg2)12(cos2)12(cos)()(2),,,((1-7)式中，C(u)和C(v)的定义同式（7-48）；x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1。二维DCT定义如下：设f(x,y)为M×N的数字图像矩阵，则NvyMuxvCuCyxfMNvuFMxNy2)12(cos2)12(cos)()(),(2),(1010(1-8)离散余弦变换（DCT）及其应用式中：x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1二维DCT逆变换定义如下：NvyMuxvuFvCuCMNyxfMuNv2)12(cos2)12(cos),()()(2),(1010(1-9)式中：x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1。类似一维矩阵形式的DCT，可以写出二维DCT的矩阵形式如下：F=GfGT(1-10)离散余弦变换（DCT）及其应用同时，由式(1-8)和式(1-9)可知二维DCT的逆变换核与正变换核相同，且是可分离的，即NvyvCNMuxuCMvyguxgvuyxg2)12(cos)(22)12(cos)(2),(),(),,,(21(1-11)式中：C(u)和C(v)的定义同式（1-2）；x,u=0,1,2,…,M－1；y,v=0,1,2,…,N－1。离散余弦变换（DCT）及其应用通常根据可分离性，二维DCT可用两次一维DCT来完成，其算法流程与DFT类似，即),(),(]),([),(),()],([),(vuFvuFvxFFvxFvxFyxfFyxfTTT转置列转置行(1-12)•1.3快速离散余弦变换离散余弦变换（DCT）及其应用离散余弦变换的计算量相当大，在实用中非常不方便，也需要研究相应的快速算法。目前已有多种快速DCT（FCT），在此介绍一种由FFT的思路发展起来的FCT。首先，将f(x)延拓为0)()(xfxfex=0,1,2,…,N-1x=N，N+1,…,2N-1(1-13)离散余弦变换（DCT）及其应用按照一维DCT的定义，fe(x)的DCT10)(1)0(NxexfNF(1-14)NxujNxeNujNuxjNxeNxeNNxeNxeNNxNxNxexfeNexfNNuxxfNNuxxfNNuxxfNNuxNNuxxfNNuxxfNuF2212022)12(1201201210121010)(Re2})(Re{22)12(cos)(22)12(cos)(22)12(cos)(22)12(cos022)12(cos)(22)12(cos)(2)(式中，Re{·}表示取复数的离散余弦变换（DCT）及其应用由于为fe(x)的2N点DFT。因此，在作DCT时，可把长度为N的f(x)的长度延拓为2N点的序列fe(x)，然后对fe(x)作DFT，最后取DFT的实部便可得到DCT的结果。同理对于离散余弦逆变换IDCT，可首先将F(u)延拓为12022)(NxNxujeexf0)()(uFuFeu=0,1,2,…,N-1u=N,N+1,…,2N-1(1-15)离散余弦变换（DCT）及其应用由式(1-9)可得，DCT的IDCT1202)12(21212)12(121])([Re2)0(21)(Re2)0(12)12(cos)(2)0(1)(NuNuxjNujeeNuNuxjeeNueeeeuFNFNNeuFNFNNuxuFNFNxf(1-16)由式（7-63）可见，IDCT可由的2N点的IDFT来实现。NujeeuF2)(离散余弦变换（DCT）及其应用最后要注意的是二维DCT的频谱分布，其谱域分布与DFT相差一倍，如图1-1所示。从图中可以看出，对于DCT而言，(0,0)点对应于频谱的低频成分，(N-1,N-1)点对应于高频成分，而同阶的DFT中，(N／2,N／2)点对应于高频成分（注：此频谱图中未作频谱中心平移）。由于DFT和IDFT已有快速算法FFT和IFFT，因此可用它们实现快速DCT和IDCT算法FCT及IFCT。不过，由于FFT及IFFT中要涉及到复数运算，因此这种FCT及IFCT算法并不是最佳的。离散余弦变换（DCT）及其应用图1-1DFT和DCT（a）DFT频谱分布；（b）DCT频谱分布•1.4离散余弦变换在图像压缩中的应用•1.4.1图像压缩概述多媒体数据的显著特点：数据量非常大。例如，一张彩色相片的数据量可达10MB；视频影像和声音由于连续播放，数据量更加庞大。这对计算机的存储以及网络传输都造成了极大的负担。解决办法之一就是进行数据压缩，压缩后再进行存储和传输，到需要时再解压、还原。在位图格式的图像存储方式中，像素与像素之间在行方向和列方向都具有很大的相关性，我们说整体数据的冗余度很大，需要对图像数据进行很大程度的压缩离散余弦变换（DCT）及其应用离散余弦变换（DCT）及其应用多媒体数据的冗余类型多媒体数据表示中存在着大量的冗余，数据压缩技术就是利用多媒体数据的冗余性来减少数据量的方法。常见图像、视频、音频数据中存在的冗余类型如下：1.空间冗余2.时间冗余3.视觉冗余离散余弦变换（DCT）及其应用1.空间冗余一幅图像表面上各采样点的颜色之间往往存在着空间连贯性，基于离散像素采样来表示物体表面颜色的像素存储方式可利用空间连贯性，达到减少数据量的目的。例如，在静态图像中有一块表面颜色均匀的区域，在此区域中所有点的光强和色彩以及饱和度都是相同的，因此数据有很大的空间冗余。帧内压缩图——Bitmap——颜色相同的块——帧内压缩离散余弦变换（DCT）及其应用2.时间冗余运动图像一般为位于一时间轴区间的一组连续画面，其中的相邻帧往往包含相同的背景和移动物体，只不过移动物体所在的空间位置略有不同，所以后一帧的数据与前一帧的数据有许多共同的地方，这种共同性是由于相邻帧记录了相邻时刻的同一场景画面，所以称为时间冗余。同理，语音数据中也存在着时间冗余。离散余弦变换（DCT）及其应用3.视觉冗余人类的视觉系统由于受生理特性的限制，对于图像场的注意是非均匀的，人对细微的颜色差异感觉不明显。例如，人类视觉的一般分辨能力为26灰度等级，而一般的图像的量化采用的是28灰度等级，即存在视觉冗余。人类的听觉对某些信号反映不太敏感，使得压缩后再还原有允许范围的变化，人也感觉不出来。离散余弦变换（DCT）及其应用数据压缩方法的分类1.按照压缩方法是否产生失真分类(1)无失真压缩无失真压缩要求解压以后的数据和原始数据完全一致。解压后得到的数据是原数据的复制，是一种可逆压缩。无失真压缩法去掉或减少数据中的冗余，恢复时再重新插到数据中，因此是可逆过程根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2－1/4。一些常用的无损压缩算法有赫夫曼(Huffman)算法和LZW(Lenpel-Ziv&Welch)压缩算法(2)有失真压缩解压以后的数据和原始数据不完全一致，是不可逆压缩方式。有失真压缩还原后，不影响信息的表达例如，图像、视频、音频数据的压缩就可以采用有损压缩方法，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。图像、视频、音频数据的压缩比可高达100:1，但人的主观感受仍不会对原始信息产生误解。离散余弦变换（DCT）及其应用数据压缩方法的分类2.按照压缩方法的原理分类•预测编码：基本思想是利用已被编码的点的数据值，预测邻近的一个像素点的数据值•变换编码:基本思想是将图像的光强矩阵变换到系数空间上，然后对系数进行编码压缩•统计编码：根据信息出现概率的分布特性而进行的压缩编码*无失真编码*•分析－合成编码：基元和特征参数•混合编码：混合压缩是利用了各种单一压缩的长处，以求在压缩比、压缩效率及保真度之间取得最佳折衷离散余弦变换（DCT）及其应用数据压缩方法的分类离散余弦变换（DCT）及其应用影响数据压缩的要素•压缩比–压缩前后文件大小之比，越高越好，但受速度、消耗资源等的影响•图像质量–还原后与原图像相比，评估的方法有客观评估和主观评估•压缩与解压缩速度–与压缩方法和压缩编码的算法有关，一般压缩比解压缩计算量大，因而压缩比解压缩慢离散余弦变换（DCT）及其应用图像压缩编码举例(1)、行程编码（RLE）现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的像素都具有相同的颜色值。在这种情况下就不需要存储每一个像素的颜色值，而仅仅存储一个像素的颜色值，以及具有相同颜色的像素数目就可以，或者存储像素的颜色值，以及具有相同颜色值的行数。这种压缩编码称为行程编码(runlengthencoding，RLE)，具有相同颜色并且是连续的像素数目称为行程长度。•例如,字符串AAABCDDDDDDDDBBBBB利用RLE原理可以压缩为3ABC8D5BRLE编码简单直观，编码/解码速度快，因此许多图形和视频文件，如.BMP.TIFF及AVI等格式文件的压缩均采用此方法.由于一幅图像中有许多颜色相同的图块，用一整数对存储一个像素的颜色值及相同颜色像素的数目（长度）。例如：（G，L）离散余弦变换（DCT）及其应用图像压缩编码举例长度颜色值编码时采用从左到右，从上到下的排列，每当遇到一串相同数据时就用该数据及重复次数代替原来的数据串。离散余弦变换（DCT）及其应用图像压缩编码举例000000003333333333222222222226666666111111111111111111111111555555555555888888888888888888555555555555553333