第三章图像压缩编码

第三章图像压缩编码3.1图像压缩的必要性和可行性3.2图像编码理论基础3.3无失真编码3.4有失真编码作业3.1图像压缩的必要性和可行性一、图像压缩的必要性以一般彩色电视信号为例，设代表光强、色彩和色饱和度的YIQ空间中各分量的带宽分别为4MHz、1.3MHz和0.5MHz。3.1图像压缩的必要性和可行性根据采样定理，仅当采样频率大于或等于2倍的原始信号的频率时，才能保证采样后的信号可能被无失真地恢复为原始信号。再设各样点均被数字化8bit，从而1秒钟的电视信号的数据量为(4+1.3+0.5)×2×8bit=92.8Mbit。3.1图像压缩的必要性和可行性二、图像压缩的可行性在图像数据中，一般存在以下一些数据冗余类型。空间冗余：在任何一幅图像中，均有许多灰度和颜色都相同的邻近像素组成的局部区域，它们形成了一个性质相同的集合块，在图像中就表现为空间冗余。3.1图像压缩的必要性和可行性3.1图像压缩的必要性和可行性对空间冗余的压缩方法就是把这种集合块当做一个整体，用极少的数据量来表示它，从而节省了存储空间。这种压缩方法叫空间压缩或帧内压缩，它的基本点在于减少邻近像素之间的空间相关性。3.1图像压缩的必要性和可行性时间冗余：活动图像中的两幅相邻的图像有较大的相关性，这反映为时间冗余。时间压缩/帧间压缩3.1图像压缩的必要性和可行性信息熵冗余（编码冗余）所谓信息熵，是指数据所带的信息量。信息熵的数学表达式为：式中，Pi为任意一个码元i出现的概率，k为数据码元的总个数。3.1图像压缩的必要性和可行性

H的单位是bit/码元。如果对码元采用二进制编码，并且第i个码元yi所分配的比特数为b(yi)，那么码元的平均长度（即包含的平均比特数或平均信息量）为：3.1图像压缩的必要性和可行性为了使编码后的信息不损失，应当使d接近H，理论上应取b(yi)=-lbPi。实际上，很难估计{P0，…，Pk-1}，因此，一般总是取b(y0)=b(y1)=…=b(yk-1)，而等概情况下的平均信息量是最大的，这样d必定大于H，由此带来的冗余称为信息熵冗余或编码冗余。3.1图像压缩的必要性和可行性结构冗余：有些图像从整体上看存在着非常强的纹理结构，称它在结构上存在冗余。3.1图像压缩的必要性和可行性知识冗余：人们通过认识世界而得到某些图像所具有的先验知识和背景知识，由此带来的冗余称为知识冗余。视觉冗余：人的眼睛是图像信息的接收端，而人类的视觉系统并不能对图像画面的任何变化都能感觉到，这称为视觉冗余。3.1图像压缩的必要性和可行性空间冗余和时间冗余是将图像信号看作随机信号时反映出来的统计特征，因此有时把这两种冗余称为统计冗余。它们也是图像数据处理中两种最主要的数据冗余。3.2图像编码理论基础一、图像压缩编码系统的基本结构对图像的压缩编码是信源编码问题，其目的是减少冗余数据。3.2图像编码理论基础变换器对输入图像数据进行一对一的变换，其输出是比原始图像数据更适合高效压缩的图像表示形式。量化器要完成的功能是按一定的规则对采样值作近似表示，使量化器输出幅值的大小为有限个数。3.2图像编码理论基础编码器为量化器输出端的每个符号分配一个码字或二进制比特率，编码器可采用等长码或变长码。不同的图像编码系统可能采用上述框图中的不同组合。3.2图像编码理论基础按照压缩编码过程是否失真，图像压缩编码可分为：（1）无失真压缩方法（或称为无损压缩方法）：这是在不引人任何失真的条件下使比特率为最小的压缩方法，它可以保证图像内容不发生改变。3.2图像编码理论基础（2）有失真压缩方法（或称为有损压缩方法）：这种方法是使图像内容的差别控制在一定的范围内，保证观察效果的主观质量。这种方法能够在一定比特率下获得最佳的保真度，或在给定的保真度下获得最小的比特率。3.2图像编码理论基础按照压缩方法的原理，数字图像压缩方法可分为：

（1）预测编码（PredictiveCoding）：是一种针对统计冗余进行压缩的方法，主要是减少数据在空间和时间上的相关性。它是一种有失真的压缩方法。3.2图像编码理论基础（2）变换编码（TransformCoding）：也是一种针对统计冗余进行压缩的方法。这种方法将图像光强矩阵（时域信号）变换到系数空间（频域）上进行处理。（3）标量量化和矢量量化编码（VectorQuantization）：本质上也还是一种针对统计冗余进行压缩的方法。3.2图像编码理论基础（4）信息熵编码（EntropyCoding）：根据信息熵原理，用短的码字表示出现概率大的信息，用长的码字表示出现概率小的信息。（5）子带编码（Sub-bandCoding）：将图像数据变换到频域后，按频率分带，然后用不同的量化器进行量化，从而达到最优的组合。3.2图像编码理论基础（6）结构编码（StructureCoding）：也称为第二代编码（SecondGenerationCoding）。编码时首先求出图像中的边界、轮廓、纹理等结构特征参数，然后保存这些参数信息。3.2图像编码理论基础（7）基于知识的编码（Knowledge-BasedCoding）：对于人脸等可用规则描述图像，利用人们对其的知识形成一个规则库，据此将人脸的变化等特征用一些参数进行描述，从而用参数加上模型就可以实现人脸的图像编码与解码。3.2图像编码理论基础3.2图像编码理论基础二、信源模型及其熵1、图像的信息量已知某一个图像信息源所发出的符号集合为X={S1，S2，…，Sn}，发出符号Si的概率为p(Si)，且p(Si)满足条件：0≤p（Si）≤1（）。这样，符号Si所携带的信息量I(Si)可以表示为I(Si)=log(1/p(Si))=-logp(Si)。

3.2图像编码理论基础以上定义的信息量也称为自信息量，在公式中，对数的底不同，则计算的值也不同。当r=2时，相应的单位为“bit”；当r=e时，其单位为奈特（Nat），当r=10时，其单位称为哈特（Hart）。3.2图像编码理论基础自信息量的含义：

自信息量表示在接收者未收到符号Si之前，并不清楚究竟会收到符号集X={S1，S2，…，Sn}中的哪一个符号，即存在不确定性。只有当接收者收到Si符号之后，才可能消除这种不确定性，这就是通过接收所获得的信息量。3.2图像编码理论基础2、离散信源如果信息源所发出的符号均取自某一个离散集合，这样的信息源称为离散信源。离散信源X可以描述为：其中：îíì=)(,),(),(,,,2121nnSpSpSpSSSXLL3.2图像编码理论基础如果从离散信息源X中所发出的各种符号彼此独立无关，即任意两个相继发出的符号Si和Sj，Si符号不会对Sj符号构成影响，称这样的图像信息源为“无记忆”的离散信息源，或者叫独立信源。

3.2图像编码理论基础由一个无记忆的离散信息源所发出的任意长度的符号序列S1，S2，…，Sn的信息量为：

I(S1,S2,…,Sn)=-lb[p(S1)p(S2)…p(Sn)]=I(S1)+I(S2)+…+I(Sn)3.2图像编码理论基础实际的图像信息源所发出的各符号并不是相互独立的，而是具有一定的相关性，即相继发出的符号序列中Si符号的出现与它之前已相继出现的几个符号Si-1，Si-2，…有关，这样的信源就是“有记忆”信息源，或叫联合信源。3.2图像编码理论基础3、图像的信息熵独立信源独立图像信息源X的熵为：其单位为bit/符号。

3.2图像编码理论基础如果考虑一个多幅图像的集合，以每一幅图像为一个基本符号单位时，pi表示集合中某一幅图像出现的概率，H(x)的单位是bit/每幅图像。以图像为一个基本符号单位时，每幅图像的内容被认为是确定的，需要消除的不确定性是当前接收的图像是集合中的哪一幅。

3.2图像编码理论基础实际通信图像是以每一幅图像表达的内容为传送信息的，这时pi为各采样值出现的概率，H(x)的单位是bit/像素。图像熵H表示各个灰度级比特数的统计平均值。熵越大，图像含有的信息量越丰富，各个灰度级的出现呈等概率分布的可能性也越大。3.2图像编码理论基础联合信源具有实际通信意义的图像，其相邻像素间必有一定的联系，因此图像信息源是一种有记忆的信源。如果一个信源符号发生的概率和其前面的M个符号有关，这种信源就叫做M阶马尔可夫信源。3.2图像编码理论基础马尔可夫信源用一组条件概率来表示：条件熵为：

3.2图像编码理论基础对所有状态下的条件熵计算统计平均，即得到M阶马尔可夫信源的熵为：式中SM是所有状态的集合。

3.2图像编码理论基础的含义：在前M个符号取值分别为sj1、sj2一直到sjM的条件下，当前符号取si值的概率。条件信息熵的含义：在前M个符号取值分别为sj1、sj2一直到sjM的条件下，当前符号的平均信息量。3.2图像编码理论基础两个信息源X和Y，分别取值于集合和，对X和Y作笛卡尔乘积，就构成联合信源（X,Y）。3.2图像编码理论基础描述联合信源的性能指标：联合概率：P(xi,yj)——联合信源(X,Y)取值为(xi,yj)的概率。边缘概率：3.2图像编码理论基础条件概率：X与Y的联合熵：3.2图像编码理论基础X的条件熵：Y的条件熵：3.3无失真编码一、无失真编码理论无失真压缩方法是指编码后的图像可经译码完全恢复为原图像的压缩编码方法。在编码系统中，无失真编码也称为熵编码。3.3无失真编码【无失真编码定理】

对于离散信源X，对其编码时每个符号能达到的平均码长满足不等式：式中，为编码的平均码长，单位为每符号比特数；ε为任意小的正数，H(X)为X的熵，即，P(xi)为信源X发出符号xi的概率。3.3无失真编码该定理一方面指出了每个符号平均码长的下限为信源的熵，另一方面说明存在任意接近该下限的编码。对于独立信源，该定理适用于单个符号编码的情况，也适用于对符号块编码的情况。对于M阶马尔可夫信源，该定理只适用于不少于M个符号的符号块编码的情况。3.3无失真编码1、变字长编码经过数字化后的图像，每个采样值都是以相同长度的二进制码表示的，称为等长编码。等长编码的优点是编码简单，但编码效率低。改进编码效率的方法是采用不等长编码，或称为变字长编码。3.3无失真编码设图像信源X有n种符号，，且它们出现的概率为，那么，不考虑信源符号的相关性，对每个符号单独编码时，平均码长为：。式中，Li是xi的码字长度。3.3无失真编码不等长编、译码过程都比较复杂。首先，编码前要知道个符号的概率p(xi)，为了具有实用性，还要求码字具有唯一可译性和实时可译性。此外，还要与输入、输出的速率匹配。解决译码的唯一可译性和实时性的方法是采用非续长码，解决速度匹配则是在编码、译码器中引入缓冲匹配器。3.3无失真编码所谓非续长码，是指码字集合中的任何一个码字都不是其他码的字头（前缀）。非续长码保证了译出的码字的唯一性，而且没有译码延迟。3.3无失真编码2、最佳变长编码定理【最佳变长编码定理】

在变长编码中，对出现概率大的信息符号赋予短码字，而对于出现概率小的信息符号赋予长码字。如果码字长度严格按照所对应符号出现概率大小逆序排列，则编码结果平均码字长度一定小于任何其他排列方式。3.3无失真编码【证明】

设最佳排列方式的码字平均长度为，则有，其中pi为符号xi出现的概率，Li为xi的码字长度。设pi≥ps，则Li≤Ls，其中ps为符号xs出现的概率，Ls为xs的码字长度，i，s取值为1~n。3.3无失真编码如果将xi的码字和xs的码字互换，而其余码字不变，这时的平均码字长度记为L‘，则它可以表示为加上两码字互换后的平均长度之差，即：因为pi≥ps，且Li≤Ls，所以L‘≥，这说明原先给出的是最短的码长。3.3无失真编码3、准变长编码

即双字长编码。这种编码只有两种长度的码字，对概率小的符号用长码，反之用短码。同时，在短码字中留出一个作为长码字的字头（前缀），保证整个码字集的非续长性。3.3无失真编码3/6比特双字长编码3.3无失真编码4、性能指标平均码字长度：设βk为数字图像第k个码字Ck的长度，其相应出现的概率为Pk，则该数字图像所赋予的码字平均长度R为:3.3无失真编码压缩比：编码前后平均码长之比，即n为压缩前图像每个像素的平均比特数，通常为用自然二进制码表示时的比特数；表示压缩后每个像素所需的平均比特数。3.3无失真编码编码效率：信源的熵与平均码长之比，即H(X)为信源熵，为平均码长。3.3无失真编码冗余度：如果编码效率η≠100%，这说明还有冗余信息。冗余度可由下式表示：ξ=1-η。比特率：通常指编码的平均码长。在数字图像中，对于静止图像，指每个像素平均所需的比特数，单位为bit。而对于活动图像，常指每秒输出或输入的比特数，单位为Mb/s，kb/s等。3.3无失真编码二、哈夫曼编码哈夫曼编码是根据最佳变长编码定理，应用哈夫曼算法而产生的一种编码方法。该方法于1952年由哈夫曼提出，该编码的码字长度的排列与符号的概率大小的排列是严格逆序的，理论上已经证明其平均码长最短，因此被称为最佳码或紧凑码。3.3无失真编码【编码步骤】(1)按概率从大到小的顺序排列信源符号；(2)从最小的两个概率开始编码，将概率较大的信源符号编为1（或0），将概率较小的信源符号编为0（或1）；(3)对已编的两个概率相加，将结果与未编码的概率从大到小进行排序；3.3无失真编码(4)重复(2)、(3)两步，直到概率达到1.0为止；(5)画出由每个信源符号概率到1.0处的路径，记下沿路径的1和0；(6)对于每个信源符号都写出1、0序列，则从右到左就得到哈夫曼编码。3.3无失真编码【例】对一个6符号信源X={x1，x2，…，x6}进行哈夫曼编码。其概率为{p1，p2，…，p6}={0.4,0.25,0.15,0.1,0.05,0.05}。3.3无失真编码编码结果：x1→0，x2→10，x3→110，x4→1111，x5→11101，x6→11100。平均码长：信源熵：

3.3无失真编码编码效率：

压缩比：r=3/2.25=1.33冗余度：ξ=1-η=1-97.94%=2.06%说明：由于“0”和“1”的指定是任意的，因此由上述过程编成的最佳码并不唯一，但其平均码长是一样的。

3.3无失真编码哈夫曼码的解码过程：解码器中有一个缓冲器，用于存放从已编码的码流中收到的比特。一开始缓冲器为空，每收到一个比特，将它依次压于缓冲器，并将缓冲器中已形成的码字与哈夫曼码表中的每一码字比较。如果找到一个相同的，则输出该码字对应的信源符号，并将缓冲器刷新为空；否则，继续读取码流中的下一个比特，这一过程一直持续到结束。3.3无失真编码【练习】已知一个8符号信源X={x1，x2，…，x8}的概率为{p1，p2，…，p8}={0.4,0.18,0.10,0.10,0.07,0.06,0.05,0.04}。对其进行哈夫曼编码并计算编码效率。3.3无失真编码三、游程编码当图像不太复杂时，往往存在着灰度或颜色相同的图像子块。由于图像编码是按顺序对每个像素进行编码的，因而会存在多行的数据具有相同数值的情况，这样可只保留连续相同像素值和像素点数目。这种方法就是游程编码。

3.3无失真编码二值图像是指图像中的像素值只有两种取值，即“0”和“1”，因而在图像中这些符号会连续地出现，通常将连“0”这一段称为“0”游程，而连“1”的一段则称为“1”游程，它们的长度分别为L(0)和L(1)，往往“0”游程与“1”游程会交替出现，即第一游程为“0”游程，第二游程为“1”游程，第三游程又为“0”游程。3.3无失真编码【例】已知一个二值序列00101110001001……，根据游程编码规则，可知其游程序列为21133121……

图像中具有相同灰度（或颜色）的图像块越大、越多时，压缩的效果就越好，反之当图像越复杂，即其中的颜色层次越多时，则压缩效果越不好。对于复杂的图像，通常采用游程编码与哈夫曼编码的混合编码方式。

3.4有失真编码一、有失真编码理论失真不超过某给定条件下的编码可称为限失真编码。能使限失真条件下比特数最少的编码则为最佳编码。在限失真图像编码方法中，允许有一定的失真存在，因而可以大大提高压缩比。3.4有失真编码【条件信息量】

设信源发出符号为xi，编码输出为yj，用P(xi,yj)表示联合概率；用P(xi|yj)表示已知编码输出为yj，估计信源发出xi的条件概率；Q(yj|xi)表示发出xi而编码输出yj的概率。条件信息量定义为：I(xi|yj)=-logP(xi|yj)

I(yj|xi)=-logQ(yj|xi)3.4有失真编码【互信息量】

互信息量定义为：I(xi,yj)=I(xi)-I(xi|yj)，式中，I(xi)是xi所含的信息量，I(xi|yj)表示已知yj后xi还保留的信息量。它们的差，即互信息量代表了信源符号yj为xi所提供的信息量。互信息量是扣除了信道中噪声干扰或量化损失的信息量。

3.4有失真编码【平均互信息量】

可以证明：I(X,Y)=H(X)-H(X|Y)。

3.4有失真编码由于

3.4有失真编码所以

3.4有失真编码该式表明，平均互信息量由信源符号概率P(xi)、编码输出符号概率Q(yj)及已知信源符号出现的条件概率Q(yj|xi)所确定。在信源一定的情况下，P(xi)是确定的。编码方法的选择实际上是改变条件概率Q(yj|xi)，它同时也决定了引入失真（量化噪声）的大小。3.4有失真编码在允许一定失真D条件下的最低平均互信息量称为率失真函数，记为R(D)：

R(D)是在平均失真小于允许失真D以内能够编码的码率下界。3.4有失真编码

D‘代表平均失真，可将其写为：其中，d(xi,yj)表示信源发出xi，而被编码成yj时引起的失真量。3.4有失真编码对于数字型的符号，通常采用以下两种失真（误差）度量：均方误差，计算公式为(xi-yj)2

绝对误差，计算公式为|xi-yj|3.4有失真编码在图像编码中还采用超视觉阈值均方值:d=(xi-yj)2u其中：图像信号的误差在一定大小范围之内人眼感觉不出来，这个范围对应一个视觉阈值T。3.4有失真编码率失真函数还可以写成更为紧凑的式子：其中，QD=Q(D(Q)<D)，表示在所有允许失真范围D内的条件概率的集合，也就是各种编码方法。3.4有失真编码【有失真时信源编码的逆定理】

当数码率R小于率失真函数时，无论采用何种编码方式，其平均失真必大于D。

3.4有失真编码率失真函数R(D)与失真D的关系曲线：

3.4有失真编码率失真函数R(D)的性质：R(D)为有限值。当D<0时，不存在R(D)。当D≥Dmax（Dmax为正值，其数值上等于信号方差σ2）时，R(D)=0，表示此时所传输的数据信息毫无意义。当0<D<Dmax时，R(D)是一个下凸型连续函数，并且R(0)小于接收信号的熵值H(Y)。3.4有失真编码二、线性预测编码预测编码通过减小图像信息在时间上和空间上的相关性达到数据压缩的目的。对于一个图像信源，首先根据某一模型，并利用以往的样本值对新样本值进行预测，得出预测值，然后将预测值与实际样本值相减，从而得出误差值，最后对误差值进行量化、编码和传输。3.4有失真编码1、线性预测原理

1952年贝尔实验室的B.M.Oliver等人开始了线性预测编码理论的研究，同年，该实验室的C.C.Cutler取得了差分脉冲编码调制DPCM系统的专利，奠定了真正使用的预测编码系统的基础。3.4有失真编码DPCM编码原理3.4有失真编码设输入信号xn为tn时刻的取样值。是根据tn时刻以前已知的m个取样值xn-m，…，xn-1对xn所作的预测值，即ai(i＝1,…,m)称为预测系数，m为预测阶数。

3.4有失真编码

en为预测误差信号，显然:ai(i＝1,…,m)称为预测系数，m为预测阶数。设qn为量化器的量化误差，为量化器输出信号，可见qn=en-en＇。

3.4有失真编码接收端解码输出为，如果信号在传输过程中不产生误差，则有，，。此时发送端的输入信号xn与接收端的输出信息之间的误差为：3.4有失真编码2、最佳线性预测应用均方误差为极小值准则获得的线性预测称为最佳线性预测。线性预测DPCM中，对xn作最佳预测时，如何取用以前的已知像素值xn-1,xn-2,…,x1?3.4有失真编码3.4有失真编码前值预测：若取用现在像素xn的同一扫描行中前面最邻近像素x1来预测xn，即xn的预测值，则称为前值预测。一维预测（行内预测）：若取用xn的同一扫描行中前几个已知像素值，如x1,x5,…来预测xn，则称为一维预测。3.4有失真编码二维预测（帧内预测）：若取用xn的同一行和前几行若干个已知像素值，如x1,x5,x2,x3,x4,…来预测xn，则称为二维预测。三维预测（帧间预测）：若取用已知像素不但是前几行的而且还包括前几帧的，那么称为三维预测。3.4有失真编码【求一维最佳线性预测系数】

设xn是期望E{xn}=0的广义平稳随机过程，则：为了使最小，必定有：

，i=1，2，…，m。

3.4有失真编码解这m个联立方程可得ai（i=1，2，…，m）。由于xn的自相关函数为R(k)=E{xnxn-k}，且R(-k)=R(k)，因此：i＝1，2，…，m。写出矩阵的形式：3.4有失真编码3.4有失真编码【应用均方差极小准则所获得的各个预测系数ai之间的约束关系】3.4有失真编码在最佳预测前提下，可以证明预测误差的均方值为：因为E{xn}=0,所以R(0)即为xn的方差，可见：因而传送差值en比直接传送原始信号xn更有利于数据压缩。3.4有失真编码三、变换编码如果对图像数据进行某种形式的正交变换，并对变换后的数据进行编码，从而达到数据压缩的目的，这就是变换编码。变换编码是所有有损压缩国际标准的基础。

3.4有失真编码1、变换编码的工作原理变换编码不直接对原图像信号压缩编码，而首先将图像信号映射到另一个域中，产生一组变换系数，然后对这些系数进行量化、编码、传输。

3.4有失真编码图像变换编码一般采用统计编码和视觉心理编码。前者是把统计上彼此密切相关的像素矩阵，通过正交变换变成彼此相互独立，甚至完全独立的变换系数所构成的矩阵。后者即对每一个变换系数或主要的变换系数进行量化和编码。量化特性和变换比特数由人的视觉特性确定。3.4有失真编码变换编码也是一种限失真编码。经过变换编码而产生的恢复图像的误差与所选用的正交变换的类型、图像类型和变换块的尺寸、压缩方式和压缩程度等因素有关。在变换方式确定以后，还应选择变换块的大小。3.4有失真编码2、子块划分变换块的尺寸选得太小，