孫道輝

摘 要：幀間預(yù)測編碼法是視頻編碼過程中消除冗余的重要方法。運(yùn)動估計和運(yùn)動補(bǔ)償技術(shù)是視頻幀間預(yù)測編碼中的核心技術(shù)。詳細(xì)研究了塊匹配運(yùn)動估計的基本原理，重點(diǎn)介紹了幾種經(jīng)典的塊匹配運(yùn)動估計算法，通過實(shí)驗(yàn)定性地評價了各算法的性能特點(diǎn)，分析了各算法的優(yōu)缺點(diǎn)，總結(jié)出了運(yùn)動估計算法優(yōu)化的方向，對目前運(yùn)動估計技術(shù)的研究和設(shè)計具有重要意義。

關(guān)鍵詞：幀間預(yù)測編碼；時間冗余；塊匹配；運(yùn)動估計；運(yùn)動矢量

中圖分類號：TN919.81 文獻(xiàn)標(biāo)志碼：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

引言

幀間預(yù)測是視頻編碼的關(guān)鍵內(nèi)容，而運(yùn)動估計是其核心。據(jù)統(tǒng)計在H.264/AVC編碼中運(yùn)動估計約占全部計算量的60%到80%，所以運(yùn)動估計算法的性能至關(guān)重要。塊匹配算法廣泛應(yīng)用標(biāo)準(zhǔn)視頻編碼。

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

1 幀間預(yù)測原理

1.1 運(yùn)動估計

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

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

1.2 運(yùn)動補(bǔ)償

運(yùn)動估計得到的運(yùn)動矢量同參考幀補(bǔ)償出當(dāng)前幀的預(yù)測幀的過程叫做運(yùn)動補(bǔ)償（Motion Compensation，MC），預(yù)測幀與當(dāng)前幀相減得到預(yù)測誤差[3]。再對預(yù)測誤差進(jìn)行進(jìn)一步處理。

2 運(yùn)動估計算法

全搜索算法[4]（Exhaustive Search method，ES）能夠得到全局最優(yōu)的運(yùn)動矢量，但該算法的運(yùn)算量巨大無法實(shí)時應(yīng)用?？焖偎阉魉惴╗5]簡單，計算量小，加速比較大，但有時會陷入局部最優(yōu)值，搜索的準(zhǔn)確度不高。經(jīng)典的快速搜索算法[6]有：三步法（Three Step Search method，TSS），二維對數(shù)法，交叉搜索法，新三步法（New Three Step Search method，NTSS），四步法（Four Step Search method，F(xiàn)SS），菱形法[7]（Diamond Search method，DS），十字菱形搜索法，自適應(yīng)十字搜索法（Adaptive Rood Pattern Search method，ARPS），六邊形搜索法。

2.1 全局搜索算法

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

2.2 三步搜索法

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

2.3 菱形法

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)平臺和實(shí)驗(yàn)條件設(shè)置

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

3.2 實(shí)驗(yàn)結(jié)果和分析

每幀圖像在所采用算法下的峰值信噪比PSNR如圖2所示。實(shí)驗(yàn)所用31幀圖像的平均搜索點(diǎn)數(shù)和平均峰值信噪比PSNR值如表1所示。

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

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

4 結(jié)束語

本文在分析塊匹配運(yùn)動估計原理的基礎(chǔ)上，實(shí)現(xiàn)了幾種經(jīng)典的塊匹配運(yùn)動估計算法，通過實(shí)驗(yàn)結(jié)果和數(shù)據(jù)證明了不同運(yùn)動估計算法的優(yōu)劣，進(jìn)而從理論上分析了這些經(jīng)典算法優(yōu)劣的原因，為更加魯棒和快速的運(yùn)動估計算法的研究設(shè)計提供了思路，有利于視頻幀間預(yù)測編碼的進(jìn)一步研究。

參考文獻(xiàn)：

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

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

[3]張曉星.基于塊匹配的運(yùn)動估計算法研究與實(shí)現(xiàn)[D].北京交通大學(xué)，2008.

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

[5]劉書平.H.264運(yùn)動估計算法比較與分析[J].現(xiàn)代計算機(jī)，2017（9）：41-46.

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

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