第五章图像编码(1)

2024/3/261第五章图像编码（1）

信息与通信工程学院张洪刚zhhg@25.1图像编码介绍5.1.1图像编码技术的必要性：1.信息传输方式发生了很大的改变通信方式的改变

文字+语音图像+文字+语音Instagram每天图片上传量约为6000万张；今年2月份WhatsApp每天的图片发送量为5亿张；国内的微信朋友圈也是以图片分享为驱动。35.1.1图像编码技术的必要性

2.图像传输与存储需要的信息量空间：

1）彩色视频信息

对于电视画面的分辨率640*480的彩色图像，每秒30帧，则一秒钟的数据量为：

640*480*24*30=221.12M

所以播放时，需要221Mbps的通信回路。

4

2.图像传输与存储需要的信息量空间：

2）传真数据如果只传送2值图像，以200dpi的分辨率传输，一张A4稿纸的内容的数据量为：

1654*2337*1=3888768bit

5.1.1图像编码技术的必要性55.1.2图像编码技术的可能性1.数字图像本身的特征带来的数据压缩的可能性

1)图象中象素灰度出现的不均匀性，造成图象信息熵冗余,即用同样长度比特表示每一个灰度，则必然存在冗余。

2)图象能量在变换域内分布的不均匀性，比如大部分能量集中在低频部分，而小部分能量集中在高和较高的频率部分。63)图象象素灰度在时间和空间上的相关性造成信息冗余。例如*空间冗余，邻近象素灰度分布的相关性很强；*时间冗余：序列图象帧间画面对应象素灰度的相关性很强；*结构冗余：图像中存在重复出现或相近的纹理结构，可以通过特定的过程来生成。5.1.2图像编码技术的可能性2024/3/267时间冗余：序列图象帧间画面对应象素灰度的相关性很强。结构冗余：重复出现或相近的纹理结构2024/3/2689描述语言

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

2）“这是一幅2*2的图像，整幅图都是红色的”。

由此我们知道，整理图像的描述方法可以达到压缩的目的。图像中的数据冗余的概念10图像冗余无损压缩的原理RGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGB16RGB从原来的16*3*8=284bits压缩为：(1+3)*8=32bits图像中的数据冗余的概念11图像冗余有损压缩的原理36353434343434323434333730343434343434343435343431343434343434343434343434343434343434343434343434342534图像中的数据冗余的概念12实际图像中冗余信息的表现（灰度图）图像中的数据冗余的概念13图象的视觉冗余（彩色）

R

G

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

由于一幅图像存在数据冗余和主观视觉冗余，我们的压缩方式就是从这两方面着手来开展的。1）因为有数据冗余，当我们将图像信息的描述方式改变之后，可以压缩掉这些冗余。2）因为有主观视觉冗余，当我们忽略一些视觉不太明显的微小差异，可以进行所谓的“有损”压缩。图像中的数据冗余的概念154.应用环境允许图象有一定程度失真1)接收端图象设备分辨率较低，则可降低图象分辨率；2)根据人的视觉特性对不敏感区进行降分辨率编码（视觉冗余）；3)应用方关心图象区域有限，可对其余部分图象可采用空间和灰级上的粗化；4)对于识别，图象特征抽取和描述也是数据压缩。161.等长码与不等长码映射变换量化器编码器解码器反映射原始图像信源码字恢复的图像等长码的码位长度都相等，即每一个码字均有相同的比特数，而不等长码则相反常用编码类型5.1.3编码过程与编码分类173.唯一可译码与非唯一可译码例如，某种代码，c1=0,c2=1,c3=01,c4=10,

则序列0011具有多意性：0011c1c3c2c1c1c2c22.瞬时可译码与非瞬时可译码瞬时可译码：接收到一个码位即可译码非瞬时可译码：接收到下一码位才能译码185.1.4图像的熵与平均码字长度1.图像的熵

设数字图像像素的灰度集合为｛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说明信号的随机程度最大。192.图像的平均码字长度

设bk为数字图像第k

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

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

在R≧H

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

100％，Rd=0%2024/3/26225.2统计编码5.2.1Huffman编码（Huffman

，1952）Huffman编码是根据可变长度最佳编码定理，应用Huffman编码算法而产生的一种编码方法它的平均码字长度在系统的输入概率集合下，比其它唯一可译码都小。因此也称为紧凑码。Huffman编码的原则是概率大的信息用短码，而概率小的信息用长码，即：若：p1(w1)>p2(w2)>……>pM(wM)则取：b1(c1)<b2(c2)<……<bM(cM)2024/3/2623Huffman编码的编码步骤：①将信源符号按概率由大到小排列，概率相同的可以任意放②将两个最小概率相加，形成新的概率集合，并按①的原则重新排队③重复②的过程，直到仅剩下两个概率为止④分配码字进行编码，原则是从后到前，上0下1(或上1下0)2024/3/2624Huffman编码举例：第一次重排编码结果输入数据对应概率W10.4W20.3W30.1W40.1W50.06W60.040.40.30.10.10.10.40.30.20.10.40.30.30.60.4第二次重排第三次重排第四次重排01111110001000000000100110110100010101000101001011010110101001101101002024/3/2625熵计算编码效率：编码效率：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码不是等长码，但解码中能自动确定起止位。解码结果是唯一的。2024/3/2626Huffman编码特点优点平均码长>=熵平均码长<等长码需要的码字码长与概率成反比分布唯一可译码瞬时可译码缺点编码过程强烈依赖概率结构，不断排序，工作量大码字长度变化大，码字结构复杂，实现困难。2024/3/2627构造结果不唯一01与10的不同；概率相同的情况码字字长参差不齐硬件实现不方便对不同的信源的编码效率不同信源概率是2-n

时

哈夫曼编码效率达到100%信源概率相等时

哈夫曼编码效率最低只有在概率分布很不均匀时,哈夫曼编码才会收到显著的效果；信源分布均匀,一般不使用哈夫曼编码哈夫曼编码——特点2024/3/2628Huffman编码在图像压缩中的实现

我们知道，对一幅图像进行编码时，如果图像的大小大于256时，这幅图像的不同的码字就有可能是很大，例如极限为256个不同的码字。对整幅图直接进行Huffman编码时，小分布的灰度值，就有可能具有很长的编码。如：100位以上，这样不但达不到压缩的效果反而会使数据量加大，应该如何处理？2024/3/2629常用的且有效的方法是：将图像分割成若干的小块，对每块进行独立的Huffman编码。例如：分成的子块，就可以大大降低不同灰度值的个数（最多是64而不是256）。2024/3/26305.2.2.Shannon－Fano编码编码步骤：①将信源符号按概率由大到小排列，概率相同的可以任意放②将概率分为近似相等的两部分③进行编码，上半部分赋予0，下半部分赋予1④重复②③直至编码完成S－F编码举例：编码结果输入数据对应概率W10.4W20.3W30.1W40.1W50.06W60.0401101111011111001101111011111111111011011100100编码效率：h＝

97.3%平均码长：R＝2.2bit2024/3/2631适用于少细节的图像，如工程图纸，文字，指纹等。基本思路：对图像中灰度相同的区域，可以通过确定以下特征来表示：5.3等值线编码(1)包围这个区域的外围边界，即轮廓的方向序列(2)轮廓的起始位置(行数和列数)(3)轮廓所包围区域的灰度值若区域有一定面积，则对上述三个特征编码，可能比对区域内每个象素都分配码字节约，且图像细节越少，节省的比特数越多。2024/3/2632算法：寻找轮廓的算法计算轮廓方向序列的算法：T算法计算轮廓起始点的算法：IP算法先找到第一个起始点，并进行第一个轮廓方向序列的计算，再找到第二个起始点，进行第二个轮廓方向序列的计算，依次交叉进行，直到找到所有轮廓。2024/3/26335.3.1轮廓方向序列的计算－T算法采用LML(LeftMostLooking)规则，沿轮廓前进。例：LML规则：①先向左看②向前看③向右看④向后看利用LML规则，判断所看的点是否灰度相等，若相等则前进，若所有方向都不等，则为孤立点。共有四种象素灰度：代码 灰度值表示为

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

RAAA合并后RDAIP1ARRRRRRDDDDDDRRRARRRRRAAAAADR或RA或或或输出输入指示符号分为I，A，R，D四种，初始化时各点赋指示符号I，然后根据等值线输入和输出的方向按下列规则更改：2024/3/26353.用IP算法寻找新起始点通过建立一个比较表，并顺序扫描搜索，利用判别规则确定扫描过的点是否为新的起始点。表的建立：(1)每扫描一行制一个表，扫描前表为空(2)对每一行扫描，从左到右逐象素进行判别，若遇到标记为A的点，将该点