第四章 預(yù)測編碼和變換編碼

第四章預(yù)測編碼和變換編碼

4.1預(yù)測編碼

4.2變換編碼4.1預(yù)測編碼預(yù)測編碼是數(shù)據(jù)壓縮理論的一個(gè)重要分支。根據(jù)離散信號(hào)之間存在一定相關(guān)性的特點(diǎn)，利用前面的一個(gè)或多個(gè)信號(hào)對(duì)下一個(gè)信號(hào)進(jìn)行預(yù)測，然后對(duì)實(shí)際值和預(yù)測值的差（預(yù)測誤差）進(jìn)行編碼。如果預(yù)測比較準(zhǔn)確，那么誤差信號(hào)就會(huì)很小，就可以用較少的碼位進(jìn)行編碼，以達(dá)到數(shù)據(jù)壓縮的目的。第n個(gè)符號(hào)Xn的熵滿足：n越大考慮更多元素之間的依賴關(guān)系時(shí)，熵值進(jìn)一步降低，得到的熵越接近于實(shí)際信源所含的實(shí)際熵（極限熵）。所以參與預(yù)測的符號(hào)越多，預(yù)測就越準(zhǔn)確，該信源的不確定性就越小，數(shù)碼率就可以降低。原理利用以往的樣本值對(duì)新樣本值進(jìn)行預(yù)測，將新樣本值的實(shí)際值與其預(yù)測值相減，得到誤差值，對(duì)該誤差值進(jìn)行編碼，傳送此編碼即可。理論上數(shù)據(jù)源可以準(zhǔn)確地用一個(gè)數(shù)學(xué)模型表示，使其輸出數(shù)據(jù)總是與模型的輸出一致，因此可以準(zhǔn)確地預(yù)測數(shù)據(jù)，但是實(shí)際上預(yù)測器不可能找到如此完美的數(shù)學(xué)模型；預(yù)測本身不會(huì)造成失真。誤差值的編碼可以采用無失真壓縮法或失真壓縮法。分類無損預(yù)測編碼有損預(yù)測編碼DPCM：差分脈沖調(diào)制預(yù)測，DifferentialPulseCodeModulation：差值脈沖編碼調(diào)制是利用信號(hào)的相關(guān)性找出可以反映信號(hào)變化特征的一個(gè)差值量進(jìn)行編碼。ADPCM：自適應(yīng)差分脈沖調(diào)制預(yù)測，AdaptiveDifferentialPulseCodeModulation4.1.1無損預(yù)測編碼原理整數(shù)舍入預(yù)測器譯碼器預(yù)測器-＋編碼器發(fā)送端接收端Xk^Xkekek^XkXk圖4-1整數(shù)舍入當(dāng)輸入信號(hào)序列X(k＝1，2、…)逐個(gè)進(jìn)入編碼器時(shí)，預(yù)測器根據(jù)若干個(gè)過去的輸入產(chǎn)生當(dāng)前輸入的預(yù)測(估計(jì))值。將預(yù)測器的輸出舍入成最接近的整數(shù)，并用來計(jì)算預(yù)測誤差ek

ek

=

xk-這個(gè)誤差可用符號(hào)編碼器借助變長碼進(jìn)行編碼以產(chǎn)生壓縮信號(hào)數(shù)據(jù)流的下—個(gè)元素。在解碼器方根據(jù)接收到的變長碼字重建預(yù)測誤差，并執(zhí)行以下操作以得到解碼信號(hào)

xk

=ek+借助預(yù)測器將原來對(duì)原始信號(hào)的編碼轉(zhuǎn)換成對(duì)預(yù)測誤差的編碼。在預(yù)測比較準(zhǔn)確時(shí)，預(yù)測誤差的動(dòng)態(tài)范圍會(huì)遠(yuǎn)小于原始信號(hào)序列的動(dòng)態(tài)范圍，所以對(duì)頂測誤差的編碼所需的比持?jǐn)?shù)會(huì)大大減少，這是預(yù)測編碼獲得數(shù)據(jù)壓縮結(jié)果的原因。

在多數(shù)情況下，可通過將M個(gè)先前的值進(jìn)行線性組合以得到預(yù)測值^Xk^Xk^Xk預(yù)測方程式:K>N表示x1,x2,…,xN

的時(shí)序在xk

之前。線性預(yù)測是指預(yù)測方程式的右方是各個(gè)xi的線性函數(shù)：

如果ai

(k)是常數(shù)，則為時(shí)不變線性預(yù)測。最簡單的預(yù)測方程：最佳線性預(yù)測使誤差函數(shù)達(dá)到最小值的預(yù)測方程式叫做最佳線性預(yù)測。求最佳線性預(yù)測的各個(gè)參數(shù)ai，列方程組：代入得到聯(lián)立方程組，解方程定出ai。量化器預(yù)測器譯碼器預(yù)測器－＋＋編碼器發(fā)送端接收端Xkek^XkXk’ek’ek’^XkXk’4.1.2有損預(yù)測編碼原理（DPCM）^Xkxk’=ek’+圖4-2在無損預(yù)測編碼系統(tǒng)的基礎(chǔ)上加一個(gè)量化器構(gòu)成壓縮過程發(fā)送端預(yù)測器帶有存儲(chǔ)器，把tn時(shí)刻以前的采樣值x1,x2,x3,…,xk-1存儲(chǔ)起來并據(jù)此對(duì)xk進(jìn)行預(yù)測，得到預(yù)測值ek為xn與的差值，ek’為ek經(jīng)量化器量化的值xk’是接收端的輸出信號(hào)誤差ek為ek=xk-xk’=xk-(+ek’)=(xk-)-ek’=ek

-ek’實(shí)際上就是發(fā)送端的量化器對(duì)誤差ek’量化的誤差對(duì)

ek’的量化越粗糙，壓縮比越高，失真越大.^Xk^Xk^Xk^Xk有損預(yù)測編碼（DPCM）為接納量化步驟，需要改變圖4-1中的無損編碼器以使編碼器和解碼器所產(chǎn)生的預(yù)測能相等。為此在圖4-2中將有損編碼器的預(yù)測器放在1個(gè)反饋環(huán)中。這個(gè)環(huán)的輸入是過去預(yù)測和與其對(duì)應(yīng)的量化誤差的函數(shù)

這樣一個(gè)閉環(huán)結(jié)構(gòu)能防止在解碼器的輸出端產(chǎn)生誤差。這里解碼器的輸出也由上式給出。^Xkxk’=ek’+示例一：德爾塔調(diào)制(DM或ΔM)

最簡單的有損預(yù)測編碼方法是德爾塔（或稱增量）調(diào)制(DM或ΔM)方法，早期在數(shù)字電話中采用，是一種最簡單的差值脈沖編碼。其預(yù)測器和量化器分別定義為其中a是預(yù)測系數(shù)(一般小于等于1)，c是1個(gè)正的常數(shù)。因?yàn)榱炕鞯妮敵隹捎脝蝹€(gè)位符表示(輸出只有2個(gè)值)，所以編碼器中的符號(hào)編碼器可以只用長度固定為1比特的碼。由DM方法得到的碼率是1比特／像素。示例：取a＝1和c＝5。設(shè)輸入序列為12，16，12，14，20、32，46，52，50，51，50。編碼開始時(shí)先將第1個(gè)輸入像素直接傳給編碼器。DM編碼失真示例上例的輸入和輸出中顯示出2種有損預(yù)測編碼典型的失真現(xiàn)象。其一，當(dāng)c遠(yuǎn)大于輸入中的最小變化時(shí)，如在n＝0到n＝3的相對(duì)平滑區(qū)間，DM編碼會(huì)產(chǎn)生顆粒噪聲，即誤差正負(fù)波動(dòng)。其二，當(dāng)c遠(yuǎn)小于輸入中的最大變化時(shí)，如在n=5到n=9的相對(duì)陡峭區(qū)間，DM編碼會(huì)產(chǎn)生斜率過載，有較大的誤差。對(duì)大多數(shù)圖像來說，上述2種情況分別會(huì)導(dǎo)致圖像中目標(biāo)邊緣發(fā)生模糊和整個(gè)圖像產(chǎn)生紋狀表面。輸入數(shù)據(jù)不是平穩(wěn)的隨機(jī)過程自適應(yīng)差分脈沖調(diào)制（ADPCM）預(yù)測定期重新調(diào)整預(yù)測器的預(yù)測參數(shù)，使預(yù)測器隨輸入數(shù)據(jù)的變化而變化自適應(yīng)改變量化器的量化階數(shù)，用小量化階量化小差值，大量化階量化大差值分為線性自適應(yīng)預(yù)測與非線性自適應(yīng)預(yù)測兩種4.1.3自適應(yīng)差分脈沖調(diào)制（ADPCM）預(yù)測

自適應(yīng)量化在一定量化級(jí)數(shù)下減少量化誤差或在同樣的誤差條件下壓縮數(shù)據(jù)，根據(jù)信號(hào)分布不均勻的特點(diǎn)，希望系統(tǒng)具有隨輸入信號(hào)的變化區(qū)間足以保持輸入量化器的信號(hào)基本均勻的能力，這種能力叫自適應(yīng)量化。示例二：

ADPCM采用與DPCM相同的預(yù)測器，但對(duì)誤差量化時(shí)采用自適應(yīng)改變量化器的量化階數(shù)的壓縮結(jié)果自適應(yīng)預(yù)測預(yù)測參數(shù)的最佳化依賴信源的特征，要得到最佳預(yù)測參數(shù)顯然是一件繁瑣的工作。而采用固定的預(yù)測參數(shù)往往又得不到較好的性能。為了能使性能較佳，又不致于有太大的工作量，可以采用自適應(yīng)預(yù)測。為了減少計(jì)算工作量，預(yù)測參數(shù)仍采用固定的，但此時(shí)有多組預(yù)測參數(shù)可供選擇，這些預(yù)測參數(shù)根據(jù)常見的信源特征求得。編碼時(shí)具體采用哪組預(yù)測參數(shù)需根據(jù)特征來自適應(yīng)地確定。為了自適應(yīng)地選擇最佳參數(shù)，通常將信源數(shù)據(jù)分區(qū)間編碼，編碼時(shí)自動(dòng)地選擇一組預(yù)測參數(shù)，使該實(shí)際值與預(yù)測值的均方誤差最小。隨著編碼區(qū)間的不同，預(yù)測參數(shù)自適應(yīng)地變化，以達(dá)到準(zhǔn)最佳預(yù)測。示例三：4個(gè)不同的預(yù)測器如下所示其中第4個(gè)預(yù)測器是自適應(yīng)預(yù)測器，它通過計(jì)算圖像的局部方向性來選擇合適的預(yù)測值以達(dá)到保持圖像邊緣的目的。4.1.4圖像信號(hào)的預(yù)測編碼一幅數(shù)字圖像可以看成一個(gè)空間點(diǎn)陣，圖像信號(hào)不僅在水平方向是相關(guān)的，在垂直方向也是相關(guān)的。根據(jù)已知樣值與待預(yù)測樣值間的位置關(guān)系，可以分為：（1）一維預(yù)測（行內(nèi)預(yù)測）：利用同一行上相鄰的樣值進(jìn)行預(yù)測。（2）二維預(yù)測（幀內(nèi)預(yù)測）：利用同一行和前面幾行的數(shù)據(jù)進(jìn)行預(yù)測。一、靜止圖像的二維預(yù)測編碼這種壓縮算法被應(yīng)用到JPEG標(biāo)準(zhǔn)的無損壓縮模式之中，中等復(fù)雜程度的圖像壓縮比可達(dá)到2:1。LosslessJPEGDPCM/HuffmanCodignDPCM/ArithmeticCodingcabx選擇值預(yù)測值0非預(yù)測1a2b3c4a+b-c5a+(b-c)/26b+(a-c)/27(a+b)/2d三鄰域預(yù)測法ResultsDPCMat1.0bppResultsDPCMat2.0bppResultsDPCMat3.0bpp二、活動(dòng)圖像的幀間預(yù)測編碼視頻信號(hào)的冗余度主要體現(xiàn)在空間相關(guān)性（幀內(nèi)）、時(shí)間相關(guān)性（幀間）和色度空間表示上的相關(guān)性。對(duì)于每秒25幀（30）的電視信號(hào)，其相繼幀之間存在極強(qiáng)的相關(guān)性。所以在活動(dòng)圖像序列中可以利用前面的幀來預(yù)測后面的幀，以實(shí)現(xiàn)數(shù)據(jù)壓縮。幀間預(yù)測編碼技術(shù)被廣泛應(yīng)用到H.261、H.263、MPEG-1和MPEG-2等視頻壓縮標(biāo)準(zhǔn)之中。采用預(yù)測編碼的方法消除序列圖像在時(shí)間上的相關(guān)性，即不直接傳送當(dāng)前幀的像素值，而是傳送x和其前一幀或后一幀的對(duì)應(yīng)像素x‘

之間的差值,這稱為幀間預(yù)測。當(dāng)圖像中存在著運(yùn)動(dòng)物體時(shí)，簡單的預(yù)測不能收到好的效果，例如當(dāng)前幀與前一幀的背景完全一樣，只是小球平移了一個(gè)位置，如果簡單地以第k-1幀像素值作為k幀的預(yù)測值，則在實(shí)線和虛線所示的圓內(nèi)的預(yù)測誤差都不為零。如果已經(jīng)知道了小球運(yùn)動(dòng)的方向和速度，可以從小球在k-1幀的位置推算出它在k幀中的位置來，而背景圖像（不考慮被遮擋的部分）仍以前一幀的背景代替，將這種考慮了小球位移的k-1幀圖像作為k幀的預(yù)測值，就比簡單的預(yù)測準(zhǔn)確得多，從而可以達(dá)到更高的數(shù)據(jù)壓縮比。這種預(yù)測方法稱為具有運(yùn)動(dòng)補(bǔ)償?shù)膸g預(yù)測。

三、具有運(yùn)動(dòng)補(bǔ)償?shù)膸g預(yù)測活動(dòng)圖像序列中的一個(gè)畫面可以大致劃分為3個(gè)區(qū)域：背景區(qū)：相鄰兩個(gè)畫面的背景區(qū)基本相同。運(yùn)動(dòng)物體區(qū)：可以視為由前一個(gè)畫面的某一區(qū)域的像素平移而成。（位移矢量）暴露區(qū)：指物體運(yùn)動(dòng)后而顯露出來的曾被遮蓋的背景區(qū)域。運(yùn)動(dòng)補(bǔ)償預(yù)測就是將前一個(gè)畫面的背景區(qū)＋平移后的運(yùn)動(dòng)物體區(qū)作為后一個(gè)畫面的預(yù)測值。運(yùn)動(dòng)補(bǔ)償幀間預(yù)測編碼運(yùn)動(dòng)補(bǔ)償幀間預(yù)測從原理上包括如下幾個(gè)基本步驟：（1）圖像分割：把圖像劃分為靜止的背景和若干運(yùn)動(dòng)的物體，各個(gè)物體可能有不同的位移，但構(gòu)成同一物體的所有像素的位移相同。（2）運(yùn)動(dòng)矢量估值：考察前后兩個(gè)畫面，利用運(yùn)動(dòng)估值算法得到每個(gè)物體的位移矢量。（3）運(yùn)動(dòng)補(bǔ)償：用運(yùn)動(dòng)矢量補(bǔ)償物體的運(yùn)動(dòng)效果再進(jìn)行預(yù)測。（4）編碼：除了對(duì)實(shí)測值與預(yù)測值之間的差值進(jìn)行編碼傳送外，還要傳送位移矢量以及區(qū)域分割信息。運(yùn)動(dòng)補(bǔ)償幀間預(yù)測編碼編碼器運(yùn)動(dòng)補(bǔ)償圖像輸入運(yùn)動(dòng)矢量輸出-譯碼器幀緩存運(yùn)動(dòng)估值預(yù)測誤差輸出4.2變換編碼利用預(yù)測編碼可以去除圖象數(shù)據(jù)的時(shí)間和空間的冗余。它的優(yōu)點(diǎn)是直觀、簡捷、易于實(shí)現(xiàn)，特別是用于硬件實(shí)現(xiàn)。但壓縮能力有限，DPCM一般只能壓縮到2~4bit/像素。變換編碼是進(jìn)行一種函數(shù)變換，映射變換從信號(hào)域變換到另一個(gè)信號(hào)域。預(yù)測編碼希望通過對(duì)信源建模來盡可能的預(yù)測源數(shù)據(jù)；而變換編碼則考慮將原始數(shù)據(jù)變換到另一個(gè)表示空間，使數(shù)據(jù)在新的空間上盡可能相互獨(dú)立，而能量更集中。原理為達(dá)到目的，可以通過不同的路徑——殊途同歸例1：數(shù)學(xué)計(jì)算機(jī)中，經(jīng)常利用某些數(shù)學(xué)函數(shù)略加轉(zhuǎn)換可以找出一條計(jì)算的捷徑。 乘法：1000000X100000＝100000000000

運(yùn)算時(shí)，數(shù)據(jù)很大，可以變成對(duì)數(shù)進(jìn)行加法1000000X100000＝100000000000取對(duì)數(shù)lg106取對(duì)數(shù)lg105取指數(shù)10116＋5＝11算法變換例2：X(t)為模擬輸入信號(hào)，取樣后成為樣本序列{Xk}

現(xiàn)在以n=8為例，即對(duì)（x0,…,x7)進(jìn)行正交變換，可得到Y(jié)L

的8個(gè)輸出值（y0,…,y8).在該坐標(biāo)系中，信息集中在y0,y1,y2三個(gè)值上。例3:對(duì)緩變信號(hào)，相鄰采樣值x1,x2各用3bit編碼，有64種合成可能；x1,x2同時(shí)出現(xiàn)相同等級(jí)的可能性比較高，如綠圈所示（相關(guān)圈）；對(duì)數(shù)據(jù)進(jìn)行正交變換（旋轉(zhuǎn)45o）后，去掉了相關(guān)性，X1’,X2’合成種類減少，達(dá)到了壓縮的效果0X1X2變換去掉相關(guān)性示意圖X1’X2’定義：變換域編碼就是將時(shí)間域信號(hào)(如語聲信號(hào))或空間域信號(hào)(如圖像信號(hào))，變換到另外一些正交矢量空間(即變換域)，產(chǎn)生一批變換系數(shù)，對(duì)系數(shù)進(jìn)行編碼處理原理：信號(hào)在時(shí)域或空域時(shí)信息冗余度大，變換后參數(shù)之間相關(guān)性很小或互不相關(guān)，數(shù)據(jù)量減少。利用人的視覺特性，對(duì)高頻細(xì)節(jié)不敏感，可以濾除高頻系數(shù)，保留低頻系數(shù)，達(dá)到數(shù)據(jù)壓縮的效果。4.2.1變換編碼原理4.2.2變換編碼的系統(tǒng)構(gòu)成原始信號(hào)正變換量化編碼存儲(chǔ)和傳輸解碼反變換重建信號(hào)編碼信號(hào)4.2.3正交變換的討論定義相鄰的n個(gè)信號(hào)樣本看作在n維線性空間中的一個(gè)列向量例4：Walsh-Hadamard變換能量守恒：42+62+52+22=

8.52+1.52+（-2.5）2+0.52=81由Y可逆變換重建X能量集中：可將Y量化為[9，1，-3，0]后重建為[3.56.55.52.5]0.50.5

0.5

0.50.50.5-0.5-0.50.5-0.5-0.50.50.5-0.50.5-0.5X=[4652]A=Y=AX=[8.51.5-2.50.5]例5:二維離散余弦變換DCT變換DCT逆變換正交變換與編碼相關(guān)的性質(zhì)熵保持：極限熵的保持通過正交變換本身并不丟失信息，因此，可以用傳送變換系數(shù)來達(dá)到傳輸信息的目的。能量保持：變換域中的信號(hào)能量與原來空間域中的信號(hào)能量相等。其對(duì)于數(shù)據(jù)壓縮的指導(dǎo)意義在于：只有當(dāng)空間域信號(hào)能量全部轉(zhuǎn)換到某個(gè)變換域后，有限個(gè)空間取樣值才能完全由有限個(gè)變換系數(shù)對(duì)于基矢量的加權(quán)來恢復(fù)。去(解)相關(guān)：正交變換可使強(qiáng)相關(guān)的空間樣值變?yōu)椴幌嚓P(guān)或弱相關(guān)的變換系數(shù)，使得存在于相關(guān)性之中的數(shù)據(jù)冗余度得以去除。在一定條件下甚至可以使這些系數(shù)相互獨(dú)立，從而得到無記憶信源。如果能得到無記憶信源，正交變換具有保熵性，就得到了通常無法得到的原始數(shù)據(jù)塊(如圖像)的極限熵。這預(yù)示著可望達(dá)到更高的壓縮倍數(shù)。能量重新分配與集中：這是正交變換法最重要的優(yōu)點(diǎn)，也是利用它能實(shí)現(xiàn)數(shù)據(jù)壓縮的物理本質(zhì)。此性質(zhì)DPCM并不具備。變換域系數(shù)(除直流系數(shù)外)與DPCM法相同，零和小幅值系數(shù)占絕大多數(shù)．但DPCM的幅度分布在全空間均可能相同，對(duì)每個(gè)殘差均需編碼；而變換法則按統(tǒng)計(jì)規(guī)律集中分布在一定的區(qū)域上，這就使我們可利用先驗(yàn)知識(shí)在質(zhì)量允許的情況下，舍棄一些能量較小者(或者只給其分配較少的位數(shù))，從而使數(shù)據(jù)率有較大的壓縮。關(guān)鍵：如何找A矩陣。4.2.4圖像的正交變換編碼1.變換矩陣的選擇從實(shí)用意義上考慮，必須從去相關(guān)與能量集中性能以及實(shí)現(xiàn)的難易程度（運(yùn)算量）來綜合選擇。只要在性能滿足要求的條件下，盡量選擇簡單的變換。按正交變換運(yùn)算量從大到小排序?yàn)椋篕-L變換→Fourier變換→

DCT→

斜變換→

Walsh-Hadamard

變換按正交變換的能量集中性能從差到好排序?yàn)椋篧alsh-Hadamard

變換→斜變換→

DCT→Fourier變換→

K-L變換能量集中與去相關(guān)性能當(dāng)然以K-L變換為最佳。但由于對(duì)任意實(shí)際的數(shù)據(jù)集合，很難得到K-L變換的結(jié)果，因此常以K-L變換性能作比較標(biāo)準(zhǔn)。2變換域系數(shù)的選擇1）區(qū)域編碼只對(duì)規(guī)定區(qū)域內(nèi)的變換系數(shù)進(jìn)行量化編碼，略去區(qū)域外的系數(shù)。編碼區(qū)域的形狀和大小取決于所需壓縮比的大小、所選用的變換方法、變換塊的大小等。關(guān)鍵在于選出能量相對(duì)集中的區(qū)域，以便保留大部分圖像能量，使得恢復(fù)圖像的質(zhì)量劣化不顯著。變換域信號(hào)的能量大部分集中在矩陣的左上部，且左上角元素集中的能量最大。這個(gè)現(xiàn)象反映出變換域信號(hào)能量集中于低頻部分。這就是只對(duì)變換域左上部區(qū)域變換系數(shù)進(jìn)行編碼傳輸，對(duì)右下角不進(jìn)行編碼傳輸?shù)囊环N編碼