多媒體技術(shù)基礎(chǔ)04課件

1、第四講無損數(shù)據(jù)壓縮第1頁，共46頁。主要內(nèi)容數(shù)據(jù)壓縮概述香農(nóng)范諾與霍夫曼編碼算術(shù)編碼行程編碼詞典編碼圖形圖像處理實驗室第2頁，共46頁。數(shù)據(jù)壓縮的定義數(shù)據(jù)壓縮的必要性數(shù)據(jù)壓縮的好處數(shù)據(jù)壓縮的衡量標準數(shù)據(jù)壓縮的分類數(shù)據(jù)壓縮概述第3頁，共46頁。數(shù)據(jù)壓縮就是在一定的精度損失條件下，以最少的數(shù)碼表示信源所發(fā)出的信號信源編碼信道編碼信道信道譯碼信源譯碼信源信宿數(shù)據(jù)壓縮的定義第4頁，共46頁。多媒體信源引起了“數(shù)據(jù)爆炸”,如果不進行數(shù)據(jù)壓縮傳輸和存儲都難以實用化。如下兩表所示:多媒體數(shù)據(jù)數(shù)據(jù)壓縮的必要性第5頁，共46頁。1分鐘數(shù)字音頻信號需要的存儲空間數(shù)據(jù)壓縮的必要性(續(xù))第6頁，共46頁。1分鐘數(shù)字視

2、頻信號需要的存儲空間數(shù)據(jù)壓縮的必要性(續(xù))第7頁，共46頁。時間域壓縮迅速傳輸媒體信源頻率域壓縮并行開通更多業(yè)務(wù)空間域壓縮降低存儲費用能量域壓縮降低發(fā)射功率數(shù)據(jù)壓縮的好處第8頁，共46頁。壓縮比要大恢復后的失真小壓縮算法要簡單、速度快壓縮能否用硬件實現(xiàn)數(shù)據(jù)壓縮技術(shù)實現(xiàn)的衡量標準第9頁，共46頁。根據(jù)還原后數(shù)據(jù)的有無失真分為： 無損壓縮:是指使用壓縮后的數(shù)據(jù)進行重構(gòu)(或者叫做還原，解壓縮)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)完全相同；無損壓縮用于要求重構(gòu)的信號與原始信號完全一致的場合，如文檔、軟件安裝包等。 有損壓縮:是指使用壓縮后的數(shù)據(jù)進行重構(gòu)，重構(gòu)后的數(shù)據(jù)與原來的數(shù)據(jù)有所不同，但不影響人對原始資料表達

3、的信息造成誤解。有損壓縮適用于重構(gòu)信號不一定非要和原始信號完全相同的場合，如聲音、圖像、視頻數(shù)據(jù)等。數(shù)據(jù)壓縮的分類第10頁，共46頁。根據(jù)編碼特點分為以下五種類型:脈沖編碼調(diào)制：如PCM編碼。預測編碼：如DM編碼、ADPCM編碼等。統(tǒng)計編碼(無損)：如Huffman編碼、算術(shù)編碼、RLE編碼、詞典編碼。變換編碼：如DCT變換、K-L變換、Wavelet變換?；旌暇幋a：如Jpeg編碼、Mpeg編碼。數(shù)據(jù)壓縮的分類(續(xù))第11頁，共46頁。熵的概念信源的熵香農(nóng)-范諾編碼霍夫曼編碼香農(nóng)范諾與霍夫曼編碼第12頁，共46頁。熵的概念在符號出現(xiàn) (事件發(fā)生)之前，熵(Entropy)表示符號集(離散信源)

4、中的符號出現(xiàn)的不確定性；在符號出現(xiàn)之后，熵代表接收這個符號所獲得的信息量或者表示這個符號所需的位數(shù)。熵是信息量的度量方法，它表示某一事件出現(xiàn)的消息越多，事件發(fā)生的可能性就越小，數(shù)學上就是概率越小。 第13頁，共46頁。熵的概念(續(xù))為了完全確定事件x(使后驗概率為1)所必須提供的信息量稱為x事件的非平均自信息量I(x)，非平均自信息量是隨機事件的一個固有特性，它表明了事件的先驗不確定性大小。某事件x的發(fā)生概率為p(x)，則其非平均自信息量I(x)為：例一第14頁，共46頁。信源被抽象為一個隨機變量序列（隨機過程）。如果信源輸出的隨機變量取值于某一連續(xù)區(qū)間，就叫做連續(xù)信源。比如語音信號X(t)。

5、如果信源輸出的隨機變量取值于某一離散符號集合，就叫做離散信源。比如數(shù)字平面圖像X(x，y)和電報等。信源的熵第15頁，共46頁。離散信源(隨機事件集合)中每個事件的非平均自信息量I(x)是定義在這個樣本空間上的一個隨機變量，所以我們要研究它們的統(tǒng)計特性。其數(shù)學期望為：信源的熵(續(xù))稱H(X)為一階信息熵或者簡稱為信源的熵，H(X)表明了集合中所有隨機事件的平均不確定性，或者說平均信息量。根據(jù)直覺，信源編碼的數(shù)據(jù)輸出速率(平均碼長)與信源熵之間應(yīng)該有某種對應(yīng)關(guān)系。第16頁，共46頁。熵的大小與信源的概率分布模型有著密切的關(guān)系。最大離散熵定理：當與信源對應(yīng)的符號集中的各個符號為等概率分布時，信源的

6、熵具有極大值log2m。m為符號集中符號的個數(shù)。信源的熵(續(xù))第17頁，共46頁。對于同一個信源其總的信息量是不變的，如果能夠通過某種變換(編碼)，使信源盡量等概率分布，則每個輸出符號所獨立攜帶的信息量增大，那么傳送相同信息量所需要的序列長度就越短。離散信源的冗余度隱含在信源符號的非等概率分布之中。只要H(x)小于log2m，就存在數(shù)據(jù)壓縮的可能。信源的熵(續(xù))第18頁，共46頁。如果采用二進制編碼方式，設(shè)符號j的編碼長度為Lj，則信源符號表的平均碼長為： 在Lj log2pj時，平均碼長取得極小值H(X)根據(jù)前面對二進制信源的分析，有：信源的熵(續(xù))例二第19頁，共46頁。信源的熵即為離散信

7、源的壓縮極限。(理論極限)只要信源不是等概率分布，就存在著數(shù)據(jù)壓縮的可能性。數(shù)據(jù)壓縮的基本途徑：使符號的編碼長度盡量等于符號的信息量。典型的熵編碼算法有香農(nóng)-范諾編碼與霍夫曼編碼。信源的熵(續(xù))第20頁，共46頁。香農(nóng)范諾編碼香農(nóng)范諾編碼采用從上到下的方法進行編碼，具體步驟為：首先將編碼字符集中的字符按照出現(xiàn)頻度和概率進行排序。用遞歸的方法將其分成兩部分，使兩個部分的概率和接近于相等。直至不可再分，即每一個葉子對應(yīng)一個字符。對每一個葉子結(jié)點進行編碼。第21頁，共46頁。符號ABCDE次數(shù)157765A BC D EABCD EDE01010011香農(nóng)范諾編碼(續(xù))第22頁，共46頁。香農(nóng)范諾編

8、碼(續(xù))符號出現(xiàn)次數(shù)編碼A1500B701C710D6110E5111總位數(shù)=(15+7+7+)X2+(6+5)X3=91壓縮比：120:91第23頁，共46頁。霍夫曼編碼霍夫曼編碼與香農(nóng)-范諾編碼正好相反，它采用自下向上的方式，其核心思想就是構(gòu)建一棵霍夫曼樹，然后對葉子結(jié)點編碼，具體步驟：初始化，根據(jù)概率對符號進行排序。合并概率最小的兩個符號形成新的中間結(jié)點。重復步驟2，直至形成一個Huffman樹。對Huffman樹葉子結(jié)點從根結(jié)點起進行編碼。第24頁，共46頁。霍夫曼編碼(續(xù))符號ABCDE次數(shù)157765B C D EABCD EDE01010011B C第25頁，共46頁?；舴蚵幋a

9、(續(xù))符號出現(xiàn)次數(shù)編碼A150B7100C7101D6110E5111總位數(shù)=15X1+(7+7+6+5)X3=90壓縮比：120:90=4:3第26頁，共46頁?；舴蚵幋a(續(xù))霍夫曼編碼的特點：霍夫曼碼沒有錯誤保護功能，且錯誤發(fā)生后會出現(xiàn)錯誤傳播，計算機無法更正這種錯誤，也不知錯誤發(fā)生在何處。霍夫曼碼是可變長度碼，無法從壓縮后的數(shù)據(jù)中提取部分數(shù)據(jù)?；舴蚵幋a又稱為前輟碼，即每個符號的編碼不能夠是其它符號編碼的前輟。 第27頁，共46頁。熵編碼算法的核心思想香農(nóng)范諾編碼、霍夫曼編碼和后面講到的算術(shù)編碼，它們共同的宗旨在于找到一種編碼使得平均碼長到達信源熵極限，基本思想就是對信源符號中出現(xiàn)概率

10、較大的符號用較少的碼長去表示，而對出現(xiàn)概率較小的符號用較長的碼長去表示，以使總的位數(shù)達到最少。第28頁，共46頁。算術(shù)編碼基本思想：算術(shù)編碼不是將單個信源符號映射成一個編碼，而是把真?zhèn)€信源表示為0到1之間的一個實數(shù)區(qū)間，其長度等于該序列的概率，再在該區(qū)間內(nèi)選擇一個代表性的小數(shù)，轉(zhuǎn)化為二進制作為實際的編碼輸出。信源中的每個元素都要用來縮短這個區(qū)間。消息序列中元素越多，所得到的區(qū)間就越小，當區(qū)間變小時，就需要更多的位來表示這個區(qū)間。算術(shù)編碼用到兩個基本的參數(shù)：符號的概率和它的編碼間隔。 第29頁，共46頁。算術(shù)編碼(續(xù))例 假設(shè)信源符號為00, 01, 10, 11，這些符號的概率分別為 0.1,

11、 0.4, 0.2, 0.3 ，根據(jù)這些概率可把間隔0, 1)分成4個子間隔：0, 0.1), 0.1, 0.5), 0.5, 0.7), 0.7, 1)，如下表所示。 符號00011011概率0.10.40.20.3初始區(qū)間0, 0.1)0.1, 0.5)0.5, 0.7)0.7, 1)如果二進制消息序列的輸入為：10 00 11 00 10 11 01。則編碼過程如下所示 。第30頁，共46頁。步驟 輸入符號編碼間隔 編碼判決1100.5, 0.7)符號的間隔范圍0.5, 0.7) 2000.5, 0.52)0.5, 0.7)間隔的第一個1/103110.514, 0.52)0.5, 0.

12、52)間隔的最后一個1/104000.514, 0.5146)0.514, 0.52)間隔的第一個1/105100.5143, 0.51442)0.514, 0.5146)間隔的第五個1/10開始，二個1/106110.514384, 0.51442)0.5143, 0.51442)間隔的最后3個1/107010.5143836, 0.514402)0.514384, 0.51442)間隔的4個1/10，從第1個1/10開始8從0.5143876, 0.514402中選擇一個數(shù)作為輸出：0.5143876算術(shù)編碼(續(xù))編碼過程表輸入為10 00 11 00 10 11 01,輸出為0.5143

13、876 。第31頁，共46頁。算術(shù)編碼(續(xù))編碼過程圖示第32頁，共46頁。算術(shù)編碼(續(xù))步驟間隔符號譯碼判決10.5, 0.7)100.51439在間隔 0.5, 0.7)20.5, 0.52)000.51439在間隔 0.5, 0.7)的第1個1/1030.514, 0.52)110.51439在間隔0.5, 0.52)的第7個1/1040.514, 0.5146)000.51439在間隔0.514, 0.52)的第1個1/1050.5143, 0.51442)100.51439在間隔0.514, 0.5146)的第5個1/1060.514384, 0.51442)110.51439在間隔

14、0.5143, 0.51442)的第7個1/1070.5143876, 0.514402)010.51439在間隔0.51439, 0.5143948)的第1個1/108譯碼的消息：10 00 11 00 10 11 01譯碼過程表輸入為0.5143876,輸出為10 00 11 00 10 11 01。第33頁，共46頁。算術(shù)編碼(續(xù))在算術(shù)編碼中需要注意的幾個問題：由于實際的計算機的精度不可能無限長，運算中出現(xiàn)溢出是一個明顯的問題，但多數(shù)機器都有16位、32位或者64位的精度，因此這個問題可使用比例縮放方法解決。 算術(shù)編碼器對整個消息只產(chǎn)生一個碼字，這個碼字是在間隔0, 1)中的一個實數(shù)，

15、因此譯碼器在接受到表示這個實數(shù)的所有位之前不能進行譯碼。 算術(shù)編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導致整個消息譯錯。算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。第34頁，共46頁。行程編碼(RLE) 行程編碼（Run-Length Encoding）：它通過將信源中相同符號序列轉(zhuǎn)換成一個計數(shù)字段再加上一個重復字符標志實現(xiàn)壓縮。 例如:RTTTTTTTTABBBBC被轉(zhuǎn)換為：R#8TA#4BC，其中“”作為轉(zhuǎn)義字符，表明其后所跟的字符表示長度。 行程編碼多用于黑白二值圖像的壓縮中。 例如:00000000111111111111000001111111被轉(zhuǎn)化為一系列黑串和白串長度的編

16、碼：81257。第35頁，共46頁。詞典編碼詞典編碼主要利用數(shù)據(jù)本身包含許多重復的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我們?nèi)绻靡恍┖唵蔚拇柎孢@些字符串，就可以實現(xiàn)壓縮，實際上就是利用了信源符號之間的相關(guān)性。字符串與代號的對應(yīng)表就是詞典。 實用的詞典編碼算法的核心就是如何動態(tài)地形成詞典，以及如何選擇輸出格式以減小冗余。第36頁，共46頁。第一類詞典編碼第一類詞典法的想法是企圖查找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，然后用已經(jīng)出現(xiàn)過的字符串替代重復的部分，它的輸出僅僅是指向早期出現(xiàn)過的字符串的“指針”。第一類詞典編碼算法主要有LZ77算法和LZSS算法，這

17、里只介紹LZ77算法。第37頁，共46頁。LZ77算法LZ77算法在某種意義上又可以稱為“滑動窗口壓縮”，該算法將一個虛擬的，可以跟隨壓縮進程滑動的窗口作為詞典，要壓縮的字符串如果在該窗口中出現(xiàn)，則輸出其出現(xiàn)位置和長度。使用固定大小窗口進行詞語匹配，而不是在所有已經(jīng)編碼的信息中匹配，是因為匹配算法的時間消耗往往很多，必須限制詞典的大小才能保證算法的效率；隨著壓縮的進程滑動詞典窗口，使其中總包含最近編碼過的信息，是因為對大多數(shù)信息而言，要編碼的字符串往往在最近的上下文中更容易找到匹配串。第38頁，共46頁。LZ77算法編碼過程:1、從當前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動窗口中找出最長

18、的匹配字符串，如果找到，則進行步驟 2，否則進行步驟 3。2、輸出三元符號組 ( off, len, c )。其中 off 為窗口中匹配字符串相對窗口邊界的偏移，len 為可匹配的長度，c 為下一個字符，即不匹配的第一個字符。然后將窗口向后滑動 len + 1 個字符，繼續(xù)步驟 1。3、輸出三元符號組 ( 0, 0, c )。其中 c 為下一個字符。然后將窗口向后滑動 1 個字符，繼續(xù)步驟 1。LZ77算法(續(xù))第39頁，共46頁。LZ77算法(續(xù))LZ77算法編碼示意圖第40頁，共46頁。AABCBBABCA步驟位置匹配串輸出110, 0, A22A1, 1, B340, 0, C45B2, 1, B57ABC5, 3, ALZ77算法(續(xù))LZ77算法編碼舉例第41頁，共46頁。第二類詞典編碼第二類算法的想法是企圖從輸入的已編碼的數(shù)據(jù)中創(chuàng)建一個“短語詞典”，這種短語可以是任意字符的組合。在接下來的數(shù)據(jù)編碼過程中當遇到已經(jīng)在詞典中出現(xiàn)的“短語”時，編碼器就輸出“短語”在這個詞典中 “索引號”，而不是短語本身，從而達到