第六章多媒體數(shù)據(jù)壓縮

2023/2/61多媒體技術(shù)22023/2/6第6章多媒體數(shù)據(jù)壓縮常用的無(wú)損數(shù)據(jù)壓縮方法6.3常用的有損數(shù)據(jù)壓縮方法6.4多媒體數(shù)據(jù)壓縮概述6.1數(shù)據(jù)壓縮的技術(shù)基礎(chǔ)6.232023/2/66.1多媒體數(shù)據(jù)壓縮概述6.1.1多媒體數(shù)據(jù)壓縮的必要性⑴原始采樣的媒體數(shù)據(jù)量巨大⑵有效利用存儲(chǔ)器存儲(chǔ)容量⑶提高通信線路的傳輸效率⑷消除計(jì)算機(jī)系統(tǒng)處理視頻I/O瓶頸42023/2/66.1多媒體數(shù)據(jù)壓縮概述6.1.2多媒體數(shù)據(jù)壓縮的可能性常見的圖像數(shù)據(jù)冗余種類：⑴空間冗余⑵時(shí)間冗余⑶結(jié)構(gòu)冗余⑷知識(shí)冗余⑸視覺(jué)冗余52023/2/6空間冗余

在任何一幅圖像中，均有由許多灰度或顏色都相同的鄰近像素組成的區(qū)域，它們形成了一個(gè)性質(zhì)相同的集合塊，即它們相互之間具有空間上的強(qiáng)相關(guān)性，在圖像中就表現(xiàn)為空間冗余。例如，一塊表面顏色均勻的區(qū)域中所有點(diǎn)的光強(qiáng)和色彩以及飽和度都是相同的，這就是空間冗余。62023/2/6時(shí)間冗余這是序列圖像（電視圖像、運(yùn)動(dòng)圖像）表示中經(jīng)常包含的冗余。圖像序列中兩幅相鄰的圖像有較大的相關(guān)，這反映為時(shí)間冗余。運(yùn)動(dòng)圖像的相鄰幀往往包含相同的背景和移動(dòng)物體，只不過(guò)物體所在的位置略有不同，由于相鄰幀記錄了相鄰時(shí)刻的同一場(chǎng)景，所以稱為時(shí)間冗余。72023/2/6結(jié)構(gòu)冗余在有些圖像的紋理區(qū)，圖像的像素值存在著明顯的分布模式。例如，方格狀的板圖案等，我們稱此為結(jié)構(gòu)冗余。已知分布模式，可以通過(guò)某一過(guò)程生成圖像。82023/2/6知識(shí)冗余有些圖像的理解與某些知識(shí)有相當(dāng)大的相關(guān)性。例如：狗的圖像有固定的結(jié)構(gòu)，狗有四條腿，頭部有眼、鼻、耳朵，有尾巴等。這類規(guī)律性的結(jié)構(gòu)可由先驗(yàn)知識(shí)和背景知識(shí)得到，我們稱此類冗余為知識(shí)冗余。92023/2/6視覺(jué)冗余人類的視覺(jué)系統(tǒng)對(duì)圖像場(chǎng)的敏感度是非均勻的。但是，在記錄原始的圖像數(shù)據(jù)時(shí)，通常假定視覺(jué)系統(tǒng)近似線性的和均勻的，對(duì)視覺(jué)敏感和不敏感的部分同等對(duì)待，從而產(chǎn)生比理想編碼（即把視覺(jué)敏感和不敏感的部分區(qū)分開來(lái)的編碼）更多的數(shù)據(jù)，這就是視覺(jué)冗余。人類視覺(jué)系統(tǒng)的一般分辨能力估計(jì)為26灰度等級(jí)，而一般圖像的量化采用的是28的灰度等級(jí)。這也被稱之為視覺(jué)冗余。102023/2/66.1多媒體數(shù)據(jù)壓縮概述6.1.3多媒體數(shù)據(jù)壓縮的原理1.圖像數(shù)據(jù)壓縮的主要依據(jù)有兩個(gè)一是圖像數(shù)據(jù)中有許多重復(fù)的數(shù)據(jù)，使用數(shù)學(xué)方法來(lái)表示這些重復(fù)數(shù)據(jù)就可以減少數(shù)據(jù)量；另一個(gè)依據(jù)是人眼睛對(duì)圖像細(xì)節(jié)和顏色的辨認(rèn)有一個(gè)極限，把超過(guò)極限的部分去掉，這也就達(dá)到了數(shù)據(jù)壓縮的目的?；跀?shù)據(jù)冗余的壓縮技術(shù)是無(wú)損壓縮技術(shù)基于人眼視覺(jué)特性的壓縮技術(shù)是有損壓縮技術(shù)112023/2/66.1.3多媒體數(shù)據(jù)壓縮的原理2.圖像壓縮說(shuō)明視頻壓縮與語(yǔ)音相比，語(yǔ)音的數(shù)據(jù)量較小，且基本壓縮方法已經(jīng)成熟，目前的數(shù)據(jù)壓縮研究主要集中于圖像和視頻信號(hào)的壓縮方面。壓縮處理過(guò)程有兩個(gè)過(guò)程，編碼過(guò)程是將原始數(shù)據(jù)經(jīng)過(guò)編碼進(jìn)行壓縮，以便存儲(chǔ)與傳輸；解碼過(guò)程是對(duì)編碼數(shù)據(jù)進(jìn)行解碼，還原為可以使用的數(shù)據(jù)。122023/2/66.1.3多媒體數(shù)據(jù)壓縮的原理3.與壓縮相關(guān)的指標(biāo)衡量一種數(shù)據(jù)壓縮技術(shù)的好壞有四個(gè)重要的指標(biāo)：⑴壓縮比大：即壓縮前后所需要的信息存儲(chǔ)量之比要大。⑵算法簡(jiǎn)單：實(shí)現(xiàn)壓縮的算法簡(jiǎn)單，壓縮、解壓速度快，盡可能地做到實(shí)時(shí)壓縮解壓。⑶恢復(fù)效果好：恢復(fù)效果好，要盡可能地恢復(fù)原始數(shù)據(jù)。⑷壓縮能否用硬件實(shí)現(xiàn)。132023/2/66.1.3多媒體數(shù)據(jù)壓縮的原理142023/2/66.1.3多媒體數(shù)據(jù)壓縮的原理⑴冗余壓縮法也稱無(wú)損壓縮法，是指使用壓縮后的數(shù)據(jù)可以解壓縮，且解壓之后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)完全相同。它利用數(shù)據(jù)的統(tǒng)計(jì)冗余進(jìn)行壓縮，可完全恢復(fù)原始數(shù)據(jù)而不引入任何失真，但壓縮率受到數(shù)據(jù)統(tǒng)計(jì)冗余度的理論限制，一般為2:1到5:1。152023/2/66.1.3多媒體數(shù)據(jù)壓縮的原理⑵熵壓縮法也稱有損壓縮法，有失真壓縮，是指使用壓縮后的數(shù)據(jù)進(jìn)行解壓縮，解壓之后的數(shù)據(jù)與原來(lái)的數(shù)據(jù)有所不同，但不會(huì)讓人對(duì)原始資料表達(dá)的信息造成誤解。162023/2/66.1.3多媒體數(shù)據(jù)壓縮的原理⑶熵壓縮法與冗余壓縮法的比較在圖像壓縮系統(tǒng)組成中，變換和編碼是無(wú)損耗的，而量化是有損耗的。無(wú)損壓縮方法僅利用了統(tǒng)計(jì)冗余，而沒(méi)有利用量化器。有損壓縮方法既利用了統(tǒng)計(jì)冗余又采用了量化器，利用了心理視覺(jué)冗余。172023/2/66.1.4數(shù)據(jù)壓縮方法的分類1.根據(jù)編、解碼后數(shù)據(jù)是否一致來(lái)進(jìn)行分類，數(shù)據(jù)壓縮的方法一般被劃分為兩類：可逆編碼（無(wú)損編碼）。此種方法的解碼圖像與原始圖像嚴(yán)格相同，壓縮比大約在2:1~5:1之間。主要編碼有Huffman編碼、算術(shù)編碼、行程長(zhǎng)度編碼等。不可逆編碼（有損編碼）。此種方法的解碼圖像與原始圖像存在一定的誤差，但視覺(jué)效果一般可以接受，壓縮比可以從幾倍到上百倍調(diào)節(jié)。常用的編碼有變換編碼和預(yù)測(cè)編碼。182023/2/66.1.4數(shù)據(jù)壓縮方法的分類2.根據(jù)壓縮方法的原理，可將其具體劃分為以下幾種：⑴量化與向量量化編碼⑵預(yù)測(cè)編碼

⑶變換編碼⑷信息熵編碼⑸混合編碼變換編碼與預(yù)測(cè)編碼相結(jié)合192023/2/6量化與向量量化編碼對(duì)像元點(diǎn)進(jìn)行量化時(shí)，除了每次僅量化一個(gè)點(diǎn)的方法外，也可以考慮一次量化多個(gè)點(diǎn)的做法，這種方法稱為向量量化。即利用相鄰數(shù)據(jù)間的相關(guān)性，將數(shù)據(jù)系列分組進(jìn)行量化。202023/2/6預(yù)測(cè)編碼預(yù)測(cè)編碼預(yù)測(cè)編碼是根據(jù)離散信號(hào)之間存在著一定關(guān)聯(lián)性的特點(diǎn)，利用前面一個(gè)或多個(gè)信號(hào)預(yù)測(cè)下一個(gè)信號(hào)進(jìn)行，然后對(duì)實(shí)際值和預(yù)測(cè)值的差（預(yù)測(cè)誤差）進(jìn)行編碼。如果預(yù)測(cè)比較準(zhǔn)確，誤差就會(huì)很小。在同等精度要求的條件下，就可以用比較少的比特進(jìn)行編碼，達(dá)到壓縮數(shù)據(jù)的目的。如：增量調(diào)制（DM）、差分脈沖編碼調(diào)制（DPCM）、自適應(yīng)增量調(diào)制（ADPCM）等。主要用于聲音編碼。212023/2/6變換編碼變換編碼將圖像時(shí)域信號(hào)轉(zhuǎn)換為頻域信號(hào)進(jìn)行處理。數(shù)據(jù)處理時(shí)可以將主要的注意力集中在相對(duì)較小的區(qū)域，從而實(shí)現(xiàn)數(shù)據(jù)壓縮。一般采用正交變換，如：離散余弦變換（DCT）、離散傅立葉變換（DFT）222023/2/6信息熵編碼信息熵原理讓出現(xiàn)概率大的信號(hào)用較短的碼字表示，反之用較長(zhǎng)的碼字表示。常見的編碼方法Huffman編碼Shannon編碼算術(shù)編碼232023/2/66.2數(shù)據(jù)壓縮的技術(shù)基礎(chǔ)6.2.1熵的概念表示一條信息中真正需要編碼的信息量，即數(shù)據(jù)壓縮的理論極限。對(duì)于任何一種無(wú)損數(shù)據(jù)壓縮，最終的數(shù)據(jù)量一定大于信息熵，數(shù)據(jù)量越接近于熵值，說(shuō)明其壓縮效果越好。242023/2/66.2數(shù)據(jù)壓縮的技術(shù)基礎(chǔ)6.2.2信息熵的計(jì)算1.信息量信息量是指從N個(gè)等概率事件中選出一個(gè)事件所需要的信息含量。設(shè)從N個(gè)數(shù)中選定任一個(gè)數(shù)xj的概率為p(xj)，假定選定任意一個(gè)數(shù)的概率都相等，即p(xj)＝1/N，因此定義信息量如下：概率相等概率不等252023/2/66.2.2信息熵的計(jì)算2.信息熵:平均信息量信源X發(fā)出的xj（j=1,2,…,n）共n個(gè)隨機(jī)事件，每個(gè)事件產(chǎn)生的平均信息量為：H(X)稱為信源X的“熵”，即信源X發(fā)出任意一個(gè)隨機(jī)變量的平均信息量。其中：等概率事件的熵最大，假設(shè)有N個(gè)事件，則此時(shí)熵為：最大熵概率×信息量262023/2/66.2.3信息熵的范圍當(dāng)P(x1)＝1時(shí)，P(x2)＝P(x3)＝…＝P(xj)＝0，則此時(shí)熵為：由上可得熵的范圍為：最小熵272023/2/66.2.4平均碼長(zhǎng)在編碼中用熵值來(lái)衡量是否為最佳編碼。若以Lc表示編碼器輸出碼字的平均碼長(zhǎng)，則當(dāng)Lc≥H(X)有冗余，不是最佳。Lc＜H(X)不可能。Lc＝H(X)最佳編碼（Lc稍大于H(X)）。熵值為平均碼長(zhǎng)Lc的下限。平均碼長(zhǎng)Lc的計(jì)算公式為：（j=1,2,…,n）其中：P(xj)是信源X發(fā)出xj的概率，L(xj)為xj的編碼長(zhǎng)。282023/2/66.2.5冗余度、編碼效率與壓縮比在數(shù)字圖像通信系統(tǒng)中，冗余度、編碼效率與壓縮比是衡量信源特性以及編解碼設(shè)備性能的重要指標(biāo)。設(shè)原圖像的平均碼長(zhǎng)為L(zhǎng)，熵為H(X)，壓縮后圖像的平均碼長(zhǎng)為L(zhǎng)c，則編碼效率為：冗余度為：1-壓縮比為：Lc292023/2/66.3常用的無(wú)損數(shù)據(jù)壓縮方法6.3.1Huffman編碼6.3.2算術(shù)編碼6.3.3行程RLE編碼6.3.4詞典編碼302023/2/66.3.1Huffman編碼基本原理依據(jù)信源字符出現(xiàn)的概率大小來(lái)構(gòu)造代碼，對(duì)出現(xiàn)概率較大的信源字符，給予較短碼長(zhǎng)，而對(duì)于出現(xiàn)概率較小的信源字符，給予較長(zhǎng)的碼長(zhǎng)，最后使得編碼的平均碼字最短。312023/2/66.3.1Huffman編碼具體的編碼步驟將信源出現(xiàn)的概率由大到小排序。將兩處最小概率組合相加，形成新概率。將新概率與未編碼的字符一起重新排序。重復(fù)步驟2、3，直到出現(xiàn)的概率和為1。分配代碼代碼分配從最后一步開始反向進(jìn)行，對(duì)最后兩個(gè)概率一個(gè)賦予0代碼，一個(gè)賦予1代碼。記錄下從樹的根到每個(gè)信源符號(hào)終節(jié)點(diǎn)的0和1序列。至于哪個(gè)為“1”哪個(gè)為“0”則無(wú)關(guān)緊要，最后的結(jié)果僅僅是分配的代碼不同，而代碼的平均長(zhǎng)度是相同的。322023/2/66.3.1Huffman編碼Huffman編碼中求平均碼長(zhǎng)的方法：概率×碼長(zhǎng)332023/2/66.3.1Huffman編碼Huffman編碼練習(xí)一:設(shè)輸入圖像的灰度級(jí){a1,a2,a3,a4,a5,a6}出現(xiàn)的概率分別是0.4、0.2、0.12、0.15、0.1、0.03。試進(jìn)行哈夫曼編碼，并計(jì)算平均碼字長(zhǎng)度。342023/2/66.3.1Huffman編碼Huffman編碼練習(xí)二:信源符號(hào)的概率如下，請(qǐng)按要求作答：畫出其Huffman編碼的編碼樹給出各信源符號(hào)的碼字與碼長(zhǎng)計(jì)算該信源的平均碼長(zhǎng)。（說(shuō)明：大概率符號(hào)賦予0，小概率符號(hào)賦予l，相同概率情況下上面的是0，下面的是1。）XX1X2X3X4X5X6P(X)0.350.250.200.10.050.05352023/2/6Huffman編碼練習(xí)一答案最終編碼結(jié)果為：a1=1,a2=011,a3=001,a4=010,

a5=0001,a6=00001010010362023/2/6Huffman編碼練習(xí)一答案據(jù)公式圖像信源熵為：H(X)=-(0.4×log20.4+0.2×log20.2+0.12×log20.12+0.15×log20.15+0.1×log20.1+0.03×log20.03)=2.25bit根據(jù)哈夫曼編碼結(jié)果，平均碼字長(zhǎng)度：Lc=0.4×1+0.2×3+0.15×3+0.12×3+0.1×4+0.03×4=2.33編碼效率、壓縮比和冗余度分別為：96.6%、1.2、3.4%r=1-η=3.4%372023/2/6Huffman編碼練習(xí)二答案382023/2/66.3.1Huffman編碼Huffman編碼注意事項(xiàng)哈夫曼編碼沒(méi)有錯(cuò)誤保護(hù)功能，在譯碼時(shí)，如果碼串中沒(méi)有錯(cuò)誤，那么就能一個(gè)接一個(gè)的正確譯出代碼。但如果碼串中有錯(cuò)誤，哪怕僅是1位出現(xiàn)錯(cuò)誤，不但這個(gè)碼本身譯錯(cuò)，后面的譯碼可能全錯(cuò)，這種現(xiàn)象稱為錯(cuò)誤傳播（ErrorPropagation）。哈夫曼編碼是可變長(zhǎng)度碼，很難隨意查找或調(diào)用壓縮文件中間的內(nèi)容，然后再譯碼，這就需要在存儲(chǔ)代碼之前加以考慮。392023/2/66.3.2算術(shù)編碼算術(shù)編碼（arithmeticcodingAC）是利用0和1之間的間隔來(lái)表示信源編碼的一種方法，其編碼值是間隔的上、下限包含的相同二進(jìn)制。編碼過(guò)程中的間隔決定了符號(hào)壓縮后的輸出。算術(shù)編碼用到兩個(gè)基本的參數(shù)符號(hào)的概率和它的編碼間隔。信源符號(hào)的概率決定壓縮編碼的效率，也決定編碼過(guò)程中信源符號(hào)的間隔，而這些間隔包含在0到1之間。402023/2/66.3.2算術(shù)編碼編碼過(guò)程:設(shè)信源符號(hào)為{A,B,C,D}，其概率分別為{0.1,0.4,0.2,0.3}，按概率可把間隔[0,1]分成4個(gè)子間隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1]，其中[x,y)表示半開放間隔，即包含x不包含y，如下表所示。符號(hào)ABCD概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1]412023/2/66.3.2算術(shù)編碼如果消息序列的輸入為：CADACDB，其編碼過(guò)程如下：首先輸入的符號(hào)是C，找到它的編碼范圍是[0.5,0.7)；由于消息中第2個(gè)符號(hào)A的編碼范圍是[0,0.1)，因此它的間隔就取[0.5,0.7)的第一個(gè)1/10作為新間隔[0.5,0.52)；編碼第3個(gè)符號(hào)D時(shí)取新間隔為[0.514,0.52)；編碼第4個(gè)符號(hào)A時(shí)，取新間隔為[0.514,0.5146)

，…。422023/2/66.3.2算術(shù)編碼符號(hào)ABCD概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1]432023/2/66.3.2算術(shù)編碼消息的編碼輸出可以是最后一個(gè)間隔中的任意數(shù)，整個(gè)編碼過(guò)程如下圖所示。最后在[0.5143876,0.514402)中選擇一個(gè)數(shù)作為編碼輸出值：0.51439。解碼時(shí)，解碼器由編碼輸出值：0.51439，可馬上解得一個(gè)字符為C，然后依次得到唯一解A,D,A,C,D,B。442023/2/66.3.2算術(shù)編碼步驟譯碼間隔譯碼10.51439在間隔[0.5,0.7)1020.51439在間隔[0.5,0.7)的第1個(gè)1/100030.51439在間隔[0.5,0.52)的第7個(gè)1/101140.51439在間隔[0.514,0.52)的第1個(gè)1/100050.51439在間隔[0.514,0.5146)的第5個(gè)1/101060.51439在間隔[0.5143,0.51442)的第7個(gè)1/101170.51439在間隔[0.51439,0.5143948)的第1個(gè)1/10018譯碼消息：10001100101101

譯碼過(guò)程如下：452023/2/66.3.2算術(shù)編碼在算術(shù)編碼中需要注意的幾個(gè)問(wèn)題：由于計(jì)算機(jī)精度不可能無(wú)限長(zhǎng)，運(yùn)算中容易出現(xiàn)溢出，但多數(shù)機(jī)器都有16位、32位或者64位的精度，因此可使用比例縮放方法解決。算術(shù)編碼器對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔[0,1)中的一個(gè)實(shí)數(shù)，因此譯碼器在接受到所有位之前不能進(jìn)行譯碼。算術(shù)編碼也是一種對(duì)錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會(huì)導(dǎo)致整個(gè)消息譯錯(cuò)。462023/2/66.3.2算術(shù)編碼算術(shù)編碼練習(xí)一:假設(shè)有4個(gè)符號(hào)的信源，它門的概率如下表所示：輸入序列為Xn:a2,a1,a3,…。試畫出它的編碼過(guò)程信源符號(hào)aia1a2a3a4概率PiP1＝0.5P2＝0.25P3＝0.125P4＝0.125初始編碼間隔[0,0.5)[0.5,0.75)[0.75,0.875)[0.875,1)472023/2/66.3.2算術(shù)編碼算術(shù)編碼練習(xí)二：假設(shè)信源符號(hào)為{1,0}，如果消息序列的輸入為1101。這些符號(hào)的概率分別為:畫出其編碼過(guò)程！！信源01概率1/43/4編碼間隔[0,1/4)[1/4,1]482023/2/6算術(shù)編碼練習(xí)一答案最后的編碼結(jié)果是：[0.59375,0.609375]492023/2/6算術(shù)編碼練習(xí)二答案最后的編碼結(jié)果是：[121/256,37/64)502023/2/66.3.3行程長(zhǎng)度編碼RLE（Run-LengthEncoding）是一個(gè)針對(duì)包含有順序排列的多次重復(fù)的數(shù)據(jù)的壓縮方案。其原理就是把一系列的重復(fù)值用一個(gè)單獨(dú)的值再加上一個(gè)計(jì)數(shù)值來(lái)取代，行程長(zhǎng)度就是連續(xù)且重復(fù)的單元數(shù)目。如果想得到原始數(shù)據(jù)，只需展開這個(gè)編碼就可以了。512023/2/66.3.3行程長(zhǎng)度編碼例如，計(jì)算機(jī)制作圖像中，不需要存儲(chǔ)每一個(gè)像素的顏色值，而僅存儲(chǔ)一個(gè)像素的顏色值以及具有相同顏色的像素?cái)?shù)目就可以，或者存儲(chǔ)一個(gè)像素的顏色值，以及具有相同顏色值的行數(shù)，這種壓縮編碼稱為行程編碼。具有相同顏色的連續(xù)的像素?cái)?shù)目稱為行程長(zhǎng)度。522023/2/66.3.3行程長(zhǎng)度編碼如圖所示，假定一幅灰度圖像，第n行的像素值為：用RLE編碼方法得到的代碼為：3150841160。代碼紅色斜體表示的數(shù)字是行程長(zhǎng)度，后面的數(shù)字代表像素的顏色值。例如紅色斜體字50代表有連續(xù)50個(gè)像素具有相同的顏色值，它的顏色值是8。532023/2/66.3.3行程長(zhǎng)度編碼對(duì)比RLE編碼前后的代碼數(shù)可以發(fā)現(xiàn)，在編碼前要用73個(gè)代碼表示這一行的數(shù)據(jù)，而編碼后只要用10個(gè)代碼表示代表原來(lái)的73個(gè)代碼，壓縮前后的數(shù)據(jù)量之比約為7:1，即壓縮比為7:1。這說(shuō)明RLE確實(shí)是一種壓縮技術(shù)，而且編碼技術(shù)實(shí)用。542023/2/66.3.3行程長(zhǎng)度編碼RLE的性能好壞主要取決于圖像本身的特點(diǎn)。RLE壓縮編碼尤其適用于計(jì)算機(jī)生成的圖像，對(duì)減少圖像文件的存儲(chǔ)空間非常有效。然而，由于顏色豐富的自然圖像在同一行上具有相同顏色的連續(xù)像素往往很少，而連續(xù)幾行都具有相同顏色值的連續(xù)行數(shù)就更少，如果仍然使用RLE編碼方法，不僅不能壓縮圖像數(shù)據(jù)，反而可能使原來(lái)的圖像數(shù)據(jù)變得更大。552023/2/66.3.3行程長(zhǎng)度編碼譯碼時(shí)按照與編碼時(shí)采用的相同規(guī)則進(jìn)行，還原后得到的數(shù)據(jù)與壓縮前的數(shù)據(jù)完全相同。因此，RLE屬于無(wú)損壓縮技術(shù)。它被用于BMP、JPEG/MPEG、TIFF和PDF等編碼之中，還被用于傳真機(jī)。562023/2/66.3.4詞典編碼詞典編碼屬于無(wú)損壓縮技術(shù)，其根據(jù)是數(shù)據(jù)本身包含有重復(fù)代碼序列這個(gè)特性。詞典編碼的種類較多，歸納起來(lái)有兩類。第一類詞典編碼LZ77、LZSS第二類詞典編碼LZ78、LZW572023/2/6第一類詞典編碼第一類詞典編碼的基本思想是查找正在壓縮的字符序列是否在前面輸入的數(shù)據(jù)中出現(xiàn)過(guò)，如果是，則用指向早期出現(xiàn)過(guò)的字符串的“指針”替代重復(fù)的字符串。582023/2/6第一類詞典編碼這里所指的“詞典”是指用以前處理過(guò)的數(shù)據(jù)來(lái)表示編碼過(guò)程中遇到的重復(fù)部分。這類編碼中的所有算法都是以AbrahamLempel和JakobZiv在1977年開發(fā)和發(fā)表的稱為L(zhǎng)Z77算法為基礎(chǔ)的。LZSS算法——LZ77的改進(jìn)方法

592023/2/6LZ77算法輸入數(shù)據(jù)流(inputstream):待壓縮的字符序列字符(character):輸入數(shù)據(jù)流中的基本單元。編碼位置(codingposition):輸入數(shù)據(jù)流中當(dāng)前要編碼的字符位置，前向緩沖器的開始字符。前向緩沖器(lookaheadbuffer):存放從編碼位置到輸入數(shù)據(jù)流結(jié)束的字符序列的存儲(chǔ)器。窗口(Window):包含W個(gè)字符的窗口，字符從編碼位置開始向后數(shù)。指針(Pointer):指向窗口中的匹配串且含長(zhǎng)度。602023/2/6LZ77算法LZ77編碼算法的核心是查找從前向緩沖器開始的最長(zhǎng)的匹配串。具體執(zhí)行步驟如下：把編碼位置設(shè)置到輸入數(shù)據(jù)流的開始。查找窗口中最長(zhǎng)的匹配串。輸出(Pointer，Length)Characters，其中Pointer是指向窗口中匹配串的指針，Length表示匹配字符的長(zhǎng)度，Characters是前向緩沖器中第1個(gè)不匹配的字符。如果前向緩沖器不是空的，則把編碼位置和窗口向前移Length+1個(gè)字符，然后返回到步驟2。612023/2/6LZ77算法待編碼的數(shù)據(jù)流

位置12345678910字符A

A

B

C

BBABCC編碼過(guò)程

步驟位置匹配串字符輸出11--A

(0，0)A

22A

B

(1，1)B

34--C

(0，0)C

45B

B

(2，1)B

57ABC

C

(5，3)C

告訴譯碼器回退5個(gè)字符,然后拷貝3個(gè)字符“ABC”622023/2/6LZ77算法“步驟”欄表示編碼步驟?！拔恢谩睓诒硎揪幋a位置?！捌ヅ洹睓诒硎敬翱谥姓业降淖铋L(zhǎng)的匹配串。“字符”欄表示匹配之后在前向緩沖器中的第1個(gè)字符“輸出”欄以(Back_chars，Chars_length)Explicit_character格式輸出。其中(Back_chars，Chars_length)是指指向匹配串的指針，告訴譯碼器“在這個(gè)窗口中向后退Back_chars個(gè)字符然后拷貝Chars_length個(gè)字符到輸出”，Explicit_character是真實(shí)字符。例如，輸出“(5，2)C”告訴譯碼器回退5個(gè)字符，然后拷貝2個(gè)字符“AB”632023/2/6LZ77算法解壓算法——解碼當(dāng)碰到編碼字符串時(shí)，解壓算法使用<指針>，和<長(zhǎng)度>，字段將編碼替換成實(shí)際的正文字符串。642023/2/6LZ77算法練習(xí)給定一個(gè)報(bào)文:abcdbbccaaabaeaaabaee，請(qǐng)用LZ77算法對(duì)該報(bào)文序列進(jìn)行編碼！Output:(0,0,a)(0,0,b)(0,0,c)(0,0,d)(3,1,b)(4,1,c)(8,1,a)(10,2,a)(0,0,e)(6,6,e)abcdbbccaaabaeaaabaee652023/2/6LZSS算法LZ77冗余信息空指針和編碼器可能輸出額外的字符，這種字符可能包含在下一個(gè)匹配串中。LZSS算法以比較有效的方法解決這個(gè)問(wèn)題，它的思想是如果匹配串的長(zhǎng)度比指針本身的長(zhǎng)度長(zhǎng)就輸出指針，否則就輸出真實(shí)字符。指針長(zhǎng)度為2662023/2/6LZSS算法把編碼位置置于輸入數(shù)據(jù)流的開始位置。在前向緩沖存儲(chǔ)器中查找與窗口中最長(zhǎng)的匹配串

Pointer：=匹配串指針。Length：=匹配串長(zhǎng)度。判斷匹配串長(zhǎng)度是否大于等于最小匹配串長(zhǎng)度如果“是”：輸出指針，然后把編碼位置向前移動(dòng)Length個(gè)字符。如果“否”：輸出前向緩沖存儲(chǔ)器中的第1個(gè)字符，然后把編碼位置向前移動(dòng)一個(gè)字符。如前向緩沖存儲(chǔ)器不是空的，就返回到步驟2。

672023/2/6LZSS算法舉例待編碼的數(shù)據(jù)流

位置1234567891011字符A

A

B

B

CBBAABC編碼過(guò)程

步驟位置匹配串輸出11--A22A

A33--B

44B

B55--C66BB(3,2)78AAB(7,3)811CC682023/2/6LZSS解碼與LZ77一樣完全可逆692023/2/6LZSS算法在相同的計(jì)算機(jī)環(huán)境下，LZSS算法比LZ77可獲得比較高的壓縮比，而譯碼同樣簡(jiǎn)單。許多后來(lái)開發(fā)的文檔壓縮程序都使用了LZSS的思想。例如，PKZip,ARJ,LHArc和ZOO等等。LZSS同樣可以和熵編碼聯(lián)合使用例如ARJ就與霍夫曼編碼聯(lián)用，而PKZip則與Shannon-Fano聯(lián)用。702023/2/6第二類詞典編碼第二類算法的思想是從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語(yǔ)詞典”（dictionaryofthephrases）（可能是任意字符的組合）。編碼數(shù)據(jù)過(guò)程中，遇到已經(jīng)在詞典中出現(xiàn)的“短語(yǔ)”時(shí)，編碼器就輸出這個(gè)詞典中該短語(yǔ)的“索引號(hào)”，而不是短語(yǔ)本身，如圖。712023/2/6第二類詞典編碼722023/2/6第二類詞典編碼——LZW與LZ78LZ78是首個(gè)第二類詞典編碼，1984年提出的LZW壓縮編碼也屬于這類編碼LZW是對(duì)LZ78進(jìn)行了實(shí)用性修正后提出的一種邏輯簡(jiǎn)單、速度快、硬件實(shí)現(xiàn)廉價(jià)的壓縮算法，被GIF和PNG格式的圖像壓縮所采用，并被廣泛應(yīng)用于文件的壓縮打包（如ZIP和RAR）和磁盤壓縮。732023/2/6LZ78算法LZ78算法的有關(guān)術(shù)語(yǔ)和符號(hào)字符流(Charstream)：要被編碼的數(shù)據(jù)序列。前綴(Prefix)：在一個(gè)字符之前的字符序列。綴-符串(String)：前綴＋字符。碼字(Codeword)：碼字流中的基本數(shù)據(jù)單元，代表詞典中的一串字符。碼字流(Codestream)：碼字和字符組成的序列，是編碼器的輸出。詞典(Dictionary)：綴-符串表。按照詞典中的索引號(hào)對(duì)每條綴-符串(String)指定一個(gè)碼字(Codeword)。742023/2/6LZ78編碼算法在開始時(shí)，詞典和當(dāng)前前綴P都是空的。當(dāng)前字符C:=字符流中的下一個(gè)字符。判斷P+C是否在詞典中：如果“是”：用C擴(kuò)展P，讓P:=P+C；如果“否”：輸出與當(dāng)前前綴P相對(duì)應(yīng)的碼字和當(dāng)前字符C；把字符串P+C添加到詞典中。令P:=空值。判斷字符流中是否還有字符需要編碼如果“是”：返回到步驟2。如果“否”：若當(dāng)前前綴P不是空的，輸出相應(yīng)于當(dāng)前前綴P的碼字，然后結(jié)束編碼。752023/2/6LZ78編碼舉例位置123456789字符ABBCBCABA步驟位置詞典輸出11A(0,A)22B(0,B)33BC(2,C)45BCA(3,A)58BA(2,A)編碼字符串：

編碼過(guò)程：與LZ77相比，LZ78的最大優(yōu)點(diǎn)是在每個(gè)編碼步驟中減少了綴-符串(String)比較的數(shù)目，而壓縮率與LZ77類似。

762023/2/6LZ78解碼詞典序列即輸入的字符序列772023/2/6LZW算法在LZW算法中使用的術(shù)語(yǔ)與LZ78使用的相同，僅增加了一個(gè)術(shù)語(yǔ)—前綴根(Root)，它是由單個(gè)字符串組成的綴-符串(String)。在編碼原理上，LZW與LZ78有如下差別：LZW在開始時(shí)詞典必須包含可能在字符流出現(xiàn)中的所有單個(gè)字符，即前綴根(Root)。由于所有可能出現(xiàn)的單個(gè)字符都事先包含在詞典中，因此在詞典中搜索的第1個(gè)綴-符串有兩個(gè)字符。

782023/2/6LZW編碼算法的具體執(zhí)行步驟步驟1：開始的詞典包含所有可能根，而前綴P為空；步驟2：當(dāng)前字符(C)=字符流中的下一個(gè)字符；步驟3：判斷綴字符串P+C是否在詞典中

(1)如果“是”：P=P+C，即用C擴(kuò)展P；

(2)如果“否”

①把代表當(dāng)前前綴P的碼字輸出到碼字流;

②把綴字符串P+C添加到詞典;

③令P=C，即現(xiàn)在的P僅包含一個(gè)字符C;步驟4：判斷碼字流中是否還有碼字要譯

(1)如果“是”，就返回到步驟2；

(2)如果“否”

①把代表當(dāng)前前綴P的碼字輸出到碼字流;

②結(jié)束。792023/2/6LZW算法舉例被編碼的字符串LZW的編碼過(guò)程

步驟位置詞典輸出(1)A

(2)B

(3)C

11(4)AB

(1)22(5)BB

(2)

33(6)BA

(2)44(7)ABA

(4)

56(8)ABAC

(7)

69----(3)

位置字符1A2B3B4A5B6A7B8A9C802023/2/6LZW算法舉例被編碼的字符串LZW的譯碼過(guò)程

步驟代碼詞典輸出(1)A

(2)B

(3)C

1(1)

(4)AB

A2(2)(5)BB

B3(2)(6)BA

B4(4)(7)ABA

AB5(7)(8)ABAC

ABA6(3)----C位置字符1A2B3B4A5B6A7B8A9C812023/2/6LZW算法練習(xí)編碼字符：位置12345678910111213141516字符ababcbababaaaaaa編碼過(guò)程：步驟位置詞典輸出(1)A

(2)B

(3)C

1(4)2(5)…………822023/2/66.4常用的有損數(shù)據(jù)壓縮方法6.4.1預(yù)測(cè)編碼預(yù)測(cè)編碼是根據(jù)離散信號(hào)之間存在著一定關(guān)聯(lián)性的特點(diǎn)，利用前面一個(gè)或多個(gè)信號(hào)對(duì)下一個(gè)信號(hào)進(jìn)行預(yù)測(cè)，然后對(duì)實(shí)際值和預(yù)測(cè)值的差（預(yù)測(cè)誤差）進(jìn)行編碼。832023/2/66.4.1預(yù)測(cè)編碼1.脈沖編碼調(diào)制PCM842023/2/6脈沖編碼調(diào)制PCM輸入的模擬信號(hào)輸入信號(hào)在時(shí)間軸上的數(shù)字化均勻量化或非均勻量化量化的信號(hào)電平轉(zhuǎn)換成二進(jìn)制碼組離散的二進(jìn)制輸出序列采樣時(shí)鐘信號(hào)相乘852023/2/6脈沖編碼調(diào)制PCM均勻量化：采用相同的“等分尺”來(lái)度量采樣得到的幅度，也稱為線性量化，如圖所示。量化后的樣本值Y和原始值X的差E=Y-X稱為量化誤差或量化噪聲。862023/2/6均勻量化為了適應(yīng)幅度大的輸入信號(hào)，同時(shí)又要滿足精度要求，就需要增加樣本的位數(shù)。但是，對(duì)話音信號(hào)來(lái)說(shuō)，大信號(hào)出現(xiàn)的機(jī)會(huì)并不多，增加的樣本位數(shù)就沒(méi)有充分利用。為了克服這個(gè)不足，就出現(xiàn)了非均勻量化的方法，這種方法也叫做非線性量化。872023/2/6非均勻量化對(duì)輸入信號(hào)進(jìn)行量化時(shí)，大的輸入信號(hào)采用大的量化間隔，小的輸入信號(hào)采用小的量化間隔，如下圖所示。882023/2/66.4.1預(yù)測(cè)編碼2.增量調(diào)制DM增量調(diào)制也稱△調(diào)制(deltamodulation，DM)，是一種預(yù)測(cè)編碼技術(shù)，是PCM編碼的一種變形。PCM是對(duì)每個(gè)采樣信號(hào)的整個(gè)幅度進(jìn)行量化編碼，它具有對(duì)任意波形進(jìn)行編碼的能力；DM是對(duì)實(shí)際的采樣信號(hào)與預(yù)測(cè)的采樣信號(hào)之差的極性進(jìn)行編碼，將極性變成“0”和“1”這兩種可能的取值之一。如果實(shí)際的采樣信號(hào)與預(yù)測(cè)的采樣信號(hào)之差的極性為“正”，則用“1”表示；相反則用“0”表示，或者相反。由于DM編碼只須用1位進(jìn)行編碼，所以它是二進(jìn)制一位編碼，每個(gè)碼組不是表示信號(hào)的幅度，而是表示幅度的增量。892023/2/6DM波形編碼示意圖X[i]表示在i點(diǎn)的編碼輸出i表示采樣點(diǎn)的位置輸入信號(hào)的實(shí)際值輸入信號(hào)的預(yù)測(cè)值902023/2/6“斜率過(guò)載”與“粒狀噪聲”斜率過(guò)載——與量化階△相比，在開始階段當(dāng)實(shí)際波形幅度發(fā)生急劇變化時(shí)，DM不能充分跟蹤這種快速變化而產(chǎn)生的失真。粒狀噪聲——在輸入信號(hào)緩慢變化部分，即輸入信號(hào)與預(yù)測(cè)信號(hào)的差值接近零的區(qū)域，DM出現(xiàn)隨機(jī)交變的“0”和“