一種適用于Ｈ．２６４的高效塊匹配運動估計算法

摘 要：提出一種基于節點模型的可變形塊匹配運動估計算法來搜索最佳運動矢量。實驗表明，在編碼性能損失很小的條件下，可以使得運動搜索塊匹配的運算量在通常快速運動搜索算法的基礎上下降61%。

關鍵詞： H.264； 運動估計； 塊匹配

中圖分類號：TN919.81文獻標志碼：A

文章編號：1001—3695(2007)03—0076—03

最新視頻壓縮標準H.264是由ISO/IEC的運動圖像專家組（MPEG）和ITUT的視頻編碼專家組（VCEG）共同制定的，其主要特點是具有更高的編碼效率和更好的網絡適應性。在相同重構圖像質量下，H.264預測精度達到了1/4像素，與H.263和MPEG—4標準相比能節約50％的碼流，但是所帶來的結果是，其運算的復雜度是H.263編碼復雜度的四倍。運動估計模塊是整個編碼模塊中運算量最大的部分，在JVT的文檔中表明運動估計在使用一個參考幀時占整個運算量的70%，在使用五個參考幀時占整個運算量的90%。因此無論在硬件實現還是在軟件實現的過程中，運動估計和補償均占很重要的地位，在一個可行的解決方案中必須對這一部分進行優化和改進。

在深入研究Ｈ.264視頻編碼標準及其運動矢量統計特征的基礎上，提出了采用一種基于節點模型的可變形塊匹配運動估計算法。實驗結果表明，該算法不僅保證了編碼器原有的失真特性，而且還大大降低了運算復雜度與實現上的難度。

1 H. 264運動估計算法分析

Ｈ.264標準的編碼效率之所以比其他標準要高很多，主要是應用了多預測塊匹配和多參考幀預測，H.264同時引入了幀間預測和幀內預測，并且采用宏塊大小可變的多預測塊模式。幀內預測可去除幀內編碼的空間冗余，而幀間預測可去除時間上的冗余度。由于運動圖像時間上的連續性，去除時間上的冗余可獲得更大的壓縮效率，通過運動估計方法去除幀間的冗余，一直是視頻編碼研究的熱點。運動估計方法一般基于塊匹配搜索，現有的視頻編碼標準也都基于DCT(或類DCT)變換。通常將一幀圖像按16×16的圖像塊進行編碼。如在編碼某一Ｐ幀中的一個宏塊M時，在參考幀相應位置的一定范圍內搜索最為匹配的塊R作為宏塊中某一塊M的參考塊，將當前塊M減去參考塊R即可得到運動估計后的殘余矩陣，此殘余矩陣經過變換、量化、熵編碼即得到該宏塊編碼后的碼流，而運動估計也就是搜索匹配塊的過程。 

H.264幀間預測采用了不同大小和形狀的宏塊分割與亞分割方法，支持16×16—4×4的七種預測塊模式，如圖1所示。對于每一種分割塊都有一個對應的運動矢量，編碼器將對每個運動矢量和預測塊模式標志進行編碼和傳輸，解碼器根據預測塊模式標志和運動矢量進行宏塊解碼。

圖1 七種預測塊模式

編碼器對每一種預測塊均進行搜索預測，并利用RDO技術得到一個最佳的預測塊，使編碼預測殘差和運動信息所用的比特數最小。因此在塊匹配運動估計中，運動估計的精度會對碼率產生很大影響，如果能降低計算冗余，那么計算量就會顯著降低。全搜索算法以其極高的精度受到廣泛關注，但由于其要求對搜索窗內所有點進行匹配，所需運算量十分巨大，很難適應實際應用，特別是實時應用的要求。為了追求較高運動估計精度下的較低運算量，人們不斷地提出各種快速算法。概覽這些快速算法，大致可分為以下幾類:①通過在搜索窗內按一定規則，僅搜索較少的幾個點來降低運算復雜度，經典算法有三步法(3SS)、新三步法(N3SS)[1]、四步法(4SS)[2]等；②通過使用相對較為簡單的匹配準則來降低運算復雜度，如最小最大誤差等；③通過利用代數不等式排除不可能成為最佳匹配的待搜索點，從而減少匹配點數，降低運算復雜度，如近兩年提出的一些快速全搜索算法等。

2 H. 264/AVC運動矢量統計特征分析

在視頻序列中，視頻對象的運動具有連續的運動特征，因此描述視頻序列運動特征的宏塊運動矢量間也存在時間和空間上的相關性。而且由于視頻序列運動程度的不同，相鄰宏塊間運動相關性存在非常明顯的變化。這一變化對H.264/AVC編碼結果的影響可以通過對不同視頻序列的宏塊編碼模式進行的統計來看[3]，如表1所示。

可以發現對于運動平滑的視頻序列（Bus序列）或視頻圖像中的平坦區域，宏塊大多采用了大編碼模式，即16×16、16×8和8×16模式；而對于運動劇烈的視頻序列Stefan，編碼時更多的宏塊則采用了小編碼模式，即8×8、8×4、4×8和4×4模式。H.264/AVC采用的七種分塊模式可以在視頻序列不同的運動程度情況下選擇使用，而且可以隨著運動程度的變化，相應地調整模塊的選擇。基于上述分析，本文提出采用一種基于節點模型的可變形塊匹配運動估計算法。

3 基于節點模型的運動估計算法

3.1 基于節點的運動表示

在基于節點的塊運動模型中，假設在塊中所選擇的某個數目的控制節點能夠自由運動，而且任何中間點的位移可以通過節點的位移內插[4]。令K表示控制節點數目，B_m代表第m個圖像塊，dm，k表示B_m中控制節點的運動矢量（MV），則塊的運動函數可以描述為

式（1）表示作為節點位移的內插塊中任意點的位移，如圖2所示。內插核m，k(x)取決于B_m中第k個控制節點所期望的對x的貢獻。一般使用與相應的節點結構有關的行狀函數來設計這種內核。如果采用多節點的模型則可以表征在運動過程中比較復雜的變形。在單節點情況下（在塊中心或一個選擇的角）的內插核是一個脈沖函數，相當于最臨近內插。在三節點（塊的任意三個角）和四節點（四個角）情況下的內插函數分別是仿射函數和雙線性函數。要對矩形塊應用仿射模型，首先要將矩形分成兩個三角形，然后再將每個三角形模型轉換為三節點模型。

當塊的四個角點位置給定后就可以估計出節點的MV，根據關于運動的動態范圍和期望估計精度的先驗知識可以確定出節點MV合適的搜索范圍和搜索步長。而且由于基于節點模型表示中所有的運動參數同等重要，采用整數或半像素精度就可以規定節點的MV。

在這種情況下，每次更新只需要兩個K×K矩陣的求逆即可。在四節點情況下，[H]是一個8×8的矩陣，而[Hxx]和[Hyy]是4×4的矩陣，從而減少了運算復雜度。

本算法的初始值由窮盡搜索塊匹配算法提供，考慮到四節點模型，每一個塊的每一個角都是一個節點，可以用與每個節點相連的四個塊的運動矢量的平均作為這個節點MV的初始估計，然后該初始估計可以由式（5）進行迭代更新。

3.3 搜索中匹配準則的選擇在上述塊匹配算法中采用不同的匹配準則會獲得不盡相同的運動估計結果。采用均方差(MSD)準則的匹配效果優于絕對幀差準則(MAD)，但是在H.264視頻編/解碼系統中，幀間編碼是對運動補償差信號進行編碼，所以MAD的計算次數和復雜度將少于MSD，但會在一定程度上犧牲運動估計的性能。基于以上分析以及H.264視頻編/解碼的特點，本文采用像素差值分類的運動估計匹配準則。

該準則將參考像塊中的每一個像素分類為匹配像素和失配像素進行統計[5]，在運動搜索中選取參考塊中失配像素最少的塊作為匹配塊，可以對保持當前塊與匹配塊形狀的一致性有較強的約束。具體運算過程如下：

其中，dh、dv為該塊的水平和垂直位移矢量。因此可以看出采用這種匹配準則的運動估計體現了最小風險準則，在運動搜索中選取參考塊中失配像素最少的塊作為匹配塊，對保持當前塊與匹配塊形狀的一致性有較強的約束。但在運動搜索范圍內，有些位置在本匹配準則下會具有相同的匹配像素數，即有相同的風險。對于此種情況再采用基于最小相對位移約束的判決方法進行二次匹配。

選取與Δd(i_opt， j_opt)對應的位移矢量(i_opt， j_opt)為最佳運動矢量。因此在上述匹配準則中，若多個不同位移的參考塊有相同最小風險時，選擇與相鄰像塊相對位移最小的像塊為當前塊的最佳匹配塊。運用這樣的判斷準則不但顯著地提高了判決的準確性和唯一性，而且又由于在相同風險下選擇最小的相對位移，使得相鄰圖像區域的運動矢量場的一致性得到進一步的提高，減小了搜索像素的復雜度。

4 實驗結果

在JVT的H.264/AVC編碼參考模型JM6.1上實現本文所提算法。選擇具有廣泛代表性的六個標準測試序列：Bus、Carphone、Claire、Foreman、Flower、Stefan。其中，Stefan為大運動序列；Carphone、Foreman、Bus為中等運動序列；Claire為小運動或幾乎靜止序列；Flower則包含了較多的細節與鏡頭的平移。采用的幀率是30Hz，搜索范圍是[-32，32]，五個參考幀，CABAC熵編碼，使用全部七種塊進行匹配。為便于比較，還在JM6.1上實現了兩個經典算法，即FS（Full Search Algorithm）和MVFAST(Motion Vector Field Adaptive Search Technique)[6]算法。

表2是本文算法與FS和MVFAST算法實驗結果的比較，主要比較了信噪比（PSNR）、搜索點數（Points）以及搜索時間（Time）。從表中可以看出，與FS算法以及MVFAST算法相比，本文算法明顯地減少了計算量，加快了搜索速度，同時又在不同程度上提高了編碼質量。對于測試所有序列， PSNR平均比MVFAST提高了0.06 dB，更接近FS算法的編碼質量；平均搜索點數只有20.5，運算量比MVFAST算法下降了61%。

5 結束語

在深入研究H.264視頻編碼標準及其運動矢量統計特征的基礎上，提出了一種適用于最新視頻編碼標準H.264/AVC的基于節點模型的可變形塊匹配運動估計算法。該算法針對H.264的編碼特點，利用視頻圖像序列的運動矢量統計特性以及時域、空域的相關性，在保持PSNR方面性能不受損失的同時，大大降低了運算復雜度。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。