第7章-图像编码-2

1、7.4 行行 程程 编编 码码7.4.1 行程编码基本方法行程编码基本方法 行程编码又称行程长度编码（Run Length Encoding， RLE）， 是一种熵编码，其编码原理相当简单，即将具有相同值的连续串用其串长和一个代表值来代替， 该连续串就称为行程，串长称为行程长度。例如，有一字符串“aabbbcddddd”， 则经行程长度编码后， 该字符串可以只用“2a3b1c5d”来表示。 行程编码分为定长和不定长编码两种。定长编码是指编码的行程长度所用的二进制位数固定，而变长行程编码是指对不同范围的行程长度使用不同位数的二进制位数进行编码。使用变长行程编码需要增加标志位来表明所使用的二进制位

2、数。 行程编码比较适合于二值图像的编码，一般用于量化后出现大量零系数连续的场合，用行程来表示连零码。如果图像是由很多块颜色或灰度相同的大面积区域组成的，那么采用行程编码可以达到很高的压缩比。如果图像中的数据非常分散，则行程编码不但不能压缩数据，反而会增加图像文件的大小。为了达到较好的压缩效果，一般不单独采用行程编码， 而是和其他编码方法结合使用。例如， 在JPEG中， 就综合使用了行程编码、DCT、量化编码以及哈夫曼编码， 先对图像作分块处理， 再对这些分块图像进行离散余弦变换（DCT）， 对变换后的频域数据进行量化并作Z字形扫描，接着对扫描结果作行程编码， 对行程编码后的结果再作哈夫曼编码。

3、 1.一维行程编码一维行程编码编码思想：编码思想： 将一行中颜色值相同的相邻象素（行将一行中颜色值相同的相邻象素（行程）用一个计数值（行程的长度）和该颜程）用一个计数值（行程的长度）和该颜色值（行程的灰度）来代替，从而去除像色值（行程的灰度）来代替，从而去除像素冗余。素冗余。 设沿某一扫描行的像素为设沿某一扫描行的像素为x1,x2,xN对应的对应的灰度值可能为灰度值可能为g1,g2,g3,g4. 把像素映射成序列对：把像素映射成序列对： (g1,l l1)，(g2, l l2)，(g3, l l3)，(g4, l l4) 直接对直接对(gi, li)编码，可大大压缩比特率编码，可大大压缩比特率

4、0 0 5 5 1 10 0 1 15 5 2 20 0 2 25 51 10 09 98 87 76 65 54 43 32 21 1l l1 1l l2 2l l3 3l l4 4g g1 1g g2 2g g3 3g g4 4像像素素li:表示第表示第i次运行的行程，即连续取值为次运行的行程，即连续取值为gi灰度值的像素灰度值的像素的个数的个数 8级灰度，级灰度，24个像素个像素对对xi编码，总的比特数，至少编码，总的比特数，至少24 3=72bit如对如对(gi,li)编码，灰度值用编码，灰度值用3bit，行程长度用，行程长度用4bit每对参数用每对参数用7bit，总比特数只需，总比特

5、数只需28bit就够就够i gi li13 62510342486 例：映射对：例：映射对：行程编码（RLE）n对于有大面积色块的图像，压缩效果很好n对于纷杂的图像，压缩效果不好，最坏情况下（图像中每两个相邻点的颜色都不同 ），会使数据量加倍，所以现在单纯采用行程编码的压缩算法用得并不多，PCX文件算是其中之一二维行程编码n二维行程编码要解决的核心问题是：将二维排列的像素，采用某种方式转化成一维排列的方式。之后按照一维行程编码方式进行编码n两种典型的二维行程编码的排列方式例1：n数据量：64*8=512(bit)13013013012913413312913013013013012913413

6、3130130130130130129132132130130129130130129130130129129127128127129131 129131 130127128127128127128132132125126129129127129133132127125128128126130131131f二维行程编码如果按照方式(a)扫描的顺序排列的话，数据分布为：130，130，130，130，130，130，130，130，130；129，129，129，129，130，130，129；127，128，127，129，131，130，132，134，134；133，133，132，130

7、，129，128，127，128，127，128，127，125，126，129，129；127，129，133，132，131，129，130，130；129，130，130，130，129，130，132，132；131，131，130，126，128，128，127，127行程编码为:数据量为:43*（3+8）=473(bit) (94.22%)（7，130），（），（2，130），（），（4，129），（），（2，130），（），（1，129）；（）；（1，127），），（1，128），（），（1，127），（），（1，129），（），（1，131），（），（1，130），（），（1，

8、132），），（2，134），（），（2，133），（），（1，132），（），（1，130），（），（1，129），（），（1，128），），（1，127），（），（1，128），（），（1，127），（），（1，128），（），（1，127），（），（1，125），），（1，126），（），（2，129），（），（1，127），（），（1，129），（），（1，133），（），（1，132），），（1，131），（），（1，129），（），（2，130），（），（1，129），（），（3，130），（），（1，129），），（1，130），（），（2，132），（），（2，131），（），

9、（1，130），（），（1，126），（），（2，128），），（2，127）1) 原始数据所需存储空间原始数据所需存储空间: 503B+23B+13B+93B+723B=402B2) RLE编码后得到的代码为：编码后得到的代码为： 50（200,30,100）2（255,255,255）1（0,5,5）9（0,0,0）72（200,30,100）编码后需存储空间（行程长度值用编码后需存储空间（行程长度值用2B表示）表示）2B+3B+2B+3B+2B+3B+2B+3B+ 2B+3B =25B3) 压缩比率压缩比率：402:25=16.08 : 1例2：7.5 LZW编码编码 7.5.1 LZW

10、编码方法编码方法 LZW（Lempel-Ziv & Welch）编码又称字串表编码， 属于一种无损编码， 是Welch将Lempel和Ziv所提出的无损压缩技术改进后的压缩方法。LZW编码与行程编码类似， 也是对字符串进行编码从而实现压缩，但它在编码的同时还生成了特定字符串以及与之对应的索引字符串表。 LZW算法取得了专利，专利权的所有者是美国的一个大型计算机公司Unisys(优利系统公司)，除了商业软件生产公司之外，可以免费使用LZW算法。 字典式（LZ）编码LZLZ是其发明者是其发明者J.ZivJ.Ziv和和A.LempelA.Lempel两个犹两个犹太人姓氏的缩写。此二人于太人姓

11、氏的缩写。此二人于19771977年发表题年发表题为为顺序数据压缩的一个通用算法顺序数据压缩的一个通用算法的论的论文，论文中描述的算法被后人称为文，论文中描述的算法被后人称为LZ77LZ77算算法。法。19781978年，二人又发表了该论文的续篇，年，二人又发表了该论文的续篇，描述了后来被命名为描述了后来被命名为LZ78LZ78的压缩算法。的压缩算法。LZW编码19841984年，年，Terry WelchTerry Welch发表论文描述了他在发表论文描述了他在SperrySperry研究中心的研究成果，也就是后来非常研究中心的研究成果，也就是后来非常有名的有名的LZWLZW算法。算法。它实

12、质上是它实质上是LZ78LZ78算法的一个变种，但被认为算法的一个变种，但被认为是一个独立的编码算法。是一个独立的编码算法。LZWLZW继承了继承了LZ77LZ77和和LZ78LZ78压缩效果好、速度快的优点，而且在算法描述压缩效果好、速度快的优点，而且在算法描述上更容易被人们接受，实现也相对简单。上更容易被人们接受，实现也相对简单。字典式（LZ）编码其实其实LZLZ系列的算法并不新鲜，其中既没有高系列的算法并不新鲜，其中既没有高深的理论背景，也没有复杂的数学公式。它们深的理论背景，也没有复杂的数学公式。它们只是简单的延续了千百年来人们对字典的追崇只是简单的延续了千百年来人们对字典的追崇和喜好

13、，并用一种极为巧妙的方式将字典技术和喜好，并用一种极为巧妙的方式将字典技术运用于通用数据压缩领域。运用于通用数据压缩领域。简单的说如果你习惯用字典中的页码和行号简单的说如果你习惯用字典中的页码和行号代替文章中的每个单词的时候，那实际上你已代替文章中的每个单词的时候，那实际上你已经掌握了经掌握了LZLZ系列算法的真谛，因此这类编码算系列算法的真谛，因此这类编码算法被统称为法被统称为Dictionary codersDictionary coders。LZW编码而在其后发展出来的各式各样的字典编码算而在其后发展出来的各式各样的字典编码算法，基本上都是这三种编码算法的分支或变体。法，基本上都是这三种

14、编码算法的分支或变体。也就是说也就是说LZ77LZ77、LZ78LZ78和和LZWLZW是字典编码中最基础是字典编码中最基础的的3 3种编码算法种编码算法LZ编码与传统统计编码比较在压缩效果上字典式编码大大超过了在压缩效果上字典式编码大大超过了HuffmanHuffman编码；编码；而且在实现上，压缩和解压缩的速度也异而且在实现上，压缩和解压缩的速度也异常惊人。常惊人。于是于是LZLZ系列算法的优越性很快就在数据压系列算法的优越性很快就在数据压缩领域里体现出来，使用缩领域里体现出来，使用LZLZ系列算法的工具系列算法的工具软件数量呈爆炸式增长软件数量呈爆炸式增长LZ78LZ78和和LZWLZW

15、一时间几乎统治了一时间几乎统治了UNIXUNIX和和DOSDOS两大两大平台。平台。然而随着时间流逝，事情变得耐人寻味。目然而随着时间流逝，事情变得耐人寻味。目前为止占据个人用户计算机的主流压缩工具几前为止占据个人用户计算机的主流压缩工具几乎都采用乎都采用LZ77LZ77变种算法；变种算法；更为优秀的更为优秀的LZ78LZ78和和LZWLZW没有成为最主流的算法？没有成为最主流的算法？LZ77LZ77与它们有什么不同？与它们有什么不同？LZ字典编码专利限制LZ77LZ77完全没有专利限制；完全没有专利限制；LZ78LZ78在美国稍稍涉及到一些专利禁止区；在美国稍稍涉及到一些专利禁止区；而而LZ

16、WLZW专利权最终归属于专利权最终归属于UnisysUnisys公司；公司；ZIP格式的诞生DOSDOS环境下由于硬件资源的有限，标准配置环境下由于硬件资源的有限，标准配置360kB360kB的的5.255.25寸软盘；网络条件十分有限，寸软盘；网络条件十分有限，14.4kbit/s14.4kbit/s19851985年年SEASEA公司开发的公司开发的MS-DOSMS-DOS环境下第一个应环境下第一个应用用LZWLZW算法的算法的ARCARC（商业软件）（商业软件）Phillip W.KatzPhillip W.Katz（菲利普（菲利普卡兹）卡兹）ZIP格式的诞生DEFLATEDEFLATE

17、：完美地结合：完美地结合LZ77LZ77和和HuffmanHuffman编码可编码可将多个文件压缩到一个文件中，无论压缩比、将多个文件压缩到一个文件中，无论压缩比、压缩速度都全面超过了商业软件压缩速度都全面超过了商业软件ARCARC开放开放ZIPZIP格式，任何人都可以自由使用格式，任何人都可以自由使用ZIPZIP编编码算法而不需要缴纳任何专利费用。这个决定码算法而不需要缴纳任何专利费用。这个决定最终改变了压缩的世界，使得通用数据无损压最终改变了压缩的世界，使得通用数据无损压缩领域再无法出现垄断的商业巨鳄缩领域再无法出现垄断的商业巨鳄LZW性能分析对于可预测性不大的数据具有较好的处理效果对于可

18、预测性不大的数据具有较好的处理效果对于简单图像、平滑且噪声小的信号源具有较对于简单图像、平滑且噪声小的信号源具有较高的压缩比，且压缩解压缩速度快；高的压缩比，且压缩解压缩速度快；对于数据流中连续重复出现的字节和字串，具对于数据流中连续重复出现的字节和字串，具有很高的压缩比，除用于图像数据的压缩处理外，有很高的压缩比，除用于图像数据的压缩处理外，还被用于文本程序等领域的数据压缩还被用于文本程序等领域的数据压缩 LZW编码的基本思想是：在编码过程中，将所遇到的字符串建立一个字符串表，表中的每个字符串都对应一个索引，编码时用该字符串在字串表中的索引来代替原始的数据串。例如， 一幅8位的灰度图像，我们

19、可以采用12位来表示每个字符串的索引，前256个索引用于对应可能出现的256种灰度，由此可建立一个初始的字符串表，而剩余的3840个索引就可分配给在压缩过程中出现的新字符串，这样就生成了一个完整的字符串表， 压缩数据就可以只保存它在字符串表中的索引，从而达到压缩数据的目的。字符串表是在压缩过程中动态生成的，不必将它保存在压缩文件里，因为解压缩时字符串表可以由压缩文件中的信息重新生成。 LZW编码算法的具体执行步骤如下： 步骤1：开始时的词典包含所有可能的根(Root)，而当前前缀P是空的； 步骤2：当前字符(C) ：=字符流中的下一个字符； 步骤3：判断缀-符串P+C是否在词典中 (1) 如果

20、“是”：P：= P+C ，即用C扩展P)； (2) 如果“否” 把代表当前前缀P的码字输出到码字流; 把缀-符串P+C添加到词典; 令P：= C ，即现在的P仅包含一个字符C; 步骤4：判断码字流中是否还有码字要译 (1) 如果“是”，就返回到步骤2； (2) 如果“否” 把代表当前前缀P的码字输出到码字流; 结束。 GIF（Graphics Interchange Format）最初是由美国CompuServe 于1987年开发的一种压缩位图格式。它可支持多达 256 种的颜色，具有极佳的压缩效率，已成为Internet 上一种流行的文件格式。GIF图像文件采用的是一种改良的LZW压缩算法，

21、 通常称为GIF-LZW压缩算法。GIF图像文件以块（又称为区域结构）的方式来存储图像相关的信息，具体的文件格式可参考图像文件格式的相关书籍。下面简要介绍GIF-LZW的编码方法。 设S1、S2为两个存放字符串的临时变量，LZW_CLEAR和LZW_EOI分别为字符表初始化标志和编码结束标志，GIF-LZW的编码步骤如下： （1）根据图像中使用的颜色数初始化一个字串表，字串表中的每个颜色对应一个索引。在初始字串表的末尾再添加两个符号（LZW_CLEAR和LZW_EOI）的索引。设置字符串变量S1、 S2并初始化为空。 （2） 接着输出LZW_CLEAR在字串表中的索引。 （3）从图像数据流中第

22、一个字符（假设数据以字符串表示）开始， 每次读取一个字符，将其赋给字符串变量S2。 （4）判断“S1+S2”是否已存在于字串表中。如果字串表中存在“S1+S2”，则S1=S1+S2；否则，输出S1在字串表中的索引， 并在字串表末尾为“S1+S2”添加索引，同时，S1=S2。 （5）重复第3和第4步， 直到所有字符读完为止。 （6）输出S1中的字符串在字串表中的索引， 然后输出结束标志LZW_EOI的索引，编码完毕。 GIF-LZW的解码过程比较复杂，它和编码过程正好相反， 即将编码后的码字转换成对应的字符串， 重新生成字串表，然后依次输出对应的字符串即可。GIF-LZW的解码流程如图7-2所示

23、， 表中的Code和OldCode是两个存放索引的临时变量。 LZW编码算法流程初始化字典初始化字典前缀前缀S = 空串空串C = 从输入流中读一个字符从输入流中读一个字符把新串把新串S+C加到字典中加到字典中S = C输出结束标记输出结束标记是结尾标志吗？是结尾标志吗？是是S = S+CS+C在字典中吗？在字典中吗？是是图7-2 GIF-LZW解码流程 开始CodeLZW_EOI依次读取每个编码并赋予Code初始化字符串表读取下一个编码给Code将OldCode对应的字符串及该串的第一个字符组合成新串; 输出新串,并把新串添加到字串表中OldCode=CodeYNYYNNNY字串表中是否存在

24、CodeCodeLZW_CLEAR结束解码CodeLZW_CLEAR输出Code对应的字符串OldCodeCode输出Code对应的字符串; 将OldCode对应的字符串与Code对应的字符串的第一个字符组合成新串, 添加到字串表中OldCodeCodenLZW译码算法的具体执行步骤如下： n n步骤1：在开始译码时词典包含所有可能的前缀根(Root)； n步骤2：cW：=码字流中的第一个码字； n步骤3：输出当前缀-符串string.cW到码字流； n步骤4：先前码字pW：= 当前码字cW； n步骤5：当前码字cW：= 码字流中的下一个码字； n步骤6：判断先前缀-符串string.pW是否

25、在词典中 (1) 如果“是”： 把先前缀-符串string.pW输出到字符流； 当前前缀P：=先前缀-符串string.pW； 当前字符C：=当前前缀-符串string.cW的第一个字符； 把缀-符串P+C添加到词典； (2) 如果“否”： 当前前缀P：=先前缀-符串string.pW； 当前字符C：=当前缀-符串string.cW的第一个字符； 输出缀-符串P+C到字符流，然后把它添加到词典中。 n步骤7：判断码字流中是否还有码字要译 (1) 如果“是”，就返回到步骤4； (2) 如果“否”，结束。 7.5.2 LZW编码实例编码实例 设有一来源于4色（以a、b、c、d表示）图像的数据流aa

26、bcabbbbd，现对其进行LZW编码。编码过程如下： 编码前，首先需要初始化一个字符串表。由于图像中只有四种颜色，因而我们可以只用4比特表示字符串表中每个字符串的索引，表中的前4项代表4种颜色， 后两项分别表示初始化和图像结束标志，建立的初始化字符串表如表7-5所示。接着把S1和S2初始化为空（即NULL），输出LZW_CLEAR的在字符串表中的索引值4H， 接下来是对图像数据的编码。 表表7-5 初始化字符串表初始化字符串表 字符串 索引 A 0 H b1 H c2 H d3 H LZW_CLEAR 4 H LZW_EOI 5 H 读取图像数据流的第一个字符“a”，赋给S2， 因S1+S2

27、=“a”已存在字串表中，所以S1=S1+S2=“a”。 接着读入下一个字符“a”赋给S2， 因S1+S2=“aa”不存在于字串表中， 所以输出S1=“a”的索引0H，同时在字符串表末尾添加新字符串“aa”的索引6H， 并使S1=S2=“a”。 依次读取数据流中的每个字符，如果S1+S2没有出现在字符串表中，则输出S1中的字符串的索引，并在字符串表末尾为新字符串S1+S2添加索引，并使S1=S2； 否则，不输出任何结果，只是使S1=S1+S2。所有字符处理完毕后，输出S1中的字符串的索引，最后输出结束标志LZW_EOI的索引。至此，编码完毕，完整的编码过程如表7-6所示， 最后的编码结果为“40

28、01271B35”（以十六进制表示）。 表表7-6 GIF-LZW编码过程编码过程 下面对上述编码结果“4001271B35”进行解码。按图7-2的解码 流 程 ， 首 先 读 取 第 一 个 编 码 C o d e = 4 H ， 由 于 它 为LZW_CLEAR，因此需初始化字符串表， 结果如表7-5所示（在实际应用中，可根据文件头中给定的信息建立初始字符串表）。 读入下一个编码Code=0H，由于它不等于LZW_CLEAR， 因此 输 出 字 串 表 中 0 H 对 应 的 字 符 串 “ a ” ， 同 时 使OldCode=Code=0H。 读入下一个编码Code=0H，由于字串表中

29、存在该索引，因此输出0H所对应的字符串“a”，然后将OldCode=0H所对应的字符串“a”加上Code=0H所对应的字符串的第一个字符“a”，即“aa”添加到字串表中，其索引为6H，同时使OldCode=Code=0H。 读入下一个编码Code=1H，由于字串表中存在该索引，因此输出1H所对应的字符串“b”，然后将OldCode=0H所对应的字符串“a”加上Code=1H所对应的字符串的第一个字符“b”，即“ a b ” 添 加 到 字 串 表 中 ， 其 索 引 为 7 H ， 同 时 使OldCode=Code=1H。 读入下一个编码Code=2H，由于字串表中存在该索引， 因此输出2H

30、所对应的字符串“c”，然后将OldCode=1H所对应的字符串“b”加上Code=2H所对应的字符串的第一个字符“c”，即“ b c ” 添 加 到 字 串 表 中 ， 其 索 引 为 8 H ， 同 时 使OldCode=Code=2H。 读入下一个编码Code=7H，由于字串表中存在该索引，因此输出7H所对应的字符串“ab”，然后将OldCode=2H所对应的字符串“c”加上Code=7H所对应的字符串的第一个字符“a”， 即“ c a ” 添 加 到 字 串 表 中 ， 其 索 引 为 9 H ， 同 时 使OldCode=Code=7H。 读入下一个编码Code=1H，由于字串表中存在

31、该索引，因此输出1H所对应的字符串“b”，然后将OldCode=7H所对应的字符串“ab”加上Code=1H所对应的字符串的第一个字符“b”，即 “ a b b ” 添 加 到 字 串 表 中 ， 其 索 引 为 A H ， 同 时 使OldCode=Code=1H。 读入下一个编码Code=BH，由于字串表中不存在该索引， 因此输出OldCode=1H所对应的字符串“b”加上该字符串的第一个字符“b”，即“bb”，同时将“bb”添加到字串表中，其索引为BH， 同时使OldCode=Code=BH。 读入下一个编码Code=3H，由于字串表中存在该索引， 因此输出其对应的字符串“d”，然后将O

32、ldCode=BH所对应的字符串“bb”加上Code=3H所对应的字符串的第一个字符“d”，即“bbd”添加到字串表中，其索引为CH，同时使OldCode=Code=3H。读入下一个编码Code=5H， 它等于LZW_EOI， 数据解码完毕， 最后的解码结果为aabcabbbbd。为清晰起见， 完整的解码过程如表7-7所示。 表表7-7 GIF-LZW解码过程解码过程 7.6 算算 术术 编编 码码 算术编码有两种模式：一种是基于信源概率统计特性的固定编码模式，另一种是针对未知信源概率模型的自适应模式。自适应模式中各个符号的概率初始值都相同， 它们依据出现的符号而相应地改变。只要编码器和解码器

33、都使用相同的初始值和相同的改变值的方法，那么它们的概率模型将保持一致。上述两种形式的算术编码均可用硬件实现，其中自适应模式适用于不进行概率统计的场合。有关实验数据表明，在未知信源概率分布的情况下， 算术编码一般要优于Huffman编码。在JPEG扩展系统中，就用算术编码取代了哈夫曼编码。 下面结合一个实例来阐述固定模式的算术编码的具体方法。设一待编码的数据序列（即信源）为“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,

34、0.6）, c=0.6, 0.8）, d=0.8, 1.0） 为便于讨论， 再给出一组关系式： StartN=StartB+LeftCL EndN=StartB+RightCL 式中，StartN、EndN分别表示新间隔（或称之为区间）的起始位置和结束位置，StartB表示前一间隔的起始位置，L为前一间隔的长度， LeftC、RightC分别表示当前编码符号的初始区间的左端和右端。 第一个被压缩的符号为“d”，其初始间隔为0.8, 1.0)； 第二个被压缩的符号为“a”，由于前面的符号“d”的取值区间被限制在0.8, 1.0)范围内，所以“a”的取值范围应在前一符号间隔0.8, 1.0)的0,

35、 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)之间。 第三个被压缩的符号为“c”， 其编码取值范围应在0.8, 0.88)区间的0.6, 0.8)的子区间内，据上式可知 864. 0)8 . 088. 0(8 . 08 . 0848. 0)8 . 088. 0(6 . 08 . 0NNEndStart第四个被压缩的符号为“a”，同理，根据上式可知 StartN=0.848+0(0.864-0.848)=0.848EndN=0.848+0.4(0.864-0.

36、848)=0.8544 第五个被压缩的符号为“b”，同理，根据上式可知 StartN=0.848+0.4(0.8544-0.848)=0.85056EndN=0.848+0.6(0.8544-0.848)=0.85184 至此，数据序列“dacab”已被描述为一个实数区间0.85056, 0.85184，或者说在此区间内的任一实数值都惟一对应该数据序列。这样，就可以用一个实数表示这一数据序列。我们把区间0. 850 56, 0.851 84用二进制形式表示为0.110110011011, 0.110110100001。 从这个区间可以看出，0.1101101位于这个区间内并且其编码最短， 故把

37、其作为数据序列“dacab”的编码输出。考虑到算术编码中任一数据序列的编码都含有“0.”，所以在编码时，可以不考虑“0.”，于是把1101101作为本例中的数据序列的算术编码。由此可见， 数据序列“dacab”用7比特的二进制代码就可以表示， 平均码长为1.4比特字符。 解码是编码的逆过程，根据编码时的概率分配表和压缩后数据代码所在的范围，确定代码所对应的每一个数据符号。由此可见，算术编码的实现方法要比哈夫曼编码复杂一些。 n预测编码是统计冗余数据压缩理论的三个重要分支之一。 n预测编码的理论基础是现代统计学和控制论，它主要减少了数据在时间和空间上的相关性。 n对于静止图像来说，预测编码将被图

38、像变换编码所取代。n而预测编码对于视频信号来说，它充分利用了连续帧之间的统计冗余性，是当今主流技术并且还会流行于未来。预测编码的基本原理预测编码的基本原理 v 预测编码是根据图像数学模型利用以往的样本值对于新样本值进行预测，然后将样本的实际值与其预测值相减得到一个误差值，对这一误差值进行编码。v 如果模型足够好且样本序列在时间上相关性较强，那么误差信号的幅度将远远小于原始信号，从而可以用较少的电平类对其差值量化得到较大的数据压缩效果。 预测编码的基本原理预测编码的基本原理 如果能精确地预测数据源输出，那就不存在关于数据源的不确定性，因而也就不存在要传输的信息。然而没有一个实际的系统能找到其完整

39、的数学模型，我们能找到的最好预测器是以某种最小化的误差对下一个采样进行预测的预测器。 v 通常预测器的设计不是利用数据源的实际数学模型，因为数据源的实际数学模型是非常复杂，而且是时变的。v实验结果表明以最小均方预测误差设计的预测器不但能获得最小均方预测误差，同时在视觉效果上也是比较好的 DPCM(差分差分脉冲编码）脉冲编码）工作原理工作原理+量化器输出到信道+列延迟器23/aa行延迟器2a1a+jiu,jie,jiu,*jie,*jiu,*jiu,*jiu, 1*1, 131,2*jijiuauavuij为输入信号ve*ij量化后的输出信号va1, a2, a3为预测系数*ijuv 为根据ui

40、-1,j、ui,j-1、ui-1,j-1对uij所作的预测值veij为差值信号*iju预测编码器n如果没有量化器，那么就是无损编码n如果有量化器，则是有损编码+ -符号符号编码编码压缩图像输入图像enfn fn量化器量化器n预测器预测器预测方程为 量化器的输入为重建方程为v预测模型的复杂程度取决于线性预测中使用以前样本的数目，样本点越多，预测器就越复杂。 v预测器的好坏取决于预测系数*11,2,131,1ijiji jijuaua ua u*ijijijeuu*ijijijuue无损预测编码n举例：公式： 中取：nm = 2，a1 = a2 = 1/2f = 154,159,151,149,1

41、39,121,112,109,129预测值 f2 = 1/2 * (154 + 159) 156 e2 = 151 156 = -5 f3 = 1/2 * (159 + 151) = 155 e3 = 149 155 = -6 f4 = 1/2 * (151 + 149) = 150 e4 = 139 150 = -11 f5 = 1/2 * (149 + 139) = 144 e5 = 121 144 = -23 f6 = 1/2 * (139 + 121) = 130 e6 = 112 130 = -18 f7 = 1/2 * (121 + 112) 116 e7 = 109 116 =

42、-7 f8 = 1/2 * (112 + 109) 110 e8 = 129 110 = 19)(1miininfaroundf采用自适应系数预测编码后的重构图像a1=0.340, a2=0.664, a3=-0.005 1. 根据输入图像来确定预测系数 2. 另外一种采用的是固定的预测系数是采用固定系数预测编码后的结果 a1=0.5, a2=0.5, a3=-0.5 直接采用均匀标量量化后的结果在实验中采用几种不同的预测系数 采用不同的预测系数的预测编码的结果 混合编码混合编码n设计思想：设计思想： 每一种编码方式都有其擅长的一点，以及每一种编码方式都有其擅长的一点，以及局限的一点，混合编码

43、的思想就是将两局限的一点，混合编码的思想就是将两种以上的编码方式的优点进行综合，达种以上的编码方式的优点进行综合，达到提高编码效率的目的。到提高编码效率的目的。n混合编码实现的可能性及有效性分析混合编码实现的可能性及有效性分析回顾一下讲过的几个内容的特点：回顾一下讲过的几个内容的特点：1 1）行程编码：）行程编码： 擅长于重复数字的压缩。擅长于重复数字的压缩。2 2）HuffmanHuffman编码：擅长于像素个数分布不均匀情编码：擅长于像素个数分布不均匀情 况下的编码。况下的编码。n例：例： aaaa bbb cc d eeeee fffffff （共共2222* *8=176 bits)8

44、=176 bits) 4 3 2 1 5 7 行程编码：行程编码：4a3b2c1d5e7f 4a3b2c1d5e7f ( (共共6 6* *（8+38+3）= 66Bits = 66Bits ) ) 176 66 aaaa bbb cc d eeeee fffffff （共22*8=176 bits) 4 3 2 1 5 7 HuffmanHuffman编码：编码： f=01 e=11 a=10 b=001 c=0001 d=0000 10101010 001001001 00010001 0000 1111111111 01010101010101 (共共 7*2+5*2+4*2+3*3+2

45、*4+1*4=53 bits) 176 66 53 aaaa bbb cc d eeeee fffffff （共22*8=176 bits) 4 3 2 1 5 7 HufmanHufman与行程编码混合：与行程编码混合： 41030012000110000511701 (共：共：3+2+3+3+3+4+3+4+3+2+3+2=35 bits) 176 66 53 35 100%37.5%30.1% 9.9%预处理正交变换量化编码传输或存储后处理反变换译码f(x,y)g(x,y)7.8 正交变换编码正交变换编码 对变换系数编码对变换系数编码1.基本原理基本原理特性特性: :正交变换具有熵保持特

46、性正交变换具有熵保持特性正交变换具有能量保持特性正交变换具有能量保持特性能量的重新分布与集中能量的重新分布与集中去相关特性去相关特性(去冗余度去冗余度)2.数学模型分析数学模型分析 设图像信源设图像信源向量向量X, X =X0,X1,XN-1 变换后得变换后得向量向量Y, Y =Y0,Y1,YN-1 变换为变换为T正交矩阵正交矩阵 TT = I =TT-1 Y=TX 关键问题，在于选取什么样的正交变换关键问题，在于选取什么样的正交变换T, 才能既得到最大的压缩率，又不造成严重的才能既得到最大的压缩率，又不造成严重的失真失真YTXNM,Y,.,Y,YY1M10如果取一部分系数编码如果取一部分系数

47、编码则将将Y=TX代入，可得：代入，可得：的的均均值值与与分分别别是是)()(YXYXYYYYECXXXXECYX TCTCXY 研究研究Y的协方差矩阵的协方差矩阵Cx是图像本身固有是图像本身固有关键是寻找关键是寻找T,使变换系数间的相关性尽量小使变换系数间的相关性尽量小 (2)最佳的准则最佳的准则 均方误差准则下的最佳变换均方误差准则下的最佳变换 1010221010222),(),(1),(1NxNyNxNyyxfyxgNyxeNe3.最佳变换最佳变换(1)应满足的条件应满足的条件 把相关性全部去除把相关性全部去除 方差高度集中方差高度集中设有一数据向量设有一数据向量 X =x1,x2,x

48、N,正交变换后正交变换后 Y=TX Y =Y1,Y2,YN01ITTjijiji (3)K-L变换变换(Karhunan-Loeve) 设设T是正交变换矩阵是正交变换矩阵 T = 1, 2, NN N N是是N维向量，矩阵是正交的：维向量，矩阵是正交的： NiiiNYYTX1NN221121Y.YYY.则则 为压缩，取为压缩，取M个元素个元素 MN Y1,Y2,YM 其余用其余用bi代替，可得代替，可得X的估计值的估计值 NMiiiMiiibYX11X NMiiiNMiNMjjijjiiNMiiiiNMiiiMiiibYEbYbYEXXEXEbYbYXXXX12112111)()()()(:由

49、由正正交交条条件件为为均均方方差差设设估估计计误误差差： iNMiXiiNMiiNMiiiiiNMiiiiiiiiCXXXXEbYbYEbYEbYXbX 11112i )()(,Y 是是实实数数代代入入将将ib . 求求最最佳佳AXXEbXYYEbbYEbYEbbiiiiiiiiiiiii0 2)(2 又又 求条件极值，求条件极值，LagrangeLagrange法求极值法求极值求求f(xf(x1 1,x,x2 2, ,x,xN N) )服从服从 k k(x(x1 1,x,x2 2, ,x,xN N) )条件的极值问条件的极值问题题, ,作一个新的函数作一个新的函数1 ii是是拉拉格格朗朗日日

50、乘乘数数kNkNkkNxxxxxxf 12121),.,(),.,(B.B.求最佳的求最佳的 i i01 Nkikkixxf 1)1(11 NMiiiiiXiNMiiiiC iXiXiiCC 2对对 求求导导求极值求极值作一个新的函数作一个新的函数iiiXiiiXiiiiCCi 0222由线性代数理论由线性代数理论: : 0)(0iXiiXiiCIC 知知 i i是是C Cx x的特征根的特征根, , i i是是C Cx x的特征向量的特征向量(4)最佳变换的实现最佳变换的实现 a)给定信源给定信源X,统计统计X b)由由Cx求求 矩阵矩阵,即即 I-Cx 由由 I-Cx =0求特征根及特征向

51、量求特征根及特征向量 c)由特征向量求由特征向量求T d)由由T对图像作对图像作K-L变换变换求最佳变换求最佳变换 100011011XC0, 1, 20) 1() 1(100011011)(100011011 3213 fCIX例例:已知信源已知信源X写出写出 矩阵矩阵)0 ,(0) 1 , 0 , 0(1)0 ,(),0 , 1 , 1 (0000100011011212132212132121321同理归一化基础解系xxxxxxxx求求 1=2的特征向量的特征向量( 1I-Cx)X=0 01000010002121212121212121TT求求T3 DCT变换编码nDCTDCT变换编码方法：变换编码方法：DCT变换变换DCTDCT逆变换逆变换原图像原图像除以量化矩阵除以量化矩阵取整取整1 1）编码过程：）编码过程：2 2）解码过程：）解码过程：压缩图像压缩图像乘以量化矩阵乘以量化矩阵取整取整压缩压缩图像图像解压解压图像图像3 DCT变换编码Huffman:42bits； 编码效率编码效率32.8%Huffman:16bits;编码效率：编码效率：12.5%29221714241613141914121216111116C例：例：56606159586059625759596157586059F