第三章 數(shù)據(jù)壓縮的基本技術(shù)

1、第3章 數(shù)據(jù)壓縮的基本技術(shù) 3.1 概述概述 3.2數(shù)據(jù)壓縮的理論依據(jù)數(shù)據(jù)壓縮的理論依據(jù)3.5預(yù)測(cè)編碼預(yù)測(cè)編碼3.6正交變換編碼正交變換編碼3.9量化量化3.10熵編碼熵編碼 3.1 概述概述 數(shù)據(jù)壓縮處理一般由兩個(gè)過(guò)程組成數(shù)據(jù)壓縮處理一般由兩個(gè)過(guò)程組成: 一是編碼過(guò)程一是編碼過(guò)程, 即對(duì)原始數(shù)據(jù)進(jìn)行編碼壓縮即對(duì)原始數(shù)據(jù)進(jìn)行編碼壓縮, 以便存儲(chǔ)和傳輸以便存儲(chǔ)和傳輸; 二是解二是解碼過(guò)程碼過(guò)程, 即對(duì)壓縮的數(shù)據(jù)進(jìn)行解壓即對(duì)壓縮的數(shù)據(jù)進(jìn)行解壓, 恢復(fù)成可用的數(shù)據(jù)?；謴?fù)成可用的數(shù)據(jù)。根據(jù)解壓后數(shù)據(jù)的保真度根據(jù)解壓后數(shù)據(jù)的保真度, 數(shù)據(jù)壓縮技術(shù)可分為數(shù)據(jù)壓縮技術(shù)可分為無(wú)損壓無(wú)損壓縮編碼縮編碼和和有損壓

2、縮編碼有損壓縮編碼兩大類(lèi)兩大類(lèi)。無(wú)損壓縮編碼無(wú)損壓縮編碼是指是指解碼后的數(shù)據(jù)與原始數(shù)據(jù)完全相同解碼后的數(shù)據(jù)與原始數(shù)據(jù)完全相同, 無(wú)任何偏差。這種無(wú)任何偏差。這種編碼通常基于信息熵原理編碼通?；谛畔㈧卦? 常用的編碼有哈夫曼編碼、常用的編碼有哈夫曼編碼、 算術(shù)編碼、算術(shù)編碼、 行程編碼等。行程編碼等。它的壓縮比通常比較低它的壓縮比通常比較低, 一般一般在在2 15 1。主要用于要求數(shù)據(jù)無(wú)損壓縮存儲(chǔ)。主要用于要求數(shù)據(jù)無(wú)損壓縮存儲(chǔ)和傳和傳輸?shù)膱?chǎng)合輸?shù)膱?chǎng)合, 如傳真機(jī)、文本文件傳輸?shù)?。如傳真機(jī)、文本文件傳輸?shù)取?有損壓縮編碼有損壓縮編碼是指解碼后的數(shù)據(jù)與原始數(shù)據(jù)相比是指解碼后的數(shù)據(jù)與原始數(shù)據(jù)相比有

3、一定的偏差有一定的偏差, 但仍可保持一定的視聽(tīng)質(zhì)量和效果。但仍可保持一定的視聽(tīng)質(zhì)量和效果。 它主要是在保持一定保真度下對(duì)數(shù)據(jù)進(jìn)行壓縮它主要是在保持一定保真度下對(duì)數(shù)據(jù)進(jìn)行壓縮, 其壓其壓縮比可達(dá)縮比可達(dá)100 1。 壓縮比愈高壓縮比愈高, 其解壓縮后的視、其解壓縮后的視、 音音頻質(zhì)量就愈低。編碼方法有：頻質(zhì)量就愈低。編碼方法有：基于線(xiàn)性預(yù)測(cè)原理的基于線(xiàn)性預(yù)測(cè)原理的預(yù)預(yù)測(cè)編碼測(cè)編碼、基于分量量化的、基于分量量化的量化編碼量化編碼、基于正交變換原、基于正交變換原理的理的正交變換編碼正交變換編碼、基于分層處理的、基于分層處理的分層編碼分層編碼以及基以及基于頻帶分割原理的于頻帶分割原理的子帶編碼子帶編碼

4、等等。主要用于。主要用于對(duì)音頻和視對(duì)音頻和視頻數(shù)據(jù)的壓縮。頻數(shù)據(jù)的壓縮。 多媒體信息編碼技術(shù)主要側(cè)重于有損壓縮編碼的研多媒體信息編碼技術(shù)主要側(cè)重于有損壓縮編碼的研究。究。 經(jīng)過(guò)多年的研究與開(kāi)發(fā)經(jīng)過(guò)多年的研究與開(kāi)發(fā), 已經(jīng)出臺(tái)了一系列有關(guān)的已經(jīng)出臺(tái)了一系列有關(guān)的國(guó)際標(biāo)準(zhǔn)。其中國(guó)際標(biāo)準(zhǔn)。其中, 最著名的是國(guó)際標(biāo)準(zhǔn)組織（最著名的是國(guó)際標(biāo)準(zhǔn)組織（ISO）制）制定的定的JPEG和和MPEG。JPEG是靜止圖像的壓縮標(biāo)準(zhǔn)是靜止圖像的壓縮標(biāo)準(zhǔn), 其其壓縮比可達(dá)壓縮比可達(dá)40 1。 MPEG（MPEG-1、 MPEG-2及及MPEG-4）是動(dòng)態(tài)圖像的壓縮標(biāo)準(zhǔn)）是動(dòng)態(tài)圖像的壓縮標(biāo)準(zhǔn), 采用采用MPEG-2標(biāo)準(zhǔn)標(biāo)

5、準(zhǔn)對(duì)對(duì)NTSC質(zhì)量視頻進(jìn)行壓縮后質(zhì)量視頻進(jìn)行壓縮后, 網(wǎng)絡(luò)帶寬需求可降低到網(wǎng)絡(luò)帶寬需求可降低到3.36 Mb/s。 其它的標(biāo)準(zhǔn)還有國(guó)際電信聯(lián)合會(huì)（其它的標(biāo)準(zhǔn)還有國(guó)際電信聯(lián)合會(huì)（ITU）制定的用于可視電話(huà)、制定的用于可視電話(huà)、 會(huì)議電視的會(huì)議電視的H.261和和H.263; 用用于音頻的于音頻的G.711、 G.721、 G.728等。等。 3.2數(shù)據(jù)壓縮的理論依據(jù)數(shù)據(jù)壓縮的理論依據(jù)離散信源X：信息源所產(chǎn)生的符號(hào)取自某一離散集合。每個(gè)符號(hào)的信息量I：指符號(hào)si出現(xiàn)的概率，I是隨機(jī)變量；最大離散熵定理最大離散熵定理熵（H）：各個(gè)符號(hào)信息量 I 的統(tǒng)計(jì)平均，是從統(tǒng)計(jì)平均的角度反映信源的一個(gè)總體特征符

6、號(hào)出現(xiàn)之前，熵表示符號(hào)出現(xiàn)的平均不肯定性；符號(hào)出現(xiàn)之后，熵表示接收一個(gè)符號(hào)所得到的平均信息量；各符號(hào)出現(xiàn)的概率分布不同，信源的熵也不同；當(dāng)信源符號(hào)出現(xiàn)的概率相等時(shí)，信源具有最大熵，每個(gè)符號(hào)攜帶的平均信息量最大。最大離散熵定理，在熵編碼時(shí)，可以確保每個(gè)符號(hào)攜帶最大的信息量。3.2.2信源的相關(guān)性與序列熵的關(guān)系信源的相關(guān)性與序列熵的關(guān)系平穩(wěn)序列平穩(wěn)序列：序列中的各符號(hào)有相同的概率分布；：序列中的各符號(hào)有相同的概率分布；無(wú)記憶序列無(wú)記憶序列：序列中的各符號(hào)間為統(tǒng)計(jì)獨(dú)立；：序列中的各符號(hào)間為統(tǒng)計(jì)獨(dú)立；聯(lián)合熵聯(lián)合熵：又稱(chēng)：又稱(chēng)序列熵序列熵，隨機(jī)序列中包含兩個(gè)符號(hào)，隨機(jī)序列中包含兩個(gè)符號(hào)X、Y， X、Y取

7、自各自的離散信源，則新序列的平均信息量為取自各自的離散信源，則新序列的平均信息量為獨(dú)立熵獨(dú)立熵：離散信源：離散信源X、Y如果統(tǒng)計(jì)獨(dú)立，則如果統(tǒng)計(jì)獨(dú)立，則H（X）、）、H（Y）稱(chēng)為獨(dú)立熵。）稱(chēng)為獨(dú)立熵。此時(shí)有：此時(shí)有：給定給定X的條件下，的條件下，Y所具有的熵，稱(chēng)為所具有的熵，稱(chēng)為條件熵條件熵聯(lián)合熵與條件熵的關(guān)系：聯(lián)合熵與條件熵的關(guān)系：互信息互信息：無(wú)條件熵和條件熵之差，反映兩個(gè)事件之間的：無(wú)條件熵和條件熵之差，反映兩個(gè)事件之間的相關(guān)性。相關(guān)性?；バ畔⒃叫?，兩個(gè)事件的相關(guān)性越小，當(dāng)統(tǒng)計(jì)獨(dú)立時(shí)，互信息越小，兩個(gè)事件的相關(guān)性越小，當(dāng)統(tǒng)計(jì)獨(dú)立時(shí)，聯(lián)合熵為獨(dú)立熵之和，聯(lián)合熵達(dá)到最大值。聯(lián)合熵為獨(dú)立熵之和

8、，聯(lián)合熵達(dá)到最大值。應(yīng)用意義應(yīng)用意義：數(shù)據(jù)壓縮的一個(gè)基本途徑就是去除信源符號(hào)之間的數(shù)據(jù)壓縮的一個(gè)基本途徑就是去除信源符號(hào)之間的相關(guān)性，盡可能使得信源符號(hào)統(tǒng)計(jì)獨(dú)立，使序列成為相關(guān)性，盡可能使得信源符號(hào)統(tǒng)計(jì)獨(dú)立，使序列成為無(wú)記憶序列。無(wú)記憶序列。無(wú)記憶序列有最大的聯(lián)合熵，保證每個(gè)符號(hào)所獨(dú)立攜帶無(wú)記憶序列有最大的聯(lián)合熵，保證每個(gè)符號(hào)所獨(dú)立攜帶的信息量最大，傳送相同的信息量所需要的序列長(zhǎng)度越短，的信息量最大，傳送相同的信息量所需要的序列長(zhǎng)度越短，從而達(dá)到數(shù)據(jù)壓縮的目的。從而達(dá)到數(shù)據(jù)壓縮的目的。最大離散熵定理，告訴我們，在等概率情況下，離散平穩(wěn)最大離散熵定理，告訴我們，在等概率情況下，離散平穩(wěn)無(wú)記憶信源

9、的單個(gè)符號(hào)有最大熵，數(shù)據(jù)壓縮的另一途徑是無(wú)記憶信源的單個(gè)符號(hào)有最大熵，數(shù)據(jù)壓縮的另一途徑是改變離散信源的概率分布，比如：霍夫曼編碼；改變離散信源的概率分布，比如：霍夫曼編碼；幾種常用的壓縮編碼方法幾種常用的壓縮編碼方法（差分）預(yù)測(cè)編碼（離散余弦）正交變換編碼量化編碼熵編碼 3.5.1 差分脈沖編碼調(diào)制差分脈沖編碼調(diào)制 圖圖 2.2 DPCM編碼、解碼器原理框圖編碼、解碼器原理框圖差分信息差分信息（通過(guò)預(yù)測(cè)和差分，將（通過(guò)預(yù)測(cè)和差分，將x(n)轉(zhuǎn)化成差分信轉(zhuǎn)化成差分信息息e(n),降低了信息冗余，實(shí)現(xiàn)壓縮）降低了信息冗余，實(shí)現(xiàn)壓縮）)( nx)(nx)( )()(nxnxne線(xiàn)性預(yù)測(cè)器：線(xiàn)性預(yù)測(cè)

10、器：)( nx3.5預(yù)測(cè)編碼預(yù)測(cè)編碼信息發(fā)送端的預(yù)測(cè)與差分的示意圖信息發(fā)送端的預(yù)測(cè)與差分的示意圖差分值差分值原信息值原信息值預(yù)測(cè)值預(yù)測(cè)值其中，e(n)x(n)，實(shí)現(xiàn)數(shù)據(jù)幅值方面的壓縮；信道只傳送：差分值與有限的幾個(gè)初始值；有限的幾個(gè)有限的幾個(gè)初始值初始值信息接收端的信息重建的示意圖信息接收端的信息重建的示意圖接收到的接收到的差分值差分值重建的信息值重建的信息值重建的預(yù)測(cè)值重建的預(yù)測(cè)值接收到的接收到的初始值初始值有限的幾個(gè)初始值，用于重建預(yù)測(cè)值；3.5.2 序列圖像中運(yùn)動(dòng)矢量的估值序列圖像中運(yùn)動(dòng)矢量的估值 運(yùn)動(dòng)補(bǔ)償預(yù)測(cè)編碼，是一種主要用于動(dòng)態(tài)圖像的壓縮的預(yù)測(cè)編碼。動(dòng)態(tài)圖像是由一系列視頻幀組成,

11、幀與幀之間可能存在著瞬時(shí)冗余, 這種瞬時(shí)冗余主要是由靜態(tài)背景前的運(yùn)動(dòng)物體或攝像機(jī)的移動(dòng)引起的。運(yùn)動(dòng)補(bǔ)償預(yù)測(cè)編碼主要通過(guò)幀間編碼來(lái)壓縮時(shí)間冗余信息。 其基本原理如下: 在視頻幀序列中設(shè)置參考幀（I幀）, 且第1幀總是參考幀。 對(duì)于當(dāng)前的編碼幀, 首先在該幀的前幀和/或后幀（參照幀）中尋找與該幀的一個(gè)圖像塊相匹配的圖像塊（匹配塊），按照式3-47、3-48、3-49，進(jìn)行塊匹配計(jì)算。 幀內(nèi)編碼幀間預(yù)測(cè)編碼 如果找到這樣的匹配塊, 則進(jìn)行下列計(jì)算: 當(dāng)前塊的塊亮度值與參照幀中對(duì)應(yīng)塊（稱(chēng)參照塊）的塊亮度值之間的差值信號(hào); （背景差）當(dāng)前塊相對(duì)于參照塊在x和y兩個(gè)方向上的運(yùn)動(dòng)向量值, 表示該塊在x和y方

12、向上的平移。 通過(guò)定義一個(gè)搜索域來(lái)限制x和y方向上的搜索范圍, 以降低運(yùn)動(dòng)信息的開(kāi)銷(xiāo); （運(yùn)動(dòng)估值）用差值信號(hào)和運(yùn)動(dòng)向量值來(lái)表示參照塊與所預(yù)測(cè)塊之間的誤差, 稱(chēng)為預(yù)測(cè)誤差。 這時(shí), 只需對(duì)當(dāng)前塊的預(yù)測(cè)誤差（運(yùn)動(dòng)向量值、差值信號(hào)）進(jìn)行編碼, 不必對(duì)當(dāng)前塊的圖像進(jìn)行編碼, 以壓縮時(shí)間冗余信息。 如果找不到這樣的匹配塊, 則必須進(jìn)行幀內(nèi)編碼, 即對(duì)當(dāng)前塊的圖像進(jìn)行編碼。 運(yùn)動(dòng)補(bǔ)償預(yù)測(cè)編碼可分成下列三種方式: 單向運(yùn)動(dòng)補(bǔ)償預(yù)測(cè): 只使用前參照幀或后參照幀之一進(jìn)行預(yù)測(cè)。 雙向運(yùn)動(dòng)補(bǔ)償預(yù)測(cè): 使用前、 后兩個(gè)幀作為參照幀來(lái)計(jì)算各塊的運(yùn)動(dòng)向量, 最后只選擇具有最小匹配誤差的參照幀相關(guān)的運(yùn)動(dòng)向量值。 插值運(yùn)動(dòng)

13、補(bǔ)償預(yù)測(cè): 使用前參照幀和后參照幀兩者預(yù)測(cè)值的平均值。這時(shí), 必須分別存儲(chǔ)和傳輸這兩個(gè)運(yùn)動(dòng)向量。 3.6.2離散余弦變換編碼離散余弦變換編碼 1、正交變換、正交變換彼此之間線(xiàn)性無(wú)關(guān)為正交基向量,i如：傅氏變換的基向量，就是一個(gè)正交（酉）變換基；正交變換：正交變換：重構(gòu)：重構(gòu)： 屬于正交變換編碼，選擇不同的正交基向量，可以得到不同的正交變換。變換編碼主要有離散傅立葉變換(DFT)編碼、 離散余弦變換(DCT)編碼等。其中, DCT編碼方法被普遍使用, 在JPEG、 MPEG和H.261等標(biāo)準(zhǔn)中都采用了DCT編碼。由于聲音信號(hào)只有一個(gè)時(shí)間維, 因此音頻信號(hào)壓縮采用一維DCT編碼, 而圖像壓縮必須考

14、慮水平和垂直兩個(gè)方向, 因此圖像壓縮則采用二維DCT編碼。2、DCT編碼編碼 DCT編碼方法是對(duì)一個(gè)88圖像塊灰度樣本數(shù)據(jù)流進(jìn)行壓縮, 而彩色圖像壓縮可看成是壓縮圖像的多個(gè)分量。在編碼器中, 首先將源圖像88樣本數(shù)據(jù)塊（像素塊）的取值范圍由0, 2p-1（無(wú)符號(hào)）轉(zhuǎn)換成-2p-1, 2p-1-1（有符號(hào)）, 其中p為樣本定義的精度。 然后對(duì)88樣本數(shù)據(jù)塊進(jìn)行正向離散余弦變換（FDCT）。在解碼器中, 利用逆向離散余弦變換（IDCT）重建88樣本數(shù)據(jù)塊, 恢復(fù)圖像。 FDCT和IDCT的數(shù)學(xué)表達(dá)式如(1)式和(2)式所示: NvkNujvuSvCuCNkjsNvkNujkjsvCuCNuSNuN

15、vNjNk2) 12(cos2) 12(cos),()()(2),(2) 12(cos2) 12(cos),()()(2),(10101010式中： 121)()(vCuCu,v=0其它 二維二維DCT變換變換系數(shù)代表直流分量；，這時(shí)對(duì)應(yīng)的時(shí)，兩個(gè)余弦項(xiàng)均為零注意：對(duì)于DCT0 vu基函數(shù)基函數(shù)DCT系數(shù)系數(shù)直流成份 源圖像88樣本數(shù)據(jù)塊實(shí)質(zhì)上是64點(diǎn)離散信號(hào)（空間范圍x和y的函數(shù)）, FDCT將其變換成64個(gè)正交基信號(hào), FDCT的輸出是64個(gè)DCT系數(shù)（即：基信號(hào)振幅）。由于圖像幀上點(diǎn)與點(diǎn)之間的樣本值變化比較緩慢, 大多數(shù)信號(hào)集中在低頻區(qū)。 可以刪去DCT系數(shù)中的高頻分量，僅用低頻分量子集

16、，逆DCT變換來(lái)重構(gòu)原圖像，不會(huì)引起明顯誤差，從而實(shí)現(xiàn)數(shù)據(jù)壓縮。二維DCT變換將基系數(shù)絕對(duì)值10的分量置零 （DCT截?cái)嗔炕┒S逆DCT變換 重構(gòu)圖像（數(shù)據(jù)壓縮程度較小） 圖像清晰（截?cái)嗔炕`差較?。┰瓐D像對(duì)對(duì)DCT數(shù)據(jù)的截?cái)嗔炕疽鈭D數(shù)據(jù)的截?cái)嗔炕疽鈭D1二維DCT變換將基系數(shù)絕對(duì)值(10101101) 2十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)低位數(shù)碼低位數(shù)碼高位數(shù)碼高位數(shù)碼對(duì)于離散無(wú)記憶信源，只要各符號(hào)出現(xiàn)的概率不相等，對(duì)于離散無(wú)記憶信源，只要各符號(hào)出現(xiàn)的概率不相等，該信源就還有冗余存在，還可以進(jìn)一步壓縮。該信源就還有冗余存在，還可以進(jìn)一步壓縮。霍夫曼霍夫曼(Huffman)編碼是

17、一種無(wú)損壓縮編碼方法。編碼是一種無(wú)損壓縮編碼方法。它是它是一種概率平衡的思想。一種概率平衡的思想。按信源符號(hào)出現(xiàn)的概率大小進(jìn)行按信源符號(hào)出現(xiàn)的概率大小進(jìn)行排序。排序。出現(xiàn)概率大的符號(hào)分配短碼出現(xiàn)概率大的符號(hào)分配短碼, 反之，反之，出現(xiàn)概率小出現(xiàn)概率小的符號(hào)的符號(hào)分配長(zhǎng)碼。分配長(zhǎng)碼。這樣可以確保編碼序列中的每個(gè)符號(hào)這樣可以確保編碼序列中的每個(gè)符號(hào)等概率出現(xiàn)，從而滿(mǎn)足等概率出現(xiàn)，從而滿(mǎn)足最大離散熵定理最大離散熵定理。1.霍夫曼編碼霍夫曼編碼3.10熵編碼熵編碼霍夫曼(Huffman)熵編碼的一個(gè)應(yīng)用實(shí)例平均碼長(zhǎng)平均碼長(zhǎng)越短，數(shù)據(jù)量越小，數(shù)據(jù)率越低；例：例：對(duì)于一個(gè)對(duì)于一個(gè)4電平量化（電平量化（4個(gè)符號(hào)）的信源個(gè)符號(hào)）的信源則，信源熵H=1.75比特/符號(hào)經(jīng)計(jì)算可知，編碼方式I：平均碼長(zhǎng)為2.0比特/符號(hào)；編碼方式II：平均碼長(zhǎng)為1.75比特/符號(hào)，等于信源熵，達(dá)到最大；在分配代碼過(guò)程中, 需要建立一個(gè)n階二叉樹(shù), 如下: 對(duì)信源符號(hào)按其出現(xiàn)的概率進(jìn)行遞減排序; 將兩個(gè)最小的概率相加, 其和作為合成事件的概率; 重復(fù)和, 直到概率之和達(dá)到1為止; 每次合并消息時(shí), 將被合并的消息賦予1和0或者0和1; 尋找從每