第四章 預測編碼和變換編碼

第四章預測編碼和變換編碼

4.1預測編碼

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

ek

=

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

xk

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

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

的時序在xk

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

如果ai

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

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

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

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

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

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

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

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

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

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

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

的8個輸出值（y0,…,y8).在該坐標系中，信息集中在y0,y1,y2三個值上。例3:對緩變信號，相鄰采樣值x1,x2各用3bit編碼，有64種合成可能；x1,x2同時出現(xiàn)相同等級的可能性比較高，如綠圈所示（相關圈）；對數(shù)據(jù)進行正交變換（旋轉(zhuǎn)45o）后，去掉了相關性，X1’,X2’合成種類減少，達到了壓縮的效果0X1X2變換去掉相關性示意圖X1’X2’定義：變換域編碼就是將時間域信號(如語聲信號)或空間域信號(如圖像信號)，變換到另外一些正交矢量空間(即變換域)，產(chǎn)生一批變換系數(shù)，對系數(shù)進行編碼處理原理：信號在時域或空域時信息冗余度大，變換后參數(shù)之間相關性很小或互不相關，數(shù)據(jù)量減少。利用人的視覺特性，對高頻細節(jié)不敏感，可以濾除高頻系數(shù)，保留低頻系數(shù)，達到數(shù)據(jù)壓縮的效果。4.2.1變換編碼原理4.2.2變換編碼的系統(tǒng)構成原始信號正變換量化編碼存儲和傳輸解碼反變換重建信號編碼信號4.2.3正交變換的討論定義相鄰的n個信號樣本看作在n維線性空間中的一個列向量例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逆變換正交變換與編碼相關的性質(zhì)熵保持：極限熵的保持通過正交變換本身并不丟失信息，因此，可以用傳送變換系數(shù)來達到傳輸信息的目的。能量保持：變換域中的信號能量與原來空間域中的信號能量相等。其對于數(shù)據(jù)壓縮的指導意義在于：只有當空間域信號能量全部轉(zhuǎn)換到某個變換域后，有限個空間取樣值才能完全由有限個變換系數(shù)對于基矢量的加權來恢復。去(解)相關：正交變換可使強相關的空間樣值變?yōu)椴幌嚓P或弱相關的變換系數(shù)，使得存在于相關性之中的數(shù)據(jù)冗余度得以去除。在一定條件下甚至可以使這些系數(shù)相互獨立，從而得到無記憶信源。如果能得到無記憶信源，正交變換具有保熵性，就得到了通常無法得到的原始數(shù)據(jù)塊(如圖像)的極限熵。這預示著可望達到更高的壓縮倍數(shù)。能量重新分配與集中：這是正交變換法最重要的優(yōu)點，也是利用它能實現(xiàn)數(shù)據(jù)壓縮的物理本質(zhì)。此性質(zhì)DPCM并不具備。變換域系數(shù)(除直流系數(shù)外)與DPCM法相同，零和小幅值系數(shù)占絕大多數(shù)．但DPCM的幅度分布在全空間均可能相同，對每個殘差均需編碼；而變換法則按統(tǒng)計規(guī)律集中分布在一定的區(qū)域上，這就使我們可利用先驗知識在質(zhì)量允許的情況下，舍棄一些能量較小者(或者只給其分配較少的位數(shù))，從而使數(shù)據(jù)率有較大的壓縮。關鍵：如何找A矩陣。4.2.4圖像的正交變換編碼1.變換矩陣的選擇從實用意義上考慮，必須從去相關與能量集中性能以及實現(xiàn)的難易程度（運算量）來綜合選擇。只要在性能滿足要求的條件下，盡量選擇簡單的變換。按正交變換運算量從大到小排序為：K-L變換→Fourier變換→

DCT→

斜變換→

Walsh-Hadamard

變換按正交變換的能量集中性能從差到好排序為：Walsh-Hadamard

變換→斜變換→

DCT→Fourier變換→

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