孫道輝

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

關(guān)鍵詞：幀間預(yù)測(cè)編碼；時(shí)間冗余；塊匹配；運(yùn)動(dòng)估計(jì)；運(yùn)動(dòng)矢量

中圖分類(lèi)號(hào)：TN919.81 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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ù)測(cè)是視頻編碼的關(guān)鍵內(nèi)容，而運(yùn)動(dòng)估計(jì)是其核心。據(jù)統(tǒng)計(jì)在H.264/AVC編碼中運(yùn)動(dòng)估計(jì)約占全部計(jì)算量的60%到80%，所以運(yùn)動(dòng)估計(jì)算法的性能至關(guān)重要。塊匹配算法廣泛應(yīng)用標(biāo)準(zhǔn)視頻編碼。

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

1 幀間預(yù)測(cè)原理

1.1 運(yùn)動(dòng)估計(jì)

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

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

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

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

2 運(yùn)動(dòng)估計(jì)算法

全搜索算法[4]（Exhaustive Search method，ES）能夠得到全局最優(yōu)的運(yùn)動(dòng)矢量，但該算法的運(yùn)算量巨大無(wú)法實(shí)時(shí)應(yīng)用。快速搜索算法[5]簡(jiǎn)單，計(jì)算量小，加速比較大，但有時(shí)會(huì)陷入局部最優(yōu)值，搜索的準(zhǔn)確度不高。經(jīng)典的快速搜索算法[6]有：三步法（Three Step Search method，TSS），二維對(duì)數(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 全局搜索算法

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

2.2 三步搜索法

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

2.3 菱形法

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

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

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

仿真實(shí)驗(yàn)在配置為 Intel（R） Core（TM） CPU i7-8550@1.80GHz 1.99Hz，8.00GB內(nèi)存，Windows10的PC平臺(tái)下，使用Matlab2014b作為仿真平臺(tái)，對(duì)ES、TSS、NTSS、SESTSS、FSS、DS、ARPS算法進(jìn)行實(shí)驗(yàn)，測(cè)試視頻為caltrain的前31幀。運(yùn)動(dòng)估計(jì)塊采用邊長(zhǎng)為16個(gè)像素的正方形，搜索范圍為距當(dāng)前塊的上下左右各15個(gè)像素。最佳搜索點(diǎn)采用最小絕對(duì)誤差匹配準(zhǔn)則。測(cè)試指標(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)動(dòng)矢量最佳。四步法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ǔ)

本文在分析塊匹配運(yùn)動(dòng)估計(jì)原理的基礎(chǔ)上，實(shí)現(xiàn)了幾種經(jīng)典的塊匹配運(yùn)動(dòng)估計(jì)算法，通過(guò)實(shí)驗(yàn)結(jié)果和數(shù)據(jù)證明了不同運(yùn)動(dòng)估計(jì)算法的優(yōu)劣，進(jìn)而從理論上分析了這些經(jīng)典算法優(yōu)劣的原因，為更加魯棒和快速的運(yùn)動(dòng)估計(jì)算法的研究設(shè)計(jì)提供了思路，有利于視頻幀間預(yù)測(cè)編碼的進(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)動(dòng)估計(jì)算法研究與實(shí)現(xiàn)[D].北京交通大學(xué)，2008.

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

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

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

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