3.5 預測編碼

預測編碼根據3.2節中介紹的原理，旨在去除相鄰像素之間的冗余度，只對不能預測的信息進行編碼。這里說的“相鄰”可以指像素與它在同一幀圖像內上、下、左、右的像素之間的空間相鄰關系，也可以指該像素與相鄰的前幀、后幀圖像中對應于同一空間位置上的像素之間時間上的相鄰關系。其中后者，即相鄰幀圖像中位于同一坐標位置上的像素，常稱為該像素的同位（co-located）像素。人們在幾十年之前就認識到，電視圖像的相鄰幀之間畫面內容變化甚小，存在著大量的重復信息；另外，圖像亮度、色度的空間分布多是漸變的，同一幀畫面內相鄰像素之間也存在著重復信息。但是，要降低像素間信息的冗余度，以降低對傳輸信道容量的要求，則只有在數字電視中才有了實際實現的可能。

3.5.1 差分脈沖編碼調制（DPCM）

差分脈沖編碼調制簡稱為DPCM（Differential PCM），它是預測編碼的一種基本方式。圖3-13為DPCM的原理方框圖。

輸入信號x（n）是取樣后（沒有量化以前）的圖像信號的樣值，虛線方框內的電路稱為預測器，其中z－i（i＝1，…，N）為延時單元，其延遲時間為i個取樣周期，a1，a2，…，aN為固定的加權系數，其數值在預測器設計中確定。預測器根據前幾個鄰近樣值（數目為N）推算出當前樣值的估計值。Q為量化器。發送端只對預測的誤差信號[即當前的實際樣值x（n）與估計值之差]e（n）進行量化編碼、傳送，而不是傳送x（n）本身。

圖3-13中預測器的輸出為

式中，N稱為預測器的階數。由于等于各輸入樣值的線性疊加，該預測器稱為線性預測器。

在解碼器中有一個相同的預測器，收到的預測誤差信號經解量化器DQ以后，與預測器的輸出相加，從而恢復出原信號。由于在編碼端預測誤差信號已被量化，因此在解碼端所恢復出的信號y（n）只是原信號x（n）的近似值。

由于電視畫面在內容上的連續性，空間域相鄰像素之間有很強的相關性，可以利用這些相關性對當前的像素進行預測。這通常稱為空間域預測。在解碼端，根據前幾個樣值所得到的預測值已經是已知的，如果當前值x（n）與相同，就不需要再傳送新的數據給解碼端了。因此，通過預測將x（n）轉換成e（n），在很大程度上降低了信息源的冗余度，這便是利用DPCM進行數據壓縮的基本原理。

在圖3-14中，X表示被預測的像素，x1，x2，…，x5則是根據不同的預測方案有可能被選擇用來對X進行預測的已知的像素。如果用作預測的樣值與被預測的樣值在同一行內（如圖中的x1、x2與X），稱為一維預測；當用作預測的樣值位于相鄰的不同行上時（如圖中x3、x4與X）則稱為二維預測。

一維預測利用了像素之間在水平方向上的相關性。對水平方向亮度變化緩慢的圖像，有較好的預測效果。如果水平方向上亮度有突變，例如圖3-14所示的圖像是以x1和X為界的黑白條，那么一階的一維預測為

會給出錯誤的預測數值。在這種情況下，采用下面的二維預測給出較好的預測值，即

下面考慮N階預測器的設計問題。預測誤差信號e（n）平方值的統計平均由下式表示：

式中〈 〉表示均值。顯然，〈e2（n）〉最小時，表示在最小均方誤差意義下，預測最準確，此時的預測器稱為在最小均方誤差MMSE（Minimum Mean Square Error）意義下的最佳預測器。最佳預測器的系數ai（i＝1，…，N）可以通過如下求〈e2（n）〉極小值的方法獲得：

將上式用輸入序列的自相關函數R來表示：

如果對需要壓縮的某類圖像的自相關函數已經做過測量的話，則可通過求解（3-40）式所表示的方程組，獲得最佳預測器的系數值。此時的均方誤差值則為

由（3-39）式可知，

于是（3-41）式可簡化為

由上式可以看出，預測誤差的平均功率比原信號的功率R（0）要小。在相同的均方量化誤差下，e（n）比x（n）要求較少的量化級數，因此，傳送e（n）比傳送x（n）的數據率要低。

在圖3-13所示的電路中，量化器處于預測差分環路之外。編碼端利用原始信號為參考進行預測，而在解碼端卻是以量化后的信號為參考進行預測的，這種兩端參考信號不相同的情況，稱為失配，它導致重建信號y（n）與輸入信號x（n）之間存在較大誤差。圖3-15給出了一個嚴格意義上的DPCM原理方框圖，圖中編碼器的反饋環路模擬了解碼端的結構：量化后的預測誤差信號經解量化器后，與預測值相加構成預測器的輸入信號，從而使解碼端重建信號的誤差降低。

3.5.2 序列圖像中運動矢量的估值

1.運動矢量估值的必要性

電視圖像是由在時間上相互間隔為幀周期（1/25s、或1/30s）的一幀幀圖像組成的圖像序列?？梢韵胂?，在拍攝同一場景時，時間上相鄰的兩幅圖像之間在內容上差異不會太大，或者說后一幀的內容與前一幀重復的部分很多。用數學的術語來講，二者是相關的。消除序列圖像在時間上的相關性（冗余度），是視頻信號壓縮編碼的一條重要途徑。

序列圖像在時間上的冗余情況可分為如下幾種：①對于靜止不動的場景，當前幀和前一幀的圖像內容是完全相同的；②對于運動的物體，只要知道其運動規律，就可以從前一幀圖像推算出它在當前幀中的位置來；③攝像鏡頭對著場景進行橫向移動（稱為滑鏡頭）、焦距變化等操作會引起整個圖像的平移、放大或縮小，對于這種情況，只要攝像機的運動規律和鏡頭改變的參數已知，圖像隨時間所產生的變化也是可以推算出來的。由電視圖像的這些特點我們可以想到，發送端不一定必須把每幀圖像上所有的像素都傳給接收端，而只要將物體（或攝像機）的運動信息告知收端，收端就可根據運動信息和前一幀圖像的內容來更新當前幀圖像，這比全部傳送每幀圖像的具體細節所需的數據量小得多。

要這樣做，一個首先需要解決的問題是如何從序列圖像中提取出有關物體運動的信息，這通常稱為運動估值。本節討論的內容就是運動估值的方法。攝像機的運動和參數變化影響到圖像的每個像素，我們將這種由攝像機運動導致的像素位置變化稱為全局運動。本節將不涉及全局運動估值問題，有興趣的讀者可以參考其他文獻。

為了簡單起見，本節介紹的物體運動估值方法基于如下的假設：

（1）物體是剛體，且只在與攝像機鏡頭的光軸（即穿過鏡頭球面中心和球心的軸）垂直的平面內移動。這就是說，物體的形變、旋轉、鏡頭焦距的變更等因素不考慮在內；

（2）無論物體移動到任何位置，照明條件都不變，也就是說，同一物體在所有序列圖像中亮度沒有變化；

（3）被物體遮擋的背景和由于物體移開而新暴露出來的背景部分不做特殊考慮。在上述假設下，t時刻運動物體的像素bt可以用它在時間τ以前的值bt－τ表示出來，即

bt（z）＝bt－τ（z－D）　（3-44）

式中，b代表像素亮度值；z＝（x，y）T為位置矢量，T代表矢量的轉置；D為在時間間隔τ內物體運動的位移矢量（Displacement Vector）。嚴格地講，位移矢量與運動矢量（Motion Vector，MV），在概念上是有區別的，因為位移只是物體運動的一種方式，但由于在當前技術條件下，位移幾乎是進行視頻數據壓縮時所考慮的唯一運動方式，因此在相關的文獻中，常將D稱為運動矢量。上式表示t時刻的圖像是（t－τ）時刻的圖像經適當移位后的結果。因此通過比較相距時間為τ的兩幀圖像可以估計出在這段時間間隔內物體的位移D。根據這一公式進行運動估值的方法主要分為兩大類，分別稱為塊匹配方法和像素遞歸方法。由于塊匹配方法是目前視頻壓縮編碼廣泛采用的方法，因此本節僅針對它進行討論。

2.塊匹配方法

按照一般的想法，運動估值應當首先將圖像中的靜止背景和運動物體區分開來，然后對運動物體的實際位移進行估值，但是從圖像中分割出物體常常是一個困難的任務。為了回避這個困難，在塊匹配方法中，將圖像劃分為許多互不重疊的塊（如16×16），并假設塊內所有像素的位移量都相同。這實際上意味著將每個塊視為一個“運動物體”。假設在圖像序列中，t時刻對應于第k幀圖像，t－τ時刻對應于k－1幀圖像。對于k幀中的一個塊，在k－1幀中找與其最相似的塊，稱為匹配塊，并認為該匹配塊在k－1幀中的位置，就是k幀塊位移前的位置，根據（3-44）式則可以得到該塊的位移矢量D。此時，k－1幀稱為k幀的參考幀。

為了節省計算量，在k－1幀中的匹配搜索只在一定范圍內進行。假設在τ時間間隔內塊的最大可能水平和垂直位移量為dm個像素，則搜索范圍SR為

SR＝（M＋2dm）×（N＋2dm）?。?-45）

式中，M、N分別為塊在水平和垂直方向上的像素數。圖3-16給出了塊與搜索范圍的相對位置關系。顯然，在塊匹配方法中最重要的兩個問題是：判別兩個塊匹配的準則和尋找匹配塊的搜索方法。

對這兩個問題的不同解決方案構成了不同的算法。

判斷兩個塊相似程度的最直接的準則是歸一化的二維互相關函數NCCF，其定義為

式中的時間和位置已用相應的離散量表示，分子為在第k幀中的塊與在k－1幀中與該塊對應位置相差i行、j列的塊之間的互相關函數，分母中括號里的項分別代表這兩個塊各自的自相關函數的峰值。當NCCF為最大值時兩個塊匹配，此時對應的i、j值即構成位移矢量D。

在實際應用中，常常使用如下計算比較簡單的判斷塊匹配的準則：

（1）塊亮度的均方差值（MSE）

（2）塊亮度差的絕對值均值（MAD）

（3）塊亮度差的絕對值和（SAD）

SAD（i，j）＝MN·MAD（i，j） （3-49）

當MSE或MAD或SAD最小時，表示兩個塊匹配。

研究結果表明，匹配判別準則的不同對匹配的精度，也就是對位移矢量估值的精度影響不大。因此，（3-49）式所表示的不含有乘法和除法的SAD準則成為最常使用的匹配判別準則。

為了尋找最佳的匹配塊，我們需要將k－1幀中對應的塊在整個搜索區內沿水平和垂直方向逐個像素移動，每移動一次計算一次判決函數（如SAD）?？偟囊苿哟螖担ㄋ阉鼽c）Q為

Q＝（2dm＋1）2 （3-50）

這種搜索方式稱為全搜索。全搜索的運算量是相當大的。使用SAD為準則時每個像素要進行三個基本運算（相減、求絕對值、求和），對一個塊進行全搜索要求3×（2dm＋1）2×MN次運算。假設視頻圖像的分辨率為NW×NH，則每幀有（NW×NH）/MN個塊，即使在dm＝7、[NW，NH]＝[352，288]和幀率f＝30時，所需的運算量也達到2.05千萬次/秒。一般來說，運動估值的運算量通常占到現行標準下視頻壓縮編碼的60%～80%。

3.塊匹配的快速搜索方法

為了加快搜索過程，人們提出了許多不同的搜索方法。圖3-17所示的三步法是早期提出的一個典型快速搜索算法。它通過降低搜索點的數目來降低算法的計算復雜度。其搜索過程為：第一步，以待匹配塊中心的同位像素（即前一幀中與之位置相同的像素）為中心，在中心點和與其相距4個像素的8個鄰域點上計算判決函數SAD值，取SAD值最小的點作為下一步搜索的中心；第二步，以該點為中心，對與中心相距2個像素的未搜索過的鄰域點進行搜索；第三步，以上一步中SAD值最小的點為中心，對距離中心1個像素的未搜索過的鄰域點進行搜索，最終找到最佳匹配位置。圖中帶有數字的圓圈代表每一步驟中的搜索點，帶有數字的方塊代表該步驟中SAD值最小的位置。本例中，在dm≤7的搜索范圍內，通過三步找到最佳匹配位置（i＋7，j－2）。早期提出的其他算法，如二維對數法、共軛方向法等，與三步法相類似，只是每個步驟搜索點所構成的圖形的形狀和大小不同。

幾乎所有的快速搜索算法都基于如下的假設：當偏離最佳匹配位置（運動矢量D＝Dopt）時，判決函數（匹配誤差）值是單調上升的。因此無需搜索所有的點，只要沿著誤差值減少的方向進行搜索，就能找到最佳匹配位置。圖3-18給出了一維情況下沿誤差曲線搜索的情況（如圖實線上箭頭所示）。但是當誤差曲線非凸時（如圖中虛線示），這種搜索方法則可能落入局部極值點，例如從圖中A點左側任意點沿誤差減小方向的搜索將中止于A點，而不能搜索到最佳匹配位置（全局極小點）。

保證在任何情況下找到全局極值點是一個困難的問題，但是從另一個角度來考慮，在全局極值點的鄰近區域，誤差曲線（二維時為曲面）為凸的假設總是成立的，因此只要有一個搜索點落在全局極值點的附近，搜索到最佳匹配位置的概率就會很大。

根據上述想法，近年來人們提出了許多新的快速搜索算法，具有代表性的有MVFAST，APDZS和EPZS等，它們不僅大大提高了搜索的速度，而且具有與全搜索方法相當的性能。這些算法的基本策略可以概括如下。

（1）運動矢量預測

由于圖像內容的連續性，相鄰塊的運動矢量一般是相近的，換句話說，運動矢量場（運動矢量的分布函數）在空間和時間上一般是平滑、漸變的，因此，我們可以根據已進行過運動估值的相鄰塊的運動矢量（假設它們的估值是正確的），對當前待匹配塊的運動矢量進行預測，然后從預測位置開始進行搜索。如果預測得足夠準確，那么預測點落在誤差曲線的全局極值點附近，這不僅能夠縮短搜索需要的時間，而且使搜索到全局極值點的概率增高。

在圖3-19中，設k幀中灰色塊為當前待匹配的塊，它的MV的預測值可以選擇為：（0，0），或當前塊的左、上和右上三個空間鄰域塊的運動矢量MVL，MVT和MVTR，也可以選擇為這三個MV的中值MVmed，或前一幀同位塊的運動矢量MVC。其他預測值還可以考慮：前一幀同位塊的上、下、左、右4個鄰域塊的MV、前2幀的“加速度”MV＝MVC＋（MVC－MVC2）（見圖3-19），以及上述各預測值的線性組合等。我們將各個MV預測值所確定的一組點作為搜索的候選起始點，計算它們的SAD值，并選擇SAD值最小的點作為最佳起始點；然后以該點為中心類似于三步法那樣，計算規定的搜索圖形上各搜索點的SAD值，并按SAD值減小的方向移動搜索圖形，直至找到最佳匹配位置為止。由于搜索采用了多個候選起始點，所以使得因MV預測不準確而引起的起始點遠離全局極值點的風險降低。

（2）搜索提前中止

所謂“提前中止”是指，在某個搜索點上如果匹配誤差SAD小于預先設定的閾值T，則認為匹配已經足夠好，搜索中止。人們通過研究發現，大多數圖像塊的運動矢量與空間鄰塊運動矢量的中值MVmed相關性最強，與（0，0）、MVL、MVT、MVTR和MVC的相關性次之，與其他MV預測值的相關性則小一些。顯然，先搜索相關性強的預測點，可能較早滿足提前中止的條件，從而提高搜索效率。

提前中止閾值T的選取是一個值得考慮的問題，閾值過小達不到提前中止的目的；過大則搜索不到最佳匹配位置。一般來說，針對不同情況可以設置不同的閾值，例如對相關性強的點，閾值嚴格一些，對相關性弱的點則寬松一些。除了固定閾值之外，還可以動態地選取閾值?？紤]到待匹配塊的SAD值與它的空間鄰域（左、上和上右）和時間鄰域（同位）塊的SAD值之間也存在著相關性，一種動態閾值的選擇方法為

T＝a·min（SADL，SADT，SADTR，SADc）＋b （3-51）

式中，a、b為預定的常數。

（3）緊湊的搜索圖形

在三步法中，為了提高搜索速度，在開始時采用了大尺寸（隔4個像素）的矩形搜索圖形；在搜索趨向于匹配點的過程中，搜索圖形的尺寸逐步減小。由于近年提出的快速算法都進行了不同程度的運動矢量預測，搜索的起始點已經接近于匹配點，因此可以采用緊湊的搜索圖形。圖3-20給出了幾個例子，其中（a）稱為“大鉆石”，在距離匹配點稍遠處使用；（b）為“小鉆石”，在匹配點附近使用。判斷當前搜索點距離匹配點的遠近可以有多種準則，一種常用的辦法是檢查搜索點SAD值的大小。SAD值小意味著接近匹配點，可以使用小尺寸圖形。

上述三種基本策略的不同運用形成了不同的算法。圖3-21給出了一個搜索過程的示例，其中帶有數字的圓圈代表每一個步驟的搜索點，帶有數字的方塊代表該步驟中的SAD值最小的位置（見習題9）。搜索圖形為小鉆石。

3.5.3 具有運動補償的幀間預測

1.前向預測

與消除圖像中相鄰像素間的空間冗余度一樣，消除序列圖像在時間上的相關性，也可以采用預測編碼的辦法，即不直接傳送當前幀（即k幀）的像素值x[見圖3-22（a）]，而傳送x與前一幀（即k－1幀）同位像素x′之間的差值，這稱為幀間預測。對隔行掃描的電視信號，也可以用前一場來預測當前場的像素（場間預測）。當圖像中存在著運動物體時，簡單的預測不能收到好的效果。例如圖3-22（b）中，當前幀與前一幀的背景完全一樣，只是小球平移了一個位置。如果簡單地以k－1幀的同位像素值作為k幀像素的預測值，則在實線和虛線所示的圓內預測誤差都不為零。如果已經知道了小球的位移矢量，可以從小球在k－1幀的位置推算出它在k幀中的位置來，而背景圖像（不考慮被遮擋的部分）仍以前一幀的背景代替。將這種考慮了小球位移的k－1幀圖像作為k幀的預測值，就比簡單的預測準確得多，從而可以達到更高的數據壓縮比。這種預測方法稱為具有運動補償的幀間預測。

從原理上講，具有運動補償的幀間預測應包括如下幾個基本步驟：

（1）將圖像分割成靜止的背景和若干運動的物體，各個物體可能有不同的位移，但構成同一物體的所有像素的位移相同。通過運動估值得到每個物體的位移矢量；

（2）利用位移矢量計算經運動補償后的預測值；

（3）除了對預測誤差進行編碼、傳送以外，還需要傳送位移矢量以及如何進行運動物體和靜止背景分割等方面的附加信息。

圖3-23給出了這種預測器的原理方框圖。圖中向下的虛線箭頭標出分割的結果送進運動估值單元，以便針對不同物體進行位移估值。而向上的虛線箭頭表示用估值的結果和分割的結果一起去控制預測器，以得到經運動補償后的預測圖像。編碼器的最終輸出為幀間預測誤差、位移矢量和分割產生的地址信息等。

如前所述，將圖像分割成靜止區域和不同的運動區域是一項困難的工作，當要求實時地完成這項運算時就更加困難。一種簡化的辦法是將圖像分割成塊，每塊看成是一個物體，按3.5.2節中講的塊匹配的方法估計每個塊的位移矢量，將經過位移補償的幀間預測誤差（Displaced Frame Difference，DFD）和位移矢量D傳送給接收端，接收端就可以按下式從已經收到的前一幀信息中恢復出該塊：

bk（z）＝bk－1（z－D）＋DFD（z，D）?。?-52）

圖3-24中表示出了k幀各塊及它們在k－1幀中對應的匹配塊之間的關系。從該塊的預測誤差和它的位移矢量所指向的k－1幀中的匹配塊，可以恢復出k幀中的塊來。顯然，當一個塊中的像素實際上屬于位移量不同的物體時，這種對整個塊用同一位移作的預測則不夠準確，這將使預測誤差DFD增加，從而影響數據壓縮比的提高。

2.后向預測和雙向預測

上面介紹的用k－1幀預測k幀圖像的預測方式稱為前向預測。如果待預測的塊是在k幀，而搜索區域處于k＋1幀之內，也就是從后續的k＋1幀圖像預測前面的k幀圖像，這種方式稱為后向預測。對于在k－1幀中被覆蓋，而從k幀開始新暴露出的物體（或背景），使用后向預測可以得到更好的預測值。

第三種預測方式是采用前、后兩幀來預測中間幀，這稱為雙向預測。如圖3-25所示，對于k幀中的塊（灰色塊），先從k－1幀中找到它的最佳匹配塊，從而得到該塊從k－1到k幀的位移矢量D1，再利用后向預測得到它從k＋1到k幀的位移矢量D2，然后將經過運動補償的前向預測值或后向預測值，或二者平均值作為k幀塊的預測值（視哪種預測誤差最小而定）。這樣的做法與單純的前向預測相比，可以進一步降低預測誤差，從而提高數據壓縮比。

雙向預測所付出的代價是，對每一個圖像塊需要傳送兩個位移矢量給接收端，而且k幀的恢復必須等到k＋1幀解碼之后才能進行。也就是說，輸入序列的幀順序是k－1、k、k＋1，編碼和解碼運算的幀順序是k－1、k＋1、k，而圖像顯示的順序又是k－1、k、k＋1。要保持處理和顯示的連續性，在編碼端和解碼端分別需要引入一幀的延時。