第10章 图像编码

第10章图像编码

由于通信方式和通信对象的改变带来的最大问题是：

传输带宽、速度、存储器容量的限制。给我们带来的一个难题，也给了我们一个机会：

如何用软件的手段来解决硬件上的物理极限。10.1概述10.1.1图像编码的缘起实例：图像传输与存储需要的信息量空间

1）彩色视频信息对于电视画面的分辨率640*480的彩色图像，每秒30帧，则一秒钟的数据量为：640*480*24*30=221.12M

所以播放时，需要221Mbps的通信回路。参考数据：宽带网为512K,电话线为56K。存储时，1张CD可存640M，则仅可以存放2.89秒的数据。2）传真数据如果只传送2值图像，以200dpi的分辨率传输，一张A4稿纸的内容的数据量为：1654*2337*1=3888768bit

按目前14.4K传输速率，需要传送的时间是：270秒（4.5分）

按每分钟4元计算：18元10.1概述图像编码主要研究压缩数码率，即高效编码问题，用最少的数码传递最大的信息量。利用图像信号的统计特性及视觉对图像的生理学和心理学特性对图像进行信源编码。图像编码属于信源编码的范围。10.1概述描述语言

1）“这是一幅2*2的图像，图像的第一个像素是红的，第二个像素是红的，第三个像素是红的，第四个像素是红的”。

2）“这是一幅2*2的图像，整幅图都是红色的”。整理图像的描述方法可以达到压缩的目的。10.1.2图像中数据冗余的概念10.1概述图像冗余无损压缩的原理RGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGB16RGB从原来的16*3*8=284bits压缩为：(1+3)*8=32bits10.1概述10.1.2图像中数据冗余的概念图像冗余有损压缩的原理3635343434343432343433373034343434343434343534343134343434343434343434343434343434343434343434343434253410.1概述10.1.2图像中数据冗余的概念图象的视觉冗余（彩色）

R

G

B2488822*2*2=242=16,777,216(248,27,4)(251,32,15)(248,27,4)(248,27,4)10.1概述10.1.2图像中数据冗余的概念图像冗余信息分析结论

由于一幅图像存在数据冗余和主观视觉冗余，图像压缩方式就是从这两方面着手来开展的。1）因为有数据冗余，将图像信息的描述方式改变之后，可以压缩掉这些冗余。2）因为有主观视觉冗余，如果忽略一些视觉不太明显的微小差异，可以进行有损压缩。10.1概述10.1.2图像中数据冗余的概念10.1.3

压缩的可能性与图像保真度

冗余空间冗余时间冗余结构冗余知识冗余视觉冗余信息熵冗余(编码冗余)其它冗余2.图像在一些情况下允许一定程度的失真主观保真度客观保真度可能不完全统一10.1概述1.图像中的数据冗余1、客观保真度：均方误差和均方信噪比2、主观保真度：主观评价10.1概述10.1.3

压缩的可能性与图像保真度

10.1.4图像数据压缩方法分类保真度编码：丢失一些无用或作用不大的信息。信息保持编码：信息没有丢失。1.从图像信息角度对编码分类特征抽取：只对需要的特征信息进行编码。10.1概述第一代压缩编码

主要是根据传统的信源编码方法，以去除冗余为基础对图像进行编码。第二代压缩编码

较新的编码方法，结合分形、模型基、神经网络、小波变换等数学工具，充分利用视觉系统生理心理特性和图像信源的各种特性对图像进行数据压缩。2.从图像编码方法对编码分类10.1概述10.1.4图像数据压缩方法分类像素编码变换编码预测编码

轮廓编码方块编码增量调制熵编码算术编码Fourier变换Walsh-Hadamard变换DPCM调制第一代压缩编码其他编码行程编码10.1概述10.1.4图像数据压缩方法分类子带编码模型编码分层编码分型编码第二代压缩编码10.1概述10.1.4图像数据压缩方法分类10.1.5

常用编码类型与举例1.等长码与不等长码等长码的码位长度都相等，即每一个码字均有相同的比特数，而不等长码则相反。2.瞬时可译码与非瞬时可译码瞬时可译码：接收到一个码位即可译码非瞬时可译码：接收到下一码位才能译码10.1概述3.唯一可译码非唯一可译码例如：某种代码，c1=0,c2=1,c3=01,c4=10,则序列0011具有多意性：0011c1c3c2c1c1c2c210.1.5

常用编码类型与举例10.1概述10.2.1熵编码基本概念一、图像的熵与平均码字长度1.图像的熵(Entropy)设数字图像像素的灰度集合为｛w1,w2,……,wM｝，其对应的概率分别为p1,p2,……,pM,按信息论中信源熵的定义，可以定义图像的熵

H

为：(bit)由上述定义可以看到：图像的熵H

是表示其各个灰度级比特数的统计平均值10.2熵编码例如：①设随机序列M由8个变量组成，等概率出现，即p1=p2=……,=p8，则：(bit)②设随机序列M由8个变量组成，p1=1,p2=……,=p8=0，

则：(bit)因此，当M

等于8时，H

的范围从0到3，即H＝0～log2M，其中H＝3说明信号的随机程度最大。10.2.1熵编码基本概念10.2熵编码2.图像的平均码字长度设bk为数字图像第k

个码字ck的长度(二进制数的位数)，其对应出现的概率为pk,则该数字图像的码字平均长度

R定义为：(bit)10.2.1熵编码基本概念10.2熵编码3.图像的编码效率：在

R≧H

情况下总可以设计出某种无失真编码方法，若R接近于H，则说明码编的较好，称为最佳编码。若要求编码结果R<H,则必然要丢失信息而引起图像失真。定义数字图像编码的效率为：同时定义图像编码的冗余度为：4.图像压缩比：图像压缩前后所需的信息存储量之比。5.香农信息论：10.2.1熵编码基本概念10.2熵编码二、图像的变长最佳编码定理在变长编码中，若对出现概率大的信息赋予短码字，而对于出现概率小的信息赋予长码字，如果码字长度严格按照所对应符号出现的概率大小而逆序排列，则此种编码结果的平均码字长度一定小于其它任何排列形式得到的编码。10.2.1熵编码基本概念10.2熵编码例如：图像的熵：(bit)采用等长编码：平均码长R＝2(bit)，编码效率h＝87.5％，Rd=12.5%输入数据W1W2W3W4概率1/21/41/81/8W1W2W3W400011011W1W2W3W4010110111采用不等长编码：平均码长R＝7/4(bit)，编码效率h＝

100％，Rd=0%10.2.1熵编码基本概念10.2熵编码10.2.2哈夫曼（Huffman）编码

Huffman编码是根据可变长度最佳编码定理，应用Huffman编码算法而产生的一种编码方法。它的平均码字长度在系统的输入概率集合下，比其它唯一可译码都小。因此也称为紧凑码。Huffman编码的原则是概率大的信息用短码，而概率小的信息用长码，即：若：p1(w1)>p2(w2)>……>pM(wM)则取：b1(c1)<b2(c2)<……<bM(cM)10.2熵编码Huffman编码的编码步骤：①将信源符号（图像的灰度等级）按概率由大到小排列，概率相同的可以任意放置。②将两个最小概率相加，形成新的概率集合，并按①的原则重新排队③重复②的过程，直到仅剩下两个概率为止④分配码字进行编码，原则是从后到前，上0下1(或上1下0)例：设一幅图像的六个灰度等级w1,w2,w3,w4,w5,w6出现的概率分别为0.4,0.3,0.1,0.1,0.06,0.04，对此图像进行Huffman编码10.2.2哈夫曼（Huffman）编码10.2熵编码第一次重排编码结果输入数据对应概率W10.4W20.3W30.1W40.1W50.06W60.040.40.30.10.10.10.40.30.20.10.40.30.30.60.4第二次重排第三次重排第四次重排111110001000000000100110110100010101000101001011010110101001101101001010.2.2哈夫曼（Huffman）编码10.2熵编码熵计算编码效率：编码效率：h=2.14/2.2=97.3%平均码长：R＝0.4＋0.3×2＋0.1×3＋0.1×4＋0.06×5＋0.04×5＝2.2bit10.2.2哈夫曼（Huffman）编码10.2熵编码

为在接收端对上述编码进行解码，可以采用树形解码方法唯一地解码，每输入一位即可确定分支情况，并自动确定码字的起止位。为此需要建立右图的解码树。wi1011110000w1w3w6w2w4w5

在解码时将输入的数码按树去分配，得到码字的切分和代码符号，例如，输入序列1011100010101

从上述解码过程可以看到，虽然Huffman码不是等长码，但解码中能自动确定起止位。解码结果是唯一的。10.2.2哈夫曼（Huffman）编码10.2熵编码10.2.3Shannon-Fano编码编码步骤：将信源符号按概率由大到小排列，概率相同的可以任意放置；②将概率分为近似相等的两部分；③进行编码，上半部分赋予0，下半部分赋予1；④重复②

③直至编码完成。Huffman编码需要多次排序，当信源取值很多时计算不方便，Fano和Shannon分别提出了类似方法，使编码更简单：10.2熵编码编码结果输入数据对应概率W10.4W20.3W30.1W40.1W50.06W60.0401010111001101111011111111111011011100100S－F编码举例：编码效率：h＝

97.3%平均码长：R＝2.2bit001101010.2.3Shannon-Fano编码10.2熵编码Huffman编码使用二进制符号进行编码，该方法在许多情况下无法得到最佳的压缩效果。

假设某个信源符号出现的概率为80%，其自信息量为：

即用0.322位编码就可以了，而Huffman编码只能分配一位0或一位1进行编码。若采用Huffman编码，80%的信源数据所需的码字长度要比理想编码后的码字长度多5倍。算术编码能有效解决Huffman编码面临的压缩效果不理想的问题！10.2.4算术编码10.2熵编码

算术编码不是将单个信源符号映射成一个码字，而是把整个信源表示为实数线上的0到1之间的一个区间（Interval），其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都要缩短为一个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。采用算术编码每个符号的平均编码长度可以为小数。10.2.4算术编码算术编码基本原理10.2熵编码例：假设信源符号为X={a1,a2,a3,a4},其中各符号的概率为P(X)={1/8,1/4,1/2,1/8},若对符号序列a3a3a2a4进行算术编码，其编码过程为：首先根据信源符号的概率，确定初始区间；即：符号a1a2a3a4概率1/8(0.001)1/4(0.01)1/2(0.1)1/8(0.001)区间[0,0.001)[0.001,0.011)[0.011,0.111)[0.111,1.0)10.2.4算术编码10.2熵编码然后按如下步骤进行编码：初始化编码点C0=0，区间间隔A0=1；依次对符号序列进行编码，并更新编码点Ci和区间间隔Ai；其中Ci=Ci-1+Ai-1*Pi

Ai=Ai-1*piPi

为待编码符号的区间间隔最小值（累积概率）；pi为待编码符号对应的概率。③编码结束，输出新的编码点Ci对a3a3a2a4的编码过程如下：10.2.4算术编码10.2熵编码步骤输入1a3

符号编码间隔[0.011,0.111)

2a3

符号编码间隔[0.1001,0.1101)3a2

符号编码间隔[0.10011,0.10101)

4a4

符号编码间隔[0.1010011,0.10101)

Ci=Ci-1+Ai-1*Pi

Ai=Ai-1*pi对a3a3a2a4的编码过程如下：输入符号a3输入符号a3输入符号a2输入符号a4解码过程码字0.1010011解码过程是：[（收到的码字串)－(已解符号子区间的下端点）]÷

（字符概率)累积概率

收到码字串0.1010011时，由于这个码字串指向子区间[0.011,0.111]，因此，解出的第一个符号应为a3;收到码字串a3累积概率a3字符概率

该字串仍然落在[0.011,0.111]区间内，因此，解出的第二个字符为

a3符号a1a2a3a4概率1/8(0.001)1/4(0.01)1/2(0.1)1/8(0.001)区间[0,0.001)[0.001,0.011)[0.011,0.111)[0.111,1.0)解码第三个字符：a3的累积概率a3字符的概率收到码字串

该字符串落在[0.001,0.011]区间，因此，解出的第三个字符为

a2符号a1a2a3a4概率1/8(0.001)1/4(0.01)1/2(0.1)1/8(0.001)区间[0,0.001)[0.001,0.011)[0.011,0.111)[0.111,1.0)a2的累积概率a2字符的概率收到码字串

该字符串落在[0.111,1]区间，因此，解出的第三个字符为

a4算术编码的特点:

1.实际的计算机精度有限,会产生溢出问题;2.对整个消息只产生一个编码,因此译码器必须接受到这个实数后才能译码;3.对错误很敏感.4.在信源符号概率接近时，算术编码比霍夫曼编码效率高，但硬件实现比霍夫曼编码要复杂。10.2熵编码10.2.4算术编码10.3预测编码预测编码的理论基础是现代统计学和控制论，它主要减少了数据在时间和空间上的相关性。预测编码有线性预测和非线性预测。

对于静止图像来说，预测编码将被图像变换编码所取代。而预测编码对于视频信号来说，它充分利用了连续帧之间的统计冗余性，是当今主流技术。10.3.1预测编码概述预测编码是根据图像数学模型利用以往的样本值对于新样本值进行预测，然后将样本的实际值与其预测值相减得到一个误差值，对这一误差值进行编码。如果模型足够好且样本序列在时间上相关性较强，那么误差信号的幅度将远远小于原始信号，从而可以用较少的电平对其差值量化得到较大的数据压缩效果。

如果能精确地预测数据源输出，那就不存在关于数据源的不确定性，因而也就不存在要传输的信息。

然而没有一个实际的系统能找到其完整的数学模型，能找到的最好预测器是以某种最小化的误差对下一个采样进行预测的预测器。10.3预测编码10.3.1预测编码原理

通常预测器的设计不是利用数据源的实际数学模型，因为数据源的实际数学模型是非常复杂，而且是时变的。实验结果表明以最小均方预测误差设计的预测器不但能获得最小均方预测误差，同时在视觉效果上也是比较好的。

预测法编码的实践性成果主要体现在DPCM的应用上。DPCM充分利用了图像中相邻象素之间的相关性。差值脉冲编码调制DPCM(DifferentialPulseCodeModulation)：首先将象素按时间先后排序，若n时刻象素Xn可由其前面的M个象素值来估计，估计值为，则误差e=Xn-，满足e最小并对e进行量化编码。10.3预测编码10.3.1预测编码原理10.3.2DPCM的基本原理设输入信号XN为tN时刻的亮度取样值；为tN时刻以前已知象素亮度取样值X1,X2,…,XN-1对XN所作的预测值（估计值）；eN为差值信号，也称误差信号。为量化器的量化误差，为量化器输出信号接收端输出为在接收端复原的象素值与发送端的原始输入象素值XN之间的误差为：10.3.2DPCM的基本原理结论：DPCM系统的误差来源于发送端的量化器，与接收无关。①若去掉量化器，那么则这样就可以完全不失真的恢复输入信号XN，可实现信息保持编码。②如果，那么输入信号和复原信号输出之间就一定存在误差，从而产生图像质量的某种失真。10.3.2DPCM的基本原理图像样本在t时刻XN的线性预测10.3预测编码10.3.3最佳线性预测采用最小均方误差准则，以获得最佳线性预测值。定义XN的均方误差为为使其最小，分别对各个ai求偏微分，即为求极值，令当时简记为10.3.3最佳线性预测令Xi和Xj的协方差Rij为则当所有的协方差Rij为已知时，即可求出N-1个预测系数ai最佳预测问题就变成求图像的协方差了，假定图像为平稳随机过程且均值为零，则方差在最佳预测的各个ai已知时，其输出误差信号的方差为显然即误差信号序列{ei}的相关性比原图像信号输入序列{Xi}相关性小很多。使达到最小趋近于零，即为最佳预测。10.3.3最佳线性预测量化器的最佳设计有两类：①量化比特数b（量化等级）确定，根据最小均方误差原则设计。②量化误差一定的情况下，减小量化比特数b。10.3.4最佳量化器10.3预测编码DPCM系统的预测器、量化器的设计以及传输信号的影响，会引起图像的失真。归纳起来有以下几种：①斜率过载噪声②散粒噪声③伪轮廓图像④边沿忙乱

为了纠正以上四种噪声，应采用自适应量化，即量化步长随图像灰度等级变化的陡、缓而自适应调节。DPCM系统存在的问题DPCM在传输过程中，一旦遇到信道干扰，就会呈彗星状向右下方蔓延。

一般来讲二维预测要比一维预测的抗干扰能力强，对通信信道的质量要求也较高。一维信道误码率应小于10-9，二维信道误码率应小于10-8。10.3.5DPCM系统中的噪声10.3预测编码

预测编码和Huffman编码直接对象素在图像空间进行操作，称为空域变换。基于图像正交变换的编码方法常称为频域方法。熵保持性质：正交变换不会丢失信息；能量保持性质：可以由变换域中的有限个系数来重建信号；能量重新分配和集中：可以对信号能量进行重新分配，可以舍弃一些能量较小的系数，或者根据谱点能量大小的分配不同的存储位数；去相关特性：可以使相关的空间域变为不相关的变换域，使相关性之中的多余度得以去除。正交变换的性质：正交变换可以使图像在变换域中变为能量保持、集中且不相关。如果用变换系数来代替空间样值编码传送，只需对变换系数中能量比较记集中的部分进行编码，就可以达到压缩的目的。10.4.1变换编码概述10.4变换编码基于图像变换的编码方法常称为频域方法。压缩比高，视觉效果好，一般为非信息保持编码。图像变换编码的系统框图：10.4变换编码10.4.1变换编码概述

在变换编码中，首先要将图像数据分割成子图像，然后对子图像数据块实施某种变换，如DCT变换，那么子图像尺寸取多少好呢？根据实践证明子图像尺寸取4×4、8×8、16×16适合作图像的压缩，这是因为：

<1>如果子图像尺寸取得太小，虽然计算速度快，实现简单，但压缩能力有一定的限制。

<2>如果子图像尺寸取得太大，虽然去相关效果变好，因为象DFT、DCT等正弦型变换均具有渐近最佳性，但也渐趋饱和。若尺寸太大，由于图像本身的相关性很小，反而使其压缩效果不显示，而且增加了计算的复杂性。

10.4.2子图像尺寸选择10.4变换编码FT能量集中于中心（示意图）移中FT原图像f（x，y）能量分布于四角（示意图）10.4.3二维傅立叶变换编码10.4变换编码WT移中FTWT将能量集中于频率平面的左上角移中FT将能量集中于频率平面的中央10.4.4二维沃尔什－哈达玛变换编码WT截取图像的左上角保存补0经反变换，恢复原图像10.4.4二维沃尔什－哈达玛变换编码跳过白块编码游程长度编码准最佳可变长度编码预测差值量化编码识别编码方块编码二值图像常用的编码方法二值图像是指只有两个灰度级的图像。例如文字组成的文件扫描图、气象图、工程图、指纹卡、军用态势图…10.5二值图像编码10.5.1二值图像编码概述基本原理

大多数二值图像中的黑象素只占整个图像的一小部分，若能跳过白色象素，只对黑色象素编码，则表示图像的比特数就能减少，平均比特数就能大大降低。一维WBS将图像的每条扫描线分成若干段，每一段的象素个数为n对全部是白色的象素用0表示对至少有一个黑象素的线段用n+1个比特表示，第一个比特为1，其余n比特采用直接编码如：黑白白黑～～11001白白白白～～0设长度为N的象素段出现全白的概率为PN，则一维WBS编码平均字长bN为：10.5.2跳过白块编码（WBS）二维WBS将一维WBS的象素段推广为象素块。设象素块大小为M×N，全白象素块用“0”表示否则用M×N个比特来直接编码自适应WBS编码根据图像的局部结构或统计特性，改变象素块的大小，进一步提高压缩效果，这就是所谓的自适应WBS编码。改进型的一维WBS编码：对于一维的WBS编码，如果一条扫描线全为白象素时，则用1比特“0”表示，否则先赋1码元，再用正常的一维WBS编码。自适应的WBS编码可以使得表示图像的bit数下降很多，但是为了自适应增加了设备的复杂性。10.5.2跳过白块编码（WBS）对二值图像的每一扫描行来看，总是由若干段连着的黑象素段和连着的白象素段组成，分别称为“黑长”和“白长”。黑长和白长总是交替发生。对于不同长度按其发生概率分配以不同长度的码字，这就是游程长度编码(RLC)。基本原理设二值图象中有长度为1,2,…，N等不同长度的黑长和白长，N为一个扫描行的象素数。如果不分黑长和白长进行统一编码，则图像对游程长度的熵H为：其中Pi为游程长度为i所发生的概率。游程(行程)：连续灰度取值相同的象素个数(长度)。10.5.3游程长度编码（RLC）游程的平均长度E为：游程的符号熵（即象素的熵）为：根据信号编码定理，每个游程的平均长度B满足：即每个象素的熵h为用游程长度编码所得的最小比特率的估计值10.5.3游程长度编码（RLC）为了进一步减小比特率，可以将黑长和白长分开分别编码，因为它们出现的概率不同。对白长进行最优编码后，应该有：令Ew为表示白长的平均长度于是，10.5.3游程长度编码（RLC）同样，对于黑长，有经过黑白统计平均，每个象素的熵值hbw为每个象素的编码比特数bbw为综合以上各式：由于hbw<h，因此黑长白长分别编码比混合编码效果好。要估算RLC编码的最小比特率，必须知道图像游程长度的概率分布。这是十分复杂的测量技术，往往采用某些实用的游程长度概率模型来计算。10.5.3游程长度编码（RLC）

实际使用的压缩编码方法，都是综合了各种方法而达到最高的效率。在计算机图像压缩编码方面，已经有一批标准，并在不断发展。MPEG-1标准，1992

MPEG-2标准，1993

H.261标准(CCITT)H.263标准MPEG-4标准，1999第1版，2000第2版MPEG-7标准，1996－1998，2001年底

二值图像压缩标准静止图像压缩标准视频图像压缩标准G3G4JBIGCCITTGroup3&Group4JointBilevelImagingGroup,1991JPEGJointPictureExpertGroup,1991标准化组织：ISO(国际标准化组织)ITU(国际电信联盟)CCITT(国际电报电话咨询委员会，ITU的前身)JPEG2000H.26L标准10.6图像压缩编码国际标准

JPEG是一个应用广泛的静态图像数据压缩标准，其中包含两种压缩算法(DCT和DPCM)，并考虑了人眼的视觉特性，在量化和无损压缩编码方面综合权衡，达到较大的压缩比(25:1以上)。JPEG既适用于灰度图像也适用于彩色图像。JPEG有三种编码系统：1、基于DCT变换的有损编码；2、扩展编码系统(高压缩比、高精度等)；3、无损独立编码系统。10.6图像压缩编码国际标准10.6