基于哈夫曼编码的图像编解码系统设计及实现(编辑修改稿)

基于哈夫曼编码的图像编解码系统设计及实现(编辑修改稿)内容摘要：

两个值作为叶子节点构成一棵二叉树，值较 大的叶子节点在左，两个叶子节点对应的频率之和作为根节点。 把原排列中最小的两个节点删除，新的根节点插入排列保持大小从左到右的排列顺序不变；重复执行 2），直到最后得到值为 1 的根节点。 得到一棵哈夫曼 树，如下图所示： 图 哈夫曼编码树 在得到的 哈夫曼 树上左分支标记 1，右分支标记 0，所有的字符根据其频率标记到对应的叶子节点上，从根节点到叶子节点路径上遇到的 0、 1 字符串即为对应叶子节点所在字符的武汉理工大学《 信息处理课群综合训练与设计 》 5 编码。 a、 b、 c、 d、 e、 f、 g 七个字符的 哈夫曼 编码分别是： 000 0000、 001 1 00010，可以看到 ,符号只能出现在树叶上 ,任何一个字符的路径都不会是另一字符路径的前缀路径。 哈夫曼编码的缺点 哈夫曼编码虽然是最佳编码，但 存在一些缺点 ，具体如下 ： （ 1）对于过短的文件进行编码，意义不大。 因为存储哈夫曼树的信息需要一定的存储空间； （ 2）利用哈夫曼编码，若用于通信网络，会引起较大的延时； （ 3）对较大文件进行编码，会出现频繁的磁盘读写访问，降低了数据编码的速度。 武汉理工大学《 信息处理课群综合训练与设计 》 6 3 基于哈夫曼编码的图像编解码 系统的程序设计 分块程序设计 分析 （ 1）首先，寻找出 现的所有元素，接着计算各元素出现的概率，并将元素按照出现概率排列，产生码字。 部分程序如下： function [huffcode， info]=codeing（ vector） p=probability（ vector）； %计算各元素出现的概率 simbols=find（ p）； %寻找出现的所有元素 p=p（ simbols）； [p， sortindex]=sort（ p）； %概率从小到大排列 simbols=simbols（ sortindex）； %将元素按照出现概率排列 len=length（ simbols） ； %产生码字 （ 2）把出现的元素概率最小的两个相加合并成新的概率，与剩余的概率组成新的概率集合，直到剩下最后两个概率。 部分程序如下： while length（ p） 1； index1=simbols_index{1}； index2=simbols_index{2}； codeword_tmp （ index1） =addnode （ codeword_ tmp（ index1）， uint8（ 0））； codeword_tmp （ index2） =addnode （ codeword_ tmp（ index2）， uint8（ 1））； p=[sum（ p（ 1:2）） p（ 3:end） ]； simbols_index =[{[index1 index2]} simbols_index（ 3:end） ]； [p， sortindex]=sort（ p）； %将数据重新排列 simbols_index=simbols_index（ sortindex）； （ 3）从最后一步开始反向进行分配码字，对于每次相加的两个概率，给大的赋 “0”，小的赋 “1”，存储到一个稀疏矩阵，最后写出 01 序列的哈夫曼编码。 部分程序如下： 武汉理工大学《 信息处理课群综合训练与设计 》 7 pad=8mod（ len， 8）； if pad0； string=[string uint8（ zeros（ 1， pad）） ]； end cols=length（ string） /8； %计算压缩后的向量 string=reshape（ string， 8， cols）； weights=2.^（ 0:7）； huffcode =uint8 （ weights*double （ string））； % 编码字符串凑成一个 %字节一个字节存在 huffcode codeword=codeword（ simbols）； %保存实际有出现元素对应的码字 （ 4） 把整字节存储的 huffcode 一位一位取出，转为字符串，去掉原来为凑整字节数所添加的零进行解码。 部分解码程序如下： vector=zeros（ 1， ， 39。 uint839。 ）； %解码 vectorindex=1； codeindex=1； code=0； for index=1:len； code=bitset（ code， codeindex， string（ index））； codeindex=codeindex+1； byte = （ bitset （ code， codeindex））； %从码字表中读出对应元素 if byte0； vector（ vectorindex） =byte1； codeindex=1； code=0； vectorindex=vectorindex+1； （ 5）显示编码的压缩信息（如压缩率、最大码长等），部分程序如下所示： whos data huffcode huffdecode %显示压缩效果 fprintf（ 39。 pad=%d\n39。 ， ）； %=为凑整字节数，编码字符 武汉理工大学《 信息处理课群综合训练与设计 》 8 串最后添加零的位数 fprintf （ 39。 ratio=%f\n39。 ， ）； %=压缩率 fprintf （ 39。 maxcodelen=%d\n39。 ， ）； %=最大码长 主程序 系统设计的完整主程序如下 %%%%%%%%%%%%%%%%%%%%%%%%%主程序 %%%%%%%%%%%%%%%%%%%%%%%%%%% % 信息处理课群综合训练与设计 基于哈夫曼编码的图像编解码系统设计及实现 %信息 SY1001 班 王鸣 0121009320403 clc clear cd。 X=imread(39。 39。 )。 data=uint8(X)。 [zipped,info]=huffencode(data)。 unzipped=huffdecode(zipped,info)。 subplot(121)。 imshow(data)。 title(39。 原始图像 39。 ) subplot(122)。 imshow(unzipped)。 title(39。 解码后的图像 39。 ) whos data unzipped zipped fprintf(39。 pad=%d\n39。 ,)。 %=为凑整字节数，编码字符串最后添加零的位数 fprintf(39。 ratio=%f\n39。 ,)。 %=压缩率 fprintf(39。 maxcodelen=%d\n39。 ,)。 %=最大码长 程序函数 编码函数 主程序中使用的函数代码如下 武汉理工大学《 信息处理课群综合训练与设计 》 9 %%%%%%%%%%%%%%%%%%%%%%%%%%编码 函数 %%%%%%%%%%%%%%%%%%%%%%%%%% % 信息处理课群综合训练与设计 基于哈夫 曼编码的图像编解码系统设计及实现 %信息 SY1001 班 王鸣 0121009320403 %huffencode 函数对输入矩阵 vector 进行 huffman 编码，返回编码后的向量及相关信息 function [zipped,info]= huffencode(vector) if ~isa(vector,39。 uint839。 ) eror(39。 input argument must be a uint8 vector39。 )。 end。