數(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ù)測(cè)編碼原理

5.2.3變換編碼原理

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

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)的由來(lái)

5.3.2JPEG壓縮算法

5.3.3無(wú)失真預(yù)測(cè)編碼

5.3.4有失真DCT壓縮編碼5.4動(dòng)態(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ù)壓縮的對(duì)象是數(shù)據(jù)。數(shù)據(jù)是信息的載體，用來(lái)記錄和傳送信息。真正有用的不是數(shù)據(jù)本身，而是數(shù)據(jù)所攜帶的信息。大的數(shù)據(jù)量并不代表含有大的信息量。而對(duì)于去掉冗余的數(shù)據(jù)對(duì)信息沒(méi)有本質(zhì)的影響稱為壓縮?！駭?shù)據(jù)壓縮原理3數(shù)據(jù)壓縮基本原理5.1數(shù)據(jù)壓縮的對(duì)象是數(shù)據(jù)。數(shù)據(jù)是信息的載體5.1.1信息、數(shù)據(jù)與編碼我們了解的東西，描述它用的信息量少，不了解的東西，描述它用的信息量大。在信息論中，可以說(shuō)：信息是用不確定的度量來(lái)定義的；一個(gè)消息的可能性越小，其信息含量越大；消息的可能性越大，則信息含量越小。例自然現(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ù)。信息量越大，消息的可能性越小，反之亦然?！裥畔⒘浚簽榱藦腘個(gè)相等的可能事件中挑選出一個(gè)事件所需的信息度量和含量，所提問(wèn)“是或否”的次數(shù)。也就是說(shuō)，在N個(gè)事件中辨識(shí)特定的一個(gè)事件要詢問(wèn)“是或否”次數(shù)。要從256個(gè)數(shù)中選定某一個(gè)數(shù)，可以先提問(wèn)“是否大于128？”，不論回答是與否，則半數(shù)的可能事件被取消。如果繼續(xù)詢問(wèn)下去，每次詢問(wèn)將對(duì)應(yīng)一個(gè)1bit的信息量。例5數(shù)據(jù)壓縮基本原理5.15.1.1信息、數(shù)據(jù)與編碼1．信息例●隨著每次詢問(wèn)，有半數(shù)的可能事件被取消，這個(gè)過(guò)程由公式表示：可看出：對(duì)于256個(gè)數(shù)的詢問(wèn)只要進(jìn)行8次，即可確定一個(gè)具體的數(shù)。設(shè)：從N個(gè)數(shù)中選定任意一個(gè)數(shù)x的概率為p(x)，假定選定任意一個(gè)數(shù)的概率都相等，即p(x)=1/N，則信息量為：log2256=8bit如果將信息源所有可能事件的信息量進(jìn)行平均，即可得到信息的“熵”(熵是平均信息量)，信息源X的符號(hào)集為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例●隨著每次詢問(wèn)，有半數(shù)的可能事件被取消，這個(gè)過(guò)程由公式表示信息與數(shù)據(jù)2.信息可以用函數(shù)表示，該函數(shù)由信息論創(chuàng)始人C.E.Shannon香農(nóng)提出，以概率論的觀點(diǎn)對(duì)信息進(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)的先驗(yàn)概率。Pi

可以度量ai(i

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

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

——假設(shè)屏幕顯示分辨率為1024×768，字符為16×16點(diǎn)陣，每個(gè)字符用4個(gè)字節(jié)表示，則顯示一屏字符所需要的存儲(chǔ)空間為：（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制視頻信號(hào)，掃描速度25幀/s，樣本寬度24bit，采樣頻率最低10MHz，則一幀數(shù)字化圖像所占用的最少存儲(chǔ)空間為：

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)

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

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

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

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

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

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

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

冗余基本概念●

冗余

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

冗余度

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

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

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

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

無(wú)損壓縮編碼

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

有損壓縮編碼

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

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

統(tǒng)計(jì)編碼

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

霍夫曼編碼——無(wú)損編碼?！?/p>

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

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

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

●可以得到：

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

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

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

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

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

——跟蹤畫面上的活動(dòng)元素，并進(jìn)行向量計(jì)算，加以補(bǔ)償，然后再利用幀間預(yù)測(cè)進(jìn)行壓縮。適用于活動(dòng)元素少的可視電話和電視會(huì)議。42動(dòng)態(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)行編碼，實(shí)現(xiàn)數(shù)據(jù)壓縮的目的。幀內(nèi)圖像的壓縮比屬于中度壓縮，典型的壓縮像素編碼為2bit。2)預(yù)測(cè)圖像（Predictedpictures）

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

——又稱“B圖像”，可使用前一幀圖像和后一幀圖像作參照物，進(jìn)行雙向預(yù)測(cè)。雙向預(yù)測(cè)可以采用四種編碼技術(shù)，即幀內(nèi)圖像編碼、前向預(yù)測(cè)編碼、后向預(yù)測(cè)編碼、雙向預(yù)測(cè)編碼。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的速率傳輸視頻信號(hào)，即壓縮信號(hào)帶寬為1.5Mb/s。2)以單通道64kb/s、128kb/s和192kb/s的傳輸速率傳輸音頻信號(hào)。3)可通過(guò)差值運(yùn)算，在352×240畫面分辨率上顯示活動(dòng)圖像。4)分三個(gè)組成部分：視頻、音頻和系統(tǒng)。5)對(duì)于幀內(nèi)圖像，采用二維余弦變換、自適應(yīng)算術(shù)編碼、行程編碼、變字長(zhǎng)編碼，以及差分脈沖編碼（DPCM）進(jìn)行壓縮。6)幀間壓縮采用運(yùn)動(dòng)補(bǔ)償預(yù)測(cè)編碼和運(yùn)動(dòng)補(bǔ)償內(nèi)插編碼?！裨试S采用多種存儲(chǔ)介質(zhì)，如CD-ROM、數(shù)字錄音帶、磁盤、CD-R、

CD-RW、M.O.，以及ISDN集成服務(wù)數(shù)字網(wǎng)絡(luò)、LAN局域網(wǎng)絡(luò)等。設(shè)計(jì)MPEG壓縮算法時(shí)，要考慮隨機(jī)訪問(wèn)、快進(jìn)快退、檢索、聲像同步、容錯(cuò)、延時(shí)控制、可編輯特性以及視頻窗口設(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)壓縮信號(hào)帶寬為4~15Mb/s，即信號(hào)傳輸速率為4~15Mb/s。2)支持NTSC制720×480畫面分辨率，PAL制720×576畫面分辨率，畫面質(zhì)量達(dá)到廣播級(jí)，適用于HDTV高質(zhì)量電視信號(hào)的傳送與播放。3)解碼器同時(shí)支持MPEG-Ⅰ和MPEG-Ⅱ兩種標(biāo)準(zhǔn)。4)視頻信號(hào)的傳輸速率為30幀/s，音頻信號(hào)的質(zhì)量達(dá)到CD級(jí)。5)為了在畫面質(zhì)量、數(shù)據(jù)量和帶寬之間尋求最佳值，允許在一定范圍內(nèi)調(diào)整壓縮比。6)最高壓縮比為200:1，但由于畫面中活動(dòng)內(nèi)容的多少和人為調(diào)整壓縮比等因素的影響，大多數(shù)情況下達(dá)不到最高壓縮比。7)MPEG-Ⅱ用于DVD視頻信號(hào)的壓縮，DVD音頻信號(hào)的壓縮隨制式的不同而不同：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ù)測(cè)編碼原理

5.2.3變換編碼原理

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

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)的由來(lái)

5.3.2JPEG壓縮算法

5.3.3無(wú)失真預(yù)測(cè)編碼

5.3.4有失真DCT壓縮編碼5.4動(dòng)態(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無(wú)損壓縮編碼指的是什么？5.5數(shù)據(jù)壓縮具備哪兩個(gè)過(guò)程？5.6霍夫曼編碼的特點(diǎn)是什么？5.7采用JPEG壓縮格式的靜態(tài)圖像具有哪些主要特點(diǎn)？5.8動(dòng)態(tài)圖像壓縮主要解決哪些問(wèn)題？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í)通信的少數(shù)科學(xué)家和思想家之一。他是美國(guó)科學(xué)院院士、美國(guó)工程院院士、英國(guó)皇家學(xué)會(huì)會(huì)員、美國(guó)哲學(xué)學(xué)會(huì)會(huì)員。他獲得過(guò)許多榮譽(yù)和獎(jiǎng)勵(lì)。例如1949年Morris獎(jiǎng)、1955年Ballantine獎(jiǎng)、1962年Kelly獎(jiǎng)、1966年的國(guó)家科學(xué)獎(jiǎng)?wù)?、IEEE的榮譽(yù)獎(jiǎng)?wù)隆?978年Jaquard獎(jiǎng)、1983年Fritz獎(jiǎng)、1985年基礎(chǔ)科學(xué)京都獎(jiǎng)?！裣戕r(nóng)克勞德?香農(nóng)(ClaudeElwoodShannon，1916-2001)1916年4月30日誕生于美國(guó)密西根州的Petoskey。2001年2月24日，香農(nóng)在馬薩諸塞州Medford辭世，享年85歲。香農(nóng)被信息界譽(yù)為信息論及數(shù)字通信時(shí)代的奠基人。返回48香農(nóng)1948年則創(chuàng)立了信息論(informationtheHuffman樹(shù)的定義構(gòu)造Huffman樹(shù)Huffman編碼●Huffman(哈夫曼）編碼49Huffman樹(shù)的定義●Huffman(哈夫曼）編碼49Huffman樹(shù)也稱為最優(yōu)樹(shù)，是一類帶權(quán)路徑最短的二叉樹(shù)。樹(shù)的帶權(quán)路徑長(zhǎng)度定義為：

WPL=∑wklkk=1n

其中：

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

wi

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

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

WPLc=7x1+5x2+2x3+4x3=35√事實(shí)證明按哈夫曼樹(shù)構(gòu)造二叉樹(shù)，可得到很好的特性，應(yīng)用于實(shí)際問(wèn)題，可提高處理效率。（a）（b）（c）abcdabcdacbd777555222444●Huffman樹(shù)舉例51以下有三棵樹(shù)：WPLa=WPLb=WPLc=事實(shí)證由統(tǒng)計(jì)規(guī)律可知，考試成績(jī)的分布符合正態(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)計(jì)規(guī)律可知，考試成績(jī)的分布符合正態(tài)分布：-110分判定樹(shù)比較：若輸入1萬(wàn)個(gè)數(shù)據(jù)：按A的判定過(guò)程進(jìn)行操作，約需比較3.2萬(wàn)次而按B比較,則僅需2.2萬(wàn)次。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判定樹(shù)比較：若輸入1萬(wàn)個(gè)數(shù)據(jù)：a<60?a<70?a<80?構(gòu)造Huffman樹(shù)算法步驟：Step1將n個(gè)帶權(quán)值wi（i≤n）的結(jié)點(diǎn)構(gòu)成n棵二叉樹(shù)的集合T={T1，T2，……，Tn}，每棵二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)。Step2在T中選取兩個(gè)權(quán)值最小的結(jié)點(diǎn)作為左右子樹(shù)，構(gòu)成一個(gè)新的二叉樹(shù)，其根結(jié)點(diǎn)的權(quán)值取左右子樹(shù)權(quán)值之和；Step3在T中刪除這兩棵樹(shù)，將新構(gòu)成的樹(shù)加入到T中；Step4重復(fù)2）、3）步的操作，直到T中只含一棵樹(shù)為止，該樹(shù)就是Huffman樹(shù)?！駱?gòu)造Huffman樹(shù)54構(gòu)造Huffman樹(shù)算法步驟：●構(gòu)造Huffman樹(shù)54以權(quán)值分別為7，5，2，4的結(jié)點(diǎn)a、b、c、d構(gòu)造Huffman樹(shù)。T={abcd}cdT3246bT3T26511bT26511cd2418aT2711T1618a7T1bT3T251118a7T1b511cd264（d）T={T1}（c）T={aT2}（b）T={abT3}（a）T={abcd}代入T2代入T3代入T1示例●構(gòu)造Huffman樹(shù)舉例55以權(quán)值分別為7，5，2，4的結(jié)點(diǎn)a、b、c、d構(gòu)造Huffm編碼：用二進(jìn)制數(shù)的不同組合來(lái)表示字符的方法。前綴編碼：一種非等長(zhǎng)度的編碼(任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴)。Huffman編碼：一種非等長(zhǎng)度的編碼。以給定權(quán)值的結(jié)點(diǎn)構(gòu)造Huffman樹(shù)，按二進(jìn)制前綴編碼的方式構(gòu)成的編碼為Huffman編碼。

a0b01cd011編碼：a（0）

b（01）

c（011）

d（111）方法約定：1）左分支為‘0’2）右分支為‘1’3）由葉到根路徑上字符組成的二進(jìn)制串就是該葉結(jié)點(diǎn)的編碼。●Huffman編碼56編碼：用二進(jìn)制數(shù)的不同組合來(lái)表示字符的方法。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樹(shù)為：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)無(wú)失真編碼模式。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)。面向無(wú)損壓縮的應(yīng)用，采用無(wú)損預(yù)測(cè)壓縮。輸入圖像精度2-16位/像素/色，順序模式，采用Huffman或算術(shù)編碼?！褚粋€(gè)產(chǎn)品或系統(tǒng)必須包括對(duì)基線系統(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ù)中無(wú)符號(hào)整數(shù)轉(zhuǎn)換成有符號(hào)整數(shù)，進(jìn)行正變換。還原圖像時(shí)，解碼器輸出端經(jīng)過(guò)逆變換，重新建立圖像。由于運(yùn)算誤差和系數(shù)的量化，因而重建不很精確，與源圖像存在差異。2．DCT系數(shù)的量化量化依據(jù)量化表進(jìn)行，量化表中的元素由開(kāi)發(fā)人員根據(jù)人類視覺(jué)特性制作。量化的定義：CQ(u,v)=IntegerRound[F(u,v)/Q(u,v)]解量化是量化過(guò)程的逆運(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ù)對(duì)DCT系數(shù)進(jìn)行量化，該加權(quán)函數(shù)對(duì)于人視覺(jué)系統(tǒng)是最佳的。⒊Huffman編碼用Huffman可變字長(zhǎng)編碼器對(duì)量化系數(shù)進(jìn)行編碼。譯碼或者叫做解壓縮的過(guò)程與壓縮編碼過(guò)程相反。

有失真壓縮三個(gè)步驟

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

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

●量化器DCT正向變換構(gòu)造8×8的子圖輸入圖像N×N符號(hào)編碼器壓縮圖像顏色空間轉(zhuǎn)換零偏置轉(zhuǎn)換65圖像矩陣分塊JPEG壓縮步驟●量化器DCT正構(gòu)造8×8輸入人眼對(duì)亮度更敏感，提取亮度特征，將RGB轉(zhuǎn)換為YCbCr模型。對(duì)亮度采用特殊編碼：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人眼對(duì)亮度更敏感，提取亮度特征，將RGB轉(zhuǎn)換為YCbCr模型YUV是電視系統(tǒng)中采用的顏色模式。Y是亮度信號(hào)，U、V是色度信號(hào)。轉(zhuǎn)換公式:YUVRGB=

0.300.590.11-0.15-0.290.440.61-0.52-0.096RGB與YUV顏色空間的轉(zhuǎn)換●67YUV是電視系統(tǒng)中采用的顏色模式。Y是亮度信號(hào)，U、V是色度將圖像矩陣分為8×8的子塊，對(duì)每一塊單獨(dú)進(jìn)行DCT變換。根據(jù)人眼對(duì)亮度信號(hào)比對(duì)色度信號(hào)更加敏感的生理特性，將Y分量劃分為8×8的塊，將U、V分量劃分為16×16的塊。U、V分量的每一塊舍棄1/2的信息后形成一個(gè)8×8的矩陣。構(gòu)造子圖像●68將圖像矩陣分為8×8的子塊，對(duì)每一塊單獨(dú)進(jìn)行DCT變換。根據(jù)對(duì)變換后的DCT矩陣進(jìn)行量化處理（用表1和表2的量化矩陣分別對(duì)Y分量和U、V分量量化）。量化的原則：低頻部分用小值量化，高頻部分用大值量化，量化結(jié)果使高頻部分出現(xiàn)大量“0”。采用閾值作為子圖系數(shù)位置函數(shù)的量化方式。所有子圖使用同一個(gè)全局閾值模板，但閾值的取值與系數(shù)的位置相關(guān)，閾值模板給出了不同位置上系數(shù)的相應(yīng)閾值。對(duì)于亮度和顏色使用不同的量化閾值模板，并取整。量化處理●69對(duì)變換后的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ù)的個(gè)數(shù)，重新編排量化后的系數(shù)。方法是按照Z(yǔ)字形的式樣編排（把一個(gè)8×8的矩陣變成一個(gè)1×64的矢量，頻率較低的系數(shù)放在矢量的頂部）。

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

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

各存儲(chǔ)R、G、B的3個(gè)分量信息。

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

●例78變換后矩陣的左上角是圖像的低頻部分，越靠近右下角，頻率越高。對(duì)應(yīng)645×600的矩陣A，為了舍棄高頻部分，將該矩陣的高頻部分置為0值。在這令此時(shí)矩陣減小為387×360，數(shù)據(jù)量是原來(lái)的（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對(duì)應(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。去掉少量低頻部分對(duì)圖像的影響

●重構(gòu)后的圖像顯然對(duì)低頻部分的細(xì)小修改都會(huì)對(duì)圖像有很大的影響返回83將矩陣A的前15行和列置為0。去掉少量低頻部分對(duì)圖像的影響第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ù)測(cè)編碼原理

5.2.3變換編碼原理

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

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)的由來(lái)

5.3.2JPEG壓縮算法

5.3.3無(wú)失真預(yù)測(cè)編碼

5.3.4有失真DCT壓縮編碼5.4動(dòng)態(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ù)壓縮的對(duì)象是數(shù)據(jù)。數(shù)據(jù)是信息的載體，用來(lái)記錄和傳送信息。真正有用的不是數(shù)據(jù)本身，而是數(shù)據(jù)所攜帶的信息。大的數(shù)據(jù)量并不代表含有大的信息量。而對(duì)于去掉冗余的數(shù)據(jù)對(duì)信息沒(méi)有本質(zhì)的影響稱為壓縮?！駭?shù)據(jù)壓縮原理86數(shù)據(jù)壓縮基本原理5.1數(shù)據(jù)壓縮的對(duì)象是數(shù)據(jù)。數(shù)據(jù)是信息的載體5.1.1信息、數(shù)據(jù)與編碼我們了解的東西，描述它用的信息量少，不了解的東西，描述它用的信息量大。在信息論中，可以說(shuō)：信息是用不確定的度量來(lái)定義的；一個(gè)消息的可能性越小，其信息含量越大；消息的可能性越大，則信息含量越小。例自然現(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ù)。信息量越大，消息的可能性越小，反之亦然?！裥畔⒘浚簽榱藦腘個(gè)相等的可能事件中挑選出一個(gè)事件所需的信息度量和含量，所提問(wèn)“是或否”的次數(shù)。也就是說(shuō)，在N個(gè)事件中辨識(shí)特定的一個(gè)事件要詢問(wèn)“是或否”次數(shù)。要從256個(gè)數(shù)中選定某一個(gè)數(shù)，可以先提問(wèn)“是否大于128？”，不論回答是與否，則半數(shù)的可能事件被取消。如果繼續(xù)詢問(wèn)下去，每次詢問(wèn)將對(duì)應(yīng)一個(gè)1bit的信息量。例88數(shù)據(jù)壓縮基本原理5.15.1.1信息、數(shù)據(jù)與編碼1．信息例●隨著每次詢問(wèn)，有半數(shù)的可能事件被取消，這個(gè)過(guò)程由公式表示：可看出：對(duì)于256個(gè)數(shù)的詢問(wèn)只要進(jìn)行8次，即可確定一個(gè)具體的數(shù)。設(shè)：從N個(gè)數(shù)中選定任意一個(gè)數(shù)x的概率為p(x)，假定選定任意一個(gè)數(shù)的概率都相等，即p(x)=1/N，則信息量為：log2256=8bit如果將信息源所有可能事件的信息量進(jìn)行平均，即可得到信息的“熵”(熵是平均信息量)，信息源X的符號(hào)集為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例●隨著每次詢問(wèn)，有半數(shù)的可能事件被取消，這個(gè)過(guò)程由公式表示信息與數(shù)據(jù)2.信息可以用函數(shù)表示，該函數(shù)由信息論創(chuàng)始人C.E.Shannon香農(nóng)提出，以概率論的觀點(diǎn)對(duì)信息進(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)的先驗(yàn)概率。Pi

可以度量ai(i

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

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

——假設(shè)屏幕顯示分辨率為1024×768，字符為16×16點(diǎn)陣，每個(gè)字符用4個(gè)字節(jié)表示，則顯示一屏字符所需要的存儲(chǔ)空間為：（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制視頻信號(hào)，掃描速度25幀/s，樣本寬度24bit，采樣頻率最低10MHz，則一幀數(shù)字化圖像所占用的最少存儲(chǔ)空間為：

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)

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

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

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

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

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

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

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