图像霍夫曼编码与压缩

A. 基于霍夫曼编码在MATLAB下 对彩色图像编码压缩和解压~~~

先将彩色图像灰度化，再绘制灰度直方图，接着霍夫曼编码，再解码

B. 利用哈夫曼编码进行压缩压缩率一般达到多少

哈夫曼编码进行压缩的压缩率是根据平均码长来计算的，压缩率比较低。

例如：用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：

4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61

2.61/3=0.87=87%

其平均码长是等长码的87%，所以平均压缩率为13%。

哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。

Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

压缩率，描述压缩文件的效果名，是文件压缩后的大小与压缩前的大小之比，例如：把100m的文件压缩后是90m，压缩率为90/100*100%=90%，压缩率一般是越小越好，但是压得越小，解压时间越长。

(2)图像霍夫曼编码与压缩扩展阅读

哈夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。

每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的哈夫曼编码。

C. 如何计算Huffman编码的编码效率和压缩比

赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。

例如a7从左至右，由U至U″″，其码字为1000；

a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…

用赫夫曼编码所得的平均比特率为：Σ码长×出现概率

上例为：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit

可以算出本例的信源熵为2.61bit，二者已经是很接近了。

哈夫曼编码进行压缩的压缩率是根据平均码长来计算的，压缩率比较低。例如：用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：

4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61

2.61/3=0.87=87%

其平均码长是等长码的87%，所以平均压缩率为13%。

(3)图像霍夫曼编码与压缩扩展阅读：

霍夫曼编码的基本方法先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的霍夫曼码表。编码后的图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。

赫夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就称Huffman编码。下面引证一个定理，该定理保证了按字符出现概率分配码长，可使平均码长最短。

D. 图像压缩原理

1、为什么要对图像数据进行压缩？其压缩原理是什么？
答：（1）数字图像如果不进行压缩，数据量是比较大的，例如一幅分辨率为1024×768的静态真彩色图像，其数据量为1024×768×24=2.25（MB）。这无疑对图像的存储、处理、传送带来很大的困难。事实上，在图像像素之间，无论在行方向还是列方向，都存在一定的相关性。也就是说，在一般图像中都存在很大的相关性，即冗余度。静态图像数据的冗余包括：空间冗余、时间冗余、结构冗余、知识冗余和视觉冗余、图像区域的相同性冗余、纹理的统计冗余等。图像压缩编码技术就是利用图像数据固有的冗余性和相干性，将一个大的图像数据文件转换为较小的同性质的文件。
（2）其压缩原理: 空间冗余、时间冗余、结构冗余、和视觉冗余。
2、图像压缩编码的目的是什么？目前有哪些编码方法？
答：（1）视频经过数字化处理后易于加密、抗干扰能力强、可再生中继等诸多优点，但是由于数字化的视频数据量十分巨大，不利于传输和存储。若不经压缩，数字视频传输所需的高传输率和数字视频存储所需的巨大容量，将成为推广数字电视视频通信的最大障碍，这就是进行视频压缩编码的目的。
（2）目前主要是预测编码，变换编码，和统计编码三种编码方法。
3、某信号源共有7个符号，概率分别为0.2,0.18,0.1,0.15,0.07,0.05,0.25,试进行霍夫曼编码，并解释是否进行了压缩，压缩比为多少？

0000 0001 000 00 111 110 10
0.05 0.07 0.1 0.2 0.18 0.15 0.25
0.05×4＋0.07×4＋0.1×3＋0.2×2＋0.18×3＋0.15×3＋0.25×2=2.67

E. Huffman编码不适合图像压缩么，为什么。有相关的资料么。能给我看看不QQ504278770

下面是我从网上搜索到的资料，希望对你有帮助。

1.哈夫曼图像压缩算法引言

随着网络与多媒体技术的兴起，人们需要存储和传输的数据越来越多，数据量越来越大，以前带宽有限的传输网络和容量有限的存储介质难以满足用户的需求。

特别是声音、图像和视频等媒体在人们的日常生活和工作中的地位日益突出，这个问题越发显得严重和迫切。如今，数据压缩技术早已是多媒体领域中的关键技术之一。

Huffman(哈夫曼)算法在上世纪五十年代初提出来了，它是一种无损压缩方法，在压缩过程中不会丢失信息熵，而且可以证明Huffman算法在无损压缩算法中是最优的。Huffman原理简单，实现起来也不困难，在现在的主流压缩软件得到了广泛的应用。对应用程序、重要资料等绝对不允许信息丢失的压缩场合，Huffman算法是非常好的选择。

2.哈夫曼图像压缩算法原理

Huffman编码是1952年由Huffman提出的对统计独立信源能达到最小平均码长的编码方法。这一年，他发表了着名论文“A Method for the Construction of Minimum Rendancy Codes”，即最短冗余码的构造方法.之后，Huffman编码及其一些改进方法一直是数据压缩领域的研究热点之一。

Huffman码是一种变长码，其基本思想是：先统计图像(已经数字化)中各灰度出现的概率，出现概率较大的赋以较短的码字，而出现概率较小的则赋以较长的码字。我们可以用下面的框图来表示Huffman编码的过程：

在整个编码过程中，统计图像各灰度级出现的概率和编码这两步都很简单，关键的是Huffman树的构造。不但编码的时候需要用到这颗树，解码的时候也必须有这颗树才能完成解码工作，因此，Huffman树还得完整的传输到解码端。

Huffman树的构造可以按照下面图2的流程图来完成。首先对统计出来的概率从小到大进行排序，然后将最小的两个概率相加;到这儿的时候，先把已经加过的两个概率作为树的两个节点，并把他们从概率队列中删除;然后把相加所得的新概率加入到队列中，对这个新队列进行排序。

如此反复，直到最后两个概率相加为1的时候停止。这样，Huffman树就建立起来了。

3. 哈夫曼图像压缩算法软件实现

这儿，我们以Turbo C为例来说明软件实现Huffman图像压缩算法的一些关键技术。

为了叙述方便，我们不妨假设处理的图像的灰度级变化范围从0到255，即具有256个灰度级。我们先来统计输入图像的概率，实际上是要统计各个灰度级在整幅图像中出现的次数。为此，我们先定义一个具有256个元素的数组。

然后对输入图像信号进行扫描，每出现一个灰度，就把它存入实现定义好的一个数组中的相应元素中(让这个元素的值自增1)。最后，通过读取数组中各元素的值就可以求出各个灰度出现的频数。

接下来就该构造Huffman树了。为了构造Huffman树，我们要用到C语言中链表的概念。我们必须用一个结构体来表示Huffman树的节点。对于每个节点而言我们需要这样几个信息：本节点的权重(就是灰度的频数)、指向父节点的指针和分别指向左右子叶节点的指针。于是，我们可以定义这样一个结构体：

Struct Node{

Floatweight;

Node * father;

Node * left;

Node * right;}Huffman_Node

我们需要先确定权最低的两个自由结点，这将是最初的left和right节点。然后建立这两个结点的父结点，并让它的权等于这两个结点的权之和。

接着将这个父结点增加到自由结点的序列中，而两个子结点则从序列中去掉。重复前面的步骤直到只剩下一个自由结点，这个自由结点就是Huffman树的根。

Huffman编码树作为一个二叉树从叶结点逐步向上建立。Huffman树建立好以后，为了把权、概率等数值转化码字，我们还得对整个Huffman树进行扫描。请注意，在建立Huffman树的时候，我们是从树叶开始的，而在对Huffman树分配码字的时候却刚好相反，是从树根开始，沿着各个树枝的走向“顺藤摸瓜”似的对各个系数进行编码。

对于一个节点的两个子节点(left和right)，其中一个节点对应的位为0，而另一个结点则人为地设置成为l。解码的时候也是完全相同的一颗Huffman树完成的。下面的循环是实现压缩的关键语句之一[ 1 ]。

for (i = length-1; i >= 0; ――i) {

if ((current_code >> i) & 1)

thebyte |= (char) (1 << curbit);

if (--curbit < 0) {

putc (thebyte, ofile);

thebyte = 0;

curbyte++;

curbit = 7;

}

}

注意：这几行代码执行了数据压缩的功能，但是还没有生成编码和解码所需要的代码表。

4.哈夫曼图像压缩算法性能评价

我们主要从三方面[ 2 ]来评价Huffman的性能：

(1)压缩比的大小;

(2)恢复效果的好坏，也就是能否尽可能的恢复原始数据;

(3)算法的简单易用性以及编、解码的速度。

首先分析一下对压缩比的影响因素(不同的着作中对压缩比的定义不尽相同，这儿我们采用如下定义：压缩比等于压缩之前的以比特计算的数据量比上压缩之后的数据量)。对于Huffman编码来说，我们因为要用额外的位保存和传输Huffman树而“浪费”掉一些存储位，也就是说，为了编、解码的方便，我们把本已减少的数据量又增加了一些。

如果文件比较大的话，这一点多余的数据根本算不了什么，所占比例很小。但是，如果压缩的文件本来就很小的话，那么这笔数据就很可观了。一般来说，经典的Huffman算法的压缩比不是很高，这是无损压缩的“通病”。

第二点就不用说了，由于它是无损压缩，能够完全恢复压缩之前图像的本来面貌。

最后，让我们来分析一下Huffman压缩方法的速度问题。大家在第三节中已经看到了，在压缩的过程中，我们进行了两次扫描，第一次是为了统计各个灰度出现的频数而扫描整幅图像，第二次则是为了分配码字而扫描整个Huffman树。

这样一来，对较大的文件进行编码时，频繁的磁盘读写访问必然会降低数据编码的速度，如果用于网络的话，还会因此带来一些延时，不利于实时压缩和传输。另外，Huffman算法的编码和解码的速度是不对称的，解码快于编码，因为解码不需要生成Huffman树的环节。

5.图像压缩算法结束语

Huffman算法目前已经得到了广泛的应用，软件和硬件都已经实现。基于Huffman经典算法的缺陷，不少人提出了一些自适应算法。前面的算法中，Huffman树是整个图像全部输入扫描完成后构造出来的，而自适应算法(或称动态算法)则不必等到全部图像输入完成才开始树的构造，并且可以根据后面输入的数据动态的对Huffman树进行调整。实际上，实用的Huffman树都是经过某种优化后的动态算法。

网络资源

F. 哈夫曼编码进行图像压缩

% 演示图象的哈夫曼编解码过程
% chenyong 2009.04.20

clear all;
close all;
clc;
Dimens = 256; % 矩阵维数，假设矩阵为方阵即256*256
src_size = Dimens^2; % 矩阵元素的个数
gray_level = 9; % 灰度级

src = randn(Dimens); %产生模拟图像矩阵，满足正态分布，零均值，方差为1
%src = randint(Dimens,Dimens,gray_level); % 产生随机图像矩阵，灰度值为0~63，满足均匀分布
src_one = reshape(src,1,src_size);
src_max = max(src_one);
src_min = min(src_one);
quan = linspace(src_min,src_max,gray_level); % 产生均匀量化区间
src_d = []; % 数字矩阵
for row = 1:Dimens % 逐点量化
for vol = 1:Dimens
diff = abs(src(row,vol)-quan);
[min_diff,min_index] = min(diff);
quan_gray = min_index -1;
src_d(row,vol) = quan_gray;
end
end

%将数字图像矩阵还原成模拟矩阵
src_a = [];
quan_space = quan(2)-quan(1);
for row = 1:Dimens
for vol = 1:Dimens
src_a(row,vol) = src_d(row,vol) * quan_space + src_min;
end
end

% prob数组保存图像中各灰度出现的概率
prob = [];
for src_value=0:(gray_level-1)
index = find(src_d==src_value);
i = src_value + 1;
prob(i) = length(index)/src_size;
end

% 画出直方图
% stem(0:gray_level-1,prob);
% xlabel('灰度值');
% ylabel('概率');
% title('灰度直方图');

% huffman编码
p = prob;
n=length(p);
q=p;
m=zeros(n-1,n);
for i=1:n-1
[q,l]=sort(q);
m(i,:)=[l(1:n-i+1),zeros(1,i-1)];
q=[q(1)+q(2),q(3:n),1];
end
bre=zeros(n-1,n);
bre(n-1,1)=0+j; %虚部表示当前的二进制数的位数，以下类似
bre(n-1,2)=1+j;
for time=1:n-2
loc_1 = find(real(m(n-time,:))==1);
prebit = bre(n-time,loc_1);
bre(n-time-1,1) = (real(prebit)*2 + 0) + j*(imag(prebit)+1);
bre(n-time-1,2) = (real(prebit)*2 + 1) + j*(imag(prebit)+1);

loc_not1 = find(real(m(n-time,:))>1);
bre(n-time-1,3:3+time-1) = bre(n-time,loc_not1);
end
[m1,index] = sort(m(1,:));
code = bre(1,index);
code_data = real(code);
code_bits = imag(code);
disp(['gray level',' ', 'huffman code']);
for i = 1:length(code)
disp([num2str(i-1),' ' ,num2str(dec2bin(code_data(i)))]);
disp([num2str(i-1),' ' ,num2str(dec2bin(code_data(i),code_bits(i)))]);
end
code_binary = dec2bin(code_data);

%逐点编码
out = [];
for row = 1:Dimens
for vol = 1:Dimens
now_gray = src_d(row,vol);
now_code = code_binary(now_gray+1,:);
now_bits = code_bits(now_gray+1);
now_code = now_code(end-now_bits+1:end);
out = [out, now_code];
end
end

%计算压缩比
real_bitnum = length(out);
bitnum_no_huffman = src_size*nextpow2(gray_level);
comp_ratio =bitnum_no_huffman/real_bitnum;
Lavg = real_bitnum/src_size;
Hshannon = (-1)*prob*(log2(prob))';
disp(['Lavg = ',num2str(Lavg)]);
disp(['normal bit num = ',num2str(nextpow2(gray_level))]);
disp(['comp_ratio = ',num2str(comp_ratio)]);
disp(['Hshannon = ',num2str(Hshannon)]);

G. 跪求哈夫曼编码压缩与其它压缩算法的比较（复杂性和压缩效果）

（1）所形成的Huffman编码的码字是不是唯一的，但是可以被指定为唯一的编码效率为“1”大，小的是“0”时，两个最小概率符号赋值。反之也可以。如果两个符号的发生的概率是相等的，排列无论前面是可能的，所以霍夫曼码字的结构不是唯一的，对于相同的信息源，不管如何在上述的顺序安排的，它的平均码字长度是不改变，因此，编码效率是独一无二的。
（2）只有当不均匀时，每个符号的信息源的发生的概率，霍夫曼编码的效果是唯一明显的。
（3）霍夫曼编码必须是精确的原始文件中的各符号的发生频率的统计数据，并且如果没有准确的统计数据，压缩将低于预期。 Huffman编码通常必须经过两道，第一遍统计的第二次产生编码，编码速度是比较慢的。电路的复杂性的另一种实现的各种长度的编码，解码处理是相对复杂的，因此，解压缩处理是相对缓慢。
（4）Huffman编码只能使用整数来表示一个符号，而不是使用小数，这在很大程度上限制了压缩效果。
（5）霍夫曼是所有的位，如果改变其中一个可以使数据看起来完全不同

H. 如何用哈夫曼编码对图像进行压缩

% 演示图象的哈夫曼编解码过程
% chenyong 2009.04.20

clear all;
close all;
clc;
Dimens = 256; % 矩阵维数，假设矩阵为方阵即256*256
src_size = Dimens^2; % 矩阵元素的个数
gray_level = 9; % 灰度级

src = randn(Dimens); %产生模拟图像矩阵，满足正态分布，零均值，方差为1
%src = randint(Dimens,Dimens,gray_level); % 产生随机图像矩阵，灰度值为0~63，满足均匀分布
src_one = reshape(src,1,src_size);
src_max = max(src_one);
src_min = min(src_one);
quan = linspace(src_min,src_max,gray_level); % 产生均匀量化区间
src_d = []; % 数字矩阵
for row = 1:Dimens % 逐点量化
for vol = 1:Dimens
diff = abs(src(row,vol)-quan);
[min_diff,min_index] = min(diff);
quan_gray = min_index -1;
src_d(row,vol) = quan_gray;
end
end

%将数字图像矩阵还原成模拟矩阵
src_a = [];
quan_space = quan(2)-quan(1);
for row = 1:Dimens
for vol = 1:Dimens
src_a(row,vol) = src_d(row,vol) * quan_space + src_min;
end
end

% prob数组保存图像中各灰度出现的概率
prob = [];
for src_value=0:(gray_level-1)
index = find(src_d==src_value);
i = src_value + 1;
prob(i) = length(index)/src_size;
end

% 画出直方图
% stem(0:gray_level-1,prob);
% xlabel('灰度值');
% ylabel('概率');
% title('灰度直方图');

% huffman编码
p = prob;
n=length(p);
q=p;
m=zeros(n-1,n);
for i=1:n-1
[q,l]=sort(q);
m(i,:)=[l(1:n-i+1),zeros(1,i-1)];
q=[q(1)+q(2),q(3:n),1];
end
bre=zeros(n-1,n);
bre(n-1,1)=0+j; %虚部表示当前的二进制数的位数，以下类似
bre(n-1,2)=1+j;
for time=1:n-2
loc_1 = find(real(m(n-time,:))==1);
prebit = bre(n-time,loc_1);
bre(n-time-1,1) = (real(prebit)*2 + 0) + j*(imag(prebit)+1);
bre(n-time-1,2) = (real(prebit)*2 + 1) + j*(imag(prebit)+1);

loc_not1 = find(real(m(n-time,:))>1);
bre(n-time-1,3:3+time-1) = bre(n-time,loc_not1);
end
[m1,index] = sort(m(1,:));
code = bre(1,index);
code_data = real(code);
code_bits = imag(code);
disp(['gray level',' ', 'huffman code']);
for i = 1:length(code)
disp([num2str(i-1),' ' ,num2str(dec2bin(code_data(i)))]);
disp([num2str(i-1),' ' ,num2str(dec2bin(code_data(i),code_bits(i)))]);
end
code_binary = dec2bin(code_data);

%逐点编码
out = [];
for row = 1:Dimens
for vol = 1:Dimens
now_gray = src_d(row,vol);
now_code = code_binary(now_gray+1,:);
now_bits = code_bits(now_gray+1);
now_code = now_code(end-now_bits+1:end);
out = [out, now_code];
end
end

%计算压缩比
real_bitnum = length(out);
bitnum_no_huffman = src_size*nextpow2(gray_level);
comp_ratio =bitnum_no_huffman/real_bitnum;
Lavg = real_bitnum/src_size;
Hshannon = (-1)*prob*(log2(prob))';
disp(['Lavg = ',num2str(Lavg)]);
disp(['normal bit num = ',num2str(nextpow2(gray_level))]);
disp(['comp_ratio = ',num2str(comp_ratio)]);
disp(['Hshannon = ',num2str(Hshannon)]);

I. “RLE适用于图形压缩，霍夫曼编码适用于文本压缩”这句话对吗

错误，RLE适用于文本和图像