【文章內(nèi)容簡介】 壓縮稱為非對稱壓縮，如多媒體 CDROM的節(jié)目制作。壓縮的速度不僅與采用的壓縮方法有關(guān)，而且與快速算法的計算量有關(guān)，如果在算法上有較大的突破，無疑將對多媒體的開發(fā)與應(yīng)用產(chǎn)生很大的影響。 上一頁 下一頁 返回首頁 ? 信息熵編碼也稱為統(tǒng)計編碼，是利用信息源出現(xiàn)的概率來進行編碼，目前比較常見的信息熵編碼包括行程長度編碼、哈夫曼編碼、算術(shù)統(tǒng)計編碼等。 上一頁 下一頁 返回首頁 ? 是一個針對包含有順序排列的多次重復(fù)的數(shù)據(jù)的壓縮方案。其原理就是把一系列的重復(fù)值用一個單獨的值再加上一個計數(shù)值來取代，行程長度就是連續(xù)且重復(fù)的單元數(shù)目。如果想得到原始數(shù)據(jù)，只需展開這個編碼就可以了。 上一頁 下一頁 返回首頁 ? 例如，計算機制作圖像中，常常具有許多顏色相同的圖塊，而且在行上都具有相同的顏色，或者在一行上有許多連續(xù)的像素都具有相同的顏色值。這時，就不需要存儲每一個像素的顏色值，而僅存儲一個像素的顏色值以及具有相同顏色的像素數(shù)目就可以，或者存儲一個像素的顏色值，以及具有相同顏色值的行數(shù)，這種壓縮編碼稱為行程編碼。具有相同顏色的連續(xù)的像素數(shù)目稱為行程長度。 上一頁 下一頁 返回首頁 ? 如圖所示 ， 假定一幅灰度圖像 ， 第 n行的像素值為： 用 RLE編碼方法得到的代碼為： 3150841代碼斜黑體表示的數(shù)字是行程長度，黑體字后面的數(shù)字代表像素的顏色值。例如黑體字 50代表有連續(xù) 50個像素具有相同的顏色值，它的顏色值是 8。 上一頁 下一頁 返回首頁 ? 基本原理 依據(jù)信源字符出現(xiàn)的概率大小來構(gòu)造代碼，對出現(xiàn)概率較大的信源字符，給予較短碼長，而對于出現(xiàn)概率較小的信源字符，給予較長的碼長，最后使得編碼的平均碼字最短。 上一頁 下一頁 返回首頁 ? 具體的編碼步驟如下： ? （ 1） 將信源符號出現(xiàn)的概率按由大到小的順序排序 。 ? （ 2） 將兩處最小的概率進行組合相加 ， 形成一個新的概率 。 ? （ 3） 將新出現(xiàn)的概率與未編碼的字符一起重新排序 。 ? （ 4） 重復(fù)步驟 （ 2） 、 （ 3） ， 直到出現(xiàn)的概率和為 1。 ? （ 5）分配代碼。代碼分配從最后一步開始反向進行，對最后兩個概率一個賦予 0代碼，一個賦予 1代碼。如此反向進行到開始的概率排列。在此過程中，若概率不變則采用原代碼。 上一頁 下一頁 返回首頁 ? 例： 設(shè)輸入圖像的灰度級 {a1,a2,a3,a4,a5,a6}出現(xiàn)的概率分別是 、 、 、 、 、。試進行哈夫曼編碼，并計算編碼效率、壓縮比、冗余度。 a 1a 6a 5a 3a 4a 20 . 40 . 20 . 0 30 . 10 . 1 20 . 1 5110100010P 1P 21P 3P 4P 5最終編碼結(jié)果為： a1 =1, a2 =000 , a3 =011, a4 =001, a5 =0100, a6 =0101 上一頁 下一頁 返回首頁 a1 01 a2 00 a3 111 a4 110 a5 101 a6 1001 a7 1000 1 0 1 1 1 0 0 0 1 0 0 1 上一頁 下一頁 返回首頁 采用哈夫曼編碼時有兩個問題值得注意： （ 1）它必須精確地計算出原始文件中每個值的出現(xiàn)頻率，否則壓縮的效果就會大打折扣，甚至根本就達不到壓縮的效果。 （ 2）對于位的增刪比較敏感，這是由于哈夫曼編碼的所有位都是合在一起而不考慮字節(jié)分位的，因此增加一位或減少一位都會使譯碼變得結(jié)果面目全非。 上一頁 下一頁 返回首頁 是將被編碼的信息表示成實數(shù) 0和 1之間的一個間隔。信息越長編碼表示它的間隙就越小，表示這一間隙所需二進制位就越多，大概率符號出現(xiàn)的概率越大對應(yīng)于區(qū)間愈寬，可用長度較短的碼字表示；小概率符號出現(xiàn)概率越小區(qū)間愈窄，需要較長碼字表示。信息源中連續(xù)的符號根據(jù)某一模式生成概率的大小來減少間隔?？赡艹霈F(xiàn)的符號要比不太可能出現(xiàn)的符號減少范圍少，因此只增加了較少的比特位。 上一頁 下一頁 返回首頁 算術(shù)編碼對整條信息（無論信息有多么長），其輸出僅僅是一個數(shù)，而且是一個介于 0 和 1 之間的二進制小數(shù)。例如算術(shù)編碼對某條信息的輸出為 1010001111，那么它表示小數(shù) ，也即十進制數(shù) 。 上一頁 下一頁 返回首頁 例： 假設(shè)信源符號為 {00,01,10,11}，這些符號的概率分別為 { , , , }，根據(jù)這些概率可把間隔 [0, 1]分成4個子間隔： [0, ） , [, ） , [, ） , [, 1），其中 [x,y）表示半開放間隔，即包含 x不包含 y，如表所示。 符號 00 01 10 11 概率 初始編碼間隔 [0,) [,) [,) [,1) 上一頁 下一頁 返回首頁 編碼時，設(shè)置兩個專用寄存器（ C， A） 初始時：令 C 寄存器的值為子區(qū)域的起始位置 A 寄存器的值為子區(qū)域的寬度 (該寬度恰好是已輸入符號串的概率 ) 上一頁 下一頁 返回首頁 初始化時，令 C=0， A=1，當(dāng)新的符號到來時， C中的值變?yōu)?C+A L， A中值變?yōu)锳 (H L) L和 H為分別為編碼字符的初始編碼區(qū)間的低端值和高端值。 上一頁 下一頁 返回首頁 如果二進制輸入的為 10 00 11 00 10 11 01則 （ 1）第一個符號 10，其編碼范圍 [,)。因此 C=0+1 =, A=1 = （ 2）第二個符 00，其編碼范圍 [0,)。因此 C=+ 0=, A= = ? 初始化時，令 C=0， A=1，當(dāng)新的符號到來時， C中的值變?yōu)?C+A L， A中值變?yōu)?A (H L) ? L和 H為分別為編碼字符的初始編碼區(qū)間的低端值和高端值。 上一頁 下一頁 返回首頁 如果二進制輸入的為 10 00 11 00 10 11 01則 （ 3）第三個符號 11，其編碼范圍 [,1)。因此 C=+ =, A= = （ 4）第二個符 00，其編碼范圍 [0,)。因此 C=+ 0=, A= = ? 初始化時，令 C=0， A=1，當(dāng)新的符號到來時， C中的值變?yōu)?C+A L， A中值變?yōu)?A (H L) ? L和 H為分別為編碼字符的初始編碼區(qū)間的低端值和高端值。 上一頁 下一頁 返回首頁 算術(shù)編碼的特點： (1) 不需要碼表； (2) 當(dāng)信源概率比較接近時，建議使用算術(shù)編碼。 (3) JPEG成員對多幅圖進行算術(shù)編碼效率可以提高 5%。 JPEG擴展系統(tǒng)用算術(shù)編碼代替 Huffman。 上一頁 下一頁 返回首頁 ，其根據(jù)是數(shù)據(jù)本身包含有重復(fù)代碼序列這個特性。詞典編碼的種類較多，歸納起來有兩類。 第一類詞典編碼的基本思想是查找正在壓縮的字符序列是否在前面輸入的數(shù)據(jù)中出現(xiàn)過，如果是，則用指向早期出現(xiàn)過的字符串的 “ 指針 ” 替代重復(fù)的字符串。這種編碼思想如圖。 上一頁 下一頁 返回首頁 這里所指的 “ 詞典 ” 是指用以前處理過的數(shù)據(jù)來表示編碼過程中遇到的重復(fù)部分。這類編碼中的所有算法都是以 Abraham Lempel 和 Jakob Ziv在 1977年開發(fā)和發(fā)表的稱為 LZ77算法為基礎(chǔ)的， 1982年由Storer和 Szymanski改進的稱為 LZSS算法。 上一頁 下一頁 返回首頁 第二類算法的思想是從輸入的數(shù)據(jù)中創(chuàng)建一個 “ 短語詞典 ” （ dictionary of the phrases）（這種短語可以是任意字符的組合）。編碼數(shù)據(jù)過程中，遇到已經(jīng)在詞典中出現(xiàn)的 “ 短語 ” 時，編碼器就輸出這個詞典中該短語的“ 索引號 ” ，而不是短語本身，如圖。 上一頁 下一頁 返回首頁 1978年首次發(fā)表了介紹這種編碼方法的文章。在他們研究的基礎(chǔ)上， Terry 1984年發(fā)表了改進這種編碼算法的文章，因此把這種編碼方法稱為 LZW（ LempelZiv Walch）壓縮編碼。這種算法首先在高速硬盤控制器上得到了應(yīng)用。在眾多的壓縮技術(shù)中， LZW算法時一種通用的、性能優(yōu)良并得到廣泛應(yīng)用的壓縮算法。 LZW是一種完全可逆的算法，與其他算法比較，往往具有更高的壓縮效率，因此被廣泛應(yīng)用于多種流行的壓縮軟件中。 上一頁 下一頁 返回首頁 LZW算法的壓縮過程 上一頁 下一頁 返回首頁 LZW編碼 ? LZW是一種比較復(fù)雜的壓縮算法，壓縮效率較高 – 每一個第一次出現(xiàn)的字符串用一個數(shù)值來編碼，再將這個數(shù)值還原為字符串。 – 例如：用數(shù)值 0x100代替字符串“ abccddeee”，每當(dāng)出現(xiàn)該字符串時，都用 0x100代替，從而起到了壓縮作用。 – 數(shù)值與字符串的對應(yīng)關(guān)系在壓縮過程中動態(tài)生成并隱含在壓縮數(shù)據(jù)中，在解壓縮時逐步得到恢復(fù)。 – LZW是無損的。 GIF和 Tiff圖像都采用了這種壓縮算法。 ? 要注意的是， LZW算法由 Unisys公司在美國申請了專利，要使用它首先要獲得該公司的認(rèn)可 上一頁 下一頁 返回首頁 LZW算法 在 LZW算法中使用的術(shù)語與 LZ78使用的相同，僅增加了一個術(shù)語 —前綴根 (Root)，它是由單個字符串組成的綴 符串 (String)。在編碼原理上， LZW與 LZ78相比有如下差別： ① LZW只輸出代表詞典中的綴 符串 (String)的碼字 (code word)。這就意味在開始時詞典不能是空的，它必須包含可能在字符流出現(xiàn)中的所有單個字符，即前綴根 (Root)。 ② 由于所有可能出現(xiàn)的單個字符都事先包含在詞典中，每個編碼步驟開始時都使用一字符前綴 (onecharacter prefix)，因此在詞典中搜索的第 1個綴 符串有兩個字符。 上一頁 下一頁 返回首頁 現(xiàn)將 LZW編碼算法和譯碼算法介紹如下。 1. 編碼算法 LZW編碼是圍繞稱為詞典的轉(zhuǎn)換表來完成的。這張轉(zhuǎn)換表用來存放稱為前綴 (Prefix)的字符序列，并且為每個表項分配一個碼字 (Code word)，或者叫做序號，如表所示。 上一頁 下一頁 返回首頁 這張轉(zhuǎn)換表實際上是把 8位 ASCII字符集進行擴充，增加的符號用來表示在文本或圖像中出現(xiàn)的可變長度 ASCII字符串。擴充后的代碼可用 9位、 10位、 11位、 12位甚至更多的位來表示。Welch的論文中用了 12位， 12位可以有 4096個不同的 12位代碼，這就是說，轉(zhuǎn)換表有 4096個表項，其中 256個表項用來存放已定義的字符，剩下 3840個表項用來存放前綴 (Prefix)。 表詞典 上一頁 下一頁 返回首頁 表 詞典 上一頁 下一頁 返回首頁 LZW編碼器 (軟件編碼器或硬件編碼器 )就是通過管理這個詞典完成輸入與輸出之間的轉(zhuǎn)換。 LZW編碼器的輸入是字符流(Charstream)，字符流可以是用 8位 ASCII字符組成的字符串，而輸出是用 n位 (例如12位 )表示的碼字流 (Codestream)，碼字代表單個字符或多個字符組成的字符串。 上一頁 下一頁 返回首頁 LZW編碼器使用了一種很實用的分析 (parsing)算法，稱為貪婪分析算法 (greedy parsing algorithm)。在貪婪分析算法中，每一次分析都要串行地檢查來自字符流 (Charstream)的字符串，從中分解出已經(jīng)識別的最長的字符串，也就是已經(jīng)在詞典中出現(xiàn)的最長的前綴 (Prefix)。用已知的前綴 (Prefix)加上下一個輸入字符 C也就是當(dāng)前字符 (Current character) 上一頁 下一頁 返回首頁