第七章 圖像編碼與壓縮(2012)

1、電子科技大學(xué)電子科技大學(xué) 光電信息學(xué)院光電信息學(xué)院 二一二年二一二年4月月16日日彭真明彭真明E-mail: pengzm_主要內(nèi)容u編碼及信息論概述編碼及信息論概述u行程編碼行程編碼uLZW編碼編碼u霍夫曼編碼霍夫曼編碼u預(yù)測編碼預(yù)測編碼u變換編碼變換編碼u壓縮標(biāo)準(zhǔn)簡介壓縮標(biāo)準(zhǔn)簡介主要內(nèi)容u編碼及信息論概述編碼及信息論概述u行程編碼行程編碼uLZW編碼編碼u霍夫曼編碼霍夫曼編碼u預(yù)測編碼預(yù)測編碼u變換編碼變換編碼u壓縮標(biāo)準(zhǔn)簡介壓縮標(biāo)準(zhǔn)簡介 數(shù)字圖像通常要求很大的比特數(shù)，這給圖像的傳輸和存儲帶來一定的困難。要占用很多的資源，花很高的費用。 如一幅512x512的灰度圖像的比特數(shù)為： 512x5

2、12x8 = =。 再如一部90分鐘的彩色電影，每秒放映24幀。把它數(shù)字化，每幀512x512象素，每象素的 、 、三分量分別占8 bit，總比特數(shù)為：90602435125128bit=。一、編碼及信息論概述一、編碼及信息論概述1、圖像壓縮的必要性 如一張CD光盤可存600兆字節(jié)數(shù)據(jù)，這部電影圖像（不包括聲音）就需要張CD光盤用來存儲。 因此，對圖像數(shù)據(jù)進行壓縮顯得非常必要。 本章討論的問題：在滿足一定條件下，能否減小圖像bit數(shù)，以及用什么樣的編碼方法使之減少。一、編碼及信息論概述一、編碼及信息論概述編碼是用符號數(shù)碼元素表示信號、消息或事編碼是用符號數(shù)碼元素表示信號、消息或事件的過程。件的

3、過程。圖像編碼圖像編碼是研究圖像數(shù)據(jù)的編碼方法，期望用最少的碼字表示信源發(fā)出的圖像信號，使數(shù)據(jù)得到壓縮，減少圖像數(shù)據(jù)占用的信號空間和能量，降低信號處理的復(fù)雜程度。 這里的信號空間是指：物理空間存儲器、磁盤等數(shù)據(jù)存儲介質(zhì)；時間空間傳輸給定消息集合所需要的時間；頻譜空間傳輸給定消息集合所需要的帶寬。一、編碼及信息論概述一、編碼及信息論概述一種發(fā)型可以代表一種信息。 鼠標(biāo)指向圖像，按右鍵，選“播放”圖像編碼主要是研究信源編碼。圖像編碼主要是研究信源編碼。人類社會已全面進入信息時代，從而引起“信息爆炸”。數(shù)據(jù)壓縮特別是圖像信息數(shù)據(jù)壓縮，其社會效益和經(jīng)濟效益將越來越明顯，未來的圖像通訊、多媒體技術(shù)和目標(biāo)

4、識別等領(lǐng)域?qū)?shù)據(jù)處理速度、存儲容量都提出新了的要求，因此，圖像數(shù)據(jù)壓縮是必要的。因此，圖像數(shù)據(jù)壓縮是必要的。一、編碼及信息論概述一、編碼及信息論概述n圖像中像素灰度出現(xiàn)的不均勻性，造成圖像信息熵冗余，即用同樣長度比特表示每一個灰度，則必然存在冗余。n圖像能量在變換域內(nèi)分布的不均勻性，比如大部分能量集中在低頻部分，而小部分能量集中在高和較高的頻率部分。n圖像像素灰度在時間和空間上的相關(guān)性造成信息冗余。2、圖像壓縮的可能性 一、編碼及信息論概述一、編碼及信息論概述n數(shù)據(jù)冗余包括：空間冗余，鄰近像素灰度分布的相關(guān)性很強；頻間冗余，多譜段圖像中各譜段圖像對應(yīng)像素之間灰度相關(guān)性很強；時間冗余，序列圖像幀

5、間畫面對應(yīng)像素灰度的相關(guān)性很強。一、編碼及信息論概述一、編碼及信息論概述如果用8 bit表示下面圖像的像素，我們就說該圖像存在著編碼冗余，因為該圖像的像素只有兩個灰度，用1 bit即可表示。例析例析1 1： 由于任何給定的像素值，原理上都可以通過它的鄰居預(yù)測到，單個像素攜帶的信息相對是小的。 對于一個圖像，很多單個像素對視覺的貢獻是冗余的。這是建立在對鄰居值預(yù)測的基礎(chǔ)上。如：原圖像數(shù)據(jù)：250 253 251 252 250 40bit。壓縮后數(shù)據(jù)：250 3 1 2 0 14bit。例析例析2 2： 應(yīng)用環(huán)境允許圖像有一定程度失真(1)接收端圖像設(shè)備分辨率較低，則可降低圖像分辨率；(2)根據(jù)

6、人的視覺特性對不敏感區(qū)進行降分辨率編碼（視覺冗余）；(3)應(yīng)用方關(guān)心圖像區(qū)域有限，可對其余部分圖像可采用空間和灰級上的粗化；(4)對于識別，圖像特征抽取和描述也是數(shù)據(jù)壓縮。一、編碼及信息論概述一、編碼及信息論概述33K15K例析例析1 1： 視覺心理冗余視覺心理冗余： 一些信息在一般視覺處理中比其它信息的相對重要程度一些信息在一般視覺處理中比其它信息的相對重要程度要小，這種信息就被稱為要小，這種信息就被稱為視覺心理冗余視覺心理冗余。圖像編碼方法有許多，但從信息是否失真角度來看，可以分作兩大類：無失真編碼（無損壓縮、可逆壓縮）是一種經(jīng)編、解碼后圖像不會產(chǎn)生失真的編碼方法?？芍亟▓D像，但壓縮比不大

7、；有失真編碼（有損壓縮、不可逆壓縮）解碼時無法完全恢復(fù)原始圖像，壓縮比大但有信息損失。失真失真是指編碼輸入圖像與解碼輸出圖像之間的隨機誤差；壓縮比壓縮比指原圖像比特數(shù)與壓縮后圖像比特數(shù)之比。3、圖像編碼分類一、編碼及信息論概述一、編碼及信息論概述變換編碼變換編碼統(tǒng)計編碼統(tǒng)計編碼預(yù)測編碼預(yù)測編碼圖像壓縮方法圖像壓縮方法有損壓縮有損壓縮行程編碼行程編碼編碼編碼哈夫曼編碼哈夫曼編碼算術(shù)編碼算術(shù)編碼其他其他無損預(yù)測無損預(yù)測有損預(yù)測有損預(yù)測其他其他編碼編碼變換變換其他其他無損壓縮無損壓縮一、編碼及信息論概述一、編碼及信息論概述 傳統(tǒng)的圖像編碼方法有傳統(tǒng)的圖像編碼方法有脈碼調(diào)制、量化算法、空間脈碼調(diào)制、量

8、化算法、空間和時間亞采樣編碼、熵編碼、預(yù)測編碼、變換編碼、矢和時間亞采樣編碼、熵編碼、預(yù)測編碼、變換編碼、矢量量化和子帶編碼等。量量化和子帶編碼等。新型編碼技術(shù)包括第二代圖像編碼方法、新型編碼技術(shù)包括第二代圖像編碼方法、分形編碼、分形編碼、基于模型的編碼和小波變換編碼等?；谀Ｐ偷木幋a和小波變換編碼等?？傊?，圖像編碼是從不同角度消除圖像數(shù)據(jù)中的冗總之，圖像編碼是從不同角度消除圖像數(shù)據(jù)中的冗余，減少表示圖像所需的比特數(shù)，或平均比特數(shù)，實現(xiàn)余，減少表示圖像所需的比特數(shù)，或平均比特數(shù)，實現(xiàn)數(shù)據(jù)壓縮。數(shù)據(jù)壓縮。一、編碼及信息論概述一、編碼及信息論概述信息量：從N個相等可能發(fā)生的事件中，選出其中一個事件

9、所需的信息度量，稱為信息量。4、信息量和熵一、編碼及信息論概述一、編碼及信息論概述要辨識1到32中選定的某一個數(shù)，可先提問：“是否大于16？”，得到回答就消去半數(shù)可能事件。每提問一次得到回答，可以得到1bit信息量（二進制位）。這里共需5次，因此所需的信息量為：532log2例析例析2 2： 在數(shù)學(xué)上，信源是一概率場 ，若信源可能產(chǎn)生的信息是 ，這些信息出現(xiàn)的概率分別是 ，則該信源可表示為：nsss,21)(,),(),(21nspspsp)(,),(,),(,2211nnspsspssps一、編碼及信息論概述一、編碼及信息論概述信源的定義：信源指能夠產(chǎn)生信息的事物。信源指能夠產(chǎn)生信息的事物。

10、信息量：從N個數(shù)選定一個數(shù)s的概率為p(s)，且等概率，p(s)=1/N。熵：設(shè)信源符號表為 s=s1, s2, , sq，其概率分布為P(s)=p(s1), p(s2), , p(sq)，則信源的熵為：)()(log1loglog)(222spIspNNsI 211logqqiiiiiiHp sp sp sIp s s一、編碼及信息論概述一、編碼及信息論概述 217log4kiiiHsp sp s 814813412211,ssssS 編碼應(yīng)用中，熵表示信源中消息的平均信息量平均信息量。在不考慮消息間的相關(guān)性時，是無失真代碼平均長度比特數(shù)的下限。例：信源 說明該信源編碼平均碼長最短情況下為7

11、/4，不能再小，否則就會引起錯誤。而平均碼長比此數(shù)大許多時，就表明還有待改進。一、編碼及信息論概述一、編碼及信息論概述熵的性質(zhì)：(1) 熵是一個非負(fù)數(shù)，即總有H(s)0。 (2) 當(dāng)其中一個符號sj的出現(xiàn)概率p(sj)=1時，其余符號si(ij)的出現(xiàn)概率p(si) =0，H(s)=0。 (3) 當(dāng)各個si出現(xiàn)的概率相同時，則最大平均信息量為log2 q。 (4) 熵值總有H(s) log2 q。4、信息量和熵一、編碼及信息論概述一、編碼及信息論概述(1) s作為灰度，共q級，出現(xiàn)概率均等時，p(si)=1/q，(2)當(dāng)灰度只有兩級時，即si = 0, 1，且0出現(xiàn)概率為p1，1出現(xiàn)概率為p2

12、=1- p1 ，其熵： 22111loglogqiH sqqq 12121111log1log1H sppppn圖像的熵一、編碼及信息論概述一、編碼及信息論概述(3)對位圖像，對位圖像，s作為灰度，共256級，其熵為：(4)當(dāng)圖像由單一灰度級組成時（即灰度均勻分布圖像）, 其熵為： 25520logiHp ip i s 25520log0iHp ip i sn圖像的熵一、編碼及信息論概述一、編碼及信息論概述編碼器是用符號集中的符號構(gòu)成輸出代碼，并建立輸入信號單元與輸出代碼的對應(yīng)關(guān)系。如下圖所示：5、信息編碼過程),(21msssSmwwwW,21naaaA,21消息集合消息集合輸出代碼輸出代碼

13、符號集符號集 符號符號(碼元碼元)編碼器編碼器一、編碼及信息論概述一、編碼及信息論概述 可以證明，在無干擾的條件下，存在一種無失真的編碼方法，使編碼的平均長度 L 與 信 源 的 熵 H ( s ) 任 意 地 接 近 ， 即 L=H(s)+其中為任意小的正數(shù)，但以H(s)為其下限，即LH(s)，這就是。6、無失真編碼定理一、編碼及信息論概述一、編碼及信息論概述定義為：( )11H sRL 冗余度接近于0，或編碼效率接近于1的編碼稱為。(1)、編碼效率一、編碼及信息論概述一、編碼及信息論概述 若原始圖像的平均比特率為n，編碼后的平均比特率為nd，則壓縮比壓縮比C定義為：dnCn 由Shanno

14、n定理，無失真編碼最大可能最大可能的數(shù)據(jù)壓縮比的數(shù)據(jù)壓縮比為：)()(sHnsHnCM(2) 壓縮比一、編碼及信息論概述一、編碼及信息論概述 對于無失真圖像的編碼，原始圖像數(shù)據(jù)的壓縮存在一個下限，即平均碼組長度不能小于原始圖像的熵，而理論上的最佳編碼的平均碼長無限接近原始圖像的熵。 原始圖像冗余度定義為：1)(1sHLR原始圖像的熵原始圖像平均碼長7、熵與相關(guān)性、冗余度的關(guān)系一、編碼及信息論概述一、編碼及信息論概述主要內(nèi)容u編碼及信息論概述編碼及信息論概述u行程編碼行程編碼uLZW編碼編碼u霍夫曼編碼霍夫曼編碼u預(yù)測編碼預(yù)測編碼u變換編碼變換編碼u壓縮標(biāo)準(zhǔn)簡介壓縮標(biāo)準(zhǔn)簡介統(tǒng)計編碼統(tǒng)計編碼1、概

15、念： 行程：具有相同灰度值的像素序列。2、編碼思想： 去除像素冗余。即用行程的灰度和行程的長度代替行程本身。二、行程編碼二、行程編碼(Run Length Encoding)(Run Length Encoding)例：設(shè)重復(fù)次數(shù)為 iC, 重復(fù)像素值為 iP，則 編碼為：iCiP iCiP iCiP 編碼前：aaaaaaabbbbbbcccccccc 編碼后：7a6b8c二、行程編碼二、行程編碼二、行程編碼二、行程編碼n分析p 對于有大面積色塊的圖像，壓縮效果很好；p 對于紛雜的圖像，壓縮效果不好，最壞情況下，會加倍圖像。主要內(nèi)容u編碼及信息論概述編碼及信息論概述u行程編碼行程編碼uLZW編

16、碼編碼u霍夫曼編碼霍夫曼編碼u預(yù)測編碼預(yù)測編碼u變換編碼變換編碼u壓縮標(biāo)準(zhǔn)簡介壓縮標(biāo)準(zhǔn)簡介 1985年,美國人Welch將LZ壓縮技術(shù)從概念發(fā)展到實用階段,簡稱LZW壓縮技術(shù)。廣泛用于圖象壓縮領(lǐng)域。 LZW（Lempel-Ziv & Welch）編碼又稱字串表編碼字串表編碼，屬于一種無損編碼。LZW編碼與行程編碼類似，也是對字符串進行編碼從而實現(xiàn)壓縮，但它在編碼的同時還生成了特定字符串以及與之對應(yīng)的索引字符串表。 三、三、LZWLZW編碼編碼 1977年,以色列人Lempel和Ziv共同提出了查找冗余字符和用較短的符號標(biāo)記替代冗余字符的概念，簡稱LZ壓縮技術(shù)。 1、簡介三、三、LZWL

17、ZW編碼編碼(1) 在壓縮過程中動態(tài)地形成一個字符序列表(字典)。(2) (a)每當(dāng)壓縮掃描圖像發(fā)現(xiàn)一個字典中沒有的字符序列，就把該字符序列存到字典中； (b)并用字典的地址（編碼）作為這個字符序列的代碼，替換原圖像中的字符序列； (c)下次再碰到相同的字符序列，就用字典的地址代替字符序列。2、基本思想 去除像素冗余。三、三、LZWLZW編碼編碼(3) 壓縮的結(jié)果，除了壓縮圖像外，不需要保留壓縮過程中形成的字典；而在解壓縮時，臨時恢復(fù)這個字典。問題：問題： 字符序列的長度如何確定？ 字典的長度如何確定？ 字典滿了怎么辦？ 如何查字典？三、三、LZWLZW編碼編碼(1) 字典中字符序列的長度：

18、其長度可能會很長。由于每一個字符串，都是表中一個已經(jīng)存在的字符串加上一個字符組成。所以，可以把字符串以: + 這樣字典元素的長度統(tǒng)一為12+8，20位。(2) 字典的長度： 對于以字節(jié)（8位）為壓縮單元，如ASCII碼，字典的長度為212 = 4096，索引的長度為12位。字典的前256個保存單個字符，剩下的3840個的分配給壓縮過程中出現(xiàn)的字符串。三、三、LZWLZW編碼編碼(3)字典滿了的解決辦法： 在字典滿了以后（新字符串超過4096），輸出一個清除字典的標(biāo)記 LZW_CLEAR，清空字典，開始新的編碼。(4)查表的方法： 可通過Hashing函數(shù)（散列、雜湊）的方法來減少查表的次數(shù)。(

19、5)輸出編碼的時機： 發(fā)現(xiàn)新串時，輸出前一個串的編碼。F步驟步驟1：將詞典初始化為包含所有可能的單字將詞典初始化為包含所有可能的單字F步驟步驟2：當(dāng)前字符當(dāng)前字符C:=C:=字符流中的下一個字符。字符流中的下一個字符。字符，當(dāng)前前綴字符，當(dāng)前前綴P P初始化為空初始化為空( (NULL) )。3、基本步驟三、三、LZWLZW編碼編碼令令P:=CP:=C，現(xiàn)在的現(xiàn)在的P P僅包含僅包含一個字符一個字符C CF步驟步驟3 3：判斷判斷P PC C是否在詞典中是否在詞典中? ?（1 1）如果）如果“是是”，則用，則用C C擴展擴展P P，即讓即讓P:=PP:=PC C（2 2）如果）如果“否否”，則

20、，則輸出與當(dāng)前前綴輸出與當(dāng)前前綴P P相對應(yīng)的碼字；相對應(yīng)的碼字；將將P PC C添加到詞典中；添加到詞典中；三、三、LZWLZW編碼編碼F步驟步驟4 4：判斷碼字流中是否還有碼字要譯判斷碼字流中是否還有碼字要譯? ?（1 1）如果）如果“是是”，就返回到步驟，就返回到步驟2 2；（2 2）如果）如果“否否”把代表當(dāng)前前綴把代表當(dāng)前前綴P P的碼字輸出到碼字流；的碼字輸出到碼字流；結(jié)束。結(jié)束。三、三、LZWLZW編碼編碼初始化字符串表 字符串 索引(16進制) a 0 H b1 H c2 H d3 H LZW_CLEAR（初始化標(biāo)記） 4 H LZW_EOI （結(jié)束標(biāo)記） 5 H LZWLZW

21、編碼例析編碼例析例如：對例如：對“aabcabbbbd”進行編碼進行編碼輸入數(shù)據(jù)輸入數(shù)據(jù)S2S2S1+S2S1+S2輸出結(jié)果輸出結(jié)果S1S1生成的新字符串及索引生成的新字符串及索引NULLNULLa aa ab bc ca ab bb bb bb bd dNULLNULLNULLNULLa aa aa aaaaa4H4H0H0H0H0Hababbcbccacaabababbabbbbbbbbbbbbdbbd1H1H2H2H7H7H1H1HBHBH3H3H5H5Hb bc ca aababb bb bbbbbd daaaa abab bcbc ca ca abbabb bb bb bbd bbd

22、 S1為NULL,故輸出結(jié)果為空S1+S2在字符表中,S1=S1+S2aa不存在,故輸出S1=“a”的索引0HS1+S2不在字符表中,S1=S2=“a”ab不存在,故輸出S1=“a”的索引0HS1+S2不在字符表中,S1=S2=“b”S1+S2結(jié)果已存在,故輸出結(jié)果為空S1+S2在字符表中,S1=S1+S2輸入結(jié)束輸出S1的索引3H輸出LZW_EOI標(biāo)志的索引LZW編碼例析：“aabcabbbbd”主要內(nèi)容u編碼及信息論概述編碼及信息論概述u行程編碼行程編碼uLZW編碼編碼u霍夫曼編碼霍夫曼編碼u預(yù)測編碼預(yù)測編碼u變換編碼變換編碼u壓縮標(biāo)準(zhǔn)簡介壓縮標(biāo)準(zhǔn)簡介 霍夫曼(Huffman)編碼是可變字

23、長編碼(Variable length coding，VLC)的一種。 Huffman于1952年提出的一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長 度最短的碼字，常被稱作Huffman編碼，有時稱之為最佳編碼， 1、簡介四、霍夫曼四、霍夫曼(Huffman)(Huffman)編碼編碼四、霍夫曼四、霍夫曼(Huffman)(Huffman)編碼編碼2、基本思想通過減少編碼冗余來達(dá)到數(shù)據(jù)壓縮的目的。a) 基本思想是統(tǒng)計各個符號出現(xiàn)的概率。b) 建立一個概率統(tǒng)計表。 將最常出現(xiàn)(概率大的)的符號用最短的編碼；最少出現(xiàn)的符號用最長的編碼。例如：例如：信號源 s=s1, s2, s3,

24、 s4, s5, s6，其概率分布為p1=0.4, p2=0.3, p3=0.1, p4=0.1, p5=0.06, p6=0.04，求最佳Huffman碼。步驟如下： 將信源符號按出現(xiàn)概率從大到小排成一列，然后把最末兩個符號的概率相加，合成一個概率。四、霍夫曼四、霍夫曼(Huffman)(Huffman)編碼編碼 把這個符號的概率與其余符號的概率按從大到小排列，然后再把最末兩個符號的概率加起來，合成一個概率。 重復(fù)上述做法，直到最后剩下兩個概率為止。 從最后一步剩下的兩個概率開始逐步向前進行編碼。每步只需對兩個分支各賦予一個二進制碼，如對概率大的賦予碼元0，對概率小的賦予碼元1。四、霍夫曼四

25、、霍夫曼(Huffman)(Huffman)編碼編碼輸入S1S2S3S4S5S6輸入概率0.10.060.04HuffmanHuffman編碼例析編碼例析輸入S1S2S3S4S5S6輸入概率0.10.060.04第一步0.10.1HuffmanHuffman編碼例析編碼例析輸入S1S2S3S4S5S6輸入概率0.10.060.04第一步0.10.1第二步0.1HuffmanHuffman編碼例析編碼例析輸入S1S2S3S4S5S6概率0.10.060.04第1步0.40

26、.第2步0.1第3步HuffmanHuffman編碼例析編碼例析輸入S1S2S3S4S5S6概率0.10.060.04第1步0.10.1第2步0.1第3步第4步0.60.4HuffmanHuffman編碼例析編碼例析輸入S1S2S3S4S5S6概率0.10.060.04第1步0.10.1第2步0.1第3步第4步0.60.40101010101HuffmanHuffman編碼例析編碼例析輸入S1S2

27、S3S4S5S6概率0.10.060.04第1步0.10.1第2步0.1第3步第4步0.60.40101010101S1=1HuffmanHuffman編碼例析編碼例析輸入S1S2S3S4S5S6概率0.10.060.04第1步0.10.1第2步0.1第3步第4步0.60.40101010101S2=00HuffmanHuffman編碼例析編碼例析輸入S1S2S3S4S5S6概率0.10.060.04第1步0.10.

28、1第2步0.1第3步第4步0.60.40101010101S3=011HuffmanHuffman編碼例析編碼例析輸入S1S2S3S4S5S6概率0.10.060.04第1步0.10.1第2步0.1第3步第4步0.60.40101010101S4=0100HuffmanHuffman編碼例析編碼例析輸入S1S2S3S4S5S6概率0.10.060.04第1步0.10.1第2步0.1第3步第4步0.60.4010101

29、0101S5=01010HuffmanHuffman編碼例析編碼例析輸入S1S2S3S4S5S6概率0.10.060.04第1步0.10.1第2步0.1第3步第4步0.60.40101010101S6=01011HuffmanHuffman編碼例析編碼例析下面是一首英文歌曲：Because Im bad, I am badcome onBad, badreally, really badYou know Im bad, Im badBad, badreally, really badYou know Im bad, Im

30、badcome on, you knowBad, bad-really, really badHuffmanHuffman編碼樹結(jié)構(gòu)編碼樹結(jié)構(gòu)短語符號頻率概率BecauseB10.03ImI60.17BadB150.43Come onC20.06ItI10.03ReallyR60.17You knowY40.11HuffmanHuffman編碼樹結(jié)構(gòu)編碼樹結(jié)構(gòu)S6S5S3S2S1B 0.43(Bad)10(1.00)S40100I 0.17(Im)R 0.17(Really)Y 0.11(You know)C 0.06(Come on)B 0.03(Because)I 0.03(It)0000

31、01011010000000010000000001(0.57)(0.23)(0.12)(0.06)(0.34)HuffmanHuffman編碼樹結(jié)構(gòu)編碼樹結(jié)構(gòu)短語符號頻率概率代碼長度編碼BecauseB10.03500001ImI60.173011BadB150.4311Come onC20.0640001ItI10.03500000ReallyR60.173010You knowY40.113001HuffmanHuffman編碼樹結(jié)構(gòu)編碼樹結(jié)構(gòu)平均碼長：平均碼長：R=0.03x5+0.17x3+0.43x1+0.06x4+0.03x5+0.17x3+0.11x3=2.32熵：熵：H=-(

32、0.03xlog0.03+0.17xlog0.17+0.43xlong0.43+0.06xlog0.06+0.03xlog0.03+0.17xlog0.17+0.11xlog0.11)=2.29編碼前：35xlog27=98.3, 編碼后：81位，壓縮比：約20。HuffmanHuffman編碼樹結(jié)構(gòu)編碼樹結(jié)構(gòu)主要內(nèi)容u編碼及信息論概述編碼及信息論概述u行程編碼行程編碼uLZW編碼編碼u霍夫曼編碼霍夫曼編碼u預(yù)測編碼預(yù)測編碼u變換編碼變換編碼u壓縮標(biāo)準(zhǔn)簡介壓縮標(biāo)準(zhǔn)簡介n預(yù)測編碼是屬于時間域 (Time domain)的編碼方法。n基本概念是利用前面已經(jīng)出現(xiàn)過的符號來預(yù)測當(dāng)前的符號，然后將實際上

33、的符號與預(yù)測相減得到預(yù)測誤差值。n利用預(yù)測編碼的好處在于預(yù)測誤差值的范圍比原信號的數(shù)字范圍小，如果預(yù)測足夠精確的話。n通常會對預(yù)測誤差值進一步編碼（quantization）。n可分為有損和無損預(yù)測，但預(yù)測本身不會造成失真。五、預(yù)測編碼五、預(yù)測編碼五、預(yù)測編碼五、預(yù)測編碼1、無損預(yù)測編碼(Lossless Predictive Coding)(1)基本思想基本思想p 去除像素冗余。p 認(rèn)為相鄰像素的信息有冗余。當(dāng)前像素值可以用先前的像素值來獲得。p 用當(dāng)前像素值fn，通過預(yù)測器得到一個預(yù)測值 ，對當(dāng)前值和預(yù)測值求差。對差編碼，作為壓縮數(shù)據(jù)流中的下一個元素。nf五、預(yù)測編碼五、預(yù)測編碼10010

34、21011001001011001021021001001031001021011001001001021001011011001001001002-1-101-120-2-13-32-10002-210-100n 例：利用前一個像素預(yù)測1mnin iifroundf1( , )( ,)mniifx yroundf x yi五、預(yù)測編碼五、預(yù)測編碼n 一般情況下，利用前m個像素的線性組合來預(yù)測，即因此，在一維線性(行預(yù)測)預(yù)測編碼中，預(yù)測器為：其中，round為取最近整數(shù)，i為預(yù)測系數(shù)(可為1/m)，y是行變量。注意：前m個像素不能用此法編碼，可用哈夫曼編碼。154,159,151,149,1

35、39,121,112,109,1292,1 2Fm取例析例析預(yù)測值：預(yù)測值：2 1/2 (154 159) 156,2 151 156 -53 1/2 (159 151) 155, 3 149 155 -64 1/2 (151 149) 150, 4 139 150 -115 1/2 (149 139) 144, 5 121 144 -236 1/2 (fefefefef 139 121) 130, 6 112 130 -187 1/2 (121 112) 116, 7 109 116 -78 1/2 (112 109) 110 ,8 129 110 19efefe五、預(yù)測編碼五、預(yù)測編碼(2

36、) 編碼步驟 第步：壓縮頭處理。 第步：預(yù)測值。 第步：求預(yù)測誤差值。 第步：對誤差e(x,y)編碼，作為壓縮值。重復(fù) 、 、 步,e x yf x yf x y預(yù)測器預(yù)測器最接近最接近的整數(shù)的整數(shù)+ -符號符號編碼編碼壓縮圖像輸入圖像enfn fn五、預(yù)測編碼五、預(yù)測編碼(3) 編碼原理圖p 基本概念p 量化器p 編碼原理五、預(yù)測編碼五、預(yù)測編碼2、有損預(yù)測編碼(Lossy Predictive Coding)（1）有損壓縮的基本概念n有損壓縮是：n通過犧牲圖像的準(zhǔn)確率來達(dá)到增大壓縮率的目的。通過犧牲圖像的準(zhǔn)確率來達(dá)到增大壓縮率的目的。n如果容忍解壓后的結(jié)果中有一定的誤差，那么壓縮率可以顯著

37、提如果容忍解壓后的結(jié)果中有一定的誤差，那么壓縮率可以顯著提高。高。n有損壓縮方法的壓縮比：n在圖像壓縮比大于在圖像壓縮比大于30:130:1時，仍然能夠重構(gòu)圖像。時，仍然能夠重構(gòu)圖像。n在圖像壓縮比為在圖像壓縮比為10:110:1到到20:120:1時，重構(gòu)圖像與原圖幾乎沒有差別。時，重構(gòu)圖像與原圖幾乎沒有差別。n無損壓縮的壓縮比很少有能超過無損壓縮的壓縮比很少有能超過3:1的的（Why ?）。n有損與無損壓縮的根本差別在于有沒有量化器模塊有沒有量化器模塊。五、預(yù)測編碼五、預(yù)測編碼數(shù)據(jù)源編、解碼的一般模型n編碼模型編碼模型n解碼模型解碼模型符號符號解碼器解碼器反向反向映射器映射器映射器映射器量

38、化器量化器編碼器編碼器五、預(yù)測編碼五、預(yù)測編碼(2) 量化器：n減少數(shù)據(jù)量的最簡單的辦法是將圖像量化成較少的灰減少數(shù)據(jù)量的最簡單的辦法是將圖像量化成較少的灰度級，通過減少圖像的灰度級來實現(xiàn)圖像的壓縮；度級，通過減少圖像的灰度級來實現(xiàn)圖像的壓縮；n這種量化是不可逆的，因而解碼時圖像有損失。這種量化是不可逆的，因而解碼時圖像有損失。例如： 如果輸入是如果輸入是256256個灰度級，對灰度級量化后輸個灰度級，對灰度級量化后輸出，只剩下出，只剩下4 4個層次，數(shù)據(jù)量被大大減少個層次，數(shù)據(jù)量被大大減少。五、預(yù)測編碼五、預(yù)測編碼n量化器的定義n階梯形量化函數(shù)階梯形量化函數(shù)t=t=q(sq(s) )，是一個

39、是一個s s的奇函數(shù)（即的奇函數(shù)（即q(-s) q(-s) =-q(s)=-q(s)），），它可以通過它可以通過L/2L/2、s si i和和t ti i來完全描述，從來完全描述，從而定義了一個量化器。而定義了一個量化器。ns si i 被稱為量化器的被稱為量化器的決策級決策級（閾值）；（閾值）； t ti i 被稱為量化器的被稱為量化器的重構(gòu)級重構(gòu)級（代表級）。（代表級）。 L L：是量化器的級數(shù)。是量化器的級數(shù)。n由于習(xí)慣的原因，由于習(xí)慣的原因，s si i被認(rèn)為是映射到被認(rèn)為是映射到t ti i，如果它在半如果它在半開區(qū)間開區(qū)間(s(si i,s,si+1i+1 。五、預(yù)測編碼五、預(yù)測編

40、碼n量化器的定義inputs1s2S(L/2)-1outputstt1t2t(L/2)-t(L/2)S-(L/2)-1t = q(s)決策級決策級( (閾值閾值) )注：量化的對象可能是負(fù)數(shù)五、預(yù)測編碼五、預(yù)測編碼(3)無損到有損算法演變基本思想：基本思想：對無損預(yù)測壓縮的誤差進行量化，通過消除視覺心理冗余，達(dá)到對圖像進一步壓縮的目的。 引入量化引入量化(Quantification)五、預(yù)測編碼五、預(yù)測編碼nnnfef )(nneQe nnff)(nnnffQennnfef 五、預(yù)測編碼五、預(yù)測編碼 將en量化： 用： 近似 編碼： 解碼：n編、解碼原理及過程 n編碼流程圖： n = Q(

41、fn - fn)+ -壓縮圖像輸入圖像enfn fnn五、預(yù)測編碼五、預(yù)測編碼壓縮圖像 n解碼流程圖： fn = n + fn+ +解壓圖像 fn fnn五、預(yù)測編碼五、預(yù)測編碼預(yù)測器預(yù)測器預(yù)測器預(yù)測器編碼編碼fn解碼解碼fn五、預(yù)測編碼五、預(yù)測編碼注意：上述方案的壓縮編碼中，預(yù)測器的輸入是fn，而解壓中的預(yù)測器的輸入是fn ，要使用相同的預(yù)測器，編碼方案要進行修改。n修改后的有損預(yù)測編碼 n = Q( fn - fn)壓縮圖像+ -en輸入圖像fnn fn+ + fn fn = n + fn五、預(yù)測編碼五、預(yù)測編碼差分脈沖編碼調(diào)制(Differential Pulse Code Modula

42、tion, DPCM)，采用反饋方法預(yù)測估值。1950年，卡特勒申請專利;1952年，獲得批準(zhǔn);1958年，格雷厄姆（Graham)開始計算機模擬研究編碼方法；1966年，奧尼爾（ONeal)對電視信號預(yù)測編碼進行理論分析以及計算機模擬；1971年投入使用。五、預(yù)測編碼五、預(yù)測編碼量化器編碼器解碼器預(yù)測器預(yù)測器nx nxne五、預(yù)測編碼五、預(yù)測編碼n編碼原理圖,0,1nnneeelsee 是一個正常數(shù)用 位編碼1nnff五、預(yù)測編碼五、預(yù)測編碼n量化器：n預(yù)測器： 一般是一個小于1的預(yù)測系數(shù)。例如：量化器設(shè)： = 6.5+6.5-6.5ee有損預(yù)測編碼有損預(yù)測編碼DPCMDPCMn舉例： =

43、1， = 6.5 計算：兩個像素 f0 =14、f1 =15，則：000,14nff有損預(yù)測編碼有損預(yù)測編碼DPCMDPCM101,1 14nff 115 141e 編碼:116.50ee 1116.5 1420.5fef解碼：111520.55.5ff (預(yù)測結(jié)果預(yù)測結(jié)果)(預(yù)測誤差預(yù)測誤差)(預(yù)測誤差預(yù)測誤差)(重構(gòu)結(jié)果重構(gòu)結(jié)果)(重構(gòu)誤差重構(gòu)誤差) 輸入 編碼 解碼 誤差n f f e e f f f f-f0 14 - - - 14.0 - 14.0 0.01 15 14.0 1.0 6.5 20.5 14.0 20.5 -5.52 14 20.5 -6.5 -6.5 14.0 20.

44、5 14.0 0.03 15 14.0 1.0 6.5 20.5 14.0 20.5 -5.5 . . . . . . . . 14 29 20.5 8.5 6.5 27.0 20.5 27.0 2.015 37 27.0 10.0 6.5 33.5 27.0 33.5 3.516 47 33.5 13.5 6.5 40.0 33.5 40.0 7.017 62 40.0 22.0 6.5 46.5 40.0 46.5 15.5有損預(yù)測編碼有損預(yù)測編碼DPCMDPCM3、預(yù)測器的一般模型、預(yù)測器的一般模型),(11nmnmnnxxxfx可以是固定的，也可以是自適應(yīng)的；可以是線性的，也可以是非線

45、性的。 預(yù)測器設(shè)計得越好，對輸入的數(shù)據(jù)壓縮就越多。五、預(yù)測編碼五、預(yù)測編碼預(yù)測的階數(shù)。預(yù)測系數(shù)，其中，性預(yù)測，的線性組合，則稱為線是若maknxanxnxnxneknxanxxxxxkmkkmkknmnmnn1111)()()( )()()()( ,預(yù)測器模型預(yù)測器模型 選ak使2d(n)最小。 設(shè)x(n)是廣義平穩(wěn)的，且e(n)均值為0，則222( )12( )1( ) ( )() 0( )()01(3 1)me nkke nimkkE e nEx na x nkaR ia R kiim 令可得：預(yù)測器模型預(yù)測器模型 假設(shè)x(n)是各態(tài)遍歷的，且訓(xùn)練樣本數(shù)N相當(dāng)大，則x(n)的自相關(guān)函數(shù)Nn

46、knxnxNkRkR1)()(1)()( 把(3-1)式寫成矩陣形式：)()2() 1 ()0()2() 1()2()0() 1 () 1() 1 ()0(21mRRRaaaRmRmRmRRRmRRRm預(yù)測器模型預(yù)測器模型若x(n)是非平穩(wěn)的，或是分段近似廣義平穩(wěn)，則可采用邊送數(shù)據(jù)邊測量與估計x(n)的自相關(guān)函數(shù)，求出相應(yīng)的最佳預(yù)測系數(shù)。隨之，相應(yīng)的最佳預(yù)測系數(shù)隨著x(n)的統(tǒng)計特性的變化而變化，這就是自適應(yīng)線性預(yù)測。預(yù)測器模型預(yù)測器模型原始圖象用f (m,n)表示： 預(yù)測的差值定義為：這里Z為對象素f (m,n)進行預(yù)測的相關(guān)點的集合。Zlklklnkmfanmf),(,),(),(),()

47、,(),(nmfnmfnme預(yù)測器模型預(yù)測器模型 方程的解 a1, a2, , am 便是 一組最佳的預(yù)測系數(shù)。壓縮效果可用方差2e(n)來衡量， 原始序列相關(guān)性越強， R(k)越大，2e(n)越小，壓縮效果越顯著；原始序列互不相關(guān)，即R(k) =0，k0，則，2e(n)= 2x(n)一點也不能壓縮。mkknxnekRa12)(2)()(預(yù)測器模型預(yù)測器模型主要內(nèi)容u編碼及信息論概述編碼及信息論概述u行程編碼行程編碼uLZW編碼編碼u霍夫曼編碼霍夫曼編碼u預(yù)測編碼預(yù)測編碼u變換編碼變換編碼u壓縮標(biāo)準(zhǔn)簡介壓縮標(biāo)準(zhǔn)簡介六、變換編碼六、變換編碼p 用一個可逆的、線性的變換用一個可逆的、線性的變換(如

48、如FFT、DFT)，把圖像，把圖像映射到變換系數(shù)集合映射到變換系數(shù)集合;p 然后對該系數(shù)集合進行量化和編碼然后對該系數(shù)集合進行量化和編碼;p 對于大多數(shù)自然圖像，對于大多數(shù)自然圖像，重要系數(shù)的數(shù)量是比較少的重要系數(shù)的數(shù)量是比較少的，因而可以用量化因而可以用量化(或完全拋棄或完全拋棄)，且僅以較小的圖像失，且僅以較小的圖像失真為代價。真為代價。52 55 61 66 70 61 64 7363 59 66 90 109 85 69 7262 59 68 113 144 104 66 7363 58 71 122 154 106 70 6967 61 68 104 126 88 68 7079 6

49、5 60 70 77 68 58 7585 71 64 59 55 61 65 8387 79 69 68 65 76 78 94六、變換編碼六、變換編碼610 -29 -612655 -19 037-20-61912-6-67-46877-25 -29117-4-481235-14-972211-7-12-202-42924301202121132210020001原圖像原圖像DCT變換系數(shù)變換系數(shù)正變換量化器符號編碼器構(gòu)造nn的子圖合成nn的子圖輸入圖像NN壓縮圖像壓縮圖像解壓圖像六、變換編碼六、變換編碼n構(gòu)造nn的子圖Nnnnnnnnnnnnn六、變換編碼六、變換編碼N1100,exp2

50、 ()/NNuvf x yF u vjuxvyN1010),(),(),(NuNvvuyxHvuTyxf六、變換編碼六、變換編碼2、變換編碼的基本原理將FFT逆變換表達(dá)式進行改寫：F(u,v) 記為：T(u,v)expj2(ux+vy)/n 記為：H(x,y,u,v)變換編碼,即要用等式的右部近似原圖像。 1010),(NuNvuvHvuTF六、變換編碼六、變換編碼基本理論基本理論進一步改寫：其中：1) F是一個包含了f(x,y)的象素的nn的矩陣；2) Huv的值只依賴坐標(biāo)變量x,y,u,v，與T(u,v)和f(x,y) 的值無關(guān)。被稱為基圖像。可以在變換前一次生成，對每一個 nn的子圖變換

51、都可以使用。六、變換編碼六、變換編碼基本理論基本理論0,0, ,0,1, ,0,1, ,1,0, ,1,1, ,0,1, ,1,0, ,1,1, ,1,1, ,uvhu vhu vhnu vhu vhu vhnu vHh nu vh nu vh nnu v基圖像Huv：0,( , )( , )1,T u vm u votherwise如果滿足特定的截斷條件六、變換編碼六、變換編碼基本理論基本理論n變換系數(shù)截取模板函數(shù)通過定義變換系數(shù)截取模板函數(shù)，消去冗余。1010),(NuNvuvHvuTF對于：1010),(),(NuNvuvHvumvuTF近似：1 1 1 1 0 0 0 01 1 1 1

52、 0 0 0 01 1 1 0 0 0 0 01 1 0 0 0 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 010102),(210102101010102),(1),(1),(),(),(),(nunvvuTnunvuvnununvuvnvuvmsvumvumHvuTEHvumvuTHvuTEFFEe六、變換編碼六、變換編碼基本理論基本理論n誤差評估：六、變換編碼六、變換編碼基本理論基本理論n誤差評估其中，|F F|是(F F)的矩陣范數(shù)， 2T(u,v)是變換在(u,v)位置上的系數(shù)方差。最后的簡化是基于

53、基圖像的規(guī)范正交，并假設(shè)F的像素是通過一個具有0均值和已知協(xié)方差的隨機處理產(chǎn)生的。n誤差評估小結(jié)六、變換編碼六、變換編碼基本理論基本理論（1）總的均方近似誤差是丟棄的變換系數(shù)的方差之和（也即對于m(u,v) = 0的系數(shù)方差之和）。（2）能把大多數(shù)信息封裝到最少的系數(shù)里去的變換，可得到最好的子圖像的近似，同時重構(gòu)誤差也最小。（3）在導(dǎo)致等式成立的假設(shè)下，一個NN的圖像的(N/n)2個子圖像的均方誤差是相同的。因此，NN圖像的均方誤差（是平均誤差的測量）等于一個子圖像的均方誤差。六、變換編碼六、變換編碼3、變換編碼幾個關(guān)鍵問題p 變換的選擇p 對變換的評價p 子圖尺寸的選擇p 壓縮的位分配（編碼

54、）六、變換編碼六、變換編碼基本理論基本理論n變換的選擇(1) Karhunen-Loeve變換(KLT)(2) 離散傅立葉變換（DFT）(3) 離散余弦變換（DCT）(4) Walsh-Hadamard變換（WHT）(5) 離散小波變換(DWT)六、變換編碼六、變換編碼幾個關(guān)鍵問題幾個關(guān)鍵問題n對變換的評價按信息封裝能力排序： KLT，DCT，DFT，WHT，HaarT但KLT的基圖像是數(shù)據(jù)依賴的，每次都要重新計算Huv。因而很少使用。 DFT的塊效應(yīng)嚴(yán)重。常用的是DCT，現(xiàn)已被國際標(biāo)準(zhǔn)采納，作成芯片。其優(yōu)點有： (1) 基本沒有塊效應(yīng)。 (2) 信息封裝能力強，把最多的信息封裝在最少的系數(shù)中

55、。六、變換編碼六、變換編碼幾個關(guān)鍵問題幾個關(guān)鍵問題n子圖尺寸的選擇子圖尺寸的選擇有兩個原則：(1) 如果n是子圖的維數(shù)，n應(yīng)是應(yīng)是2的整數(shù)次方的整數(shù)次方。為便于降低計算復(fù)雜度。(2) n一般選為8x8或16x16，可由試驗得到。(3) 隨著n的增加，塊效應(yīng)相應(yīng)減少。六、變換編碼六、變換編碼幾個關(guān)鍵問題幾個關(guān)鍵問題六、變換編碼六、變換編碼幾個關(guān)鍵問題幾個關(guān)鍵問題n壓縮位的分配（編碼）定義：截取、量化、系數(shù)編碼統(tǒng)稱為位分配。主要解決m(u,v)的設(shè)計、編碼問題。截取和量化一般有兩種方法：(1) 子帶編碼。(2) 閾值編碼(適應(yīng)性編碼)。1 1 1 1 1 0 0 01 1 1 1 0 0 0 01

56、 1 1 0 0 0 0 01 1 0 0 0 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 0可消去87.5%的系數(shù)的模板六、變換編碼六、變換編碼幾個關(guān)鍵問題幾個關(guān)鍵問題n(1) 子帶編碼基本思想： 所有子圖像使用相同的編碼模板。六、變換編碼六、變換編碼幾個關(guān)鍵問題幾個關(guān)鍵問題(a) 大部分的信息應(yīng)該包含在最大方差的變換系數(shù)中。u每一個DCT變換系數(shù)被認(rèn)為是一個隨機變量；u該變量的分布可以在所有變換子圖像的集合上進行計算。 (b) 在(N/n)2個子圖找出取最大方差的m個系數(shù)的位置。u同時確定了系數(shù)的坐標(biāo)u和v

57、；u對所有子圖像，這m個系數(shù)的T(u,v)值是保留的，其他的T值被拋棄；um是一個可選常數(shù)。六、變換編碼六、變換編碼幾個關(guān)鍵問題幾個關(guān)鍵問題n算法的實現(xiàn)：1計算模板：方差最大的地方置1，其它地方置0;2量化系數(shù)：例如最優(yōu)Lloyd-Max量化器3結(jié)果編碼：有兩種分配二進制位的編碼方法： 系數(shù)被賦予相同數(shù)量的二進制位。 系數(shù)之間固定地分配一定的二進制位。8 7 6 4 3 2 1 07 6 5 4 3 2 1 06 5 4 3 3 1 1 04 4 3 3 2 1 0 03 3 3 2 1 1 0 02 2 1 1 1 0 0 01 1 1 0 0 0 0 00 0 0 0 0 0 0 0六、變

58、換編碼六、變換編碼幾個關(guān)鍵問題幾個關(guān)鍵問題例如： 系數(shù)之間固定地分配一定的二進制位的用位模板。六、變換編碼六、變換編碼幾個關(guān)鍵問題幾個關(guān)鍵問題n(2) 閾值編碼(適應(yīng)性編碼)基本思想：沒有一個取舍系數(shù)的固定模板。不同的子圖保留不同的系數(shù)。通過一個閾值T，來決定一個系數(shù)的去留。 If a(系數(shù)) T(閾值) m(u,v) = 1 else m(u,v) = 0 由于其簡單性，閾值編碼是實際應(yīng)用中經(jīng)常使用的編碼方法。1 1 0 1 0 0 0 01 1 1 1 0 0 0 01 1 0 0 0 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0 00

59、0 0 0 0 0 0 00 0 0 0 0 0 0 0六、變換編碼六、變換編碼幾個關(guān)鍵問題幾個關(guān)鍵問題n理論根據(jù)：(1) 取值最大的變換系數(shù)，在重構(gòu)子圖的質(zhì)量中起的作用也最重要。(2) 最大系數(shù)的分布隨子圖的不同而不同。六、變換編碼六、變換編碼幾個關(guān)鍵問題幾個關(guān)鍵問題n算法的實現(xiàn)：(1) 所有子圖使用同一個全局閾值。壓縮率的大小隨圖像的不同而不同。由超過全局閾值的系數(shù)的個數(shù)所決定。1. 閾值的選取，常有三種取法。(2) 對每個子圖使用不同的閾值。每個子圖保留的系數(shù)的個數(shù)事先確定，即總保留N個最大的。稱為N-最大化編碼。對于每個子圖同樣多的系數(shù)被丟棄。因此，每個子圖的壓縮率是相同的，并且是預(yù)先

60、知道的。16 11 10 16 24 40 51 6112 12 14 19 26 58 60 5514 13 16 24 40 57 69 5614 17 22 29 51 87 80 6218 22 37 56 68 109 103 7724 35 55 64 81 104 113 9249 64 78 87 103 121 120 10172 92 95 98 112 100 103 99六、變換編碼六、變換編碼幾個關(guān)鍵問題幾個關(guān)鍵問題(3) 閾值作為子圖系數(shù)位置的函數(shù)。所有子圖使用同一個全局閾值模板，但閾值的選取，與系數(shù)的位置相關(guān)，閾值模板給出了不同位置上系數(shù)的相應(yīng)閾值。例如：六、變換編碼六、