!利用游程编码实现二值图像压缩.

算术编码 游程编码都属于无损压缩 算术编码 算术编码 Arithmetic coding 算术编码是一种无损数据压缩方法 也是一种熵编码的方法 和其它熵编码方法不同的地方在于 其他的熵编码方法通常 是把输入的消息分割为符号 然后对每个符号进行编码 而算术编码是直接把整个输入的消息编码为一个数 一个满足 0 0 n 1 0 的小数 n 算术编码用到两个基本的参数 符号的概率和它的编码间隔 信源符号的概率决定压缩编码的效率 也决定编码过程中信 源符号的间隔 而这些间隔包含在 0 到 1 之间 算术编码的算法思想如下 1 对一组信源符号按照符号的概率从大到小排序 将 0 1 设为当前分析区间 按信源符号的概率序列在当前分析区间划 分比例间隔 2 检索 输入消息序列 锁定当前消息符号 初次检索的话就是第一个消息符号 找到当前符号在当前分析区间的比 例间隔 将此间隔作为新的当前分析区间 并把当前分析区间的起点 即左端点 指示的数 补加 到编码输出数里 当前消 息符号指针后移 3 仍然按照信源符号的概率序列在当前分析区间划分比例间隔 然后重复第二步 直到 输入消息序列 检索完毕为止 4 最后的编码输出数就是编码好的数据 在算术编码中需要注意几个问题 1 由于实际计算机的精度不可能无限长 运算中出现溢出是一个明显的问题 但多数及其都有 16 位 32 位或者 64 位 的精度 因此这个问题可以使用比例缩放方法解决 2 算术编码器对整个消息只产生一个码字 这个码字是在间隔 0 1 中的一个实数 因此译码器在接受到表示这个实数的 所有位之前不能进行译码 3 算术编码是一种对错误很敏感的编码方法 如果有一位发生错误就会导致整个消息译错 算术编码可以是静态的或者是自适应的 在静态算术编码中 信源符号的概率是固定的 在自适应算术编码中 信源符号 的概率根据编码时符号出现的频率动态地进行修改 在编码期间估算信源符号概率的过程叫做建模 需要开发动态算术编 码的原因是因为事前知道精确的信源概率是很难的 而且不切实际 当压缩消息时 不能期待一个算术编码器获得最大的 效率 所能做的最有效的方法是在编码过程中估算概率 因此动态建模就成为确定编码器压缩效率的关键 游程编码 游程编码 RLE 编码编码 Run Length Encoding 游程编码又称 运行长度编码 或 行程编码 是一种统计编码 该编码属于无损压缩编码 对于二值图有效 行程编码的基本原理是 用一个符号值或串长代替具有相同值的连续符号 连续符号构成了一段连续的 行程 行程编码因 此而得名 使符号长度少于原始数据的长度 例如 5555557777733322221111111 行程编码为 5 6 7 5 3 3 2 4 l 7 可见 行程编码的位数远远少于原始字符串的位数 在对图像数据进行编码时 沿一定方向排列的具有相同灰度值的像素可看成是连续符号 用字串代替这些连续符号 可大 幅度减少数据量 行程编码分为定长行程编码和不定长行程编码两种类型 行程编码是连续精确的编码 在传输过程中 如果其中一位符号发生错误 即可影响整个编码序列 使行程编码无法还原 回原始数据 游程编码所能获得的压缩比有多大 主要取决于图像本身的特点 如果图像中具有相同颜色的图像块越大 图像块数目越 少 获得的压缩比就越高 反之 压缩比就越小 利用游程编码实现二值图像压缩利用游程编码实现二值图像压缩 文章出处 编码方案设计 按位进行压缩 对二进制流进行超前扫描 判断是否值得压缩 如果压缩有意义 则压缩 否则保持原始数据 系统实现方案 总体思想 将图像文件以二进制方式读入缓冲区 把二进制位转制为整数 对缓冲区数据进行编码 以特定的格式 unsigned short 写入输出文件 解压缩过程反过来即可 压缩文件存储格式 以每两个字节为单位储存 即每次写入 16 位 unsigned short 类型 0 1 2 15 第 0 位 存储压缩信息 1 压缩 0 不压缩 原始数据 第 1 位 如果第 0 位为 1 压缩 此位标明字符类别 0 或 1 如果第 0 位为 0 原始数据 此位无意义 默认为 0 后 14 位 存储字符数量或者原始数据的值 算法实现 缓冲区 定义缓冲区为一维 char 数组 因为只用 14 位来统计数量 所以缓冲区总字符量即维数应小于或等于 214 16384 判断可压缩性 对当前指针位置 超前扫描 16 位 如果这 16 位全相同 例 11111111111111 或 00000000000000 那 么可压缩性为真 从当前位置开始计数并指针前移 直到相同序列终止或到达缓冲区边界为止 将统计数量写入 unsigned short 类型后 14 位 第 0 位置 1 第 0 位置为当前字符 如果 16 位中有不相同数据 例 11111101111011 或缓 冲区中有效数据不足 16 位 那么可压缩性为假 从当前位置开始读 14 位 如果缓冲区中剩余不足 14 位 有多少位读 多少位 把原始数位写入 unsinged short 类型后 14 位 前两位置 0 解压缩 每次从压缩文件读取 16 位到 short 类型 根据第 0 位和第 1 位的数值进行相应的解码处理 直到缓冲区满 每次从缓冲区中取 位 写入文件 源码 gcc 或 C 编译器 Bmpheader h typedef unsigned char BYTE typedef unsigned short WORD typedef unsigned long DWORD typedef long LONG typedef struct BITMAPFILEHEADER BYTE bfType 2 位图文件的类型 必须为 BM DWORD bfSize 位图文件的大小 以字节为单位 WORD bfReserved1 位图文件保留字 必须为 WORD bfReserved2 位图文件保留字 必须为 DWORD bfOffBits 位图数据的起始位置 以相对于位图文件头的偏移量表示 以字节为单位 BITMAPINFOHEADER DWORD BiSize 本结构所占用字节数 LONG BiWidth 位图的宽度 以像素为单位 LONG BiHeight 位图的高度 以像素为单位 WORD BiPlanes 目标设备的级别 必须为 WORD BiBitCount 每个像素所需的位数 必须是 DWORD BiCompression 位图压缩类型 必须是 0 不压缩 1 BI RLE8 压缩类型 或 BI RLE4 压缩类型 之一 DWORD BiSizeImage 位图的大小 以字节为单位 LONG BiXpelsPerMeter 位图水平分辨率 每米像素数 LONG BiYpelsPerMeter 位图垂直分辨率 每米像素数 DWORD BiClrUsed 位图实际使用的颜色表中的颜色数 DWORD BiClrImportant 位图显示过程中重要的颜色数 BITMAPHEADER 颜色表 typedef struct unsigned char blue 蓝色的亮度 值范围为 255 unsigned char green unsigned char red char reserved 保留 必须为 RGBQUAD 压缩字符流结点 Main cpp 黑白点二值位图游程编码压缩程序 2008 3 20 作者 付闯 include include include include include bmpheader h const unsigned short MaxSize 16384 14 字节最大数 void compress FILE FILE 压缩 void decompress FILE FILE 解压缩 void wbuffer FILE char int 将像素信息写入缓冲区 void buf init char int 缓冲初始化 void rbuffer FILE char int 读缓冲到文件 unsigned long RLE FILE char int unsigned long 游程压缩 并返回写入字节数 void decode FILE char int 解码 逆运算 void bufdisplay char char int 打印缓冲 测试用 DWORD getBMPsize FILE ifp 获取位图大小 int IsFeasible char char int 判断压缩可行性 可行 int main FILE ifp ofp ffp char choic char ifilename ofilename ifilename char malloc 1 ofilename char malloc 1 printf a 压 缩 b 解压缩 choic getch if choic a printf 请输入压缩 Compress 源文件名 scanf s ifilename printf 请输入压缩 Compress 输出文件名 scanf s ofilename if ifp fopen ifilename rb NULL printf 无法打开文件 getch return 1 if ofp fopen ofilename wb NULL printf 无法创建文件 getch return 1 compress ifp ofp printf 文件 s 成功压缩为文件 s ifilename ofilename fclose ifp fclose ofp else printf 请输入解压缩 Decompress 源文件名 scanf s ifilename printf 请输入解压缩 Decompress 输出文件名 scanf s ofilename if ofp fopen ifilename rb NULL printf 无法打开文件 getch return 1 if ffp fopen ofilename wb NULL printf 无法创建文件 getch return 1 decompress ofp ffp printf 文件 s 成功解压缩为文件 s ifilename ofilename fclose ofp fclose ffp getch return 0 DWORD getBMPsize FILE ifp DWORD size fseek ifp 2 0 fread rewind ifp return size 缓冲区初始化 void buf init char buffer int size memset buffer 1 size 以下是压缩算法 void compress FILE ifp FILE ofp unsigned long input output 0 input getBMPsize ifp char buffer MaxSize 缓冲区 while feof ifp wbuffer ifp buffer MaxSize output RLE ofp buffer MaxSize output printf Compressing Rate f output 100 0 input printf d sizeof OutUnit 将二进制的位写入缓冲区 void wbuffer FILE ifp char buffer int size char tpbuf buffer unsigned char temp 0 int i fseek ifp 62 0 buf init buffer size while size 0 每次取 8 个像素 if feof ifp break BUG 之所在 必须要再读一个字节 函数才能判断文件尾 for i 7 i 0 i tpbuf tpbuf temp i 写入一行转换为二进制 高位在行左边 printf d buffer MaxSize size j size 8 bufdisplay codisplay txt buffer MaxSize getch 对缓冲区中数值进行编码 并返回码序列 unsigned long RLE FILE ofp char buffer int size unsigned long output unsigned short ounit 0 count 0 int i 0 char temp char tpbuf buffer temp 0 while tpbuf 1 k tpbuf i 越界了 count tpbuf id 0 任意值 fwrite else count 0 ounit 1 15 压缩 ounit temp 14 while tpbuf temp tpbuf i ounit count fwrite output sizeof unsigned short return output int IsFeasible char current char buffer int size char i id int distance current buffer for i 0 id current i size 1 return 0 return 1 以下是解压缩算法 void decompress FILE ifp FILE ofp char buffer MaxSize buf init buffer MaxSize while feof ifp fgetc ifp decode ifp buffer MaxSize rbuffer ofp buffer MaxSize printf Waiting getch 根据编码规则进行解码 void decode FILE ifp char buffer int size int i 0 unsigned short temp 0 char tpbuf buffer buf init buffer MaxSize while i 1 14 num1 i tpbu