于基哈夫曼编码的图像编解码系统设计及实现--毕业设计.doc

武汉理工大学《信息处理课群综合训练与设计》
课程设计任务书
题 目: 基于哈夫曼编码的图像编解码系统设计及实现

初始条件：
计算机
Windows8操作系统
MATLAB7.8.0软件

要求完成的主要任务:

设计哈夫曼编码的图像编解码系统、利用软件编写程序、仿真实现

时间安排：
第1-18周：理论讲解
第19周：理论设计，实验室安装调试以及撰写设计报告

答辩：
时间：7月2日
地点: 鉴主15楼通信实验室四

指导教师签名： 年 月 日

系主任（或责任教师）签名： 年 月 日

20
目录
目录 I
摘要 II
ABSTRACT III
1引言 1
1.1图像数据压缩的目的 1
1.2图像数据压缩的原理 1
1.3常用的压缩编码方法 3
2哈夫曼编码 3
2.1 哈夫曼编码简介 3
2.2哈夫曼编码步骤 3
2.3 哈夫曼编码的缺点 5
3基于哈夫曼编码的图像编解码系统的程序设计 6
3.1 分块程序设计分析 6
3.2主程序 8
3.3程序函数 8
3.3.1编码函数 8
3.3.2解码函数 12
3.3.3符号概率计算函数 13
3.3.4节点添加函数 14
3.3.5解码返回符号函数 14
4系统仿真结果 15
4.1程序运行结果 15
4.2 程序运行结果分析 16
5.总结 18
参考文献 19

摘要
本论文首先介绍了图像压缩相关知识。随后，分析概述了哈夫曼压缩编码的原理及方法，并采用 MATLAB 软件对两幅图片进行压缩编码程序设计，获得压缩信息及哈夫曼编码表，分析压缩后的图像像素数据及压缩比。

关键词： 图像压缩；MATLAB；哈夫曼编码;无损压缩编码

ABSTRACT
This paper firstly introduces the theoretical knowledge of image compression. Then, it analyses the principle and method of Huffman coding and using Huffman coding principle and methods, compression coding design is made for two images on the MATLAB software. Also gain the compression information and Huffman coding table. What’s more, compressed image pixel data and compression ratio are analyzed.

Key words： Image compression; MATLAB; Huffman encoding; Lossless compression coding

1引言
1.1图像数据压缩的目的
数字图像通常要求很大的比特数，这给图像的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。一般原始图像中存在很大的冗余度。
例如1；一幅512x512的灰度图象的比特数为512x512x8=256k 。
例如2；一部90分钟的彩色电影，每秒放映24帧。把它数字化，每帧512x512象素，每象素的R、G、B三分量分别占8 bit，总比特数为90x60x24x3x512x512x8bit=97,200M。
例如3：一张CD光盘可存600兆字节数据，这部电影光图像（还有声音）就需要160张CD光盘用来存储。
所以，对图像数据进行压缩显得非常必要。
而通常用户通常允许图像失真；当信道的分辨率不及原始图像的分辨率时，降低输入的原始图像的分辨率对输出图像分辨率影响不大；用户对原始图像的信号不全都感兴趣，可用特征提取和图像识别的方法，丢掉大量无用的信息；提取有用的信息，使必须传输和存储的图像数据大大减少。在以上的条件下，其为数据压缩提供了可能性。
图像数据压缩的目的是在满足一定图像质量条件下，用尽可能少的比特数来表示原始图像，以提高图像传输的效率和减少图像存储的容量。在信息论中称为信源编码。
1.2图像数据压缩的原理
对数字图像进行压缩通常利用两个基本原理:一是数字图像的相关性。在图像的同一行相邻象素之间，相邻象素之间，活动图像的相邻帧的对应象素之间往往存在很强的相关性，去除或减少这些相关性，也即去除或减少图像信息中的冗余度也就实现了对数字图像的压缩。帧内象素的相关称做空域相关性。相邻帧间对应象素之间的相关性称做时域相关性。二是人的视觉心理特征。人的视觉对于边缘急剧变化不敏感(视觉掩盖效应)，对颜色分辨力弱，利用这些特征可以在相应部分适当降低编码精度而使人从视觉上并不感觉到图像质量的下降，从而达到对数字图像压缩的目的。
图像压缩是通过删除图像数据中冗余的或者不必要的部分来减小图像数据量的技术，压缩过程就是编码过程，解压缩过程就是解码过程。压缩技术分为无损压缩和有损压缩两大类，前者在解码时可以精确地恢复原图像，没有任何损失；后者在解码时只能近似原图像，不能无失真地恢复原图像。假设有一个无记忆的信源,它产生的消息为{ai},1≤i≤N,其出现的概率是已知的,记为P(ai)。则其信息量定义为:

由此可见一个消息出现的可能性越小，其信息量就越多，其出现对信息的贡献量越大，反之亦然。
信源的平均信息量称为“熵”（entropy），可以表示为：

对上式取以2为底的对数时，单位为比特（bits）：

根据香农（Shannon）无噪声编码定理，对于熵为H的信号源，对其进行无失真编码所可能达到的最低比特数为，这里为一任意小的正数，因此可能达到的 　
最大压缩比：

其中B是原始图像的平均比特率。
在图像压缩中，压缩比是一个重要的衡量指标。可以定义压缩比为：

图像的平均码字长度R为：

编码效率η定义为:

信息冗余度为：

1.3常用的压缩编码方法
图1-1常用的压缩编码方法
2哈夫曼编码
2.1 哈夫曼编码简介
哈夫曼编码是哈夫曼博士在1952 年根据可变长最佳编码定理提出的, 它依据信源数据中各信号出现的频率分配不同长度的编码。即，对于出现概率大的信息符号编以短字长的码，对于出现概率小的信息符号编以长字长的码。采用哈夫曼编码方法的实质是针对统计结果对字符本身重新编码，而不是对重复字符或重复子串编码，得到的单位像素的比特数最接近图像的实际熵值。它是一种无损编码方法。
2.2哈夫曼编码步骤
其具体步骤如下：
1.将信源符号按出现概率从大到小排成一列，然后把最末两个符号的概率相加，合成一个概率。
2.把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。
3.重复上述做法，直到最后剩下两个概率为止。
4.从最后一步剩下的两个概率开始逐步向前进行编码。每步只需对两个分支各赋予一个二进制码，如对概率大的赋予码0，对概率小的赋予码1。
例如：假设信源符号为【a、b、c、d、e、f、g】，其出现的概率相应的为【0.25、0.025、0.025、0.05、0.35、0.25、0.05】，一共7个字符，对其进行哈夫曼编码，算法如下：
首先按照每个字符出现的频率大小从左到右排列：0.35、0.25、0.25、0.05、0.05、0.025、0.025；选出最小的两个值作为叶子节点构成一棵二叉树，值较大的叶子节点在左，两个叶子节点对应的频率之和作为根节点。把原排列中最小的两个节点删除，新的根节点插入排列保持大小从左到右的排列顺序不变；重复执行2），直到最后得到值为1 的根节点。得到一棵哈夫曼树，如下图所示：

图 2.1哈夫曼编码树
在得到的哈夫曼树上左分支标记1，右分支标记0，所有的字符根据其频率标记到对应的叶子节点上，从根节点到叶子节点路径上遇到的0、1 字符串即为对应叶子节点所在字符的编码。a、b、c、d、e、f、g七个字符的哈夫曼编码分别是：10、0001、0000、0011、11、01、0010，可以看到,符号只能出现在树叶上,任何一个字符的路径都不会是另一字符路径的前缀路径。
2.3 哈夫曼编码的缺点
哈夫曼编码虽然是最佳编码，但存在一些缺点，具体如下：
（1）对于过短的文件进行编码，意义不大。因为存储哈夫曼树的信息需要一定的存储空间；
（2）利用哈夫曼编码，若用于通信网络，会引起较大的延时；
（3）对较大文件进行编码，会出现频繁的磁盘读写访问，降低了数据编码的速度。

3基于哈夫曼编码的图像编解码系统的程序设计
3.1 分块程序设计分析
（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 序列的哈夫曼编码。部分程序如下：
pad=8-mod（len，8）；
if pad>0；
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，info.length，'uint8'）；%解码
vectorindex=1；
codeindex=1；
code=0；
for index=1:len；
code=bitset（code，codeindex，string（index））；
codeindex=codeindex+1；
byte =info.codetable （bitset （code，codeindex））；
%从码字表中读出对应元素
if byte>0；
vector（vectorindex）=byte-1；
codeindex=1；
code=0；
vectorindex=vectorindex+1；
（5）显示编码的压缩信息（如压缩率、最大码长等），部分程序如下所示：
whos data huffcode huffdecode %显示压缩效果
fprintf（'pad=%d\n'，info.pad）； %info.pad=为凑整字节数，编码字符
串最后添加零的位数
fprintf （'ratio=%f\n'，info.ratio）； %info.ratio=压缩率
fprintf （'maxcodelen=%d\n'，info.maxcodelen）；%info.maxcodelen=最大码长
3.2主程序
系统设计的完整主程序如下
%%%%%%%%%%%%%%%%%%%%%%%%%主程序%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 信息处理课群综合训练与设计--基于哈夫曼编码的图像编解码系统设计及实现
%信息SY1001班--王鸣--0121009320403
clc
clear
cd;
X=imread('watch.bmp');
data=uint8(X);
[zipped,info]=huffencode(data);
unzipped=huffdecode(zipped,info);
subplot(121);imshow(data);title('原始图像')
subplot(122);imshow(unzipped);title('解码后的图像')
whos data unzipped zipped
fprintf('pad=%d\n',info.pad); %info.pad=为凑整字节数，编码字符串最后添加零的位数
fprintf('ratio=%f\n',info.ratio); %info.ratio=压缩率
fprintf('maxcodelen=%d\n',info.maxcodelen);%info.maxcodelen=最大码长
3.3程序函数
3.3.1编码函数
主程序中使用的函数代码如下
%%%%%%%%%%%%%%%%%%%%%%%%%%编码函数%%%%%%%%%%%%%%%%%%%%%%%%%%
% 信息处理课群综合训练与设计--基于哈夫曼编码的图像编解码系统设计及实现
%信息SY1001班--王鸣--0121009320403
%huffencode函数对输入矩阵vector进行huffman编码，返回编码后的向量及相关信息
function [zipped,info]= huffencode(vector)
if ~isa(vector,'uint8')
eror('input argument must be a uint8 vector');
end
[m,n]=size(vector);
vector=vector(:)';
f=frequency(vector);
symbols=find(f~=0);
f=f(symbols);
[f,sortindex]=sort(f);
symbols=symbols(sortindex);
len=length(symbols);
symbols_index=num2cell(1:len);
codeword_tmp=cell(len,1);
while length(f)>1
index1=symbols_index{1};
index2=symbols_index{2};
codeword_tmp(index1)=addnode(codeword_tmp(index1),uint8(0));
codeword_tmp(index2)=addnode(codeword_tmp(index2),uint8(1));
f=[sum(f(1:2)) f(3:end)];
symbols_index=[{[index1,index2]} symbols_index(3:end)];
[f,sortindex]=sort(f);
symbols_index=symbols_index(sortindex);
end
codeword=cell(256,1);
codeword(symbols)=codeword_tmp;
len=0;
for index=1:length(vector)
len=len+length(codeword{double(vector(index))+1});
end
string=repmat(uint8(0),1,len);
pointer=1;
for index=1:length(vector)
code=codeword{double(vector(index))+1};
len=length(code);
string(pointer+(0:len-1))=code;
pointer=pointer+len;
end
len=length(string);
pad=8-mod(len,8);
if pad>0
string=[string uint8(zeros(1,pad))];
end
codeword=codeword(symbols);
codelen=zeros(size(codeword));
weights=2.^(0:23);
maxcodelen=0;
for index=1:length(codeword)
len=length(codeword{index});
if len>maxcodelen
maxcodelen=len;
end
if len>0
code=sum(weights(codeword{index}==1));
code=bitset(code,len+1);
codeword{index}=code;
codelen(index)=len;
end
end
codeword=[codeword{:}];

%计算压缩后的向量
cols=length(string)/8;
string=reshape(string,8,cols);
weights=2.^(0:7);
zipped=uint8(weights*double(string));

%码表存储到一个稀疏矩阵
huffcodes=sparse(1,1);
for index=1:nnz(codeword)
huffcodes(codeword(index),1)=symbols(index);
end

%填写解码时所需的结构信息
info.pad=pad;
info.huffcodes=huffcodes;
info.ratio=cols./length(vector);
info.length=length(vector);
info.maxcodelen=maxcodelen;
info.rows=m;
info.cols=n;
%huffdecode函数对输入矩阵vector进行Huffman编码，
%返回解压后的图像数据
3.3.2解码函数
%%%%%%%%%%%%%%%%%%%%%%%%%%解码函数%%%%%%%%%%%%%%%%%%%%%%%%%
% 信息处理课群综合训练与设计--基于哈夫曼编码的图像编解码系统设计及实现
%信息SY1001班--王鸣--0121009320403
%huffdecode函数对输入矩阵vector进行huffman解码，返回解压后的图像数据
function vector=huffdecode(zipped,info)
if ~isa(zipped,'uint8')
error('input argument must be a uint8 vector');
end

%产生0，1序列，每位占一个字节
len=length(zipped);
string=repmat(uint8(0),1,len.*8);
bitindex=1:8;
for index=1:len
string(bitindex+8.*(index-1))=uint8(bitget(zipped(index),bitindex));
end
string=logical(string(:)');
len=length(string);
string((len-info.pad+1):end)=[];
len=length(string);

%开始解码
weights=2.^(0:51);
vector=repmat(uint8(0),1,info.length);
vectorindex=1;
codeindex=1;
code=0;
for index=1:len
code=bitset(code,codeindex,string(index));
codeindex=codeindex+1;
byte=decode(bitset(code,codeindex),info);
if byte>0
vector(vectorindex)=byte-1;
codeindex=1;
code=0;
vectorindex=vectorindex+1;
end
end
vector=reshape(vector,info.rows,info.cols);
3.3.3符号概率计算函数
%%%%%%%%%%%%%%%%函数frequency计算各符号出现的概率%%%%%%%%%%%%%%%
% 信息处理课群综合训练与设计--基于哈夫曼编码的图像编解码系统设计及实现
%信息SY1001班--王鸣--0121009320403
function f=frequency(vector)
if~isa(vector,'uint8')
error('input argument must be a uint8 vector');
end
f=repmat(0,1,256);
len=length(vector);
for index=0:255
f(index+1)=sum(vector==uint8(index));
end
f=f./len;
3.3.4节点添加函数
%%%%%%%%%%%%%%%%%%%%%%%%%函数addnode添加节点%%%%%%%%%%%%%%%%%%%
% 信息处理课群综合训练与设计--基于哈夫曼编码的图像编解码系统设计及实现
%信息SY1001班--王鸣--0121009320403
function codeword_new=addnode(codeword_old,item)
codeword_new=cell(size(codeword_old));
for index=1:length(codeword_old)
codeword_new{index}=[item codeword_old{index}];
end
3.3.5解码返回符号函数
%%%%%%%%%%%%%%%%%%%%函数decode返回码字对应的符号%%%%%%%%%%%%%
% 信息处理课群综合训练与设计--基于哈夫曼编码的图像编解码系统设计及实现
%信息SY1001班--王鸣--0121009320403
function byte=decode(code,info)
byte=info.huffcodes(code);

4系统仿真结果
4.1程序运行结果
根据设计好的程序加载到MATLAB软件中(即m文件)，运行输出结果。
（1） 选择一幅位图图像（watch.bmp）进行哈夫曼编码压缩编码，得到输出结果如下：
图4-1位图图像压缩编码输出结果1
图4-2位图图像压缩编码输出结果2

（2） 选择一幅jpg图像（王鸣.jpg）进行哈夫曼编码压缩编码，得到输出结果如下：
图4-3jpg图像压缩编码输出结果1
图4-4jpg图像压缩编码输出结果2
4.2 程序运行结果分析
（1）图像压缩、解压缩整个过程大约要花2~3 min，一开始不知道，以为死机，后来稍等会就会出结果；
（2）认真观察原始图像和新图像，比较发现：新旧的位图图像视觉效果相差不大，但是其文件大小却变小了。如watch图像262144bytes减小到233877bytes。压缩率为0.892170。由此可说明，哈夫曼编码是一种无损压缩编码,它不会造成信息损失,解压缩时能够从压缩数据精确地恢复原始图像。
（3）比较两幅不同大小的位图的压缩比可知，对不同的信源，哈夫曼编码的压缩比不同。
（4）后者为jpg彩色图像，有RGB三个分量，所以其输出有三个分量解码输出的图像。

5.总结
通过本次设计，我进一步巩固了哈夫曼压缩编码基本原理及方法，学会了使用MATLAB编写哈夫曼编码程序，并仿真实现基于哈夫曼编码的图像编解码系统；也初步了解图像压缩编码技术的应用和开发，进一步提高编程能力；此外，我对于matlab的有关操作也更加熟悉了。
此外，在这次课程设计中开始调试程序时，解码的图像迟迟不能显示，以为MATLAB软件死机，其实是哈夫曼编码有一定的时间（一般为2-3分钟），这是由于自己的不耐心而导致了这个问题。所以我从中习得不管做什么设计、项目，耐心最重要。当未出结果的时候，我们不能一味的焦躁，而是应该冷静的分析，找出问题的所在。
总之这次设计，我受益匪浅。

参考文献
[1] 冈萨雷斯.数字图像处理[M].北京.电子工业出版社.2005.
[2] 王新成.高级图像处理技术[M].第一版,北京.中国科学技术出版社. 2 0 0 1.
[3] 孙仲康,等.数字图像处理及其应用[M].北京.国防工业出版社.1985.
[4] 董士海,等.图像格式编程指南[M].北京.清华大学出版社, 1994.
[5] Ian H Witten.张仲颖 ,曹文斌 ,曹永革 ,译.海量数据管理-文档和图像的压缩与索引.北京.科学出版社 .1996.
[6] 夏良正. 数字图像处理 [M ]. 南京.东南大学出版社. 2002.
[7] 陈守吉, 张立明. 分形与图像压缩 [M ].上海科技教育出版社. 1998.
[8] 陈衍仪. 图像压缩的分形理论和方法 [ M ].国防工业出版社, 1997.
[9] 王防修, 周康. 通过哈夫曼编码实现文件的压缩与解压 [ J].武汉工业学院学报.2008.

专业综合课程设计成绩评定表
姓 名
王鸣
性 别
男
专业、班级
信息sy1001班
学 号
0121009320403
题 目：基于哈夫曼编码的图像编解码系统设计及实现
答辩或质疑记录：
（1）简述一下哈夫曼编码的原理？
答：哈夫曼编码依据信源数据中各信号出现的频率分配不同长度的编码。即对于出现概率大的信息符号编以短字长的码，对于出现概率小的信息符号编以长字长的码。它是一种无损编码方法。
（2）哈夫曼编码的步骤是什么？
答：1.将信源符号按出现概率从大到小排成一列，然后把最末两个符号的概率相加，合成一个概率。2.把这个符号的概率与其余符号的概率按从大到小排列，然后再把最末两个符号的概率加起来，合成一个概率。 3.重复上述做法，直到最后剩下两个概率为止。4.从最后一步剩下的两个概率开始逐步向前进行编码。每步只需对两个分支各赋予一个二进制码，如对概率大的赋予码0，对概率小的赋予码1。
（3）为什么要进行图像压缩编码？
答：数字图像通常要求很大的比特数，这给图像的传输和存储带来相当大的困难。要占用很多的资源，花很高的费用。一般原始图像中存在很大的冗余度。而图像数据压缩的目的是在满足一定图像质量条件下，用尽可能少的比特数来表示原始图像，以提高图像传输的效率和减少图像存储的容量。
成绩评定依据：

最终评定成绩（以优、良、中、及格、不及格评定）

指导教师签字：
年 月 日