霍夫曼編碼圖像壓縮

『壹』 如何計算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%。

(1)霍夫曼編碼圖像壓縮擴展閱讀：

霍夫曼編碼的基本方法先對圖像數據掃描一遍，計算出各種像素出現的概率，按概率的大小指定不同長度的唯一碼字，由此得到一張該圖像的霍夫曼碼表。編碼後的圖像數據記錄的是每個像素的碼字，而碼字與實際像素值的對應關系記錄在碼表中。

赫夫曼編碼是可變字長編碼(VLC)的一種。 Huffman於1952年提出一種編碼方法，該方法完全依據字元出現概率來構造異字頭的平均長 度最短的碼字，有時稱之為最佳編碼，一般就稱Huffman編碼。下面引證一個定理，該定理保證了按字元出現概率分配碼長，可使平均碼長最短。

『貳』 對圖像進行霍夫曼編碼壓縮後如何輸出壓縮後圖像

壓縮後的圖像就是哈夫曼編碼後的01比特流

『叄』 「RLE適用於圖形壓縮，霍夫曼編碼適用於文本壓縮」這句話對嗎

錯誤，RLE適用於文本和圖像

『肆』 對灰度圖像進行霍夫曼編碼，用Matlab怎麼操作

給你一段程序,自己研究下吧!

clc
clear
close all;
%定義HufData/Len為全局變數的結構體
global HufData;
global Len
disp('計算機正在准備輸出哈夫曼編碼結果,請耐心等待……');
%原始碼字的灰度
a=imread('kids.tif');

%分區畫出原始圖像和灰度直方圖
figure;
subplot(1,2,1)
imshow(a);
%取消坐標軸和邊框
axis off
box off
title('MATLAB自帶圖像','fontsize',13);
subplot(1,2,2);
axis off
box off
imhist(a);
title('圖像灰度直方圖','fontsize',13);
%圖像的灰度統計
GrayStatistics=imhist(a);
GrayStatistics=GrayStatistics';
GrayRatioo=GrayStatistics/sum(GrayStatistics);
GrayRatioNO=find(GrayRatioo~=0);
Len=length(GrayRatioNO);
%初始化灰度集，防止系統隨即賦予其垃圾值
GrayRatio=ones(1,Len);

for i=1:Len
GrayRatio(i)=GrayRatioo(i);
end

GrayRatio=abs(sort(-GrayRatio));
%將圖像灰度概率賦予結構體
for i=1:Len
HufData(i).value=GrayRatio(i);
end

% 哈夫曼編碼/霍夫曼編碼
HuffmanCode(Len);
%輸出碼字

zippedHuffman=1;
for i=1:Len
tmpData=HufData(i).code;
str='';
for j=1:length(tmpData)
str=strcat(str,num2str(tmpData(j)));
zippedHuffman=zippedHuffman+1;
end
disp(strcat('a',num2str(i),'= ',str))
end
i;
%計算計算機一共輸出多少個哈夫曼編碼/霍夫曼編碼
zippedHuffman;
%計算在刪去0灰度級壓縮之前的原始圖像位元組容量
unzipped_delete=i*8;

%計算壓縮比率
ratio_delete=zippedHuffman/unzipped_delete;

%計算圖像的壓縮比率
ad=num2str(ratio_delete*100);
str2=strcat(ad,'%');
disp(strcat('哈夫曼編碼壓縮比率','= ',str2))

%子程序：哈夫曼編碼/霍夫曼編碼函數HuffmanCode.m
function HuffmanCode(OriginSize)
global HufData;
global Len
for i=1:Len
%%霍夫曼編碼樹左邊紀錄為1
HufData(i).left=1;
%%霍夫曼編碼樹右邊紀錄為0
HufData(i).right=0;
%%輸出碼初始化為0
HufData(i).code=[];
%%排序列表初始化
SortList(i).symbol=i;
SortList(i).value=HufData(i).value;
end
%初始化原始消息數目
newsymbol=OriginSize;
for n=OriginSize:-1:2
%將N個消息進行排序
SortList=sortdata(SortList,n);
%將最後兩個出現概率最小的消息合成一個消息
newsymbol=newsymbol+1;
HufData(newsymbol).value=SortList(n-1).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
function reData=sortdata(SortList,n)
%根據消息概率進行排序
for k=n:-1:2
for j=1:k-1
min=SortList(j).value;
sbl=SortList(j).symbol;
if(min<SortList(j+1).value)
SortList(j).value=SortList(j+1).value;
SortList(j+1).value=min;
SortList(j).symbol=SortList(j+1).symbol;
SortList(j+1).symbol=sbl;
end
end
end
reData=SortList;
end

%子程序：遍歷哈夫曼編碼/霍夫曼編碼樹搜索函數visit.m
function visit(node,n,ocode)
global HufData
if node<=n
%如果沒有哈夫曼編碼/霍夫曼編碼樹的子接點直接輸出原始碼，這里為空碼（[]）
HufData(node).code=ocode;
else
if(HufData(node).left>0)
%遍歷左分支接點輸出1，這里採用子函數嵌套調用
ocode1=[ocode 1];
visit(HufData(node).left,n,ocode1);
end
if(HufData(node).right>0)
%遍歷右分支接點輸出0，這里採用子函數嵌套調用
ocode2=[ocode 0];
visit(HufData(node).right,n,ocode2);
end
end
end

『伍』 圖像壓縮原理

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

『陸』 jpeg圖片壓縮的原理（談談怎麼個壓縮法怎麼個有損法）

JPEG壓縮過程

JPEG壓縮分四個步驟實現：
1.顏色模式轉換及采樣；
2.DCT變換；
3.量化；
4.編碼。
二.
1．顏色模式轉換及采樣 RGB色彩系統是我們最常用的表示顏色的方式。JPEG採用的是YCbCr色彩系統。想要用JPEG基本壓縮法處理全彩色圖像，得先把RGB顏色模式圖像數據，轉換為YCbCr顏色模式的數據。Y代表亮度，Cb和Cr則代表色度、飽和度。通過下列計算公式可完成數據轉換。 Y=0.2990R+0.5870G+0.1140B Cb=-0.1687R-0.3313G+0.5000B+128 Cr=0.5000R-0.4187G-0.0813B＋128 人類的眼晴對低頻的數據比對高頻的數據具有更高的敏感度，事實上，人類的眼睛對亮度的改變也比對色彩的改變要敏感得多，也就是說Y成份的數據是比較重要的。既然Cb成份和Cr成份的數據比較相對不重要，就可以只取部分數據來處理。以增加壓縮的比例。JPEG通常有兩種采樣方式：YUV411和YUV422，它們所代表的意義是Y、Cb和Cr三個成份的數據取樣比例。
2.DCT變換 DCT變換的全稱是離散餘弦變換(Discrete Cosine Transform)，是指將一組光強數據轉換成頻率數據，以便得知強度變化的情形。若對高頻的數據做些修飾，再轉回原來形式的數據時，顯然與原始數據有些差異，但是人類的眼睛卻是不容易辨認出來。 壓縮時，將原始圖像數據分成8*8數據單元矩陣，例如亮度值的第一個矩陣內容如下：
JPEG將整個亮度矩陣與色度Cb矩陣，飽和度Cr矩陣，視為一個基本單元稱作MCU。每個MCU所包含的矩陣數量不得超過10個。例如，行和列采樣的比例皆為4:2:2，則每個MCU將包含四個亮度矩陣，一個色度矩陣及一個飽和度矩陣。 當圖像數據分成一個8*8矩陣後，還必須將每個數值減去128，然後一一代入DCT變換公式中，即可達到DCT變換的目的。圖像數據值必須減去128，是因為DCT轉換公式所接受的數字范圍是在-128到+127之間。 DCT變換公式：
x,y代表圖像數據矩陣內某個數值的坐標位置f(x,y)代表圖像數據矩陣內的數個數值u,v代表DCT變換後矩陣內某個數值的坐標位置F(u,v)代表DCT變換後矩陣內的某個數值 u=0 且 v=0 c(u)c(v)=1/1.414 u>0 或 v>0 c(u)c(v)=1 經過DCT變換後的矩陣數據自然數為頻率系數，這些系數以F（0，0）的值最大，稱為DC，其餘的63個頻率系數則多半是一些接近於0的正負浮點數，一概稱之為AC。
3、量化 圖像數據轉換為頻率系數後，還得接受一項量化程序，才能進入編碼階段。量化階段需要兩個8*8矩陣數據，一個是專門處理亮度的頻率系數，另一個則是針對色度的頻率系數，將頻率系數除以量化矩陣的值，取得與商數最近的整數，即完成量化。 當頻率系數經過量化後，將頻率系數由浮點數轉變為整數，這才便於執行最後的編碼。不過，經過量化階段後，所有數據只保留整數近似值，也就再度損失了一些數據內容，JPEG提供的量化表如下：

4、編碼 Huffman編碼無專利權問題，成為JPEG最常用的編碼方式，Huffman編碼通常是以完整的MCU來進行的。 編碼時，每個矩陣數據的DC值與63個AC值，將分別使用不同的Huffman編碼表，而亮度與色度也需要不同的Huffman編碼表，所以一共需要四個編碼表，才能順利地完成JPEG編碼工作。 DC編碼 DC是彩採用差值脈沖編碼調制的差值編碼法，也就是在同一個圖像分量中取得每個DC值與前一個DC值的差值來編碼。DC採用差值脈沖編碼的主要原因是由於在連續色調的圖像中，其差值多半比原值小，對差值進行編碼所需的位數，會比對原值進行編碼所需的位數少許多。例如差值為5，它的二進製表示值為101，如果差值為-5，則先改為正整數5，再將其二進制轉換成1的補數即可。所謂1的補數，就是將每個Bit若值為0，便改成1；Bit為1，則變成0。差值5應保留的位數為3，下表即列出差值所應保留的Bit數與差值內容的對照。
在差值前端另外加入一些差值的霍夫曼碼值，例如亮度差值為5（101）的位數為3，則霍夫曼碼值應該是100，兩者連接在一起即為100101。下列兩份表格分別是亮度和色度DC差值的編碼表。根據這兩份表格內容，即可為DC差值加上霍夫曼碼值，完成DC的編碼工作。
AC編碼 AC編碼方式與DC略有不同，在AC編碼之前，首先得將63個AC值按Zig-zag排序，即按照下圖箭頭所指示的順序串聯起來。
63個AC值排列好的，將AC系數轉換成中間符號，中間符號表示為RRRR/SSSS，RRRR是指第非零的AC之前，其值為0的AC個數，SSSS是指AC值所需的位數，AC系數的范圍與SSSS的對應關系與DC差值Bits數與差值內容對照表相似。 如果連續為0的AC個數大於15，則用15/0來表示連續的16個0，15/0稱為ZRL（Zero Rum Length），而（0/0）稱為EOB（Enel of Block）用來表示其後所剩餘的AC系數皆等於0，以中間符號值作為索引值，從相應的AC編碼表中找出適當的霍夫曼碼值，再與AC值相連即可。 例如某一組亮度的中間符為5/3，AC值為4，首先以5/3為索引值，從亮度AC的Huffman編碼表中找到1111111110011110霍夫曼碼值，於是加上原來100（4）即是用來取[5，4]的Huffman編碼1111111110011110100，[5，4]表示AC值為4的前面有5個零。 由於亮度AC，色度AC霍夫曼編碼表比較長，在此省略去，有興趣者可參閱相關書籍。 實現上述四個步驟，即完成一幅圖像的JPEG壓縮。 參考資料[1] 林福宗 《圖像文件格式（上）——Windows 編程》，清華大學出版社， 1996年[2] 李振輝、李仁各編著，《探索圖像文件的奧秘》，清華大學出版社，1996年[3] 黎洪松、成實譯《JPEG靜止數據壓縮標准》，學苑出版社，1996年

希望有點幫助
參考資料：http://www.daima.com.cn/Info/94/Info31445/

『柒』 一些圖像轉換軟體 「優化霍夫曼編碼」什麼意思

是一種編碼技術
哈夫曼編碼(Huffman Coding)是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。 Huffman於1952年提出一種編碼方法，該方法完全依據字元出現概率來構造異字頭的平均長 度最短的碼字，有時稱之為最佳編碼，一般就叫作Huffman編碼。 以哈夫曼樹—即最優二叉樹，帶權路徑長度最小的二叉樹，經常應用於數據壓縮。 在計算機信息處理中，「哈夫曼編碼」是一種一致性編碼法（又稱"熵編碼法"），用於數據的無損耗壓縮。這一術語是指使用一張特殊的編碼表將源字元（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在於，它是根據每一個源字元出現的估算概率而建立起來的（出現概率高的字元使用較短的編碼，反之出現概率低的則使用較長的編碼，這便使編碼之後的字元串的平均期望長度降低，從而達到無損壓縮數據的目的）。這種方法是由David.A.Huffman發展起來的。 例如，在英文中，e的出現概率很高，而z的出現概率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位(bit)來表示，而z則可能花去25個位（不是26）。用普通的表示方法時，每個英文字母均佔用一個位元組（byte），即8個位。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現對於英文中各個字母出現概率的較准確的估算，就可以大幅度提高無損壓縮的比例。

『捌』 現今的圖像壓縮演算法有哪些急...

淺談圖像壓縮演算法

余科亮

本文僅討論靜止圖像的壓縮基本演算法，圖像壓縮的目的在於以較少的數據來
表示圖像以節約存儲費用，或者傳輸時間和費用。
JPEG壓縮演算法可以用失真的壓縮方式來處理圖像，但失真的程度卻是肉眼所
無法辯認的。這也就是為什麼JPEG會有如此滿意的壓縮比例的原因。
下面主要討論，JPEG基本壓縮法。
一.JPEG壓縮過程

JPEG壓縮分四個步驟實現：
1.顏色模式轉換及采樣；
2.DCT變換；
3.量化；
4.編碼。

二.1．顏色模式轉換及采樣

RGB色彩系統是我們最常用的表示顏色的方式。JPEG採用的是YCbCr色彩系統。
想要用JPEG基本壓縮法處理全彩色圖像，得先把RGB顏色模式圖像數據，轉換為
YCbCr顏色模式的數據。Y代表亮度，Cb和Cr則代表色度、飽和度。通過下列計算
公式可完成數據轉換。
Y=0.2990R+0.5870G+0.1140B
Cb=-0.1687R-0.3313G+0.5000B+128
Cr=0.5000R-0.4187G-0.0813B＋128
人類的眼晴對低頻的數據比對高頻的數據具有更高的敏感度，事實上，人類
的眼睛對亮度的改變也比對色彩的改變要敏感得多，也就是說Y成份的數據是比較
重要的。既然Cb成份和Cr成份的數據比較相對不重要，就可以只取部分數據來處
理。以增加壓縮的比例。JPEG通常有兩種采樣方式：YUV411和YUV422，它們所代
表的意義是Y、Cb和Cr三個成份的數據取樣比例。

2.DCT變換

DCT變換的全稱是離散餘弦變換(Discrete Cosine Transform)，是指將一組
光強數據轉換成頻率數據，以便得知強度變化的情形。若對高頻的數據做些修飾，
再轉回原來形式的數據時，顯然與原始數據有些差異，但是人類的眼睛卻是不容
易辨認出來。
壓縮時，將原始圖像數據分成8*8數據單元矩陣，例如亮度值的第一個矩陣內
容如下：

JPEG將整個亮度矩陣與色度Cb矩陣，飽和度Cr矩陣，視為一個基本單元稱作
MCU。每個MCU所包含的矩陣數量不得超過10個。例如，行和列采樣的比例皆為4:
2:2，則每個MCU將包含四個亮度矩陣，一個色度矩陣及一個飽和度矩陣。
當圖像數據分成一個8*8矩陣後，還必須將每個數值減去128，然後一一代入
DCT變換公式中，即可達到DCT變換的目的。圖像數據值必須減去128，是因為DCT
轉換公式所接受的數字范圍是在-128到+127之間。
DCT變換公式：

x,y代表圖像數據矩陣內某個數值的坐標位置
f(x,y)代表圖像數據矩陣內的數個數值
u,v代表DCT變換後矩陣內某個數值的坐標位置
F(u,v)代表DCT變換後矩陣內的某個數值
u=0 且 v=0 c(u)c(v)=1/1.414
u>0 或 v>0 c(u)c(v)=1
經過DCT變換後的矩陣數據自然數為頻率系數，這些系數以F（0，0）的值最
大，稱為DC，其餘的63個頻率系數則多半是一些接近於0的正負浮點數，一概稱
之為AC。
3、量化
圖像數據轉換為頻率系數後，還得接受一項量化程序，才能進入編碼階段。
量化階段需要兩個8*8矩陣數據，一個是專門處理亮度的頻率系數，另一個則是
針對色度的頻率系數，將頻率系數除以量化矩陣的值，取得與商數最近的整數，
即完成量化。
當頻率系數經過量化後，將頻率系數由浮點數轉變為整數，這才便於執行最
後的編碼。不過，經過量化階段後，所有數據只保留整數近似值，也就再度損失
了一些數據內容，JPEG提供的量化表如下：

4、編碼
Huffman編碼無專利權問題，成為JPEG最常用的編碼方式，Huffman編碼通常
是以完整的MCU來進行的。
編碼時，每個矩陣數據的DC值與63個AC值，將分別使用不同的Huffman編碼
表，而亮度與色度也需要不同的Huffman編碼表，所以一共需要四個編碼表，才
能順利地完成JPEG編碼工作。
DC編碼
DC是彩採用差值脈沖編碼調制的差值編碼法，也就是在同一個圖像分量中取
得每個DC值與前一個DC值的差值來編碼。DC採用差值脈沖編碼的主要原因是由於
在連續色調的圖像中，其差值多半比原值小，對差值進行編碼所需的位數，會比
對原值進行編碼所需的位數少許多。例如差值為5，它的二進製表示值為101，如
果差值為-5，則先改為正整數5，再將其二進制轉換成1的補數即可。所謂1的補
數，就是將每個Bit若值為0，便改成1；Bit為1，則變成0。差值5應保留的位數
為3，下表即列出差值所應保留的Bit數與差值內容的對照。

在差值前端另外加入一些差值的霍夫曼碼值，例如亮度差值為5（101）的位
數為3，則霍夫曼碼值應該是100，兩者連接在一起即為100101。下列兩份表格分
別是亮度和色度DC差值的編碼表。根據這兩份表格內容，即可為DC差值加上霍夫
曼碼值，完成DC的編碼工作。

AC編碼
AC編碼方式與DC略有不同，在AC編碼之前，首先得將63個AC值按Zig-zag排
序，即按照下圖箭頭所指示的順序串聯起來。

63個AC值排列好的，將AC系數轉換成中間符號，中間符號表示為RRRR/SSSS，
RRRR是指第非零的AC之前，其值為0的AC個數，SSSS是指AC值所需的位數，AC系
數的范圍與SSSS的對應關系與DC差值Bits數與差值內容對照表相似。
如果連續為0的AC個數大於15，則用15/0來表示連續的16個0，15/0稱為ZRL
（Zero Rum Length），而（0/0）稱為EOB（Enel of Block）用來表示其後所
剩餘的AC系數皆等於0，以中間符號值作為索引值，從相應的AC編碼表中找出適
當的霍夫曼碼值，再與AC值相連即可。
例如某一組亮度的中間符為5/3，AC值為4，首先以5/3為索引值，從亮度AC
的Huffman編碼表中找到1111111110011110霍夫曼碼值，於是加上原來100（4）
即是用來取[5，4]的Huffman編碼1111111110011110100，[5，4]表示AC值為4的
前面有5個零。
由於亮度AC，色度AC霍夫曼編碼表比較長，在此省略去，有興趣者可參閱相
關書籍。
實現上述四個步驟，即完成一幅圖像的JPEG壓縮。

參考資料
[1] 林福宗 《圖像文件格式（上）——Windows 編程》，清華大學出版社，
1996年
[2] 李振輝、李仁各編著，《探索圖像文件的奧秘》，清華大學出版社，1996年
[3] 黎洪松、成實譯《JPEG靜止數據壓縮標准》，學苑出版社，1996年