第七章圖像壓縮編碼數(shù)字圖像處理李俊山編著.《數(shù)字圖像處理（第5版）》

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

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

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

DCT（DiscreteCosineTransform），即散余弦變換，主要是利用了余弦函數(shù)的偶對稱性cos(-x)=cos(x)，以及歐拉公式：的運算規(guī)則，使DCT變換結(jié)果只有實數(shù)域，不再涉及復(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即由定義：…（7.1）用y=x-1/2對上式作變量代換：

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

當x=M-1+1/2時，y=M-1則有：再用x代替（換回）y得：（7.2）7.1.1一維DCT

(7.2)

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

(7.3a)其中

(7.3b)7.1.1一維DCT

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

(7.4a)

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

(7.5)

基于如右圖的顯示坐標：

當u=0時：且當x=0，1，…，M-1時，有：

01…M-1ux7.1.1一維DCTx=一維DCT正變換核都為：

(7.5)

基于如右圖的顯示坐標：

當u=1時：且當x=0，1，…，M-1時，有：

01…M-1ux7.1.1一維DCTx=一維DCT正變換核都為：

(7.5)

基于如右圖的顯示坐標：

當u=M-1時：且當x=0，1，…，M-1時，有：

01…M-1ux7.1.1一維DCTx=(7.6)ux7.1.1一維DCT也即，對于一維DCT正變換核：

(7.5)

當顯示坐標系的縱坐標(行方向)u（u=0,1,2…,M-1）；橫坐標(列方向)為x（x=0,1,2…,M-1）時，式（7.5）可表示成(7.6)7.1.1一維DCT7.1.1一維DCT

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

(7.7a)

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

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

(7.8)7.1.1一維DCT同理，可得當M＝4時的一維反變換矩陣為：(7.9)7.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.10)

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

(7.14a)其中:(7.14b)

(7.14c)

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

并記

(7.17)

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

(7.18a)(7.18b)

7.1.2二維偶DCT

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

(7.18a)(7.18b)

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

ux(7.19)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ù)雜，詳細地給出和解釋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);elsef_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);%進行DCT逆變換重建圖像subplot(1,3,3);imshow(f_dct,[]);title('DCT變換解壓縮圖像');7.1.2二維偶DCT——DCT變換結(jié)果示例

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

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

(7.20)(7.21)

其中：

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

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

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

根據(jù)式（7.22），當N=4時的二維DCT變換的基圖像共有4×4=16個塊，對應(yīng)于Q(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ù)與基圖像

所以當N=4時，二維DCT變換的基圖像為：

V

0

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

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ù)視覺貢獻是多余的，它的值可以通過與其相鄰的像素的值來推斷。7.2.1圖像壓縮的基本概念2.信息冗余（續(xù)3）

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

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

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

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

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

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

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

◆無失真編碼是指壓縮后的數(shù)據(jù)經(jīng)解壓縮還原后，得到的數(shù)據(jù)與原數(shù)據(jù)完全相同，沒有任何信息損失的數(shù)據(jù)編碼方法。

無失真編碼也稱為無失真壓縮，或無損壓縮。7.2.1圖像壓縮的基本概念3.信源編碼及其分類（續(xù)1）

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

◆有失真編碼是指壓縮后的數(shù)據(jù)經(jīng)解壓縮還原后，得到的數(shù)據(jù)與原數(shù)據(jù)不完全相同，是有信息損失的數(shù)據(jù)編碼方法。

有失真編碼也稱為有失真壓縮，或有損壓縮。7.2.2圖像編碼模型

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

圖7.6圖像編碼系統(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.23）7.2.2圖像編碼模型

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

7.2.2圖像編碼模型

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

給出。并且：2.信道編碼器與信道解碼器（續(xù)3）

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

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

7.2.2圖像編碼模型

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

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

2.信道編碼器與信道解碼器（續(xù)5）例7.1(1)編碼：已知◆也即：信道編碼器輸出的7個比特位為：7.2.2圖像編碼模型

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

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

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

解碼：（3）當傳輸不正確，且假設(shè)第6位傳輸錯誤時，解碼器的輸入應(yīng)為：且：◆校驗碼，說明第6位傳輸有錯誤。正確值：7.2.2圖像編碼模型

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

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

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

映射變換器將輸入的圖像數(shù)據(jù)轉(zhuǎn)換為可以減少輸入圖像中像素間冗余的表示格式，其輸出是比原始圖像數(shù)據(jù)更適合于高效壓縮的圖像表示形式。信道編碼器或信道映射變換器符號編碼器量化器圖7.7信源編碼器模型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ù)進行量化，以便產(chǎn)生表示被壓縮圖像的有限數(shù)量的符號。

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

3.信源編碼器模型與信源解碼器模型

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

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

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

輸入X稱為信源符號集，集合中的每一個元素xi稱為信源符號。輸出W稱為代碼，集合中的每一個元素wi稱為碼字。A稱為碼元集，集合中的每一個元素aj稱為碼元。圖7.8信源符號編碼器構(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.27）7.2.3數(shù)字圖像的信息熵

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

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

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

例7.2

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

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

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

例7.3

設(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.3，可以使用編碼串：0、10、110、1110、111100、111101、111110、111111來表示狀態(tài){a,b,c,d,e,f,g,h}。根據(jù)式（7.28），其需要傳輸?shù)钠骄L度為7.2.3數(shù)字圖像的信息熵

基于以上的引例可知：

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

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

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

），則信息量可表示為

將式（7.29）代入式（7.28）可得：

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

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

比較式（7.27）和式（7.30）可知，每個信源符號的信息量實質(zhì)上反映的是該信源符號的編碼長度。（7.30）7.2.3數(shù)字圖像的信息熵

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

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

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

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

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

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

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

7.3.1費諾碼

費諾編碼方法認為：

在數(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.4設(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.4解：平均碼字長度：

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)的二進制符號序列。（8）逆序逐位地寫出每個信源符號對應(yīng)的二進制符號序列，即可得到每個信源符號的霍夫曼編碼。例7.5設(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.05，P(x6)=0.05，求其霍夫曼編碼W={w1,w2,w3,w4,w5,w6}。

7.3.2霍夫曼編碼

0

0.110

0.110

0.3100.410

1

0.050.05

0.40.40.40.40.6

0.30.30.30.3

0.10.1

0.2

0.10.1

例7.5解：編碼過程為：

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

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

=2.2（bit）

課堂練習：7.3.2霍夫曼編碼

2.

利用霍夫曼編碼進行壓縮編碼的方法

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

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

2.

利用霍夫曼編碼進行壓縮編碼的方法

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

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

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

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

3.

霍夫曼編碼的優(yōu)點◆當對獨立信源符號進行編碼時，霍夫曼編碼可對每個信源符

號產(chǎn)生可能是最少數(shù)量（最短）碼元的碼字。◆霍夫曼編碼是所有變長編碼中平均碼長最短的。如果所有信

源符號的概率都是2的指數(shù)，霍夫曼編碼的平均長度將達到最低限，即信源的熵?！魧τ诙M制的霍夫曼編碼，平均碼字的平均長度滿足關(guān)系：7.3.2霍夫曼編碼7.3.3幾種接近最佳的變長編碼輸入輸出Wi(信源符號i)二進制編碼

B1碼B2碼二進制移位碼00000C0C0000010001C1C0100120010C0C0C1001030011C0C1C1101140100C1C0C00C0010050101C1C1C00C0110160110C0C0C0C00C1011070111C0C0C1C00C1111100081000C0C1C0C01C0011100191001C0C1C1C01C01111010101010C1C0C0C01C10111011111011C1C0C1C01C11111100121100C1C1C0C10C00111101131101C1C1C1C10C01111110141110C0C0C0C0C10C10111111000151111C0C0C0C1C10C11111111001

表7.2

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

1）B碼

（1）B1碼{自學}

（2）B2碼{自學}

2）二進制移位碼

{自學}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ū)間就越寬，表達它所用的比特數(shù)就越少，因而相應(yīng)的碼字就越短。

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

圖7.12算術(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.35a）（7.35b）

（7.35c）

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

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

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

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

也就是說，圖像的同一個比特位的系數(shù)的集合就是一個二值圖像，稱為一個“位平面”。位平面編號從0開始，直到m-1。將m個位平面組合，顯然又可以恢復(fù)原來的灰度圖像。7.4.1位平面分解

舉例來說，對于一幅N×N的灰度圖像，若每個像素用m位表示，就可以從每個像素的二進制表示中取出相同位置上的一位，這樣就形成了一幅N×N的二值圖像，稱該二值圖像為原灰度圖像的一個位平面。

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

85灰度圖像圖7.138位圖像的位平面分解圖示7.4.1位平面分解

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

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

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

設(shè)反映灰度值大小的m位二進制編碼為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游程編碼——一維游程編碼

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

決定游程長度值最通常的約定是：（1）指定每一行第一個游程的值；（2）假設(shè)每一行從白色游程開始。如果該行是從黑色游程開始，則記這個游程長度為0。國際傳真標準CCITTT.4（G3）采用的是一維游程編碼。編碼方法是：游長的霍夫曼編碼分為形成碼和終止碼兩種。

（1）對于位于0～63之間的游長，用單個的碼字，即終止碼表示。

（2）對于大于63的游長，用一個形成碼和一個終止碼的組合來表示。其中，形成碼表示實際游長的64的最大倍數(shù)值，終止碼表示其余小于64的差值。

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

表7.4國際傳真標準ITU（CCITTT.4G3）終止碼表

游長白長碼字黑長碼字

000110101000011011110001110102011111310001041011011

5

1100

0011

6

1110

0010

┇

┇

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

表7.5國際傳真標準ITU（CCITTT.4G3）形成碼表

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

641101100000011111281001000011001000 192010111000011001001┇┇┇17280100110110000001100101

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

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

二維游程編碼是一種基于相對地址編碼原理的編碼方法，通過對黑白過渡點（從白到黑，或從黑到白后的一個比特位置稱為過渡點）相對于當前編碼行中參考像素的位置進行編碼，不僅利用了二值圖像中每一行內(nèi)相鄰像素的相關(guān)性，而且也利用了當前編碼行與參考行（前一行）的行間像素之間的相關(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ù)信息，進而達到壓縮數(shù)據(jù)的目的。7.6.1變換編碼的過程◆變換編碼過程由以下四步組成：（1）將待編碼的N×N的圖像分解成(N/n)2個大小為n×n的子圖像。通常選取的子圖像大小為8×8或16×16，即n等于８或16。（2）對每個子圖像進行正交變換（如DCT變換等），得到各子圖像的變換系數(shù)。這一步的實質(zhì)是把空間域表示的圖像轉(zhuǎn)換成頻率域表示的圖像。（3）對變換系數(shù)進行量化。（4）使用霍夫曼變長編碼或游程編碼等無損編碼器對量化的系數(shù)進行編碼，得到壓縮后的圖像（數(shù)據(jù)）。圖7.15變換編碼系統(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)用中，把圖像進一步分割成子圖像塊要求滿足以下兩個條件：一是相鄰子圖像塊之間的相關(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.39）(7.40)其中，H(x,y,u,v)稱為變換核函數(shù)，也稱為基函數(shù)或基圖像；式(7.40)中的T(u,v)稱為變換系數(shù)。

7.6.3變換的選擇

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

(7.41)其中，反變換核函數(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.41)定義的子圖像序列的一組基函數(shù)或基圖像。

(7.42)7.6.3變換的選擇

進一步將式(7.41)表示成：為：

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

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

(7.44)(7.45)那么，的一個截斷近似可定義為：顯然，利用的截斷功能就可消除掉式(7.42)中對求和貢獻最少的系數(shù)。7.6.3變換的選擇

2.圖像的均方差（續(xù)1）

且子圖像F和它的近似之間的均方誤差為：(7.46)也即有：

7.6.3變換的選擇

2.圖像的均方差（續(xù)2）(7.46)其中，是變換系數(shù)在(u,v)處的方差。

7.6.3變換的選擇

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

(7.40)7.6.3變換的選擇

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

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

◆變換編碼通常采用的變換包括：DCT(離散余弦變換)、DFT（離散傅里葉變換）、WHT（沃爾什-哈達瑪變換）和KLT（卡-洛變換）等實現(xiàn)。3.幾種變換的性能7.6.4變換系數(shù)的量化和編碼1.區(qū)域編碼

所謂區(qū)域編碼，就是只保留變換系數(shù)方陣中一個特定區(qū)域的系數(shù)，而將其它系數(shù)置零的一種編碼方法。圖7.15變換編碼系統(tǒng)框圖壓縮圖像構(gòu)造n×n個子圖像系數(shù)量化器正變換符號編碼器原始圖像數(shù)據(jù)量化方案(量化函數(shù)或量化表)編碼方案及表說明7.6.4變換系數(shù)的量化和編碼1.區(qū)域編碼◆區(qū)域編碼是保留低頻部分的系數(shù)而丟棄高頻部分的系數(shù)。也即保留系數(shù)方陣中左上角區(qū)域的若干系數(shù)，而將其余系數(shù)置為零。◆這種保留和置0也即量化過程。1111100011110000111000001100000010000000000000000000000000000000圖7.16典型的區(qū)域模板

7.6.4變換系數(shù)的量化和編碼◆典型的區(qū)域編碼量化模板：

1.區(qū)域編碼（續(xù)1）1110000011000000100000000000000000000000000000000000000000000000（a）只保留左上角的6個系數(shù)（b）只保留左上角的15個系數(shù)

7.6.4變換系數(shù)的量化和編碼

實現(xiàn)區(qū)域編碼要求的保留左上角特定區(qū)域系數(shù)的方法：

用區(qū)域模板中的各個數(shù)據(jù)（1或0）乘以變換系數(shù)，也即乘以將各子圖像進行變換后所得到的變換系數(shù)。

1761724810715817917115317217416313416716814814817117616716116915914713117617717016916312484961851791791598041587418518414372667575691821319010011611311410411383101114123116112130176172480000017217400000017100000000000000000000000000000000000000000000000圖7.16區(qū)域編碼均勻量化方法示例

7.6.4變換系數(shù)的量化和編碼

一般把如圖7.16所示的，這種僅用區(qū)域模板進行系數(shù)量化的方法稱為均勻量化。

變換系數(shù)量化（量化器——量化模板）的作用：

減少視覺心里冗余。

顯然由于量化，所以區(qū)域編碼是有損壓縮編碼。

1.區(qū)域編碼（續(xù)2）7.6.4變換系數(shù)的量化和編碼

1.區(qū)域編碼在進行均勻量化或非均勻量化后，還要對量化后的系數(shù)根據(jù)如圖7.18所示的順序重新編排成一個具有n2個元素的1×n2的系數(shù)序列（矢量）。也即，對量化后的系數(shù)進行矢量排序。

01561415272824713162629423812172530414391118243140445310192332394552542022333846515560213437475056596135364849575862637.6.4變換系數(shù)的量化和編碼

1.區(qū)域編碼

也就是把均勻量化或非均勻量化后的系數(shù)矩陣中的系數(shù)，排序成一維矢量形式。7.6.4變換系數(shù)的量化和編碼11155000001415000000120000000000000000000000000000000000000000000000011151412155

1.區(qū)域編碼

也就是把均勻量化或非均勻量化后的系數(shù)矩陣中的系數(shù)，排序成一維矢量形式。7.6.4變換系數(shù)的量化和編碼

利用霍夫曼變長編碼或游程編碼等無損編碼器方式，對量化得到的一維矢量形式的量化系數(shù)進行編碼。

1.區(qū)域編碼（續(xù)4）7.6.4變換系數(shù)的量化和編碼例7.9

區(qū)域變換編碼說明示例。

編碼過程：（1）子圖像尺寸選為8×8。

（2）采用DCT變換，得到變換系數(shù)。每一個子圖像經(jīng)過正向DCT變換轉(zhuǎn)換為一組（64個）DCT系數(shù)。（3）對變換系數(shù)進行區(qū)域編碼和均勻量化。

區(qū)域編碼的量化模板采用四種截斷方式，分別是截取子圖像的DCT系數(shù)結(jié)果方陣的左上角的1個分量、6個分量、15個分量和28個分量，其余分量為零。

(a)原圖像(b)僅由DC系數(shù)重構(gòu)的圖像(c)(a)與(b)的誤差圖像(d)最低6個系數(shù)的重構(gòu)圖像(e)最低15個系數(shù)的重構(gòu)圖像(f)最低28個系數(shù)的重構(gòu)圖像圖(b)、(d)、(e)、(f)分別是截取每個DCT系數(shù)量化結(jié)果方陣的左上角的1個、6個、15個和28個分量的重構(gòu)圖像。7.6.4變換系數(shù)的量化和編碼7.6.4變換系數(shù)的量化和編碼

（1）門限編碼概念

所謂門限編碼，就是僅采用非均勻量化方法對變換系數(shù)進行量化的方法。

2.門限編碼7.6.4變換系數(shù)的量化和編碼

（2）變換系數(shù)的非均勻量化方案

非均勻量化是指用圖7.20所示的亮度量化陣列或圖7.21所示的色度量化陣列中的值作為分母，除以8×8的變換系數(shù)矩陣的方法。

2.門限編碼7.6.4變換系數(shù)的量化和編碼

2.門限編碼

（2）變換系數(shù)的非均勻量化方案圖7.20亮度量化矩陣1611101624405161121214192658605514131624405769561417222951878062182237566810910377243555648110411392496478871031211201017292959811210010399圖7.21色度量化矩陣171824479999999918212666999999992426569999999999476699999999999999999999999999999999999999999999999999999999999999999999999999997.6.4變換系數(shù)的量化和編碼

（3）

變換系數(shù)的非均勻量化（門限編碼）函數(shù)

2.門限編碼其中：

是變換系數(shù)。

是對進行門限處理及