数字图像处理(冈萨雷斯)-8-无损压缩

第8章图像压缩8.1基本概念8.2图像压缩模型8.3信息论基础8.4无损压缩8.5有损压缩8.6图像压缩标准8.7视频压缩标准图像压缩编码的分类图像压缩编码有损压缩无损压缩哈夫曼编码算术编码LZW编码位平面编码行程编码无损预测编码有损预测编码变换编码K.L变换Haar变换Walsh.Hadamard变换离散余弦变换离散傅立叶变换斜变换小波变换消除编码冗余消除象素间冗余8.4无损压缩变长编码霍夫曼(Huffman)编码其它变长编码算术编码LZW编码位平面编码无损预测编码无误差压缩（无损压缩）的必要性在医疗或商业文件的归档，有损压缩因为法律原因而被禁止；卫星成像的收集，考虑数据使用和所花费用，不希望有任何数据损失；X光拍片，信息的丢失会导致诊断的正确性；无损压缩的压缩率一般为2～10①减少像素间冗余:建立一种可替代的图像表达方式②减少编码冗余:对这种表达方式进行编码无误差压缩技术8.4.1变长编码无误差图像压缩的最简单方法就是减少仅有的编码冗余。编码冗余通常存在于表示图像灰度级的自然二进制编码过程中。它可以对灰度级进行编码，使表示一个像素的码字的平均比特数最小来消除编码冗余。这样做需要变长编码结构，通常将最短的码字赋予出现概率最大的灰度级。10(8.1.4)LavgkrkkLlrpr8.4无损压缩霍夫曼编码将需要考虑的符号概率排序，并将最低概率的符号联结为一个单一符号对每个化简后的信源进行编码，从最小的信源开始，一直编码到原始的信源8.4.1变长编码（一）霍夫曼编码信源化简步骤：Am设信源有个符号(消息)，1212mmaaaAppp1.把信源中的消息按概率从大到小顺序排列;2.把最后两个出现概率最小的消息合并成一个消息,并同时再按信源符号（消息）出现的概率从大到小排列；3.重复上述2步骤,直到信源最后为为止；4.将被合并的消息分别赋予1和0，并对最后的两个消息也相应的赋予1和0；通过上述步骤就可构成最优变长码(HuffmanCodes)。1212oooooaaApp（一）霍夫曼编码信源化简大小大小大小大小8.4.1变长编码1a2a3a5a4a6a（二）霍夫曼化简后的信源编码010101010110001101000101001011其信源熵为:编码的平均长度：(0.4)(1)(0.3)(2)(0.1)3(0.1)(4)(0.06)(5)(0.04)(5)2.2/avgLbit（）符号编码的效率：()2.140.9732.2avgHzL61log2.14/jjjHzPaPabit符号8.4.1变长编码8.4.1变长编码（三）霍夫曼解码解码通过查询表的方式完成。例：编码串0101001111003a1a2a2a6a对编码串010100111100解码，其解码唯一：a3a1a2a2a6huffman码的优点：①是一种最优变长编码（平均码长最短；最接近于熵）；②一种快码，因为各个信源符号都被解成一组固定次序的码符号；③一种即时码，因为1串码符号中的每个码字都可以不考虑其后的符号而解出；④是一种可唯一解开的码；8.4.1变长编码其它接近最佳的变长编码：为什么需要？当对大量符号进行编码，构造霍夫曼编码比较复杂对J个信源符号，需要进行J-2次信源化简和J-2次编码分配对256个灰度级图像，需要256-2=254次信源化简和254次编码分配考虑牺牲编码效率以减少编码构造的复杂性表8.5给出了几种简化的编码方法：截断霍夫曼编码，B编码、二元平移及霍夫曼移位。几种变长编码截取霍夫曼编码霍夫曼编码二进制编码B2编码二值移位编码霍夫曼移位编码8.4.1变长编码8.4.1变长编码①截断huffman编码一种简单改进，它只对具有最大概率的个符号进行霍夫曼编码，而对其它所有码用：前缀码+定长码（二进制编码）来表示。把M个符号之后的所有符号合成一个特殊符号，其概率为各符号概率之和把该特殊符号对应的霍夫曼码作为前缀码；()MMJ例如：，则符号的概率之和再查0.2概率对应的霍夫曼码（10）作为前缀码12M1321aa0.030.030.010.28.4.1变长编码②B编码当信源符号的概率服从如下的幕规律时，B码逼近最优。0()(8.4.1),JjjPacjcj其中：——正常数每个码字由两部分组成：延续比特+信息比特（二进制数）分开各码→用0，1交替表示不同的信息符号延续比特：•用字母C表示；•随每个码字变化交替取“0”或“1”；•它的变化表示一个新的码字的开始；信息比特：•表示不同的信息符号；•B2码代表每一延续比特位后有2个信息位；例如：的B2编码为：1127aaa1127aaa0010101010000101127aaa101110001100110或者注：有下划线的为延续比特；8.4.1变长编码B编码信息符号B1码B2码1a5a8a0C10CC001CCC00C0011CC0000CC18512aaaBB信息串的编码为：码：001010110100or100000011110码：000100111000000or100000011100100B码是单义码，但是是续长码，译码时要向前看一位延续比特；B码也是给出现概率最大的消息分配最短的码字，然后依次排列下来；B码的编、译码简单，对误码的抗干扰能力也较强；01C代表延续比特，取“”或“”8.4.1变长编码③移位编码移位编码步骤：①排列信源符号，使概率单调递减；②将符号总数分成大小相同的符号块，一般第一个块叫基准块；③对所有块中的各元素采用同样方法编码；④除基准块外，对每个块加上移、下移符号加以区别。二进制移位码又叫Sn码。移位符号的二进制位数Shift优点：移位码对于具有单调递减概率的消息非常有效；8.4.1变长编码平移编码示例：例如：表8.5中的二进制平移码的获得：21个信源符号依出现的概率进行单调递减排序；分成3块，每块7个符号；基准块的7个单独符号用自然二进制编码需3位，所以用S3编码；121~aa17~aa1C2C3C4C5C6C7C8C00000101001110010111011111787~~CCCaa分配给符号，作为移位符号表8.5中的霍夫曼平移码可以类似获得。只是基准块的7个单独符号用huffman编码；所有概率相加，得0.39，移位符号是具有最大概率(0.39)的符号，且被分配一个最短的霍夫曼码字00表示。821~aa17~aa8.4.1变长编码算术编码算术编码生成的是非块码；在信源符号和码字之间不存在一一对应的关系；算术编码是给整个符号序列分配一个单一的算术码字，这个码字本身定义了一个介于0和1之间的实数间隔；当消息中的符号数目增加时，用于描述消息的间隔变的更小，而表示间隔所需要的信息单元的数目就变得更多了。消息的每个符号根据符号出现的概率减小间隔的大小，这种技术不象霍夫曼方法那样要求每次对一个符号进行编码，所以理论上达到了无噪声编码准则确定的界限。8.4.1变长编码算术编码0.20.40.812334aaaaa0.040.080.0.20104050.0.20208050.0560.0720.0.080560.040.04250.0.080720.040.04450.06240.06880.0.07062420.0560.056250.0.07068820.0560.056458.4.1变长编码算术编码0.20.40.80.040.080.0.20104050.0.20208050.0560.0720.0.080560.040.04250.0.080720.040.044512334aaaaa一个五个符号的序列a1,a2,a3,a3,a4来自一个四符号信源。经过算术编码后，区间被确定为[0.06752,0.0688),这个区间的任何数字（比如0.068)都可以用来表示这个消息。()0.58Hz信源熵：（个十进制数字/符号）123340.0683068,30.65aaaaaLavg若用（个十进制数字、、）表示消息则平均码长为=个（十进制数字/符号）编码的效率：()0.580.9670.6avgHzL8.4.2LZW编码在编码处理的开始阶段，先构造一个对信源符号进行编码的编码本（字典）。对于8位单色图像，字典中前256个字被分配给灰度值0～255。当编码器顺序地分析图像像素的时候，字典中没有包括的灰度级序列由算法决定其出现的位置。8.4无损压缩LZW编码：消除像素间冗余的无误差编码方法LZW编码的原理：对信源符号的可变长度序列分配固定长度码字，不需要了解有关被编码符号的出现概率的知识。是由Lemple和Ziv最早提出，然后由Welch充实的有专利保护的LZW算法.Lempel-Ziv-Welch(LZW)编码使用LZW的文件格式包括GIF，TIFF和PDF等。字典位置index条目01…255256…51101…255——…——LZW编码基本思想是这样的:以8位（256个灰度级）图像为例.1.准备一个数据字典(可以看做一个数组).数组的前256项初始化为0,1,2,...,255,后面的项为空白.为方便起见,我们管字典中的每一项叫“条目”.2.开始对图像文件编码,图像文件从左向右、从上到下扫描,把扫描得到的灰度级数据与字典中的条目进行比较.如果相同,就把这个条目的index(在数组中的位置)作为码字输出.如果在字典中找不到与之匹配的条目,则在字典中创建一个新的条目(从第256项开始).一个512字的字典一个4×4、8位图像3546353946784639679078126353334126示例原始码流354667354678903335467834开始编码:①因为第一个数字是35,我们必然可以从字典中找到与之匹配的条目(也就是第35个),但我们不急着用第35个条目与之匹配,先看看第二个数字是46,希望在字典中能找到一个更长的模式“3546”这样的条目,与之匹配,但不幸的是我们没有找到,所以只对第一个数字35编码,结果输出35;同时把“3546”加入字典的第256项,希望以后能碰到它.②同理,对46编码,输出46,同时把“4667”加入字典的第257项.③同理,对67编码,输出67,同时把“6735”加入字典的第258项.④这时注意了:对35编码,是不是现在还输出35呢?当然不是,我们发现35后面跟着46,扫描字典,可以发现第256个模式与之匹配,输出256.同时,将模式“354678“加入到字典的第259项.⑤同理,接下来输出78,90,33,259,34.所以输出的码流为35466725678903325934.对上面的过程归纳一下:在编码的过程中生成字典;一边从字典中选择长度尽量长的模式与原始码流匹配.8.4.3位平面编码二值图像位平面；灰度编码位平面；8.4无损压缩消除像素间冗余①位平面分解的两种方法：位平面编码过程可以分成两步：①位平面分解；②二值图像压缩将一幅图像分解为一系列二值图像并通过二值图像压缩方法对每幅二值图像进行压缩1.二值图像位平面一幅m比特的灰度图像具有的灰度级表示如下121012102222mmmmaaaa零级位平面是通过收集每个像素的a0位生成，第(m-1)级位平面包含am-1位缺点：图像在灰度级上稍有变化就会对位平面的复杂性产生显著影响，如亮度127(01111111)和亮度128(10000000)的转换2.灰度编码位平面图像的灰度编码是先用一个m比特的格雷码表示图像1221011102mmmmiiiggggggagaaim格雷码：避免二值图像位平面的缺点，连续码字只在1位位置上不同,如亮度127(01000000)和亮度128(11000000)的转换位平面分解示例——图8.14()102410248a