DCT变换原理剖析

数字图像的冗余包括空间冗余、结构冗余、知识冗余和视觉冗余等。 空间冗余是指规则物体和规则背景的表面物理特性都具有相关性，数字化 后表现为数字冗余。例如：某图片的画面中有一个规则物体 , 其表面颜色 均匀, 各部分的亮度、饱和度相近 , 把该图片作数字化处理 ,生成位图后 , 很 大数量的相邻像素的数据是完全一样或十分接近的 , 完全一样的数据当然 可以压缩 , 而十分接近的数据也可以压缩 , 因为恢复后人亦分辨不出它与 原图有什么区别 , 这种压缩就是对空间冗余的压缩。再比如视觉冗余，视 觉系统对于图像场的注意是非均匀和非线性的，视觉系统不是对图像的任 何变化都能感知，因此对图像进行压缩后人眼也并不会非常敏锐地察觉画 面内容有所删减。所谓的图像压缩 编码技术 就 是对要 处理的图像 数据按 一定的规则 进 行变换和组合 , 从而达到以尽可能少的数据流（代码 ） 来表示尽可能多的数据信 息。 在众 多的 图像 压 缩编码标 准中， JPEG（Joint Photographic Experts Group） 格式是一种称为联合图像专家组的图像压缩格式，它适用 于不同类型、不同分辨率的彩色和黑白静止图像。而在JPEG图像压缩算法中， 有一种是以离散余弦变换 （DCT, Discrete Cosine Transform） 为基础的有损压缩算法，是为本论文的主要研究对象。DCT变换利用傅立叶变换的性质。采用图像边界褶翻将像变换为偶函 数形式，然后对图像进行二维傅立叶变换，变换后仅包含余弦项，所以称 之为离散余弦变换。DCT编码属于正交变换编码方式，用于去除图像数据的空间冗余。变 换编码就是将图像光强矩阵 （ 时域信号 ）变换到系数空间 （频域信号 ）上进 行处理的方法。在空间上具有强相关的信号，反映在频域上是在某些特定 的区域内能量常常被集中在一起，或者是系数矩阵的分布具有某些规律。 我们可以利用这些规律在频域上减少量化比特数，达到压缩的目的。图像 经DCT变换以后，DCT系数之间的相关性就会变小。而且大部分能量集中 在少数的系数上，因此，DCT变换在图像压缩中非常有用，是有损图像压缩国际标准 JPEG的核心。从原理上讲可以对整幅图像进行DCT变换，但由于图像各部位上细节的丰富程度不同，这种整体处理的方式效果不好。 为此，发送者首先将输入图像分解为 8*8 或 16*16 块，然后再对每个图像 块进行二维 DCT变换，接着再对 DCT系数进行量化、编码和传输；接收者通过对量化的 DCT系数进行解码，并对每个图像块进行的二维DCT反变换。最后将操作完成后所有的块拼接起来构成一幅单一的图像。对于一般的图像而言，大多数 DCT系数值都接近于 0，所以去掉这些系数不会对重建图 像的质量产生较大影响。因此，利用 DCT进行图像压缩确实可以节约大量 的存储空间。在实验中，先将输入的原始图像分为8*8 块，然后再对每个块进行二维DCT变换。编码DCT 编码属于正交变换编码。 这类算法通常是将空间域上的图像经过正交变换映射到系数空间，使变换后的系数直接相关性降低。图像变换本 身并不能压缩数据，但变换后图像大部分能量集中到了少数几个变换系数 上，再采用适当的量化和熵编码便可以有效地压缩图像。信息论的研究表明，正交变换不改变信源的熵值，变换前后图像的信息量并无损失，完全可以通过反变换得到原来的图像值。但图像经过正交变换后，把原来分散在原空间的图像数据在新的坐标空间中得到集中，对 于大多数图像而言，大量的变换系数很小，只要删除接近于0 的系数，并对较小的系数进行粗量化，而保留包含图像主要信息的系数，以此进行压 缩编码。在重建图像进行解码（逆变换）时，所损失的将是些不重要的信 息，几乎不会引起图像失真，图像的变换编码就是利用这些来压缩图像并 得到很高的压缩比。由于图像可看成二维数据矩阵，所以在图像编码中多采用二维正交变 换方式，然而其正交变换的计算量太大，所以在实用中变换编码并不是对 整幅图像进行变换和编码，而是将图像分成若干个nxn的子图像分别处理。这是因为小块图像的变换计算比较容易，而且距离较远的像素之间的 相关性比距离较近的像素之间的相关性要小。实践证明4x 4、8x 8、16x16 适合图像压缩，这是因为： 如果子图像尺寸取得太小，虽然计算速度快，实现简单，但压缩能 力有限； 如果子图像尺寸取得太大，虽然去相关效果好，因为DCT等正弦类变换均渐近最佳化， 同时也渐近饱和， 犹豫图像本身的相关性很小， 反而使得压缩效果不明显，并且增加了计算的复杂度。变换系数的选择对子图像经过变换后，保留变换后的哪些系数用作编码和传输将直接 影响信号恢复的质量，变换系数的选择原则是保留能量集中、方差大的系 数。系数选择通常有变换变换区域编码和变换阈值编码两种方法。1）变换区域编码变换区域编 码是对设 定形状的 区域内的 变换系数进 行量化 编码区域 外的系数被舍去。一般来说，变换后的系数值较大的会集中在区域的左上 部，即低频分量都集中在左上部。保留的也是这一部分。其他部分的系数 被舍去，在恢复信号时对它们补0。这样以来，由于保留了大部分图像信号能量，在恢复信号后，其质量不会产生显著变化。变换区域编码的明显 缺陷是高频分量完全丢失。反应在恢复图像上将是轮廓及细节模糊。为克 服这一缺陷，可预先设定几个区域，根据实际系数分布自动选取能力最大 的区域。2）变换阈值编码变换阈值编码是根据实际情况设定某一大小幅度的阈值，若变换系数 超过该阈值，则保留这些系数进行编码传输，其余补0.这样，多数低频成分被编码输出，而且少数超过阈值的高频成分也将被保留下来进行编码输 出。这在一定程度上弥补了区域变换法的不足。但也有两个问题需要解决：一是被保留下来的系数在矩阵中的位置不是不确定的，因此需增加地质编 码比特数，其码率相对要高一些；二是阈值需要通过实验来确定，当然也 可以根据总比特数进行自适应阈值选择，但需要一定技术，将增加编码的 复杂程度。基于DCT编码的JPEGS码压缩基于DCT编码的JPEG编码压缩过程框图，如图2-1所示图2-1 基于DCT编码的JPEG压缩过程简化图上图是基于 DCT变换的图像压缩编码的压缩过程，解压缩与上图的 过程相反。在编码过程中，首先将输入图像分解为8X8大小的数据块，然后用正向二维DCT把每个块转变成 64个DCT系数值，其中左上角第一个数值 是直流（DC）系数，即8X 8空域图像子块的平均值，其余的63个是交流（AC）系数，接下来对 DCT系数进行量化，最后将变换得到的量化的DCT系数进行编码和传送，这样就完成了图像的压缩过程。在解码过程中，形成压缩后的图像格式，先对已编码的量子化的DCT系数进行解码，然后求逆量化并把 DCT系数转化为8 X 8样本像块（使用二 维DCT反变换），最后将操作完成后的块组合成一个单一的图像。这样就 完成了图像的解压过程。1.2 二维离散余弦变换图像数据压缩的目的是在满足一定图像质量的条件下，用尽可能少的比特数来表示原始图像，以提高图像传输的效率和减少图像存储的容量， 在信息论中称为信源编码。图像压缩是通过删除图像数据中冗余的或者不 必要的部分来减小图像数据量的技术，压缩过程就是编码过程，解压缩过 程就是解码过程。假设有一个无记忆的信源，它产生的消息为 ?, 1乞i乞N ,其出现的概率是已知的，记为P ai o则其信息量定义为：I q i=-log2 P ai（2-1）由此可见一个消息出现的可能性越小，其信息量就越多，其出现对信 息的贡献量越大，反之亦然。信源的平均信息量称为“熵”entropy，可以表示为：NNH 八 P a： I P 可 小 P ai logP ai（2-2）i 4i -4对上式取以2为底的对数时，单位为比特（ bits ）:NH - 八 P ai log2 P ai（2-3）i -4在图像压缩中，压缩比是一个重要的衡量指标。可以定义压缩比为：C=原始数据的平均比特率（B） /压缩数据的平均比特率（H）DCT变换后系数的量化是引起失真的主要原因,压缩效果与图像内容本身有较大的关系在傅里叶级数展开式中，如果被展开的函数是实偶函数，那么，其傅 里叶技术中只包含余弦项，在将其离散化由此可导出余弦变换，或称之为 离散余弦变换(DCT， Discrete Cosine Transform)。2 nn(2x+1)f2y + 1、F(u,v )=c(u C(v )書瓦 Z f(x,y)cos-u 兀cos -v 兀(2-4)N xmvi 2N丿I 2N丿u =0, v =0其它式中，x,y,u,v=0N_1。c(u12i1二维离散余弦逆变换公式为f x,y =2 N A、N u z0Nc u c v F u,v cosv z0广 2x+1i 2Nu二 cos2y S二丿I 2N 丿(2-5)式中，x, y,u,v =0,1, N -1丄c(u)二 c(v) =2i1u = 0,v = 0其它JPEG采用的是8X 8大小的子块的二维离散余弦变换。在编码器的输 入端，把原始图像顺序地分割成一系列8X8的子块，子块的数值在到127之间。采用余弦变换获得变换公式，如式(2-6)所示。1 7 F u,v c u c v 464个变换系数。x =07 _二f x,y cos -V 16y=02xcosv二丿I 16 丿-128(2-6)式中，x, y,u,v =0,1,7。c(u) = c(v)=丿 72i 1u =0,v =0其它在MATLAB仿真实现中，主要是采用二维 DCT变换的矩阵式定义来实现的,矩阵式定义可以表示为：F (u , v) I -丨 A 丨丨 F (u, v) I 丨 A I, f (x, y)丨-丨 A 丨丨 f ( x, y)丨丨 A 丨(2-7 ) 其中f(x, y)是空间数据阵列，F(u,v)是变换系数阵列，I.A 1是变换矩阵 I.A T是I.A 的转置。The basis functions of the DCT of 64X64 an Image系数的量化量化是对经过 DCT变换后的频率系数进行量化，其目的是减小非 “ 0”系数的幅度以及增加“0”值系数的数目，它是图像质量下降的最主要原因。量化过程定义了一种从实数到整数映射的方法，它是通过降低DCT变换产生的数值结果的精确度，来减少存储变换后的系数需要的比特数。定义量化公式为：K(u, v)=int F(u, V)(2-8)2(u,v)丿其中，F(u,v)为量化前的 DCT系数，K(u,v)为量化后的 DCT系数， 而Q(u,v)为量化步长，int表示取整。对于基于DCT的JPEG图像压缩编码算法，量化步距是按照系数所在 的位置和每种颜色分量的色调值来确定。因为人眼对亮度信号比对色差信 号更敏感，因此使用了表2-1所示的量化表。此外，由于人眼对低频分量 的图像比对高频分量的图像更敏感，因此表中的左上角的量化步距要比右 下角的量化步距小。亮度和色度因为代表的图像的信息量不同，亮度代表了图像的低频分 量，色度代表了图像的高频分量，要分别对亮度和色度进行量化，所以量 化表也是不同的。量化就是用 DCT变换后的系数除以量化表中想对应的量化阶后四舍 五入取整。由于量化表中，左上角的数值比较小，而右下角的数值比较大,因而能够起到保持低频分量，抑制高频分量的作用。JPEG压缩色度和亮度量化表如表2-1所示。表2-1 JPEG压缩色度和亮度量化表亮度量化表色度量化表161110162440516117182447999999991212141926586055182126669999999914131624405769562426569999999999141722295187806247669999999999991822375668109103779999999999999999243555648110411392999999999999999949647887103121120101999999999999999979929598112100103999999999999999999量化会产生误差，上图是综合大量的图像测试的实验结果，对于大部 分图像都有很好的结果。表中可以看出，高频部分对应的量化值大，目的 就是将高频部分编程接近于0，以便以后处理。JPEG可以在压缩比和图像质量间作取舍。方法就是改变量化值。如果量化值放大一倍，则有更多的 系数量化为0,提高了压缩比。在本课题研究中，用于 DCT变换的图像为灰度图像，故只考虑亮度即 可。量化系数的编排经过DCT变换后，低频分量集中在左上角，其中F(0 , 0)(即第一行第一列元素)代表了直流(DC)系数，即8X 8子块的平均值，要对它单独编码。 由于两个相邻的 8X8子块的DC系数相差很小，所以对它们采用差分编码 DPC M可以提高压缩比，也就是说对相邻的子块DC系数的差值进行编码。8X 8的其它63个元素是交流(AC)系数，采用行程编码。所以量化后的系数要重新编排，目的是为了增加连续的“0”系数的个数，就是“ 0”的游程长度，方法是按照Z字形的式样编排。DCT变换后低频分量多呈圆形辐射状向高频率衰减，因此可以看成按Z字形衰减。因此，量化系数按Z字形扫描读数，这样就把一个8X 8的矩阵变成一个1 X 64的矢量，频率较低的系数放在矢量的顶部。量化后的DCT系数的编排如图 2-2所示。兰值AC系数开始图2-2量化DCT系数的编排量化后的DCT系数的序号如表2-2所示。表2-2 量化DCT系数的序号01561415272824713162629423812172530414391118243140445310192332394552542022333846515560213437475056596135364849575862631.3 2D-DCT 与 2D-FFT 的比较这两种运算体现在程序中，分别调用了 1D-FFT和1D-DCT变换，而1D-DCT又是以1D-FFT为核心的。设计的程序是以频率抽取的基2FFT算法为基本理论的，因此蝶形运算后，需要进行排序，根据理论推算应该采取倒位序的方法，对于一个N=8的蝶形运算，其结果下标排列应是：0， 4， 2，6，1，5，3，7。倒位序后回到了自然排列顺序 0, 1，2, 3，4, 5，6，7。一维快速傅立叶正反变换 包含于一个核心子程序中，所以在求其反变换时，先将X(K)取共轭变换，在将X(K)的虚部乘以-1 ,然后就可以直接访问FFT的子程序，最后再对运算结果取一次共轭变换并乘以常数1/N即可得到x (n)值。这种IFFT算法可以完全不改动FFT的程序。在进行二维的 FFT变换时，可把二维的FFT变换变成一维后直接调用FFT子程序。因为，二维离散傅立叶变换(DFT)处理图像的时间比较长，其处理结果和FFT处理结果相同；FFT运算量非常大，实时性差，处理图像时没有实用性。傅里叶变换的不足之处在于子图像的变换系数在边界处的不连续而造 成恢复的子图像在其边界也不连续，于是由于各恢复子图像构成的整幅图 像将呈现隐约可见的子图像的方块状结构，影响图像质量。图2-3 2D-FFT的变换谱图2-4 2D-DCT的变换谱可以看出，原图像经 FFT变换后频域能的量主要集中在两条对角线附近；DCT变换后变换域的能量主要集中在低频分量附近(即左上角)。图像压缩中的DCT编码正是利用DCT变换的这一特性，在对二维图像进行DCT变换后，只对变换域低频分量进行编码，抛弃部分高频分量，减少携带的信息量，从而实现对图像的有损压缩编码DCT 变换与 FFT 变换类似，但 DCT 变换可以使用较少的频谱系数来 表示被变换的图像数据。在接收端，用逆变换 IDCT 将这些频谱系数恢复 成的图像数据，与变换前的数据更接近。因此在图像压缩算法中常用 DCT 变换。实验结果及分析离散余弦变换 DCT的MATLAB实现有两种方法,一种是基于FFT的快 速算法,这是通过MATLAB工具箱提供的dct2函数实现的；另一种是DCT变换矩阵方法。变换矩阵方法非常适合做8*8 或16*16的图像块的DCT变换,工具箱提供了dctmtx函数来计算变换矩阵。方法1：该方法出发点是对整幅图像进行DCT变换，主要应用MATLAB勺图像处理工具箱中的基于FFT的有大量输入的快速算法进行处理的dct2函数：具体程序实现如下：A=imread(D:rabitrabit.bmp);l=rgb2gray(A);DCT=dct2(I); %余弦变化DCT(abs(DCT) I A x IDCT 方法2:该方法的出发点是先将图像分解为8*8或16*16个数据块，然后分别对分解后的每个数据小方块进行DC变换，主要应用 MATLA的图像处理工具箱中dctmtx函数返回DC变换矩阵，而后进行相关处理。样本程序实现如 下：A=imread(D:rabitrabit.bmp);l=rgb2gray(A);匸im2double(l);%将图像转换为双精度格式T=dctmtx(8);%返回一个8*8的DCT变换矩阵B=blkproc(l,8 8,P1*x*P2,T,T);%对原图像进行DCT 变换mask=1 1 1 1 0 0 0 01 1 1 0 0 0 0 01 1 0 0 0 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 0；%保留了 10个DCT系数重构图像B2=blkproc(B,8 8,P1.*x,mask);%数据压缩，丢弃右下角高频数据l2=blkproc(B2,8 8,P1*x*P2,T,T);泌行DCT反变换，得到压缩后的图像subplot(1,2,1),imshow(l)title(原始图像)subplot(1,2,2),imshow(l2)title(压缩图像1)disp(压缩后图像I2的大小);whos(I2); disp(压缩前图像 A的大小);whos(A);disp(压缩后图像I的大小);whos(T);(a)(b)压缩團像2(c)压缩團像d(d)（e）(f)图4-3 基于DCT的图像压缩对于（b）图“压缩图像 1”，仿真中仅保留了3个DCT系数，约占5%从结果来看，图像压缩的效果出现了“块”失真。并且随着量化系数 的进一步减少，失真情况会越来越严重，这说明图像信息丢失严重。对于（c）图“压缩图像2”，仿真中保留了 10个DCT系数，占15%,比 较原图和重构图像，可以发现：在抛弃85%的系数后，重构图像基本上恢复了原图像的信息，可以比较清楚地辨清亮度上的差异，大部分的信息都 很好的保留下来。然而细节部分，即边缘部分，也就是高频分量所携带的 信息，并没有很好地重现出来。因为我们把高频分量通过mask表中的0值控制全部舍弃了。而且从方法1中的“ DCT变换” 一图中，我们可以清楚地看到，对于本图来说，非0值并非很好地集中在左上部很小的部分，而是分布在几乎85%的区域。因此，当我们只取了左上部15%的DCT系数时，当然不能很好地恢复剩余大部分的细节。当然，在采用这种方法来实现压缩 算法时，可以通过修改 mask变量中的DCT系数来更好地比较仿真结果。在（d）图“压缩图像3 ”中，则是对半取舍 DCT系数。较之（c）图的 效果又有了明显的进步，边缘细节信息已经得到了很好的保留和重现。在（e）图“压缩图像 4”中，便是把 mask中的DC係数取85%地进行了 保留，而只舍去了 10个右下角的DCTS数。可以看出，该图中的细节信息 较之（d）图又有了更好的体现，边缘等部分轮廓比较清晰，与之前的压 缩图像进行对比，图像的恢复重现效果明显好了很多。而在（f）图“压缩图像5”中，则是把“压缩图像 1”中的DCT系数的 取舍完全颠倒过来，即，“压缩图像 2”中，左上部分取1的系数变为取0， 同时右下部分取为 0的DCT系数则变为取1保留。从低频和高频的角度来说，即是将承载了灰度图像很大部分重要亮度信息的低频部分舍弃，而仅仅将 右下角的承载边缘细节信息的高频部分予以保留。效果如“压缩图像5 ”所示，我们可以明显看到仅仅有图像的边缘信息显示，而原始图像最重要 的信息则没有保留和显现。而当把图像分为 16*16数据块进行 DCT变换时，算法的复杂度急剧上 升，但采用较大的子块可以明显减少图像分块效应。实验结果如下：（程序见附录五）b ）图“压缩图像 1”是 16*16 子块模式中仅保留了 6 个左上角 DCT系数的效果，可以看出明显的块失真效果。（c）图“压缩图像 2”是保留了 10个DCT系数，效果与 8*8子块模式中保留 3个DCT系数的效果差不 多，但要稍微好一点。（d） 图“压缩图像 3”中保留了 36个DCT系数，约占14%，此时与 8*8子块模式中的保留了 15%的DCT系数的“压缩图像 2”效果相近，并 且稍微更清晰一些。（e）图保留了 3/8的DCT系数，而（f）图“压缩图像5”中保留了 50%的DCT系数，和8*8子块模式中同样对半取舍系数的（d）图进行对比，可以看出 16*16 子块的效果要更好一些。由此可见，将图像划分为更小的数据块进行DCT变换和压缩的效果更好，然而复杂度上升。当图像压缩比增大时，也即压缩效率减小时，图像的质量也将降低， 人们可以根据需要的图像的质量来规定压缩比的大小。