第七章 圖像編碼與壓縮

電子科技大學光電信息學院二○一○年4月15日彭真明Email:pengzm_ioe@163.com第七章圖像編碼與壓縮C7Imagecodingandcompression主要內容編碼及信息論概述行程編碼LZW編碼霍夫曼編碼預測編碼變換編碼壓縮標準簡介主要內容編碼及信息論概述行程編碼LZW編碼霍夫曼編碼預測編碼變換編碼壓縮標準簡介

數(shù)字圖像通常要求很大的比特數(shù)，這給圖像的傳輸和存儲帶來一定的困難。要占用很多的資源，花很高的費用。如一幅512x512的黑白圖像的比特數(shù)為

512x512x8=2,097,152bit=256k。再如一部90分鐘的彩色電影，每秒放映24幀。把它數(shù)字化，每幀512x512象素，每象素的R、G、B三分量分別占8bit，總比特數(shù)為：90×60×24×3×512×512×8bit=97,200M。一、編碼及信息論概述1、圖像壓縮的必要性

如一張CD光盤可存600兆字節(jié)數(shù)據(jù)，這部電影圖像（不包括聲音）就需要160張CD光盤用來存儲。

因此，對圖像數(shù)據(jù)進行壓縮顯得非常必要。本章討論的問題：在滿足一定條件下，能否減小圖像bit數(shù)，以及用什么樣的編碼方法使之減少。一、編碼及信息論概述

編碼是用符號數(shù)碼元素表示信號、消息或事件的過程。圖像編碼是研究圖像數(shù)據(jù)的編碼方法，期望用最少的數(shù)碼表示信源發(fā)出的圖像信號，使數(shù)據(jù)得到壓縮，減少圖像數(shù)據(jù)占用的信號空間和能量，降低信號處理的復雜程度。這里的信號空間是指：物理空間—存儲器、磁盤等數(shù)據(jù)存儲介質；時間空間—傳輸給定消息集合所需要的時間；電磁頻譜空間—傳輸給定消息集合所需要的帶寬。一、編碼及信息論概述FLASH一種發(fā)型可以代表一種信息。鼠標指向圖像，按右鍵，選“播放”圖像編碼主要是研究信源編碼。人類社會已經進入信息時代，從而引起“信息爆炸”。信息數(shù)據(jù)壓縮特別是圖像信息數(shù)據(jù)壓縮，其社會效益和經濟效益將越來越明顯，未來的圖像通訊、多媒體技術和目標識別等領域對數(shù)據(jù)處理速度、存儲容量都提出新的要求，因此，圖像數(shù)據(jù)壓縮是必要的。一、編碼及信息論概述圖像中像素灰度出現(xiàn)的不均勻性，造成圖像信息熵冗余，即用同樣長度比特表示每一個灰度，則必然存在冗余。圖像能量在變換域內分布的不均勻性，比如大部分能量集中在低頻部分，而小部分能量集中在高和較高的頻率部分。圖像像素灰度在時間和空間上的相關性造成信息冗余。2、圖像壓縮的可能性

一、編碼及信息論概述數(shù)據(jù)冗余包括：

空間冗余，鄰近像素灰度分布的相關性很強；

頻間冗余，多譜段圖像中各譜段圖像對應像素之間灰度相關性很強；

時間冗余，序列圖像幀間畫面對應像素灰度的相關性很強。一、編碼及信息論概述如果用8位表示下面圖像的像素，我們就說該圖像存在著編碼冗余，因為該圖像的像素只有兩個灰度，用一位即可表示。例析1：由于任何給定的像素值，原理上都可以通過它的鄰域預測到，單個像素攜帶的信息相對是小的。對于一幅圖像，很多單個像素對視覺的貢獻是冗余的。這是建立在對鄰域值預測的基礎上。如：原圖像數(shù)據(jù)：25025325125225040bit。

壓縮后數(shù)據(jù)：250312014bit。例析2：

應用環(huán)境允許圖像有一定程度失真(1)接收端圖像設備分辨率較低，則可降低圖像分辨率；(2)根據(jù)人的視覺特性對不敏感區(qū)進行降分辨率編碼（視覺冗余）；(3)應用方關心圖像區(qū)域有限，可對其余部分圖像可采用空間和灰級上的粗化；(4)對于識別，圖像特征抽取和描述也是數(shù)據(jù)壓縮。一、編碼及信息論概述33K15K例析1：視覺心理冗余：

一些信息在一般視覺處理中比其它信息的相對重要程度要小，這種信息就被稱為視覺心理冗余。圖像編碼方法有許多，但從壓縮前后的信息損失角度來看，可以分作兩大類：

無失真編碼（無損壓縮、可逆壓縮）是一種經編、解碼后圖像不會產生失真的編碼方法，可重建圖象，但壓縮比不大；

有失真編碼（有損壓縮、不可逆壓縮）解碼時無法完全恢復原始圖像，壓縮比大但，有信息損失。這里的失真是指編碼輸入圖像與解碼輸出圖像之間的隨機誤差，而壓縮比指原圖像比特數(shù)與壓縮后圖像比特數(shù)之比。3、圖像編碼分類一、編碼及信息論概述變換編碼統(tǒng)計編碼預測編碼圖像壓縮方法有損壓縮游程編碼ＬＺＷ編碼哈夫曼編碼算術編碼其他無損預測有損預測其他ＫＬＴ編碼ＤＣＴ變換其他無損壓縮一、編碼及信息論概述傳統(tǒng)的圖像編碼方法有脈碼調制、量化算法、空間和時間亞取樣編碼、熵編碼、預測編碼、變換編碼、矢量量化和子帶編碼等。新型編碼技術包括第二代圖像編碼方法、分形編碼、基于模型的編碼和小波編碼等。圖像編碼是從不同角度消除圖像數(shù)據(jù)中的冗余，減少表示圖像所需的比特數(shù)，或平均比特數(shù)，實現(xiàn)數(shù)據(jù)量的壓縮。一、編碼及信息論概述信息量：從N個相等可能發(fā)生的事件中，選出其中一個事件所需的信息度量，稱為信息量。4、信息量和熵一、編碼及信息論概述

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

信息量：從N個數(shù)選定一個數(shù)s的概率為p(s)，且等概率，p(s)=1/N。

熵(Entropy)：設信源符號表為s={s1,s2,…,

sq}，其概率分布為P(s)={p(s1),p(s2),…,p(sq)}，則信源的熵為：一、編碼及信息論概述編碼應用中，熵表示信源中消息的平均信息量，在不考慮消息間的相關性時，是無失真代碼平均長度比特數(shù)的下限。例：信源說明該信源編碼平均碼長最短情況下為7/4，不能再小，否則就會引起錯誤，而平均碼長比此數(shù)大許多時，就表明還有待改進。一、編碼及信息論概述熵的性質：

(1)熵是一個非負數(shù)，即總有H(s)≥0。(2)當其中一個符號sj的出現(xiàn)概率p(sj)=1時，其余符號si(i≠j)的出現(xiàn)概率p(si)=0，H(s)=0。(3)當各個si出現(xiàn)的概率相同時，則最大平均信息量為log2

q。(4)熵值總有H(s)≤log2

q。4、信息量和熵一、編碼及信息論概述(1)s作為灰度，共q級，出現(xiàn)概率均等時，p(si)=1/q，(2)當灰度只有兩級時，即si=0,1，且0出現(xiàn)概率為p1，1出現(xiàn)概率為p2=1-p1

，其熵圖像的熵一、編碼及信息論概述(3)對８位圖像，s作為灰度，共256級，其熵為：(4)當圖像由單一灰度級組成時（即灰度均勻分布圖像）,其熵為：圖像的熵一、編碼及信息論概述編碼器是用符號集中的符號構成輸出代碼，并建立輸入信號單元與輸出代碼的對應關系。如下圖所示：消息集合輸出代碼符號集符號(碼元)5、信息編碼過程編碼器一、編碼及信息論概述

可以證明，在無干擾的條件下，存在一種無失真的編碼方法，使編碼的平均長度

L與信源的熵H(s)任意地接近，即

L=H(s)+ε

其中ε為任意小的正數(shù)，但以H(s)為其下限，即L≥H(s)，這就是香農(Shannon)無干擾編碼定理。

6、無失真編碼定理一、編碼及信息論概述編碼效率定義為：

冗余度接近于0，或編碼效率接近于1的編碼稱為高效碼。(1)、編碼效率一、編碼及信息論概述若原始圖像的平均比特率為n，編碼后的平均比特率為nd，則壓縮比C定義為：由Shannon定理，無失真編碼最大可能的數(shù)據(jù)壓縮比為：(2)壓縮比一、編碼及信息論概述

對于無失真圖像的編碼，原始圖像數(shù)據(jù)的壓縮存在一個下限，即平均碼組長度不能小于原始圖像的熵，而理論上的最佳編碼的平均碼長無限接近原始圖像的熵。

原始圖像冗余度定義為：7、熵與相關性、冗余度的關系一、編碼及信息論概述主要內容編碼及信息論概述行程編碼LZW編碼霍夫曼編碼預測編碼變換編碼壓縮標準簡介1、概念：

行程：具有相同灰度值的像素序列。

2、編碼思想：

去除像素冗余。即用行程的灰度和行程的長度代替行程本身。二、行程編碼(RunLengthEncoding)例：設重復次數(shù)為iC,重復像素值為iP，則

編碼為：iCiPiCiPiCiP…

編碼前：aaaaaaabbbbbbcccccccc

編碼后：7a6b8c二、行程編碼二、行程編碼分析對于有大面積色塊的圖像，壓縮效果很好；對于紛雜的圖像，壓縮效果不好，最壞情況下，會加倍圖像。主要內容編碼及信息論概述行程編碼LZW編碼霍夫曼編碼預測編碼變換編碼壓縮標準簡介

1985年,美國人Welch將LZ壓縮技術從概念發(fā)展到實用階段,簡稱LZW壓縮技術。廣泛用于圖像壓縮領域。

LZW（Lempel-Ziv&Welch）編碼又稱字串表編碼，屬于一種無損編碼，LZW編碼與行程編碼類似，也是對字符串進行編碼從而實現(xiàn)壓縮，但它在編碼的同時還生成了特定字符串以及與之對應的索引字符串表。三、LZW編碼

1977年,以色列人Lempel和Ziv共同提出了查找冗余字符和用較短的符號標記替代冗余字符的概念，簡稱LZ壓縮技術。

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

字符序列的長度如何確定？字典的長度如何確定？字典滿了怎么辦？如何查字典？三、LZW編碼(1)字典中字符序列的長度：字典中字符串的長度可能會很長，由于每一個字符串，都是表中一個已經存在的字符串加上一個字符組成，所以可以把字符串以:

<已有字符串索引>+<字符>

這樣字典元素的長度統(tǒng)一為12+8，20位。(2)字典的長度：

對于以字節(jié)（8位）為壓縮單元，如ASCII碼，字典的長度為212=4096，索引的長度為12位，字典的前256個保存單個字符，剩下的3840個的分配給壓縮過程中出現(xiàn)的字符串。三、LZW編碼(3)字典滿了的解決辦法：

在字典滿了以后（新字符串超過4096），輸出一個清除字典的標記LZW_CLEAR，清空字典，開始新的編碼。(4)查表的方法：

可通過Hashing函數(shù)（散列、雜湊）的方法來減少查表的次數(shù)。(5)輸出編碼的時機：

發(fā)現(xiàn)新串時，輸出前一個串的編碼。步驟1：將詞典初始化為包含所有可能的單字步驟2：當前字符C:=字符流中的下一個字符。字符，當前前綴P初始化為空。3、基本步驟三、LZW編碼令P:=C，現(xiàn)在的P僅包含一個字符C步驟3：判斷P＋C是否在詞典中（1）如果“是”，則用C擴展P，即讓P:=P＋C（2）如果“否”，則輸出與當前前綴P相對應的碼字；將P＋C添加到詞典中；三、LZW編碼步驟4：判斷碼字流中是否還有碼字要譯（1）如果“是”，就返回到步驟2；（2）如果“否”把代表當前前綴P的碼字輸出到碼字流；結束。三、LZW編碼初始化字符串表

字符串索引(16進制)a0Hb1Hc2H

d3HLZW_CLEAR4HLZW_EOI5HLZW編碼例析例如：對“aabcabbbbd”進行編碼輸入數(shù)據(jù)S2S1+S2輸出結果S1生成的新字符串及索引NULLaabcabbbbdNULLNULLaaaaa4H0H0Habbccaababbbbbbbbd1H2H7H1HBH3H5Hbcaabbbbbdaa<6H>ab<7H>bc<8H>ca<9H>abb<AH>bb<BH>bbd<CH>S1為NULL,故輸出結果為空S1+S2在字符表中,S1=S1+S2aa不存在,故輸出S1=“a”的索引0HS1+S2不在字符表中,S1=S2=“a”ab不存在,故輸出S1=“a”的索引0HS1+S2不在字符表中,S1=S2=“b”S1+S2結果已存在,故輸出結果為空S1+S2在字符表中,S1=S1+S2輸入結束輸出S1的索引3H輸出LZW_EOI標志的索引LZW編碼例析：“aabcabbbbd”主要內容編碼及信息論概述行程編碼LZW編碼霍夫曼編碼預測編碼變換編碼壓縮標準簡介霍夫曼編碼是可變字長編碼(VLC)的一種。Huffman于1952年提出的一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫作Huffman編碼。

1、簡介四、霍夫曼(Huffman)編碼四、霍夫曼(Huffman)編碼2、基本思想——通過減少編碼冗余來達到壓縮的目的。a)基本思想是統(tǒng)計一下符號的出現(xiàn)概率。b)建立一個概率統(tǒng)計表。

將最常出現(xiàn)(概率大的)的符號用最短的編碼；最少出現(xiàn)的符號用最長的編碼。信號源s={s1,s2,s3,s4,s5,s6}，其概率分布為p1=0.4p2=0.3p3=0.1p4=0.1p5=0.06p6=0.04，求最佳Huffman碼。步驟如下：將信源符號按出現(xiàn)概率從大到小排成一列，然后把最末兩個符號的概率相加，合成一個概率。四、霍夫曼(Huffman)編碼把這個符號的概率與其余符號的概率按從大到小排列，然后再把最末兩個符號的概率加起來，合成一個概率。重復上述做法，直到最后剩下兩個概率為止。從最后一步剩下的兩個概率開始逐步向前進行編碼。每步只需對兩個分支各賦予一個二進制碼，如對概率大的賦予碼元0，對概率小的賦予碼元1。四、霍夫曼(Huffman)編碼輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04Huffman編碼例析輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1Huffman編碼例析輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1Huffman編碼例析輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3Huffman編碼例析輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.4Huffman編碼例析輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101Huffman編碼例析輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S1=1Huffman編碼例析輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S2=00Huffman編碼例析輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S3=011Huffman編碼例析輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S4=0100Huffman編碼例析輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S5=01010Huffman編碼例析輸入S1S2S3S4S5S6輸入概率0.40.30.10.10.060.04第一步0.40.30.10.10.1第二步0.40.30.20.1第三步0.40.30.3第四步0.60.40101010101S6=01011Huffman編碼例析下面是一首英文歌曲：

BecauseI’mbad,Iambad—comeon

Bad,bad—really,reallybad

YouknowI’mbad,I'mbad—

Bad,bad—really,reallybad

YouknowI’mbad,I'mbad—comeon,youknow

Bad,bad-really,reallybadHuffman編碼樹結構短語符號頻率概率BecauseB10.03I’mI60.17BadB150.43ComeonC20.06ItI10.03ReallyR60.17YouknowY40.11Huffman編碼樹結構S6S5S3S2S1B0.43(Bad)10(1.00)S40100I0.17(I’m)R0.17(Really)Y0.11(Youknow)C0.06(Comeon)B0.03(Because)I0.03(It)000001011010000000010000000001(0.57)(0.23)(0.12)(0.06)(0.34)Huffman編碼樹結構短語符號頻率概率代碼長度編碼BecauseB10.03500001I’mI60.173011BadB150.4311ComeonC20.0640001ItI10.03500000ReallyR60.173010YouknowY40.113001Huffman編碼樹結構平均碼長：R=0.03x5+0.17x3+0.43x1+0.06x4+0.03x5+0.17x3+0.11x3=2.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％。Huffman編碼樹結構主要內容編碼及信息論概述行程編碼LZW編碼霍夫曼編碼預測編碼變換編碼壓縮標準簡介預測編碼是是屬于時間域

(Timedomain，即信號本身)的編碼方法?；靖拍钍鞘抢们懊嬉呀洺霈F(xiàn)過的符號來預測當前的符號，然后將實際上的符號與預測相減得到預測誤差值。利用預測編碼的好處在于預測誤差值的范圍比原信號的數(shù)字范圍小，如果預測足夠精確的話。通常會對預測誤差值進一步量化。（quantization）?？煞譃橛袚p和無損預測，但預測本身不會造成失真。五、預測編碼五、預測編碼1、無損預測編碼(LosslessPredictiveCoding)基本思想去除像素冗余。認為相鄰像素的信息有冗余。當前像素值可以用先前的像素值來獲得。用當前像素值fn，通過預測器得到一個預測值，對當前值和預測值求差，對差編碼，作為壓縮數(shù)據(jù)流中的下一個元素。五、預測編碼1001021011001001011001021021001001031001021011001001001021001011011001001001002-1-101-120-2-13-32-10002-210-100例：利用前一個像素預測五、預測編碼一般情況下，利用前m個像素的線性組合來預測，即因此，在一維線性(行預測)預測編碼中，預測器為：其中，round為取最近整數(shù)，

i為預測系數(shù)(可為1/m)，y是行變量。注意：前m個像素不能用此法編碼，可用哈夫曼編碼。例析預測值：五、預測編碼(2)編碼步驟第①步：壓縮頭處理。第②步：預測值。第③步：求預測誤差值。第④步：對誤差e(x,y)編碼，作為壓縮值。重復②、③、④步預測器最接近的整數(shù)+

-符號編碼壓縮圖像輸入圖像enfn

fn五、預測編碼(3)編碼原理圖基本概念量化器編碼原理

五、預測編碼2、有損預測編碼(LossyPredictiveCoding)（1）有損壓縮的基本概念有損壓縮是：通過犧牲圖像的準確率來達到增大壓縮率的目的。如果容忍解壓縮后的結果中有一定的誤差，那么壓縮率可以顯著提高。有損壓縮方法的壓縮比：在圖像壓縮比大于30:1時，仍然能夠重構圖像。在圖像壓縮比為10:1到20:1時，重構圖像與原圖幾乎沒有差別。無損壓縮的壓縮比很少有能超過3:1的。有損與無損壓縮的根本差別在于有沒有量化模塊。五、預測編碼源數(shù)據(jù)編、解碼的一般模型編碼模型解碼模型符號解碼器反向映射器映射器量化器編碼器五、預測編碼(2)量化器：減少數(shù)據(jù)量的最簡單的辦法是將圖像量化成較少的灰度級，通過減少圖像的灰度級來實現(xiàn)圖像的壓縮；這種量化是不可逆的，因而解碼時圖像有損失。例如：

如果輸入是256個灰度級，對灰度級量化后輸出，只剩下4個層次，數(shù)據(jù)量被大大減少。五、預測編碼量化器的定義階梯形量化函數(shù)t=q(s)，是一個s的奇函數(shù)（即q(-s)=-q(s)），它可以通過L/2、si和ti來完全描述，從而定義了一個量化器。si被稱為量化器的決策級（閾值）；

ti被稱為量化器的重構級（代表級）。

L是量化器的級數(shù)。由于習慣的原因，si被認為是映射到ti，如果它在半開區(qū)間(si,si+1]。五、預測編碼量化器的定義inputs1s2S(L/2)-1outputstt1t2t(L/2)-t(L/2)S-[(L/2)-1]t=q(s)決策級(閾值)重構級(代表級)注：量化的對象可能是負數(shù)五、預測編碼(3)無損到有損——算法演變

基本思想：對無損預測壓縮的誤差進行量化，通過消除視覺心理冗余，達到對圖像進一步壓縮的目的?！?/p>

引入量化(Quantification)五、預測編碼五、預測編碼將en量化：用：近似編碼：解碼：編、解碼原理及過程

^編碼流程圖：

ên

=Q(fn-fn)+

-符號編碼預測器壓縮圖像輸入圖像enfn

fn量化器ên五、預測編碼壓縮圖像

^解碼流程圖：

fn=ên

+fn+

+符號解碼預測器解壓圖像

fn

fnên五、預測編碼預測器預測器編碼fn解壓

fn五、預測編碼注意：上述方案的壓縮編碼中，預測器的輸入是fn，而解壓縮中的預測器的輸入是fn

，要使用相同的預測器，編碼方案要進行修改。修改后的有損預測編碼

^ ên

=Q(fn-fn)符號編碼壓縮圖像+

-en輸入圖像fn量化器ên預測器

fn+

+

fn

^

fn=ên

+fn五、預測編碼DPCM簡介差分脈沖編碼調制(DifferentialPulseCodeModulation,DPCM)，采用反饋方法預測估值。1950年，卡特勒申請專利;1952年，獲得批準;1958年，格雷厄姆（Graham)開始計算機模擬研究編碼方法；1966年，奧尼爾（O’Neal)對電視信號預測編碼進行理論分析以及計算機模擬；1971年投入使用。五、預測編碼量化器編碼器解碼器預測器預測器五、預測編碼編碼原理圖五、預測編碼量化器：預測器：

一般是一個小于1的預測系數(shù)。例如：量化器設：

=6.5+6.5-6.5e‘e有損預測編碼——DPCM舉例：

=1，

=6.5計算：兩個像素

f0=14、f1=15，則：(預測結果)(預測誤差)(量化誤差)(重構結果)(重構誤差)有損預測編碼——DPCM

輸入 編碼解碼誤差nf^fe

e

f^f

ff-

f0 14---14.0-14.00.01 1514.0

1.06.520.514.020.5-5.52 1420.5-6.5-6.514.020.514.00.03 1514.01.06.520.514.020.5-5.5. .......14 2920.58.56.527.020.527.02.015 3727.010.06.533.527.033.53.516 4733.513.56.540.033.540.07.017 6240.022.06.546.540.046.515.5有損預測編碼——DPCM3、預測器的一般模型可以是固定的，也可以是自適應的；可以是線性的，也可以是非線性的。預測器設計得越好，對輸入的數(shù)據(jù)壓縮就越多。五、預測編碼一維線性預測預測器模型選ak使σ2d(n)最小。設x(n)是廣義平穩(wěn)的，且e(n)均值為0，則預測器模型(1)最佳線性預測假設x(n)是各態(tài)歷經的，且訓練樣本數(shù)N相當大，則x(n)的自相關函數(shù)

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

便是一組最佳的預測系數(shù)。壓縮效果可用方差σ2e(n)來衡量，原始序列相關性越強，R(k)越大，σ2e(n)越小，壓縮效果越顯著；原始序列互不相關，即R(k)=0，k≠0，則，σ2e(n)=σ2x(n)一點也不能壓縮。預測器模型主要內容編碼及信息論概述行程編碼LZW編碼霍夫曼編碼預測編碼變換編碼壓縮標準簡介六、變換編碼1、變換編碼的基本思想用一個可逆的、線性的變換(如FFT、DFT)，把圖像映射到變換系數(shù)集合;然后對該系數(shù)集合進行量化和編碼;對于大多數(shù)自然圖像，重要系數(shù)的數(shù)量是比較少的，因而可以用量化(或完全拋棄)，且僅以較小的圖像失真為代價。5255 6166 706164736359 6690 1098569726259 6811314410466736358 7112215410670696761 681041268868707965 6070 776858758571 6459 556165838779 6968 65767894六、變換編碼例如：原圖像DCT變換系數(shù)編碼、解碼流程圖符號解碼器逆變換正變換量化器符號編碼器構造n×n的子圖合成n×n的子圖輸入圖像N×N壓縮圖像壓縮圖像解壓圖像六、變換編碼構造n×n的子圖Nn×nn×nn×nn×nn×nn×n六、變換編碼N六、變換編碼2、變換編碼的基本原理將FFT逆變換表達式進行改寫：F(u,v)記為：T(u,v)exp[j2(ux+vy)/n]記為：H(x,y,u,v)變換編碼,即要用等式的右部近似原圖像。六、變換編碼——基本理論進一步改寫：其中：1)F是一個包含了f(x,y)的象素的nxn的矩陣；2)Huv的值只依賴坐標變量x,y,u,v，與T(u,v)和f(x,y)的值無關。被稱為基圖像?？梢栽谧儞Q前一次生成，對每一個nxn的子圖變換都可以使用。六、變換編碼——基本理論基圖像Huv：六、變換編碼——基本理論變換系數(shù)截取模板函數(shù)通過定義變換系數(shù)截取模板函數(shù)，消去冗余。對于：近似：1111

0000111

1

0000111

000001100000010000000000000000000000000000000六、變換編碼——基本理論誤差評估：六、變換編碼——基本理論誤差評估其中，||F–^F||是(F–^F)的矩陣范數(shù)，

2T(u,v)是變換在(u,v)位置上的系數(shù)方差。最后的簡化是基于基圖像的規(guī)范正交，并假設F的像素是通過一個具有0均值和已知協(xié)方差的隨機處理產生的。誤差評估小結六、變換編碼——基本理論（1）總的均方近似誤差是丟棄的變換系數(shù)的方差之和（也即對于m(u,v)=0的系數(shù)方差之和）。（2）能把大多數(shù)信息封裝到最少的系數(shù)里去的變換，可得到最好的子圖像的近似，同時重構誤差也最小。（3）在導致等式成立的假設下，一個N×N的圖像的(N/n)2個子圖像的均方誤差是相同的。因此，N×N圖像的均方誤差（是平均誤差的測量）等于一個子圖像的均方誤差。六、變換編碼3、變換編碼——幾個關鍵問題變換的選擇對變換的評價子圖尺寸的選擇壓縮的位分配（編碼）六、變換編碼——基本理論變換的選擇(1)Karhunen-Loeve變換(KLT)(2)離散傅立葉變換（DFT）(3)離散余弦變換（DCT）(4)Walsh-Hadamard變換（WHT）(5)離散小波變換(DWT)六、變換編碼——幾個關鍵問題對變換的評價按信息封裝能力排序：KLT，DCT，DFT，WHT，HaarT但KLT的基圖像是數(shù)據(jù)依賴的，每次都要重新計算Huv。因而很少使用。DFT的塊效應嚴重。常用的是DCT，先已被國際標準采納，作成芯片。其優(yōu)點有：

(1)基本沒有塊效應。

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

0001111

0000111

0000011

0000001

0000000000000000000000000000000可消去87.5%的系數(shù)的模板六、變換編碼——幾個關鍵問題(1)子帶編碼基本思想：所有子圖像使用相同的編碼模板。六、變換編碼——幾個關鍵問題(a)大部分的信息應該包含在最大方差的變換系數(shù)中。每一個DCT變換系數(shù)被認為是一個隨機變量；該變量的分布可以在所有變換子圖像的集合上進行計算。

(b)在(N/n)2個子圖找出取最大方差的m個系數(shù)的位置。同時確定了系數(shù)的坐標u和v；對所有子圖像，這m個系數(shù)的T(u,v)值是保留的，其他的T值被拋棄；m是一個可選常數(shù)。六、變換編碼——幾個關鍵問題算法的實現(xiàn)：〈1〉計算模板：方差最大的地方置1，其它地方置0;〈2〉量化系數(shù)：例如最優(yōu)Lloyd-Max量化器〈3〉結果編碼：有兩種分配二進制位的編碼方法：①系數(shù)被賦予相同數(shù)量的二進制位。②系數(shù)之間固定地分配一定的二進制位。8764321076543210654331104433210033321100221110001110000000000000六、變換編碼——幾個關鍵問題例如：系數(shù)之間固定地分配一定的二進制位的用位模板。六、變換編碼——幾個關鍵問題(2)閾值編碼(適應性編碼)基本思想：沒有一個取舍系數(shù)的固定模板。不同的子圖保留不同的系數(shù)。通過一個閾值T，來決定一個系數(shù)的去留。Ifa(系數(shù))>T(閾值)m(u,v)=1else m(u,v)=0由于其簡單性，閾值編碼是實際應用中經常使用的編碼方法。11

0

1

00001111

000011

0000001

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