1、MTIMTI數(shù)據(jù)壓縮基礎(chǔ)數(shù)據(jù)壓縮基礎(chǔ)多媒體技術(shù)第五章第五章2主要內(nèi)容 數(shù)據(jù)壓縮概述 經(jīng)典數(shù)據(jù)壓縮理論 香農(nóng)范諾與霍夫曼編碼 算術(shù)編碼 行程編碼 詞典編碼 預(yù)測(cè)編碼 變換編碼3什么是數(shù)據(jù)壓縮 數(shù)據(jù)壓縮就是在一定的精度損失條件下，以最少的數(shù)碼表示信源所發(fā)出的信號(hào)信源編碼信道編碼信道信道譯碼信源譯碼信源信宿4多媒體信源引起了“數(shù)據(jù)爆炸”如果不進(jìn)行數(shù)據(jù)壓縮 傳輸和存儲(chǔ)都難以實(shí)用化。多媒體數(shù)據(jù)數(shù)據(jù)壓縮的必要性5數(shù)數(shù)字字音音頻頻格格式式頻頻帶帶(Hz)帶帶寬寬(KHz)取取樣樣率率(KHz)量量化化位位數(shù)數(shù)存存儲(chǔ)儲(chǔ)容容量量(MB)電電話話20034003.2880.48會(huì)會(huì)議議電電視視伴伴音音507000

2、716141.68C CD D- -D DA A20200002044.1165.2922D DA AT T20200002048165.762數(shù)數(shù)字字音音頻頻廣廣播播20200002048165.766分鐘數(shù)字音頻信號(hào)需要的存儲(chǔ)空間1 16分鐘數(shù)字視頻信號(hào)需要的存儲(chǔ)空間1 17 時(shí)間域壓縮時(shí)間域壓縮迅速傳輸媒體信源迅速傳輸媒體信源 頻率域壓縮頻率域壓縮并行開通更多業(yè)務(wù)并行開通更多業(yè)務(wù) 空間域壓縮空間域壓縮降低存儲(chǔ)費(fèi)用降低存儲(chǔ)費(fèi)用 能量域壓縮能量域壓縮降低發(fā)射功率降低發(fā)射功率數(shù)據(jù)壓縮的好處8l壓縮比要大壓縮比要大l恢復(fù)后的失真小恢復(fù)后的失真小l壓縮算法要簡(jiǎn)單、速度快壓縮算法要簡(jiǎn)單、速度快l壓縮

3、能否用硬件實(shí)現(xiàn)壓縮能否用硬件實(shí)現(xiàn)數(shù)據(jù)壓縮技術(shù)實(shí)現(xiàn)的衡量標(biāo)準(zhǔn)9 無損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同；無損壓縮用于要求重構(gòu)的信號(hào)與原始信號(hào)完全一致的場(chǎng)合。 有損壓縮是指使用壓縮后的數(shù)據(jù)進(jìn)行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對(duì)原始資料表達(dá)的信息造成誤解。有損壓縮適用于重構(gòu)信號(hào)不一定非要和原始信號(hào)完全相同的場(chǎng)合。數(shù)據(jù)壓縮技術(shù)的分類10經(jīng)典數(shù)據(jù)壓縮理論信息論中的信源編碼理論解決的主要問題：（1）數(shù)據(jù)壓縮的理論極限（2）數(shù)據(jù)壓縮的基本途徑11離散事件的非平均自信息量 為了完全確定事件x(使后驗(yàn)概率為1)所必須提供的信息量稱為x事件

4、的非平均自信息量I(x)(log)(1log)(xpxpxI12熵（Entropy） 事件集合（樣本空間）X中每個(gè)事件的自信息量I(x)是定義在這個(gè)樣本空間上的一個(gè)隨機(jī)變量，所以我們要研究它的統(tǒng)計(jì)特性。其數(shù)學(xué)期望為： H(X)表明了集合X中隨機(jī)事件的平均不確定性，或者說平均信息量。 稱H(X)為一階信息熵或者簡(jiǎn)稱為熵(Entropy)XxXxxpxpxIxpXH)(log)()()()(13熵（Entropy） 在符號(hào)出現(xiàn)之前，熵表示符號(hào)集中的符號(hào)出現(xiàn)的平均不確定性；在符號(hào)出現(xiàn)之后，熵代表接收一個(gè)符號(hào)所獲得的平均信息量。 根據(jù)直覺，信源編碼的數(shù)據(jù)輸出速率（平均碼長(zhǎng)）與信源熵之間應(yīng)該有某種對(duì)應(yīng)關(guān)

5、系。14信源的概率分布與熵的關(guān)系 熵的大小與信源的概率分布模型有著密切的關(guān)系。 最大離散熵定理：當(dāng)與信源對(duì)應(yīng)的字符集中的各個(gè)字符為等概率分布時(shí)，熵具有極大值log2m。m為字符集中字符個(gè)數(shù)。mjjjppxH1log)(mjjp1115二進(jìn)制信源的熵 二進(jìn)制信源輸出一個(gè)二進(jìn)制數(shù)碼所攜帶的平均信息量最大為1bit。pH10.50116最大離散熵定理的應(yīng)用 對(duì)于同一個(gè)信源其總的信息量是不變的，如果能夠通過某種變換（編碼），使信源盡量等概率分布，則每個(gè)輸出符號(hào)所獨(dú)立攜帶的信息量增大，那么傳送相同信息量所需要的序列長(zhǎng)度就越短。 離散無記憶信源的冗余度隱含在信源符號(hào)的非等概率 分布之中。只要H（X）小于l

6、og2m，就存在數(shù)據(jù)壓縮的可能。17編碼信源 X1, X2, ,XL a1, a2, a3, aK編碼器 Y1, Y2, , YN b1, b2, b3, bD0,1信源字母表碼元表消息分組碼字18平均碼長(zhǎng)與熵 如果采用單字符二進(jìn)制編碼方式，設(shè)字符aj的編碼長(zhǎng)度為L(zhǎng)j，則信源字母表的平均碼長(zhǎng)為： 根據(jù)前面對(duì)二進(jìn)制信源的分析，有：KjjjLpL1)(1)(XHLLXHKjjjjKjjppLp121log 在Lj log2pj時(shí)，平均碼長(zhǎng)取得極小值H(X)19關(guān)于離散無記憶平穩(wěn)信源的結(jié)論 一階熵即為離散無記憶平穩(wěn)信源的壓縮極限。（基本極限） 只要信源不是等概率分布，就存在著數(shù)據(jù)壓縮的可能性。 數(shù)據(jù)

7、壓縮的基本途徑之一：使各字符的編碼長(zhǎng)度盡量等于字符的信息量。20熵編碼 熵編碼包括香農(nóng)范諾編碼、霍夫曼編碼和算術(shù)編碼，其宗旨在于找到一種編碼使得平均碼長(zhǎng)到達(dá)熵極限，基本思想就是對(duì)出現(xiàn)概率較大的符號(hào)取較短的碼長(zhǎng)，而對(duì)出現(xiàn)概率較小的符號(hào)取較大的碼長(zhǎng)。21霍夫曼編碼 具體步驟：（1）初始化（2）合并概率最小的兩個(gè)事件（3）排序（4）如果事件個(gè)數(shù)大于2則重復(fù)（2）和（3）（5）賦值（6）編碼22霍夫曼編碼舉例符號(hào)S1S2S3S4出現(xiàn)概率1/21/41/81/8等長(zhǎng)編碼00011011霍夫曼010110111H(X) = 1.75 L1=2 L2=1.75源S1S2S1S3S2S1S1S4等000100

8、1001000011霍0100110100011123霍夫曼編碼的局限性 利用霍夫曼編碼，每個(gè)符號(hào)的編碼長(zhǎng)度只能為整數(shù)，所以如果源符號(hào)集的概率分布不是2負(fù)n次方的形式，則無法達(dá)到熵極限。 輸入符號(hào)數(shù)受限于可實(shí)現(xiàn)的碼表尺寸 譯碼復(fù)雜 需要實(shí)現(xiàn)知道輸入符號(hào)集的概率分布 沒有錯(cuò)誤保護(hù)功能24香農(nóng)范諾編碼 香農(nóng)范諾編碼與Huffman編碼相反，采用從上到下的方法。 具體步驟為： （1）首先將編碼字符集中的字符按照出現(xiàn)頻度和概率進(jìn)行排序。 （2）用遞歸的方法分成兩部分，使兩個(gè)部分的概率和接近于相等。直至不可再分，即每一個(gè)葉子對(duì)應(yīng)一個(gè)字符。 （3）編碼。25香農(nóng)范諾編碼舉例A BC D EABCD EDE

9、符號(hào)符號(hào)ABCDE次數(shù)次數(shù)1577650101001126算術(shù)編碼 Huffman 編碼的局限性： Huffman 編碼使用整數(shù)個(gè)二進(jìn)制位對(duì)符號(hào)進(jìn)行編碼，這種方法在許多情況下無法得到最優(yōu)的壓縮效果。假設(shè)某個(gè)字符的出現(xiàn)概率為 80%，該字符事實(shí)上只需要 -log2(0.8) = 0.322 位編碼，但 Huffman 編碼一定會(huì)為其分配一位 0 或一位 1 的編碼?？梢韵胂螅麄€(gè)信息的 80% 在壓縮后都幾乎相當(dāng)于理想長(zhǎng)度的 3 倍左右。27算術(shù)編碼 基本思想：算術(shù)編碼不是將單個(gè)信源符號(hào)映射成一個(gè)碼字，而是把真?zhèn)€信源表示為實(shí)數(shù)線上的0到1之間的一個(gè)區(qū)間，其長(zhǎng)度等于該序列的概率，再在該區(qū)間內(nèi)選擇一

10、個(gè)代表性的小數(shù)，轉(zhuǎn)化為二進(jìn)制作為實(shí)際的編碼輸出。消息序列中的每個(gè)元素都要用來縮短這個(gè)區(qū)間。消息序列中元素越多，所得到的區(qū)間就越小，當(dāng)區(qū)間變小時(shí)，就需要更多的數(shù)位來表示這個(gè)區(qū)間。 采用算術(shù)編碼每個(gè)符號(hào)的平均編碼長(zhǎng)度可以為小數(shù)。28算術(shù)編碼舉例（一）符號(hào)00011011概率0.10.40.20.3初始區(qū)間0, 0.1)0.1, 0.5)0.5, 0.7)0.7, 1)29算術(shù)編碼舉例（二） 最后的子區(qū)間起始位置 85/256 = 0.01010101 子區(qū)間長(zhǎng)度 27/256 = 0.00011011 子區(qū)間尾 7/16 = 0.0111 取編碼區(qū)間中的一個(gè)值，最后編碼為：011符號(hào)01頻度1/4

11、3/4消息序列1011區(qū)間起始1/41/419/6485/256區(qū)間長(zhǎng)度3/43/169/6427/256信源分布：信源分布：30算術(shù)編碼的具體實(shí)現(xiàn) 因?yàn)閷?shí)際只能用有限長(zhǎng)的寄存器，這就要求將已編碼的高位碼字及時(shí)輸出，但又不能輸出過早，以免后續(xù)運(yùn)算還要調(diào)整已輸出的碼位。（請(qǐng)看參考書上給出的算法） 算術(shù)編碼每次遞推都要做乘法，所以效率比較低。二進(jìn)制算術(shù)編碼是一種實(shí)用的編碼算法，用移位代替了乘法，使效率大大提高。 自適應(yīng)算術(shù)編碼可以在編碼過程中根據(jù)符號(hào)出現(xiàn)的頻繁程度動(dòng)態(tài)的修改分布概率，這樣可以避免在編碼之前必須精確求出信源概率的難題。31行程編碼（RLE） 行程編碼（Run-Length Encod

12、ing）：它通過將信源中相同符號(hào)序列轉(zhuǎn)換成一個(gè)計(jì)數(shù)字段再加上一個(gè)重復(fù)字符標(biāo)志實(shí)現(xiàn)壓縮。 例如：RTTTTTTTTABBCDG被轉(zhuǎn)換為：R#8TABBCDG，其中“”作為轉(zhuǎn)義字符，表明其后所跟的字符表示長(zhǎng)度。 行程編碼多用于黑白二值圖像的壓縮中。例如00000000111111111111000001111111被轉(zhuǎn)化為一系列黑串和白串長(zhǎng)度的編碼：81257。因?yàn)榇L(zhǎng)度并非等概率分布，所以一般要配合以統(tǒng)計(jì)編碼（Huffman編碼）。32詞典編碼 詞典編碼主要利用數(shù)據(jù)本身包含許多重復(fù)的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我們?nèi)绻靡恍┖?jiǎn)單的代號(hào)代替這些字符串，就可以實(shí)現(xiàn)壓縮

13、，實(shí)際上就是利用了信源符號(hào)之間的相關(guān)性。字符串與代號(hào)的對(duì)應(yīng)表就是詞典。 實(shí)用的詞典編碼算法的核心就是如何動(dòng)態(tài)地形成詞典，以及如何選擇輸出格式以減小冗余。33第一類詞典編碼 第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的“指針”。34第二類詞典編碼 第二類算法的想法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語詞典 (dictionary of the phrases)”，這種短語可以是任意字符的組合。編碼數(shù)據(jù)過程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的“短語”時(shí)，編碼器就輸出這個(gè)詞典中的短語的“索引號(hào)”，而不是短

14、語本身。35預(yù)測(cè)編碼 預(yù)測(cè)編碼是數(shù)據(jù)壓縮理論的一個(gè)重要分支。它根據(jù)離散信號(hào)之間存在一定相關(guān)性的特點(diǎn)，利用前面的一個(gè)或多個(gè)信號(hào)對(duì)下一個(gè)信號(hào)進(jìn)行預(yù)測(cè)，然后對(duì)實(shí)際值和預(yù)測(cè)值的差（預(yù)測(cè)誤差）進(jìn)行編碼。如果預(yù)測(cè)比較準(zhǔn)確，那么誤差信號(hào)就會(huì)很小，就可以用較少的碼位進(jìn)行編碼，以達(dá)到數(shù)據(jù)壓縮的目的。 第n個(gè)符號(hào)Xn的熵滿足：).|(.)|()|()(121211xxxxHxxxHxxHxHnnnnnnnnn所以參與預(yù)測(cè)的符號(hào)越多，預(yù)測(cè)就越準(zhǔn)確，該信源的不確定性就越小，數(shù)碼率就可以降低。36DPCM編碼預(yù)測(cè)器xkekxkxk-ekDPCM是有損型還是無損型關(guān)鍵看對(duì)預(yù)測(cè)誤差是有損型還是無損型關(guān)鍵看對(duì)預(yù)測(cè)誤差ek如何

15、編碼。預(yù)測(cè)方程式 線性預(yù)測(cè)： 如果ai是常數(shù)，則為時(shí)不變線性預(yù)測(cè)，否則為自適應(yīng)線性預(yù)測(cè)（ADPCM） 最簡(jiǎn)單的預(yù)測(cè)方程：11)(kiiikxkax),.,(1321kxxxxfxkk1kkxx最佳線性預(yù)測(cè)使誤差函數(shù)達(dá)到最小值的預(yù)測(cè)方程式叫做最佳線性預(yù)測(cè)。求最佳線性預(yù)測(cè)的各個(gè)參數(shù)ai，列方程組：2)(nnxxEmse)1,.,2,1(,0)(2niaxxEinn11niiinxax代入得到聯(lián)立方程組：)1,.,2,1(, 11nixxEaxxEnlillin如果為一階線性預(yù)測(cè)，則可求得：2111nnnxExxEa11nnxax39圖像信號(hào)的預(yù)測(cè)編碼 一副數(shù)字圖像可以看成一個(gè)空間點(diǎn)陣，圖像信號(hào)不僅

16、在水平方向是相關(guān)的，在垂直方向也是相關(guān)的。根據(jù)已知樣值與待預(yù)測(cè)樣值間的位置關(guān)系，可以分為： （1）一維預(yù)測(cè)（行內(nèi)預(yù)測(cè)）：利用同一行上相鄰的樣值進(jìn)行預(yù)測(cè)。 （2）二維預(yù)測(cè)（幀內(nèi)預(yù)測(cè)）：利用同一行和前面幾行的數(shù)據(jù)進(jìn)行預(yù)測(cè)。 （3）三維預(yù)測(cè)（幀間預(yù)測(cè)）：利用相鄰幾幀（或不同波段）上的取樣值進(jìn)行預(yù)測(cè)40靜止圖像的二維預(yù)測(cè)編碼 這種壓縮算法被應(yīng)用到JPEG標(biāo)準(zhǔn)的無損壓縮模式之中，中等復(fù)雜程度的圖像壓縮比可達(dá)到2:1。cabx選擇值預(yù)測(cè)值0非預(yù)測(cè)1a2b3c4a+b-c5a+(b-c)/26b+(a-c)/27(a+b)/2d三鄰域預(yù)測(cè)法三鄰域預(yù)測(cè)法41活動(dòng)圖像的幀間預(yù)測(cè)編碼 視頻信號(hào)的冗余度主要體現(xiàn)在空間相關(guān)性（幀內(nèi)）、時(shí)間相關(guān)性（幀間）和色度空間表示