数据压缩技术概论.pptVIP

假设对x编码，令 q = int( log2x ) 则编码的前一部分是q个1加一个0，后一部分是q位长的二进制数，其值等于(x-2q ) 值 x 编码 1 0 2 10 0 3 10 1 4 110 00 5 110 01 6 110 10 7 110 11 8 1110 000 9 1110 001 γ编码 LZ77算法的其他问题 其他的编码方式： 输出匹配串时不输出后续字符 输出0表示下面是一个匹配串，输出1表示下面是一个单个字符 对匹配串长度加以限制 如何查找匹配串： 限制匹配串的长度，在内存中组织二叉有序树 将窗口中每个长度为3的字符串建立字典索引 使用Hash表建立索引 使用字符树建立索引 窗口滑动时内存中的索引重建问题： 建立环状偏移 以环状偏移为基础建立窗口索引 内存词典： 第二步：压缩串“AD ...”在内存词典中仍无法找到匹配串，则输出二元组 (0，“A”) 并将字串“A”置入内存词典 第一步：压缩串“DAD...”在内存词典中无法找到匹配串，则输出二元组 (0，“D”) 二元组中第一个元素表示词典的索引，第二个元素表示后续字符。 并将字串“D”置入内存词典 内存词典： LZW算法 LZW算法是LZ78的改进，其基本思路是在内存中维护一个动态的字典，输出的代码是该字典的索引 例：待压缩的信息为 DAD DADA DADDY DADO... 索引 0 词条 null 索引 0 1 词条 null “D” 第三步：压缩串“D D...”在内存词典中可以找到最大匹配串“D”，输出 二元组 (1，“ ”) 以此对字串“D ”进行了编码，然后将“D ”置入内存词典 内存词典： 内存词典： 第四步：压缩串“DAD...”在内存词典中可以找到最大匹配串“D”，则输出 二元组(1，“A”) 以此对字串“DA”进行了编码，然后将“DA”置入内存词典 LZW算法 例：待压缩的信息为 DAD DADA DADDY DADO... 索引 0 1 2 词条 null “D” “A” 索引 0 1 2 3 词条 null “D” “A” “D ” LZW算法 例：待压缩的信息为 DAD DADA DADDY DADO... 第九步后，内存词典的情况如下： 索引 0 1 2 3 4 词条 null “D” “A” “D ” “DA” 索引 5 6 7 8 9 词条 “DA ” “DAD” “DY” “ ” “DADO” 每一步的输出如下（每一步输出均为二元组）： 步骤 1 2 3 4 5 输出 (0,”D”) (0,”A”) (1,” ”) (1,”A”) (4,” ”) 步骤 6 7 8 9 输出 (4,”D”) (1,”Y”) (0,” ”) (6,”O”) JPEG图像压缩算法 JPEG 是有损压缩算法 JPEG 核心是“离散余弦变换(Discrete Cosine Transform,DCT)” JPEG 压缩算法的基本步骤为： 1、离散余弦变换 DCT Transformation 2、系数量子化 Coefficient Quantization 3、无损压缩 Lossless Compression 一维波 二维波 离散余弦变换 DCT DCT操作X、Y、Z坐标轴上的三维信号。X、Y坐标轴是平面图像的两个维度，Z轴表示图象的象素值。对N * N的象素矩阵进行DCT变换的公式如下： 离散余弦变换(Discrete Cosine Transform,DCT)公式： 反向离散余弦变换(Inverse Discrete Cosine Transform,IDCT)公式： 其中： 但是：按照上述基本公式写出的程序实现存在一个严重的问题——时间复杂度太高 使用矩阵运算的DCT替代公式 实现上面的替代公式的程序代码的时间复杂度就大大降低了。进一步的改进还包括将余弦函数由浮点运算改为整数运算、改进傅立叶变换技术等。 量子化 Quantization DCT变换的输入是8位的象素值（0~255，JPEG实现时将其减去128，范围变成-128~127），但输出范围是从–1024到1023 ，占11位。 量子化即通过整除运算减少输出值的存储位数。 使用量子化矩阵（Quantization Matrix）来实现量子化。 量子化公式为： 量化后的值( i, j ) = ROUND( DCT(i, j) / 量子(i, j) ) 逆量子化公式为： DCT(i, j) = 量化后的值( i, j ) * 量子(i, j) 量子化是JPEG算法中损失图像精度的根源，也是产生压缩效果的源泉 量子表Quantum Table 4 7 10 13 16 19 22 25 7 10 13 16 19 22 25 28 10 13 16 19 22