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

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

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

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

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

5、間畫面對(duì)應(yīng)像素灰度的相關(guān)性很強(qiáng)。一、編碼及信息論概述一、編碼及信息論概述如果用8 bit表示下面圖像的像素，我們就說(shuō)該圖像存在著編碼冗余，因?yàn)樵搱D像的像素只有兩個(gè)灰度，用1 bit即可表示。例析例析1 1： 由于任何給定的像素值，原理上都可以通過(guò)它的鄰居預(yù)測(cè)到，單個(gè)像素?cái)y帶的信息相對(duì)是小的。 對(duì)于一個(gè)圖像，很多單個(gè)像素對(duì)視覺(jué)的貢獻(xiàn)是冗余的。這是建立在對(duì)鄰居值預(yù)測(cè)的基礎(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、人的視覺(jué)特性對(duì)不敏感區(qū)進(jìn)行降分辨率編碼（視覺(jué)冗余）；(3)應(yīng)用方關(guān)心圖像區(qū)域有限，可對(duì)其余部分圖像可采用空間和灰級(jí)上的粗化；(4)對(duì)于識(shí)別，圖像特征抽取和描述也是數(shù)據(jù)壓縮。一、編碼及信息論概述一、編碼及信息論概述33K15K例析例析1 1： 視覺(jué)心理冗余視覺(jué)心理冗余： 一些信息在一般視覺(jué)處理中比其它信息的相對(duì)重要程度一些信息在一般視覺(jué)處理中比其它信息的相對(duì)重要程度要小，這種信息就被稱為要小，這種信息就被稱為視覺(jué)心理冗余視覺(jué)心理冗余。圖像編碼方法有許多，但從信息是否失真角度來(lái)看，可以分作兩大類：無(wú)失真編碼（無(wú)損壓縮、可逆壓縮）是一種經(jīng)編、解碼后圖像不會(huì)產(chǎn)生失真的編碼方法?？芍亟▓D像，但壓縮比不大

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

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

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

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

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

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

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

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

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

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

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

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

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

20、否”，則，則輸出與當(dāng)前前綴輸出與當(dāng)前前綴P P相對(duì)應(yīng)的碼字；相對(duì)應(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進(jìn)制) a 0 H b1 H c2 H d3 H LZW_CLEAR（初始化標(biāo)記） 4 H LZW_EOI （結(jié)束標(biāo)記） 5 H LZ

21、WLZW編碼例析編碼例析例如：對(duì)例如：對(duì)“aabcabbbbd”進(jìn)行編碼進(jìn)行編碼輸入數(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 daa aa ab ab bc bc ca ca abb abb bb bb

22、 bbd bbd 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ù)測(cè)編碼預(yù)測(cè)編碼u變換編碼變換編碼u壓縮標(biāo)準(zhǔn)簡(jiǎn)介壓縮標(biāo)準(zhǔn)簡(jiǎn)介 霍夫曼(Huffma

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

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

26、第1步0.10.1第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編碼例析編碼例

27、析輸入S1S2S3S4S5S6概率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.40.30

28、.10.10.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.

29、40101010101S5=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 b

30、ad, Im badcome on, you knowBad, bad-really, really badHuffmanHuffman編碼樹(shù)結(jié)構(gòu)編碼樹(shù)結(jié)構(gòu)短語(yǔ)符號(hào)頻率概率BecauseB10.03ImI60.17BadB150.43Come onC20.06ItI10.03ReallyR60.17You knowY40.11HuffmanHuffman編碼樹(shù)結(jié)構(gòu)編碼樹(shù)結(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(

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

32、：熵：H=-(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編碼樹(shù)結(jié)構(gòu)編碼樹(shù)結(jié)構(gòu)主要內(nèi)容u編碼及信息論概述編碼及信息論概述u行程編碼行程編碼uLZW編碼編碼u霍夫曼編碼霍夫曼編碼u預(yù)測(cè)編碼預(yù)測(cè)編碼u變換編碼變換編碼u壓縮標(biāo)準(zhǔn)簡(jiǎn)介壓縮標(biāo)準(zhǔn)簡(jiǎn)介n預(yù)測(cè)編碼是屬于時(shí)間域 (Time domain)的編碼方法。n基本概念是利用前面已經(jīng)出現(xiàn)過(guò)的符號(hào)來(lái)預(yù)測(cè)當(dāng)前的符號(hào)

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

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

35、9,139,121,112,109,1292,1 2Fm取例析例析預(yù)測(cè)值：預(yù)測(cè)值：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ù)測(cè)編碼五、預(yù)測(cè)編

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

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

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

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

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

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

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

43、DPCMn舉例： = 1， = 6.5 計(jì)算：兩個(gè)像素 f0 =14、f1 =15，則：000,14nff有損預(yù)測(cè)編碼有損預(yù)測(cè)編碼DPCMDPCM101,1 14nff 115 141e 編碼:116.50ee 1116.5 1420.5fef解碼：111520.55.5ff (預(yù)測(cè)結(jié)果預(yù)測(cè)結(jié)果)(預(yù)測(cè)誤差預(yù)測(cè)誤差)(預(yù)測(cè)誤差預(yù)測(cè)誤差)(重構(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

44、.5 14.0 20.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ù)測(cè)編碼有損預(yù)測(cè)編碼DPCMDPCM3、預(yù)測(cè)器的一般模型、預(yù)測(cè)器的一般模型),(11nmnmnnxxxfx可以是固定的，也可以是自適應(yīng)的；可以

45、是線性的，也可以是非線性的。 預(yù)測(cè)器設(shè)計(jì)得越好，對(duì)輸入的數(shù)據(jù)壓縮就越多。五、預(yù)測(cè)編碼五、預(yù)測(cè)編碼預(yù)測(cè)的階數(shù)。預(yù)測(cè)系數(shù)，其中，性預(yù)測(cè)，的線性組合，則稱為線是若maknxanxnxnxneknxanxxxxxkmkkmkknmnmnn1111)()()( )()()()( ,預(yù)測(cè)器模型預(yù)測(cè)器模型 選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ù)測(cè)器模型預(yù)測(cè)器模型 假設(shè)x(n)是各態(tài)遍歷的，且訓(xùn)練樣本數(shù)N相當(dāng)大，則x

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

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

48、逆的、線性的變換(如如FFT、DFT)，把圖像，把圖像映射到變換系數(shù)集合映射到變換系數(shù)集合;p然后對(duì)該系數(shù)集合進(jìn)行量化和編碼然后對(duì)該系數(shù)集合進(jìn)行量化和編碼;p對(duì)于大多數(shù)自然圖像，對(duì)于大多數(shù)自然圖像，重要系數(shù)的數(shù)量是比較少的重要系數(shù)的數(shù)量是比較少的，因而可以用量化因而可以用量化(或完全拋棄或完全拋棄)，且僅以較小的圖像失，且僅以較小的圖像失真為代價(jià)。真為代價(jià)。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 6

49、8 7079 65 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ù)正變換量化器符號(hào)編碼器構(gòu)造nn的子圖合成nn的子圖輸入圖像NN壓縮圖像壓縮圖像解壓圖像六、變換編碼六、變換編碼n構(gòu)造nn的子圖Nnnnnnnnnnnnn六、變換編碼六、變換編碼N110

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

51、n的子圖變換都可以使用。六、變換編碼六、變換編碼基本理論基本理論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如果滿足特定的截?cái)鄺l件六、變換編碼六、變換編碼基本理論基本理論n變換系數(shù)截取模板函數(shù)通過(guò)定義變換系數(shù)截取模板函數(shù)，消去冗余。1010),(NuNvuvHvuTF對(duì)于：1010),(),(NuNvuvHvumvuTF近似：1 1 1 1 0 0 0 01

52、 1 1 1 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誤差評(píng)估：六、變換編碼六、變換編碼基本理論基本理論n誤差評(píng)估其中，|F F|是(F F)的矩陣范數(shù)， 2T(u,v)是變換在(u,v)位置上的系數(shù)方差。最后

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

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

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

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

57、的坐標(biāo)u和v；u對(duì)所有子圖像，這m個(gè)系數(shù)的T(u,v)值是保留的，其他的T值被拋棄；um是一個(gè)可選常數(shù)。六、變換編碼六、變換編碼幾個(gè)關(guān)鍵問(wèn)題幾個(gè)關(guān)鍵問(wèn)題n算法的實(shí)現(xiàn)：1計(jì)算模板：方差最大的地方置1，其它地方置0;2量化系數(shù)：例如最優(yōu)Lloyd-Max量化器3結(jié)果編碼：有兩種分配二進(jìn)制位的編碼方法： 系數(shù)被賦予相同數(shù)量的二進(jìn)制位。 系數(shù)之間固定地分配一定的二進(jìn)制位。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

58、0 0六、變換編碼六、變換編碼幾個(gè)關(guān)鍵問(wèn)題幾個(gè)關(guān)鍵問(wèn)題例如： 系數(shù)之間固定地分配一定的二進(jìn)制位的用位模板。六、變換編碼六、變換編碼幾個(gè)關(guān)鍵問(wèn)題幾個(gè)關(guān)鍵問(wèn)題n(2) 閾值編碼(適應(yīng)性編碼)基本思想：沒(méi)有一個(gè)取舍系數(shù)的固定模板。不同的子圖保留不同的系數(shù)。通過(guò)一個(gè)閾值T，來(lái)決定一個(gè)系數(shù)的去留。 If a(系數(shù)) T(閾值) m(u,v) = 1 else m(u,v) = 0 由于其簡(jiǎn)單性，閾值編碼是實(shí)際應(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

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

60、，并且是預(yù)先知道的。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六、變換編碼六、變換編碼幾個(gè)關(guān)鍵問(wèn)題幾個(gè)關(guān)鍵問(wèn)題(3) 閾值作為子圖系數(shù)位置的函數(shù)。所有子圖使用同一個(gè)全局閾值模板，但閾值的選取，與系數(shù)的位置相關(guān)，閾值模板給出了不同位置上系數(shù)的相應(yīng)閾值。例如：六、