四川大学计算机学院 多媒体技术 4

1、语义依赖（语义依赖（semantic-dependent）的）的DC方法方法n应用背景：应用背景：对于对于“局部冗余局部冗余”的特殊类型。的特殊类型。主要应用于图象表达、处理。主要应用于图象表达、处理。n原因：原因：n数字化的数字化的image有大量的有大量的“局部冗余局部冗余” n占空间大占空间大n（一幅图像中具有许多颜色相同的图块。在这些（一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的象素都具有相同的颜色值。）行上有许多连续的象素都具有相同的颜色值。）语义依赖（语义依赖（semantic-depe

2、ndent）的）的DC方法方法典型：典型：n行程编码（行程编码（run-length encoding:RLE）n差异映射差异映射(difference mapping)n词典编码词典编码(Dictionary Encoding) 语义依赖（语义依赖（semantic-dependent）的）的DC方法方法差异映射：差异映射：n算法思想：算法思想：n图象表示为相邻像素在亮度图象表示为相邻像素在亮度/颜色上的差异颜色上的差异阵列，而不是像素本身的亮度阵列，而不是像素本身的亮度/颜色值颜色值n例例Laeser et al.1986 n8 bits/pixel (256 brightness)3 b

3、its/pixel 语义依赖（语义依赖（semantic-dependent）的）的DC方法方法词典编码词典编码n词典：词典：n全部词语（全部词语（words） n常用词语常用词语+词语结束符号词语结束符号n编码方法：编码方法：n指向词典的指针表指向词典的指针表n指向词典的指针表（常用词语）指向词典的指针表（常用词语）+编码编码（不常用词语）（不常用词语）语义依赖（语义依赖（semantic-dependent）的数据压缩）的数据压缩方法方法缺点：缺点：n实用性有限实用性有限n可以用其他更一般的编码方法获得相同可以用其他更一般的编码方法获得相同效果效果n如如huffman编码、编码、 Lemp

4、el-Ziv编码编码RLE编码编码n行程编码行程编码(RLE(RLE）算法）算法: :x1, x2, xn -( c1 ,l1 ), ( c2,l2 ), ( ck,lk ) c ci i: : 亮度亮度/ /颜色颜色l li i : :第第i i行程（相同亮度行程（相同亮度/ /颜色的像素的序列）的长度颜色的像素的序列）的长度n不需要存储每一个象素的颜色值，而仅仅存储一个象素的颜色值，以及具有相同颜色的象素数目就可以；或者存储一个象素的颜色值，以及具有相同颜色值的行数。n具有相同颜色并且是连续的象素数目称为行程长度。RLE编码编码n例：n代码字为：代码字为：（0，8),（1，3),（8，50

5、),（1，4),(0，8）RLE编码编码RLE所能获得的压缩比主要是取决于图像本身的特点。如果图像中具有相同颜色的图像块越大，图像块数目越少，获得的压缩比就越高。反之，压缩比就越小。RLE是无损压缩技术。RLE编码编码应用：尤其适用于计算机生成的图像，对减少图像文件的存储空间非常有效。（对颜色丰富的自然图像不能单纯使用RLE一种编码方法，需要和其他的压缩编码技术联合应用。）商业数据处理（如连续多个0，空格）分解与编码n源信息代码（长度）：nblock - blocknblock - variablenvariable - blocknvariable - variable例：例：“aa bbb

6、 cccc ddddd eeeeee fffffffgggggggg”n block - block (120) nSource massagecodeword na000nb001nc010nd011ne100nf101ng110nspace111例：例：“aa bbb cccc ddddd eeeeee fffffffgggggggg”n variable - variable (30) nSource massagecodeword naa0nbbb1nccccc10nddddd11neeeeeee100nfffffff101ngggggggg110nspace111分解与编码“定义字”

7、与“自由分解”方法n定义字（defined-word）方式n源信息分解的长度在编码调用之前已确定n自由分解（free-parse）方式n编码算法本身决定源信息分解的长度（变长）分解与编码典型算法n定义字方式的：nShannon-FanoShannon-Fano coding codingnHuffman codingHuffman codingnUniversal codes (Universal codes (通用码通用码) )nArithmetic coding (Arithmetic coding (算术编码算术编码) )n自由分解方式的：nLempel-Ziv codesLempel-

8、Ziv codesnAlgorithm BSTWAlgorithm BSTWLempel-Ziv编码编码nvariable - blockn自由分解n算法：n一规则：从一个有限字母表分解出不超过规定长度的子串或词；n一编码方法：将子串顺序地映射成固定长度、可辨认的代码字。Lempel-Ziv编码编码n策略：选出几乎必定出现的字串。使得概率大的字符，组成较长串；概率小的字符，组成较短串。n 对有效利用冗余，因为n符号的频繁出现n字母重复n高使用模式Lempel-Ziv编码编码n不断增长长度的语法分析策略：n在编码的每一步，分解出剩余源信息集合中与现有表的某项 匹配的最长前缀，追加上源信息集合中该

9、前缀的后一字符c,将c加入编码表中，编为（i,c): i现有表项的代码字；c追加的字符Lempel-Ziv编码编码n例：例：“010100010”n分解：分解：0，1，01，00，010n编码：编码：(0,0), (0,1), (1,1), (1,0), (3,0)例：例：“aa bbb cccc ddddd eeeeee fffffffgggggggg”（3-bits:ag, , 5-bits: table indexes,码长码长=173）na1e12n1212e13nb313e14n3b45f15n5f16nc616f17n6c717f18n6 8g19nd919g20n9d1020g21n10 1120 22Lempel-Ziv编码编码n评价：n简单，且贪心（每步找最长识别串）n渐近最优nHash 查找n实际应用：nUNIX资源压缩，5060%的压缩率 LZ78算法算法例：输入为“ABBCBCABA”步骤位置词典输出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A) LZ W算法算法例：输入为“ABBABABAC”步骤位置(序号)词典输出(1) A(2) B(3) C11(4) AB122(5) BB233(6) BA244(7) ABA456(8) ABAC763 LZ 77算法算