幀間預測運動估計算法研究

孫道輝

摘 要：幀間預測編碼法是視頻編碼過程中消除冗余的重要方法。運動估計和運動補償技術是視頻幀間預測編碼中的核心技術。詳細研究了塊匹配運動估計的基本原理，重點介紹了幾種經典的塊匹配運動估計算法，通過實驗定性地評價了各算法的性能特點，分析了各算法的優缺點，總結出了運動估計算法優化的方向，對目前運動估計技術的研究和設計具有重要意義。

關鍵詞：幀間預測編碼；時間冗余；塊匹配；運動估計；運動矢量

中圖分類號：TN919.81 文獻標志碼：A 文章編號：2095-2945（2018）18-0068-02

Abstract： Motion estimation and motion compensation are the core technologies in video inter-frame prediction coding. The basic principle of block matching motion estimation is studied in detail， and several classical block matching motion estimation algorithms are introduced in detail. The performance characteristics of each algorithm are evaluated qualitatively through experiments， and the advantages and disadvantages of each algorithm are analyzed.

Keywords： interframe prediction coding； time redundancy； block matching； motion estimation； motion vector

引言

幀間預測是視頻編碼的關鍵內容，而運動估計是其核心。據統計在H.264/AVC編碼中運動估計約占全部計算量的60%到80%，所以運動估計算法的性能至關重要。塊匹配算法廣泛應用標準視頻編碼。

在基于塊匹配的運動估計算法中，對每一幀圖像都被分成大小相同的宏塊，然后以宏塊為基本處理單元。最后對預測差值、運動矢量和相應的參考索引進行編碼。

1 幀間預測原理

1.1 運動估計

在序列圖像中，鄰近幀存在著一定的相關性。因此，可將活動圖像分成若干塊或宏塊，在參考幀中定義的搜索區域，按照一定的匹配準則，搜索出每個塊或宏塊在參考幀圖像中的匹配塊，并得出兩者之間的空間位置的相對偏移量，即運動矢量。當前塊從參考幀中求取最佳匹配塊得到運動矢量的過程被稱為運動估計[2]。運動估計的原理如圖1。

假設當前幀為P，參考幀為Pr，當前編碼塊為B，B*與B在圖像中坐標位置相同。在Pr中，按照搜索準則，尋找與B塊相減殘差最小的匹配塊Br。這個過程就是運動估計，Br左上角坐標（xr，yr）與B*左上角坐標（x，y）之差，即為運動矢量（Motion Vector，MV）。

1.2 運動補償

運動估計得到的運動矢量同參考幀補償出當前幀的預測幀的過程叫做運動補償（Motion Compensation，MC），預測幀與當前幀相減得到預測誤差[3]。再對預測誤差進行進一步處理。

2 運動估計算法

全搜索算法[4]（Exhaustive Search method，ES）能夠得到全局最優的運動矢量，但該算法的運算量巨大無法實時應用。快速搜索算法[5]簡單，計算量小，加速比較大，但有時會陷入局部最優值，搜索的準確度不高。經典的快速搜索算法[6]有：三步法（Three Step Search method，TSS），二維對數法，交叉搜索法，新三步法（New Three Step Search method，NTSS），四步法（Four Step Search method，FSS），菱形法[7]（Diamond Search method，DS），十字菱形搜索法，自適應十字搜索法（Adaptive Rood Pattern Search method，ARPS），六邊形搜索法。

2.1 全局搜索算法

全局搜索算法是以每個像素為單位，在搜索區域內，按照一定的搜索規則，尋找匹配誤差最小的塊，計算出運動矢量，這樣在每個像素的位置都會找到一個運動矢量，形成運動矢量集合。

2.2 三步搜索法

三步法是首先將圖像分成不重疊的的塊，在搜索區域內，按照一定的搜索準則分三步搜索。第一步，從塊中心開始以4步為步長的9個點的區域內計算最小誤差值。第二步，以第一步的最小值的點為中心，步長為2步的9個點的區域內計算最小的誤差值。第三步：以第二步的最小SAD值的點為中心，步長為1步的9個點的區域內計算最小誤差值，這個最小點即為最佳匹配點。三步法一共計算點數為：25個點。它的優點是搜索步驟固定簡單，只有三步，易于硬件實現新三步法、簡單快速三步法（Simple and Efficient Three Step Search method，SESTSS）、四步法等都是在三步法的基礎上進行改進的運動估計算法。

2.3 菱形法

菱形法不同于三步法及其改進的算法，它利用運動矢量的中心偏置特性，對搜索模式進行了改進，采用大小菱形模板。大菱形由9個點組成，圍繞中心點的8個點形成一個大菱形的形狀。小菱形是由5個點組成的菱形。菱形法的第一步：在大菱形中搜索計算9個點（大菱形）的SAD，找到最小值點，如果在中心，則轉至第三步；如果不在中心，轉至第二步。第二步：以第一步的最小值點為中心繼續構建大菱形搜索，直至最小值位于中心。第三步：以上一步的最小值點為中心構建5個小菱形搜索，計算結束。菱形法的優點：計算量少，搜索速度快，可以盡可能避免找到局部最優的位置，得到的性能更好。六邊形搜索法、十字形搜索等算法是在菱形法的基礎上進行改進的運動估計算法。

3 實驗結果與分析

3.1 實驗平臺和實驗條件設置

仿真實驗在配置為 Intel（R） Core（TM） CPU i7-8550@1.80GHz 1.99Hz，8.00GB內存，Windows10的PC平臺下，使用Matlab2014b作為仿真平臺，對ES、TSS、NTSS、SESTSS、FSS、DS、ARPS算法進行實驗，測試視頻為caltrain的前31幀。運動估計塊采用邊長為16個像素的正方形，搜索范圍為距當前塊的上下左右各15個像素。最佳搜索點采用最小絕對誤差匹配準則。測試指標采用搜索點數和峰值信噪比（Peak Signal to Noise Ratio，PSNR）。

3.2 實驗結果和分析

每幀圖像在所采用算法下的峰值信噪比PSNR如圖2所示。實驗所用31幀圖像的平均搜索點數和平均峰值信噪比PSNR值如表1所示。

圖2表明，出全局ES算法的PSNR值最高，搜索的精確性最好，得到的運動矢量最佳。四步法FSS和菱形法DS與全局搜索ES算法的PSNR性能上相近，幀PSNR值相差不到0.3dB。

從表1可以看出ES算法雖然PSNR最高，但是搜索點數是快速搜索算法的10～20倍，搜索速度很慢。三步法相比ES算法在PSNR上有一定的下降，但是搜索速度快約10倍。新三步法是在三步法基礎改進的，與三步法在搜索速度上相當，但是PSNR上有明顯的提高。菱形法采用大小菱形模板，在搜索速度和PSNR上均有明顯的提升。自適應十字形搜索法在PSNR上和菱形法一致，搜索速度上卻提升近一倍。

4 結束語

本文在分析塊匹配運動估計原理的基礎上，實現了幾種經典的塊匹配運動估計算法，通過實驗結果和數據證明了不同運動估計算法的優劣，進而從理論上分析了這些經典算法優劣的原因，為更加魯棒和快速的運動估計算法的研究設計提供了思路，有利于視頻幀間預測編碼的進一步研究。

參考文獻：

[1]朱秀昌，劉峰，胡棟.視頻編碼和傳輸新技術[M].北京：電子工業出版社，2014：7.

[2]陳靖，劉京，曹喜信.深入理解視頻編解碼技術：基于H.264標準及參考模型[M].北京：北京航空航天大學出版社，2012：20-29.

[3]張曉星.基于塊匹配的運動估計算法研究與實現[D].北京交通大學，2008.

[4]蔣曉悅，趙榮椿.幾種塊匹配運動估計算法的比較[J].計算機應用研究，2004，21（7）：1-3.

[5]劉書平.H.264運動估計算法比較與分析[J].現代計算機，2017（9）：41-46.

[6]吳曉軍，白世軍，盧文濤.基于H.264視頻編碼的運動估計算法優化[J].電子學報，2009，37（11）：2541-2545.

[7]劉海峰，郭寶龍，馮宗哲.用于塊匹配運動估值的正方形-菱形搜索算法[J].計算機學報，2002，25（7）：747-752.