圖像霍夫曼編碼與壓縮

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適用於文本和圖像