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

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

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

a5=0001,a6=00001010010362023/2/6Huffman編碼練習一答案據(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ù)哈夫曼編碼結果，平均碼字長度：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編碼練習二答案382023/2/66.3.1Huffman編碼Huffman編碼注意事項哈夫曼編碼沒有錯誤保護功能，在譯碼時，如果碼串中沒有錯誤，那么就能一個接一個的正確譯出代碼。但如果碼串中有錯誤，哪怕僅是1位出現(xiàn)錯誤，不但這個碼本身譯錯，后面的譯碼可能全錯，這種現(xiàn)象稱為錯誤傳播（ErrorPropagation）。哈夫曼編碼是可變長度碼，很難隨意查找或調用壓縮文件中間的內容，然后再譯碼，這就需要在存儲代碼之前加以考慮。392023/2/66.3.2算術編碼算術編碼（arithmeticcodingAC）是利用0和1之間的間隔來表示信源編碼的一種方法，其編碼值是間隔的上、下限包含的相同二進制。編碼過程中的間隔決定了符號壓縮后的輸出。算術編碼用到兩個基本的參數(shù)符號的概率和它的編碼間隔。信源符號的概率決定壓縮編碼的效率，也決定編碼過程中信源符號的間隔，而這些間隔包含在0到1之間。402023/2/66.3.2算術編碼編碼過程:設信源符號為{A,B,C,D}，其概率分別為{0.1,0.4,0.2,0.3}，按概率可把間隔[0,1]分成4個子間隔：[0,0.1),[0.1,0.5),[0.5,0.7),[0.7,1]，其中[x,y)表示半開放間隔，即包含x不包含y，如下表所示。符號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算術編碼如果消息序列的輸入為：CADACDB，其編碼過程如下：首先輸入的符號是C，找到它的編碼范圍是[0.5,0.7)；由于消息中第2個符號A的編碼范圍是[0,0.1)，因此它的間隔就取[0.5,0.7)的第一個1/10作為新間隔[0.5,0.52)；編碼第3個符號D時取新間隔為[0.514,0.52)；編碼第4個符號A時，取新間隔為[0.514,0.5146)

，…。422023/2/66.3.2算術編碼符號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ù)，整個編碼過程如下圖所示。最后在[0.5143876,0.514402)中選擇一個數(shù)作為編碼輸出值：0.51439。解碼時，解碼器由編碼輸出值：0.51439，可馬上解得一個字符為C，然后依次得到唯一解A,D,A,C,D,B。442023/2/66.3.2算術編碼步驟譯碼間隔譯碼10.51439在間隔[0.5,0.7)1020.51439在間隔[0.5,0.7)的第1個1/100030.51439在間隔[0.5,0.52)的第7個1/101140.51439在間隔[0.514,0.52)的第1個1/100050.51439在間隔[0.514,0.5146)的第5個1/101060.51439在間隔[0.5143,0.51442)的第7個1/101170.51439在間隔[0.51439,0.5143948)的第1個1/10018譯碼消息：10001100101101

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

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

位置12345678910字符A

A

B

C

BBABCC編碼過程

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

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

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

位置1234567891011字符A

A

B

B

CBBAABC編碼過程

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

A33--B

44B

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

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

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

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

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

(2)如果“否”

①把代表當前前綴P的碼字輸出到碼字流;

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

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

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

(2)如果“否”

①把代表當前前綴P的碼字輸出到碼字流;

②結束。792023/2/6LZW算法舉例被編碼的字符串LZW的編碼過程

步驟位置詞典輸出(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的譯碼過程

步驟代碼詞典輸出(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算法練習編碼字符：位置12345678910111213141516字符ababcbababaaaaaa編碼過程：步驟位置詞典輸出(1)A

(2)B

(3)C

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