第七章圖像壓縮編碼ppt課件

1、 壓縮技術(shù)簡史壓縮技術(shù)簡史 壓縮技術(shù)基礎(chǔ)壓縮技術(shù)基礎(chǔ) Huffman編碼編碼 算術(shù)編碼算術(shù)編碼 LZ77和和LZW算法算法 JPEG算法算法 小波分析用于靜止圖像編碼小波分析用于靜止圖像編碼壓縮技術(shù)的應(yīng)用電報、(CCITT)通訊(Modem/網(wǎng)絡(luò)協(xié)議)存儲(壓縮池)文件系統(tǒng)(壓縮扇區(qū))圖像(GIF/TIFF/JPEG)音頻(MP3)視頻(MPEG/RM)數(shù)據(jù)庫(B+樹)歸檔(TAR/ZIP)密碼學(xué)(消除數(shù)據(jù)的原始特征)全文索引(倒排索引表)編譯(JAVA)程序設(shè)計(jì)(算法/空間和時間效率)人工智能(專家系統(tǒng)/知識樹)壓縮技術(shù)起源信息壓縮技術(shù)的起源比計(jì)算機(jī)的發(fā)明早幾千年信息論信息存在冗余信息存在冗

2、余通過采用一定通過采用一定的模型和編碼方法，的模型和編碼方法，可以降低這種冗余度可以降低這種冗余度貝爾實(shí)驗(yàn)室的 Claude Shannon 和 MIT 的 R.M.Fano幾乎同時提出了最早的對符號進(jìn)行有效編碼從而實(shí)現(xiàn)數(shù)據(jù)壓縮的 Shannon-Fano 編碼方法。D.A.Huffman1952 年 發(fā)表論文：“最小冗余度代碼的構(gòu)造方法”A Method for the Construction of Minimum Redundancy CodesUNIX 系統(tǒng)上一個不太為現(xiàn)代人熟知的壓縮程序 COMPACT 就是 Huffman 0 階自適應(yīng)編碼的具體實(shí)現(xiàn) 80 年代初，Huffman

3、編碼又在 CP/M 和 DOS 系統(tǒng)中實(shí)現(xiàn)，其代表程序叫 SQHuffman時代：時代：60 年代、年代、70 年代乃至年代乃至 80 年代的早期年代的早期接近極限熵80年代早期，數(shù)學(xué)家們設(shè)計(jì)出算術(shù)編碼方法(Arithmetic Coding)可以證明，算術(shù)編碼得到的壓縮效果可以最大地減小信息的冗余度，用最少量的符號精確表達(dá)原始信息內(nèi)容 q 但是，在同樣的計(jì)算機(jī)系統(tǒng)上，算術(shù)編碼雖然可以得到最好的壓縮效果，卻要消耗也許幾十倍的計(jì)算時間 算術(shù)編碼是部分匹配預(yù)測(Predication by Partial matching, PPM)技術(shù)的變體以色列人1978 年 發(fā)表論文：“通過可變比率編碼的獨(dú)

4、立序列的壓縮”Compression of Individual Sequences via Variable-Rate Coding字典編碼時代：字典編碼時代：LZ77和和LZ78壓縮算法壓縮算法1977 年 發(fā)表論文：“順序數(shù)據(jù)壓縮的一個通用算法”A Universal Algorithm for Sequential Data CompressionLZW算法Welch 實(shí)現(xiàn)了 LZ78 算法的一個變種 LZW算法UNIX：運(yùn)用 LZW 算法的 Compress 程序MS-DOS：ARC 程序，以及PKWare、PKARC 等仿制品。 1984 年 發(fā)表論文：“高性能數(shù)據(jù)壓縮技術(shù)”A T

5、echnique for High-Performance Data Compression 通用數(shù)據(jù)壓縮80年代中期以后，對LZ77算法進(jìn)行改進(jìn)Haruyasu Yoshizaki(Yoshi) 的 LHarcRobert Jung 的 ARJ 從PKZip到WinZip：通用數(shù)據(jù)壓縮格式標(biāo)準(zhǔn) ZIPLZ77、LZ78、LZW 一起壟斷當(dāng)今的通用數(shù)據(jù)壓縮領(lǐng)域一起壟斷當(dāng)今的通用數(shù)據(jù)壓縮領(lǐng)域多媒體數(shù)據(jù)壓縮q國際電報電話咨詢委員會( CCITT ) ：針對二值圖像的一系列壓縮標(biāo)準(zhǔn)，如 CCITT Group3、CCITT Group4 等 (此外還包括CCITT與ISO共同制訂的JBIG標(biāo)準(zhǔn)) 。

6、q70 年代末 80 年代初：數(shù)學(xué)家們提出了損失壓縮精度以換取壓縮率的嶄新思路。國際標(biāo)準(zhǔn)化組織( ISO )和 CCITT 聯(lián)合組成了兩個委員會：靜態(tài)圖像聯(lián)合專家小組( JPEG )和動態(tài)圖像聯(lián)合專家小組( MPEG )。誕生了 JPEG、MPEG-1、MPEG-2、MPEG-4、MPEG-7 等系列標(biāo)準(zhǔn)。qPostScript矢量圖形格式：起源于 1976 年的 Evans & Sutherland 計(jì)算機(jī)公司，當(dāng)時的名字是 Design System。1978 年，John Warnock 和 Martin Newel 將其演變?yōu)?JAM 言語。1982 年，John Warnoc

7、k 和 Chuck Geschke 創(chuàng)建了著名的 Adobe System 公司，第三次設(shè)計(jì)和實(shí)現(xiàn)了這個語言，并稱其為 PostScript。技術(shù)準(zhǔn)備：什么是熵熵熵來源于來源于40年代由年代由Claude Shannon創(chuàng)立的信息論中的一條定理，創(chuàng)立的信息論中的一條定理，這一定理借用了熱力學(xué)中的名詞這一定理借用了熱力學(xué)中的名詞“熵熵”( Entropy )來表示一條信息中來表示一條信息中真正需要編碼的信息量：真正需要編碼的信息量：考慮用 0 和 1 組成的二進(jìn)制數(shù)碼為含有 n 個符號的某條信息編碼，假設(shè)符號 Fn 在整條信息中重復(fù)出現(xiàn)的概率為 Pn，則該符號的熵也即表示該符號所需的二進(jìn)制位數(shù)為

8、：En = - log2( Pn )整條信息的熵也即表示整條信息所需的二進(jìn)制位數(shù)為：E = knEn例：對信息aabbaccbaa，字符串長度為 10，字符a、b、c分別出現(xiàn)了5、3、2次，那么Ea=-log2(0.5)=1 Eb=-log2(0.3)=1.737 Ec=-log2(0.2)=2.322E= 5Ea + 3Eb + 2Ec =14.855 位對比一下，我們用ASCII編碼表示該信息需要80位技術(shù)準(zhǔn)備：模型使用模型：得到字符或單詞在信息中出現(xiàn)的概率靜態(tài)/半靜態(tài)模型自適應(yīng)模型Claude Shannon的“聚會游戲”(party game)：他每次向聽眾公布一條被他隱藏起一個字符的

9、消息，讓聽眾來猜下一個字符，一次猜一個，直到猜對為止。然后，Shannon 使用猜測次數(shù)來確定整個信息的熵。（人的語言經(jīng)驗(yàn)）靜態(tài)字典模型自適應(yīng)字典模型統(tǒng)計(jì)模型字典模型技術(shù)準(zhǔn)備：編碼通過模型，我們可以確定對某一個符號該用多少位二進(jìn)制數(shù)進(jìn)行編碼?，F(xiàn)在的問題是，如何設(shè)計(jì)一種編碼方案，使其盡量精確地用模型計(jì)算出來的位數(shù)表示某個符號。前綴編碼規(guī)則：任何一個符號的編碼都不是另一個符號編碼的前綴。最簡單的前綴編碼字符字符編碼編碼A0B10C110D1110E111101110010101110110111100010 D A B B D C E A A B 技術(shù)準(zhǔn)備：緊縮=模型+編碼輸入模型編碼輸出符號概率

10、代碼Shannon-Fano編碼cabcedeacacdeddaaabaababaaabbacdebaceada a 16b 7c 6d 6e - 5 a 16b 7-c 6-d 6e - 5 例子中的信息編碼為：例子中的信息編碼為：11 00 01 11 101 100 101 00 11 00 11 .碼長共碼長共91位，而使用位，而使用ASCII編碼表示上述信息共需要編碼表示上述信息共需要240位位a 00b 01c 11d 100e 101root00111abc01deHuffman編碼cabcedeacacdeddaaabaababaaabbacdebaceada a 16b 7c

11、 6d 6e - 5 例子中的信息編碼為：例子中的信息編碼為：001 1 000 001 011 010 011 1 001 1 001 .碼長碼長88位，比位，比Shannon-Fano編碼略短一些編碼略短一些a 1b 000c 001d 010e 011root01a011bcde001整數(shù)位編碼與信息熵cabcedeacacdeddaaabaababaaabbacdebaceada 該信息的熵經(jīng)計(jì)算可知為86.601位符號符號理想位數(shù)理想位數(shù)（熵）（熵）S-F編碼需編碼需要位數(shù)要位數(shù)Huffman編編碼需要位數(shù)碼需要位數(shù)a1.32221b2.51523c2.73723d2.73733e3

12、.00033總計(jì)總計(jì)86.6019188另：Huffman編碼還有一個變種范式Huffman編碼，可以有效減少編碼字典的存儲空間。Huffman編碼的模型選擇奇怪的段落奇怪的段落If Youth，throughout all history，had had a champion to stand up for it；to show a doubting world that a child can think；and，possibly，do it practically；you wouldnt constantly run across folks today who claim that a

13、 child dont know anything.“- Gadsby by E.V.Wright, 1939.算術(shù)編碼假設(shè)某個字符的出現(xiàn)概率為 80%，該字符事實(shí)上只需要 -log2(0.8) = 0.322 個二進(jìn)制位進(jìn)行編碼難道真的能只輸出 0.322 個 0 或 0.322 個 1 嗎？算術(shù)編碼的輸出是：一個小數(shù)算術(shù)編碼的輸出是：一個小數(shù)算術(shù)編碼對整條信息無論信息有多么長），其輸出僅僅是一個數(shù)，而且是一個介于0和1之間的二進(jìn)制小數(shù)。例如算術(shù)編碼對某條信息的輸出為1010001111，那么它表示小數(shù)0.1010001111，也即十進(jìn)制數(shù)0.64算術(shù)編碼例：考慮某條信息中可能出現(xiàn)的字符僅有

14、 a b c 三種，我們要壓縮保存的原始信息為 bccb第一步：在沒有開始壓縮進(jìn)程之前，假設(shè)我們對第一步：在沒有開始壓縮進(jìn)程之前，假設(shè)我們對 a b c a b c 三者在信息中三者在信息中的出現(xiàn)概率一無所知我們采用的是自適應(yīng)模型），即認(rèn)為三者的出現(xiàn)的出現(xiàn)概率一無所知我們采用的是自適應(yīng)模型），即認(rèn)為三者的出現(xiàn)概率相等，也就是都為概率相等，也就是都為1/31/3，我們將，我們將0-10-1區(qū)間按照概率的比例分配給三個區(qū)間按照概率的比例分配給三個字符，即字符，即a a從從0.00000.0000到到0.33330.3333，b b從從0.33330.3333到到0.66670.6667，c c從從

15、0.66670.6667到到1.00001.0000。用圖形表示就是：。用圖形表示就是：1.00000.66670.33330.0000Pc = 1/3Pb = 1/3Pa = 1/3算術(shù)編碼第二步：現(xiàn)在我們拿到第一個字符第二步：現(xiàn)在我們拿到第一個字符b b，讓我們把目光投向，讓我們把目光投向b b對應(yīng)的區(qū)間對應(yīng)的區(qū)間0.3333-0.66670.3333-0.6667。這時由于多了字符。這時由于多了字符b b，三個字符的概率分布變成：，三個字符的概率分布變成：Pa=1/4Pa=1/4，Pb=2/4Pb=2/4，Pc=1/4Pc=1/4。好，讓我們按照新的概率分布比例劃分。好，讓我們按照新的概

16、率分布比例劃分0.3333-0.66670.3333-0.6667這一區(qū)間，劃分的結(jié)果可以用圖形表示為：這一區(qū)間，劃分的結(jié)果可以用圖形表示為：0.66670.58340.41670.3333Pc = 1/4Pb = 2/4Pa = 1/4例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb算術(shù)編碼第三步：接著我們拿到字符第三步：接著我們拿到字符c c，我們現(xiàn)在要關(guān)注上一步中得到的，我們現(xiàn)在要關(guān)注上一步中得到的c c的區(qū)間的區(qū)間 0.5834-0.66670.5834-0.6667。新添了。新添了c c以后，三個字符的概率分布變成以后，三個字符的概率分布變

17、成Pa=1/5Pa=1/5，Pb=2/5Pb=2/5，Pc=2/5Pc=2/5。我們用這個概率分布劃分區(qū)間。我們用這個概率分布劃分區(qū)間0.5834-0.66670.5834-0.6667：0.66670.63340.60010.5834Pc = 2/5Pb = 2/5Pa = 1/5例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb算術(shù)編碼第四步：現(xiàn)在輸入下一個字符第四步：現(xiàn)在輸入下一個字符c c，三個字符的概率分布為：，三個字符的概率分布為：Pa=1/6Pa=1/6，Pb=2/6Pb=2/6，Pc=3/6Pc=3/6。我們來劃分。我們來劃分c c的區(qū)

18、間的區(qū)間0.6334-0.66670.6334-0.6667：0.66670.65010.63900.6334Pc = 3/6Pb = 2/6Pa = 1/6例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb算術(shù)編碼第五步：輸入最后一個字符第五步：輸入最后一個字符b b，因?yàn)槭亲詈笠粋€字符，不用再做進(jìn)一步，因?yàn)槭亲詈笠粋€字符，不用再做進(jìn)一步的劃分了，上一步中得到的的劃分了，上一步中得到的b b的區(qū)間為的區(qū)間為0.6390-0.65010.6390-0.6501，好，讓我們在這，好，讓我們在這個區(qū)間內(nèi)隨便選擇一個容易變成二進(jìn)制的數(shù)，例如個區(qū)間內(nèi)隨便選擇一

19、個容易變成二進(jìn)制的數(shù)，例如0.640.64，將它變成二進(jìn)，將它變成二進(jìn)制制0.10100011110.1010001111，去掉前面沒有太多意義的，去掉前面沒有太多意義的0 0和小數(shù)點(diǎn)，我們可以輸出和小數(shù)點(diǎn)，我們可以輸出10100011111010001111，這就是信息被壓縮后的結(jié)果，我們完成了一次最簡單的算，這就是信息被壓縮后的結(jié)果，我們完成了一次最簡單的算術(shù)壓縮過程術(shù)壓縮過程0.66670.65010.63900.6334Pc = 3/6Pb = 2/6Pa = 1/6例：考慮某條信息中可能出現(xiàn)的字符僅有 a b c 三種，我們要壓縮保存的原始信息為 bccb輸出輸出:(0.64)10

20、= (0.1010001111)2自適應(yīng)模型的階h(t)(t)gh(t)igh(t)例文：例文：the weight of .0階階1階階2階階3階階問題：半靜態(tài)模型和自適應(yīng)模型轉(zhuǎn)義碼的使用存儲空間問題LZ77算法字典模型：現(xiàn)代漢語詞典以及下面的例子LZ77算法LZ77算法的基本流程：“滑動的窗口”1、從當(dāng)前壓縮位置開始，考察未編碼的數(shù)據(jù)，并試圖在滑動窗口中找出最長的匹配字符串，如果找到，則進(jìn)行步驟 2，否則進(jìn)行步驟 3。2、輸出三元符號組(off,len,c)。其中off為窗口中匹配字符串相對窗口邊界的偏移，len為可匹配的長度，c為下一個字符。然后將窗口向后滑動len+1個字符，繼續(xù)步驟

21、1。3、輸出三元符號組(0,0,c)。其中c為下一個字符。然后將窗口向后滑動len+1個字符，繼續(xù)步驟 1。LZ77算法應(yīng)用實(shí)例：窗口大小為10個字符，剛編碼過的10個字符為“abcdbbccaa”，即將編碼的10個字符為 “abaeaaabaee”。我們首先發(fā)現(xiàn)，可以和待編碼字符匹配的最長串為ab(off=0,len=2), ab的下一個字符為a，我們輸出三元組：(0,2,a)現(xiàn)在窗口向后滑動3個字符，窗口中的內(nèi)容為：dbbccaaaba下一個字符e在窗口中沒有匹配，我們輸出三元組：(0,0,e)窗口向后滑動1個字符，其中內(nèi)容變?yōu)椋篵bccaaabae我們馬上發(fā)現(xiàn)，要編碼的aaabae在窗口

22、中存在(off=4,len=6)，其后的字符為e，我們可以輸出：(4,6,e)這樣，我們將可以匹配的字符串都變成了指向窗口內(nèi)的指針，并由此完成了對上述數(shù)據(jù)的壓縮。解壓縮時，只要我們向壓縮時那樣維護(hù)好滑動的窗口，隨著三元組的不斷輸入，我們在窗口中找到相應(yīng)的匹配串，綴上后繼字符c輸出如果off和len都為0則只輸出后繼字符c)即可還原出原始數(shù)據(jù)。LZ77算法三元組的編碼方法編碼方式取決于數(shù)據(jù)的分布概率）：對于第一個分量窗口內(nèi)的偏移，通常的經(jīng)驗(yàn)是，偏移接近窗口尾部的情況要多于接近窗口頭部的情況。但對于普通的窗口大小來說，這一差別可以忽略不計(jì)，我們用固定的位數(shù)來表示它：即編碼off需要的位數(shù)為uppe

23、r_bound(log2(MAX_WND_SIZE)對于第二個分量字符串長度，它的值在大多數(shù)時候不會太大，大字符串的匹配的發(fā)生概率很小。顯然可以使用一種變長的編碼方式來表示該長度值。我們已經(jīng)知道，要輸出變長的編碼，該編碼必須滿足前綴編碼的條件。其實(shí) Huffman 編碼也可以在此處使用，但卻不是最好的選擇。適用于此處的好的編碼方案很多，我們將在稍后介紹其中兩種應(yīng)用非常廣泛的編碼：Golomb編碼和編碼。對三元組的最后一個分量字符 c，因?yàn)槠浞植疾o規(guī)律可循，我們只能老老實(shí)實(shí)地用 8 個二進(jìn)制位對其編碼。假設(shè)對正整數(shù)x進(jìn)行Golomb編碼，選擇參數(shù)m，令b = 2mq = INT(x - 1)/

24、b)r = x - qb 1則x可以被編碼為兩部分，第一部分是由q個1加1個0組成，第二部分為m位二進(jìn)制數(shù)，其值為 r。值值 xm = 0m = 1m = 2m = 3100 00 000 0002100 10 010 001311010 00 100 0104111010 10 110 011511110110 010 000 1006111110110 110 010 101711111101110 010 100 1108111111101110 110 110 111911111111011110 0110 0010 000假設(shè)對x編碼，令q = int( log2x )則編碼的前一部

25、分是q個1加一個0，后一部分是q位長的二進(jìn)制數(shù)，其值等于(x-2q )值值 x編碼編碼10210 0310 14110 005110 016110 107110 1181110 00091110 001LZ77算法的其他問題其他的編碼方式：輸出匹配串時不輸出后續(xù)字符輸出0表示下面是一個匹配串，輸出1表示下面是一個單個字符對匹配串長度加以限制如何查找匹配串：限制匹配串的長度，在內(nèi)存中組織二叉有序樹將窗口中每個長度為3的字符串建立字典索引使用Hash表建立索引使用字符樹建立索引窗口滑動時內(nèi)存中的索引重建問題：建立環(huán)狀偏移以環(huán)狀偏移為基礎(chǔ)建立窗口索引內(nèi)存詞典：內(nèi)存詞典：第二步：壓縮串第二步：壓縮串“

26、AD .”在內(nèi)存詞典中仍無法找到匹配串，則輸出二元在內(nèi)存詞典中仍無法找到匹配串，則輸出二元組組(0，“A”)并將字串并將字串“A置入內(nèi)存詞典置入內(nèi)存詞典第一步：壓縮串第一步：壓縮串“DAD.”在內(nèi)存詞典中無法找到匹配串，則輸出二元組在內(nèi)存詞典中無法找到匹配串，則輸出二元組(0，“D”)二元組中第一個元素表示詞典的索引，第二個元素表示后續(xù)字符。二元組中第一個元素表示詞典的索引，第二個元素表示后續(xù)字符。并將字串并將字串“D置入內(nèi)存詞典置入內(nèi)存詞典內(nèi)存詞典：內(nèi)存詞典：LZW算法LZW算法是LZ78的改進(jìn)，其基本思路是在內(nèi)存中維護(hù)一個動態(tài)的字典，輸出的代碼是該字典的索引例：待壓縮的信息為例：待壓縮的信

27、息為 DAD DADA DADDY DADO. 索引索引0詞條詞條null索引索引01詞條詞條null“D”第三步：壓縮串第三步：壓縮串“D D.”在內(nèi)存詞典中可以找到最大匹配串在內(nèi)存詞典中可以找到最大匹配串“D”，輸出，輸出二元組二元組 (1，“ ”)以此對字串以此對字串“D ”進(jìn)行了編碼，然后將進(jìn)行了編碼，然后將“D ”置入內(nèi)存詞典置入內(nèi)存詞典內(nèi)存詞典：內(nèi)存詞典：內(nèi)存詞典：內(nèi)存詞典：第四步：壓縮串第四步：壓縮串“DAD.”在內(nèi)存詞典中可以找到最大匹配串在內(nèi)存詞典中可以找到最大匹配串“D”，則，則輸出輸出二元組二元組(1，“A”)以此對字串以此對字串“DA進(jìn)行了編碼，然后將進(jìn)行了編碼，然后將

28、“DA置入內(nèi)存詞典置入內(nèi)存詞典LZW算法例：待壓縮的信息為例：待壓縮的信息為 DAD DADA DADDY DADO. 索引索引012詞條詞條null“D”“A”索引索引0123詞條詞條null“D”“A”“D ”LZW算法例：待壓縮的信息為例：待壓縮的信息為 DAD DADA DADDY DADO. 第九步后，內(nèi)存詞典的情況如下：第九步后，內(nèi)存詞典的情況如下：索引索引01234詞條詞條null“D”“A”“D ”“DA”索引索引56789詞條詞條“DA ”“DAD”“DY”“ ”“DADO”每一步的輸出如下每一步輸出均為二元組）：每一步的輸出如下每一步輸出均為二元組）：步驟步驟12345輸出

29、輸出(0,”D”)(0,”A”)(1,” ”)(1,”A”)(4,” ”)步驟步驟6789輸出輸出(4,”D”)(1,”Y”)(0,” ”)(6,”O(jiān)”)JPEG圖像壓縮算法qJPEG 是有損壓縮算法qJPEG 核心是“離散余弦變換(Discrete Cosine Transform,DCT)”qJPEG 壓縮算法的基本步驟為：1、離散余弦變換DCT Transformation2、系數(shù)量化Coefficient Quantization 3、無損壓縮Lossless Compression一維波二維波離散余弦變換 DCTDCT操作X、Y、Z坐標(biāo)軸上的三維信號。X、Y坐標(biāo)軸是平面圖像的兩個維度，Z軸表示圖象的象素值。對NN的象素矩陣進(jìn)行DCT變換的公式如下：10102) 12(2) 12(),()()(21),(NxNyNjyCosNixCosyxPixeljCiCNjiDCT10102) 12(2) 12(),()()(21),(NiNjNjyCosNixCosjiDCTjCiCNyxPixel離散余弦變換(Discrete Cosine Transform,DCT)公式：反向離散余弦變換(Inverse Discrete Cosine Tra