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

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

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

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

4、是在排序过程中两个概率相等，谁前谁后也是随机的。这样编出的码字就不是唯一的。（2）Huffman编码结果，码字不等长，平均码字最短，效率最高，但码字长短不一，实时硬件实现很复杂（特别是译码），而且在抗误码能力方面也比较差。（3）Huffman编码的信源概率是2的负幂时，效率达100%，但是对等概率分布的信源，产生定长码，效率最低，因此编码效率与信源符号概率分布相关，故Huffman编码依赖于信源统计特性，编码前必须有信源这方面的先验知识，这往往限制了霍夫曼编码的应用。（4）Huffman编码只能用近似的整数位来表示单个符号，而不是理想的小数，这也是Huffman编码无法达到最理想的压缩效果的原

5、因假设一个文件中出现了8种符号S0，S1，S2，S3，S4，S5，S6，S7，那么每种符号要编码，至少需要3比特。假设编码成000，001，010，011，100，101，110，111那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成000001111000001110010010011100101000000001，共用了42比特。我们发现S0，S1，S2这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们采用一种编码方案使得S0，S1，S2的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：S0到S7的码字分别01，

6、11，101，0000，0001，0010，0011，100，那么上述符号序列变成011110001110011101101000000010010010111，共用了39比特，尽管有些码字如S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。可由下面的步骤得到霍夫曼码的码表首先把信源中的消息出现的频率从小到大排列。每一次选出频率最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。重复(2)，直到最后得到和为1的根节点。将形成的二叉树的左节点标0，右节点标1。把从最上面的根节点到最下面

7、的叶子节点途中遇到的0，1序列串起来，就得到了各个符号的编码。上面的例子用Huffman编码的过程如图下图所示，其中圆圈中的数字是新节点产生的顺序。Huffman编码的二叉树示意图信源的各个消息从S0到S7的出现概率分别为4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。计算编码效率为98.5%，编码的冗余只有1.5%，可见霍夫曼编码效率很高。产生Huffman编码需要对原始数据扫描两遍。第一遍扫描要精确地统计出原始数据中，每个值出现的频率，第二遍是建立Huffman树并进行编码。由于需要建立二叉树并遍历二叉树生成编码，因此数据压缩和还原速度都较慢，但简单有效，因

8、而得到广泛的应用。三、霍夫曼编码应用本文霍夫曼编码压缩图像的步骤如下：读入图像，并把它用矩阵表示。统计图像颜色的种数。统计各种颜色值出现的概率，并把它们按从大到小的顺序排列。进行霍夫曼编码的计算： 定义一个矩阵M，M矩阵的第一行，存放的是需要编码的各个颜色值出现的概率，并且按照从大到小排列顺序，然后再将第一行从后往前两两相加（即概率最小的两个数相加），把相加得到的结果放到第二行，然后再将第二行重新进行排序，依此类推，一直到最后一行，这时最后一行只有两个概率，并且相加肯定为1 。 对M矩阵的数值进行霍夫曼编码：首先建立N矩阵，用来存放编码的码字。然后将字符0，赋给最后一行的第一小段，再将字符1，

9、赋给最后一行的第二小段，在M矩阵中，由于每一行的最后两个数，都是这一行中概率最小的两个数，所以将倒数第二行的最后两个数进行相加，然后用相加的结果到倒数第一行中去寻找，肯定会在倒数第一行中找到一样的值，然后记录下来在倒数第一行中这个值的位置，再将这个在M矩阵中的位置对应到N矩阵中， 将N矩阵中的该位置的字符赋给倒数第二行的第二小段和第三小段，最后在给第二小段的后面赋字符0，给第三小段后面赋字符1，然后将在最后一行找到的那个数的左边的数，一一对应到上一行去，右边的数，向左串一位，再对应到上一行去，这样依此类推，那么在N矩阵的第一行，可以得到最后的编码。实验程序见附录实验结果如下：压缩效果对比：图像

10、大小比较： 从图中我们可以明显的对比出来，经过了霍夫曼编码压缩图片后，在画质上看不出明显的区别，但是实际上压缩后的图片大小是原来的五分之一，占用空间是原来的三分之一。四、附录%霍夫曼编码实现图像压缩代码：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:61 count=0; for i=1:M for j=1:N if f(i,j)=

11、t-1 count=count+1; end end end p(t)=count;p0=p;endcore=cell(61,1);sign=zeros(61);for hh=1:60 re=M*N; for t=1:61 if (p(t)0) re=p(t); end end t=1; while (p(t)=re)&(t61) t=t+1; end if sign(t,1)=0 coret=0; else coret=0,coret; i=1; while (sign(t,i)=0)&(i61) coresign(t,i)=0,coresign(t,i); i=i+1; end end p

12、(t)=0; cou=t; re1=M*N; for t=1:61 if (p(t)0) re1=p(t); end end t=1; while (p(t)=re1)&(t61) t=t+1; end if sign(t,1)=0 coret=1; else coret=1,coret; i=1; while (sign(t,i)=0)&(i61) coresign(t,i)=1,coresign(t,i); i=i+1; end end p(t)=p(t)+re; cou1=t; i=1; while (sign(t,i)=0)&(i61) i=i+1; end sign(t,i)=cou

13、; i=i+1; j=1; while (sign(cou,j)=0)&(j61) sign(t,i)=sign(cou,j); i=i+1; j=j+1; endend %产生huffman码fc=cell(M,N);for i=1:M for j=1:N if f(i,j)len-1; i=1; j=j+1; else i=i+1; end break; end endendf=uint8(f*4+35);subplot(1,2,2)imshow(f);title(解码后的压缩图像);imwrite(f,压缩图像.jpg);imfinfo(压缩图像.jpg)toc五.总结学习完本门课程之后，是我的知识面有