图像无损压缩程序设计-霍夫曼编码

成绩评定表

学生姓名班级学号1203030119

图像的无损压缩

专业电子信息工程课程设计题目程序设计一一霍

夫曼编码

评

语

组长签字：

成绩

日期2015年7月20日

课程设计任务书

学院信息科学与工程专业电子信息工程

学生姓名班级学号1203030119

课程设计题目图像的无损压缩程序设计一一霍夫曼编码

实践教学要求与任务：

本课题通过MATLAE编写适当的函数，对一个随机信源进行哈夫曼编码，得

出码字，平均码长和编码效率。从而理解信源编码的基本思想与目的以及哈夫

曼编码方法的基本过程与特点，并且提高综合运用所学理论知识独立分析和解

决问题的能力。

工作计划与进度安排：

2015年7月8日—11日：熟悉编程环境，查阅相关资料。

2015年7月11日―12日：图像的霍夫曼编码程序设计。

2015年7月12日一13日：编码、调试、实验与分析。

2015年7月13日一15日：撰写课程设计报告。

2015年7月15日一19日：准备答辩。

指导教师：专业负责人：学院教学副院长：

2015年7月2日2015年7月2日2015年7月2日

摘要

哈夫曼编码（HuffmanCoding）是一种编码方式，以哈夫曼树一即最优二叉树,

带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈

夫曼编码”是一种一致性编码法（又称〃熠编码法〃），用于数据的无损耗压缩。

这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行

编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建

立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的

编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的

目的）。

本课题通过MATLAB编写适当的函数，对一个随机信源进行哈夫曼编码，得出

码字，平均码长和编码效率。从而理解信源编码的基本思想与目的以及哈夫曼编

码方法的基本过程与特点，并且提高综合运用所学埋论知识独立分析和解决问题

的能力。

关键字：哈夫曼；信源编码；MATLAB

目录

1设计目的及相关知识..............................................1

1.1设计目的..................................................1

1.2图像的霍夫曼编码概念......................................1

1.3Matlab图像处理通用函数....................................1

2课程设计分析....................................................3

2.1图像的霍夫曼编码概述.....................................3

2.2图像的霍夫曼编码举例.....................................4

3仿真............................................................5

4结果及分析......................................................8

5附录...........................................................11

结束语...........................................................14

参考文献.........................................................15

1设计目的及相关知识

1.1设计目的

1)了解霍夫曼编码的原理。

2)理解图像的霍夫曼编码原理，了解其应用，掌握图像的霍夫曼编码的方法。

3)对图像编码程序设计进行较深入的认识，对知识牢固掌握。

4)掌握图像霍夫曼编码的整个过程及其中的注意事项。

5)了解图像无损压缩的目的及好处。

1.2图像的霍夫曼编码概念

所谓霍夫曼编码的具体方法：先按出现的概座大小排队，把两个最小的概率

相加，作为新的概率和剩余的概率重新排队，再把最小的两个概率相加，再重新

排队，直到最后变成lo每次相加时都将“0”和“1”赋与相加的两个概率，读

出时由该符号开始一直走到最后的“1”，将路线上所遇到的“0”和“1”按最低

位到最高位的顺序排好，就是该符号的霍夫曼编码

1.3Matlab图像处理通用函数

colorbar显示彩色条

语法：colorbar\coiorbar('vert')\coiorbarChoriz*)\colorbar(h)\h=colorbar(...)\

colorbar(.../peer',axes_handle)

getimage从坐标轴取得图像数据

语:去：A=getimage(h)\|x,y,A]=getimage(h)\[...,A,flag]=getimage(h)\[...]=getimage

imshow显示图像

语法:imshow(I,n)\imshow(I,[lowhigh])\imshow(BW)\imshow(X,map)\

imshow(RGB)\imshow(...,display_option)\imshow(x,y,A,...)\imshowfilename\

h=imshow(...)

montage在矩形框中同时显示多幅图像

语法：montage(I)\montage(BW)\montage(X,map)\montage(RGB)\

h=montage(...)

immovic创建多帧索引图的电影动画

语法：mov=immovie(X,map)\inov=immovie(RGB)

subimage在一副图中显示多个图像

语?去：subimage(X,map)\subimage(I)\subimage(BW)\subimage(RGB)\

subimagc(x,y,...)\subimagc(...)

truesize调整图像显示尺寸

语法：lruesize(fig,|mrowsmcols])\truesize(fig)

warp将图像显示到纹理映射表面

语法：warp(X,map)\warp(l,n)\warp(z,...)warp(x.y,z,...)\h=warp(...)

zoom缩放图像

语法：zoomon\zoomoff\zoomout\zoomreset\zoom\zoomxon\zoomyon\

zoom(factor)\zoom(fig.option)

2课程设计分析

2.1图像的霍夫曼编码概述

赫夫曼（Huffman）编码是1952年提出的，是一种比较经典的信息无损皤编

码，该编码依据变长最佳编码定理，应用Huffman算法而产生。Huffman编码是

一种基于统计的无损编码。

根据变长最佳编倡定理，Huffman编码步骤如下：

（1）将信源符号与按其出现的概率，由大到小顺序排列。

（2）将两个最小的概率的信源符号进行组合相加，并重复这一步骤，始终

将较大的概率分支放在上部，直到只剩下一个信源符号且概率达到1.0为止；

（3）对每对组合的上边一个指定为1,下边一个指定为（）（或相反：对上边

一个指定为0,下边一个指定为1）;

（4）画出由每个信源符号到概率1.0处的路径，记下沿路径的1和0；

（5）对于每个信源符号都写出1、0序列，则从右到左就得到非等长的

Huffman码。

Huffman编码的特点是：

（1）Huffman编码构造程序是明确的，但编出的码不是唯一的，其原因之

一是两个概率分配码字“0”和"1”是任意选择的（大概率为“0”，小概率为“1”，或

者反之）。第二原因是在排序过程中两个概率相等，谁前谁后也是随机的。这样

编出的码字就不是唯•的。

（2）Huffman编码结果，码字不等长，平均码字最短，效率最高，但码字

长短不一，实时硬件实现很复杂（特别是译码），而且在抗误码能力方面也比较

差。

（3）Huffman编码的信源概率是2的负暴时，效率达100%,但是对等概率分

布的信源，产生定长码，效率最低，因此编码效率与信源符号概率分布相关，故

Huffman编码依赖于信源统计特性，编码前必须有信源这方面的先验知识，这往

往限制了霍夫曼编码的应用。

（4）Huffman编码只能用近似的整数位来表示单个符号，而不是理想的小

数，这也是Huffman编码无法达到最理想的压缩效果的原因。

2.2图像的霍夫曼编码举例

假设一个文件中出现了8种符号SO,SI,S2,S3,S4,S5,S6,S7,那么

每种符号要编码,至少需要3比特。假设编码成000,001,010,011,100,101,

110,111那么符号序列SOS1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成

000001111000001110010010011100101000000001,共用了42比特。我们发现S0,

SI,S2这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们

采用一种编码方案使得SO,SI,S2的码字短，其它符号的码字长，这样就能够

减少占用的比特数。例如，我们采用这样的编码方案:S0至”7的码字分另I]01,

11,101,0000,0001,0010,0011,100,那么上述符号序列变成

011110001110011101101000000010010010111,共用了39比特，尽管有些码字如

S3,S4,S5,S6变长了(由3位变成4位)，但使用频繁的几个码字如SO,S1变

短了，所以实现了压缩。

可由下面的步骤得到霍夫塔码的码表

(1)首先把信源中的消息出现的频率从小到大排列。

(2)每一次选出频率最小的两个值，作为二叉树的两个叶子节点，将和作为

它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。

(3)重复(2),直到最后得到和为1的根节点。

(4)将形成的二叉树的左节点标()，右节点标1。把从最上面的根节点到最下

面的叶子节点途中遇到的()，1序列串起来，就得到了各个符号的编码。

上面的例子用Huffman编码的过程如图下图所示，其中圆圈中的数字是新

节点产生的顺序。

6/14⑤

4/14@

2/1402/14②

1/14O1/1401/140

图2-1Huffman编码的二叉树示意图

信源的各个消息从SO到S7的出现概率分别为4/14,3/14,2/14,1/14,1/14,

1/14,1/14,l/14o计算编码效率为98.5%,编码的冗余只有1.5%,可见霍夫曼

编码效率很高。

产生Huffman编码需要对原始数据扫描两遍。第一遍扫描要精确地统计出

原始数据中,每个值出现的频率.第二遍是建立Huffman树并进行编码°由于

需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简

单有效，因而得到广泛的应用。

3仿真

主程序：

%以下为主程序mainp.m

clc

clear

closeall;

%定义HufData/Len为全局变量的结构体

globalHufData;

globalLen

dispc计算机正在准备输出霍夫曼编码结果，请耐心等待……');

%原始码字的灰度

a=imread('kids.tif);

%分区画出原始图像和灰度直方图

figure;

subplot(1,2,1)

imshow(a);

%取消坐标轴和边框

axisoff

boxoff

tit!e('MATLAB自带图豫'fontsize',13);

subplot。,2,2);

axisoff

boxoff

imhist(a);

titleC图像灰度直方图？fontsize：13);

%图像的灰度统计

GrayStatistics=imhist(a);

GrayStatistics-GrayStatistics';

GrayRatioo=GrayStatistics/sum(GrayStatistics);

GrayRatioNO=find(GrayRatioo-=0);

Len=length(GrayRatioNO);

%初始化灰度集，防止系统随即赋予其垃圾值

GrayRatio=ones(1,Len);

fori=l:Lcn

GrayRatio(i)=GrayRatioo(i);

end

GrayRatio=abs(sort(-GrayRatio));

%将图像灰度概率赋予结构体

fori=l:Len

HufData(i).value=GrayRatio(i);

end

%霍夫曼编码/霍夫曼编码

HuffmanCodc(Lcn);

%输出码字

zippcdHuffman=I;

fori=l:Len

tmpData=HufData(i).code;

str=u;

forj=1:length(tmpData)

str=strcat(str,num2str(tmpData(j)));

zippcdHuffman=zippcdHuffman+1;

end

disp(strcat(,a,,num2str(i),-*,str))

end

i；

%计算计算机一共输出多少个霍夫曼编码/霍夫曼编码

zippedHuffman;

%计算在删去0灰度级压缩之前的原始图像字节容量

unzippcd_dclctc_i*8;

%计算压缩比率

ralio_delete=zippedHuffman/unzipped_delete;

%计算图像的压缩比率

ad=num2str(ratio_delete*100);

str2=strcat(ad；%,);

disp(strcat('霍夫曼编码压缩比率',str2))

4结果及分析

结果：

图4-1输出原图像与该图像像灰度直方图

计算机正在准备输出霍夫曼编码结果，请耐心等待….

al=110

a2=11110

a3=11101

a4=01100

a5=01010

a6=01000

a7=00101

a8=00011

a9=llllll

alO=l11001

all=101111

a12=101100

al3=101011

a14=101010

al5=10100l

al6=100111

al7=100110

a18=100100

a19=100011

a20=100010

a21=100001

a22=100000

a23=011111

a24=01I110

a25=011011

a26=011010

a27=010111

a28=010110

a29=010011

a30=001111

a31=001101

a32=001100

a33-001001

a34=001000

a35=000101

a36=000011

a37=000010

a38=00()()()l

a39=000000

a40=1111101

a41=l111100

a42=l110001

a43=1110000

a44=1011101

a45=101110()

a46=1011011

a47=1()10001

a48=101000()

a49=1001011

a50=1001010

a51=0111011

a52=0111010

a53=0111001

a54=0111000

a55=01()()l()l

a56=0I00100

a57=0011101

a58=0011100

a59=0001001

a60=0001000

a61=10110101

a62=101101001

a63=101101000

霍夫曼编码压缩比率-78.9683%

分析：

从输出灰度直方图可得出该图像的量化值主要集中在低灰度级处，通过输出

可以看到该灰度级对应的霍夫曼编码，并且输出了该图像的压缩效率。明显可得

出霍夫曼编码大大的节省了空间，可以明显的减少发送时间。

5附录

子程序：

%子程序：霍夫曼编码/霍夫一曼编码函数HuffmanCodc.m

functionHuffmanCodc(OriginSizc)

globalHufData;

globalLen

fori=l:Len

%%霍夫域编码树左边纪录为1

HufData(i).lcft=l;

%%霍夫曼编码树右边纪录为0

HufData(i).right=O;

%%输出码初始化为0

HufData(i).code=[];

%%排序列表初始化

SortList(i).symbol=i;

SortList(i).value=HufData(i).value;

end

%初始化原始消息数口

newsymbol=OriginSize;

forn=OriginSize:-1:2

%将N个消息进行排序

SortList=sortdata(SortList,n);

%将最后两个出现概率最小的消息合成一个消息

ncwsymbol-ncwsymbol+1;

HufData(newsymbol).value=SortList(n-l).value+SortList(n).value;

HufData(newsymbol).left=SortList(n-1).symbol;

HufData(newsymbol).right=SortList(n).symbol;

%将消息添加到列队的最后，为N-1个消息重新排序作好准备

SortList(n-1).symbol=newsymbol;

SortList(n-1).value=HufData(newsymbol).value;

end

%遍历霍夫曼树，获得霍夫曼编码/霍夫曼编码

visit(newsymbol,Len,[]);

end

%子程序：冒泡排序法函数sortdata.m

functionreData=sortdata(SortList,n)

%根据消息概率进行排序

fork=n:-l:2

forj=l:k-l

min=SortList(j).valuc;

sbl=SortList(j).symbol;

if(min<SortList(j+1).value)

SortList(j).value=SortList(j+l).value;

SortList(j+l).value=min;

SortList(j).symbol=SortList(j+1).symbol;

SortList(j+1).synibol=sbl;

end

end

end

reData=SortList;

end

%子程序：遍历霍夫曼编码/霍夫曼编码树搜索函数visit.m

functionvisit(node,n,ocode)

globalHufData

ifnodc<-n

%如果没有霍夫曼编码/霍夫曼编码树的子接点直接输出原始码，这里为空码([])

HufDala(node).code=ocode;

else

if(HufData(node).left>0)

%遍历左分支接点输出1