數(shù)據(jù)壓縮技術(shù)課件

第5章多媒體技術(shù)MULTIMEDIATECHNOLOGY1第5章多媒體技術(shù)MULTIMEDIATECHNOLOGY1第5

章多媒體數(shù)據(jù)壓縮技術(shù)5.1數(shù)據(jù)壓縮基本原理

5.1.1信息、數(shù)據(jù)與編碼

5.1.2數(shù)據(jù)壓縮的條件

5.1.3數(shù)據(jù)冗余5.2數(shù)據(jù)壓縮算法

5.2.1數(shù)據(jù)壓縮算法分類

5.2.2預(yù)測編碼原理

5.2.3變換編碼原理

5.2.4統(tǒng)計編碼原理

5.2.5霍夫曼編碼原理

5.2.6行程編碼原理5.2.7算術(shù)編碼原理

5.2.8LZW壓縮編碼5.3靜態(tài)圖像JPEG壓縮編碼技術(shù)

5.3.1JPEG標(biāo)準(zhǔn)的由來

5.3.2JPEG壓縮算法

5.3.3無失真預(yù)測編碼

5.3.4有失真DCT壓縮編碼5.4動態(tài)圖像MPEG壓縮編碼技術(shù)

5.4.1基本原理

5.4.2MPEG技術(shù)標(biāo)準(zhǔn)2第5章多媒體數(shù)據(jù)壓縮技術(shù)5.1數(shù)據(jù)壓縮基本原理數(shù)據(jù)壓縮基本原理5.1數(shù)據(jù)壓縮的對象是數(shù)據(jù)。數(shù)據(jù)是信息的載體，用來記錄和傳送信息。真正有用的不是數(shù)據(jù)本身，而是數(shù)據(jù)所攜帶的信息。大的數(shù)據(jù)量并不代表含有大的信息量。而對于去掉冗余的數(shù)據(jù)對信息沒有本質(zhì)的影響稱為壓縮?！駭?shù)據(jù)壓縮原理3數(shù)據(jù)壓縮基本原理5.1數(shù)據(jù)壓縮的對象是數(shù)據(jù)。數(shù)據(jù)是信息的載體5.1.1信息、數(shù)據(jù)與編碼我們了解的東西，描述它用的信息量少，不了解的東西，描述它用的信息量大。在信息論中，可以說：信息是用不確定的度量來定義的；一個消息的可能性越小，其信息含量越大；消息的可能性越大，則信息含量越小。例自然現(xiàn)象45.1.1信息、數(shù)據(jù)與編碼我們了解的東西，描述它用的信息數(shù)據(jù)壓縮基本原理5.15.1.1信息、數(shù)據(jù)與編碼1．信息和熵●信息量的大小和消息有一定的關(guān)系。在數(shù)學(xué)上，消息是其出現(xiàn)概率的單調(diào)下降函數(shù)。信息量越大，消息的可能性越小，反之亦然?！裥畔⒘浚簽榱藦腘個相等的可能事件中挑選出一個事件所需的信息度量和含量，所提問“是或否”的次數(shù)。也就是說，在N個事件中辨識特定的一個事件要詢問“是或否”次數(shù)。要從256個數(shù)中選定某一個數(shù)，可以先提問“是否大于128？”，不論回答是與否，則半數(shù)的可能事件被取消。如果繼續(xù)詢問下去，每次詢問將對應(yīng)一個1bit的信息量。例5數(shù)據(jù)壓縮基本原理5.15.1.1信息、數(shù)據(jù)與編碼1．信息例●隨著每次詢問，有半數(shù)的可能事件被取消，這個過程由公式表示：可看出：對于256個數(shù)的詢問只要進(jìn)行8次，即可確定一個具體的數(shù)。設(shè)：從N個數(shù)中選定任意一個數(shù)x的概率為p(x)，假定選定任意一個數(shù)的概率都相等，即p(x)=1/N，則信息量為：log2256=8bit如果將信息源所有可能事件的信息量進(jìn)行平均，即可得到信息的“熵”(熵是平均信息量)，信息源X的符號集為xi(i=1,2,…,N)。設(shè)：xi出現(xiàn)的概率為p(xi)，則信息源X的熵為：I(x)=log2N=-log21／N=-log2p(x)=I[p(x)]H(x)=P(xi)log2p(xi)∑P(xi)I[p(xi)]=-∑ni=1ni=16例●隨著每次詢問，有半數(shù)的可能事件被取消，這個過程由公式表示信息與數(shù)據(jù)2.信息可以用函數(shù)表示，該函數(shù)由信息論創(chuàng)始人C.E.Shannon香農(nóng)提出，以概率論的觀點(diǎn)對信息進(jìn)行定量描述，具體的信息函數(shù)表達(dá)式為：I(ai)=-log2Pi(i=1,2,…,r)公式中，Pi(i

=1,2,…,r)是隨機(jī)消息組合X{a1,a2,…,ar}中的消息ai(i

=1,2,…,r)的先驗概率。Pi

可以度量ai(i

=1,2,…,r)所含的信息量。而I(ai)(i=1,2,…,r)在X的先驗概率空間P{p1,p2,…,pr}中的統(tǒng)計平均值為信息源X的熵：信息源X的熵用來度量X中每種消息所包含的平均信息量。信息熵主要表示信息系統(tǒng)的有序程度，而不是熱力學(xué)中系統(tǒng)的無序程度。H(X)=H{p1,p2,…,pr}=-Pilog2pi∑ni=17信息與數(shù)據(jù)2.信息可以用函數(shù)表示，該函數(shù)由信息論創(chuàng)始人C.E例2-1設(shè)信源有16種符號，其出現(xiàn)的概率相同，即P（Xi）=1/16。計算其平均信息熵。例8例2-1設(shè)信源有16種符號，其出現(xiàn)的概率相同，即P（Xi

例2-2某信源有8種符號，其出現(xiàn)的概率如下：例9例2-2某信源有8種符號，其出現(xiàn)的概率如下：例9信源中含有自然冗余度，這些冗余度既來自于信源本身的相關(guān)性，又來自于信源概率分布的不均勻性，只要找到去除相關(guān)性或改變概率分布不均勻性的手段和方法，也就找到了信息熵編碼的方法。但信源所含有的平均信息量（熵）是進(jìn)行無失真編碼的理論的極限，只要不低于此極限，就能找到某種適宜的編碼方法，去逼近信息熵，實現(xiàn)數(shù)據(jù)壓縮。香儂理論的要點(diǎn)2.10信源中含有自然冗余度，這些冗余度既來自于信源本身的相關(guān)性，又多媒體信息的數(shù)據(jù)量3.1)文本

——假設(shè)屏幕顯示分辨率為1024×768，字符為16×16點(diǎn)陣，每個字符用4個字節(jié)表示，則顯示一屏字符所需要的存儲空間為：（1024/16）×（768/16）×4B=12288B（約合12KB）2)圖像

——假定圖像顯示在1024×768分辨率的屏幕上，則滿屏幕像點(diǎn)所占用的空間為：

1024×768×log2256=768KB3)音頻

——假定模擬聲音頻率22050Hz，其數(shù)字采樣頻率44100Hz，采樣精度為16bit，雙聲道立體聲模式，則1min所需數(shù)據(jù)量為：

44100Hz×2B(16bit采樣精度)×2(雙聲道)×60s=10MB/min4)視頻

——采用帶寬為5MHz的PAL制視頻信號，掃描速度25幀/s，樣本寬度24bit，采樣頻率最低10MHz，則一幀數(shù)字化圖像所占用的最少存儲空間為：

10(采樣頻率)÷25(掃描速度)×24(樣本寬度)=9.6Mbit(合1.2MB)11多媒體信息的數(shù)據(jù)量3.1)文本——假設(shè)屏幕顯示分辨率為考慮一張640×480的全彩影像

640×480×3×8=7,372,800Bits

調(diào)制解調(diào)器(Modem)為

36Kbps

7372800/36000=204.8(sec)=3.41(min)

假設(shè)壓縮算法(JPEG)的壓縮率為1:12

(7372800/12)/36000=17.1(sec)

對圖片壓縮效果較好，但對色彩單純的圖形則效果一般不很理想。

例12考慮一張640×480的全彩影像

640×數(shù)據(jù)壓縮的條件5.1.2●

數(shù)據(jù)冗余度(重復(fù)數(shù)據(jù)、可忽略數(shù)據(jù))●

信息傳輸與存儲的限制(壓縮→傳輸或存儲→解壓縮)■44.1kHz/Stereo1.3MB■22.0kHz/Mono0.3MB■Stop重復(fù)數(shù)據(jù)可忽略數(shù)據(jù)●

人類不敏感因素(顏色、亮度、細(xì)節(jié)等)224顏色(16,777,216色)28顏色(256色)●音頻不敏感因素(試聽)●

顏色不敏感因素13數(shù)據(jù)壓縮的條件5.1.2●數(shù)據(jù)冗余度(重復(fù)數(shù)據(jù)、可忽略數(shù)數(shù)據(jù)冗余5.1.3●

冗余基本概念●

冗余

——信息所具有的各種性質(zhì)中多余的無用空間●

冗余度

——多余的無用空間的程度I=D－duI—信息量D—數(shù)據(jù)量du—冗余量，包含在D中●

信息量與冗余的關(guān)系●

冗余舉例播音員——180字/分鐘，2Byte一個字，360Byte

(合0.35KB/分鐘)音頻數(shù)據(jù)——8kHz采樣×8bit×60秒=3840KBit(合480KB/分鐘)14數(shù)據(jù)冗余5.1.3●冗余基本概念●冗余——信息所具有冗余分類●[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余——視頻與動畫畫面間的相關(guān)性[3]統(tǒng)計冗余——具有空間冗余和時間冗余[6]視覺冗余——視覺、聽覺敏感度和非線性感覺[7]知識冗余——憑借經(jīng)驗識別[4]結(jié)構(gòu)冗余——規(guī)則紋理、相互重疊的結(jié)構(gòu)表面[5]信息熵冗余——編碼冗余，數(shù)據(jù)與攜帶的信息[8]其他冗余——上述7種以外的冗余15冗余分類●[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余——視頻與動畫畫面間的相關(guān)性[3]統(tǒng)計冗余——具有空間冗余和時間冗余[6]視覺冗余——視覺、聽覺敏感度和非線性感覺[7]知識冗余——憑借經(jīng)驗識別[4]結(jié)構(gòu)冗余——規(guī)則紋理、相互重疊的結(jié)構(gòu)表面[5]信息熵冗余——編碼冗余，數(shù)據(jù)與攜帶的信息[8]其他冗余——上述7種以外的冗余●16冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余——視頻與動畫畫面間的相關(guān)性[3]統(tǒng)計冗余——具有空間冗余和時間冗余[6]視覺冗余——視覺、聽覺敏感度和非線性感覺[7]知識冗余——憑借經(jīng)驗識別[4]結(jié)構(gòu)冗余——規(guī)則紋理、相互重疊的結(jié)構(gòu)表面[5]信息熵冗余——編碼冗余，數(shù)據(jù)與攜帶的信息[8]其他冗余——上述7種以外的冗余●17冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余——視頻與動畫畫面間的相關(guān)性[3]統(tǒng)計冗余——具有空間冗余和時間冗余[6]視覺冗余——視覺、聽覺敏感度和非線性感覺[7]知識冗余——憑借經(jīng)驗識別[4]結(jié)構(gòu)冗余——規(guī)則紋理、相互重疊的結(jié)構(gòu)表面[5]信息熵冗余——編碼冗余，數(shù)據(jù)與攜帶的信息[8]其他冗余——上述7種以外的冗余●18冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余——視頻與動畫畫面間的相關(guān)性[3]統(tǒng)計冗余——具有空間冗余和時間冗余[6]視覺冗余——視覺、聽覺敏感度和非線性感覺[7]知識冗余——憑借經(jīng)驗識別[4]結(jié)構(gòu)冗余——規(guī)則紋理、相互重疊的結(jié)構(gòu)表面[5]信息熵冗余——編碼冗余，數(shù)據(jù)與攜帶的信息[8]其他冗余——上述7種以外的冗余10110001110010110001110001011010101010111100010111111010●19冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余——視頻與動畫畫面間的相關(guān)性[3]統(tǒng)計冗余——具有空間冗余和時間冗余[6]視覺冗余——視覺、聽覺敏感度和非線性感覺[7]知識冗余——憑借經(jīng)驗識別[4]結(jié)構(gòu)冗余——規(guī)則紋理、相互重疊的結(jié)構(gòu)表面[5]信息熵冗余——編碼冗余，數(shù)據(jù)與攜帶的信息[8]其他冗余——上述7種以外的冗余224色28色●20冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余——視頻與動畫畫面間的相關(guān)性[3]統(tǒng)計冗余——具有空間冗余和時間冗余[6]視覺冗余——視覺、聽覺敏感度和非線性感覺[7]知識冗余——憑借經(jīng)驗識別[4]結(jié)構(gòu)冗余——規(guī)則紋理、相互重疊的結(jié)構(gòu)表面[5]信息熵冗余——編碼冗余，數(shù)據(jù)與攜帶的信息[8]其他冗余——上述7種以外的冗余●印度金廟泰姬陵21冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間冗余——視頻與動畫畫面間的相關(guān)性[3]統(tǒng)計冗余——具有空間冗余和時間冗余[6]視覺冗余——視覺、聽覺敏感度和非線性感覺[7]知識冗余——憑借經(jīng)驗識別[4]結(jié)構(gòu)冗余——規(guī)則紋理、相互重疊的結(jié)構(gòu)表面[5]信息熵冗余——編碼冗余，數(shù)據(jù)與攜帶的信息[8]其他冗余——上述7種以外的冗余聲音頻率文字組句色彩漸變主觀意識::●22冗余分類[1]空間冗余——規(guī)則物體的物理相關(guān)性[2]時間數(shù)據(jù)壓縮算法5.25.2.1數(shù)據(jù)壓縮算法分類●

無損壓縮編碼

——壓縮數(shù)據(jù)還原后，與原始數(shù)據(jù)一致，無損失。(可逆編碼)霍夫曼編碼行程編碼算術(shù)編碼……●

有損壓縮編碼

——壓縮后再還原的數(shù)據(jù)有損失。(不可逆編碼)預(yù)測編碼變換編碼統(tǒng)計編碼行程編碼算數(shù)編碼LZW編碼……壓縮比：2:1～5:1壓縮比：≤1：10023數(shù)據(jù)壓縮算法5.25.2.1數(shù)據(jù)壓縮算法分類●無損壓縮視頻壓縮算法結(jié)構(gòu)圖●視頻壓縮無損壓縮有損壓縮霍夫曼編碼行程編碼算術(shù)編碼LZW編碼預(yù)測編碼變換編碼模型編碼基于重要性混合編碼DPCMADPCM運(yùn)動編碼DCT變換小波變換子帶編碼分形變換濾波子采樣矢量量化H.261MPEG24視頻壓縮算法結(jié)構(gòu)圖●視頻無損有損霍夫曼編碼預(yù)測編碼DPCMD預(yù)測編碼原理5.2.2●預(yù)測編碼——有損壓縮編碼，主要對統(tǒng)計冗余進(jìn)行壓縮。1．預(yù)測編碼的基本原理用原樣本值對新樣本進(jìn)行預(yù)測，得到新樣本的預(yù)測值。接著，取新樣本的實際值和預(yù)測值進(jìn)行比較，二者相減得到差值，然后對差值進(jìn)行編碼。2．預(yù)測編碼的應(yīng)用預(yù)測編碼用于圖像的傳輸和存儲。對于連續(xù)的多幀圖像，新一幀通常保留前一幀的部分內(nèi)容。首先存儲當(dāng)前內(nèi)容，如像點(diǎn)、幀或線。然后與下一幀圖像進(jìn)行比較（預(yù)測），把不同點(diǎn)存儲或傳輸，而相同點(diǎn)則是數(shù)據(jù)冗余，予以剔除。對于語音，就是通過預(yù)測去除語音信號時間上的相關(guān)性。例如語音中的LPC(linearPredictiveCoding，線性預(yù)測)。例25預(yù)測編碼原理5.2.2●預(yù)測編碼——有損壓縮編碼，主要變換編碼原理5.2.3●變換編碼(Transformcoding)

有損壓縮編碼，用于對統(tǒng)計冗余(圖像數(shù)據(jù))的壓縮?！窆ぷ髟硎紫葘r域上的信號進(jìn)行函數(shù)運(yùn)算，并變換到頻域上，然后在頻域上對變換后的信號進(jìn)行編碼。在頻域上，信息是按照頻譜的能量和頻率分布進(jìn)行排列的?？ê稀诎７蜃儞Q離散傅里葉變換離散余弦變換WHT變換例如，聲音中的頻譜分析實際上是對語音波形進(jìn)行了快速傅里葉變換（FFT），將時域信號變到了頻域中，可以清楚地看到能量集中在哪些頻率范圍內(nèi)。例26變換編碼原理5.2.3●變換編碼(Transformc5.2.4統(tǒng)計編碼原理

統(tǒng)計編碼

——無損壓縮編碼。根據(jù)消息出現(xiàn)的概率分布特性，在消息和碼字之間確定嚴(yán)格的對應(yīng)關(guān)系，以便準(zhǔn)確無誤地恢復(fù)數(shù)據(jù)。一般而言，圖像中某些數(shù)據(jù)出現(xiàn)概率比較高，而另一些出現(xiàn)概率較低。對出現(xiàn)概率高的數(shù)據(jù)分配短碼，對出現(xiàn)概率低的數(shù)據(jù)分配長碼。此種方式不舍棄數(shù)據(jù)冗余，只改變編碼分配的長度，因此總數(shù)據(jù)流量降低。275.2.4統(tǒng)計編碼原理統(tǒng)計編碼——霍夫曼編碼原理5.2.5●

霍夫曼編碼——無損編碼?！?/p>

編碼特點(diǎn)[1]編碼長度可變，壓縮與解壓縮較慢。[2]硬件實現(xiàn)困難。[3]編碼效率取決于信號源的數(shù)據(jù)出現(xiàn)概率。●

編碼原理——出現(xiàn)頻率高的數(shù)據(jù)編碼長度短，反之亦然。[1]信號源的數(shù)據(jù)按照出現(xiàn)概率遞減的順序排列。[2]合并兩個最小出現(xiàn)概率，作為新數(shù)據(jù)出現(xiàn)概率。[3]重復(fù)進(jìn)行[1][2]，直至概率相加為1為止。[4]合并運(yùn)算時，概率大者取0，概率小者取1。[5]記錄概率為1處到信號源的0、1序列。28霍夫曼編碼原理5.2.5●霍夫曼編碼——無損編碼?！裨O(shè)信號源為X={、a、e、I、m、t、c、h、r}。對應(yīng)的概率為p={O.22、0.22、0.14、O.07、0.07、0.07、0.07、0.07、0.07},試給出該信源的霍夫曼編碼方案。解：

若傳送一個串字符串“Iamateacher”，共14個字符。若用ASCII傳送，每個字符8位，共需112位。該字符串中有9個不同的符號，至少需要4位二進(jìn)制才能表示，這樣傳送該字符串也要56位。若用剛計算的Huffman編碼，只需要42位?；舴蚵幋a舉例●︺29設(shè)信號源為X={、a、e、I、m、t、c、h、r霍夫曼編碼過程

●可以得到：

a的編碼00e的編碼111I的編碼1101m的編碼1100t的編碼1011c的編碼1010h的編碼1001r的編碼1000原字符串（二進(jìn)制）長度：=112（14×8）位Huffman編碼長度：=42位（0100111110111001011101010011000）30霍夫曼編碼過程●可以得到：30行程編碼原理5.2.6●行程編碼（RunLengthCoding）——無損壓縮編碼。例一個字符串：5555557777733322221111111行程編碼：(5,6)(7,5)(3,3)(2,4)(1,7)可見，行程編碼的位數(shù)遠(yuǎn)遠(yuǎn)少于原始字符串的位數(shù)?！窕驹碛靡粋€符號值或串代替具有相同值的連續(xù)符號，使符號長度少于原始數(shù)據(jù)的長度。在對圖像數(shù)據(jù)進(jìn)行編碼時，沿一定方向排列的，具有相同灰度值的像素被看成是連續(xù)符號，并用字串代替這些連續(xù)符號，可大幅度減少數(shù)據(jù)量。31行程編碼原理5.2.6●行程編碼（RunLengthC設(shè)有數(shù)據(jù)流“AAABBBBCCCCCDAAAAAA”，試計算該數(shù)據(jù)的行程編碼。解：A重復(fù)3次，B重復(fù)4次，C重復(fù)5次，D不重復(fù)，A重復(fù)6次，RLC數(shù)據(jù)流為：“SA3SB4SC5DSA6”，其中S為指示符?？偣舱加?3個字節(jié)，而源數(shù)據(jù)占用19個字節(jié)。有時行程編碼不用指示符，重復(fù)與否相同對待，則相應(yīng)的RLC為“A3B4C5D1A6”占用10個字節(jié)。例32設(shè)有數(shù)據(jù)流“AAABBBBCCCCCDAAAAAA”，試計算算術(shù)編碼原理5.2.7●算術(shù)編碼——無損壓縮編碼，屬于統(tǒng)計編碼。20世紀(jì)60年代由Elias提出，某些方面優(yōu)于霍夫曼編碼。因此，在JPEG標(biāo)準(zhǔn)的擴(kuò)展系統(tǒng)中，算術(shù)編碼已經(jīng)取代了霍夫曼編碼。●基本原理將被編碼的信息表示成實數(shù)軸上0和1之間的間隔，信息越長，間隔越小，表示這一間隔所需的二進(jìn)制位數(shù)就越多?！裉攸c(diǎn)1)算術(shù)編碼有基于概率統(tǒng)計的固定模式，也有相對靈活的自適應(yīng)模式。2)自適應(yīng)模式適用于不進(jìn)行概率統(tǒng)計的場合。3)當(dāng)信號源符號的出現(xiàn)概率接近時，算術(shù)編碼的效率高于霍夫曼編碼。4)算術(shù)編碼的實現(xiàn)相應(yīng)地比霍夫曼編碼復(fù)雜，但在圖像測試中表明，算術(shù)編碼效率比霍夫曼編碼效率高5％左右。33算術(shù)編碼原理5.2.7●算術(shù)編碼——無損壓縮編碼，屬于LZW壓縮編碼5.2.8●LZW（LempelZivWelch）無損壓縮編碼，用于圖像數(shù)據(jù)的壓縮。LZW（LempelZivWelch）是一種字典式無損壓縮編碼。1977年兩位以色列教授Lempel和Ziv提出了查找冗余字符和用較短的符號標(biāo)記替代冗余字符的概念。1985年美國人Welch將該技術(shù)發(fā)展到實際運(yùn)用階段，命名為LZW技術(shù)。LZW把數(shù)據(jù)流中復(fù)雜的數(shù)據(jù)用簡單的代碼來表示，并把代碼和數(shù)據(jù)的對應(yīng)關(guān)系建立一個轉(zhuǎn)換表（“字符串表”）。該轉(zhuǎn)換表是在壓縮或解壓縮過程中動態(tài)生成的表,并用于壓縮和解壓縮過程中。LZW被廣泛用于圖像壓縮領(lǐng)域。34LZW壓縮編碼5.2.8●LZW（LempelZivWLZW壓縮編碼●●

基本原理把復(fù)雜的數(shù)據(jù)用簡單的代碼表示，并把代碼和數(shù)據(jù)的對應(yīng)關(guān)系建立轉(zhuǎn)換表，又叫“字符串表”。轉(zhuǎn)換表記錄了代碼和數(shù)據(jù)的對應(yīng)關(guān)系。在壓縮和解壓縮過程中，LZW壓縮編碼會生成兩個完全相同的轉(zhuǎn)換表，數(shù)據(jù)以嚴(yán)格對應(yīng)的方式被壓縮和還原。●

特點(diǎn)1)對于可預(yù)測性不大的數(shù)據(jù)效果較好，常用于GIF格式的圖像壓縮。2)對于數(shù)據(jù)流中連續(xù)重復(fù)出現(xiàn)的字節(jié)和字串，具有很高的壓縮比。3)被用于文本程序等數(shù)據(jù)壓縮領(lǐng)域。4)有很多變體，如常見的ARC、RKARC、PKZIP高效壓縮程序。5)壓縮和解壓縮速度較快，對硬件條件要求不高。35LZW壓縮編碼●●基本原理把復(fù)雜的數(shù)據(jù)用簡單的代碼表示，并靜態(tài)圖像JPEG壓縮編碼技術(shù)5.35.3.1JPEG標(biāo)準(zhǔn)的由來1991年，聯(lián)合專家組提出了ISOCD建議草案，后經(jīng)過國際電子技術(shù)委員會ISO/IEC的批準(zhǔn)，正式成為第10918號標(biāo)準(zhǔn)，并正式命名為“JPEG高質(zhì)量靜止圖像壓縮編碼標(biāo)準(zhǔn)”，簡稱“JPEG標(biāo)準(zhǔn)”。多灰度靜止圖像的數(shù)字壓縮編碼標(biāo)準(zhǔn)計算機(jī)業(yè)內(nèi)人士探尋一種壓縮比大、圖像質(zhì)量高的壓縮編碼。在這種背景下,壓縮標(biāo)準(zhǔn)成為急待解決的問題。1986年CCITT和ISO共同成立了JPEG聯(lián)合圖像專家組，從事圖像壓縮的工業(yè)標(biāo)準(zhǔn)和學(xué)術(shù)意義的研究、探索。提出了ISOCD建議草案、即多灰度靜止圖像的數(shù)字壓縮編碼標(biāo)準(zhǔn)。36靜態(tài)圖像JPEG壓縮編碼技術(shù)5.35.3.1JPEG標(biāo)準(zhǔn)●JPEG算法概述JPEG算法根據(jù)人眼對亮度和顏色變化比較敏感的原理，在對圖像數(shù)據(jù)進(jìn)行壓縮時，只保存亮度和顏色變化的數(shù)據(jù)部分，而舍棄人眼不敏感的成分，以達(dá)到壓縮的目的。在圖像還原時，并不重新建立原始圖像，而是生成類似圖像，該圖像保留了人眼敏感的色彩和亮度。JPEG適合于連續(xù)色調(diào)、多級灰度、彩色或黑白圖像的數(shù)據(jù)壓縮。37●JPEG算法概述JPEG算法根據(jù)人眼對亮度和顏色變化比較JPEG壓縮算法5.3.2●適用于連續(xù)色調(diào)、多級灰度、彩色或黑白圖像的數(shù)據(jù)壓縮。無損壓縮比：大約為4:1。有損壓縮比：在10:1~100:1之間。不大于40:1時，還原的圖像在色彩、清晰度、顏色分布等方面與原始圖像相比，誤差不大，基本上保持了原始圖像的風(fēng)貌?！?/p>

特點(diǎn)1)對圖像進(jìn)行幀內(nèi)編碼，每幀色調(diào)連續(xù)，隨機(jī)存取。2)在寬范圍內(nèi)調(diào)節(jié)圖像的壓縮比和保真度，解碼器可參數(shù)化。3)對圖像進(jìn)行壓縮時，可隨意選擇期望的壓縮比值。4)對于硬件環(huán)境要求不高，只要有一般的CPU運(yùn)算速度即可。5)可運(yùn)行四種編碼模式：DCT順序編碼模式、DCT遞增模式、無失真編碼模式和分層編碼模式。JPEG算法更多……38JPEG壓縮算法5.3.2●適用于連續(xù)色調(diào)、多級灰度、彩色無失真預(yù)測編碼5.3.3●無失真預(yù)測編碼——無損壓縮，壓縮比一般為2:1。原始圖像數(shù)據(jù)經(jīng)過無失真編碼器進(jìn)行預(yù)測編碼，然后把壓縮圖像數(shù)據(jù)存儲在介質(zhì)中或傳送出去。在使用圖像時，經(jīng)過解碼器解碼，建立與原始圖像一致的不失真圖像?！裨眍A(yù)測器圖像數(shù)據(jù)熵編碼器碼表說明解碼器壓縮圖像數(shù)據(jù)無失真編碼器還原圖像數(shù)據(jù)采用了簡單的線性預(yù)測編碼方法，DPCM壓縮算法和霍夫曼壓縮算法，硬件容易實現(xiàn)，重新建立的圖像質(zhì)量與原始圖像無差別。●特點(diǎn)39無失真預(yù)測編碼5.3.3●無失真預(yù)測編碼——無損壓縮，有失真DCT壓縮編碼5.3.4●采用DCT（DiscreteCosineTransform）離散余弦變換的壓縮算法。1．DCT離散余弦變換●原理源圖像在輸入到編碼器之前，被分割成一系列順序排列的由8×8像點(diǎn)構(gòu)成的數(shù)據(jù)塊，把原始采樣數(shù)據(jù)中無符號整數(shù)轉(zhuǎn)換成有符號整數(shù)，進(jìn)行正變換。還原圖像時，解碼器輸出端經(jīng)過逆變換，重新建立圖像。由于運(yùn)算誤差和系數(shù)的量化，因而重建不很精確，與源圖像存在差異。2．DCT系數(shù)的量化量化依據(jù)量化表進(jìn)行，量化表中的元素由開發(fā)人員根據(jù)人類視覺特性制作。量化的定義：CQ(u,v)=IntegerRound[F(u,v)/Q(u,v)]解量化是量化過程的逆運(yùn)算，其公式為：CQ(u,v)=CQ(u,v)·Q(u,v)40有失真DCT壓縮編碼5.3.4●采用DCT（Discret有失真DCT壓縮編碼5.3.43．圖像的質(zhì)量與壓縮比●采用DCT算法存在失真，但是，只要量化表中的元素更科學(xué)、更符合人類視覺敏感度，則壓縮后的圖像不會產(chǎn)生過大的視覺變化。壓縮結(jié)果bit/像素圖像質(zhì)量的主觀評價●假定某圖像的像素采用8bit編碼，則壓縮結(jié)果和圖像效果見下表。1.5~2.00.75~1.50.5~0.750.25~0.5色彩、灰階過度、清晰度等與原始圖像差別不大。圖像質(zhì)量良好，灰階過度和層次略感有損失。圖像質(zhì)量中等，灰階過度、層次、色彩稍差。圖像質(zhì)量一般，色彩和灰階與原始圖像相比有明顯差別41有失真DCT壓縮編碼5.3.43．圖像的質(zhì)量與壓縮比●采用動態(tài)圖像MPEG壓縮編碼技術(shù)5.45.4.1基本原理1．動態(tài)圖像壓縮主要解決的問題1)正確區(qū)分靜止圖像和動態(tài)圖像。2)提取動態(tài)圖像中的活動成分。3)進(jìn)行幀之間的預(yù)測，提供壓縮的依據(jù)。2．幀的預(yù)測編碼1)條件像素補(bǔ)充法

——比較兩幀對應(yīng)位置的像素亮度，若亮度差超過預(yù)先規(guī)定的閥值，則認(rèn)為兩個像素有變化，傳送像素。若亮度差未超過閥值，不處理。2)運(yùn)動補(bǔ)償法

——跟蹤畫面上的活動元素，并進(jìn)行向量計算，加以補(bǔ)償，然后再利用幀間預(yù)測進(jìn)行壓縮。適用于活動元素少的可視電話和電視會議。42動態(tài)圖像MPEG壓縮編碼技術(shù)5.45.4.1基本原理1．圖像的分類3.●MPEG標(biāo)準(zhǔn)根據(jù)處理圖像的性質(zhì)，把圖像分成以下三類：1)幀內(nèi)圖像（Intrapictures）

——又稱“I圖像”，JPEG標(biāo)準(zhǔn)按照靜止圖像的模式進(jìn)行壓縮處理。主要利用靜止圖像自身的相關(guān)性進(jìn)行編碼，實現(xiàn)數(shù)據(jù)壓縮的目的。幀內(nèi)圖像的壓縮比屬于中度壓縮，典型的壓縮像素編碼為2bit。2)預(yù)測圖像（Predictedpictures）

——又稱“P圖像”，通過對最近的前一幀I圖像或者P圖像進(jìn)行預(yù)測的“前向預(yù)測”過程，把前面圖像作為預(yù)測下一幀圖像的參照物，使圖像編碼的數(shù)據(jù)量減少。預(yù)測圖像有較高的壓縮比，但會增加失真。3)雙向圖像（Bidirestionalpictures）

——又稱“B圖像”，可使用前一幀圖像和后一幀圖像作參照物，進(jìn)行雙向預(yù)測。雙向預(yù)測可以采用四種編碼技術(shù)，即幀內(nèi)圖像編碼、前向預(yù)測編碼、后向預(yù)測編碼、雙向預(yù)測編碼。43圖像的分類3.●MPEG標(biāo)準(zhǔn)根據(jù)處理圖像的性質(zhì)，把圖像分成MPEG技術(shù)標(biāo)準(zhǔn)5.4.2●MPEG-Ⅰ標(biāo)準(zhǔn)●

誕生于1991年，主要特點(diǎn)：1)以1.5Mb/s的速率傳輸視頻信號，即壓縮信號帶寬為1.5Mb/s。2)以單通道64kb/s、128kb/s和192kb/s的傳輸速率傳輸音頻信號。3)可通過差值運(yùn)算，在352×240畫面分辨率上顯示活動圖像。4)分三個組成部分：視頻、音頻和系統(tǒng)。5)對于幀內(nèi)圖像，采用二維余弦變換、自適應(yīng)算術(shù)編碼、行程編碼、變字長編碼，以及差分脈沖編碼（DPCM）進(jìn)行壓縮。6)幀間壓縮采用運(yùn)動補(bǔ)償預(yù)測編碼和運(yùn)動補(bǔ)償內(nèi)插編碼?！裨试S采用多種存儲介質(zhì)，如CD-ROM、數(shù)字錄音帶、磁盤、CD-R、

CD-RW、M.O.，以及ISDN集成服務(wù)數(shù)字網(wǎng)絡(luò)、LAN局域網(wǎng)絡(luò)等。設(shè)計MPEG壓縮算法時，要考慮隨機(jī)訪問、快進(jìn)快退、檢索、聲像同步、容錯、延時控制、可編輯特性以及視頻窗口設(shè)置的靈活性等。44MPEG技術(shù)標(biāo)準(zhǔn)5.4.2●MPEG-Ⅰ標(biāo)準(zhǔn)●誕生于19MPEG技術(shù)標(biāo)準(zhǔn)5.4.2●MPEG-Ⅱ標(biāo)準(zhǔn)●

主要特點(diǎn)1)壓縮信號帶寬為4~15Mb/s，即信號傳輸速率為4~15Mb/s。2)支持NTSC制720×480畫面分辨率，PAL制720×576畫面分辨率，畫面質(zhì)量達(dá)到廣播級，適用于HDTV高質(zhì)量電視信號的傳送與播放。3)解碼器同時支持MPEG-Ⅰ和MPEG-Ⅱ兩種標(biāo)準(zhǔn)。4)視頻信號的傳輸速率為30幀/s，音頻信號的質(zhì)量達(dá)到CD級。5)為了在畫面質(zhì)量、數(shù)據(jù)量和帶寬之間尋求最佳值，允許在一定范圍內(nèi)調(diào)整壓縮比。6)最高壓縮比為200:1，但由于畫面中活動內(nèi)容的多少和人為調(diào)整壓縮比等因素的影響，大多數(shù)情況下達(dá)不到最高壓縮比。7)MPEG-Ⅱ用于DVD視頻信號的壓縮，DVD音頻信號的壓縮隨制式的不同而不同：PAL制采用MPEG-Ⅱ；NTSC制采用AC3壓縮標(biāo)準(zhǔn)。45MPEG技術(shù)標(biāo)準(zhǔn)5.4.2●MPEG-Ⅱ標(biāo)準(zhǔn)●主要特點(diǎn)1第5章多媒體數(shù)據(jù)壓縮技術(shù)小結(jié)●5.1數(shù)據(jù)壓縮基本原理

5.1.1信息、數(shù)據(jù)與編碼

5.1.2數(shù)據(jù)壓縮的條件

5.1.3數(shù)據(jù)冗余5.2數(shù)據(jù)壓縮算法

5.2.1數(shù)據(jù)壓縮算法分類

5.2.2預(yù)測編碼原理

5.2.3變換編碼原理

5.2.4統(tǒng)計編碼原理

5.2.5霍夫曼編碼原理

5.2.6行程編碼原理5.2.7算術(shù)編碼原理

5.2.8LZW壓縮編碼5.3靜態(tài)圖像JPEG壓縮編碼技術(shù)

5.3.1JPEG標(biāo)準(zhǔn)的由來

5.3.2JPEG壓縮算法

5.3.3無失真預(yù)測編碼

5.3.4有失真DCT壓縮編碼5.4動態(tài)圖像MPEG壓縮編碼技術(shù)

5.4.1基本原理

5.4.2MPEG技術(shù)標(biāo)準(zhǔn)46第5章多媒體數(shù)據(jù)壓縮技術(shù)小結(jié)●5.1數(shù)據(jù)壓縮基本原理●習(xí)題五5.1數(shù)據(jù)壓縮的理由有哪些？5.2什么是數(shù)據(jù)冗余？5.3冗余有多少種？分別是什么？5.4無損壓縮編碼指的是什么？5.5數(shù)據(jù)壓縮具備哪兩個過程？5.6霍夫曼編碼的特點(diǎn)是什么？5.7采用JPEG壓縮格式的靜態(tài)圖像具有哪些主要特點(diǎn)？5.8動態(tài)圖像壓縮主要解決哪些問題？5.9MPEG-Ⅱ標(biāo)準(zhǔn)具有哪些主要特點(diǎn)？47●習(xí)題五5.1數(shù)據(jù)壓縮的理由有哪些？47香農(nóng)1948年則創(chuàng)立了信息論(informationtheory)?？藙诘?香農(nóng)在公眾中并不特別知名，但他是使我們的世界能進(jìn)行即時通信的少數(shù)科學(xué)家和思想家之一。他是美國科學(xué)院院士、美國工程院院士、英國皇家學(xué)會會員、美國哲學(xué)學(xué)會會員。他獲得過許多榮譽(yù)和獎勵。例如1949年Morris獎、1955年Ballantine獎、1962年Kelly獎、1966年的國家科學(xué)獎?wù)隆EEE的榮譽(yù)獎?wù)隆?978年Jaquard獎、1983年Fritz獎、1985年基礎(chǔ)科學(xué)京都獎?！裣戕r(nóng)克勞德?香農(nóng)(ClaudeElwoodShannon，1916-2001)1916年4月30日誕生于美國密西根州的Petoskey。2001年2月24日，香農(nóng)在馬薩諸塞州Medford辭世，享年85歲。香農(nóng)被信息界譽(yù)為信息論及數(shù)字通信時代的奠基人。返回48香農(nóng)1948年則創(chuàng)立了信息論(informationtheHuffman樹的定義構(gòu)造Huffman樹Huffman編碼●Huffman(哈夫曼）編碼49Huffman樹的定義●Huffman(哈夫曼）編碼49Huffman樹也稱為最優(yōu)樹，是一類帶權(quán)路徑最短的二叉樹。樹的帶權(quán)路徑長度定義為：

WPL=∑wklkk=1n

其中：

n樹中葉結(jié)點(diǎn)的個數(shù)

wi

第i個結(jié)點(diǎn)的權(quán)值

li第i個結(jié)點(diǎn)的路徑長度●Huffman樹的定義50Huffman樹也稱為最優(yōu)樹，是一類帶權(quán)路徑最短的二叉樹。以下有三棵樹：WPLa=7x2+5x2+2x2+4x2=36WPLb=7x3+5x3+2x1+4x2=46

WPLc=7x1+5x2+2x3+4x3=35√事實證明按哈夫曼樹構(gòu)造二叉樹，可得到很好的特性，應(yīng)用于實際問題，可提高處理效率。（a）（b）（c）abcdabcdacbd777555222444●Huffman樹舉例51以下有三棵樹：WPLa=WPLb=WPLc=事實證由統(tǒng)計規(guī)律可知，考試成績的分布符合正態(tài)分布：-110

分?jǐn)?shù)0～5960～6970～7980～8990～100比例數(shù)0.050.150.400.30.10根據(jù)正態(tài)分布規(guī)律，在60～90之間的分?jǐn)?shù)占85%，而不及格和優(yōu)秀是少數(shù)?！駪?yīng)用舉例52由統(tǒng)計規(guī)律可知，考試成績的分布符合正態(tài)分布：-110分判定樹比較：若輸入1萬個數(shù)據(jù)：按A的判定過程進(jìn)行操作，約需比較3.2萬次而按B比較,則僅需2.2萬次。a<60?a<70?a<80?a<90?不及格

及格

中等

良好

優(yōu)秀YYYYNNNNa<80?a<70?a<90?a<60?不及格

優(yōu)秀

良好

中等

中等

及格不及格YYYNNNNYY(A)(B)●將百分制轉(zhuǎn)換成五分制53判定樹比較：若輸入1萬個數(shù)據(jù)：a<60?a<70?a<80?構(gòu)造Huffman樹算法步驟：Step1將n個帶權(quán)值wi（i≤n）的結(jié)點(diǎn)構(gòu)成n棵二叉樹的集合T={T1，T2，……，Tn}，每棵二叉樹只有一個根結(jié)點(diǎn)。Step2在T中選取兩個權(quán)值最小的結(jié)點(diǎn)作為左右子樹，構(gòu)成一個新的二叉樹，其根結(jié)點(diǎn)的權(quán)值取左右子樹權(quán)值之和；Step3在T中刪除這兩棵樹，將新構(gòu)成的樹加入到T中；Step4重復(fù)2）、3）步的操作，直到T中只含一棵樹為止，該樹就是Huffman樹?！駱?gòu)造Huffman樹54構(gòu)造Huffman樹算法步驟：●構(gòu)造Huffman樹54以權(quán)值分別為7，5，2，4的結(jié)點(diǎn)a、b、c、d構(gòu)造Huffman樹。T={abcd}cdT3246bT3T26511bT26511cd2418aT2711T1618a7T1bT3T251118a7T1b511cd264（d）T={T1}（c）T={aT2}（b）T={abT3}（a）T={abcd}代入T2代入T3代入T1示例●構(gòu)造Huffman樹舉例55以權(quán)值分別為7，5，2，4的結(jié)點(diǎn)a、b、c、d構(gòu)造Huffm編碼：用二進(jìn)制數(shù)的不同組合來表示字符的方法。前綴編碼：一種非等長度的編碼(任一個字符的編碼都不是另一個字符編碼的前綴)。Huffman編碼：一種非等長度的編碼。以給定權(quán)值的結(jié)點(diǎn)構(gòu)造Huffman樹，按二進(jìn)制前綴編碼的方式構(gòu)成的編碼為Huffman編碼。

a0b01cd011編碼：a（0）

b（01）

c（011）

d（111）方法約定：1）左分支為‘0’2）右分支為‘1’3）由葉到根路徑上字符組成的二進(jìn)制串就是該葉結(jié)點(diǎn)的編碼?！馠uffman編碼56編碼：用二進(jìn)制數(shù)的不同組合來表示字符的方法。Huffman編在某系統(tǒng)的通信聯(lián)絡(luò)中可能出現(xiàn)8種字符，其頻率分別為0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，設(shè)權(quán)值分別為{5，29，7，8，14，23，3，11}，n=8，其Huffman樹為：000000011111115378142911234258100Huffman編碼為：A50110B2901C70111D81111E14011F2300G31110H11010●返回Huffman編碼舉例57在某系統(tǒng)的通信聯(lián)絡(luò)中可能出現(xiàn)8種字符，其頻率分別為0.05、●JPEG算法的四種編碼模式1)DCT順序編碼模式——基本操作模式，也稱基本系統(tǒng)，所有JPEG

編碼解碼器都必須支持基本系統(tǒng)，采用二維余弦變換的編碼方案。2)DCT遞增模式，該模式又叫累進(jìn)模式。3)無失真編碼模式。4)分層編碼模式。⑴基線編碼系統(tǒng)。面向大多數(shù)有損壓縮的應(yīng)用，采用DCT變換壓縮。輸入圖像精度8位/像素/色，順序模式，采用Huffman或算術(shù)編碼；⑵擴(kuò)展編碼系統(tǒng)。為滿足更廣泛領(lǐng)域的應(yīng)用而設(shè)置的，從低分辨率到高分辨率逐步遞進(jìn)傳遞的應(yīng)用。輸入圖像精度12位/像素/色，累進(jìn)模式，采用Huffman或算術(shù)編碼；⑶獨(dú)立編碼系統(tǒng)。面向無損壓縮的應(yīng)用，采用無損預(yù)測壓縮。輸入圖像精度2-16位/像素/色，順序模式，采用Huffman或算術(shù)編碼?！褚粋€產(chǎn)品或系統(tǒng)必須包括對基線系統(tǒng)的支持?！馢PEG算法的三種壓縮系統(tǒng)58●JPEG算法的四種編碼模式1)DCT順序編碼模式——順序模式累進(jìn)模式●順序模式和累進(jìn)模式59順序模式累進(jìn)模式●順序模式和累進(jìn)模式59有失真DCT壓縮編碼●采用DCT（DiscreteCosineTransform）離散余弦變換的壓縮算法。1．DCT離散余弦變換●原理源圖像在輸入到編碼器之前，被分割成一系列順序排列的由8×8像點(diǎn)構(gòu)成的數(shù)據(jù)塊，把原始采樣數(shù)據(jù)中無符號整數(shù)轉(zhuǎn)換成有符號整數(shù)，進(jìn)行正變換。還原圖像時，解碼器輸出端經(jīng)過逆變換，重新建立圖像。由于運(yùn)算誤差和系數(shù)的量化，因而重建不很精確，與源圖像存在差異。2．DCT系數(shù)的量化量化依據(jù)量化表進(jìn)行，量化表中的元素由開發(fā)人員根據(jù)人類視覺特性制作。量化的定義：CQ(u,v)=IntegerRound[F(u,v)/Q(u,v)]解量化是量化過程的逆運(yùn)算，其公式為：CQ(u,v)=CQ(u,v)·Q(u,v)●60有失真DCT壓縮編碼●采用DCT（DiscreteCos⒈正向離散余弦變換(ForwardDiscreteCosineTransform，F(xiàn)DCT)

把空間域表示的圖像變換為頻率域表示的圖像。⒉量化DCT系數(shù)用加權(quán)函數(shù)對DCT系數(shù)進(jìn)行量化，該加權(quán)函數(shù)對于人視覺系統(tǒng)是最佳的。⒊Huffman編碼用Huffman可變字長編碼器對量化系數(shù)進(jìn)行編碼。譯碼或者叫做解壓縮的過程與壓縮編碼過程相反。

有失真壓縮三個步驟

●61⒈正向離散余弦變換(ForwardDiscreteCoDCT變換是數(shù)字圖像處理中的重要變換。但對于大尺寸的二維數(shù)值矩陣，若采用普通DCT變換，其花費(fèi)的時間將是讓人難以忍受甚至無法達(dá)到實用。解決方案，關(guān)注快速DCT變換的算法研究。目前而言，DCT變換的快速算法有以下兩種方式：1．快速FFT算法。直接利用FFT來實現(xiàn)DCT變換的快速算法。特點(diǎn)是實現(xiàn)相對較容易，但計算過程會涉及到復(fù)數(shù)運(yùn)算。由于DCT變換前后的數(shù)據(jù)都是實數(shù)，而引入復(fù)數(shù)，顯然是增加了運(yùn)算量，也給硬件存儲提出了更高的要求。2．直接在實數(shù)域進(jìn)行DCT快速變換。顯然，這種方法相比于前一種而言，計算量和硬件要求都要優(yōu)于前者。鑒于此，一般采用第二種方法來實現(xiàn)DCT變換的快速算法。DCT變換存在的問題●62DCT變換是數(shù)字圖像處理中的重要變換。但對于大尺寸的二維數(shù)值DCT變換是一種實數(shù)域變換，其變換核心為實數(shù)的余弦函數(shù)。變換實質(zhì)是將一個空間域上的信號，變換為一個頻域上的信號。設(shè)一幅圖像，或者一幅圖像的某個彩色分量經(jīng)過數(shù)字化后存為矩陣A，并設(shè)A為M×N矩陣，則2維DCT變換定義為：-1-1-1-1DCT變換的快速算法●63DCT變換是一種實數(shù)域變換，其變換核心為實數(shù)的余弦函數(shù)。變換

采用快速DCT變換對一幅256灰度的256×256的圖像進(jìn)行DCT正變換只需94ms。而如果采用普通DCT變換，所需時間要575,172ms。舉例●例64采用快速DCT變換對一幅256灰度的256×256的圖像進(jìn)圖像矩陣分塊顏色變換零偏置轉(zhuǎn)換 頻域變換系數(shù)量化符號編碼JPEG壓縮步驟

●量化器DCT正向變換構(gòu)造8×8的子圖輸入圖像N×N符號編碼器壓縮圖像顏色空間轉(zhuǎn)換零偏置轉(zhuǎn)換65圖像矩陣分塊JPEG壓縮步驟●量化器DCT正構(gòu)造8×8輸入人眼對亮度更敏感，提取亮度特征，將RGB轉(zhuǎn)換為YCbCr模型。對亮度采用特殊編碼：Y=0.299R+0.5870G+0.1140BCb=–0.1787R–0.3313G+0.5000B+128Cr=0.5000R–0.4187G–0.0813B+128顏色解碼：R=Y+1.40200(Cr

–128)G=Y–0.34414(Cb

–128)–0.71414(Cr

–128)B=Y+1.77200(Cb

–128)顏色空間轉(zhuǎn)換RGB轉(zhuǎn)到Y(jié)CbCr●66人眼對亮度更敏感，提取亮度特征，將RGB轉(zhuǎn)換為YCbCr模型YUV是電視系統(tǒng)中采用的顏色模式。Y是亮度信號，U、V是色度信號。轉(zhuǎn)換公式:YUVRGB=

0.300.590.11-0.15-0.290.440.61-0.52-0.096RGB與YUV顏色空間的轉(zhuǎn)換●67YUV是電視系統(tǒng)中采用的顏色模式。Y是亮度信號，U、V是色度將圖像矩陣分為8×8的子塊，對每一塊單獨(dú)進(jìn)行DCT變換。根據(jù)人眼對亮度信號比對色度信號更加敏感的生理特性，將Y分量劃分為8×8的塊，將U、V分量劃分為16×16的塊。U、V分量的每一塊舍棄1/2的信息后形成一個8×8的矩陣。構(gòu)造子圖像●68將圖像矩陣分為8×8的子塊，對每一塊單獨(dú)進(jìn)行DCT變換。根據(jù)對變換后的DCT矩陣進(jìn)行量化處理（用表1和表2的量化矩陣分別對Y分量和U、V分量量化）。量化的原則：低頻部分用小值量化，高頻部分用大值量化，量化結(jié)果使高頻部分出現(xiàn)大量“0”。采用閾值作為子圖系數(shù)位置函數(shù)的量化方式。所有子圖使用同一個全局閾值模板，但閾值的取值與系數(shù)的位置相關(guān)，閾值模板給出了不同位置上系數(shù)的相應(yīng)閾值。對于亮度和顏色使用不同的量化閾值模板，并取整。量化處理●69對變換后的DCT矩陣進(jìn)行量化處理（用表1和表2的量化矩陣分別表1JPEG標(biāo)準(zhǔn)所推薦的亮度量化表亮度的量化模板系數(shù)●70表1JPEG標(biāo)準(zhǔn)所推薦的亮度量化表亮度的量化模板系數(shù)●71718 24 47 99 99 99 9918 21 26 66 99 99 99 9924 26 56 99 99 99 99 9947 66 99 99 99 99 99 9999 99 99 99 99 99 99 9999 99 99 99 99 99 99 9999 99 99 99 99 99 99 9999 99 99 99 99 99 99 99表2JPEG標(biāo)準(zhǔn)所推薦的色度量化表顏色的量化模板系數(shù)●711718 24 47 99 99 99 1）正向量化：Squv=round(Suv/Quv)其中：Suv是DCT系數(shù)，Quv量化模板系數(shù)2）逆向量化：Ruv=SquvQuv例：Sq(0,0)=round[-415/16] =round[-25.9]=-26 Ruv(0,0)=-26*16=-416系數(shù)量化公式●721）正向量化：系數(shù)量化公式●72-26-3-6 2 2

0 0 00

1 -2-4 0 0

0 00-315 -1 -1

0 0 00

-412 -1 0

0 0 00

1

00 0 0 0 0 0

0 00 0 0 0 0 00 00 0 0 0 0 00 00 0 0 0 0 0量化變換后矩陣樣式示意圖低頻部分高頻部分量化結(jié)果●73-26-3-6 2 2 0 0 0為了增加連續(xù)“0”系數(shù)的個數(shù)，重新編排量化后的系數(shù)。方法是按照Z字形的式樣編排（把一個8×8的矩陣變成一個1×64的矢量，頻率較低的系數(shù)放在矢量的頂部）。

[-26-31-3-2-62-41-41150200-1200000-1-1EOB]

全零結(jié)尾用特殊符號EOB重新編排量化后的系數(shù)●74為了增加連續(xù)“0”系數(shù)的個數(shù)，重新編排量化后的系數(shù)。[-在重新對量化數(shù)據(jù)進(jìn)行編碼后，得到的數(shù)據(jù)有大量連續(xù)的零。對全部數(shù)據(jù)進(jìn)行Huffman編碼。完成后的編碼數(shù)組（重排的）是：10101100100001010001011000010110100011001100011001001100101111001101101100110111101000001010其中空格是為了可閱讀性而插入的。完成編碼的重排數(shù)組的總位數(shù)是92，不壓縮需要8×8×8=512位。結(jié)果的壓縮率是512/92，或5.6:1。對量化結(jié)果進(jìn)行編碼●75在重新對量化數(shù)據(jù)進(jìn)行編碼后，得到的數(shù)據(jù)有大量連續(xù)的零。對全部壓縮圖像數(shù)據(jù)IDCT逆量化器熵解碼器恢復(fù)的圖像數(shù)據(jù)解碼器壓縮圖像數(shù)據(jù)FDCT量化器熵編碼器源圖像數(shù)據(jù)編碼器解碼過程基于DCT編碼過程●76壓縮圖像數(shù)據(jù)IDCT逆量化器熵解碼器恢復(fù)的圖像數(shù)據(jù)解碼器壓縮彩色圖像像素645×600在計算機(jī)中存儲為3個矩陣每個矩陣為645×600

各存儲R、G、B的3個分量信息。

舉例●例77彩色圖像舉例●例77變換后矩陣的左上角是圖像的低頻部分，越靠近右下角，頻率越高。人的眼睛對高頻部分是不敏感的?？梢陨釛増D像中的高頻部分而基本上不影響圖像質(zhì)量。DCT變換后的圖

●例78變換后矩陣的左上角是圖像的低頻部分，越靠近右下角，頻率越高。對應(yīng)645×600的矩陣A，為了舍棄高頻部分，將該矩陣的高頻部分置為0值。在這令此時矩陣減小為387×360，數(shù)據(jù)量是原來的（387×360）/（645×600）=36%（387×360）a1,1a1,2……a1,360

00……0a2,1a2,2……

a2,360

00……0

…………

……a387,1a387,2…a387,360

00……000……000……0………………00……000……0不同壓縮比率的圖像質(zhì)量比較

●79對應(yīng)645×600的矩陣A，為了舍棄高頻部分，將該矩陣的高頻重構(gòu)后的圖像只保留部分258×240

（258×240）增大高頻部分的舍棄范圍（1）

●數(shù)據(jù)量是原圖的16%80重構(gòu)后的圖像只保留部分258×240（258×240）只保留部分130×120

數(shù)據(jù)量是原圖的4%（130×120）重構(gòu)后的圖像增大高頻部分的舍棄范圍（2）

●81只保留部分130×120數(shù)據(jù)量是原圖的4%（130×1只保留部分65×60

數(shù)據(jù)量是原圖的1%（65×60）重構(gòu)后的圖像增大高頻部分的舍棄范圍（3）

●82只保留部分65×60數(shù)據(jù)量是原圖的1%（65×60將矩陣A的前15行和列置為0。去掉少量低頻部分對圖像的影響

●重構(gòu)后的圖像顯然對低頻部分的細(xì)小修改都會對圖像有很大的影響返回83將矩陣A的前15行和列置為0。去掉少量低頻部分對圖像的影響第5章多媒體技術(shù)MULTIMEDIATECHNOLOGY84第5章多媒體技術(shù)MULTIMEDIATECHNOLOGY1第5

章多媒體數(shù)據(jù)壓縮技術(shù)5.1數(shù)據(jù)壓縮基本原理

5.1.1信息、數(shù)據(jù)與編碼

5.1.2數(shù)據(jù)壓縮的條件

5.1.3數(shù)據(jù)冗余5.2數(shù)據(jù)壓縮算法

5.2.1數(shù)據(jù)壓縮算法分類

5.2.2預(yù)測編碼原理

5.2.3變換編碼原理

5.2.4統(tǒng)計編碼原理

5.2.5霍夫曼編碼原理

5.2.6行程編碼原理5.2.7算術(shù)編碼原理

5.2.8LZW壓縮編碼5.3靜態(tài)圖像JPEG壓縮編碼技術(shù)

5.3.1JPEG標(biāo)準(zhǔn)的由來

5.3.2JPEG壓縮算法

5.3.3無失真預(yù)測編碼

5.3.4有失真DCT壓縮編碼5.4動態(tài)圖像MPEG壓縮編碼技術(shù)

5.4.1基本原理

5.4.2MPEG技術(shù)標(biāo)準(zhǔn)85第5章多媒體數(shù)據(jù)壓縮技術(shù)5.1數(shù)據(jù)壓縮基本原理數(shù)據(jù)壓縮基本原理5.1數(shù)據(jù)壓縮的對象是數(shù)據(jù)。數(shù)據(jù)是信息的載體，用來記錄和傳送信息。真正有用的不是數(shù)據(jù)本身，而是數(shù)據(jù)所攜帶的信息。大的數(shù)據(jù)量并不代表含有大的信息量。而對于去掉冗余的數(shù)據(jù)對信息沒有本質(zhì)的影響稱為壓縮?！駭?shù)據(jù)壓縮原理86數(shù)據(jù)壓縮基本原理5.1數(shù)據(jù)壓縮的對象是數(shù)據(jù)。數(shù)據(jù)是信息的載體5.1.1信息、數(shù)據(jù)與編碼我們了解的東西，描述它用的信息量少，不了解的東西，描述它用的信息量大。在信息論中，可以說：信息是用不確定的度量來定義的；一個消息的可能性越小，其信息含量越大；消息的可能性越大，則信息含量越小。例自然現(xiàn)象875.1.1信息、數(shù)據(jù)與編碼我們了解的東西，描述它用的信息數(shù)據(jù)壓縮基本原理5.15.1.1信息、數(shù)據(jù)與編碼1．信息和熵●信息量的大小和消息有一定的關(guān)系。在數(shù)學(xué)上，消息是其出現(xiàn)概率的單調(diào)下降函數(shù)。信息量越大，消息的可能性越小，反之亦然?！裥畔⒘浚簽榱藦腘個相等的可能事件中挑選出一個事件所需的信息度量和含量，所提問“是或否”的次數(shù)。也就是說，在N個事件中辨識特定的一個事件要詢問“是或否”次數(shù)。要從256個數(shù)中選定某一個數(shù)，可以先提問“是否大于128？”，不論回答是與否，則半數(shù)的可能事件被取消。如果繼續(xù)詢問下去，每次詢問將對應(yīng)一個1bit的信息量。例88數(shù)據(jù)壓縮基本原理5.15.1.1信息、數(shù)據(jù)與編碼1．信息例●隨著每次詢問，有半數(shù)的可能事件被取消，這個過程由公式表示：可看出：對于256個數(shù)的詢問只要進(jìn)行8次，即可確定一個具體的數(shù)。設(shè)：從N個數(shù)中選定任意一個數(shù)x的概率為p(x)，假定選定任意一個數(shù)的概率都相等，即p(x)=1/N，則信息量為：log2256=8bit如果將信息源所有可能事件的信息量進(jìn)行平均，即可得到信息的“熵”(熵是平均信息量)，信息源X的符號集為xi(i=1,2,…,N)。設(shè)：xi出現(xiàn)的概率為p(xi)，則信息源X的熵為：I(x)=log2N=-log21／N=-log2p(x)=I[p(x)]H(x)=P(xi)log2p(xi)∑P(xi)I[p(xi)]=-∑ni=1ni=189例●隨著每次詢問，有半數(shù)的可能事件被取消，這個過程由公式表示信息與數(shù)據(jù)2.信息可以用函數(shù)表示，該函數(shù)由信息論創(chuàng)始人C.E.Shannon香農(nóng)提出，以概率論的觀點(diǎn)對信息進(jìn)行定量描述，具體的信息函數(shù)表達(dá)式為：I(ai)=-log2Pi(i=1,2,…,r)公式中，Pi(i

=1,2,…,r)是隨機(jī)消息組合X{a1,a2,…,ar}中的消息ai(i

=1,2,…,r)的先驗概率。Pi

可以度量ai(i

=1,2,…,r)所含的信息量。而I(ai)(i=1,2,…,r)在X的先驗概率空間P{p1,p2,…,pr}中的統(tǒng)計平均值為信息源X的熵：信息源X的熵用來度量X中每種消息所包含的平均信息量。信息熵主要表示信息系統(tǒng)的有序程度，而不是熱力學(xué)中系統(tǒng)的無序程度。H(X)=H{p1,p2,…,pr}=-Pilog2pi∑ni=190信息與數(shù)據(jù)2.信息可以用函數(shù)表示，該函數(shù)由信息論創(chuàng)始人C.E例2-1設(shè)信源有16種符號，其出現(xiàn)的概率相同，即P（Xi）=1/16。計算其平均信息熵。例91例2-1設(shè)信源有16種符號，其出現(xiàn)的概率相同，即P（Xi

例2-2某信源有8種符號，其出現(xiàn)的概率如下：例92例2-2某信源有8種符號，其出現(xiàn)的概率如下：例9信源中含有自然冗余度，這些冗余度既來自于信源本身的相關(guān)性，又來自于信源概率分布的不均勻性，只要找到去除相關(guān)性或改變概率分布不均勻性的手段和方法，也就找到了信息熵編碼的方法。但信源所含有的平均信息量（熵）是進(jìn)行無失真編碼的理論的極限，只要不低于此極限，就能找到某種適宜的編碼方法，去逼近信息熵，實現(xiàn)數(shù)據(jù)壓縮。香儂理論的要點(diǎn)2.93信源中含有自然冗余度，這些冗余度既來自于信源本身的相關(guān)性，又多媒體信息的數(shù)據(jù)量3.1)文本

——假設(shè)屏幕顯示分辨率為1024×768，字符為16×16點(diǎn)陣，每個字符用4個字節(jié)表示，則顯示一屏字符所需要的存儲空間為：（1024/16）×（768/16）×4B=12288B（約合12KB）2)圖像

——假定圖像顯示在1024×768分辨率的屏幕上，則滿屏幕像點(diǎn)所占用的空間為：

1024×768×log2256=768KB3)音頻

——假定模擬聲音頻率22050Hz，其數(shù)字采樣頻率44100Hz，采樣精度為16bit，雙聲道立體聲模式，則1min所需數(shù)據(jù)量為：

44100Hz×2B(16bit采樣精度)×2(雙聲道)×60s=10MB/min4)視頻

——采用帶寬為5MHz的PAL制視頻信號，掃描速度25幀/s，樣本寬度24bit，采樣頻率最低10MHz，則一幀數(shù)字化圖像所占用的最少存儲空間為：

10(采樣頻率)÷25(掃描速度)×24(樣本寬度)=9.6Mbit(合1.2MB)94多媒體信息的數(shù)據(jù)量3.1)文本——假設(shè)屏幕顯示分辨率為考慮一張640×480的全彩影像

640×480×3×8=7,372,800Bits

調(diào)制解調(diào)器(Modem)為

36Kbps

7372800/36000=204.8(sec)=3.41(min)

假設(shè)壓縮算法(JPEG)的壓縮率為1:12

(7372800/12)/36000=17.1(sec)

對圖片壓縮效果較好，但對色彩單純的圖形則效果一般不很理想。

例95考慮一張640×480的全彩影像

640×數(shù)據(jù)壓縮的條件5.1.2●

數(shù)據(jù)冗余度(重復(fù)數(shù)據(jù)、可忽略數(shù)據(jù))●

信息傳輸與存儲的限制(壓縮→傳輸或存儲→解壓縮)■44.1kHz/Stereo1.3MB■22.0kHz/Mono0.3MB■Stop重復(fù)數(shù)據(jù)可忽略數(shù)據(jù)●

人類不敏感因素(顏色、亮度、細(xì)節(jié)等)224顏色(16,777,216色)28顏色(256色)●音頻不敏感因素(試聽)●

顏色不敏感因素96數(shù)據(jù)壓縮的條件5.1.2●數(shù)據(jù)冗余度(重復(fù)數(shù)據(jù)