曾接賢，鄭大芳，符 祥

南昌航空大學 軟件學院，南昌 330063

基于運動矢量空間相關(guān)性的H.264分像素運動估計

曾接賢，鄭大芳，符 祥

南昌航空大學 軟件學院，南昌 330063

1 引言

運動估計是視頻壓縮編碼中的關(guān)鍵技術(shù)之一，它可消除視頻信號的時間冗余，它的效率直接影響到編碼速度，壓縮率和視頻解碼后的圖像質(zhì)量。H.264中由于采用分層設計、多幀參論、多模式運動估計、1/4像素精度運動估計等技術(shù)，提高了預測精度，降低了匹配誤差，從而獲得比其他標準更好的壓縮性能。但是，它的計算復雜度卻大幅度增加。因此，研究高效快速的運動估計算法具有重要意義。

典型的運動估計包括整像素運動估計和分像素運動估計。整像素運動估計由于其搜索點數(shù)多而備受關(guān)注，許多快速運動估計算法致力于整像素運動估計計算復雜度降低的研究。隨著整像素運動估計快速算法的發(fā)展，整像素搜索點數(shù)[1]可以減少到10個以下，這使得分像素運動估計的計算量高于或相當于整像素運動估計的計算量。因此，分像素運動估計快速算法的發(fā)展對于整個運動估計的計算量的減少變得尤為重要。目前分像素運動估計快速算法主要有三類：一類是基于運動補償預測誤差模型的算法，如H.264/AVC中快速1/4像素運動估計算法[2]和具有低計算復雜度的基于模型的1/4像素運動估計[3]等，這類算法根據(jù)最優(yōu)整像素點的一個整像素運動領(lǐng)域的數(shù)學模型建立誤差模型，避免了運算量很大的分像素內(nèi)插運算和分像素搜索過程，但算法的匹配精度較低。另一類是采用提前終止搜索策略的算法，如改進的面向H.264/AVC的快速運動估計策略[4]，這類算法通過閾值判定，提前結(jié)束分像素搜索，但存在閾值選取或計算問題——閾值過大，搜索準確度就會降低，閾值過小，搜索速度很難有明顯提高。還有一類是基于圖像平坦區(qū)域預測的算法，這類算法避免了前兩類算法的缺陷，如針對H.264的基于平坦區(qū)域預測的分像素運動估計[5]。該算法采用中值預測運動矢量和模式1的運動矢量，通過預測整像素匹配宏塊，從而跳過部分宏塊的分像素搜索過程，達到提高搜索速度的目的，但對于未預測為整像素匹配宏塊的宏塊，其中可能含有整像素運動塊，對這部分整像素運動塊進行分像素搜索就是浪費。

針對文獻[5]的不足，本文提出了一種基于運動矢量空間相關(guān)性的H.264分像素運動估計算法，簡稱MVSCBS算法。該算法充分利用運動矢量空間相關(guān)性來預測整像素運動塊，并對整像素運動塊只進行整像素搜索，不進行分像素搜索。實驗結(jié)果表明，本文算法結(jié)合全分像素搜索算法使用，基本保持了搜索精度的同時，可比文獻[5]中的算法減少10%左右的分像素搜索點。

2 H.264中的分像素搜索算法

H.264中采納了兩種分像素搜索算法：分像素全搜索（FFPS）和基于中心的快速分像素搜索（CBFPS）[6]。

2.1 分像素全搜索

分像素全搜索算法如圖1所示。該算法首先計算最佳整像素位置周圍的8個1/2像素位置（如圖1所示中的空心方框“□”處），找到最佳1/2像素位置（如圖1所示中的實心方框“■”處）；然后計算最佳1/2像素位置周圍的8個1/4像素位置（如圖1所示中的空心三角“△”處），找到最佳1/4像素位置（如圖1所示中的實心三角“▲”處），作為分像素搜索的最佳運動矢量。由于分像素搜索在計算匹配誤差值時增加了Hadamard變換，所以最佳整像素位置的匹配誤差值在分像素運動估計時要重新計算。分像素全搜索算法總共需要搜索17個點，其中包括8個1/2像素位置，8個1/4像素位置和1個最優(yōu)整像素位置。

圖1 分像素全搜索

2.2 基于中心的快速分像素搜索

基于中心的快速分像素搜索算法如圖2所示。該算法首先根據(jù)式（1）計算(pred_x，pred_y)，比較該點處的匹配誤差值和最佳整像素位置的匹配誤差值的大小，選匹配誤差值較小的位置作為搜索起始點；然后再循環(huán)使用小菱形模板進行搜索，直到最小匹配誤差點為搜索模板的中心時停止；最后選取最小匹配誤差點為最終的分像素匹配點。

其中，fracpredmv=(pred_x，pred_y)，predmv是相鄰塊運動矢量的中值，mv為當前塊的整像素運動矢量，%是求模操作，在1/4像素的情況下，β=4。

圖2 基于中心的快速分像素搜索

3 MVSCBS算法

3.1 MVSCBS算法的切入點

H.264的運動估計采用七種模式，并選取匹配誤差最小的模式作為幀間預測模式。每種模式的運動估計都是首先進行整像素運動估計，然后以最優(yōu)整像素位置為中心，在一個整像素運動領(lǐng)域內(nèi)進行分像素精確搜索。但是當分像素搜索之后最佳點仍為整數(shù)位置時，分像素搜索過程就是浪費。表1顯示了在五個圖像測試序列中的最終運動矢量分別為整像素運動矢量和分像素運動矢量的比例。從表1可以看出，18.33%以上的運動塊的最終運動矢量都是整像素運動矢量。特別是對于運動程度比較低的測試序列，70%以上的運動塊的最終運動矢量在整像素位置，如claire序列的整像素運動矢量比例占74.25%。設經(jīng)過分像素搜索之后最佳點仍為整像素位置的運動塊為整像素運動塊（Integer Pixel Motion Block，IPMB）?？梢蕴崆邦A測這些IPMB，從而跳過IPMB的分像素搜索過程，這就是MVSCBS算法的切入點。通過跳過這些IPMB的分像素搜索，可以減少運動估計時間，從而提高編碼效率。

表1 整像素和分像素運動矢量比例 （%）

3.2 MVSCBS算法描述

在整像素運動估計中，許多快速搜索算法都利用運動矢量的空間相關(guān)性來預測運動塊的初始搜索點，如文獻[6-7]中的算法，減少了大量的搜索點數(shù)，提高了整像素運動估計效率。因此，本文對運動矢量的空間相關(guān)性在分像素運動估計中的影響進行了統(tǒng)計性研究。本文根據(jù)運動塊的運動矢量空間相關(guān)性來預測IPMB，即分別利用運動塊的左鄰塊運動矢量（左）、上鄰塊運動矢量（上）、右上鄰塊運動矢量（右上）、中值預測運動矢量（中值）和上層塊模式運動矢量（上層）作為當前塊的預測運動矢量，如果預測運動矢量在整像素位置，則預測當前塊為IPMB。表2和表3分別列出了用各種單個預測運動矢量來預測IPMB的預測精度和預測比例。表4和表5分別列出了用各種多個預測運動矢量來預測IPMB的預測精度和預測比例。其中預測精度表示在被預測的IPMB中，真正的IPMB所占的比例；預測比例則表示在所有的IPMB中，能提前預測為IPMB的運動塊所占的比例。

表2 IPMB預測方法的預測精度 （%）

表3 IPMB預測方法的預測比例 （%）

表4 IPMB合并預測方法的預測精度 （%）

表5 IPMB合并預測方法的預測比例 （%）

預測精度越高，匹配誤差就越小，因此圖像的編碼質(zhì)量變化也越小；預測比例越高，能夠預測出的IPMB越多，跳過分像素搜索的運動塊就越多，因此分像素運動估計的計算量就越小。從表2和表3綜合來看，雖然單個預測運動矢量預測IPMB的方法的預測比例較高，在小運動程度的測試序列中，達到90%以上，但是預測精度不夠高，大部分都在90%以下。從表4和表5綜合來看，對于同一測試序列，將左鄰塊運動矢量、上鄰塊運動矢量、右上鄰塊運動矢量和上層塊模式運動矢量都作為預測運動矢量來預測IPMB的方法的預測精度是最高的，但是預測比例偏低，特別是對于運動程度比較大的測試序列，如foreman測試序列，預測比例只有29.81%，這樣分像素運動估計計算量的減少就不明顯。因此，本文從預測精度和預測比例兩方面來綜合考慮，選用了一種折中的方法，即將中值預測運動矢量和上層塊模式運動矢量作為預測運動矢量來預測IPMB的方法。

為了判斷預測運動矢量是否落在整像素位置，本文給出如下判斷準則：當is_IntPos_x和is_IntPos_y都為0時，當前預測運動矢量被判定為落在整像素位置。is_IntPos_x和is_IntPos_y計算如下：

其中，(fracmν_x,fracmν_y)是分像素預測運動矢量，(mν_x,mν_y)是當前塊的最優(yōu)整像素運動矢量。

如果中值預測運動矢量和上層塊模式運動矢量這兩個預測運動矢量都落在整像素位置，則預測當前塊為IPMB。對于被判定為IPMB的運動塊，本文算法對其只進行整像素搜素，不進行分像素搜索，但是重新計算最優(yōu)整像素位置的匹配誤差值；對于未判定為IPMB的運動塊，本文算法對其進行常規(guī)的整像素和分像素搜索。

表4和表5中的數(shù)據(jù)顯示了本文方法比文獻[5]方法的預測精度和預測比例都要高。文獻[5]根據(jù)中值預測運動矢量和模式1的運動矢量，預測整像素匹配宏塊，但對于未預測為整像素匹配宏塊的宏塊，其中可能含有IPMB，本文方法能預測出其中大部分的IPMB，因此預測比例更高，并且本文方法對所有的運動塊都進行IPMB預測判決，所以預測精度更高。

4 實驗結(jié)果及分析

本文實驗是基于H.264/AVC參考模型和JM10.1平臺進行的。實驗硬件環(huán)境：Pentium?Dual-Core CPU 2.6 GHz，2 GB RAM。編碼環(huán)境如下：搜索范圍是[-16，16]，5幀作為參考幀，序列類型是IPPP，YUV的格式是4∶2∶0，幀率是30 frame/s。實驗選取5個運動程度不同的QCIF格式的圖像測試序列：akiyo，mother-daughter，news，foreman，claire，對這些序列中的前100幀進行視頻編碼。本文主要研究分像素運動估計算法，因此整像素運動估計算法采用JM10.1中的UMHexagonS[3]。分像素運動估計算法分別使用FFPS、CBFPS和本文提出的MVSCBS算法結(jié)合，分別稱之為F&M，C&M。為了驗證算法的有效性，與文獻[5]提到的F&F，C&F算法進行了對比實驗，并測試了峰值信噪比（PSNR），碼率（Bitrate）和總分像素搜索點數(shù)（Τotal Fractional Pixel Searching Points，ΤFPSP）。分別計算了F&M，C&M算法相對于FFPS和CBFPS的峰值信噪比改變△PSNR，碼率改變率△Bitrate和總分像素搜索點數(shù)改變率△TFPSP。表6反映了算法在量化參數(shù)為28時的性能。圖3至圖6顯示了△PSNR和△Bitrate在量化參數(shù)從20到40之間的波動情況。

從表6可以看出，MVSCBS算法和FFPS結(jié)合使用，與FFPS算法相比，可以降低12.26%至69.26%的分像素搜索點，而峰值信噪比平均下降不超過0.012 dB，最高下降不超過0.03 dB；碼率平均上升不超過0.118%，最高上升不超過0.57%，即F&M算法在保證搜索精度的同時，降低了分像素搜索工作量。若MVSCBS算法和CBFPS結(jié)合使用，與CBFPS算法相比，可以降低11.13%至55.44%的分像素搜索點，峰值信噪比平均下降不超過0.004 dB，最高下降不超過0.03 dB；碼率平均上升不超過0.17%，最高上升不超過1.63%，即C&M算法保證了搜索精度的同時，也降低了分像素搜索工作量。

從表6還可以看出，相對于FFPS來說，F(xiàn)&M的峰值信噪比平均下降不超過0.012 dB，F(xiàn)&F的峰值信噪比平均下降不超過0.008 dB，F(xiàn)&M的碼率平均上升不超過0.118%，F(xiàn)&F的碼率平均上升不超過0.122%，即表明F&M和F&F有著相同的搜素精度，但F&M比F&F減少了大約10%的分像素搜索點；相對于CBFP來說，C&M的峰值信噪比平均下降不超過0.004 dB，C&F的峰值信噪比平均下降不超過0.008 dB，C&M的碼率平均上升不超過0.170%，C&F的碼率平均上升不超過0.198%，即表明C&M和C&F有著相同的搜素精度，但C&M比C&F減少了大約10%的分像素搜索點。

從圖3可以看出，F(xiàn)&M算法相對于FFPS算法，△PSNR的波動范圍為－0.07 dB到0.05 dB。從圖4可以看出，F(xiàn)&M算法相對于FFPS算法，△Bitrate的波動范圍為－0.94%到1.87%。從圖5可以看出，C&M算法相對于CBFPS算法，△PSNR的波動范圍為－0.07 dB到0.06 dB。從圖6可以看出，C&M算法相對于CBFPS算法，△Bitrate的波動范圍為－1.75%到1.99%。這說明本文提出的MVSCBS算法具有較高的搜素精度。

表6 算法性能

圖3 F&M算法對PSNR的影響

圖5 C&M算法對PSNR的影響

圖4 F&M算法對Bitrate的影響

圖6 C&M算法對Bitrate的影響

5 結(jié)論

為了減少分像素運動估計的計算量，本文提出了一種基于運動矢量空間相關(guān)性的分像素運動估計方法。它充分利用了運動矢量的空間相關(guān)性來避免IPMB的分像素搜索過程。本文算法將中值預測運動矢量和上層塊模式運動矢量都作為預測運動矢量，并根據(jù)預測運動矢量是否落在整像素位置的方法來預測IPMB。對于被判定為IPMB的運動塊，本文算法對其只進行整像素搜索，不進行分像素搜索，從而提高了搜索速度。實驗結(jié)果表明，本文算法結(jié)合全分像素搜索算法使用，在基本保持搜索精度不變的同時，可比文獻[5]中的算法減少10%左右的分像素搜索點。本文算法可與其他快速分像素搜索算法結(jié)合使用，以獲得更好的編碼性能。

[1]He Wenwei，Zhang Yuling.Improved hexagon-based searching algorithm for fast motion estimation[C]//IEEE Wireless Communications，Networking and Mobile Computing（WiCOM）. Shenzhen，China：IEEE Press，2010：1-3.

[2]陳剛，賈振紅，陳荷.H.264/AVC中快速1/4像素運動估計算法[J].光電子·激光，2008，19（7）：960-962.

[3]Suh J W，Cho J，Jeong J.Model-based quarter-pixel motion estimation with low computational complexity[J].Electronics Letters，2009，45（12）：618-620.

[4]Xu Xiaozhong，He Yun.Improvements on fast motion estimation strategy for H.264/AVC[J].IEEE Τransactions on Circuits and Systems for Video Τechnology，2008，18（3）：285-293.

[5]方健，鄭偉，李炳博，等.針對H.264的基于平坦區(qū)域預測的分像素運動估計[J].中國圖象圖形學報，2008，13（12）：2286-2290.

[6]Chen Z B，Zhou P，He Y.Fast integer pel and fractional pel motion estimation for JVΤ（JVΤ-F017）[C]//Proceedings of 6th Joint Video Τeam Meeting，Awaji，Japan，2002：5-13.

[7]Wu Xiaomin，Xu Weizhang，Zhu Nanhao，et al.A fast motion estimation algorithm for H.264[C]//Proceedings of International Conference on Signal Acquisition and Processing（ICSAP）.Bangalore，India：IEEE Press，2010：112-116.

ZENG Jiexian,ZHENG Dafang,FU Xiang

School of Software,Nanchang Hangkong University,Nanchang 330063,China

With the development of fast integer pixel motion estimation algorithms,the proportion of the computational cost of fractional pixel motion estimation in that of the whole motion estimation has become more and more significant.Τo reduce the complexity of fractional pixel motion estimation,a novel method of H.264 fractional pixel motion estimation based on the spatial correlation of motion vector is proposed.It predicts Integer Pixel Motion Block（IPMB）using the spatial correlation of motion vector.It skips the fractional pixel search process for IPMB.Experimental results show that combined with the full fractional pixel search algorithm,the proposed algorithm can reduce 60%of fractional pixel search points while maintaining the search accuracy basically compared with the pure full fractional pixel search algorithm.Τhe proposed algorithm can be combined with other fractional pixel search algorithm to get better coding performance.

H.264;motion vector;spatial correlation;motion estimation;Integer Pixel Motion Block（IPMB）

隨著整像素運動估計快速算法的發(fā)展，分像素運動估計的計算量在運動估計中所占比重越發(fā)明顯。為了減少分像素運動估計的計算量，提出了一種利用運動矢量空間相關(guān)性來預測整像素運動塊，對整像素運動塊進行分像素搜索過程跳過的分像素運動估計方法。實驗結(jié)果表明，該算法與全分像素搜索算法結(jié)合使用，在基本保持搜索精度不變的情況下，比單純的全分像素搜索算法減少60%左右的分像素搜索點。該算法可與其他快速分像素搜索算法結(jié)合使用，以獲得更好的編碼性能。

H.264；運動矢量；空間相關(guān)性；運動估計；整像素運動塊

A

ΤN919.81

10.3778/j.issn.1002-8331.1111-0334

ZENG Jiexian,ZHENG Dafang,FU Xiang.H.264 fractional pixel motion estimation based on spatial correlation of motion vector.Computer Engineering and Applications,2013,49（15）：175-178.

國家自然科學基金（No.61165011）；江西省科技支撐計劃項目（No.20112BBG70092）；航天科技創(chuàng)新基金。

曾接賢（1958—），男，教授，主要研究領(lǐng)域為圖像處理與模式識別，計算機視覺；鄭大芳（1988—），女，碩士，主要研究領(lǐng)域為圖像處理與模式識別；符祥（1980—），男，博士，講師，主要研究領(lǐng)域為數(shù)字圖像處理和計算機視覺。E-mail：zengjx58@163.com

2011-11-18

2011-12-20

1002-8331（2013）15-0175-04

CNKI出版日期：2012-04-25 http://www.cnki.net/kcms/detail/11.2127.ΤP.20120425.1720.043.html