数;据压缩技术讲课.ppt

* 信息工程学院 戴 永 * 二维DCT 算法是对于一个大小为N ×N 的像素块来说，假设x ( i ，j) 为输入的像素点阵数据，其二维DCT变换公式如下: * 信息工程学院 戴 永 * 上式也可以写成矩阵运算形式Z = CXCT 其中，C为带余弦基本函数的变换系数矩阵，CT 为C 的转置。从上两式可以看出，二维DCT 变换是可分离的，它可以分解成串联的两次一维变换，即： 写成矩阵形式为: Z = CY，Y = XCT 这里，Y为中间乘积矩阵(Y的列等于X 行的一维DCT 输出) 。因此，在做二维DCT 变换时，可以应用一维DCT 变换来计算，即先沿X 的行进行一维DCT 计算获得Y，再沿着Y的转置的行进行一维DCT运算。 * 信息工程学院 戴 永 * 反离散余弦变化（IDCT）的实用公式 * 信息工程学院 戴 永 * 4.4二维DCT图  像压缩实现 　是否打开？ 打开256色灰度图 出错提示 对位图按照8*8分块处理 顺序将图象像素值读入到数组中，并写入初始文件存储 对分块后的位图的像素矩阵进行DCT变换 对DCT结果进行量化 将DCT变换量化后的数据存储起来，等待RLE压缩处理 开始 结束 * 信息工程学院 戴 永 * 开始 Y 读取下一行 结束 bChar12是否相等 iCount是否大于255 bChar1写入， bChar1＝ bChar2； 255，iCount ，bChar1写入文件 bChar2＝ bChar1； iCount＝1； 读取下一个字节，存入bChar2中 行是否结束 列是否结束 读取当前字节存入bChar1中，iCount=1； iCount＋＋； Y Y Y N N N N RLE压缩编码程序流程图 * 信息工程学院 戴 永 * RLE解压缩算法流程图 是 是 有 否 开始 结束 读取下一行 读取当前字节存入bChar中， iCount=1； 读取标志为后的数字存入iCount， 读取标志位后的第二位数字存入bChar 当iCount=0时，读入下个字节 行是否结束 将bChar写入文件，写入iCount次 同时每写入一次iCount-1； 否 否 判断bChar中标志位 列是否结束 * 信息工程学院 戴 永 * 反离散余弦变换图 读入加载的压缩文件 将图像像素矩阵分成8*8的若干像素矩阵 开始 利用二维IDCT公式，分别对以上的分块进行变换 结束IDCT 显示变换后的图像 * 信息工程学院 戴 永 * 例1. 设单词bet在词典的第1025项,编码为20位数0|0000000010000000001. 例2.单词xet不在词典中,用三个字段来标识 1|000001101100101共4个字节,左起红1为标志码,表示找不到匹配词;标志码后跟的是单词字母数的2进制编码;再后为各字母对应的ASCII码串. 采用这种代码结构的压缩性分析: 设单词平均长5个字符,输入N个词,可匹配概率为P.对N个词进行压缩处理会出现两种情况, * 信息工程学院 戴 永 * (1)在词典中可查,则压缩为20位,如例1,可压缩为20位的词有NP个,对应输出20NP位; (2)在词典中不可查,则压缩为三个字段,如例2,字母数按平均5个算,则每个单词平均占(5+1)8=48位,不可压缩为20位的词有N(1-P)个,对应输出48N(1-P)位; 总的输出位为20NP+ 48N(1-P)=N(48-28P),而总的输入为5·8N=40N,达到压缩的条件是40N (48-28P)N,或当P0.29时可产生压缩效果. 当P=0.29,即字典中可匹配词太少时,会出现膨胀现象. 这种静态方法比较适用用词规范的文本压缩.对于不规范文字的文本多采用自适用字典方法. * 信息工程学院 戴 永 * 自适用字典方法的一般原理为 给出一个空字典或一个默认的小字典开始,把从输入数据流中遇到的新字添加进去,并删除旧字.具体过程是 (1)从输入数据流中读一段文本,通过语法解析,将其分解为字或短语