第4章图象压缩编码

第二章作业1.马赫带效应和同时对比度反映了什么共同问题？2.什么是色度？3.奈奎斯特率采样条件是什么？为什么？4.根据采样定理、量化理论及人的视觉特性，说明非均匀采样和非一致量化的具体实施方案，解释其合理性。5.RGB颜色模型和CMYK颜色模型之间有什么关系？6.HSV颜色模型有什么优点？7.舌形图里连接红、绿、蓝构成的三角形与HSV颜色三角形有何不同？第三章作业2-D傅里叶变换的分离性有什么实际意义？证明二维离散傅里叶变换对的平移特性。举例说明二维傅里叶变换的周期性和共轭对称性的用途。证明f(x)的自相关函数的傅里叶变换就是f(x)的功率谱|F(u)|2。证明离散傅里叶变换和反变换都是周期函数（为简便可用1维函数为例）。试讨论连续卷积和离散卷积的不同。证明2个函数卷积的傅里叶变换是这2个函数傅里叶变换的乘积（为简便可用1维函数为例）。写出N=2时的2维DCT的正反变换核的值，讨论反变换核的可分离性和对称性。第四章图象压缩编码4.1概述4.2熵编码4.3预测编码4.4变换编码

压缩编码的必要性图象压缩编码的必要性：数据量非常庞大例：一幅黑白静止图象，512×512×8＝2Mbit地球资源卫星一帧(4幅)，2340×2340×7×4＝153Mbit数字电视PAL制4.43×106×3×8＝106Mb/s

占用数字话路106M/64k=1656图象压缩编码的目的：

减少表示一幅数字图象所需的数据量。节省图象存储的容量，缩短图象处理时间，减少传输信道容量。压缩编码的可能性图象压缩编码的可能性：图象数据存在冗余。空间冗余：图像中大部分景物是均匀的、连续的。相邻象素的数据完全一样或十分接近。像素的值可以通过与它相邻的象素值为基础进行预测。f(x,y)邻域空间冗余压缩编码的可能性时间冗余：视频图像序列中的不同帧之间的相关性造成的冗余。f(x,y,t3)f(x,y,t2)f(x,y,t1)时间冗余压缩编码的可能性心理视觉冗余：人眼不能感知或不敏感的那部分图像信息被认为是心理视觉冗余的。去除这些信息并不会明显降低图象质量，此种压缩往往是不可逆的。压缩编码的可能性编码冗余：如果一个图象的灰度级编码，使用了多于实际需要的编码符号，就称该图象包含了编码冗余。图象中象素灰度出现不均匀，用同样长度比特表示每一个灰度，则必然存在冗余。如果用8位表示该图象的象素，我们就说该图象存在编码冗余，因为该图象的象素只有两个灰度，用一位即可表示。压缩编码的可能性结构冗余：图像中存在很强的纹理结构或自相关性。知识冗余：图像中包含与某些先验知识有关的信息。压缩编码的分类根据对压缩编码后的图象进行重建的准确程度分类：1.信息保持型数据压缩(无失真、无损、可逆编码)

多用于图象的数字存储，可以实现高速“读”和“写”；各类图像可以通过数字存储介质进行多次重复复制而不失真。目前压缩率2～10。在医疗或商业文件的归档，有损压缩因为法律原因而被禁止；卫星成象的收集，考虑数据使用和所花费用，不希望有任何数据损失；X光拍片，信息的丢失会导致诊断的错误……压缩编码的分类2.保真度型数据压缩(有失真、有损、不可逆编码)

多应用在数字电视技术和多媒体图象通信中。丢失一些对信宿无用或作用不大的信息，也就是在允许失真条件下或一定的保真度准则下进行图象编码。有损压缩方法在图象压缩比大于30:1时仍然能够重构图象，而如果压缩比为10:1到20:1，则重构的图象与原图几乎没有差别。3.特征保持型数据压缩在图象识别、分析与理解中，仅对于实际需要的特征信息进行编码，无用信息都可丢掉。压缩编码的分类根据编码原理分类：

统计编码：基于信号统计特性的编码技术。哈夫曼编码、费诺香农编码、算术编码……

预测编码：预测编码是基于图象数据的空间或时间冗余特性，用相邻的已知象素来预测当前象素的取值，然后再对预测误差进行量化和编码。DPCM、ADPCM、

M……

变换编码：变换编码通常是将空间域上的图象经过正交变换映射到另一变换域上，使变换后的系数之间的相关性降低。Fourier、Walsh、Hadamard、Haar、Cosine、Sine、K-L……

其他编码：方块编码、轮廓编码、跳过白色块编码……图像编码技术经典现代空域变换域熵编码矢量量化方块编码预测编码块编码多分辨率编码傅里叶变换编码离散余弦变换编码沃尔什变换编码KL变换编码小波变换编码子带编码塔形编码分形编码模型基编码神经网络编码图象压缩编码模型信源编码：完成输入图象数据的压缩。信道编码：为了抗干扰，增加一些容错、校验位，实际上是增加冗余。信道：如Internet、广播、通讯、可移动介质……g(x,y)f(x,y)信源编码信道编码信道信道解码信源解码信源编、解码模型信源编码的模型映射器：减少象素间冗余，如游程编码或变换编码。量化器：减少心理视觉冗余，不可逆，仅用于有损压缩。符号编码器：减少编码冗余，如使用哈夫曼编码。信源解码的模型映射器量化器符号编码器符号解码器反向映射器基本概念1.信息量信源信道信宿消息集X={x1,x2,…xn}编码输出集Z={z1,z2,…zn}符号集Am={a1,a2,…an}以10为底，哈特利Hartley以e为底，奈特nat以2为底，比特bit信息量与码长呈线性等概率事件的信息量最大基本概念熵(entropy)——平均信息量无失真编码的理论极限

平均码字长度编码效率基本概念5.变长最佳编码定理在变长编码中，对出现概率大的信息符号赋予短码字，而对于出现概率小的信息符号赋予长码字。如果码字严格按照所对应符号出现概率大小逆序排列，则编码结果平均码字长度一定小于任何其他排列方式。6.可变长度最佳编码的平均码字长度基本概念7.非续长码任何一个码字都不是其它码字的续长，也就是不能在某一个码字后面添加一些码元而构成另一个码字。8.单义码任意有限长的码字序列，只能被唯一地分割成一个个码字，而其它任何分割方法都会产生不属于码字集合的码字。克劳夫特(kraft)不等式：

非续长码一定是单义码，但单义码不一定是非续长码。基本概念码1：非单义，续长。码2：非单义，续长。码3：单义，非续长，可用。码4：单义，续长。01无法判断，需下一个码字出现才能正确译码。Huffman编码步骤：将输入符号按出现的概率由大到小顺序排列。将两个最小概率相加，形成一个新的概率集合。再按1重排，如此重复进行直到只有两个概率为止。分配码字。码字分配从最后一步开始反向进行，对最后两个概率一个赋予“0”码，一个赋予“1”码。Huffman编码方法举例

例：

信号源s={s1,s2,s3,s4,s5,s6}，其概率分布为p1=0.4p2=0.3p3=0.1p4=0.1p5=0.06p6=0.04，求最佳Huffman码。Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S1=1Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S2=00Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S3=011Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S4=0100Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S5=01010Huffman编码例输入S1S2S3S4S5S6输入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S6=01011Huffman编码Huffman编码Huffman编码特点1)Huffman及Fano-shannon码不是唯一的；2)Huffman码缺乏构造性。即不能用数学方法建立消息和码字的一一对应关系，只能用查表方法实现。如果消息较多，则表必定很大，存储器也大，设备亦复杂。3)非等长码给传输和存储译码带来许多困难。4)对于二进制编码，当信源概率为2的负幂次方时，huffman编码效率可达100%；当信源概率为均匀分布时，其编码效率明显降低。也就是说图像灰度值分布很不均匀是，huffman编码效率高；而图像灰度值分布比较均匀是，huffman编码效率低。香农编码将输人灰度级（信息符号）按出现的概率由大到小顺序排列（相等者可以任意颠倒排列位置）。按式（4.2.5）或式（4.2.6）计算各概率对应的码字长度ti。计算各概率对应的累加概率ai

，即把各个累加概率由十进制小数转换成二进制小数。取二进制表示的累加概率小数点后面ti位，即获得各个信息符号的码字例：香农编码效率比哈夫曼编码效率低些，但仍算是一种高效编码方法。算术编码特点模式选择直接影响效率，有固定模式和自适应模式。自适应模式无需先定义概率模型，适合无法进行概率统计的信源，在这点上优越于哈夫曼编码。在信源符号概率接近时，比哈夫曼编码效率高。硬件实现比哈夫曼编码复杂。在JPEG的扩展系统中被推荐代替哈夫曼编码。算术编码基本原理：用0到1的线段上的一个区间来定义一个信源符号序列的算术码字，区间长度等于概率。例：已知信源，试对1011进行算术编码。游程长度编码（行程编码）现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。行程编码：不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值以及具有相同颜色的象素数目就可以，或者存储一个象素的颜色值以及具有相同颜色值的行数。行程长度：具有相同颜色并且是连续的象素数目。例子假定一幅灰度图像，第n行的象素值为：用RLC编码方法得到的代码为：80315084180。代码中用黑体表示的数字是行程长度，黑体字后面的数字代表象素的颜色值。例如黑体字50代表有连续50个象素具有相同的颜色值，它的颜色值是8。特点对比RLC编码前后的代码数可以发现，在编码前要用73个代码表示这一行的数据，而编码后只要用11个代码表示代表原来的73个代码，压缩前后的数据量之比约为7:1，即压缩比为7:1这说明RLC确实是一种压缩技术，而且这种编码技术相当直观，也非常经济。压缩比：RLC所能获得的压缩比有多大，这主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。译码时按照与编码时采用的相同规则进行，还原后得到的数据与压缩前的数据完全相同。因此，RLC是无损压缩技术。适用场景行程编码多用于黑白二值图像的压缩中。例如000000001111111111110000011111181256被转化为一系列黑串和白串长度的编码：8C56(0x)行程编码(RunLengthcoding,RLC)分析：对于有大面积色块的图象，压缩效果很好；对于纷杂的图象，压缩效果不好，最坏情况下，会加倍图象。脉冲编码调制(PCM)量化器基本思想：减少数据量的最简单的办法是将图象量化成较少的灰度级；这种量化是不可逆的，因而解码时图象有损失。量化器的定义：阶梯形量化函数t=q(s)，是奇函数q(-s)=-q(s)。si

量化器的决策级（阈值）；

ti

量化器的重构级（代表级）；L量化器的级数。脉冲编码调制(PCM)inputs1s2S(L/2)-1outputstt1t2t(L/2)-t(L/2)S-[(L/2)-1]t=q(s)决策级（阈值）重构级（代表级）增量调制(ΔPCM、ΔM、DM)

只有一个量化箱，即其增量只能增加一个Δ或减小一个Δ。

ΔM方案最大的缺点是易于过载。自适应增量调制(ADM)基本思想：为了适应图象信号变化陡度大的情况而相应改变量化箱Δ

的大小，对于平稳信号，Δ

变得很小，变化陡度大的信号，Δ

可变得很大。000、111——最宽箱101、010——窄档箱011、001、110、100——中等箱差分脉冲编码调制(DPCM)基本原理：是基于图象中相邻象素之间具有较强的相关性。每个象素可以根据以前已知的几个象素值来预测。因此在预测编码中，编码和传输的不是象素取样值本身，而是这个取样值和预测值之间的差值。差分脉冲编码调制(DPCM)最佳线性预测假定一幅二维静止黑白图像,经过逐帧行扫描而获得的图像信号X(t)是一个均值为零、方差为σ2的平稳随机过程。X(t)在时刻抽样值分别为,那么，根据Xi到XN-1的N-1个抽样值，就可以按下式获得tN时刻抽样值的线性预测值

1）基本原理其中，ai(i=1,2,3,…,N-1)为线性预测系数，为待定常数，与Xi无关。如果ai是已知的，或已设计确定的，那么就可以按式（4.3.4）构成线性预测编码器即DPCM，其框图见图如下。图4.3.2中略去DPCM系统框图中的量化器，Di(i=1,2,3,…,N-1)代表i个节拍的延时元件。对于各个ai的设计，一般采用最小均方误差准则最佳线性预测最佳线性预测取用以前像素的位置前值预测：用同一扫描行中前面最邻近象素值来预测。一维预测：用同一扫描行中前几个已知象素值来预测。二维预测(帧内预测)：用同一行和前几行若干个已知值来预测。三维预测(帧间预测)：用前几行和前几帧的已知象素值来预测。最佳线性预测

应用均方误差极小准则获得各个预测系数ai之间的约束关系：预测误差e=0应是一个量化输出电平，即量化分层的总数K应是奇数；满足最佳量化器

在量化比特数b(即量化层总数K=2b)已确定情况下，根据量化误差的均方值最小原则设计；最佳量化器

在保证量化误差满足应用要求前提下，尽可能使量化比特数b小。可见度阈值：量化误差被预测误差绝对值掩盖而观察不到时的数值上限。DPCM系统中的图像降质1.斜率过载：量化输出电平太小，使原陡峭轮廓变为缓变的轮廓，引起图象边缘模糊。2.散粒噪声：量化输出电平太大，缓变区域的输出在两个最小输出电平间变化，画面出现细斑。3.假轮廓：量化间隔太大，缓变的边缘产生等高线一样的图形。4.边沿忙乱：主要在电视图象中，因不同帧在同一象素位置上量化不同，边沿呈现闪烁跳动状干扰。5.误码扩散：自适应预测编码(ADPCM)一种自适应预测方案自适应预测编码(ADPCM)一种自适应量化器设计图像变换编码图像变换编码：将在空间域里描述的图像，在某种变换域里进行描述。优点：

在变换域里描述比空间域里简单；

在变换域里图像相关性下降；

若再对变换域图像进行某种编码可进一步压缩图像；

二维帧内变换编码的数据压缩程度和二维DPCM大致相当，但抗信道误码能力比DPCM强。缺点：

算法复杂，技术设备量也较大，成本高。正交变换压缩图像的物理本质物理本质：经过多维坐标系中的适当的坐标旋转和变换，能够把散布在各个坐标轴上的原始图像数据，在新的坐标系中集中到少数坐标轴上，因此可能用较少的编码比特来表示一幅子图像，实现高效率的压缩编码。变换编码原理框图变换量化编码器解码器逆变换信道输入GAA’发送端接收端输出G’二维傅立叶变换编码某图像经过2D-DFT后，其变换系数矩阵即二维频谱如图4.4.3所示。若变换矩阵FN原点设在中心，其频谱能量集中分布在变换系数矩阵的中心附近。若所用的二维傅立叶变换矩阵FN的原点设在左上角，那么图像信号能量将集中在系数矩阵的4个角上。这表明一般图像能量集中低频区域。由图可见，能量集中在中心附近，而中点数据即直流分量32占总能量很大比例。其实这个直流分量就是(a)图全图数值的算术平均值。根据变换系数分布的这些基本特点，采用区域抽样，再以区域编码，即只对数值较大的变换系数进行编码，即可实现图像压缩的目的。02D-DFT不足：相邻子图像数据在各个边界不连续造成Gibbs现象（在信号的边缘或某些位置，出现巨大的尖峰或失真）解决方法是用2D-DCT代替2D-DFT。基本思路为：用一个对称的2N×2N像素的子图像代替原来的N×N子图像，即可消除Gibbs现象。2D-DFT变换编码误差来源：变换系数经过量化器而引起的量化误差；采用“区域抽样”方式，使其高频成分被假定为零（相当于二维低通滤波，由于高频分量丢失引起图像模糊）；傅立叶变换编码对相邻的子图像变换并非移不变运算，因而在相邻子图像交界处将引起一定程度的边缘效应。二维沃尔什－哈达玛变换编码二维沃尔什－哈达玛变换简称沃尔什变换。与傅立叶变换相比，其算法简单（只涉及加法和减法），因而运算速度快，适用于高速实时系统，也容易硬件实现。二维沃尔什变换域中数值大的变换系数也都集中于低频区域，故采用区域抽样和区域编码同样可达到数据压缩的目的。区域抽样和区域编码区域抽样：只对能量大的变换系数抽样编码，而能量小的变换系数全部假定为零。区域编码：把变换系数矩阵分成若干个区域，每个区域编码比特数由该区域中变换系数的能量大小决定。子图像尺寸选择子图像尺寸也是影响变换编码误差和计算复杂度的一个重要因素。在多数情况下，我们将图像分成尺寸满足以下两个条件的子图像：①相邻子图像之间的相关性(冗余)减小到某个可以接受的水平；②子图像的长和宽都是2的整数次幂。最常用的子图像尺寸是8×8和16×16。离散余弦变换编码和JPEG基本系统先明确两个概念：DC系数和AC系数。

一幅8×8图像经过DCT变换和量化后得到的仍是64个系数，量化并没有改变系数的性质。DCT变换是将数据域从时（空）域变换到频域，在频域平面上变换系数是二维频域变量u和v的函数。对应于u=0，v=0的系数，称