计算机图像处理-第六章课件

计算机图像处理

郭永芳36160251@第六章图像编码与压缩6.1概述6.1.1图像数据压缩的必要性与可能性数据压缩主要研究数据的表示、传输、变换和编码方法，目的是减少存储数据所需的空间和传输所用的时间。图像编码与压缩就是对图像数据按一定的规则进行变换和组合，达到以尽可能少的代码（符号）来表示尽可能多的信息。图像数据的特点之一是信息量大。海量数据需要巨大的存储空间。如多媒体中的海量图像数据，不进行编码压缩处理，一张600M字节的光盘，只能存放20秒左右的640×480像素的图像，可见没有编码压缩，多媒体信息的保存有多么困难。在现代通信中，图像传输已成为重要内容。采用编码压缩技术，减少传输数据量，是提高通信速度、实现实时性的重要手段。可以说，没有图像编码与压缩技术的发展，大容量图像信息的存储与传输是难以实现的，多媒体、信息高速公路等新技术在实际中的应用会碰到很大困难。从信息论观点看，描述图像信源的数据由有用数据和冗余数据两部分组成。冗余数据主要表现为：编码冗余（信息熵冗余）象素间冗余（空间冗余、时间冗余、结构冗余）心理视觉冗余如果能减少或消除其中的1种或多种冗余，就能取得数据压缩的效果。因此图像信息的压缩是可能的。但到底能压缩多少，除了和图像本身存在的冗余度大小有关外，很大程度取决于对图像质量的要求。

广播电视压缩比3∶1可视电话压缩比1500∶1目前高效图像压缩编码技术已能用硬件实现实时处理，在广播电视、工业电视、电视会议、可视电话、传真和互连网、遥感等多方面得到应用。6.1.2图像编码压缩的分类根据解压重建后的图像和原始图像之间是否具有误差，图像编码压缩分为无误差（亦称无失真、无损、信息保持）编码和有误差（有失真或有损）编码两大类。根据编码作用域划分，图像编码为空间域编码和变换域编码两大类。图像压缩无损编码有损编码霍夫曼编码行程编码算术编码预测编码变换编码其它编码6.2图像保真度准则描述解码图像相对原始图像偏离程度的测度称为保真度。可分以下两类：6.2.1客观保真度准则

最常用的客观保真度准则是原图像和解码图像之间的均方根误差和均方根信噪比两种。6.2.2主观保真度准则

很多解压图最终是供人观看的，一种常用的方法是对一组（不少于20人）观察者显示图像，并将他们对该图像的评分取平均，用来评价一幅图像的主观质量。原图100:1400:1600:1图像的熵为图像的平均码长为冗余度为编码效率为

6.3统计编码方法6.3.1图像冗余度和编码效率根据Shannon无干扰信息保持编码定理，若对原始图像数据的信息进行信源的无失真图像编码，压缩后平均码率存在一个下限，这个下限是信源信息熵H。理论上最佳信息保持编码的平均码长可以无限接近信源信息熵H。但总是大于或等于图像的信息量H（熵）。6.3.2霍夫曼编码Huffman编码是1952年由Huffman提出的一种编码方法。这种编码方法根据源数据符号发生的概率进行编码。在源数据中出现概率越大的符号，编码以后相应的码长越短；出现概率越小的符号，其码长越长，从而达到用尽可能少的码符表示源数据。它在无损变长编码方法中是最佳的。下面通过实例来说明此方法。设输入数据为，其频率分布分别为P(x1)=0.4，P(x2)=0.3，P(x3)=0.1，P(x4)=0.1，P(x5)=0.06，P(x6)=0.04。求其最佳霍夫曼编码编码方法是：①把输入元素按概率从小到大排列起来，然后把概率最小的两个元素概率加起来;②把它同其余元素概率由小到大排序，然后把两个最小概率加起来，再重新排队;③重复②，直到最后只剩下一个和为1的概率为止。④在上述工作完毕之后，从最后两个概率开始逐步向前进行编码。对于概率大的消息赋予0，小的赋予1。一般用二叉树方法实现Huffman编码较为便利。问题：计算该信源的熵、编码后的平均码长，编码效率及冗余度，并思考对于同一图像采用Huffman编码，编码是否唯一？元素xi概率P(xi)编码wix1x2x3x4x5x60.40.30.10.10.06100011010001010元素xi概率P(xi)编码wix1x2x3x4x5x60.40.30.10.10.060.04100011010001010010110.61x100

x20.3011

x30.20100

x401011

x601010

x50.10.040.060.10.10.30.40000011111Huffman编码树及编码过程：6.3.5行程编码（RunLengthEncoding）

基本原理：通过改变图像的描述方式，来实现压缩。将一行中颜色值相同的相邻像素用一个计数值和该颜色值来代替。

举例说明：aaaa

bbb

cc

d

eeeee

fffffff(共22*8=176bits)

4a3b2c1d5e7f(共12*8=96bits)

若计数值用3bit来表示

(共6*3+6*8=66bits)黑白二值图像：

默认起始为白，码流为：4，5，7，5，9，3，3默认起始为黑，码流为：0，4，5，7，5，9，3，3一维行程编码和二维行程编码：图像的一般特点：像素之间距离越近，其相关性越强。要提高行程编码的效率，就希望能够通过一定的扫描顺序，使相邻像素值相等的情况尽可能多。一维行程编码只考虑了消除行内像素之间的相关性，却没有考虑到某种方向间的相关性。二维行程编码可先将图像分块，再对各子块的像素按一定的扫描路线进行扫描。例如：混合编码混合编码实现的可能性及有效性：回顾一下讲过的几个内容的特点1.行程编码：擅长于重复数字的压缩。2.Huffman编码：擅长于像素个数的出现频度不同的编码。例：aaaa

bbb

cc

d

eeeee

fffffff（共22*8=176bits）

432157

行程编码：4a3b2c1d5e7f（共6*(8+3)=66bits）17666Huffman编码：f=01e=11a=10b=001c=0001d=00001010101010001001001000100010000111111111101010101010101（共7*2+5*2+4*2+3*3+2*4+1*4=53bits）17653Huffman与行程编码混合：41030012000110000511701

（共3+2+3+3+3+4+3+4+3+2+3+2=35bits）17635以上三种编码的数据量分别为原始数据量的37.5%，30.1%和19.9%。

6.3.3费诺-仙侬（Fannon-Shannon）编码二分法费诺-仙侬编码的步骤如下：

（1）首先统计出每个符号出现的概率；

（2）从上（左）到下（右）对上述概率从大到小排序；

（3）从这个概率集合中的某个位置将其分为两个子集合，并尽量使两个子集合的概率和近似相等，给前面一个子集合赋值为0，后面一个子集合赋值为1；

（4）重复步骤（3），直到各个子集合中只有一个元素为止；

（5）将每个元素所属的子集合的值依次串起来，即可得到各个元素的费诺-仙侬编码。

6.3.4算术编码理论上，用霍夫曼方法对源数据流进行编码可达最佳编码效率，但由于计算机中存储、处理数据的最小单位是“位”，因此实际编码效果不会达到理论上的压缩比。例如，源数据流由X和Y两个符号构成，它们出现的概率分别为2/3和1/3，理论上，根据符号X的熵确定的最优码长为：H(X)=-log2(2/3)=0.585(bit)若要达到最佳编码效果，相应于X的码长为0.585位。但由于计算机中不可能有非整数位出现，那么受硬件的限制，编码只能按“位”进行。用霍夫曼方法对这两个符号进行编码，得到X和Y的代码分别为0和1，显然出现概率大的符号不能给予较短的代码。算术编码没有沿用编码技术中用一个特定的代码代替一个输入符号的一般做法，而是把要压缩处理的整段数据映射到一段实数半开区间[0，1）内的某一区段，构造出小于1且大于或等于0的数值，这个数值是输入数据流的惟一可译代码。算术编码有两种模式，均可用硬件实现。一种是基于信源概率统计特性的固定编码模式，另一种是针对未知信源概率模型的自适应模式。算术编码的实现方法要比霍夫曼编码复杂一些，但有关研究表明，算术编码一般要优于Huffman编码。例如，在JPEG扩展系统中，就用算术编码取代了霍夫曼编码；在MPEG-4标准中，对形状编码采用的也是算术编码。自适应模式中各个符号的概率初始值都相同，它们依据出现的符号而相应地改变。只要编码器和解码器都使用相同的初始值和相同的改变值的方法，那么它们的概率模型将保持一致。下面结合一个实例来阐述固定模式的算术编码的具体方法。

设有一个五符号信源的待编码数据序列“dacab”，信源中各符号出现的概率依次为：P(a)=0.4，P(b)=0.2，P(c)=0.2，P(d)=0.2。

首先，数据序列中的各数据符号在区间［0,1）内的赋值范围设定为：a=［0,0.4）,b=［0.4,0.6）,c=［0.6,0.8）,d=［0.8,1.0）StartN=StartB+LeftC×L

EndN=StartB+RightC×L

第一个被压缩的符号为“d”，其初始赋值区间为［0.8,1.0）；第二个被压缩的符号为“a”，由于前面的符号“d

”的取值区间被限制在［0.8,1.0）范围内，所以“a

”的取值范围应该在前一符号区间［0.8,1.0）的［0,0.4）范围内。为便于讨论，再给出一组关系式：StartN=0.8+0×(1.0-0.8)=0.8EndN=0.8+0.4×(1.0-0.8)=0.88即“a”的实际编码区间在［0.8,0.88)之间。式中，StartN、EndN分别表示新子区间的起始位置和结束位置，StartB表示前一子区间的起始位置，L为前一子区间的长度，LeftC、RightC分别表示当前编码符号的初始区间的左端和右端。根据上式可知：第三个被压缩的符号为“c”，其编码取值范围应在［0.8,0.88）区间的［0.6,0.8）的子区间内，据上式可知：StartN=0.8+0.6×(0.88-0.8)=0.848EndN=0.8+0.8×(0.88-0.8)=0.864第四个被压缩的符号为“a”，同理，根据上式得［0.848，0.8544）第五个被压缩的符号为“b”，同理，根据上式得［0.84856，0.85144）

至此,数据序列“dacab”已被描述为一个实数区间［0.85056,0.85184），或者说在此区间内的任一实数值都惟一对应该数据序列。这样，就可以用一个实数表示这一数据序列。我们把区间［0.85056,0.85184）用二进制形式表示为［0.110110011011,0.110110100001）。从这个区间可以看出，0.1101101位于这个区间内并且其编码最短，故把其作为数据序列“dacab”的编码输出。考虑到算术编码中任一数据序列的编码都含有“0.”，所以在编码时，可以不考虑“0.”，于是把1101101作为本例中的数据序列的算术编码。由此可见，数据序列“dacab”用7比特的二进制代码就可以表示，平均码长为1.4比特／字符。

解码是编码的逆过程，根据编码时的概率分配表和压缩后数据代码所在的范围，确定代码所对应的每一个数据符号。在完成对第一个符号的解码后，设法去掉第一个符号对区间的影响，再用相同的方法找到下一个符号。重复此过程，直到完成解码。6.6图像压缩的标准图像压缩的国际标准主要是由国际标准化组织（ISO）和国际电报电话咨询委员会（CCITT）制订的。6.6.1静态图像压缩标准JPEG(JointPictureExpertGroup)格式即联合图像专家组,是由ISO和CCITT为静态图像所建立的第一个国际数字图像压缩标准，1991年开始使用。在相同图像质量条件下，JPEG文件拥有比其他图像文件格式更高的压缩比。JPEG目前被广泛应用于多媒体和网络程序中，是现今万维网中使用最广泛的两种图像文件格式之一。(JPEG和GIF成为HTML语法选用的图像格式。)JPEG定义了三种编码系统：DCT（离散余弦变换）有损编码系