第7章-圖像編碼-2

1、7.4 行行 程程 編編 碼碼7.4.1 行程編碼基本方法行程編碼基本方法 行程編碼又稱行程長(zhǎng)度編碼（Run Length Encoding， RLE）， 是一種熵編碼，其編碼原理相當(dāng)簡(jiǎn)單，即將具有相同值的連續(xù)串用其串長(zhǎng)和一個(gè)代表值來(lái)代替， 該連續(xù)串就稱為行程，串長(zhǎng)稱為行程長(zhǎng)度。例如，有一字符串“aabbbcddddd”， 則經(jīng)行程長(zhǎng)度編碼后， 該字符串可以只用“2a3b1c5d”來(lái)表示。 行程編碼分為定長(zhǎng)和不定長(zhǎng)編碼兩種。定長(zhǎng)編碼是指編碼的行程長(zhǎng)度所用的二進(jìn)制位數(shù)固定，而變長(zhǎng)行程編碼是指對(duì)不同范圍的行程長(zhǎng)度使用不同位數(shù)的二進(jìn)制位數(shù)進(jìn)行編碼。使用變長(zhǎng)行程編碼需要增加標(biāo)志位來(lái)表明所使用的二進(jìn)制位

2、數(shù)。 行程編碼比較適合于二值圖像的編碼，一般用于量化后出現(xiàn)大量零系數(shù)連續(xù)的場(chǎng)合，用行程來(lái)表示連零碼。如果圖像是由很多塊顏色或灰度相同的大面積區(qū)域組成的，那么采用行程編碼可以達(dá)到很高的壓縮比。如果圖像中的數(shù)據(jù)非常分散，則行程編碼不但不能壓縮數(shù)據(jù)，反而會(huì)增加圖像文件的大小。為了達(dá)到較好的壓縮效果，一般不單獨(dú)采用行程編碼， 而是和其他編碼方法結(jié)合使用。例如， 在JPEG中， 就綜合使用了行程編碼、DCT、量化編碼以及哈夫曼編碼， 先對(duì)圖像作分塊處理， 再對(duì)這些分塊圖像進(jìn)行離散余弦變換（DCT）， 對(duì)變換后的頻域數(shù)據(jù)進(jìn)行量化并作Z字形掃描，接著對(duì)掃描結(jié)果作行程編碼， 對(duì)行程編碼后的結(jié)果再作哈夫曼編碼。

3、 1.一維行程編碼一維行程編碼編碼思想：編碼思想： 將一行中顏色值相同的相鄰象素（行將一行中顏色值相同的相鄰象素（行程）用一個(gè)計(jì)數(shù)值（行程的長(zhǎng)度）和該顏程）用一個(gè)計(jì)數(shù)值（行程的長(zhǎng)度）和該顏色值（行程的灰度）來(lái)代替，從而去除像色值（行程的灰度）來(lái)代替，從而去除像素冗余。素冗余。 設(shè)沿某一掃描行的像素為設(shè)沿某一掃描行的像素為x1,x2,xN對(duì)應(yīng)的對(duì)應(yīng)的灰度值可能為灰度值可能為g1,g2,g3,g4. 把像素映射成序列對(duì)：把像素映射成序列對(duì)： (g1,l l1)，(g2, l l2)，(g3, l l3)，(g4, l l4) 直接對(duì)直接對(duì)(gi, li)編碼，可大大壓縮比特率編碼，可大大壓縮比特率

4、0 0 5 5 1 10 0 1 15 5 2 20 0 2 25 51 10 09 98 87 76 65 54 43 32 21 1l l1 1l l2 2l l3 3l l4 4g g1 1g g2 2g g3 3g g4 4像像素素li:表示第表示第i次運(yùn)行的行程，即連續(xù)取值為次運(yùn)行的行程，即連續(xù)取值為gi灰度值的像素灰度值的像素的個(gè)數(shù)的個(gè)數(shù) 8級(jí)灰度，級(jí)灰度，24個(gè)像素個(gè)像素對(duì)對(duì)xi編碼，總的比特?cái)?shù)，至少編碼，總的比特?cái)?shù)，至少24 3=72bit如對(duì)如對(duì)(gi,li)編碼，灰度值用編碼，灰度值用3bit，行程長(zhǎng)度用，行程長(zhǎng)度用4bit每對(duì)參數(shù)用每對(duì)參數(shù)用7bit，總比特?cái)?shù)只需，總比特

5、數(shù)只需28bit就夠就夠i gi li13 62510342486 例：映射對(duì)：例：映射對(duì)：行程編碼（RLE）n對(duì)于有大面積色塊的圖像，壓縮效果很好n對(duì)于紛雜的圖像，壓縮效果不好，最壞情況下（圖像中每?jī)蓚€(gè)相鄰點(diǎn)的顏色都不同 ），會(huì)使數(shù)據(jù)量加倍，所以現(xiàn)在單純采用行程編碼的壓縮算法用得并不多，PCX文件算是其中之一二維行程編碼n二維行程編碼要解決的核心問(wèn)題是：將二維排列的像素，采用某種方式轉(zhuǎn)化成一維排列的方式。之后按照一維行程編碼方式進(jìn)行編碼n兩種典型的二維行程編碼的排列方式例1：n數(shù)據(jù)量：64*8=512(bit)13013013012913413312913013013013012913413

6、3130130130130130129132132130130129130130129130130129129127128127129131 129131 130127128127128127128132132125126129129127129133132127125128128126130131131f二維行程編碼如果按照方式(a)掃描的順序排列的話，數(shù)據(jù)分布為：130，130，130，130，130，130，130，130，130；129，129，129，129，130，130，129；127，128，127，129，131，130，132，134，134；133，133，132，130

7、，129，128，127，128，127，128，127，125，126，129，129；127，129，133，132，131，129，130，130；129，130，130，130，129，130，132，132；131，131，130，126，128，128，127，127行程編碼為:數(shù)據(jù)量為:43*（3+8）=473(bit) (94.22%)（7，130），（），（2，130），（），（4，129），（），（2，130），（），（1，129）；（）；（1，127），），（1，128），（），（1，127），（），（1，129），（），（1，131），（），（1，130），（），（1，

8、132），），（2，134），（），（2，133），（），（1，132），（），（1，130），（），（1，129），（），（1，128），），（1，127），（），（1，128），（），（1，127），（），（1，128），（），（1，127），（），（1，125），），（1，126），（），（2，129），（），（1，127），（），（1，129），（），（1，133），（），（1，132），），（1，131），（），（1，129），（），（2，130），（），（1，129），（），（3，130），（），（1，129），），（1，130），（），（2，132），（），（2，131），（），

9、（1，130），（），（1，126），（），（2，128），），（2，127）1) 原始數(shù)據(jù)所需存儲(chǔ)空間原始數(shù)據(jù)所需存儲(chǔ)空間: 503B+23B+13B+93B+723B=402B2) RLE編碼后得到的代碼為：編碼后得到的代碼為： 50（200,30,100）2（255,255,255）1（0,5,5）9（0,0,0）72（200,30,100）編碼后需存儲(chǔ)空間（行程長(zhǎng)度值用編碼后需存儲(chǔ)空間（行程長(zhǎng)度值用2B表示）表示）2B+3B+2B+3B+2B+3B+2B+3B+ 2B+3B =25B3) 壓縮比率壓縮比率：402:25=16.08 : 1例2：7.5 LZW編碼編碼 7.5.1 LZW

10、編碼方法編碼方法 LZW（Lempel-Ziv & Welch）編碼又稱字串表編碼， 屬于一種無(wú)損編碼， 是Welch將Lempel和Ziv所提出的無(wú)損壓縮技術(shù)改進(jìn)后的壓縮方法。LZW編碼與行程編碼類似， 也是對(duì)字符串進(jìn)行編碼從而實(shí)現(xiàn)壓縮，但它在編碼的同時(shí)還生成了特定字符串以及與之對(duì)應(yīng)的索引字符串表。 LZW算法取得了專利，專利權(quán)的所有者是美國(guó)的一個(gè)大型計(jì)算機(jī)公司Unisys(優(yōu)利系統(tǒng)公司)，除了商業(yè)軟件生產(chǎn)公司之外，可以免費(fèi)使用LZW算法。 字典式（LZ）編碼LZLZ是其發(fā)明者是其發(fā)明者J.ZivJ.Ziv和和A.LempelA.Lempel兩個(gè)猶兩個(gè)猶太人姓氏的縮寫(xiě)。此二人于太人姓氏的縮寫(xiě)

11、。此二人于19771977年發(fā)表題年發(fā)表題為為順序數(shù)據(jù)壓縮的一個(gè)通用算法順序數(shù)據(jù)壓縮的一個(gè)通用算法的論的論文，論文中描述的算法被后人稱為文，論文中描述的算法被后人稱為L(zhǎng)Z77LZ77算算法。法。19781978年，二人又發(fā)表了該論文的續(xù)篇，年，二人又發(fā)表了該論文的續(xù)篇，描述了后來(lái)被命名為描述了后來(lái)被命名為L(zhǎng)Z78LZ78的壓縮算法。的壓縮算法。LZW編碼19841984年，年，Terry WelchTerry Welch發(fā)表論文描述了他在發(fā)表論文描述了他在SperrySperry研究中心的研究成果，也就是后來(lái)非常研究中心的研究成果，也就是后來(lái)非常有名的有名的LZWLZW算法。算法。它實(shí)質(zhì)上是它

12、實(shí)質(zhì)上是LZ78LZ78算法的一個(gè)變種，但被認(rèn)為算法的一個(gè)變種，但被認(rèn)為是一個(gè)獨(dú)立的編碼算法。是一個(gè)獨(dú)立的編碼算法。LZWLZW繼承了繼承了LZ77LZ77和和LZ78LZ78壓縮效果好、速度快的優(yōu)點(diǎn)，而且在算法描述壓縮效果好、速度快的優(yōu)點(diǎn)，而且在算法描述上更容易被人們接受，實(shí)現(xiàn)也相對(duì)簡(jiǎn)單。上更容易被人們接受，實(shí)現(xiàn)也相對(duì)簡(jiǎn)單。字典式（LZ）編碼其實(shí)其實(shí)LZLZ系列的算法并不新鮮，其中既沒(méi)有高系列的算法并不新鮮，其中既沒(méi)有高深的理論背景，也沒(méi)有復(fù)雜的數(shù)學(xué)公式。它們深的理論背景，也沒(méi)有復(fù)雜的數(shù)學(xué)公式。它們只是簡(jiǎn)單的延續(xù)了千百年來(lái)人們對(duì)字典的追崇只是簡(jiǎn)單的延續(xù)了千百年來(lái)人們對(duì)字典的追崇和喜好，并用一

13、種極為巧妙的方式將字典技術(shù)和喜好，并用一種極為巧妙的方式將字典技術(shù)運(yùn)用于通用數(shù)據(jù)壓縮領(lǐng)域。運(yùn)用于通用數(shù)據(jù)壓縮領(lǐng)域。簡(jiǎn)單的說(shuō)如果你習(xí)慣用字典中的頁(yè)碼和行號(hào)簡(jiǎn)單的說(shuō)如果你習(xí)慣用字典中的頁(yè)碼和行號(hào)代替文章中的每個(gè)單詞的時(shí)候，那實(shí)際上你已代替文章中的每個(gè)單詞的時(shí)候，那實(shí)際上你已經(jīng)掌握了經(jīng)掌握了LZLZ系列算法的真諦，因此這類編碼算系列算法的真諦，因此這類編碼算法被統(tǒng)稱為法被統(tǒng)稱為Dictionary codersDictionary coders。LZW編碼而在其后發(fā)展出來(lái)的各式各樣的字典編碼算而在其后發(fā)展出來(lái)的各式各樣的字典編碼算法，基本上都是這三種編碼算法的分支或變體。法，基本上都是這三種編碼算法

14、的分支或變體。也就是說(shuō)也就是說(shuō)LZ77LZ77、LZ78LZ78和和LZWLZW是字典編碼中最基礎(chǔ)是字典編碼中最基礎(chǔ)的的3 3種編碼算法種編碼算法LZ編碼與傳統(tǒng)統(tǒng)計(jì)編碼比較在壓縮效果上字典式編碼大大超過(guò)了在壓縮效果上字典式編碼大大超過(guò)了HuffmanHuffman編碼；編碼；而且在實(shí)現(xiàn)上，壓縮和解壓縮的速度也異而且在實(shí)現(xiàn)上，壓縮和解壓縮的速度也異常驚人。常驚人。于是于是LZLZ系列算法的優(yōu)越性很快就在數(shù)據(jù)壓系列算法的優(yōu)越性很快就在數(shù)據(jù)壓縮領(lǐng)域里體現(xiàn)出來(lái)，使用縮領(lǐng)域里體現(xiàn)出來(lái)，使用LZLZ系列算法的工具系列算法的工具軟件數(shù)量呈爆炸式增長(zhǎng)軟件數(shù)量呈爆炸式增長(zhǎng)LZ78LZ78和和LZWLZW一時(shí)間幾

15、乎統(tǒng)治了一時(shí)間幾乎統(tǒng)治了UNIXUNIX和和DOSDOS兩大兩大平臺(tái)。平臺(tái)。然而隨著時(shí)間流逝，事情變得耐人尋味。目然而隨著時(shí)間流逝，事情變得耐人尋味。目前為止占據(jù)個(gè)人用戶計(jì)算機(jī)的主流壓縮工具幾前為止占據(jù)個(gè)人用戶計(jì)算機(jī)的主流壓縮工具幾乎都采用乎都采用LZ77LZ77變種算法；變種算法；更為優(yōu)秀的更為優(yōu)秀的LZ78LZ78和和LZWLZW沒(méi)有成為最主流的算法？沒(méi)有成為最主流的算法？LZ77LZ77與它們有什么不同？與它們有什么不同？LZ字典編碼專利限制LZ77LZ77完全沒(méi)有專利限制；完全沒(méi)有專利限制；LZ78LZ78在美國(guó)稍稍涉及到一些專利禁止區(qū)；在美國(guó)稍稍涉及到一些專利禁止區(qū)；而而LZWLZW

16、專利權(quán)最終歸屬于專利權(quán)最終歸屬于UnisysUnisys公司；公司；ZIP格式的誕生DOSDOS環(huán)境下由于硬件資源的有限，標(biāo)準(zhǔn)配置環(huán)境下由于硬件資源的有限，標(biāo)準(zhǔn)配置360kB360kB的的5.255.25寸軟盤(pán)；網(wǎng)絡(luò)條件十分有限，寸軟盤(pán)；網(wǎng)絡(luò)條件十分有限，14.4kbit/s14.4kbit/s19851985年年SEASEA公司開(kāi)發(fā)的公司開(kāi)發(fā)的MS-DOSMS-DOS環(huán)境下第一個(gè)應(yīng)環(huán)境下第一個(gè)應(yīng)用用LZWLZW算法的算法的ARCARC（商業(yè)軟件）（商業(yè)軟件）Phillip W.KatzPhillip W.Katz（菲利普（菲利普卡茲）卡茲）ZIP格式的誕生DEFLATEDEFLATE：完美地

17、結(jié)合：完美地結(jié)合LZ77LZ77和和HuffmanHuffman編碼可編碼可將多個(gè)文件壓縮到一個(gè)文件中，無(wú)論壓縮比、將多個(gè)文件壓縮到一個(gè)文件中，無(wú)論壓縮比、壓縮速度都全面超過(guò)了商業(yè)軟件壓縮速度都全面超過(guò)了商業(yè)軟件ARCARC開(kāi)放開(kāi)放ZIPZIP格式，任何人都可以自由使用格式，任何人都可以自由使用ZIPZIP編編碼算法而不需要繳納任何專利費(fèi)用。這個(gè)決定碼算法而不需要繳納任何專利費(fèi)用。這個(gè)決定最終改變了壓縮的世界，使得通用數(shù)據(jù)無(wú)損壓最終改變了壓縮的世界，使得通用數(shù)據(jù)無(wú)損壓縮領(lǐng)域再無(wú)法出現(xiàn)壟斷的商業(yè)巨鱷縮領(lǐng)域再無(wú)法出現(xiàn)壟斷的商業(yè)巨鱷LZW性能分析對(duì)于可預(yù)測(cè)性不大的數(shù)據(jù)具有較好的處理效果對(duì)于可預(yù)測(cè)性不

18、大的數(shù)據(jù)具有較好的處理效果對(duì)于簡(jiǎn)單圖像、平滑且噪聲小的信號(hào)源具有較對(duì)于簡(jiǎn)單圖像、平滑且噪聲小的信號(hào)源具有較高的壓縮比，且壓縮解壓縮速度快；高的壓縮比，且壓縮解壓縮速度快；對(duì)于數(shù)據(jù)流中連續(xù)重復(fù)出現(xiàn)的字節(jié)和字串，具對(duì)于數(shù)據(jù)流中連續(xù)重復(fù)出現(xiàn)的字節(jié)和字串，具有很高的壓縮比，除用于圖像數(shù)據(jù)的壓縮處理外，有很高的壓縮比，除用于圖像數(shù)據(jù)的壓縮處理外，還被用于文本程序等領(lǐng)域的數(shù)據(jù)壓縮還被用于文本程序等領(lǐng)域的數(shù)據(jù)壓縮 LZW編碼的基本思想是：在編碼過(guò)程中，將所遇到的字符串建立一個(gè)字符串表，表中的每個(gè)字符串都對(duì)應(yīng)一個(gè)索引，編碼時(shí)用該字符串在字串表中的索引來(lái)代替原始的數(shù)據(jù)串。例如， 一幅8位的灰度圖像，我們可以采用

19、12位來(lái)表示每個(gè)字符串的索引，前256個(gè)索引用于對(duì)應(yīng)可能出現(xiàn)的256種灰度，由此可建立一個(gè)初始的字符串表，而剩余的3840個(gè)索引就可分配給在壓縮過(guò)程中出現(xiàn)的新字符串，這樣就生成了一個(gè)完整的字符串表， 壓縮數(shù)據(jù)就可以只保存它在字符串表中的索引，從而達(dá)到壓縮數(shù)據(jù)的目的。字符串表是在壓縮過(guò)程中動(dòng)態(tài)生成的，不必將它保存在壓縮文件里，因?yàn)榻鈮嚎s時(shí)字符串表可以由壓縮文件中的信息重新生成。 LZW編碼算法的具體執(zhí)行步驟如下： 步驟1：開(kāi)始時(shí)的詞典包含所有可能的根(Root)，而當(dāng)前前綴P是空的； 步驟2：當(dāng)前字符(C) ：=字符流中的下一個(gè)字符； 步驟3：判斷綴-符串P+C是否在詞典中 (1) 如果“是”：

20、P：= P+C ，即用C擴(kuò)展P)； (2) 如果“否” 把代表當(dāng)前前綴P的碼字輸出到碼字流; 把綴-符串P+C添加到詞典; 令P：= C ，即現(xiàn)在的P僅包含一個(gè)字符C; 步驟4：判斷碼字流中是否還有碼字要譯 (1) 如果“是”，就返回到步驟2； (2) 如果“否” 把代表當(dāng)前前綴P的碼字輸出到碼字流; 結(jié)束。 GIF（Graphics Interchange Format）最初是由美國(guó)CompuServe 于1987年開(kāi)發(fā)的一種壓縮位圖格式。它可支持多達(dá) 256 種的顏色，具有極佳的壓縮效率，已成為Internet 上一種流行的文件格式。GIF圖像文件采用的是一種改良的LZW壓縮算法， 通常稱

21、為GIF-LZW壓縮算法。GIF圖像文件以塊（又稱為區(qū)域結(jié)構(gòu)）的方式來(lái)存儲(chǔ)圖像相關(guān)的信息，具體的文件格式可參考圖像文件格式的相關(guān)書(shū)籍。下面簡(jiǎn)要介紹GIF-LZW的編碼方法。 設(shè)S1、S2為兩個(gè)存放字符串的臨時(shí)變量，LZW_CLEAR和LZW_EOI分別為字符表初始化標(biāo)志和編碼結(jié)束標(biāo)志，GIF-LZW的編碼步驟如下： （1）根據(jù)圖像中使用的顏色數(shù)初始化一個(gè)字串表，字串表中的每個(gè)顏色對(duì)應(yīng)一個(gè)索引。在初始字串表的末尾再添加兩個(gè)符號(hào)（LZW_CLEAR和LZW_EOI）的索引。設(shè)置字符串變量S1、 S2并初始化為空。 （2） 接著輸出LZW_CLEAR在字串表中的索引。 （3）從圖像數(shù)據(jù)流中第一個(gè)字符

22、（假設(shè)數(shù)據(jù)以字符串表示）開(kāi)始， 每次讀取一個(gè)字符，將其賦給字符串變量S2。 （4）判斷“S1+S2”是否已存在于字串表中。如果字串表中存在“S1+S2”，則S1=S1+S2；否則，輸出S1在字串表中的索引， 并在字串表末尾為“S1+S2”添加索引，同時(shí)，S1=S2。 （5）重復(fù)第3和第4步， 直到所有字符讀完為止。 （6）輸出S1中的字符串在字串表中的索引， 然后輸出結(jié)束標(biāo)志LZW_EOI的索引，編碼完畢。 GIF-LZW的解碼過(guò)程比較復(fù)雜，它和編碼過(guò)程正好相反， 即將編碼后的碼字轉(zhuǎn)換成對(duì)應(yīng)的字符串， 重新生成字串表，然后依次輸出對(duì)應(yīng)的字符串即可。GIF-LZW的解碼流程如圖7-2所示， 表中

23、的Code和OldCode是兩個(gè)存放索引的臨時(shí)變量。 LZW編碼算法流程初始化字典初始化字典前綴前綴S = 空串空串C = 從輸入流中讀一個(gè)字符從輸入流中讀一個(gè)字符把新串把新串S+C加到字典中加到字典中S = C輸出結(jié)束標(biāo)記輸出結(jié)束標(biāo)記是結(jié)尾標(biāo)志嗎？是結(jié)尾標(biāo)志嗎？是是S = S+CS+C在字典中嗎？在字典中嗎？是是圖7-2 GIF-LZW解碼流程 開(kāi)始CodeLZW_EOI依次讀取每個(gè)編碼并賦予Code初始化字符串表讀取下一個(gè)編碼給Code將OldCode對(duì)應(yīng)的字符串及該串的第一個(gè)字符組合成新串; 輸出新串,并把新串添加到字串表中OldCode=CodeYNYYNNNY字串表中是否存在Code

24、CodeLZW_CLEAR結(jié)束解碼CodeLZW_CLEAR輸出Code對(duì)應(yīng)的字符串OldCodeCode輸出Code對(duì)應(yīng)的字符串; 將OldCode對(duì)應(yīng)的字符串與Code對(duì)應(yīng)的字符串的第一個(gè)字符組合成新串, 添加到字串表中OldCodeCodenLZW譯碼算法的具體執(zhí)行步驟如下： n n步驟1：在開(kāi)始譯碼時(shí)詞典包含所有可能的前綴根(Root)； n步驟2：cW：=碼字流中的第一個(gè)碼字； n步驟3：輸出當(dāng)前綴-符串string.cW到碼字流； n步驟4：先前碼字pW：= 當(dāng)前碼字cW； n步驟5：當(dāng)前碼字cW：= 碼字流中的下一個(gè)碼字； n步驟6：判斷先前綴-符串string.pW是否在詞典中

25、 (1) 如果“是”： 把先前綴-符串string.pW輸出到字符流； 當(dāng)前前綴P：=先前綴-符串string.pW； 當(dāng)前字符C：=當(dāng)前前綴-符串string.cW的第一個(gè)字符； 把綴-符串P+C添加到詞典； (2) 如果“否”： 當(dāng)前前綴P：=先前綴-符串string.pW； 當(dāng)前字符C：=當(dāng)前綴-符串string.cW的第一個(gè)字符； 輸出綴-符串P+C到字符流，然后把它添加到詞典中。 n步驟7：判斷碼字流中是否還有碼字要譯 (1) 如果“是”，就返回到步驟4； (2) 如果“否”，結(jié)束。 7.5.2 LZW編碼實(shí)例編碼實(shí)例 設(shè)有一來(lái)源于4色（以a、b、c、d表示）圖像的數(shù)據(jù)流aabcab

26、bbbd，現(xiàn)對(duì)其進(jìn)行LZW編碼。編碼過(guò)程如下： 編碼前，首先需要初始化一個(gè)字符串表。由于圖像中只有四種顏色，因而我們可以只用4比特表示字符串表中每個(gè)字符串的索引，表中的前4項(xiàng)代表4種顏色， 后兩項(xiàng)分別表示初始化和圖像結(jié)束標(biāo)志，建立的初始化字符串表如表7-5所示。接著把S1和S2初始化為空（即NULL），輸出LZW_CLEAR的在字符串表中的索引值4H， 接下來(lái)是對(duì)圖像數(shù)據(jù)的編碼。 表表7-5 初始化字符串表初始化字符串表 字符串 索引 A 0 H b1 H c2 H d3 H LZW_CLEAR 4 H LZW_EOI 5 H 讀取圖像數(shù)據(jù)流的第一個(gè)字符“a”，賦給S2， 因S1+S2=“a”

27、已存在字串表中，所以S1=S1+S2=“a”。 接著讀入下一個(gè)字符“a”賦給S2， 因S1+S2=“aa”不存在于字串表中， 所以輸出S1=“a”的索引0H，同時(shí)在字符串表末尾添加新字符串“aa”的索引6H， 并使S1=S2=“a”。 依次讀取數(shù)據(jù)流中的每個(gè)字符，如果S1+S2沒(méi)有出現(xiàn)在字符串表中，則輸出S1中的字符串的索引，并在字符串表末尾為新字符串S1+S2添加索引，并使S1=S2； 否則，不輸出任何結(jié)果，只是使S1=S1+S2。所有字符處理完畢后，輸出S1中的字符串的索引，最后輸出結(jié)束標(biāo)志LZW_EOI的索引。至此，編碼完畢，完整的編碼過(guò)程如表7-6所示， 最后的編碼結(jié)果為“400127

28、1B35”（以十六進(jìn)制表示）。 表表7-6 GIF-LZW編碼過(guò)程編碼過(guò)程 下面對(duì)上述編碼結(jié)果“4001271B35”進(jìn)行解碼。按圖7-2的解碼 流 程 ， 首 先 讀 取 第 一 個(gè) 編 碼 C o d e = 4 H ， 由 于 它 為L(zhǎng)ZW_CLEAR，因此需初始化字符串表， 結(jié)果如表7-5所示（在實(shí)際應(yīng)用中，可根據(jù)文件頭中給定的信息建立初始字符串表）。 讀入下一個(gè)編碼Code=0H，由于它不等于LZW_CLEAR， 因此 輸 出 字 串 表 中 0 H 對(duì) 應(yīng) 的 字 符 串 “ a ” ， 同 時(shí) 使OldCode=Code=0H。 讀入下一個(gè)編碼Code=0H，由于字串表中存在該索

29、引，因此輸出0H所對(duì)應(yīng)的字符串“a”，然后將OldCode=0H所對(duì)應(yīng)的字符串“a”加上Code=0H所對(duì)應(yīng)的字符串的第一個(gè)字符“a”，即“aa”添加到字串表中，其索引為6H，同時(shí)使OldCode=Code=0H。 讀入下一個(gè)編碼Code=1H，由于字串表中存在該索引，因此輸出1H所對(duì)應(yīng)的字符串“b”，然后將OldCode=0H所對(duì)應(yīng)的字符串“a”加上Code=1H所對(duì)應(yīng)的字符串的第一個(gè)字符“b”，即“ a b ” 添 加 到 字 串 表 中 ， 其 索 引 為 7 H ， 同 時(shí) 使OldCode=Code=1H。 讀入下一個(gè)編碼Code=2H，由于字串表中存在該索引， 因此輸出2H所對(duì)應(yīng)的

30、字符串“c”，然后將OldCode=1H所對(duì)應(yīng)的字符串“b”加上Code=2H所對(duì)應(yīng)的字符串的第一個(gè)字符“c”，即“ b c ” 添 加 到 字 串 表 中 ， 其 索 引 為 8 H ， 同 時(shí) 使OldCode=Code=2H。 讀入下一個(gè)編碼Code=7H，由于字串表中存在該索引，因此輸出7H所對(duì)應(yīng)的字符串“ab”，然后將OldCode=2H所對(duì)應(yīng)的字符串“c”加上Code=7H所對(duì)應(yīng)的字符串的第一個(gè)字符“a”， 即“ c a ” 添 加 到 字 串 表 中 ， 其 索 引 為 9 H ， 同 時(shí) 使OldCode=Code=7H。 讀入下一個(gè)編碼Code=1H，由于字串表中存在該索引，

31、因此輸出1H所對(duì)應(yīng)的字符串“b”，然后將OldCode=7H所對(duì)應(yīng)的字符串“ab”加上Code=1H所對(duì)應(yīng)的字符串的第一個(gè)字符“b”，即 “ a b b ” 添 加 到 字 串 表 中 ， 其 索 引 為 A H ， 同 時(shí) 使OldCode=Code=1H。 讀入下一個(gè)編碼Code=BH，由于字串表中不存在該索引， 因此輸出OldCode=1H所對(duì)應(yīng)的字符串“b”加上該字符串的第一個(gè)字符“b”，即“bb”，同時(shí)將“bb”添加到字串表中，其索引為BH， 同時(shí)使OldCode=Code=BH。 讀入下一個(gè)編碼Code=3H，由于字串表中存在該索引， 因此輸出其對(duì)應(yīng)的字符串“d”，然后將OldCo

32、de=BH所對(duì)應(yīng)的字符串“bb”加上Code=3H所對(duì)應(yīng)的字符串的第一個(gè)字符“d”，即“bbd”添加到字串表中，其索引為CH，同時(shí)使OldCode=Code=3H。讀入下一個(gè)編碼Code=5H， 它等于LZW_EOI， 數(shù)據(jù)解碼完畢， 最后的解碼結(jié)果為aabcabbbbd。為清晰起見(jiàn)， 完整的解碼過(guò)程如表7-7所示。 表表7-7 GIF-LZW解碼過(guò)程解碼過(guò)程 7.6 算算 術(shù)術(shù) 編編 碼碼 算術(shù)編碼有兩種模式：一種是基于信源概率統(tǒng)計(jì)特性的固定編碼模式，另一種是針對(duì)未知信源概率模型的自適應(yīng)模式。自適應(yīng)模式中各個(gè)符號(hào)的概率初始值都相同， 它們依據(jù)出現(xiàn)的符號(hào)而相應(yīng)地改變。只要編碼器和解碼器都使用相

33、同的初始值和相同的改變值的方法，那么它們的概率模型將保持一致。上述兩種形式的算術(shù)編碼均可用硬件實(shí)現(xiàn)，其中自適應(yīng)模式適用于不進(jìn)行概率統(tǒng)計(jì)的場(chǎng)合。有關(guān)實(shí)驗(yàn)數(shù)據(jù)表明，在未知信源概率分布的情況下， 算術(shù)編碼一般要優(yōu)于Huffman編碼。在JPEG擴(kuò)展系統(tǒng)中，就用算術(shù)編碼取代了哈夫曼編碼。 下面結(jié)合一個(gè)實(shí)例來(lái)闡述固定模式的算術(shù)編碼的具體方法。設(shè)一待編碼的數(shù)據(jù)序列（即信源）為“dacab”， 信源中各符號(hào)出現(xiàn)的概率依次為P(a)=0.4，P(b)=0.2，P(c)=0.2， P(d)=0.2。 首先，數(shù)據(jù)序列中的各數(shù)據(jù)符號(hào)在區(qū)間0, 1內(nèi)的間隔（賦值范圍）設(shè)定為a=0, 0.4）, b=0.4, 0.6）

34、, c=0.6, 0.8）, d=0.8, 1.0） 為便于討論， 再給出一組關(guān)系式： StartN=StartB+LeftCL EndN=StartB+RightCL 式中，StartN、EndN分別表示新間隔（或稱之為區(qū)間）的起始位置和結(jié)束位置，StartB表示前一間隔的起始位置，L為前一間隔的長(zhǎng)度， LeftC、RightC分別表示當(dāng)前編碼符號(hào)的初始區(qū)間的左端和右端。 第一個(gè)被壓縮的符號(hào)為“d”，其初始間隔為0.8, 1.0)； 第二個(gè)被壓縮的符號(hào)為“a”，由于前面的符號(hào)“d”的取值區(qū)間被限制在0.8, 1.0)范圍內(nèi)，所以“a”的取值范圍應(yīng)在前一符號(hào)間隔0.8, 1.0)的0, 0.4

35、)子區(qū)間內(nèi)， 根據(jù)上式可知 StartN=0.8+0(1.0-0.8)=0.8EndN=0.8+0.4(1.0-0.8)=0.88 即“a”的實(shí)際編碼區(qū)間在0.8, 0.88)之間。 第三個(gè)被壓縮的符號(hào)為“c”， 其編碼取值范圍應(yīng)在0.8, 0.88)區(qū)間的0.6, 0.8)的子區(qū)間內(nèi)，據(jù)上式可知 864. 0)8 . 088. 0(8 . 08 . 0848. 0)8 . 088. 0(6 . 08 . 0NNEndStart第四個(gè)被壓縮的符號(hào)為“a”，同理，根據(jù)上式可知 StartN=0.848+0(0.864-0.848)=0.848EndN=0.848+0.4(0.864-0.848)

36、=0.8544 第五個(gè)被壓縮的符號(hào)為“b”，同理，根據(jù)上式可知 StartN=0.848+0.4(0.8544-0.848)=0.85056EndN=0.848+0.6(0.8544-0.848)=0.85184 至此，數(shù)據(jù)序列“dacab”已被描述為一個(gè)實(shí)數(shù)區(qū)間0.85056, 0.85184，或者說(shuō)在此區(qū)間內(nèi)的任一實(shí)數(shù)值都惟一對(duì)應(yīng)該數(shù)據(jù)序列。這樣，就可以用一個(gè)實(shí)數(shù)表示這一數(shù)據(jù)序列。我們把區(qū)間0. 850 56, 0.851 84用二進(jìn)制形式表示為0.110110011011, 0.110110100001。 從這個(gè)區(qū)間可以看出，0.1101101位于這個(gè)區(qū)間內(nèi)并且其編碼最短， 故把其作為數(shù)

37、據(jù)序列“dacab”的編碼輸出。考慮到算術(shù)編碼中任一數(shù)據(jù)序列的編碼都含有“0.”，所以在編碼時(shí)，可以不考慮“0.”，于是把1101101作為本例中的數(shù)據(jù)序列的算術(shù)編碼。由此可見(jiàn)， 數(shù)據(jù)序列“dacab”用7比特的二進(jìn)制代碼就可以表示， 平均碼長(zhǎng)為1.4比特字符。 解碼是編碼的逆過(guò)程，根據(jù)編碼時(shí)的概率分配表和壓縮后數(shù)據(jù)代碼所在的范圍，確定代碼所對(duì)應(yīng)的每一個(gè)數(shù)據(jù)符號(hào)。由此可見(jiàn)，算術(shù)編碼的實(shí)現(xiàn)方法要比哈夫曼編碼復(fù)雜一些。 n預(yù)測(cè)編碼是統(tǒng)計(jì)冗余數(shù)據(jù)壓縮理論的三個(gè)重要分支之一。 n預(yù)測(cè)編碼的理論基礎(chǔ)是現(xiàn)代統(tǒng)計(jì)學(xué)和控制論，它主要減少了數(shù)據(jù)在時(shí)間和空間上的相關(guān)性。 n對(duì)于靜止圖像來(lái)說(shuō)，預(yù)測(cè)編碼將被圖像變換編

38、碼所取代。n而預(yù)測(cè)編碼對(duì)于視頻信號(hào)來(lái)說(shuō)，它充分利用了連續(xù)幀之間的統(tǒng)計(jì)冗余性，是當(dāng)今主流技術(shù)并且還會(huì)流行于未來(lái)。預(yù)測(cè)編碼的基本原理預(yù)測(cè)編碼的基本原理 v 預(yù)測(cè)編碼是根據(jù)圖像數(shù)學(xué)模型利用以往的樣本值對(duì)于新樣本值進(jìn)行預(yù)測(cè)，然后將樣本的實(shí)際值與其預(yù)測(cè)值相減得到一個(gè)誤差值，對(duì)這一誤差值進(jìn)行編碼。v 如果模型足夠好且樣本序列在時(shí)間上相關(guān)性較強(qiáng)，那么誤差信號(hào)的幅度將遠(yuǎn)遠(yuǎn)小于原始信號(hào)，從而可以用較少的電平類對(duì)其差值量化得到較大的數(shù)據(jù)壓縮效果。 預(yù)測(cè)編碼的基本原理預(yù)測(cè)編碼的基本原理 如果能精確地預(yù)測(cè)數(shù)據(jù)源輸出，那就不存在關(guān)于數(shù)據(jù)源的不確定性，因而也就不存在要傳輸?shù)男畔?。然而沒(méi)有一個(gè)實(shí)際的系統(tǒng)能找到其完整的數(shù)學(xué)模

39、型，我們能找到的最好預(yù)測(cè)器是以某種最小化的誤差對(duì)下一個(gè)采樣進(jìn)行預(yù)測(cè)的預(yù)測(cè)器。 v 通常預(yù)測(cè)器的設(shè)計(jì)不是利用數(shù)據(jù)源的實(shí)際數(shù)學(xué)模型，因?yàn)閿?shù)據(jù)源的實(shí)際數(shù)學(xué)模型是非常復(fù)雜，而且是時(shí)變的。v實(shí)驗(yàn)結(jié)果表明以最小均方預(yù)測(cè)誤差設(shè)計(jì)的預(yù)測(cè)器不但能獲得最小均方預(yù)測(cè)誤差，同時(shí)在視覺(jué)效果上也是比較好的 DPCM(差分差分脈沖編碼）脈沖編碼）工作原理工作原理+量化器輸出到信道+列延遲器23/aa行延遲器2a1a+jiu,jie,jiu,*jie,*jiu,*jiu,*jiu, 1*1, 131,2*jijiuauavuij為輸入信號(hào)ve*ij量化后的輸出信號(hào)va1, a2, a3為預(yù)測(cè)系數(shù)*ijuv 為根據(jù)ui-1,j

40、、ui,j-1、ui-1,j-1對(duì)uij所作的預(yù)測(cè)值veij為差值信號(hào)*iju預(yù)測(cè)編碼器n如果沒(méi)有量化器，那么就是無(wú)損編碼n如果有量化器，則是有損編碼+ -符號(hào)符號(hào)編碼編碼壓縮圖像輸入圖像enfn fn量化器量化器n預(yù)測(cè)器預(yù)測(cè)器預(yù)測(cè)方程為 量化器的輸入為重建方程為v預(yù)測(cè)模型的復(fù)雜程度取決于線性預(yù)測(cè)中使用以前樣本的數(shù)目，樣本點(diǎn)越多，預(yù)測(cè)器就越復(fù)雜。 v預(yù)測(cè)器的好壞取決于預(yù)測(cè)系數(shù)*11,2,131,1ijiji jijuaua ua u*ijijijeuu*ijijijuue無(wú)損預(yù)測(cè)編碼n舉例：公式： 中?。簄m = 2，a1 = a2 = 1/2f = 154,159,151,149,139,1

41、21,112,109,129預(yù)測(cè)值 f2 = 1/2 * (154 + 159) 156 e2 = 151 156 = -5 f3 = 1/2 * (159 + 151) = 155 e3 = 149 155 = -6 f4 = 1/2 * (151 + 149) = 150 e4 = 139 150 = -11 f5 = 1/2 * (149 + 139) = 144 e5 = 121 144 = -23 f6 = 1/2 * (139 + 121) = 130 e6 = 112 130 = -18 f7 = 1/2 * (121 + 112) 116 e7 = 109 116 = -7 f

42、8 = 1/2 * (112 + 109) 110 e8 = 129 110 = 19)(1miininfaroundf采用自適應(yīng)系數(shù)預(yù)測(cè)編碼后的重構(gòu)圖像a1=0.340, a2=0.664, a3=-0.005 1. 根據(jù)輸入圖像來(lái)確定預(yù)測(cè)系數(shù) 2. 另外一種采用的是固定的預(yù)測(cè)系數(shù)是采用固定系數(shù)預(yù)測(cè)編碼后的結(jié)果 a1=0.5, a2=0.5, a3=-0.5 直接采用均勻標(biāo)量量化后的結(jié)果在實(shí)驗(yàn)中采用幾種不同的預(yù)測(cè)系數(shù) 采用不同的預(yù)測(cè)系數(shù)的預(yù)測(cè)編碼的結(jié)果 混合編碼混合編碼n設(shè)計(jì)思想：設(shè)計(jì)思想： 每一種編碼方式都有其擅長(zhǎng)的一點(diǎn)，以及每一種編碼方式都有其擅長(zhǎng)的一點(diǎn)，以及局限的一點(diǎn)，混合編碼的思想就

43、是將兩局限的一點(diǎn)，混合編碼的思想就是將兩種以上的編碼方式的優(yōu)點(diǎn)進(jìn)行綜合，達(dá)種以上的編碼方式的優(yōu)點(diǎn)進(jìn)行綜合，達(dá)到提高編碼效率的目的。到提高編碼效率的目的。n混合編碼實(shí)現(xiàn)的可能性及有效性分析混合編碼實(shí)現(xiàn)的可能性及有效性分析回顧一下講過(guò)的幾個(gè)內(nèi)容的特點(diǎn)：回顧一下講過(guò)的幾個(gè)內(nèi)容的特點(diǎn)：1 1）行程編碼：）行程編碼： 擅長(zhǎng)于重復(fù)數(shù)字的壓縮。擅長(zhǎng)于重復(fù)數(shù)字的壓縮。2 2）HuffmanHuffman編碼：擅長(zhǎng)于像素個(gè)數(shù)分布不均勻情編碼：擅長(zhǎng)于像素個(gè)數(shù)分布不均勻情 況下的編碼。況下的編碼。n例：例： aaaa bbb cc d eeeee fffffff （共共2222* *8=176 bits)8=176

44、 bits) 4 3 2 1 5 7 行程編碼：行程編碼：4a3b2c1d5e7f 4a3b2c1d5e7f ( (共共6 6* *（8+38+3）= 66Bits = 66Bits ) ) 176 66 aaaa bbb cc d eeeee fffffff （共22*8=176 bits) 4 3 2 1 5 7 HuffmanHuffman編碼：編碼： f=01 e=11 a=10 b=001 c=0001 d=0000 10101010 001001001 00010001 0000 1111111111 01010101010101 (共共 7*2+5*2+4*2+3*3+2*4+1

45、*4=53 bits) 176 66 53 aaaa bbb cc d eeeee fffffff （共22*8=176 bits) 4 3 2 1 5 7 HufmanHufman與行程編碼混合：與行程編碼混合： 41030012000110000511701 (共：共：3+2+3+3+3+4+3+4+3+2+3+2=35 bits) 176 66 53 35 100%37.5%30.1% 9.9%預(yù)處理正交變換量化編碼傳輸或存儲(chǔ)后處理反變換譯碼f(x,y)g(x,y)7.8 正交變換編碼正交變換編碼 對(duì)變換系數(shù)編碼對(duì)變換系數(shù)編碼1.基本原理基本原理特性特性: :正交變換具有熵保持特性正交變

46、換具有熵保持特性正交變換具有能量保持特性正交變換具有能量保持特性能量的重新分布與集中能量的重新分布與集中去相關(guān)特性去相關(guān)特性(去冗余度去冗余度)2.數(shù)學(xué)模型分析數(shù)學(xué)模型分析 設(shè)圖像信源設(shè)圖像信源向量向量X, X =X0,X1,XN-1 變換后得變換后得向量向量Y, Y =Y0,Y1,YN-1 變換為變換為T正交矩陣正交矩陣 TT = I =TT-1 Y=TX 關(guān)鍵問(wèn)題，在于選取什么樣的正交變換關(guān)鍵問(wèn)題，在于選取什么樣的正交變換T, 才能既得到最大的壓縮率，又不造成嚴(yán)重的才能既得到最大的壓縮率，又不造成嚴(yán)重的失真失真YTXNM,Y,.,Y,YY1M10如果取一部分系數(shù)編碼如果取一部分系數(shù)編碼則將

47、將Y=TX代入，可得：代入，可得：的的均均值值與與分分別別是是)()(YXYXYYYYECXXXXECYX TCTCXY 研究研究Y的協(xié)方差矩陣的協(xié)方差矩陣Cx是圖像本身固有是圖像本身固有關(guān)鍵是尋找關(guān)鍵是尋找T,使變換系數(shù)間的相關(guān)性盡量小使變換系數(shù)間的相關(guān)性盡量小 (2)最佳的準(zhǔn)則最佳的準(zhǔn)則 均方誤差準(zhǔn)則下的最佳變換均方誤差準(zhǔn)則下的最佳變換 1010221010222),(),(1),(1NxNyNxNyyxfyxgNyxeNe3.最佳變換最佳變換(1)應(yīng)滿足的條件應(yīng)滿足的條件 把相關(guān)性全部去除把相關(guān)性全部去除 方差高度集中方差高度集中設(shè)有一數(shù)據(jù)向量設(shè)有一數(shù)據(jù)向量 X =x1,x2,xN,正交

48、變換后正交變換后 Y=TX Y =Y1,Y2,YN01ITTjijiji (3)K-L變換變換(Karhunan-Loeve) 設(shè)設(shè)T是正交變換矩陣是正交變換矩陣 T = 1, 2, NN N N是是N維向量，矩陣是正交的：維向量，矩陣是正交的： NiiiNYYTX1NN221121Y.YYY.則則 為壓縮，取為壓縮，取M個(gè)元素個(gè)元素 MN Y1,Y2,YM 其余用其余用bi代替，可得代替，可得X的估計(jì)值的估計(jì)值 NMiiiMiiibYX11X NMiiiNMiNMjjijjiiNMiiiiNMiiiMiiibYEbYbYEXXEXEbYbYXXXX12112111)()()()(:由由正正交

49、交條條件件為為均均方方差差設(shè)設(shè)估估計(jì)計(jì)誤誤差差： iNMiXiiNMiiNMiiiiiNMiiiiiiiiCXXXXEbYbYEbYEbYXbX 11112i )()(,Y 是是實(shí)實(shí)數(shù)數(shù)代代入入將將ib . 求求最最佳佳AXXEbXYYEbbYEbYEbbiiiiiiiiiiiii0 2)(2 又又 求條件極值，求條件極值，LagrangeLagrange法求極值法求極值求求f(xf(x1 1,x,x2 2, ,x,xN N) )服從服從 k k(x(x1 1,x,x2 2, ,x,xN N) )條件的極值問(wèn)條件的極值問(wèn)題題, ,作一個(gè)新的函數(shù)作一個(gè)新的函數(shù)1 ii是是拉拉格格朗朗日日乘乘數(shù)數(shù)

50、kNkNkkNxxxxxxf 12121),.,(),.,(B.B.求最佳的求最佳的 i i01 Nkikkixxf 1)1(11 NMiiiiiXiNMiiiiC iXiXiiCC 2對(duì)對(duì) 求求導(dǎo)導(dǎo)求極值求極值作一個(gè)新的函數(shù)作一個(gè)新的函數(shù)iiiXiiiXiiiiCCi 0222由線性代數(shù)理論由線性代數(shù)理論: : 0)(0iXiiXiiCIC 知知 i i是是C Cx x的特征根的特征根, , i i是是C Cx x的特征向量的特征向量(4)最佳變換的實(shí)現(xiàn)最佳變換的實(shí)現(xiàn) a)給定信源給定信源X,統(tǒng)計(jì)統(tǒng)計(jì)X b)由由Cx求求 矩陣矩陣,即即 I-Cx 由由 I-Cx =0求特征根及特征向量求特征

51、根及特征向量 c)由特征向量求由特征向量求T d)由由T對(duì)圖像作對(duì)圖像作K-L變換變換求最佳變換求最佳變換 100011011XC0, 1, 20) 1() 1(100011011)(100011011 3213 fCIX例例:已知信源已知信源X寫(xiě)出寫(xiě)出 矩陣矩陣)0 ,(0) 1 , 0 , 0(1)0 ,(),0 , 1 , 1 (0000100011011212132212132121321同理歸一化基礎(chǔ)解系xxxxxxxx求求 1=2的特征向量的特征向量( 1I-Cx)X=0 01000010002121212121212121TT求求T3 DCT變換編碼nDCTDCT變換編碼方法：變換編碼方法：DCT變換變換DCTDCT逆變換逆變換原圖像原圖像除以量化矩陣除以量化矩陣取整取整1 1）編碼過(guò)程：）編碼過(guò)程：2 2）解碼過(guò)程：）解碼過(guò)程：壓縮圖像壓縮圖像乘以量化矩陣乘以量化矩陣取整取整壓縮壓縮圖像圖像解壓解壓圖像圖像3 DCT變換編碼Huffman:42bits； 編碼效率編碼效率32.8%Huffman:16bits;編碼效率：編碼效率：12.5%29221714241613141914121216111116C例：例：56606159586059625759596157586059F