《數(shù)字圖像處理：Matlab算法設(shè)計與解譯》 課件 第7、8章-圖像壓縮編碼、圖像分割

第七章

圖像壓縮編碼

從本質(zhì)上講，數(shù)字圖像的壓縮是指在滿足一定的圖像質(zhì)量要求條件（比如保真度評分或信噪比值）下，通過尋求圖像數(shù)據(jù)的更有效地表征形式，以便用最少的比特數(shù)表示圖像或表示圖像中所包含信息的技術(shù)。

尋求圖像的有效表示方式即是尋求一種用更少的比特數(shù)表示圖像的編碼方法，從而達(dá)到表示同一圖像所需數(shù)據(jù)更少（得到壓縮）的目的。

因此壓縮和編碼是無法分開的統(tǒng)一體。7.1DCT變換

離散余弦變換：DiscreteCosineTransform，簡寫為DCT歐拉公式:

◆余弦函數(shù)的偶對稱性，使DCT僅只有實數(shù)域變換結(jié)果，不再涉及復(fù)數(shù)運算，運算簡單，費時少。

◆變換結(jié)果保持了變換域的頻率特性?！糇儞Q結(jié)果與人類視覺系統(tǒng)特性相適應(yīng)。

◆得到了更加廣泛的應(yīng)用。

7.1.1一維DCT設(shè)f(x)為一實數(shù)離散序列，如圖7.1(a)。F(x)0

1

2

…M-1…x(a）-(M-1)-1/2

-2-1/2-1-1/2-1/2

0

1/2

1+1/2

2+1/2

M-1+1/2……x(b）Fs(x)圖7.1以x=0為中心的偶序列

將(a)延拓為偶對稱序列，如圖7.1(b)。

7.1.1一維DCT則有：顯然，fs(x)是以x=0為中心的偶對稱函數(shù)。-(M-1)-1/2

-2-1/2-1-1/2-1/2

0

1/2

1+1/2

2+1/2

M-1+1/2……x(b）Fs(x)（7.1）7.1.1一維DCT

對fs(x)求2M個點的一維離散傅里葉變換(DFT)，有用y=-x對上式的第1項作變量代換，并仍用x表示可得7.1.1一維DCT考慮到fs(x)為偶函數(shù)，即fs(x)=fs(-x)，并對式（如紅線下公式）運用歐拉公式可得7.1.1一維DCT即由定義：用y=x-1/2對上式作變量代換：

也即，設(shè)y=x-1/2，則x=y+1/2，且x=(2y+1)/2這樣，當(dāng)x=1/2時，y=0；

當(dāng)x=M-1+1/2時，y=M-1則有：再用x代替y得：（7.6）7.1.1一維DCT7.1.1一維DCT

(7.6)

對上式乘以K(u)，以便將其表示成歸一正交矩陣形式，就可得f(x)的一維DCT為：

(7.7)其中

(7.78)7.1.1一維DCT

將式（7.8）代入式（7.7），可得到一種更直觀地一維正DCT表示形式為：

(7.9)

(7.10)其中：F(u)是第u個余弦變換系數(shù)，u是廣義頻率變量，f(x)是時域上的M點實序列。u,x=0,1,2,…,M-1。7.1.1一維DCT

一維離散余弦變換的正變換核為

(7.11)

當(dāng)顯示坐標(biāo)系的縱坐標(biāo)(行方向)為u(u=0,1,2…,M-1)；橫坐標(biāo)(列方向)為v(v=0,1,2…,M-1)時:

把前面得到的各行向量拼起來：

01…M-1……就可得到：

(7.12)也即，對于一維DCT正變換核：

(7.11)

當(dāng)顯示坐標(biāo)系的縱坐標(biāo)(行方向)u（u=0,1,2…,M-1）；橫坐標(biāo)(列方向)為x（x=0,1,2…,M-1）時，式（7.11）可表示成

(7.12)7.1.1一維DCT同理可得，一維DCT反變換的定義式為：

(7.13)

x=0,1,…,M-1其中

(7.14)7.1.1一維DCT當(dāng)M＝4時，根據(jù)式（7.12）:且當(dāng)(縱坐標(biāo))u=0時：也即，F(xiàn)(0)=[0.50.50.50.5]當(dāng)u=1時，可得一維DCT的正變換矩陣為：

(7.15)7.1.1一維DCT

同理，可得當(dāng)M＝4時的一維反變換矩陣為：(7.16)

【例】計算一維離散余弦變換的正變換核矩陣值的matlab程序。clc;clearall;closeall;m=input('請輸入一維信號的長度m=')%正整數(shù)fprintf('當(dāng)M=%d',m);fprintf('時的一維離散余弦變換的正變換核矩陣P(');fprintf('%d',m);fprintf(',%d):\n',m);foru=0:m-1fprintf('[');forx=0:m-1ifu==0ku=1.0/sqrt(2.0);elseku=1.0;end

hxu=sqrt(2.0/double(m))*ku*cos((pi*(2.0*double(x)+1)*u)/(2.0*double(m)));fprintf('%f',hxu);endfprintf(']\n');end一、一維DCT【例】計算一維離散余弦變換的正變換核矩陣值的matlab程序。一、一維DCT7.1.2二維偶DCT基本思想：

把一個N×N的圖像數(shù)據(jù)矩陣延拓成二維平面上的偶對稱陣列。延拓方式有兩種：

（1）圍繞圖像邊緣（但不重疊）將其折疊成對稱形式而得到的變換稱為偶離散余弦變換；（2）通過重疊圖像的第一列像素和第N-1行像素將其折疊成對稱形式而得到的變換稱為奇離散余弦變換。

為了簡化起見，下面只介紹偶離散余弦變換。

7.1.2二維偶DCT設(shè)f(x,y)為一N×N的圖像數(shù)據(jù)陣列，將f(x,y)圍繞其左邊緣和下邊緣不重疊地折疊成偶對稱圖像,即下圖。

YN-1–N(0,0)XN-1–N(-1,-1)并表示為：(7.17)

可見,2N×2N的新圖像的對稱中心位于圖像中紅色的細(xì)十字虛線的交叉處，也即位于(-1/2,-1/2)處。圖7.37.1.2二維偶DCT對上述的新圖像fs(x,y)取二維傅立葉變換可得：（7.18）由于fs(x,y)是實對稱函數(shù)，歐拉展開式后的正弦項為零值，所以上式可簡化成：（7.19）（7.20）由于該對稱函數(shù)四個象限的變換結(jié)果完全相同，所以7.1.2二維偶DCT把上述變換矩陣定義成歸一正交矩陣形式，可得fs(x,y)的二維DCT為：

(7.21)其中:(7.22)

(7.23)

二維離散余弦變換的正、反變換核是相同的、對稱的、可分離的，即為：并記

(7.26)

7.1.2二維偶DCT7.1.2二維偶DCT

二維DCT的正、反變換的空間矢量表示形式為:

(7.27)(7.28)

其中：變換矩陣的形式為（橫坐標(biāo)為x，縱座標(biāo)為u）

(7.29)

7.1.2二維偶DCTDCT變換的計算步驟：（1）把f(x，y)延拓成，長度為2N2N；（2）求的2N2N點DFT；（3）對u和v各項乘上對應(yīng)的因子和；（4）取實部，并分別乘上因子；（5）取F(u，v)的前N項，即為f(x，y)的余弦變換。7.1.2二維偶DCT例：DCT變換的matlab編程。DCT變換的matlab程序較為復(fù)雜，詳細(xì)地給出和解釋DCT變換的matlab程序已經(jīng)超出了本書的內(nèi)容范圍。

下面從說明相關(guān)概念出發(fā)，給出利用matlab的相關(guān)DCT變換函數(shù)實現(xiàn)的DCT變換matlab程序。%DCT變換matlab程序clc;clearall;closeall;img0=imread('d:\0_matlab圖像課編程\girl.jpg');subplot(1,3,1);imshow(img0);title('原圖像');

[h,w,color]=size(img0);if(color==3)%如果輸入圖像是彩色圖像,將其轉(zhuǎn)換成灰度圖像

f_gray=rgb2gray(img0);else

f_gray=img0;end

dct_coef=dct2(f_gray);%計算DCT系數(shù)subplot(1,3,2);imshow(log(abs(dct_coef)),[]);title('DCT系數(shù)圖像');

dct_coef(abs(dct_coef)<0.1)=0;%將DCT系數(shù)矩陣中小于0.1的值置為0f_dct=idct2(dct_coef);%進(jìn)行DCT逆變換重建圖像subplot(1,3,3);imshow(f_dct,[]);title('DCT變換解壓縮圖像');7.1.2二維偶DCT——DCT變換結(jié)果示例

（a）原圖像（b）DCT換系數(shù)圖像（c）DCT反變換重建圖像

圖7.4DCT變換驗證結(jié)果圖例7.1.2二維偶DCT——DCT變換結(jié)果示例7.1.2二維偶DCT——DCT變換結(jié)果示例7.1.3DCT變換的基函數(shù)與基圖像如前所述，DCT正變換和反變換可描述為：

(7.30)(7.31)

其中：

正、反變換核H(x,y,u,v)也稱為二維DCT變換的基函數(shù)或基圖像。

式(7.31)中的F(u,v)稱為變換系數(shù)。

7.1.3DCT變換的基函數(shù)與基圖像7.1.3DCT變換的基函數(shù)與基圖像

根據(jù)式（7.32）～式（7.34），當(dāng)N=4時的二維DCT變換的基圖像共有4×4=16個塊，對應(yīng)于H(x,y,u,v)中的（u,v）為(0，0)、（0，1），…，（3，3）的16種情況。

對于某個特定的u和v所對應(yīng)的塊，每個塊包括4×4=16個元素（子方塊），對應(yīng)于（x,y）為（0，0）、（0，1）、（0，2）、（0，3）、（1，0），…，（3，3）的16種情況。7.1.3DCT變換的基函數(shù)與基圖像所以當(dāng)N=4時，二維DCT變換的基圖像為：

V

0

123u0123圖7.5N=4時的二維DCT變換基圖像

【例】根據(jù)DCT正變換的基函數(shù)計算DCT變換的基圖像Matlab程序。clc;clearall;closeall;m=4;%建立尺寸為4×4的DCT變換的基圖像foru=0:3%u×v=4×4figure;%在4個figure上依次輸出u=0、1、2和3的每個v的x×y=4×4的圖像基

forv=0:3

forx=0:3%x×y=4×4

fory=0:3ifu==0ku=1.0/sqrt(2.0);%k(u)的值

elseku=1.0;endifv==0kv=1.0/sqrt(2.0);%k(v)的值

elsekv=1.0;end%計算Q(u,v,xy)，其中2m=2.0*4=8.0

quv(x+1,y+1)=0.5*ku*kv*cos(((2.0*x+1)*3.1415926*u)/8.0)*...cos(((2.0*y+1)*3.1415926*v)/8.0);

end

endsubplot(4,4,v+1);imshow(quv,[]);

endend三、DCT變換的基函數(shù)與基圖像三、DCT變換的基函數(shù)與基圖像

【例】根據(jù)DCT正變換的基函數(shù)計算DCT變換的基圖像Matlab程序。7.1.3圖像變換的基函數(shù)與基圖像前述DCT的正、反變換的基函數(shù)和基圖像的概念也適用于傅里葉變換，只是在傅里葉變換中，正變換核與反變換核是不相同的。7.2數(shù)字圖像壓縮編碼基礎(chǔ)

1.信息相關(guān)

在絕大多數(shù)圖像的像素之間，各像素行和幀之間存在著較強的相關(guān)性。

從統(tǒng)計觀點出發(fā)，就是每個像素的灰度值（或顏色值）總是和其周圍的其它像素的灰度值（或顏色值）存在某種關(guān)系，應(yīng)用某種編碼方法減少這些相關(guān)性就可實現(xiàn)圖像壓縮。7.2.1圖像壓縮的基本概念7.2.1圖像壓縮的基本概念1.信息相關(guān)引例(圖7.5)：

新的編碼只需21位：1，0101，1111，0111，1011，0011

由此可見，利用圖像中各像素之間存在的信息相關(guān)，可實現(xiàn)圖像編碼信息的壓縮。

上圖的黑白像素序列共41位，編碼為：11111，000000000000000，1111111，00000000000，1115位15位7位11位3位7.2.1圖像壓縮的基本概念2.信息冗余從信息論的角度來看，壓縮就是去掉信息中的冗余。即保留確定信息，去掉可推知的確定信息，用一種更接近信息本質(zhì)的描述來代替原有的冗余描述。圖像數(shù)據(jù)存在的冗余可分為三類：

（1）編碼冗余；

（2）像素間的冗余；

（3）心里視覺冗余。

7.2.1圖像壓縮的基本概念2.信息冗余（續(xù)1）

（1）編碼冗余由于大多數(shù)圖像的直方圖不是均勻(水平)的，所以圖像中某個或某些灰度級會比其它灰度級具有更大的出現(xiàn)概率，如果對出現(xiàn)概率大和出現(xiàn)概率小的灰度級都分配相同的比特數(shù)，必定會產(chǎn)生編碼冗余。

也即：如果一個圖像的灰度級編碼，使用了多于實際需要的編碼符號，就稱該圖像包含了編碼冗余。7.2.1圖像壓縮的基本概念2.信息冗余（續(xù)2）

（2）像素間的冗余所謂“像素間的冗余”，是指單個像素攜帶的信息相對較少，單一像素對于一幅圖像的多數(shù)視覺貢獻(xiàn)是多余的，它的值可以通過與其相鄰的像素的值來推斷。7.2.1圖像壓縮的基本概念2.信息冗余（續(xù)3）

（3）心里視覺冗余心里視覺冗余是指，在正常的視覺處理過程中那些不十分重要的信息。

也即：一些信息在一般的視覺處理中，比其他信息的相對重要程度要小，這種信息就被稱為視覺心理冗余。7.2.1圖像壓縮的基本概念2.信息冗余（續(xù)3）

（3）心里視覺冗余7.2.1圖像壓縮的基本概念3.信源編碼及其分類

信源編碼：圖像壓縮的目標(biāo)是在滿足一定的圖像質(zhì)量的條件下，用盡可能少的比特數(shù)來表示原圖像，以減少圖像的存儲容量和提高圖像的傳輸效率。

在信息論中，把這種通過減少冗余數(shù)據(jù)來實現(xiàn)數(shù)據(jù)壓縮的過程稱為信源編碼。

7.2.1圖像壓縮的基本概念3.信源編碼及其分類（續(xù)1）

信源編碼的分類：無失真編碼和有失真編碼

◆無失真壓縮也稱為無損壓縮，是一種在不引入任何失真的條件下使表示圖像的數(shù)據(jù)比特率為最小的壓縮方法。

◆有失真壓縮也稱為有損壓縮，是一種在一定比特率下獲得最佳保真度，或在給定的保真度下獲得最小比特率的壓縮方法。7.2.2圖像編碼模型

信源編碼器信源解碼器信道解碼器信道信道編碼器編碼器解碼器1.圖像編碼系統(tǒng)模型

圖7.7圖像編碼系統(tǒng)模型7.2.2圖像編碼模型

2.信道編碼器與信道解碼器◆信道編碼器和信道解碼器是一種用來實現(xiàn)抗干擾、抗噪聲的可靠數(shù)字通信技術(shù)措施?！粜诺谰幋a器是通過向信源編碼數(shù)據(jù)中插入可控制的冗余數(shù)據(jù)來減少對信道噪聲的影響的。

信源編碼器信源解碼器信道解碼器信道信道編碼器編碼器解碼器7.2.2圖像編碼模型

2.信道編碼器與信道解碼器（續(xù)1）漢明信道編碼技術(shù)的基本原理：給被編碼的數(shù)據(jù)后面補充足夠的位數(shù)，以確保各個正確的碼字之間的最小距離大于某個給定的值。

（7.35）7.2.2圖像編碼模型

2.信道編碼器與信道解碼器（續(xù)2）設(shè)一個4bit的二進(jìn)制數(shù)為，當(dāng)信道編碼采用漢明編碼時，對應(yīng)的7位漢明碼由下式確定：◆漢明編碼的結(jié)果是一個偶數(shù)位編碼。

7.2.2圖像編碼模型

2.信道編碼器與信道解碼器（續(xù)3）對漢明碼的解碼是通過對在編碼時建立的偶校驗的位串進(jìn)行奇校驗并檢查校驗字的值來實現(xiàn)的。（7.36）◆對于單個比特位的錯誤來說，是由一個非零的奇偶校驗字給出。并且：2.信道編碼器與信道解碼器（續(xù)3）

當(dāng)校驗字的結(jié)果為零時，說明傳輸中沒有錯誤，解碼的二進(jìn)制結(jié)果中的值，就是接收的傳輸結(jié)果。

當(dāng)校驗字的結(jié)果非零時，說明傳輸中有單比特位錯誤，信道解碼器只需要將由校驗字指出的出錯的比特位的值進(jìn)行翻轉(zhuǎn)就可糾正傳輸中的單比特位錯誤，解碼的二進(jìn)制結(jié)果中的出錯位翻轉(zhuǎn)后的值（沒有翻轉(zhuǎn)的位，翻轉(zhuǎn)的位），就是接收的傳輸結(jié)果。7.2.2圖像編碼模型

7.2.2圖像編碼模型

2.信道編碼器與信道解碼器（續(xù)4）例7.4

設(shè)信道編碼器的輸入=(0110)。（1）求信道編碼器的輸出碼字值，若信道傳輸正確，請驗證并說明奇校驗結(jié)果正確。（2）若在傳輸過程中第6位的值傳輸錯誤，請驗證并說明奇校驗結(jié)果。7.2.2圖像編碼模型

2.信道編碼器與信道解碼器（續(xù)5）例7.4(1)已知

因為：◆所以：信道編碼器輸出的7個比特位為：7.2.2圖像編碼模型

2.信道編碼器與信道解碼器（續(xù)6）例7.1

（2）當(dāng)傳輸正確時，解碼器的輸入應(yīng)為：且：◆校驗碼全0，校驗結(jié)果正確，說明無傳輸錯誤。正確值：7.2.2圖像編碼模型

2.信道編碼器與信道解碼器（續(xù)7）例7.1

（3）當(dāng)傳輸不正確，且假設(shè)第6位傳輸錯誤時，解碼器

的輸入應(yīng)為：且：◆校驗碼，說明第6位傳輸有錯誤。正確值：7.2.2圖像編碼模型

3.信源編碼器模型與信源解碼器模型◆在信息論中，把通過減少冗余來壓縮數(shù)據(jù)的過程稱為信源編碼?！粜旁淳幋a器的作用就是減少或消除輸入圖像中的編碼冗余。7.2.2圖像編碼模型

3.信源編碼器模型與信源解碼器模型◆信源編碼器與信源解碼器的應(yīng)用模式信源編碼器信源解碼器信道解碼器信道信道編碼器編碼器解碼器7.2.2圖像編碼模型

3.信源編碼器模型與信源解碼器模型◆信源編碼器模型：1）映射變換器{減少像素冗余}

映射變換器將輸入的圖像數(shù)據(jù)轉(zhuǎn)換為可以減少輸入圖像中像素間冗余的表示格式，其輸出是比原始圖像數(shù)據(jù)更適合于高效壓縮的圖像表示形式。信道編碼器或信道映射變換器符號編碼器量化器圖7.8信源編碼器模型7.2.2圖像編碼模型

3.信源編碼器模型與信源解碼器模型◆信源編碼器模型（續(xù)1）：◆典型的映射變換包括：（1）線性預(yù)測變換。如各種正交變換，應(yīng)用差分映射圖像編碼的差分編碼等預(yù)測編碼；（2）酉變換。如可將圖像能量集中到少數(shù)系數(shù)上的DCT變換；（3）多分辨率變換。如子帶分解和小波變換等；（4）其它變換。如二值圖像的游程編碼等。信道編碼器或信道映射變換器符號編碼器量化器7.2.2圖像編碼模型

3.信源編碼器模型與信源解碼器模型◆信源編碼器模型（續(xù)2）：2）量化器

量化器用于對映射變換（比如DCT變換）后的變換系數(shù)進(jìn)行量化，以便產(chǎn)生表示被壓縮圖像的有限數(shù)量的符號。

利用量化器對映射變換后的變換系數(shù)進(jìn)行量化會導(dǎo)致部分信息的損失。信道編碼器或信道映射變換器符號編碼器量化器7.2.2圖像編碼模型

3.信源編碼器模型與信源解碼器模型◆信源編碼器模型（續(xù)3）：3）符號編碼器

符號編碼器的作用是對量化器輸出的每一個符號分配一個碼字或二進(jìn)制比特流。信道編碼器或信道映射變換器符號編碼器量化器7.2.2圖像編碼模型

3.信源編碼器模型與信源解碼器模型3）符號編碼器：符號編碼器

輸入X稱為信源符號集，集合中的每一個元素xi稱為信源符號。輸出W稱為代碼，集合中的每一個元素wi稱為碼字。A稱為碼元集，集合中的每一個元素aj稱為碼元。圖7.9信源符號編碼器構(gòu)成示意圖7.2.2圖像編碼模型

3.信源編碼器模型與信源解碼器模型3）符號編碼器：符號編碼器符號編碼器的功能：是用碼元集A中的一組碼元aj建立輸入的信源符號xi與輸出的碼字wi之間的關(guān)系。也就是為信源符號集中的每一個元素xi分配一個用一組碼元aj表示的碼字wi。所有的碼字wi都按規(guī)定的編碼方式由aj來組成。7.2.2圖像編碼模型

3.信源編碼器模型與信源解碼器模型4）灰度圖像的符號編碼

也即，利用碼元集A={0，1}，對灰度圖像符號序列（也即，灰度級值0，1，…，255）的編碼。

這個符號序列也即獨立信源：X={,

,…,}

獨立信源源符號集

中每個符號出現(xiàn)的概率：

P=7.2.2圖像編碼模型

3.信源編碼器模型與信源解碼器模型5）信源解碼器模型信道編碼器或信道符號解碼器反向映射變換器反量化器7.2.3數(shù)字圖像的信息熵

1.數(shù)字圖像的信息熵

設(shè)有信源符號集X={x1,x2,…,xn}，信源符號出現(xiàn)的概率為{P(x1),P(x2)，…，P(xn)}。對X編碼得到的代碼為W={w1,w2,…，wn}，其中每個碼字wi的比特數(shù)（長度）為l(xi)。則表示每個信源符號碼字的平均長度（比特數(shù)）為（7.39）7.2.3數(shù)字圖像的信息熵

2.信息熵與信源符號碼字平均長度的關(guān)系

信息熵是一個系統(tǒng)信息含量的量化指標(biāo)，通常用來作為系統(tǒng)優(yōu)化的目標(biāo)或者參數(shù)選擇的判據(jù)。

信源的熵定義為其中，熵的單位是b/s，表示每個符號的比特數(shù)。（7.40）7.2.3數(shù)字圖像的信息熵

例7.5

設(shè)有一個隨機變量X有8種可能的狀態(tài)

，每個狀態(tài)都是等可能的，則該隨機變量的熵為：

也就是說，為了把X的值傳遞給接收者，需要傳輸一個3比特的消息。（7.40）7.2.3數(shù)字圖像的信息熵

例7.6

設(shè)有一個隨機變量X有8種可能的狀態(tài){a,b,c,d,e,f,g,h}，每個狀態(tài)各自的概率為{1/2,1/4,1/8,1/16,1/64,1/64,1/64,1/64}，這種情況下該隨機變量的熵為：

也就是說，隨機變量非均勻分布時的熵，要比隨機變量均勻分布時的熵小。7.2.3數(shù)字圖像的信息熵

基于以上的引例可知：

（1）可以利用非均勻分布的特點，使用盡可能短的編碼來描述更可能的事件，使用更長的編碼來描述不太可能的事件，就可以得到更短的平均編碼長度。

比如：對于例7.6，可以使用編碼串：0、10、110、1110、111100、111101、111110、111111來表示狀態(tài){a,b,c,d,e,f,g,h}。根據(jù)式（7.39），其需要傳輸?shù)钠骄L度為7.2.3數(shù)字圖像的信息熵

基于以上的引例可知：

（2）如果所有信源符號的概率都是2的指數(shù)，信源符號碼字的平均長度就與隨機變量的熵相等。熵是編碼所需比特數(shù)的下限。例7.6

2.信息熵與信源符號碼字平均長度的關(guān)系

在信息論中，信息量是指從N個相等的可能事件中選出一個事件所需的信息度量或含量。假設(shè)N的大小為2的整次冪（比如

），則信息量可表示為

將式（7.41）代入式（7.40）可得：

（7.41）（7.42）（7.40）7.2.3數(shù)字圖像的信息熵

（7.42）7.2.3數(shù)字圖像的信息熵

（7.39）7.2.3數(shù)字圖像的信息熵

3.數(shù)字圖像的信息熵

對于一幅灰度級值分布為X={0，1，…，L-1}，且其灰度級值出現(xiàn)的概率為P={，

，…

，}的數(shù)字圖像，其信息熵定義為（7.43）7.3幾種最基本的變長編碼方法

變長編碼的基本思想是用盡可能少的比特數(shù)表示出現(xiàn)概率盡可能大的灰度級，以實現(xiàn)數(shù)據(jù)的壓縮編碼。

由于利用這些編碼方法得到的碼字長度是不相等的，所以稱為變長編碼。

利用最基本的變長編碼對圖像進(jìn)行的編碼不會產(chǎn)生信息損失，所以這類編碼方法也稱為無誤差編碼方法，或無損編碼方法。

7.3.1費諾碼

費諾編碼方法認(rèn)為：在數(shù)字形式的碼字中的0和1是相互獨立的，因而其出現(xiàn)的概率也應(yīng)是相等的（為0.5或接近0.5），這樣就可確保傳輸?shù)拿恳晃淮a含有1比特的信息量。諾設(shè)輸入的離散信源符號集為X={x0,x1,…,xn}，其出現(xiàn)概率為P(xi)，欲求的費諾碼為W={w0,w1,…，wn}，則費諾碼編碼方法的步驟為：

費諾碼編碼方法的步驟：

（1）把輸入的信源符號和其出現(xiàn)的概率按概率值的非遞增順序從上到下依次并列排列。（2）按概率之和相等或相近的原則把X分成兩組，并給上面或概率之和較大的組賦值1，給下面或概率之和較小的組賦值0。（3）再按概率之和相等或相近的原則把現(xiàn)有的組分成兩組，并給上面或概率之和較大的組賦值1，給下面或概率之和較小的組賦值0。（4）重復(fù)（3）的分組和賦值過程，直至每個組只有一個符號為止。（5）把對每個符號所賦的值依次排列，就可得到信源符號集X的費諾碼。

例7.7設(shè)有信源符號集X={x1,x2,…,x8}，其概率分布為P(x1)=0.25，P(x2)=0.125，P(x3)=0.0625，P(x4)=0.25，P(x5)=0.0625，P(x6)=0.125，P(x7)=0.0625，P(x8)=0.0625，求其費諾碼W={w1,w2,w3,w4,w5,w6,w7,w8}。

即有：P(x1)=0.25=1/4

P(x2)=0.125=1/8

P(x3)=0.0625=1/16

P(x4)=0.25=1/4

P(x5)=0.0625=1/16P(x6)=0.125=1/8P(x7)=0.0625=1/16P(x8)=0.0625=1/16

7.3.1費諾碼

符號概率編碼結(jié)果

1/41111/410101/810111/8100101/160100111/1601000101/16100011/160000007.3.1變長編碼例7.7解：平均碼字長度：

7.3.2霍夫曼編碼設(shè)輸入的離散信源符號集為X={x0,x1,…,xn}，其出現(xiàn)概率為P(xi)，欲求的霍夫曼編碼為W={w0,w1,…，wn}。

1.

霍夫曼編碼方法的步驟：

（1）統(tǒng)計信源（比如一幅圖像）中的信源符號及每個信源符號出現(xiàn)的概率。設(shè)經(jīng)統(tǒng)計有n個信源符號（i=0,…,n），其出現(xiàn)概率為

。（2）把把信源符號

和其概率

，依序按概率值的遞減順序從上到下依次排列。

（3）把最末兩個具有最小概率值的信源符號的概率值合并相加得到新的概率值。（4）給最末兩個具有最小概率值的信源符號的上面的信源符號編碼“0”，給下面的信源符號編碼“1”。（5）如果最末兩個信源符號的概率值合并相加后為1.0，則轉(zhuǎn)（7）；否則繼續(xù)下一步。（6）把合并相加得到的新概率值與其余概率值按遞減順序從上到下依次排列，并轉(zhuǎn)（3）。（7）尋找每一個信源符號到概率為1.0處的路徑，并依次記錄路徑上的“1”和“0”，即可得到每個信源符號對應(yīng)的二進(jìn)制符號序列。（8）逆序逐位地寫出每個信源符號對應(yīng)的二進(jìn)制符號序列，即可得到每個信源符號的霍夫曼編碼。例7.8設(shè)有信源符號集X={x1,x2,x3,x4,x5,x6}，其概率分布分別為P(x1)=0.1，P(x2)=0.3，P(x3)=0.1，P(x4)=0.4，P(x5)=0.04，P(x6)=0.06，求其霍夫曼編碼W={w1,w2,w3,w4,w5,w6}。

7.3.2霍夫曼編碼

0

0.110

0.110

0.3100.410

1

0.060.04

0.40.40.40.40.6

0.30.30.30.3

0.10.1

0.2

0.10.1

例7.8解：編碼過程為：

依據(jù)步驟（7），可得信源符號及其對應(yīng)的二進(jìn)制符號序列為：

根據(jù)步驟（8），將上述二進(jìn)制符號序列逆序排列，即可得到霍夫曼編碼為：W={011,00,0100,1,01010,01011}例7.87.3.2霍夫曼編碼=0.1×3+0.3×2+0.1×4++0.4×1+0.04×5+0.06×5

=2.2（bit）

課堂練習(xí)：7.3.2霍夫曼編碼

2.

利用霍夫曼編碼進(jìn)行壓縮編碼的方法

（1）創(chuàng)建霍夫曼編碼表。比如，對于例7.5的霍夫曼編碼

W={011,00,0100,1,01010,11010}可創(chuàng)建如下的霍夫曼編碼表：7.3.2霍夫曼編碼

2.

利用霍夫曼編碼進(jìn)行壓縮編碼的方法

（2）對信源符號進(jìn)行編碼，也即用碼字代替信源符號。

按照例7.5中各信源符號的概率，設(shè)要壓縮編碼的信源符號流為：

則編碼流就應(yīng)為：01100000001000100111101010111100000001101011。

在信息接收端解碼時，計科根據(jù)碼字的長度（位數(shù)）信息，還原出原來的碼值。7.3.2霍夫曼編碼

3.

霍夫曼編碼的優(yōu)點◆當(dāng)對獨立信源符號進(jìn)行編碼時，霍夫曼編碼可對每個信源符號產(chǎn)生可能是最少數(shù)量（最短）碼元的碼字?！艋舴蚵幋a是所有變長編碼中平均碼長最短的。如果所有信源符號的概率都是2的指數(shù)，霍夫曼編碼的平均長度將達(dá)到最低限，即信源的熵?！魧τ诙M(jìn)制的霍夫曼編碼，平均碼字的平均長度滿足關(guān)系：7.3.2霍夫曼編碼【例】霍夫曼編碼matlab程序。%1.輸入信源符號集及其概率向量，并檢查其值的合理性clc;clearall;closeall;symbol_S=input('請輸入信源符號(單引號括住)集向量S=');P0=input('請輸入信源符號集的概率向量P=');M=numel(symbol_S);N=numel(P0);if(M~=N)error('信源符號向量與信源符號概率向量元素個數(shù)不等！');%報錯并退出endfori=1:1:Nif(P0(i)<=0)error('信源概率不能小于等于0！');%報錯提示，并退出當(dāng)前腳本程序

endend%2.建立各概率符號的位置索引矩陣index，以便于編碼后從樹根進(jìn)行回朔[P,S_order]=sort(P0);%P為按升序排列的新向量，S_order為原向量P0中元素的序號Q=P;Index=zeros(N-1,N);%生成(N-1)*N的全零矩陣fori=1:N-1[Q,L]=sort(Q);Index(i,:)=[L(1:N-i+1),zeros(1,i-1)];Q=[Q(1)+Q(2),Q(3:N),1];%將Q中概率最小的兩個元素合并end%3.根據(jù)以上建立的index矩陣進(jìn)行回朔，獲取信源編碼fori=1:N-1%初始化一個由空格符組成的字符矩陣C,用于存放編碼

C(i,1:N*N)=blanks(N*N);endC(N-1,N)='1';%給N-1行(最后一行)第1個元素賦1，存到C中第N-1行的N列位置C(N-1,2*N)='0';%給N-1行第2個元素賦0，存到C中第N-1行的2*N列位置fori=2:N-1%將index后一行中索引為1的編碼碼字填入到當(dāng)前行的第1個編碼位置

C(N-i,1:N-1)=C(N-i+1,N*(find(Index(N-i+1,:)==1))-...(N-2):N*(find(Index(N-i+1,:)==1)));C(N-i,N)='0';%C中第N-i行第2列的N-1個字符與第N-i行的第1個元素的前N-1個符號相同

C(N-i,N+1:2*N-1)=C(N-i,1:N-1);C(N-i,2*N)='1';forj=1:i-1%將index后１行中索引不為1的編碼按左右順序填入當(dāng)前行的第3個位置開始的地方

C(N-i,(j+1)*N+1:(j+2)*N)=C(N-i+1,N*(find(Index(N-i+1,:)==j+1)-1)+...1:N*find(Index(N-i+1,:)==j+1));endend%4.形成最后的huffman編碼,在H中fori=1:NH(i,1:N)=C(1,N*(find(Index(1,:)==i)-1)+1:find(Index(1,:)==i)*N);W_length(i)=length(find(abs(H(i,:))~=32));%計算每一個編碼的長度end%5.將各信源符號的霍夫曼編碼按輸入信源符號順序排列fori=1:Nforj=1:Nif(S_order(j)==i)H1(i,:)=H(j,:);continue;endendend%6.打印結(jié)果disp('信源符號概率對應(yīng)的Huffman編碼-')fori=1:Nfprintf('%s%f%s\n',symbol_S(i),P0(i),H1(i,:));endL=sum(P.*W_length);%計算平均碼長fprintf('平均碼字長度為：%f\n',L);【例】霍夫曼編碼matlab程序。四、霍夫曼編碼7.3.3幾種接近最佳的變長編碼輸入輸出Wi(信源符號i)二進(jìn)制編碼

B1碼B2碼二進(jìn)制移位碼00000C0C0000010001C1C0100120010C0C0C1001030011C0C1C1101140100C1C0C00C0010050101C1C1C00C0110160110C0C0C0C00C1011070111C0C0C1C00C1111100081000C0C1C0C01C0011100191001C0C1C1C01C01111010101010C1C0C0C01C10111011111011C1C0C1C01C11111100121100C1C1C0C10C00111101131101C1C1C1C10C01111110141110C0C0C0C0C10C10111111000151111C0C0C0C1C10C11111111001

表7.2

幾種典型的變長變碼7.3.3幾種接近最佳的變長編碼

1）B碼

（1）B1碼{自學(xué)}

（2）B2碼{自學(xué)}

2）二進(jìn)制移位碼

{自學(xué)}7.3.4算術(shù)編碼算術(shù)編碼假設(shè)，對于一個獨立信源來說，任一由信源符號組成的長度為N的序列的發(fā)生概率之和等于1。

根據(jù)信源符號序列的概率，把[0，1]區(qū)間劃分為互不重疊的子區(qū)間，子區(qū)間的寬度恰好等于各符號序列的概率，這樣每個子區(qū)間內(nèi)的任意一個實數(shù)都可以用來表示對應(yīng)的符號。

顯然，一串符號序列發(fā)生的概率越大，對應(yīng)的子區(qū)間就越寬，表達(dá)它所用的比特數(shù)就越少，因而相應(yīng)的碼字就越短。

1、算術(shù)編碼過程（1）建立概率模型，即通過掃描統(tǒng)計，獲得各信源符號的概率大小（2）編碼過程，即掃描符號序列，依次分割相應(yīng)的區(qū)間，最終得到符號序列所對應(yīng)的碼字。7.3.4算術(shù)編碼

圖7.15算術(shù)編碼過程圖示舉例:設(shè)有一個四信源符號的五符號輸入序列a1a2a2a3a4。（1）建立信源符號集的概率模型：通過掃描可知信源符號a1a2a3a4的出現(xiàn)概率依次為0.2、0.4、0.2和0.2。（2）編碼方法：

編碼序列

7.3.4算術(shù)編碼（K=1，2，…，N）（7.47）

2、編碼過程的數(shù)學(xué)描述設(shè)由M個信源符號X=x1x2…xm

組成的長度為N的輸入符號序列中，各信源符號的概率分布為Pj（j=1,2,…，M；k=1,2,…,N；M≤N），[0，1）為對輸入符號序列進(jìn)行算術(shù)編碼的初始區(qū)間，則對第k個輸入符號進(jìn)行算術(shù)編碼的子分區(qū)間[Lk，Rk）定義為：

7.3.4算術(shù)編碼7.4位平面編碼

所謂位平面編碼，就是將一幅灰度圖像或彩色圖像分解為多幅二值圖像,然后對二值圖像應(yīng)用二值圖像編碼方法，以達(dá)到對多值圖像編碼的目的。

一幅m位的灰度級圖像的灰度值可用多項式表示為：（7.49）其中，xi∈[0，1]。

也就是說，圖像的同一個比特位的系數(shù)的集合就是一個二值圖像，稱為一個“位平面”。位平面編號從0開始，直到m-1。將m個位平面組合，顯然又可以恢復(fù)原來的灰度圖像。7.4.1位平面分解舉例來說，對于一幅N×N的灰度圖像，若每個像素用m位表示，就可以從每個像素的二進(jìn)制表示中取出相同位置上的一位，這樣就形成了一幅N×N的二值圖像，稱該二值圖像為原灰度圖像的一個位平面。

對于一幅256灰度級的圖像來說，每個像素用一個8位的字節(jié)表示，該圖像就可以分解成8個位平面，平面0由原圖像中像素的最低位組成，平面1由原圖像中像素的此低位組成，…，平面7由原圖像中像素的最高位組成。7.4.1位平面分解原圖像的一個像素對應(yīng)8位位平面7(最高位)位平面0(最低位)01010101

85灰度圖像圖7.178位圖像的位平面分解圖示7.4.1位平面分解clc;clearall;closeall;img0=imread('d:\0_matlab圖像課編程\star_img.jpg');subplot(3,3,1);imshow(img0);title('原圖像');[h,w]=size(img0);fork=1:8fori=1:hforj=1:w%bitget函數(shù)先將img0(i,j)處灰度值分解為二進(jìn)制串，然后取第k位的值

bit_mp(i,j)=bitget(img0(i,j),k);endendsubplot(3,3,k+1);imshow(bit_mp,[]);K1=num2str(k);mark=['第',K1,'個位平面'];title(mark);end五、位平面編碼

【例】從灰度圖像分解位平面圖像的Matlab程序?！纠繌幕叶葓D像分解位平面圖像的matlab程序。五、位平面編碼

圖7.19一幅8位圖像及其該圖像的8個位平面二值圖像7.4.1位平面分解7.4.2位平面的格雷碼分解編碼多數(shù)圖像中的大多數(shù)相鄰像素值具有漸變的特征，但若采用二進(jìn)制碼進(jìn)行位平面分解，就會導(dǎo)致各位平面中相關(guān)性的減小。比如，若灰度圖像中的兩個相鄰像素是127和128，它們顯然比較接近，但其二進(jìn)制編碼卻分別為01111111和10000000也即,灰度圖像中相鄰像素間的很小變化，卻引起了所有位平面值的突變，從而降低了位平面圖像的相關(guān)性，也即降低了位平面圖像的壓縮效率。

由于兩個相鄰值的格雷碼之間只有一位是不同的，這樣就可保持相鄰像素間較強的相關(guān)性，所以一般采用格雷碼（Gray）進(jìn)行位平面分解編碼。7.4.2位平面的格雷碼分解編碼

采用格雷碼進(jìn)行位平面分解編碼的思想是:如果用一個m位的灰度編碼gm-1…g2g1g0表示圖像，那么圖像中這個m位的灰度編碼gm-1…g2g1g0的所有g(shù)i就組成了第i個位平面二值圖像。7.4.2位平面的格雷碼分解編碼（7.50）

設(shè)反映灰度值大小的m位二進(jìn)制編碼為xm-1…x2x1x0，與其對應(yīng)的m位格雷碼為gm-1…g2g1g0

，則有：7.4.2位平面的格雷碼分解編碼比如：127：01111111而對于：128：

10000000對應(yīng)的格雷碼為：00000000對應(yīng)的格雷碼為：10000000◆僅有一位不同。7.4.2位平面的格雷碼分解編碼7.5游程編碼

◆一般把具有相同灰度值的一些像素組成的序列稱為一個游程。

◆把取相同灰度值的若干連續(xù)像素點的數(shù)目稱為游程長度，簡稱游長。

◆在黑白圖像中，像素點為黑和白，或者說像素只取0和1兩個灰度值，這樣，就把連續(xù)白點和連續(xù)黑點的數(shù)目分別稱為白長和黑長。

◆因為黑白圖像像素點只取兩個灰度值，所以與灰度圖像相比，黑白圖像相鄰像素點的相關(guān)性更強，游程編碼正好利用了這種相關(guān)性。

◆游程編碼的基本思想是：只存儲一個代表某個灰度值的碼，后面是它的游程長度，這樣同樣的灰度值碼就不必存儲多次。

7.5游程編碼——一維游程編碼

在編碼時，對每一行的第一個像素要有一個標(biāo)志碼，以區(qū)分該行是以白長開始還是以黑長開始，并給出其編碼。對于后面的游長，只要給出相應(yīng)游長的編碼。

決定游程長度值最通常的約定是：（1）指定每一行第一個游程的值；（2）假設(shè)每一行從白色游程開始。如果該行是從黑色游程開始，則記這個游程長度為0。國際傳真標(biāo)準(zhǔn)CCITTT.4（G3）采用的是一維游程編碼。編碼方法是：游長的霍夫曼編碼分為形成碼和終止碼兩種。對于位于0～63之間的游長，用單個的碼字，即終止碼表示；對于大于63的游長，用一個形成碼和一個終止碼的組合來表示。其中，形成碼表示實際游長的64的最大倍數(shù)值，終止碼表示其余小于64的差值。

7.5游程編碼——一維游程編碼

表7.4國際傳真標(biāo)準(zhǔn)ITU（CCITTT.4G3）終止碼表

游長白長碼字黑長碼字

000110101000011011110001110102011111310001041011011

5

1100

0011

6

1110

0010

┇

┇

┇63001101000000011001117.5游程編碼——一維游程編碼

表7.5國際傳真標(biāo)準(zhǔn)ITU（CCITTT.4G3）形成碼表

游長白長碼字（碼字）黑長碼字

641101100000011111281001000011001000 192010111000011001001┇┇┇17280100110110000001100101

1729 00000001000（黑白碼字開始相同）

185600000001100┇┇25600000000111117.5游程編碼——一維游程編碼

二維游程編碼是一種基于相對地址編碼原理的編碼方法，通過對黑白過渡點（從白到黑，或從黑到白后的一個比特位置稱為過渡點）相對于當(dāng)前編碼行中參考像素的位置進(jìn)行編碼，不僅利用了二值圖像中每一行內(nèi)相鄰像素的相關(guān)性，而且也利用了當(dāng)前編碼行與參考行（前一行）的行間像素之間的相關(guān)性。7.5游程編碼——二維游程編碼

7.6變換編碼

變換編碼以信號處理中的正交變換的性質(zhì)為理論基礎(chǔ)，基本依據(jù)是：

（1）正交變換可保證變換前后信號的能量保持不變；

（2）正交變換具有減少原始信號中各分量的相關(guān)性及將信號的能量集中到少數(shù)系數(shù)上的功能。

所謂變換編碼，是指以某種可逆的正交變換把給定的圖像變換到另一個數(shù)據(jù)域（如頻域），從而利用新的數(shù)據(jù)域的特點，用一組非相關(guān)數(shù)據(jù)（系數(shù)）來表示原圖像，并以此來去除或減小圖像在空間域中的相關(guān)性，將盡可能多的信息集中到盡可能少的變換系數(shù)上，使多數(shù)系數(shù)只攜帶盡可能少的信息，實現(xiàn)用較少的數(shù)據(jù)表示較大的圖像數(shù)據(jù)信息，進(jìn)而達(dá)到壓縮數(shù)據(jù)的目的。7.6.1變換編碼的過程◆變換編碼過程由以下四步組成：（1）將待編碼的N×N的圖像分解成(N/n)2個大小為n×n的子圖像。通常選取的子圖像大小為8×8或16×16，即n等于８或16。（2）對每個子圖像進(jìn)行正交變換（如DCT變換等），得到各子圖像的變換系數(shù)。這一步的實質(zhì)是把空間域表示的圖像轉(zhuǎn)換成頻率域表示的圖像。（3）對變換系數(shù)進(jìn)行量化。（4）使用霍夫曼變長編碼或游程編碼等無損編碼器對量化的系數(shù)進(jìn)行編碼，得到壓縮后的圖像（數(shù)據(jù)）。圖7.20變換編碼系統(tǒng)框圖壓縮圖像構(gòu)造n×n個子圖像系數(shù)量化器正變換符號編碼器原始圖像數(shù)據(jù)量化方案(量化函數(shù)或量化表)編碼方案及表說明7.6.1變換編碼的過程◆變換編碼系統(tǒng)的實現(xiàn)：7.6.2子圖像尺寸選擇

◆子圖像的大小與變換編碼的誤差和變換所需的計算量等有關(guān)。

◆在大多數(shù)應(yīng)用中，把圖像進(jìn)一步分割成子圖像塊要求滿足以下兩個條件：一是相鄰子圖像塊之間的相關(guān)性（冗余）要減少到某種可接受的程度；二是子圖的長和寬應(yīng)是2的整數(shù)次冪?！糇畛２捎玫淖訄D像尺寸為8×8和16×16。7.6.3變換的選擇

1.變換系數(shù)

如7.1.3節(jié)所述，對于N×N的圖像f(x,y)和該圖像的二維正向離散變換T(u,v)，有：（7.51）(7.52)其中，H(x,y,u,v)稱為變換核函數(shù)（正變換與反變換核函數(shù)相同），也稱為基函數(shù)或基圖像；式(7.52)中的T(u,v)稱為變換系數(shù)。

7.6.3變換的選擇

用n替換式(7.52)中的N，則一幅大小為n×n的子圖像f(x,y)可以表示成它的二維變換的函數(shù)：

(7.53)

其中：反變換核函數(shù)h(x,y,u,v)只依賴于參數(shù)x，y，u，v；與f(x,y)和T(u,v)的值無關(guān)。

所以，h(x,y,u,v)可看作是由式(7.53)定義的子圖像序列的一組基函數(shù)或基圖像。

(7.54)7.6.3變換的選擇

進(jìn)一步將式(7.53)表示成：為：

其中，(7.55)顯然，式(7.54)顯式地將F定義成n2個n×n矩陣的線性組合，這些矩陣是式(7.53)的子圖像序列的基函數(shù)或基圖像，T(u,v)是變換系數(shù)。7.6.3變換的選擇

2.圖像的均方差如果把變換系數(shù)的模板函數(shù)定義為：

(7.56)(7.57)那么，的一個截斷近似可定義為：

顯然，利用的截斷功能就可消除掉式(7.48)中對求和貢獻(xiàn)最少的系數(shù)。7.6.3變換的選擇

2.圖像的均方差（續(xù)1）且子圖像F和它的近似之間的均方誤差為：(7.58)也即有：

(7.58)其中，是變換系數(shù)在(u,v)處的方差。

7.6.3變換的選擇

(7.58)由式（7.56）和式（7.58）可知，當(dāng)T(u,v)滿足指定的截斷準(zhǔn)則時，的值為1，否則其值為0。所以總的均方差近似誤差是所有截斷的變換系數(shù)的方差之和。一個能把最多的信息集中到最少的系數(shù)上去的變換提供了最好的子圖近似，因此所產(chǎn)生的重建誤差最小。

(7.56)7.6.3變換的選擇

◆由于DCT在信息集中能力和計算復(fù)雜性方面的綜合優(yōu)勢已經(jīng)取得了較多的應(yīng)用。

◆對于大多數(shù)自然圖像來說，DCT能將最多的信息分配在最少的系數(shù)之中，還能使被稱為“分塊噪聲”的子圖邊緣可見的塊效應(yīng)達(dá)到最小。

◆變換編碼通常采用的變換包括：DCT(離散余弦變換)、DFT（離散傅里葉變換）、WHT（沃爾什-哈達(dá)瑪變換）和KLT（卡-洛變換）等實現(xiàn)。

3.幾種變換的性能7.6.4變換系數(shù)的量化和編碼1.區(qū)域編碼

所謂區(qū)域編碼，就是