多媒體數(shù)據(jù)壓縮與編碼技術(shù)

第4章多媒體數(shù)據(jù)壓縮與編碼技術(shù)本章重點(diǎn)：編碼模型編碼壓縮方法分類統(tǒng)計(jì)編碼的基本原理預(yù)測(cè)編碼的基本原理變換編碼的基本原理視頻編碼的基本原理第一頁(yè)，共七十七頁(yè)。?第4章多媒體數(shù)據(jù)壓縮與編碼技術(shù)4.1編碼壓縮的必要性與可能性4.2編碼模型4.3編碼壓縮方法分類4.4統(tǒng)計(jì)編碼4.5預(yù)測(cè)編碼4.6變換編碼4.7其他編碼4.8視頻編碼4.9本章小結(jié)第二頁(yè)，共七十七頁(yè)。?4.1編碼壓縮的必要性與可能性4.1.1編碼壓縮的必要性4.1.2編碼壓縮的可能性

第三頁(yè)，共七十七頁(yè)。?4.1.1編碼壓縮的必要性眾所周知，圖像量化所需數(shù)據(jù)量大。圖像和視頻的龐大數(shù)據(jù)對(duì)計(jì)算機(jī)的處理速度、存儲(chǔ)容量都提出過高的要求。因此必須進(jìn)行數(shù)據(jù)量壓縮。從傳送的角度來看，在信道帶寬、通信鏈路容量一定的前提下，采用編碼壓縮技術(shù)，減少傳輸數(shù)據(jù)量，是提高通信速度的重要手段。因此，更要求數(shù)據(jù)量壓縮。第四頁(yè)，共七十七頁(yè)。?4.1.2編碼壓縮的可能性

眾所周知，視頻由一幀一幀的圖像組成，而圖像的各像素之間，無(wú)論是在行方向還是在列方向，都存在著一定的相關(guān)性，即冗余度。應(yīng)用某種編碼方法提取或減少這些冗余度，便可以達(dá)到壓縮數(shù)據(jù)的目的。常見的靜態(tài)圖像數(shù)據(jù)冗余包括：1.空間冗余這是靜態(tài)圖像存在的最主要的一種數(shù)據(jù)冗余。一幅圖像記錄了畫面上可見景物的顏色。同一景物表面上各采樣點(diǎn)的顏色之間往往存在著空間連貫性，從而產(chǎn)生了空間冗余。

第五頁(yè)，共七十七頁(yè)。?4.1.2編碼壓縮的可能性2.時(shí)間冗余在視頻的相鄰幀間，往往包含相同的背景和移動(dòng)物體，因此，后一幀數(shù)據(jù)與前一幀數(shù)據(jù)有許多共同的地方，即在時(shí)間上存在大量的冗余。3.結(jié)構(gòu)冗余在有些圖像的紋理區(qū)，圖像的像素值存在著明顯的分布模式。例如，方格狀的地板圖案等。我們稱這種冗余為結(jié)構(gòu)冗余。4.知識(shí)冗余有些圖像的理解與某些知識(shí)有相當(dāng)大的相關(guān)性。例如，人臉的圖像有固定的結(jié)構(gòu)。這類第六頁(yè)，共七十七頁(yè)。?4.1.2編碼壓縮的可能性

規(guī)律性的結(jié)構(gòu)可由先驗(yàn)知識(shí)和背景知識(shí)得到，我們稱此類冗余為知識(shí)冗余。5.視覺冗余事實(shí)表明，人類的視覺系統(tǒng)對(duì)圖像場(chǎng)的敏感性是非均勻的和非線性的。然而，在記錄原始圖像數(shù)據(jù)時(shí)，通常假定視覺系統(tǒng)是線性的和均勻的，對(duì)視覺敏感和不敏感的部分同等對(duì)待，從而產(chǎn)生了比理想編碼更多的數(shù)據(jù)，這就是視覺冗余。6.圖像區(qū)域的相同性冗余

是指在圖像中的兩個(gè)或多個(gè)區(qū)域所對(duì)應(yīng)的所有第七頁(yè)，共七十七頁(yè)。?4.1.2編碼壓縮的可能性像素值相同或相近，從而產(chǎn)生的數(shù)據(jù)重復(fù)性存儲(chǔ)，這就是圖像區(qū)域的相似性冗余。

7.紋理的統(tǒng)計(jì)冗余有些圖像紋理盡管不嚴(yán)格服從某—分布規(guī)律，但是它在統(tǒng)計(jì)的意義上服從該規(guī)律。利用這種性質(zhì)也可以減少表示圖像的數(shù)據(jù)量，所以我們稱之為紋理的統(tǒng)計(jì)冗余。

第八頁(yè)，共七十七頁(yè)。?4.2編碼模型

4.2.1信源編碼器和信源解碼器4.2.2信道編碼器和解碼器第九頁(yè)，共七十七頁(yè)。?4.2編碼模型

如圖4.1所示，一個(gè)壓縮系統(tǒng)包括兩個(gè)不同的結(jié)構(gòu)塊：一個(gè)編碼器和一個(gè)解碼器。圖像f（x，y）輸入到編碼器中，這個(gè)編碼器可以根據(jù)輸入數(shù)據(jù)生成一組符號(hào)。在通過信道進(jìn)行傳輸之后，將經(jīng)過編碼的表達(dá)符號(hào)送入解碼器，經(jīng)過重構(gòu)后，就生成了輸出圖像。

第十頁(yè)，共七十七頁(yè)。?4.2.1信源編碼器和信源解碼器

信源編碼器的任務(wù)是減少或消除輸入圖像中的冗余。編碼的框圖如圖下圖(a)所示。從原理來看主要分為三個(gè)階段，第一階段將輸入數(shù)據(jù)轉(zhuǎn)換為可以減少輸入圖像中像素間冗余的數(shù)據(jù)的集合。第二階段設(shè)法去除原圖象信號(hào)的相關(guān)性，例如對(duì)電視信號(hào)就可以去掉幀內(nèi)各種相關(guān)，還可以去除幀間相關(guān)。這樣有利

第十一頁(yè)，共七十七頁(yè)。?4.2.1信源編碼器和信源解碼器于編碼壓縮。第三階段就是找一種更近于熵，又利于計(jì)算機(jī)處理的編碼方式。

下圖(b)中顯示的信源解碼器僅包含兩部分：一個(gè)符號(hào)解碼器和一個(gè)反向轉(zhuǎn)換器。這些模塊的運(yùn)行次序與編碼器的符號(hào)編碼器和轉(zhuǎn)換模塊的操作次序相反。第十二頁(yè)，共七十七頁(yè)。?4.2.2信道編碼器和解碼器

當(dāng)信道帶有噪聲或易于出現(xiàn)錯(cuò)誤時(shí)，信道編碼器和解碼器就在整個(gè)譯碼解碼處理中扮演了重要的角色。最有用的—種信道編碼技術(shù)是由R．w．Hamming提出的。該技術(shù)基于這樣的思想，即向被編碼數(shù)據(jù)中加入足夠的位數(shù)以確?？捎玫拇a字間變化的位數(shù)最小。例如，利用Hamming碼將3位冗余碼加到4位字上，使得任意兩個(gè)有效碼字間的距離為3，則所有的一位錯(cuò)誤都可以檢測(cè)出來并得到糾止。與4位二進(jìn)制數(shù)b3b2b1b0相聯(lián)系的7位Hamming(7，4)碼字

第十三頁(yè)，共七十七頁(yè)。?4.2.2信道編碼器和解碼器h1h2…h(huán)5h6h7是：這里表示異或運(yùn)算。h1，h2和h4位分別是位字段b3b2b0，b3b1b0和b2b1b0的偶校驗(yàn)位。

第十四頁(yè)，共七十七頁(yè)。?4.2.2信道編碼器和解碼器為了將漢明（Hamming）編碼結(jié)果進(jìn)行解碼，信道解碼器必須為先前設(shè)立的偶校驗(yàn)的各個(gè)位字段進(jìn)行奇校驗(yàn)并檢查譯碼值。一位錯(cuò)誤由一個(gè)非零奇偶校驗(yàn)字c4c2c1給出，這里，第十五頁(yè)，共七十七頁(yè)。?4.3編碼壓縮方法分類

數(shù)據(jù)壓縮的目標(biāo)是去除各種冗余。根據(jù)壓縮后是否有信息丟失，多媒體數(shù)據(jù)壓縮技術(shù)可分為無(wú)損壓縮技術(shù)和有損壓縮技術(shù)兩類。數(shù)據(jù)壓縮編碼分類如圖4.3所示。常見的無(wú)損壓縮技術(shù)有：霍夫曼編碼算術(shù)編碼行程編碼詞典編碼

第十六頁(yè)，共七十七頁(yè)。?4.3編碼壓縮方法分類

常用的一些有損壓縮技術(shù)包括：預(yù)測(cè)編碼變換編碼基于模型編碼分形編碼其他編碼第十七頁(yè)，共七十七頁(yè)。?4.3編碼壓縮方法分類第十八頁(yè)，共七十七頁(yè)。?4.4統(tǒng)計(jì)編碼

統(tǒng)計(jì)編碼屬無(wú)損編碼，它是根據(jù)消息出現(xiàn)概率的分布特性而進(jìn)行的壓縮編碼。統(tǒng)計(jì)編碼又可分為定長(zhǎng)碼和變長(zhǎng)碼。常用的統(tǒng)計(jì)編碼有Huffman編碼、行程編碼和算術(shù)編碼三種。

4.4.1哈夫曼（Huffman）編碼4.4.2香農(nóng)-費(fèi)諾編碼4.4.3算術(shù)編碼4.4.4游程編碼（RLC）4.4.5LZW編碼第十九頁(yè)，共七十七頁(yè)。?4.4.1哈夫曼（Huffman）編碼

在一幅圖像中，有些圖像數(shù)據(jù)出現(xiàn)的頻率高，有些圖像數(shù)據(jù)出現(xiàn)的頻率低。如果對(duì)那些出現(xiàn)頻率高的數(shù)據(jù)用較少的位數(shù)來表示，而出現(xiàn)頻率低的數(shù)據(jù)用較多的位數(shù)來表示，這樣從總的效果來看還是節(jié)省了存儲(chǔ)空間。這種編碼思想首先由香農(nóng)（Shannon）提出，哈夫曼后來對(duì)它提出了一種改進(jìn)的編碼方法，用這種方法得到的編碼稱為Huffman編碼，Huffman編碼是一種變長(zhǎng)編碼。

第二十頁(yè)，共七十七頁(yè)。?4.4.1哈夫曼（Huffman）編碼1.理論基礎(chǔ)一個(gè)事件集合x1,x2,…，xn處于一個(gè)基本概率空間，其相應(yīng)概率為p1,p2,…，pn，且p1+p2+…pn=1。每一個(gè)信息的信息量為（4-3）定義在概率空間中每—事件的概率不相等時(shí)的平均信息量為信息熵，則信息熵H可采用如下公式計(jì)算：（4-4）

第二十一頁(yè)，共七十七頁(yè)。?4.4.1哈夫曼（Huffman）編碼【例4.1】信息熵的計(jì)算。設(shè)8個(gè)隨機(jī)變量具有同等概率為1/8，則熵：即計(jì)算出H=3比特。2.Huffman編碼Huffman編碼是1952年由Huffman提出的一種編碼方法。它在變長(zhǎng)編碼方法中是最佳的。第二十二頁(yè)，共七十七頁(yè)。?4.4.1哈夫曼（Huffman）編碼設(shè)信源A的信源空間為：其中，現(xiàn)用r個(gè)碼符號(hào)的碼符號(hào)集

對(duì)信源A中的每個(gè)符號(hào)（i＝1，2，…，N）進(jìn)行編碼。具體編碼的方法是：(1)把信源符號(hào)按其出現(xiàn)概率的大小順序排列起來；(2)把最末兩個(gè)具有最小概率的元素之概率加起來；

第二十三頁(yè)，共七十七頁(yè)。?4.4.1哈夫曼（Huffman）編碼(3)把該概率之和同其余概率由大到小排隊(duì)，然后再把兩個(gè)最小概率加起來，再重新排隊(duì)；重復(fù)步驟,直到最后只剩下兩個(gè)概率為止。在上述工作完畢之后，從最后兩個(gè)概率開始逐步向前進(jìn)行編碼。對(duì)于概率大的賦予0，小的賦予1。第二十四頁(yè)，共七十七頁(yè)。?4.4.1哈夫曼（Huffman）編碼第二十五頁(yè)，共七十七頁(yè)。?4.4.1哈夫曼（Huffman）編碼經(jīng)霍夫曼編碼后，平均碼長(zhǎng)為：

=0.4×1＋0.30×2＋0.1×4+0.06×5+0.04×5=2.20（bit）第二十六頁(yè)，共七十七頁(yè)。?4.4.1哈夫曼（Huffman）編碼3.Huffman編碼的幾點(diǎn)說明（1）Huffman編碼是最佳的，雖然構(gòu)造出來的碼不唯一，但其平均碼長(zhǎng)卻相同，所以不影響編碼效率和數(shù)據(jù)壓縮性能。（2）由于Huffman碼的碼長(zhǎng)參差不齊，因此，存在一個(gè)輸入、輸出速率匹配問題。解決的辦法是設(shè)置一定容量的緩沖存儲(chǔ)器。（3）Huffman碼在存儲(chǔ)或傳輸過程中，如果出現(xiàn)誤碼，可能會(huì)引起誤碼的連續(xù)傳播，1bit的誤碼可能把一大串碼字全部破壞，因此，限制了Huffman碼的使用。第二十七頁(yè)，共七十七頁(yè)。?4.4.1哈夫曼（Huffman）編碼

（4）Huffman編碼對(duì)不同信源其編碼效率也不盡相同。當(dāng)信源概率是2的負(fù)次冪時(shí)，Huffman碼的編碼效率達(dá)到100％；當(dāng)信源概率相等時(shí)，其編碼效率最低。這表明在使用Huffman方法編碼時(shí)，只有當(dāng)信源概率分布很不均勻時(shí)，Huffman碼才會(huì)收到顯著的效果。（5）Huffman編碼應(yīng)用時(shí)，均需要與其他編碼結(jié)合起來使用，才能進(jìn)一步提高數(shù)據(jù)壓縮比。例如，在靜態(tài)圖像處理標(biāo)準(zhǔn)JPEG中，先對(duì)圖像像素進(jìn)行DCT變換、量化、Z形掃描、游程編碼后，再進(jìn)行霍夫曼編碼。第二十八頁(yè)，共七十七頁(yè)。?4.4.2香農(nóng)-費(fèi)諾編碼

具體編碼方法如下：（1）把按概率由大到小、從上到下排成一列，然后把分成兩組，，并使這兩組符號(hào)概率和相等或幾乎相等，即：（2）把兩組分別按0，1賦值,例如將第一組賦值為0，則第二組賦值為1。然后分組、賦值，不斷反復(fù)，直到每組只有一種輸入為止。將每個(gè)所賦的值依次排列起來就是香農(nóng)-費(fèi)諾編碼。第二十九頁(yè)，共七十七頁(yè)。?4.4.2香農(nóng)-費(fèi)諾編碼

以前面的數(shù)據(jù)為例，香農(nóng)-編碼費(fèi)諾如圖4.5所示。第三十頁(yè)，共七十七頁(yè)。?4.4.3算術(shù)編碼

理論上，用Huffman方法對(duì)源數(shù)據(jù)流進(jìn)行編碼可達(dá)到最佳編碼效果。但由于計(jì)算機(jī)中存儲(chǔ)、處理的最小單位是“位”，因此，在一些情況下，實(shí)際壓縮比與理論壓縮比的極限相去甚遠(yuǎn)。算術(shù)編碼把要壓縮處理的整段數(shù)據(jù)映射到—段實(shí)數(shù)半開區(qū)間[0，1]內(nèi)的某一區(qū)段，構(gòu)造出小于1且大于或等于0的數(shù)值。這個(gè)數(shù)值是輸入數(shù)據(jù)流的唯—可譯代碼。

第三十一頁(yè)，共七十七頁(yè)。?4.4.3算術(shù)編碼下面通過一個(gè)例子來說明算術(shù)編碼的方法。對(duì)一個(gè)5符號(hào)信源A＝{a1，a2，a3，a2，a4}，各字符出現(xiàn)的概率和設(shè)定的取值范圍如下表4.2：

第三十二頁(yè)，共七十七頁(yè)。?4.4.3算術(shù)編碼為討論方便起見，假定有式中Ns為新子區(qū)間的起始位置；Fs為前子區(qū)間的起始位置，Cl當(dāng)前符號(hào)的區(qū)間左端；Ne為新子區(qū)間的結(jié)束位置；Fe為前子區(qū)間的結(jié)束位置；Cr當(dāng)前符號(hào)的區(qū)間右端；L為前子區(qū)間的長(zhǎng)度。按上述區(qū)間的定義，最終結(jié)果如表4.3：

第三十三頁(yè)，共七十七頁(yè)。?4.4.3算術(shù)編碼

給定事件序列的算術(shù)編碼步驟如下：（1）編碼器在開始時(shí)將“當(dāng)前間隔”[L，H]設(shè)置為[0，1）。（2）對(duì)每一事件，編碼器按步驟（a）和（b）進(jìn)行處理第三十四頁(yè)，共七十七頁(yè)。?4.4.3算術(shù)編碼

（a）編碼器將“當(dāng)前間隔”分為子間隔，每一個(gè)事件一個(gè)。（b）一個(gè)子間隔的大小與下一個(gè)將出現(xiàn)的事件的概率成比例，編碼器選擇子間隔對(duì)應(yīng)于下一個(gè)確切發(fā)生的事件相對(duì)應(yīng)，并使它成為新的“當(dāng)前間隔”。最后輸出的“當(dāng)前間隔”的下邊界就是該給定事件序列的算術(shù)編碼。第三十五頁(yè)，共七十七頁(yè)。?4.4.3算術(shù)編碼在算術(shù)編碼中有幾個(gè)問題需要注意：由于實(shí)際的計(jì)算機(jī)的精度不可能無(wú)限長(zhǎng)，一個(gè)明顯的問題是運(yùn)算中出現(xiàn)溢出，但多數(shù)機(jī)器都有16、32或者64位的精度，因此這個(gè)問題可使用比例縮放方法解決。

算術(shù)編碼器對(duì)整個(gè)消息只產(chǎn)生一個(gè)碼字，這個(gè)碼字是在間隔[0，1]中的一個(gè)實(shí)數(shù)，因此譯碼器在接收到表示這個(gè)實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。算術(shù)編碼也是一種對(duì)錯(cuò)誤很敏感的編碼方法，如果有一位發(fā)生錯(cuò)誤就會(huì)導(dǎo)致整個(gè)消息譯錯(cuò)。

第三十六頁(yè)，共七十七頁(yè)。?4.4.4游程編碼（RLC）

游程編碼是一種利用空間冗余度壓縮圖像的方法，相對(duì)比較簡(jiǎn)單，也屬于統(tǒng)計(jì)編碼類。設(shè)圖像中的某一行或某一塊像素經(jīng)采樣或經(jīng)某種方法變換后的系數(shù)為，如圖4.7所示。某一行或某一塊內(nèi)像素值可分為k段，長(zhǎng)度為的連續(xù)串，每個(gè)串具有相同的值，那么，該圖像的某一行或某一塊可由下面偶對(duì)來表示：，其中為每個(gè)串內(nèi)的代表值，為串的長(zhǎng)度。

第三十七頁(yè)，共七十七頁(yè)。?4.4.4游程編碼（RLC）

第三十八頁(yè)，共七十七頁(yè)。?4.4.4游程編碼（RLC）

串長(zhǎng)li就是游程長(zhǎng)度（Run-length），簡(jiǎn)寫為RL，即由字符或采樣值或灰度值構(gòu)成的數(shù)據(jù)流中各個(gè)字符等重復(fù)出現(xiàn)而形成的字符串的長(zhǎng)度?；窘Y(jié)構(gòu)如圖4.8所示。

第三十九頁(yè)，共七十七頁(yè)。?4.4.4游程編碼（RLC）

游程編碼分為定長(zhǎng)游程編碼和變長(zhǎng)游程編碼兩類。定長(zhǎng)游程編碼是指RL位數(shù)是固定的。變長(zhǎng)游程編碼是指RL位數(shù)是不固定的。游程編碼一般不直接應(yīng)用于多灰度圖像，但比較適合于二值圖像的編碼。例如黑白傳真圖像的編碼等。為了達(dá)到較好的壓縮效果，有時(shí)游程編碼和其他一些編碼方法混合使用。定義游程和游程長(zhǎng)度后，就可以把任何二元序列變換成游程長(zhǎng)度的序列，簡(jiǎn)稱游程序列。這一變換是可逆的，一一對(duì)應(yīng)的。第四十頁(yè)，共七十七頁(yè)。?4.4.5LZW編碼

LZW壓縮編碼是一種無(wú)損壓縮編碼。LZW的基本思想是用符號(hào)代替一串字符，這一串字符可以是有意義的，也可以是無(wú)意義的。在編碼中僅僅把字符串看成是一個(gè)號(hào)碼，而不去管它代表什么意思。1.編碼算法

LZW編碼是圍繞稱為詞典的轉(zhuǎn)換表來完成的。這張轉(zhuǎn)換表用來存放稱為前綴（Prefix）的字符序列，并且為每個(gè)表項(xiàng)分配一個(gè)碼字（Codeword），或者叫做序號(hào)。

第四十一頁(yè)，共七十七頁(yè)。?4.4.5LZW編碼LZW編碼算法的具體執(zhí)行步驟如下：步驟1：開始時(shí)的詞典包含所有可能的根（Root），而當(dāng)前前綴P是空的；步驟2：當(dāng)前字符（C）：=字符流中的下一個(gè)字符；步驟3：判斷綴-符串P+C是否在詞典中如果“是”：P：=P+C，即用C擴(kuò)展P）；如果“否”把代表當(dāng)前前綴P的碼字輸出到碼字流；把綴-符串P+C添加到詞典；令P：=C，即現(xiàn)在的P僅包含一個(gè)字符C；步驟4：判斷碼字流中是否還有碼字要譯如果“是”，就返回到步驟2；如果“否”把代表當(dāng)前前綴P的碼字輸出到碼字流；結(jié)束。LZW編碼算法可用偽碼表示。開始時(shí)假設(shè)編碼詞典包含若干個(gè)已經(jīng)定義的單個(gè)碼字。

第四十二頁(yè)，共七十七頁(yè)。?4.4.5LZW編碼【例4.4】256個(gè)字符的碼字的偽碼形式表示：Dictionary[j]←allnsingle-character，j＝1，2，…，nj←n+1Prefix←readfirstCharacterinCharstreamwhile（（C←nextCharacter）!=NULL）BeginIfPrefix.CisinDictionaryPrefix←Prefix.CelseCodestream←cWforPrefixDictionary[j]←Prefix.Cj←n+1Prefix←CendCodestream←cWforPrefix第四十三頁(yè)，共七十七頁(yè)。?4.4.5LZW編碼2.譯碼算法LZW譯碼算法中還用到另外兩個(gè)術(shù)語(yǔ)：①當(dāng)前碼字（Currentcodeword）：指當(dāng)前正在處理的碼字，用cW表示，用string.cW表示當(dāng)前綴-符串；②先前碼字（Previouscodeword）：指先于當(dāng)前碼字的碼字，用pW表示，用string.pW表示先前綴-符串。LZW譯碼算法開始時(shí)，譯碼詞典與編碼詞典相同，它包含所有可能的前綴根（roots）。

第四十四頁(yè)，共七十七頁(yè)。?4.4.5LZW編碼LZW譯碼算法的具體執(zhí)行步驟如下：步驟1：在開始譯碼時(shí)詞典包含所有可能的前綴根（Root）；步驟2：cW：=碼字流中的第一個(gè)碼字；步驟3：輸出當(dāng)前綴-符串string.cW到碼字流；步驟4：先前碼字pW：=當(dāng)前碼字cW；步驟5：當(dāng)前碼字cW：=碼字流中的下一個(gè)碼字；步驟6：判斷先前綴-符串string.pW是否在詞典中如果“是”：把先前綴-符串string.pW輸出到字符流；當(dāng)前前綴P：=先前綴-符串string.pW；當(dāng)前字符C：=當(dāng)前前綴-符串string.cW的第一個(gè)字符；把綴-符串P+C添加到詞典；如果“否”：當(dāng)前前綴P：=先前綴-符串string.pW；當(dāng)前字符C：=當(dāng)前綴-符串string.cW的第一個(gè)字符；輸出綴-符串P+C到字符流，然后把它添加到詞典中。步驟7：判斷碼字流中是否還有碼字要譯如果“是”，就返回到步驟4；如果“否”，結(jié)束。第四十五頁(yè)，共七十七頁(yè)。?4.4.5LZW編碼

【例4.6】編碼字符串如表4.6所示，編碼過程如表4.7所示。現(xiàn)說明如下：“步驟”欄表示編碼步驟；“位置”欄表示在輸入數(shù)據(jù)中的當(dāng)前位置；“詞典”欄表示添加到詞典中的綴-符串，它的索引在括號(hào)中；“輸出”欄表示碼字輸出。

第四十六頁(yè)，共七十七頁(yè)。?4.4.5LZW編碼

表4.8解釋了譯碼過程。每個(gè)譯碼步驟譯碼器讀一個(gè)碼字，輸出相應(yīng)的綴-符串，并把它添加到詞典中。例如，在步驟4中，先前碼字（2）存儲(chǔ)在先前碼字（pW）中，當(dāng)前碼字（cW）是（4），當(dāng)前綴-符串

第四十七頁(yè)，共七十七頁(yè)。?4.4.5LZW編碼

string.cW是輸出（“AB”），先前綴-符串string.pW（"B"）是用當(dāng)前綴-符串string.cW（"A"）的第一個(gè)字符，其結(jié)果（"BA"）添加到詞典中，它的索引號(hào)是（6）。

第四十八頁(yè)，共七十七頁(yè)。?4.5預(yù)測(cè)編碼

4.5.1概述4.5.2無(wú)損預(yù)測(cè)編碼4.5.3有損預(yù)測(cè)編碼第四十九頁(yè)，共七十七頁(yè)。?4.5.1概述預(yù)測(cè)編碼是根據(jù)離散信號(hào)之間存在著一定的相關(guān)性，利用前面的一個(gè)或多個(gè)信號(hào)對(duì)下一信號(hào)進(jìn)行預(yù)測(cè)，然后對(duì)實(shí)際值和預(yù)測(cè)值的差（預(yù)測(cè)誤差）進(jìn)行編碼。預(yù)測(cè)編碼中典型的壓縮方法有脈沖編碼調(diào)制（PCM，PulseCodeModulation）、差分脈沖編碼調(diào)制（DPCM，DifferentialPulseCodeModulation）、自適應(yīng)差分脈沖編碼調(diào)制（ADPCM，AdaptiveDifferentialPulseCodeModulation）等。預(yù)測(cè)編碼可分為無(wú)損預(yù)測(cè)編碼和有損預(yù)測(cè)編碼。

第五十頁(yè)，共七十七頁(yè)。?4.5.2無(wú)損預(yù)測(cè)編碼

無(wú)損預(yù)測(cè)編碼器的工作原理圖和預(yù)測(cè)原理如圖4.9和圖4.10所示。其中f（i,j）的預(yù)測(cè)值為，將的差值進(jìn)行無(wú)損熵編碼，熵編碼器可采用霍夫曼編碼或算術(shù)編碼。圖4.10給出了像素（i，j）的預(yù)測(cè)圖，圖中給出了（i，j）的三個(gè)相鄰像素，由先前三點(diǎn)預(yù)測(cè)，定義為：其中a1,a2,a3稱預(yù)測(cè)系數(shù)，都是待定參數(shù)。如果預(yù)測(cè)器中預(yù)測(cè)系數(shù)是固定不變的常數(shù)，稱之為線性預(yù)測(cè)。

第五十一頁(yè)，共七十七頁(yè)。?4.5.2無(wú)損預(yù)測(cè)編碼圖4.9

無(wú)損預(yù)測(cè)編碼器工作原理壓縮源圖像預(yù)測(cè)器熵編碼器編碼表第五十二頁(yè)，共七十七頁(yè)。?4.5.2無(wú)損預(yù)測(cè)編碼

預(yù)測(cè)誤差計(jì)算公式如下：

設(shè)a=f（i,j-1），b=f（i-1,j）,c=f（i-1,j-1），的預(yù)測(cè)方法如圖4.11所示，可有8種選擇方法。

第五十三頁(yè)，共七十七頁(yè)。?4.5.2無(wú)損預(yù)測(cè)編碼第五十四頁(yè)，共七十七頁(yè)。?4.5.2無(wú)損預(yù)測(cè)編碼【例4.7】設(shè)有一幅圖像，f（i-1,j-1），f（i-1,j），f（i,j-1），f（i,j）的灰度值分別為253,252,253,255，用圖4.11第四種選擇方法預(yù)測(cè)

f（i,j）的灰度值，并計(jì)算預(yù)測(cè)誤差。解：

=a+b-c=f（i,j-1）+f（i-1,j）-f（i-1,j-1）=253+252-252=253

預(yù)測(cè)誤差=255-253=2

第五十五頁(yè)，共七十七頁(yè)。?4.5.3有損預(yù)測(cè)編碼

如果不是直接對(duì)差值信號(hào)進(jìn)行編碼，而是對(duì)差值信號(hào)進(jìn)行量化后再進(jìn)行編碼就稱之為有損預(yù)測(cè)編碼。有損預(yù)測(cè)方法有多種，其中差分脈沖編碼調(diào)制（DifferentialPulseCodeModulation，簡(jiǎn)稱DPCM），是一種具有代表性的編碼方法。DPCM系統(tǒng)由編碼器和解碼器組成，它們各有一個(gè)相同的預(yù)測(cè)器。圖像DPCM系統(tǒng)的工作原理如圖4.12所示。系統(tǒng)包括發(fā)送、接收和信道傳輸三個(gè)部分。第五十六頁(yè)，共七十七頁(yè)。?4.5.3有損預(yù)測(cè)編碼第五十七頁(yè)，共七十七頁(yè)。?4.6變換編碼

4.6.1變換編碼的基本原理4.6.2離散余弦變換編碼4.6.3小波變換第五十八頁(yè)，共七十七頁(yè)。?4.6.1變換編碼的基本原理

變換編碼的原理如圖4.13所示。從圖中看出，存儲(chǔ)或傳輸都是在變換域中進(jìn)行的，即傳輸或存儲(chǔ)都不是空域圖像而是變換域系數(shù)。圖4.13變換編碼、解碼原理框圖

第五十九頁(yè)，共七十七頁(yè)。?4.6.2離散余弦變換編碼

DCT計(jì)算復(fù)雜度適中，又具有可分離特性，還有快速算法等特點(diǎn)，所以近年來在圖像數(shù)據(jù)壓縮中，采用離散余弦變換編碼的方案很多，特別是20世紀(jì)80年代迅速崛起的多媒體技術(shù)中，JPEG、MPEG、H.261等壓縮標(biāo)準(zhǔn)，都用到離散余弦變換編碼進(jìn)行數(shù)據(jù)壓縮。二維離散偶余弦正變換公式為：

式中，x,y,u,v＝0，1……，N-1。，當(dāng)u=v=0時(shí)。，當(dāng)u=1，2…，N-1；v=1，2…，N-1時(shí).第六十頁(yè)，共七十七頁(yè)。?4.6.2離散余弦變換編碼二維離散偶余弦逆變換公式為：式中，x,y,u,v＝0，1……，N-1。

，當(dāng)u=v=0時(shí)。，當(dāng)u=1，2…，N-1；v=1，2…，N-1時(shí)。第六十一頁(yè)，共七十七頁(yè)。?4.6.2離散余弦變換編碼從圖4-14可以看出，采用DCT進(jìn)行變換編碼時(shí)，通常首先將原始圖像分成子塊，對(duì)每一子塊經(jīng)正交變換得到變換系數(shù)，并對(duì)變換系數(shù)經(jīng)過量化和取舍，然后采用熵編碼等方式進(jìn)行編碼后，再由信道傳輸?shù)浇邮斩?。在接收端，?jīng)過解碼、反量化、逆變換后，得到重建圖像。第六十二頁(yè)，共七十七頁(yè)。?4.6.3小波變換

小波變換對(duì)圖像的壓縮類似于離散余弦變換，即都是對(duì)圖像進(jìn)行變換。由時(shí)域變換到頻域，然后再量化、編碼、輸出。不同之處在于小波變換是對(duì)整幅圖像進(jìn)行變換；小波變換沒有量化表，它主要依據(jù)變換后各級(jí)分辨率之間的自相似的特點(diǎn)，采用逐級(jí)逼近技術(shù)實(shí)現(xiàn)減少數(shù)據(jù)存儲(chǔ)的目的。小波變換繼承了Fourier分析的優(yōu)點(diǎn)，同時(shí)又克服它的許多缺點(diǎn)，所以它在靜態(tài)和動(dòng)態(tài)圖像壓縮領(lǐng)域得到廣泛的應(yīng)用，并且已經(jīng)成為某些圖像壓縮國(guó)際標(biāo)準(zhǔn)（如MPEG-4）的重要環(huán)節(jié)。

第六十三頁(yè)，共七十七頁(yè)。?4.7其他編碼

4.7.1分形編碼4.7.2矢量量化編碼4.7.3子帶編碼第六十四頁(yè)，共七十七頁(yè)。?4.7.1分形編碼分形編碼與分形幾何相關(guān)。所謂分形幾何就是研究無(wú)限復(fù)雜但具有一定意義下的自相似圖形和結(jié)構(gòu)的幾何學(xué)。分形編碼正是利用分形幾何中自相似的原理來實(shí)現(xiàn)數(shù)據(jù)壓縮的。首先對(duì)圖像進(jìn)行分塊，然后再去尋找各塊之間的相似性，這里相似性的描述主要是依靠仿射變換來確定的，一旦找到了每塊的仿射變換，就保存下這個(gè)仿射變換的系數(shù)，由于每塊的數(shù)據(jù)量遠(yuǎn)大于仿射變換的系數(shù)，因而圖像得以大幅度地壓縮。分形圖像編碼和解碼不夠成熟，產(chǎn)生的壓縮比不夠高。壓縮效果還不十分理想，在當(dāng)前圖像壓縮編碼中還不能占據(jù)主導(dǎo)地位。第六十五頁(yè)，共七十七頁(yè)。?4.7.2矢量量化編碼

矢量量化編碼利用相鄰圖像數(shù)據(jù)間的高度相關(guān)性，將輸入圖像數(shù)據(jù)序列分組，每一組由m個(gè)數(shù)據(jù)構(gòu)成一個(gè)M維矢量，一起進(jìn)行編碼，即一次量化多個(gè)點(diǎn)。根據(jù)香農(nóng)失真率理論，對(duì)于無(wú)記憶信源，矢量量化編碼總是優(yōu)于標(biāo)量量化編碼。矢量量化編碼是有損編碼。第六十六頁(yè)，共七十七頁(yè)。?4.7.3子帶編碼

由于人眼對(duì)不同頻域段的敏感程度不同，圖像信號(hào)可以劃分為不同的頻域段。子帶編碼的基本思想是利用一濾波器組，將采樣將輸入信號(hào)分解為高頻分量和低頻分量，然后分別對(duì)高頻和低頻分量進(jìn)行量化和編碼。解碼時(shí)，高頻分量和低頻分量經(jīng)過插值和共軛濾波器而合成原信號(hào)。第六十七頁(yè)，共七十七頁(yè)。?4.8視頻編碼

4.8.1幀內(nèi)預(yù)測(cè)編碼4.8.2幀間預(yù)測(cè)編碼4.8.3活動(dòng)圖像幀間內(nèi)插第六十八頁(yè)，共七十七頁(yè)。?4.8視頻編碼視頻編碼系統(tǒng)的基本結(jié)構(gòu)如圖4.15所示。

信源模型量化參數(shù)參數(shù)統(tǒng)計(jì)特性重建視頻噪聲輸入視頻分析量化二進(jìn)制編碼編碼器有損過程無(wú)損過程信道綜合反量化二進(jìn)制解碼解碼器圖4.15視頻編碼系統(tǒng)的一般組成第六十九頁(yè)，共七十七頁(yè)。?4.8.1幀內(nèi)預(yù)測(cè)編碼

在視頻預(yù)測(cè)編碼中，主要分為幀內(nèi)預(yù)測(cè)編碼和幀間預(yù)測(cè)編碼。所謂幀內(nèi)預(yù)測(cè)，就是在一個(gè)視頻幀，即一幅圖像內(nèi)進(jìn)行的預(yù)測(cè)。幀內(nèi)預(yù)測(cè)編碼的優(yōu)點(diǎn)是算法簡(jiǎn)單，易于實(shí)現(xiàn)，但壓縮比比較低，因此在視頻圖像壓縮中幾乎不單獨(dú)使用。第七十頁(yè)，共七十七頁(yè)。?4.8.2幀間預(yù)測(cè)編碼

幀間預(yù)測(cè)編碼就是利用視頻圖像幀間的相關(guān)性，即時(shí)間相關(guān)性，來獲得比幀內(nèi)編碼高得多的壓縮比。具有運(yùn)動(dòng)補(bǔ)償?shù)膸g預(yù)測(cè)編碼是視頻壓縮的關(guān)鍵技術(shù)之一，它包括以下幾個(gè)步驟：首先，將圖像分解成相對(duì)靜止的背景和若干運(yùn)動(dòng)的物體，通過運(yùn)動(dòng)估值得到每個(gè)物體的位移矢量；然后，利用位移矢量計(jì)算經(jīng)運(yùn)動(dòng)補(bǔ)償后的預(yù)測(cè)值最后對(duì)預(yù)測(cè)誤差進(jìn)行量化、編碼、傳輸，同時(shí)將位移矢量和圖像分解方式等信息送到接收端。第七十一頁(yè)，共七十七頁(yè)。?4.8.2幀間預(yù)測(cè)編碼

在具有運(yùn)動(dòng)補(bǔ)償?shù)膸g