第六章图像数据压缩编码

第六章

图像数据的压缩编码6.1图像压缩编码概述一、图像编码的目的和应用：目的：在可能的情况下尽量减少图像数据的尺寸，以便于传输、存储、管理、处理和应用。图像数据量举例：视频图像：512×512×8×25bits/s≈150Mbit/s≈19MByte/s≈70,000MB/hr VCD：650M，74Min,约需要压缩100倍！传输带宽：CableATMMobilcommunication1.5～10Mbs播放速度：Upto34Mbs10Kbs～1Mbs医学图像：图像种类图像特征图像数/检查数据量/检查核医学128×128×1230～601～2MBMRI256×256×12608MB超声512×521×820～2305～60MB数字减影血管造影DSA512×512×815～404～10MBCT512×512×124020MB计算机放射成像2048×2048×12216MB数字化X线摄影2048×2048×12216MB数字化X线乳腺摄影4096×4096×124128MBPACS系统的需求习题：试问:(1)对一个具有三个符号的信源，有多少个唯一的Huffman码

(2)构造这些码字给出一幅8灰度级图像的灰度值分布情况如下表示，

(1)计算图像的熵

(2)对信源符号构造Huffman编码

(3)对信源符号构造S-F编码

(4)构造最优的B1码

(5)构造最优的S2码

(6)对每种编码计算平均码字长度和编码效率原始图像灰度级01/72/73/74/75/76/77/7原始图像各灰度级的像素790102385065632924512281二、压缩的可能性与图像保真度

1.图像中的数据冗余冗余空间冗余时间冗余结构冗余知识冗余视觉冗余信息熵冗余(编码冗余)其它冗余 2.图像在一些情况下允许一定程度的失真主观保真度客观保真度可能不完全统一保真度编码信息保持编码平均信息方法变换方法三、分类1.从图像信息角度对编码分类特征抽取2.从图像编码方法对编码分类预测方法其它利用图像的统计特征分配码字长度，达到压缩目的，如Huffman,S-F

等调制，1D-DPCM，2D-DPCM,帧间预测，自适应编码等频带编码，阈值编码，多维技术，自适应方法像素编码行程编码，等值线编码，位平面编码等混合编码，二值/图形编码，彩色图像编码，矢量量化，金字塔编码，基于知识的编码等1.等长码与不等长码四、图像编码的一般过程五、常用编码类型与举例映射变换量化器编码器解码器反映射原始图像信源码字恢复的图像等长码的码位长度都相等，即每一个码字均有相同的比特数，而不等长码则相反2.瞬时可译码与非瞬时可译码瞬时可译码：接收到一个码位即可译码非瞬时可译码：接收到下一码位才能译码3.唯一可译码非唯一可译码4.常用编码举例例如，某种代码，c1=0,c2=1,c3=01,c4=10,则序列0011具有多意性：0011c1c3c2c1c1c2c2输入数据W0W1W2W3W4W5W6W7自然码000001010011100101110111格雷码000001011010110111101100B1码c0c1c0c0c0c1c1c0c1c1c0c0c0c0c0c1B2码c00c01c10c11c00c00c00c01c00c10c00c11S2码000110110011011110111100111101不等长码B码中的c位称为延续位，实际传输时用0或1代替B1码和B2码为非瞬时可译码选用等长码或不等长码的原则：输入数据等概率分布时用等长码，否则，出现概率大的用短码，出现概率小的用长码说明：六、图像的熵与平均码字长度1.图像的熵(Entropy)

设数字图像像素的灰度集合为｛w1,w2,……,wM｝，其对应的概率分别为p1,p2,……,pM,按信息论中信源熵的定义，可以定义图像的熵H

为：(bit)由上述定义可以看到，图像的熵H是表示其各个灰度级比特数的统计平均值，例如：①设随机序列M由8个变量组成，等概率出现，即p1=p2=……,=p8，则：(bit)②设随机序列M由8个变量组成，p1=1,p2=……,=p8=0，则：(bit)

因此，当M

等于8时，H

的范围从0到3，即H＝0～log2M，其中H＝3说明信号的随机程度最大。2.图像的平均码字长度

设bk为数字图像第k

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

定义为：(bit)3.图像的编码效率：定义数字图像编码的效率为：

在R≧H

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

100％，Rd=0%6.2常用编码方法§6.2.1统计编码1.Huffman编码（Huffman

，1952）Huffman编码是根据可变长度最佳编码定理，应用Huffman编码算法而产生的一种编码方法它的平均码字长度在系统的输入概率集合下，比其它唯一可译码都小。因此也称为紧凑码。Huffman编码的原则是概率大的信息用短码，而概率小的信息用长码，即：若：p1(w1)>p2(w2)>……>pM(wM)则取：b1(c1)<b2(c2)<……<bM(cM)Huffman编码的编码步骤：①将信源符号按概率由大到小排列，概率相同的可以任意放②将两个最小概率相加，形成新的概率集合，并按①的原则重新排队③重复②的过程，直到仅剩下两个概率为止④分配码字进行编码，原则是从后到前，上0下1(或上1下0)Huffman编码举例：第一次重排编码结果输入数据对应概率W10.4W20.3W30.1W40.1W50.06W60.040.40.30.10.10.10.40.30.20.10.40.30.30.60.4第二次重排第三次重排第四次重排0111111000100000000010011011010001010100010100101101011010100110110100熵计算编码效率：编码效率：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.2bit说明：wi1011110000w1w3w6w2w4w5在解码时将输入的数码按树去分配，得到码字的切分和代码符号，例如，输入序列1011100010101从上述解码过程可以看到，虽然Huffman码不是等长码，但解码中能自动确定起止位。解码结果是唯一的。2.Shannon－Fano编码编码步骤：①将信源符号按概率由大到小排列，概率相同的可以任意放②将概率分为近似相等的两部分③进行编码，上半部分赋予0，下半部分赋予1④重复②

③直至编码完成S－F编码举例：编码结果输入数据对应概率W10.4W20.3W30.1W40.1W50.06W60.0401101111011111001101111011111111111011011100100编码效率：h＝

97.3%平均码长：R＝2.2bit3.采用B1

编码B类编码适用于灰度级概率按指数规律分布的图像，如打字图像。而S码适用于具有单调减少概率的输入信号。为说明B码的使用方法，对上述例题采用B1编码：编码结果输入数据对应概率W10.4W20.3W30.1W40.1W50.06W60.04C0C1C0C0C0C1C1C0C1C1编码效率：h＝

82.3%平均码长：R＝2.6bit而采用等长码时R＝3，h=71.3％解码问题：编码中的C称为延续位，在传输时用1或0代替，并交替进行。例如发送了三个符号W2W5W6，传输时为：0111100101

在解码时可以逐位判断是否应截断，在隔位比特变化时应截断，而连续比特不变则延续。因此B码不是瞬时可译码。例：有图像f(x,y)，如右图所示，灰阶为3bit，即0～7，比较几种不同编码的效果4.通过映射变换达到压缩编码0011111122333333444444445555555566667777777777777777777777777777①直接将图像传输：②采用S2码输入数据对应概率728/6458/6448/6436/6416/6464/6422/6402/64编码结果000110110011011110111100111101总码长为176bit平均码长为R＝176/64＝2.75bit编码效率：h

＝89.8%图像的熵：H＝2.47bit总码长为3×64＝192bit平均码长为R＝3bit编码效率：h

＝82.3%③采用Huffman

编码编码灰度概率重排1重排2重排3重排4重排5重排6728/6428282828283658/64881216202848/64888121636/64688816/6466864/644622/64302/6410010100000000101100111001111总码长为160bit平均码长：R＝160/64＝2.5bit编码效率：h

＝98.8%④先用差分映射进行变换，再用Huffman

编码差分映射:差分映射可以按行或按列进行，按行映射公式为：

y0=x0 y1=x0-x1 y2=x1-x2 …… yi=xi－1-xi00-10000020-10000040000000500000006000-1000700000007000000070000000映射得到的差分图像如右上图所示输入数据对应概率054/6473/64－13/6461/6451/6441/6421/64差分图像的灰度概率如右下表所示编码灰度概率重排1重排2重排3重排4重排5054/64545454545473/64334610－13/64333461/6422351/641241/64121/64对差分图像采用Huffman

编码的结果如下：01001011110111111001101总码长为88bit平均码长：R＝88/64＝1.375bit可见，经过差分映射后再进行编码，可以有效压缩编码数据。1.RLE编码的效率§6.2.2行程编码(RunLengthEncoding,RLE)

适用于有较多灰度相同对象的图像，例如海洋、湖泊的卫星图像，医学图像中的细胞，染色体，材料的显微图像等。计算机中的PCX和BMP格式的图像都采用行程编码进行压缩。RLE的原理相当简单，计算效率高。RLE编码采用整数对进行编码，例如右侧图像可以编码为(4,4)(4,1)(5,3)(4,1)(5,1)(7,2)(5,4)4444455545775555下面具体讨论RLE编码的效率和实现中的具体问题。

设图像的灰度级为M，一行的长度为N，则对每一行来说，行程数最少为1，最大为N。若将数对表示为(gk,lk)的序列，用普通二进制码存放(gk,lk)序列，并设一行中的行程数为m，则描述一行像素需要的码字长度为：m(log2M+log2N)bit而直接存储原图像一行所需的位数为：Nlog2Mbit显然，只有当m<<N

时，RLE的描述才是可取的。2.码的截断－换行问题方法1：预先存储行的长度，通过长度控制截断，缺点是长度不允许有误码例：BMP图像文件的编码BMP：文件头 位图信息 位图阵列方法2：将行的结束作为一个码对排入码流，其缺点是加长了序列长度，降低了效率。 Windows的BMP格式中支持BI-RLE8和BI-RLE4两种压缩类型的存储格式。由于使用了颜色索引表，因此可以用4位/像素存储16色的图像，用8位/像素存储256色的图像。下面介绍BI-RLE8的压缩格式： BI-RLE8的压缩格式由两字节的数据对序列组成，第一个字节给出对应画出的连续像素的数目，而所用的颜色索引在第二字节中。如果第1个字节为0，则第个字节的含意如下：0: 行结束例如下面的序列：0304050600031234560002780002030202780000061E0001解压缩为：行结束图像结束04040406060606061234567878------------78781E1E1E1E1E1E1： 图像结束2： 转义后面的两个字节，用这两个字节分别表示下一像素从当前位置水平和垂直位移的距离。n(0x03<n<0xff):转义后面的n个字节，其后的n

个像素分别由这n

个字节所指定的颜色画出。必须保证这种截断是4的整数倍，不足的位数补03.对于二值图像，由于只有两个可能的灰度取值，在一行中相邻两个行程的值一定交替出现，因此只需要在第一个行程中标出灰度值，于是一行的行程编码为：g1l1l2……lm其中g1只有两个值，只需要1bit存储，因此描述一行的行程编码的长度为：1+m•log2Nbit而用直接编码表示则需要Nbit4.为压缩图像，可以根据各种行程长度在图像中出现的概率，用不同长度的码字表示其编码，以提高图像数据的压缩率。适用于少细节的图像，如工程图纸，文字，指纹等。基本思路：对图像中灰度相同的区域，可以通过确定以下特征来表示：算法：§6.2.3等值线编码(1)包围这个区域的外围边界，即轮廓的方向序列(2)轮廓的起始位置(行数和列数)(3)轮廓所包围区域的灰度值若区域有一定面积，则对上述三个特征编码，可能比对区域内每个象素都分配码字节约，且图像细节越少，节省的比特数越多。寻找轮廓的算法计算轮廓方向序列的算法：T算法计算轮廓起始点的算法：IP算法先找到第一个起始点，并进行第一个轮廓方向序列的计算，再找到第二个起始点，进行第二个轮廓方向序列的计算，依次交叉进行，直到找到所有轮廓。1.轮廓方向序列的计算－T算法采用LML(LeftMostLooking)规则，沿轮廓前进。例：LML规则：①先向左看②向前看③向右看④向后看利用LML规则，判断所看的点是否灰度相等，若相等则前进，若所有方向都不等，则为孤立点。共有四种象素灰度：代码 灰度值表示为

00 a01 b10c11d选左上角的象素作为第一个轮廓的起始点！若等值线上的点走了两次，则按下列规则合并指示符：2.等值线上的点赋“指示符”第一次、第二次通过的方向标志DAADRRDRRDDDAR

RAAA合并后RDAIP1ARRRRRRDDDDDDRRRARRRRRAAAAADR或RA或或或输出输入指示符号分为I，A，R，D四种，初始化时各点赋指示符号I，然后根据等值线输入和输出的方向按下列规则更改：3.用IP算法寻找新起始点4.轮廓起始点判别规则5.在维护CPL表过程中，对新找到的起始点，确定其等值线，并重新扫描通过建立CPL表，并顺序扫描搜索，利用判别规则确定扫描过的点是否为新的起始点。CPL表的建立：(1)每扫描一行制一个表，扫描前表为空(2)对每一行扫描，从左到右逐象素进行判别，若遇到标记为A的点，将该点灰度值填入表中；若遇到标记为D，则将表中最后一个记录划去；若遇到标记为I，表的内容不变，但需要判别是否起始点；若标记为R，则表的内容不变。(3)每行扫描完毕，表一定是空的。(为什么？)在生成CPL表时，可利用下面的规则找到起始点：(1)扫描点指示符为I(2)灰度值与CPL表中标记的点的灰度不等DDDDDIP1ARRRRRRDRRRARRRRRAAAAA行号CPL说明0行1行1行1行2行3行4行5行aaADADabaRRRDDRAADARacAD做完上述建表和扫描、画等值线工作后，确定该图像有4条等值线！结果为空，表示该行无新起始点第1行第1列点作为IP2，利用T算法画等值线重新扫描，对轮廓2，遇到A，又遇到D，故填上b又消去b第1行第4列点作为IP3，但标记R不增加CPL项，遇D消去a无新起始点无新起始点无新起始点第1列为IP4，……同上同上空发送时将等值线的灰度值，IP点坐标和方向序列一一逐个发送，即可描述图像。6.做出编码表00011011等值线号灰度值IP行坐标IP列坐标IP点后各象素方向000000000001,01,01,01,01,01,01,10,10,10,10,10,11,11,11,11,……(共26个)010100100101,10,11,00101000110010,10,01,01,10,11,11,00,00,00111110100101,11上述采用三位自然码，亦可用Huffman编码进行优化。方向代码：§6.2.4预测方法编码(自学)一、预测方法编码的类型二、DPCM的基本原理三、DPCM方法中最佳系数的确定四、DPCM方法中图像降质的类型和原因要点§6.2.5LZW压缩算法(自学)一、LZW压缩算法说明，王广志编二、lzwcompression，ByBobMontgomery三、lzwandgifexplained，BySteveBlackstock补充材料：

上述编码均在图像空间进行操作，称为空域方法。而基于图像变换的方法称频域方法。§6.2.6变换方法压缩编码频域方法的基础：频域方法一般为非信息保持编码！频域方法的处理流程：构造子图像正变换重新量化符号编码合并子图像符号解码反变换输入图像压缩图像压缩图像解压图像通过可逆的线性变换将图像映射为一组变换系数，达到能量集中的目的，从而舍弃能量很小的系数，达到压缩的目的。频域方法的优点：压缩比高，视觉效果好1.子图像尺寸的选择原则变换编码中的主要问题：子图像尺寸的选择变换方法的选择比特分配方法子图像尺寸的选择影响到编码误差和计算的复杂度，实际中