数字图像处理(探索霍夫曼编码)

1、探索霍夫曼编码一、绪论在学习完了本学期的数字图像处理课程后，我对图像压缩这部分内容产生了兴趣，通过深入学习，我用matlab 实现了霍夫曼编码，成功地压缩了图像。随着信息时代的来临，多媒体已经被人们广泛的应用于生活的各个领域。我们每天接受的信息开始以Gb 计，众所周知Gb 是一个很大的单位，多媒体是指文字、声音、图形和图像等各种媒体，它能比单纯文字传输更多、更生动的信息，与此同时它的数据量也比文字要大得多，例如一幅分辨率为1024X 768、颜色24位的图像将占到2.3MB的存储空间，1 秒钟没有任何压缩的数字视频图像需要上百兆字节的存储空间，这是目前的存储空间和传输宽带不能承受的。采用数据压

2、缩技术去除不必要的冗余数据以减少所需传输的数据量是必然的选择。 而我正是对如何编码使图像压缩而不至于影响人的体验产生兴趣的。上课时我了解到图像数据存在3 种冗余：结构冗余、统计冗余、以及心里视觉冗余。通过上网搜寻资料我也了解到编码也是分3 种的：统计编码、预测编码，以及变换编码。我主要深入学习了用统计编码的方法来去除统计冗余。:、霍夫曼编码概述赫夫曼（Huffman）编码是1952年提出的，是一种比较经典的信息无损熵编码，该编码依据变长最佳编码定理，应用Huffman 算法而产生。Huffman 编码是一种基于统计的无损编码。根据变长最佳编码定理，Huffman 编码步骤如下：（ 1）将信源符

3、号xi 按其出现的概率，由大到小顺序排列。（ 2）将两个最小的概率的信源符号进行组合相加，并重复这一步骤， 始终将较大的概率分支放在上部，直到只剩下一个信源符号且概率达到1.0为止；（ 3） 对每对组合的上边一个指定为1， 下边一个指定为0（或相反：对上边一个指定为0，下边一个指定为1） ；（ 4） 画出由每个信源符号到概率1.0处的路径，记下沿路径的1和 0；（ 5） 对于每个信源符号都写出1 、 0 序列， 则从右到左就得到非等长的 Huffman 码。Huffman 编码的特点是：（ 1） Huffman 编码构造程序是明确的，但编出的码不是唯一的，其原因之一是两个概率分配码字“0”和“

4、1”是任意选择的（大概率为“ 0”，小概率为“1 ”，或者反之） 。第二原因是在排序过程中两个概率相等，谁前谁后也是随机的。这样编出的码字就不是唯一的。（ 2） Huffman 编码结果，码字不等长，平均码字最短，效率最高，但码字长短不一，实时硬件实现很复杂（特别是译码），而且在抗误码能力方面也比较差。（ 3） Huffman 编码的信源概率是2的负幂时，效率达100%，但是对等概率分布的信源，产生定长码，效率最低，因此编码效率与信源符号概率分布相关，故Huffman 编码依赖于信源统计特性，编码前必须有信源这方面的先验知识，这往往限制了霍夫曼编码的应用。（ 4） Huffman 编码只能用近

5、似的整数位来表示单个符号，而不是理想的小数，这也是Huffman 编码无法达到最理想的压缩效果的原因假设一个文件中出现了8 种符号S0， S1， S2， S3， S4， S5， S6，S7,那么每种符号要编码，至少需要 3比特。假设编码成000, 001, 010 ，011 ，100 ，101 ，110 ，111 那 么 符 号 序 列S0S1S7S0S1S6S2S2S3S4S5S0S0S1 编 码 后 变 成 000001111000001110010010011100101000000001 ， 共用了 42 比特。我们发现S0, S1, S2这三个符号出现的频率比较大，其它符号出现 的频

6、率比较小，如果我们采用一种编码方案使得S0, S1, S2的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：S0至US7的码字分别01,11,101,0000,0001, 0010 ，0011 ，100 ， 那 么 上 述 符 号 序 列 变 成011110001110011101101000000010010010111 ， 共用了 39 比特， 尽 管有些码字如S3， S4， S5， S6 变长了（由 3 位变成 4 位 ），但使用频繁的几个码字如S0， S1 变短了，所以实现了压缩。可由下面的步骤得到霍夫曼码的码表首先把信源中的消息出现的频率从小到大排

7、列。每一次选出频率最小的两个值，作为二叉树的两个叶子节点，将 和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参 与比较。重复(2),直到最后得到和为1的根节点。将形成的二叉树的左节点标 0,右节点标1。把从最上面的根节 点到最下面的叶子节点途中遇到的 0, 1序列串起来，就得到了各个 符号的编码。上面的例子用 Huffman编码的过程如图下图所示，其中圆圈中 的数字是新节点产生的顺序。OQDQ 0001 OD10 001110Q1011101Huffman编码的二叉树示意图信源的各个消息从S0到S7的出现概率分别为4/14 ,3/14 ,2/14 , 1/14, 1/14, 1/1

8、4, 1/14, 1/14。计算编码效率为 98.5% 编码的冗 余只有1.5%可见霍夫曼编码效率很高。产生Huffman编码需要对原始数据扫描两遍。第一遍扫描要精 确地统计出原始数据中，每个值出现的频率，第二遍是建立Huffman树并进行编码。由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有效，因而得到广泛的应用。三、霍夫曼编码应用本文霍夫曼编码压缩图像的步骤如下：读入图像，并把它用矩阵表示。统计图像颜色的种数。统计各种颜色值出现的概率，并把它们按从大到小的顺序排列。进行霍夫曼编码的计算：定义一个矩阵M ， M 矩阵的第一行，存放的是需要编码的各个颜色值出现的概

9、率，并且按照从大到小排列顺序，然后再将第一行从后往前两两相加（即概率最小的两个数相加），把相加得到的结果放到第二行，然后再将第二行重新进行排序，依此类推，一直到最后一行，这时最后一行只有两个概率，并且相加肯定为 1 。对 M 矩阵的数值进行霍夫曼编码：首先建立N 矩阵，用来存放编码的码字。然后将字符0，赋给最后一行的第一小段，再将字符1 ，赋给最后一行的第二小段，在M 矩阵中，由于每一行的最后两个数，都是这一行中概率最小的两个数，所以将倒数第二行的最后两个数进行相加， 然后用相加的结果到倒数第一行中去寻找，肯定会在倒数第一行中找到一样的值，然后记录下来在倒数第一行中这个值的位置，再将这个在M矩

10、阵中的位置对应到 N矩阵中，将N矩阵中的该位置的字符赋给倒数第二行的第二小段和第三小段，最后在给第二小段的后面赋字符 0,给第三小段后面赋字 符1,然后将在最后一行找到的那个数的左边的数，一一对应到上一 行去，右边的数，向左串一位，再对应到上一行去，这样依此类推， 那么在N矩阵的第一行，可以得到最后的编码。实验程序见附录实验结果如下：压缩效果对比：原始图像耐打后的压缩图像图像大小比较:端拉百史除amg如制在彳扼守金豆 皿-I-汪钿I.反唱交冲?S中；=图于TIF 9JK文坤（.Tift*传堂里!.W西E IIF国片室件打开E局2345名图壬足国0.I打开为曲目印恁11王副地）.1 位CMlwi

11、V疣敌惴PfcU监渐告文件关位蚤；CAUmtE无SS格铲南建文件先大小：26.1 Ki 值自 740 TJ占用空同：24.Q KB576用力Ui司生可2艮口 K节（78号聿字向向谢TB1;,22 1503白城时司.2017125223 . 22:liDJflSBTifiJ：K> 1 丁年1标三.订牌:MEX时 aiO17r1?S?2 3 2155:M坊司时用201712223.22il5SM访同时同：2£>睛隼12P?22 R , 22:1幺篦辰*t：口口口旧时高田3检布师 UM西零出），3从图中我们可以明显的对比出来，经过了霍夫曼编码压缩图片 后，在画质上看不出明显的区

12、别，但是实际上压缩后的图片大小是原 来的五分之一，占用空间是原来的三分之一。四、附录派夫曼编码实现图像压缩代码:tic;clearz=imread('原图.jpg ');gray2=rgb2gray(z);f0=gray2;subplot(1,2,1),image(f0);imshow(uint8(f0);title('原始图像');f=abs(f0/4)-10;M,N=size(f);p=zeros(1,61);for t=1:61count=0;for i=1:Mfor j=1:Nif f(i,j)=t-1 count=count+1;endendendp(

13、t)=count;p0=p;endcore=cell(61,1);sign=zeros(61);for hh=1:60re=M*N;for t=1:61if (p(t)<re)&(p(t)>0) re=p(t);endendt=1;while (p(t)=re)&(t<61)t=t+1;endif sign(t,1)=0coret='0'elsecoret='0',coret;i=1;while (sign(t,i)=0)&(i<61)coresign(t,i)='0',coresign(t,i);

14、 i=i+1;endendp(t)=0;cou=t;re1=M*N;for t=1:61if (p(t)<re1)&(p(t)>0) re1=p(t);endendt=1;while (p(t)=re1)&(t<61)t=t+1;endif sign(t,1)=0coret='1'elsecoret='1',coret;i=1;while (sign(t,i)=0)&(i<61)coresign(t,i)='1',coresign(t,i);i=i+1;endendp(t)=p(t)+re;cou1

15、=t;i=1;while (sign(t,i)=0)&(i<61)i=i+1;endsign(t,i)=cou;i=i+1;j=1;while (sign(cou,j)=0)&(j<61)sign(t,i)=sign(cou,j);i=i+1;j=j+1;endend%产生huffman 码fc=cell(M,N);for i=1:Mfor j=1:Nif f(i,j)<61fci,j=coref(i,j)+1;elsefci,j='0'endendend %fcimcore=char();for i=1:Mfor j=1:Nimcore=im

16、core,fci,j;endend%Computing the image sizedisp(' 原始图像');imwrite(f0,' 原图 .tif');imfinfo(' 原图.tif')save picture imcore core; % 保存图片码流和编码对应表tocclear all;load picture.mat %载入图片码流和编码对应表Nc=size(core);Nic=size(imcore);flag=0;i=1;j=1;n=1;cz=char();len = 101;f=zeros(len);for n=1:Nic(2)if flag=0cz=cz,imcore(n);elsecz=imcore(n);flag=0;endfor t=1:Nc(1)if strcmp(cz,coret)f(j,i)=t;flag=1;if i>len-1;i=1;j=j+1;elsei=i+1;endbreak;endendendf=uint8(f*4+35);subplot(1,2,2)imshow(f);title(' 解码后的压缩图像');imwrite(f,' 压缩图像.jpg'