第7章-圖像編碼-2

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

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

3、 1.一維行程編碼一維行程編碼編碼思想：編碼思想： 將一行中顏色值相同的相鄰象素（行將一行中顏色值相同的相鄰象素（行程）用一個計數(shù)值（行程的長度）和該顏程）用一個計數(shù)值（行程的長度）和該顏色值（行程的灰度）來代替，從而去除像色值（行程的灰度）來代替，從而去除像素冗余。素冗余。 設(shè)沿某一掃描行的像素為設(shè)沿某一掃描行的像素為x1,x2,xN對應(yīng)的對應(yīng)的灰度值可能為灰度值可能為g1,g2,g3,g4. 把像素映射成序列對：把像素映射成序列對： (g1,l l1)，(g2, l l2)，(g3, l l3)，(g4, l l4) 直接對直接對(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次運行的行程，即連續(xù)取值為次運行的行程，即連續(xù)取值為gi灰度值的像素灰度值的像素的個數(shù)的個數(shù) 8級灰度，級灰度，24個像素個像素對對xi編碼，總的比特數(shù)，至少編碼，總的比特數(shù)，至少24 3=72bit如對如對(gi,li)編碼，灰度值用編碼，灰度值用3bit，行程長度用，行程長度用4bit每對參數(shù)用每對參數(shù)用7bit，總比特數(shù)只需，總比特

5、數(shù)只需28bit就夠就夠i gi li13 62510342486 例：映射對：例：映射對：行程編碼（RLE）n對于有大面積色塊的圖像，壓縮效果很好n對于紛雜的圖像，壓縮效果不好，最壞情況下（圖像中每兩個相鄰點的顏色都不同 ），會使數(shù)據(jù)量加倍，所以現(xiàn)在單純采用行程編碼的壓縮算法用得并不多，PCX文件算是其中之一二維行程編碼n二維行程編碼要解決的核心問題是：將二維排列的像素，采用某種方式轉(zhuǎ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ù)所需存儲空間原始數(shù)據(jù)所需存儲空間: 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）編碼后需存儲空間（行程長度值用編碼后需存儲空間（行程長度值用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）編碼又稱字串表編碼， 屬于一種無損編碼， 是Welch將Lempel和Ziv所提出的無損壓縮技術(shù)改進后的壓縮方法。LZW編碼與行程編碼類似， 也是對字符串進行編碼從而實現(xiàn)壓縮，但它在編碼的同時還生成了特定字符串以及與之對應(yīng)的索引字符串表。 LZW算法取得了專利，專利權(quán)的所有者是美國的一個大型計算機公司Unisys(優(yōu)利系統(tǒng)公司)，除了商業(yè)軟件生產(chǎn)公司之外，可以免費使用LZW算法。 字典式（LZ）編碼LZLZ是其發(fā)明者是其發(fā)明者J.ZivJ.Ziv和和A.LempelA.Lempel兩個猶兩個猶太人姓氏的縮寫。此二人于太人姓

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

35、 0.4)子區(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”的實際編碼區(qū)間在0.8, 0.88)之間。 第三個被壓縮的符號為“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第四個被壓縮的符號為“a”，同理，根據(jù)上式可知 StartN=0.848+0(0.864-0.848)=0.848EndN=0.848+0.4(0.864-0.

36、848)=0.8544 第五個被壓縮的符號為“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”已被描述為一個實數(shù)區(qū)間0.85056, 0.85184，或者說在此區(qū)間內(nèi)的任一實數(shù)值都惟一對應(yīng)該數(shù)據(jù)序列。這樣，就可以用一個實數(shù)表示這一數(shù)據(jù)序列。我們把區(qū)間0. 850 56, 0.851 84用二進制形式表示為0.110110011011, 0.110110100001。 從這個區(qū)間可以看出，0.1101101位于這個區(qū)間內(nèi)并且其編碼最短， 故把

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

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

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

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

41、39,121,112,109,129預(yù)測值 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 =

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

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

44、=176 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

45、*4+1*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ù)處理正交變換量化編碼傳輸或存儲后處理反變換譯碼f(x,y)g(x,y)7.8 正交變換編碼正交變換編碼 對變換系數(shù)編碼對變換系數(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)鍵問題，在于選取什么樣的正交變換關(guān)鍵問題，在于選取什么樣的正交變換T, 才能既得到最大的壓縮率，又不造成嚴重的才能既得到最大的壓縮率，又不造成嚴重的失真失真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,x

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

49、由正正交交條條件件為為均均方方差差設(shè)設(shè)估估計計誤誤差差： iNMiXiiNMiiNMiiiiiNMiiiiiiiiCXXXXEbYbYEbYEbYXbX 11112i )()(,Y 是是實實數(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) )條件的極值問條件的極值問題題, ,作一個新的函數(shù)作一個新的函數(shù)1 ii是是拉拉格格朗朗日日

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

51、量求特征根及特征向量 c)由特征向量求由特征向量求T d)由由T對圖像作對圖像作K-L變換變換求最佳變換求最佳變換 100011011XC0, 1, 20) 1() 1(100011011)(100011011 3213 fCIX例例:已知信源已知信源X寫出寫出 矩陣矩陣)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）編碼過程：）編碼過程：2 2）解碼過程：）解碼過程：壓縮圖像壓縮圖像乘以量化矩陣乘以量化矩陣取整取整壓縮壓縮圖像圖像解壓解壓圖像圖像3 DCT變換編碼Huffman:42bits； 編碼效率編碼效率32.8%Huffman:16bits;編碼效率：編碼效率：12.5%29221714241613141914121216111116C例：例：56606159586059625759596157586059F