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

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

2、頻信號(hào)需要的存儲(chǔ)空間數(shù)據(jù)壓縮的必要性(續(xù))第7頁，共46頁。時(shí)間域壓縮迅速傳輸媒體信源頻率域壓縮并行開通更多業(yè)務(wù)空間域壓縮降低存儲(chǔ)費(fèi)用能量域壓縮降低發(fā)射功率數(shù)據(jù)壓縮的好處第8頁，共46頁。壓縮比要大恢復(fù)后的失真小壓縮算法要簡(jiǎn)單、速度快壓縮能否用硬件實(shí)現(xiàn)數(shù)據(jù)壓縮技術(shù)實(shí)現(xiàn)的衡量標(biāo)準(zhǔn)第9頁，共46頁。根據(jù)還原后數(shù)據(jù)的有無失真分為： 無損壓縮:是指使用壓縮后的數(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á)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、的匹配字符串，如果找到，則進(jìn)行步驟 2，否則進(jìn)行步驟 3。2、輸出三元符號(hào)組 ( off, len, c )。其中 off 為窗口中匹配字符串相對(duì)窗口邊界的偏移，len 為可匹配的長(zhǎng)度，c 為下一個(gè)字符，即不匹配的第一個(gè)字符。然后將窗口向后滑動(dòng) len + 1 個(gè)字符，繼續(xù)步驟 1。3、輸出三元符號(hào)組 ( 0, 0, c )。其中 c 為下一個(gè)字符。然后將窗口向后滑動(dòng) 1 個(gè)字符，繼續(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)建一個(gè)“短語詞典”，這種短語可以是任意字符的組合。在接下來的數(shù)據(jù)編碼過程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的“短語”時(shí)，編碼器就輸出“短語”在這個(gè)詞典中 “索引號(hào)”，而不是短語本身，從而達(dá)到