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