第六章圖像編碼與壓縮Chapter06Imagecodingandcompression主要內(nèi)容編碼及信息論概述行程編碼LZW編碼霍夫曼編碼預測編碼變換編碼壓縮標準簡介*一幅512×512的灰度圖像的比特數(shù)為：一、編碼及信息論概述1、圖像壓縮的必要性

可見：數(shù)字圖像通常要求很大的比特數(shù)，這給圖像的傳輸和存儲帶來一定的困難。要占用很多的資源，花很高的費用。512×512×8=2,097,152bit=256k。一部90分鐘的彩色電影，每秒放映24幀。把它數(shù)字化，每幀512x512象素，每象素的R、G、B三分量分別占8bit，總比特數(shù)為：一、編碼及信息論概述1、圖像壓縮的必要性

若一張CD光盤可存600兆字節(jié)數(shù)據(jù)，這部電影圖像（不包括聲音）就需要160張CD光盤用來存儲。90×60×24×3×512×512×8bit=97,200(M)因此，對圖像數(shù)據(jù)進行壓縮顯得非常必要。一、編碼及信息論概述本章討論的問題：在滿足一定條件下，能否減小圖像bit數(shù)，以及用什么樣的編碼方法使之減少。

編碼一、編碼及信息論概述圖像編碼信號空間是用符號數(shù)碼元素表示信號、消息或事件的過程。是研究圖像數(shù)據(jù)的編碼方法。期望用最少的碼字表示信源發(fā)出的圖像信號，使數(shù)據(jù)得到壓縮，減少圖像數(shù)據(jù)占用的信號空間和能量，降低信號處理的復雜程度。物理空間—存儲器、磁盤等數(shù)據(jù)存儲介質(zhì)；時間空間—傳輸給定消息集合所需要的時間；頻譜空間—傳輸給定消息集合所需要的帶寬。圖像中像素灰度出現(xiàn)的不均勻性，造成圖像信息熵冗余，即用同樣長度比特表示每一個灰度，則必然存在冗余。圖像能量在變換域內(nèi)分布的不均勻性，比如大部分能量集中在低頻部分，而小部分能量集中在高和較高的頻率部分。圖像像素灰度在時間和空間上的相關(guān)性造成信息冗余。2、圖像壓縮的可能性

一、編碼及信息論概述數(shù)據(jù)冗余一、編碼及信息論概述空間冗余，鄰近像素灰度分布的相關(guān)性很強；頻間冗余，多譜段圖像中各譜段圖像對應(yīng)像素之間灰度相關(guān)性很強；時間冗余，序列圖像幀間畫面對應(yīng)像素灰度的相關(guān)性很強。如果用8bit表示下面圖像的像素，可以說該圖像存在著編碼冗余。例析1：因為該圖像的像素只有兩個灰度，用1bit即可表示。對于一幅圖像，很多單個像素對視覺的貢獻是冗余的。這可以建立在對鄰域值預測的基礎(chǔ)上。例析2：例如：原圖像數(shù)據(jù)：

250253251252250壓縮后數(shù)據(jù)：

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

無失真編碼（無損壓縮、可逆壓縮）是一種經(jīng)編、解碼后圖像不會產(chǎn)生失真的編碼方法?？芍亟▓D像，但壓縮比不大；

有失真編碼（有損壓縮、不可逆壓縮）解碼時無法完全恢復原始圖像，壓縮比大但有信息損失。3、圖像編碼分類一、編碼及信息論概述失真是指編碼輸入圖像與解碼輸出圖像之間的隨機誤差；壓縮比指原圖像比特數(shù)與壓縮后圖像比特數(shù)之比。變換編碼統(tǒng)計編碼預測編碼圖像壓縮方法有損壓縮行程編碼ＬＺＷ編碼哈夫曼編碼算術(shù)編碼其他無損預測有損預測其他ＫＬＴ編碼ＤＣＴ變換其他無損壓縮一、編碼及信息論概述數(shù)學上，信源是一概率場。若信源可能產(chǎn)生的信息是，這些信息出現(xiàn)的概率分別是

。則該信源可表示為：一、編碼及信息論概述信源的定義信源即能夠產(chǎn)生信息的事物。信息量：從N個相等可能發(fā)生的事件中，選出其中一個事件所需的信息度量，稱為信息量。4、信息量和熵一、編碼及信息論概述例如：要辨識1到32中選定的某一個數(shù)，可先提問：“是否大于16？”，得到回答就消去半數(shù)可能事件。每提問一次得到回答，可以得到1bit信息量(二進制位)。這里共需5次，因此所需的信息量為：信息量的計算熵的計算一、編碼及信息論概述從N個數(shù)選定一個數(shù)s的概率為p(s)，且等概率，p(s)=1/N。設(shè)信源符號表為s={s1,s2,…

,

sq}，其概率分布為P(s)={p(s1),p(s2),…,p(sq)}，則信源的熵為：

編碼中，熵表示信源中消息的平均信息量。在不考慮消息間的相關(guān)性時，是無失真編碼平均長度比特數(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。熵的性質(zhì)(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)當圖像由單一灰度級組成時（即灰度均勻分布圖像）,其熵為：圖像的熵一、編碼及信息論概述編碼器是用符號集中的符號構(gòu)成輸出代碼，并建立輸入信號單元與輸出代碼的對應(yīng)關(guān)系。5、信息編碼過程消息集合輸出代碼符號集符號(碼元)編碼器一、編碼及信息論概述在無干擾的條件下，存在一種無失真的編碼方法，使編碼的平均長度L與信源的熵H(s)任意地接近，即L=H(s)+ε其中ε為任意小的正數(shù)，但以H(s)為其下限，即L≥H(s)，這就是香農(nóng)(Shannon)無干擾編碼定理。

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

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

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

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

2、編碼思想：

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

編碼為：iCiPiCiPiCiP

編碼前：aaaaaaabbbbbbcccccccc

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

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

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

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

1、簡介三、LZW編碼(1)在壓縮過程中動態(tài)地形成一個字符序列表(字典)。(2)(a)每當壓縮掃描圖像發(fā)現(xiàn)一個字典中沒有的字符序列，就把該字符序列存到字典中；(b)并用字典的地址（編碼）作為這個字符序列的代碼，替換原圖像中的字符序列；(c)下次再碰到相同的字符序列，就用字典的地址代替字符序列。2、基本思想

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

字符串索引(16進制)a0Hb1Hc2H

d3HLZW_CLEAR（初始化標記）

4HLZW_EOI（結(jié)束標記）

5HLZW編碼例析如：對字符串“aabcabbbbd”進行編碼輸入數(shù)據(jù)S2S1+S2輸出結(jié)果S1生成的新字符串及索引NULLaabcabbbbdNULLNULLaaaaa4H0H0Habbccaababbbbbbbbd1H2H7H1HBH3H5Hbcaabbbbbdaa<6H>ab<7H>bc<8H>ca<9H>abb<AH>bb<BH>bbd<CH>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標志的索引LZW編碼例析：“aabcabbbbd”主要內(nèi)容編碼及信息論概述行程編碼LZW編碼霍夫曼編碼預測編碼變換編碼壓縮標準簡介

霍夫曼(Huffman)編碼是可變字長編碼(Variablelengthcoding，VLC)的一種。Huffman于1952年提出的一種編碼方法。該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，常被稱作Huffman編碼，有時稱之為最佳編碼，

1、簡介四、霍夫曼(Huffman)編碼四、霍夫曼(Huffman)編碼2、基本思想通過減少編碼冗余來達到數(shù)據(jù)壓縮的目的。a)統(tǒng)計各個符號出現(xiàn)的概率。b)建立一個概率統(tǒng)計表。將最常出現(xiàn)(概率大的)的符號用最短的編碼；最少出現(xiàn)的符號用最長的編碼。例如：信號源s={s1,s2,s3,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)編碼把這個符號的概率與其余符號的概率按從大到小排列，然后再把最末兩個符號的概率加起來，合成一個概率。重復上述做法，直到最后剩下兩個概率為止。從最后一步剩下的兩個概率開始逐步向前進行編碼。每步只需對兩個分支各賦予一個二進制碼，如對概率大的賦予碼元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第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3Huffman編碼例析輸入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.4Huffman編碼例析輸入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.40101010101Huffman編碼例析輸入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.40101010101S1=1Huffman編碼例析輸入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.40101010101S2=00Huffman編碼例析輸入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.40101010101S3=011Huffman編碼例析輸入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.40101010101S4=0100Huffman編碼例析輸入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步0.60.40101010101S5=01010Huffman編碼例析輸入S1S2S3S4S5S6概率0.40.30.10.10.060.04第1步0.40.30.10.10.1第2步0.40.30.20.1第3步0.40.30.3第4步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編碼樹結(jié)構(gòu)短語符號頻率概率BecauseB10.03I’mI60.17BadB150.43ComeonC20.06ItI10.03ReallyR60.17YouknowY40.11Huffman編碼樹結(jié)構(gòu)S6S5S3S2S1B0.43(Bad)10(1.00)S40001I0.17(I’m)R0.17(Really)Y0.11(Youknow)C0.06(Comeon)B0.03(Because)I0.03(It)010011001000010001010100001001(0.57)(0.23)(0.12)(0.06)(0.34)Huffman編碼樹結(jié)構(gòu)短語符號頻率概率代碼長度編碼BecauseB10.03501001I’mI60.173001BadB150.4311ComeonC20.0640101ItI10.03501000ReallyR60.173000YouknowY40.113011Huffman編碼樹結(jié)構(gòu)平均碼長：L=0.03×5+0.17×3+0.43×1+0.06×4+0.03×5+0.17×3+0.11×3=2.32Huffman編碼樹結(jié)構(gòu)熵：

H=-(0.03×log0.03+0.17×log0.17+0.43×long0.43+0.06×log0.06+0.03×log0.03+0.17×log0.17+0.11×log0.11)=2.29編碼前：35×log27=98.3,編碼后：81位

壓縮比：(98.3-81)/98.3

≈

17.6%。主要內(nèi)容編碼及信息論概述行程編碼LZW編碼霍夫曼編碼預測編碼變換編碼壓縮標準簡介*預測編碼五、預測編碼基本思路：利用前面已經(jīng)出現(xiàn)過的符號來預測當前的符號，然后將實際上的符號與預測相減得到預測誤差值。利用預測編碼的好處在于預測誤差值的范圍比原信號的數(shù)字范圍小，如果預測足夠精確的話。通常會對預測誤差值進一步編碼（quantization）。可分為有損和無損預測，但預測本身不會造成失真。屬于時間域

(Timedomain)的編碼方法。五、預測編碼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)有損壓縮的基本概念有損壓縮：通過犧牲圖像的準確率來達到增大壓縮率的目的。如果容忍解壓后的結(jié)果中有一定的誤差，那么壓縮率可以顯著提高。有損壓縮的壓縮比：在圖像壓縮比大于30:1時，仍然能夠重構(gòu)圖像。在圖像壓縮比為10:1到20:1時，重構(gòu)圖像與原圖幾乎沒有差別。無損壓縮的壓縮比很少有能超過3:1的（Why?）。有損與無損壓縮的根本差別在于有沒有量化器模塊。五、預測編碼數(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

被稱為量化器的重構(gòu)級（代表級）。

L：是量化器的級數(shù)。由于習慣的原因，si被認為是映射到ti，如果它在半開區(qū)間(si,si+1]。inputs1s2S(L/2)-1outputstt1t2t(L/2)-t(L/2)S-[(L/2)-1]t=q(s)決策級(閾值)重構(gòu)級(代表級)注：量化的對象可能是負數(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簡介1950年，卡特勒申請專利;1952年，獲得批準;1958年，格雷厄姆（Graham)開始計算機模擬研究編碼方法；1966年，奧尼爾（O’Neal)對電視信號預測編碼進行理論分析以及計算機模擬；1971年投入使用。五、預測編碼差分脈沖編碼調(diào)制(DifferentialPulseCodeModulation,DPCM)，采用反饋方法預測估值。量化器編碼器解碼器預測器預測器五、預測編碼編碼原理圖五、預測編碼量化器預測器一般是一個小于1的預測系數(shù)。例如：量化器設(shè)：

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

=1，

=6.5計算：兩個像素

f0=14、f1=15，則：有損預測編碼——DPCM(預測結(jié)果)(預測誤差)(預測誤差)(重構(gòu)結(jié)果)(重構(gòu)誤差)

輸入 編碼解碼誤差nf^feef^fff-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、預測器的一般模型可以是固定的，也可以是自適應(yīng)的；可以是線性的，也可以是非線性的。預測器設(shè)計得越好，對輸入的數(shù)據(jù)壓縮就越多。五、預測編碼一維線性預測預測器模型選ak使σ2d(n)最小。設(shè)x(n)是廣義平穩(wěn)的，且e(n)均值為0，則預測器模型(1)最佳線性預測假設(shè)x(n)是各態(tài)遍歷的，且訓練樣本數(shù)N相當大，則x(n)的自相關(guān)函數(shù)

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

二維線性預測方程的解a1,a2,…,am

便是一組最佳的預測系數(shù)。壓縮效果可用方差σ2e(n)來衡量，原始序列相關(guān)性越強，R(k)越大，σ2e(n)越小，壓縮效果越顯著；原始序列互不相關(guān)，即R(k)=0，k≠0，則，σ2e(n)=σ2x(n)一點也不能壓縮。預測器模型主要內(nèi)容編碼及信息論概述行程編碼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ù)DCT編碼dctdemo.mDEMO編碼、解碼流程圖符號解碼器逆變換正變換量化器符號編碼器構(gòu)造n×n的子圖合成n×n的子圖輸入圖像N×N壓縮圖像壓縮圖像解壓圖像六、變換編碼構(gòu)造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)的象素的n×n的矩陣；2)Huv的值只依賴坐標變量x,y,u,v，與T(u,v)和f(x,y)的值無關(guān)。被稱為基圖像?？梢栽谧儞Q前一次生成，對每一個n×n的子圖變換都可以使用。六、變換編碼——基本理論基圖像Huv：六、變換編碼——基本理論變換系數(shù)截取模板函數(shù)通過定義變換系數(shù)截取模板函數(shù)，消去冗余。對于：近似：1111

0000111

1

0000111

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

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

0001111

0000111

0000011

0000001

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

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

0

1

00001111

000011

0000001

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

所有子圖使用同一個全局閾值模板，但閾值的選取，與系數(shù)的位置相關(guān)，閾值模板給出了不同位置上系數(shù)的相應(yīng)閾值。例如：六、變換編碼——幾個關(guān)鍵問題2、對系數(shù)的編碼(1)將系數(shù)按45度對角順序展開成序列，得到有一個有長串為零的序列。

例：-19-205216000000000(2)用RLE編碼對上述序列編碼。015614152728247131626294238121725304143

9111824314044531019233239455254202233384651556021343747505659613536484957586263六、變換編碼——幾個關(guān)鍵問題對系數(shù)編碼的展開順序zig-zag排序主要內(nèi)容編碼及信息論概述行程編碼LZW編碼霍夫曼編碼預測編碼變換編碼壓縮標準簡介*七、壓縮標準簡介圖像壓縮標準JPEG——JointPhotographicExpertsGroupMPEG——MovingPictureExpertsGroup靜止幀黑白、彩色壓縮(JPEG)連續(xù)幀單色、彩色壓縮(MPEG)(1)JPEG壓縮標準有三種壓縮系統(tǒng)：(1)基線編碼系統(tǒng)：面向大多數(shù)有損壓縮的應(yīng)用，采用DCT變換壓縮。(2)擴展編碼系統(tǒng)：面向遞進式應(yīng)用，從低分辨率到高分辨率逐步遞進傳遞的應(yīng)用。(3)獨立編碼系統(tǒng)：面向無損壓縮的應(yīng)用，采用無損預測壓縮，符號編碼采用哈夫曼或算術(shù)編碼。一個產(chǎn)品或系統(tǒng)必須包括對基線系統(tǒng)的支持。符號解碼器DCT逆變換量化器DCT正變換構(gòu)造8x8的子圖輸入圖像N×N符號編碼器壓縮圖像壓縮的圖像合成8x8的子圖解壓圖像顏色空間轉(zhuǎn)換零偏置轉(zhuǎn)換顏色空間轉(zhuǎn)換零偏置轉(zhuǎn)換JPEG壓縮標準JPEG壓縮流程MPEG1/2/4/7標準MPEG1/2/4/7標準由ISO/IEC制定的。ISO(InternationalOrganizationforStandardization)是國際標準化組織。

IEC(InternationalElectrotechnicalCommission)是國際電工委員會，是非政府性國際組織，是世界上成立最早的專門國際標準化機構(gòu),正式成立于1906年。MPEG的第一個成果MPEG-1于1992年推出，是VCD的基礎(chǔ)。由于有限的352×288像素分辨率，MPEG-1只適用于家庭環(huán)境，獲得的視頻質(zhì)量及數(shù)據(jù)率相當?shù)汀?995推出MPEG-2。720×576的像素以及更高的分辨率大大提高了視頻質(zhì)量。1999年12月發(fā)布了MPEG-4。MPEG-7為多媒體內(nèi)容描述接口標準。從MPEG組織成立至今，其任務(wù)和方向都發(fā)生了很多變化。MPEG-1和MPEG-2已經(jīng)是成熟的編碼標準，現(xiàn)在的熱點主要集中在MPEG-4和MPEG-7上。MPEG1/2/4/7標準簡介MPEG1/2/4/7MPEG1視頻CD_ROM存儲、視頻消費。DCT變換前向、雙向運動補償預測Zig-zag排序霍夫曼編碼、算術(shù)編碼每15幀至少要有一個I幀應(yīng)用范圍：編碼技術(shù)MPEG1/2/4/7DCT變換前向、雙向運動補償預測zig-zag排序霍夫曼編碼、算術(shù)編碼每15幀至少要有一個I幀編碼技術(shù)應(yīng)用范圍：數(shù)字電視、高質(zhì)量視頻、有線電視、視頻編輯、視頻存儲。MPEG2MPEG1/2/4/7應(yīng)用范圍：互聯(lián)網(wǎng)、交互視頻、移動通信。DCT變換、小波變換前向、雙向運動補償預測zig-zag排序臉部動畫、背景編碼霍夫曼編碼、算術(shù)編碼每15幀至少要有一個I幀編碼技術(shù)MPEG4MPEG1/2/4/71998年10月被提出，它的正式名稱是“多媒體內(nèi)容描述借口”。其用途非常廣泛：即可用于存儲(在線或離線)，也可應(yīng)用于流式結(jié)構(gòu)(如廣播、將模型假如Internet)。還可用于實時或非實時環(huán)境下。

MPEG7音視數(shù)據(jù)庫的存儲和檢索；廣播媒體的選擇（廣播、電視節(jié)目）；因特網(wǎng)上的個性化新聞服務(wù)；智能多媒體；教育領(lǐng)域的應(yīng)用；遠程購物；社會和文化服務(wù)；調(diào)查服務(wù)遙感；監(jiān)視；生物醫(yī)學應(yīng)用；建筑、不動產(chǎn)及內(nèi)部設(shè)計等。MPEG-7的應(yīng)用領(lǐng)域H.261/263/264H.261/263H.261/263標準是由CCITT(國際電話與電報咨詢委員會)制定的。CCITT現(xiàn)在被稱為ITU-T(國際標準化組織電訊標準化分部)，是世界上主要的制定和推廣電訊設(shè)備和系統(tǒng)標準的國際組織.它位于瑞士的geneva。H.261/263/264應(yīng)用范圍：ISDN視頻會議。DCT變換前向運動補償預測zig-zag排序臉部動畫、背景編碼霍夫曼編碼編碼技術(shù)運動補償H.261H.261/263/264應(yīng)用范圍：可視電話。DCT變換雙向運動補償預測zig-zag排序臉部動畫、背景編碼霍夫曼編碼編碼技術(shù)H.263H.261/263/264H.264是ISO/IECMPEG(運動圖