蔡 宜，周金治+

(1.西南科技大學(xué) 信息工程學(xué)院，四川 綿陽(yáng) 621010； 2.西南科技大學(xué) 特殊環(huán)境機(jī)器人技術(shù)四川省重點(diǎn)實(shí)驗(yàn)室，四川 綿陽(yáng) 621010)

0 引 言

運(yùn)動(dòng)估計(jì)(motion estimation，ME)過(guò)程占據(jù)了視頻壓縮編碼總體時(shí)間的70%(單幀參考)～90%(5幀參考)[1,2]，其中龐大的運(yùn)算量使得在實(shí)時(shí)視頻編碼過(guò)程中效果不佳，如果能減少M(fèi)E的運(yùn)算量將會(huì)顯著提高整體編碼效率。為解決上述問(wèn)題，UmhexagonS算法[3]被H.264/AVC納入采用，相比以往算法，UmhexagonS算法在保證良好率失真的情況下節(jié)省了90%的運(yùn)算量，但代價(jià)是需消耗相對(duì)較長(zhǎng)的運(yùn)動(dòng)估計(jì)時(shí)間。文獻(xiàn)[4]給出了一種基于方向的UmhexagonS算法，通過(guò)方向劃分來(lái)確定搜索區(qū)域，縮減運(yùn)動(dòng)矢量搜索時(shí)間。文獻(xiàn)[5]中提出了一種交叉十字劃分，把搜索區(qū)域劃分為4個(gè)小區(qū)域，然而該方法設(shè)置的預(yù)測(cè)精度過(guò)低，仍存在搜索冗余，這里標(biāo)記為問(wèn)題1。文獻(xiàn)[6,7]中改進(jìn)算法在劇烈運(yùn)動(dòng)情景中均節(jié)省了23.8%左右的運(yùn)動(dòng)估計(jì)時(shí)間，而在微運(yùn)動(dòng)情景中僅僅節(jié)省了7.4%左右，表明該算法在微運(yùn)動(dòng)情景下適應(yīng)能力較差，這里標(biāo)記為問(wèn)題2。文獻(xiàn)[8,9]均提到了動(dòng)矢量具有中心偏置分布特性，然而后者在3×3區(qū)域改進(jìn)算法中忽略了對(duì)中心點(diǎn)搜索，但中心點(diǎn)為最優(yōu)運(yùn)動(dòng)矢量點(diǎn)的概率高達(dá)45.49%，這里標(biāo)記為問(wèn)題3。

本文將在UmhexagonS算法以及相關(guān)文獻(xiàn)的基礎(chǔ)上，從以上3點(diǎn)進(jìn)行優(yōu)化和改進(jìn)。

1 UmhexagonS算法原理

UmhexagonS算法是一種混合運(yùn)動(dòng)矢量搜索算法，分為粗略搜索、細(xì)致搜索和精細(xì)搜索3個(gè)流程。算法基本流程如下：①聯(lián)合使用多種預(yù)測(cè)模型確定起始搜索點(diǎn)；②進(jìn)行非對(duì)稱(chēng)大十字搜索；③進(jìn)行5×5矩形搜索；④進(jìn)行擴(kuò)展大六邊形搜索，在此環(huán)節(jié)中，需由里到外進(jìn)行4輪擴(kuò)展搜索；⑤進(jìn)行小六邊形循環(huán)搜索，直到當(dāng)前最優(yōu)匹配點(diǎn)為搜索模板中心為止；⑥進(jìn)行小鉆石搜索，直到當(dāng)前最優(yōu)匹配點(diǎn)為搜索模板中心為止，此時(shí)算法結(jié)束。搜索模型如圖1所示。

圖1 UmhexagonS算法搜索模型

上述每步中均是以前一步得到的最優(yōu)點(diǎn)為中心展開(kāi)搜索；在步驟②～步驟③中均引入了判斷閾值來(lái)提前終止搜索策略。對(duì)當(dāng)前模板的最佳運(yùn)動(dòng)匹配矢量進(jìn)行率失真代價(jià)計(jì)算，然后與預(yù)設(shè)閾值T進(jìn)行比較。當(dāng)SAD>T2時(shí)，繼續(xù)執(zhí)行下一步搜索；當(dāng)T1

J(MV,λMOTION)=SAD(s,c(MV))+λMOTION×
R(MV-PMV)

(1)

式中：SAD(sum of absoulute different)的計(jì)算公式如下

(2)

式中：s表示當(dāng)前幀中[x,y]的像素值；MVx和MVy分別代表預(yù)測(cè)運(yùn)動(dòng)矢量的橫向分量和縱向分量；λMOTION為拉格朗日常數(shù)；R(MV-PMV)代表了運(yùn)動(dòng)矢量差分編碼可能損耗的比特?cái)?shù)。由于當(dāng)前運(yùn)動(dòng)矢量與預(yù)測(cè)運(yùn)動(dòng)矢量具有較強(qiáng)的相關(guān)性，所以SAD部分的預(yù)測(cè)特性完全可以反映整個(gè)匹配函數(shù)的預(yù)測(cè)特性，即J(MV,λMOTION)可以等效于SAD。

UmhexagonS算法利用起始點(diǎn)搜索預(yù)測(cè)和提前終止預(yù)測(cè)等策略使得MET(motion estimation time)得到縮減，并且保證率失真基本不變。然而，MET的縮減是以較高的計(jì)算復(fù)雜度為前提。若取默認(rèn)的16×16搜索范圍，那么在最壞情況下要搜索多達(dá)272個(gè)點(diǎn)，且對(duì)每個(gè)點(diǎn)進(jìn)行匹配誤差計(jì)算，這里的計(jì)算量是非常龐大的。

2 UmhexagonS算法改進(jìn)

2.1 搜索區(qū)域改進(jìn)

針對(duì)問(wèn)題1，研究表明當(dāng)前塊的運(yùn)動(dòng)矢量和參考幀中預(yù)測(cè)運(yùn)動(dòng)矢量具有高度的相關(guān)性，因此可以通過(guò)兩者對(duì)最優(yōu)預(yù)測(cè)矢量的落入范圍進(jìn)行預(yù)測(cè)。假設(shè)預(yù)測(cè)精度滿(mǎn)足規(guī)定的條件，那么最佳預(yù)測(cè)矢量必然是落入該范圍的，此時(shí)只用搜索該區(qū)域。

(3)

(4)

圖2 前后參考幀預(yù)測(cè)矢量

根據(jù)θ即可確定搜索范圍：①當(dāng)θ∈[0,45°)或θ∈[-45°,0°)時(shí)，對(duì)應(yīng)搜索區(qū)域1或8；②當(dāng)θ∈[45°,90°)或θ∈[-90°,-45°)時(shí)，對(duì)應(yīng)搜索區(qū)域2或7；③當(dāng)θ∈[90°,135°)或θ∈[-135°,-90°)時(shí)，對(duì)應(yīng)搜索區(qū)域3或6；④當(dāng)θ∈[135°,180°)或θ∈[-180°,-135°)時(shí)，對(duì)應(yīng)搜索區(qū)域4或5，如圖3所示。

圖3 大范圍模型區(qū)域劃分

區(qū)域劃分策略將大范圍搜索模板細(xì)化為8個(gè)區(qū)域，θ的值會(huì)將定位到特定的搜索區(qū)域。相比較UmhexagonS算法，改進(jìn)后算法的搜索面積縮小到1/8，相比較文獻(xiàn)[5]的十字劃分，改進(jìn)后算法的搜索面積縮小到1/4。

2.2 運(yùn)動(dòng)情景提前分類(lèi)策略

UmhexagonS算法中引入的非對(duì)稱(chēng)大十字搜索和擴(kuò)展大六邊形搜索很大程度上優(yōu)化了對(duì)劇烈運(yùn)動(dòng)情景的預(yù)測(cè)效果。然而在微運(yùn)動(dòng)情景下，最優(yōu)點(diǎn)通常都積聚在搜索中心點(diǎn)附近，如果仍使用大范圍搜索模型會(huì)存在搜索冗余，降低效率。

針對(duì)問(wèn)題2，文獻(xiàn)[10]提出了一種自適應(yīng)的模型切換算法，作者給出了一個(gè)基于EDR(error descent rate)模型的內(nèi)容分類(lèi)器。然而作者僅僅選取了中心點(diǎn)附近的4個(gè)點(diǎn)進(jìn)行采樣，其采樣范圍容易陷入局部最優(yōu)。

依據(jù)單峰值誤差面假設(shè)，當(dāng)前塊率失真往往隨著與全局最優(yōu)點(diǎn)距離的縮小而單調(diào)遞減[11]。通常全局最優(yōu)點(diǎn)與其周?chē)袼攸c(diǎn)的關(guān)系比遠(yuǎn)處像素點(diǎn)的關(guān)系要密切很多，越是靠近全局最優(yōu)點(diǎn)，其率失真代價(jià)越小，越是遠(yuǎn)離全局最優(yōu)點(diǎn)，其率失真代價(jià)越大。依據(jù)這一性質(zhì)，我們可以重新設(shè)定搜索策略，當(dāng)為微運(yùn)動(dòng)情景時(shí)，采用局部小范圍模型搜索；當(dāng)為劇烈運(yùn)動(dòng)情景時(shí)，采用大范圍模型搜索。

圖4給出了最優(yōu)點(diǎn)距離搜索中心越來(lái)越遠(yuǎn)的4種情況，取坡度比值分別為

(5)

其中，L1最靠近搜索中心點(diǎn)，坡度比最大；L4最遠(yuǎn)離搜索中心點(diǎn)，坡度比最小。由此我們可以通過(guò)計(jì)算搜索中心點(diǎn)與鄰近點(diǎn)的坡度來(lái)估計(jì)最優(yōu)點(diǎn)與搜索中心的距離。當(dāng)坡度比值越大，最優(yōu)點(diǎn)距離搜索中心越近；當(dāng)坡度比值越小，最優(yōu)點(diǎn)距離搜索中心越遠(yuǎn)。

圖4 全局最優(yōu)點(diǎn)與中心點(diǎn)距離的率失真表現(xiàn)

經(jīng)過(guò)起始點(diǎn)預(yù)測(cè)后得到的當(dāng)前最優(yōu)點(diǎn)是全局最優(yōu)點(diǎn)的概率非常大，那么將以當(dāng)前起始預(yù)測(cè)點(diǎn)為中心，對(duì)其周?chē)噜忺c(diǎn)進(jìn)行率失真代價(jià)計(jì)算(步長(zhǎng)為一個(gè)像素)。圖5中，點(diǎn)A是經(jīng)過(guò)起始點(diǎn)搜索后得到的，率失真代價(jià)為DA，若測(cè)得此時(shí)周?chē)徑c(diǎn)DB為最小，那么搜索中心點(diǎn)與最鄰像素點(diǎn)率失真差值為|DB-DA|。由之前討論出的結(jié)論可知，即當(dāng)|DB-DA|越大時(shí)，最優(yōu)點(diǎn)離搜索點(diǎn)中心越近；當(dāng)|DB-DA|越小時(shí)，最優(yōu)點(diǎn)離搜索點(diǎn)中心越遠(yuǎn)。這里利用EDR模型，通過(guò)三步迭代搜索進(jìn)行運(yùn)動(dòng)情景分類(lèi)，每次搜索步長(zhǎng)均為一個(gè)像素

EDR=D最小鄰點(diǎn)/D中心點(diǎn)

(6)

圖5 搜索中心點(diǎn)與周?chē)忺c(diǎn)

(1)以起始搜索點(diǎn)A為中心點(diǎn)對(duì)鄰域搜索，若測(cè)得點(diǎn)B為最小鄰點(diǎn)，此時(shí)EDR=DB/DA。當(dāng)EDR≥1時(shí)，表明此時(shí)已經(jīng)局部最小，直接終止搜索；當(dāng)EDR

(2)以點(diǎn)B為中心點(diǎn)，若測(cè)得點(diǎn)C為最小鄰點(diǎn)，此時(shí)EDR=DC/DB。當(dāng)EDR

(3)以點(diǎn)C為中心點(diǎn)，重復(fù)以上操作，當(dāng)T≤EDR<1時(shí)，當(dāng)前為劇烈運(yùn)動(dòng)情景。這里的閾值T依據(jù)參考文獻(xiàn)設(shè)置為0.9。

改進(jìn)后的算法直接分類(lèi)出3種不同強(qiáng)度的運(yùn)動(dòng)情景。當(dāng)為劇烈運(yùn)動(dòng)，仍然從非對(duì)稱(chēng)大十字搜索模型開(kāi)始依次搜索；當(dāng)為中等劇烈運(yùn)動(dòng)情景，直接從小六邊形開(kāi)始搜索；當(dāng)為微運(yùn)動(dòng)情景，直接從小鉆石開(kāi)始搜索。

2.3 5×5螺旋搜索改進(jìn)

通過(guò)對(duì)大量自然運(yùn)動(dòng)序列分析，現(xiàn)實(shí)世界中大多數(shù)圖像序列的塊運(yùn)動(dòng)場(chǎng)通常是平滑、緩慢的，主要以水平運(yùn)動(dòng)為主。

經(jīng)實(shí)驗(yàn)驗(yàn)證，約有85.39%的運(yùn)動(dòng)矢量非均勻的分布在5×5區(qū)域內(nèi)，而其中分布在3×3區(qū)域的概率高達(dá)71.79%。由此可知，運(yùn)動(dòng)矢量的中心偏置性同樣體現(xiàn)在了5×5小范圍模板中，即搜索模板中心的運(yùn)動(dòng)矢量分布密度遠(yuǎn)大于邊緣區(qū)域。針對(duì)問(wèn)題3，本文采取了由內(nèi)向外擴(kuò)展的搜索順序，如圖6(a)所示，在3×3區(qū)域中D點(diǎn)的概率低至2.78%；5×5邊緣地區(qū)(D+E+F)分布概率低至10.6%，故均予以忽略。首先對(duì)中心3×3小十字形進(jìn)行搜索，然后再向水平方向擴(kuò)展進(jìn)行5×5大十字搜索，如圖6(b)所示。對(duì)比原算法，改進(jìn)后的5×5模板只需搜索概率最大的9個(gè)點(diǎn)(占5×5全局的87.52%)，相比之下減少了16個(gè)點(diǎn)；相比文獻(xiàn)[9]，本文算法在增加了搜索中心點(diǎn)的情況下仍比其少搜索5個(gè)點(diǎn)，且搜索區(qū)域的最優(yōu)運(yùn)動(dòng)矢量分布概率比其高34.84%。

圖6 5×5區(qū)域運(yùn)動(dòng)矢量分布概率

2.4 改進(jìn)算法總結(jié)

綜上所述，本文改進(jìn)后算法流程如下：①確定起始搜索點(diǎn)；②進(jìn)行運(yùn)動(dòng)情景分類(lèi)，若為微運(yùn)動(dòng)情景直接跳轉(zhuǎn)到⑦開(kāi)始執(zhí)行，若為中等劇烈運(yùn)動(dòng)情景直接跳轉(zhuǎn)到⑥開(kāi)始執(zhí)行，若為劇烈運(yùn)動(dòng)情景則進(jìn)行下一步；③計(jì)算當(dāng)前MVC、MVPRE，進(jìn)行非對(duì)稱(chēng)大十字模型1/8區(qū)域搜索；④進(jìn)行改進(jìn)后5×5螺旋搜索；⑤計(jì)算當(dāng)前MVC、MVPRE，進(jìn)行大六邊形1/8區(qū)域搜索；⑥以前一步獲得的最優(yōu)點(diǎn)為搜索中心進(jìn)行小六邊形循環(huán)搜索，直到當(dāng)最優(yōu)匹配點(diǎn)為搜索模板中心為止；⑦以前一步獲得的最優(yōu)點(diǎn)為搜索中心進(jìn)行小鉆石搜索，直到當(dāng)最優(yōu)匹配點(diǎn)為搜索模板中心為止，此時(shí)算法結(jié)束。算法流程如圖7所示。

圖7 改進(jìn)后算法總體流程框架

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

將本文改進(jìn)后算法在官方參考軟件JM12.2模型中進(jìn)行測(cè)試，測(cè)試PC配置為Pentium(R) Dual-Core CPU E6300@2.80 Hz，4 G內(nèi)存，操作系統(tǒng)Windows 7。開(kāi)發(fā)環(huán)境為Visual Studio 2015。encoder.cfg主要參數(shù)設(shè)置如下：編碼幀數(shù)為100；幀率為30；QP=28；搜索范圍為16；參考幀數(shù)為5，其余均為默認(rèn)設(shè)置。

本文共選取了6種運(yùn)動(dòng)強(qiáng)度情景不同的YUV(4∶2∶0)測(cè)試序列，分辨率均為176×144。緩慢運(yùn)動(dòng)序列：akiyo_qcif，news_cif；中等劇烈運(yùn)動(dòng)序列：foreman_qcif，coastguard_qcif；劇烈運(yùn)動(dòng)序列：mobile_qcif，football_cif。在測(cè)試過(guò)程中，測(cè)試項(xiàng)PSNR/dB、BR/(kb/s)、ENT/s、MET/s分別代表：Y分量峰值信噪比、輸出碼率、編碼時(shí)間、運(yùn)動(dòng)估計(jì)時(shí)間。在測(cè)試結(jié)果中，分別用△PSNR(Y)/dB、△Br/%、△MET/%來(lái)表征算法性能，計(jì)算公式為

ΔPSNR(Y)=PSNR(Y)mod-PSNR(Y)ref

(7)

(8)

(9)

其中，下標(biāo)mod代表本文改進(jìn)后算法值，下標(biāo)ref代表對(duì)比算法的值。

表1對(duì)6組測(cè)試序列分別進(jìn)行4類(lèi)算法測(cè)試，其中SCUMH代表本文改進(jìn)后算法。通過(guò)分析Full search、UmhexagonS、EPZS這3種參考算法在編碼時(shí)間和運(yùn)動(dòng)估計(jì)時(shí)間中的數(shù)據(jù)，發(fā)現(xiàn)在緩慢運(yùn)動(dòng)情景下Full search最耗時(shí)，EPZS次之，UmhexagonS耗時(shí)最少；隨著運(yùn)動(dòng)情景劇烈程度的增加，EPZS算法的性能逐漸超越UmhexagonS算法。分析可知，UmhexagonS算法在劇烈運(yùn)動(dòng)情景下性能不及EPZS算法，但在微運(yùn)動(dòng)情景下性能強(qiáng)于EPZS算法。

依據(jù)表2，改進(jìn)后算法在劇烈運(yùn)動(dòng)情景下MET平均減少了40.53%；在中等劇烈運(yùn)動(dòng)情景下平均減少了32.86%；在微運(yùn)動(dòng)情景下平均減少了27.05%。對(duì)比參考文獻(xiàn)[7]，改進(jìn)算法在劇烈運(yùn)動(dòng)情景下，MET進(jìn)一步縮減了19.27%；在中等劇烈運(yùn)動(dòng)情景下縮減了15.17%；在微運(yùn)動(dòng)情景下縮減了19.45%。由以上數(shù)據(jù)可知，改進(jìn)后算法不僅能極大減少劇烈運(yùn)動(dòng)的估計(jì)時(shí)間，在微運(yùn)動(dòng)情景下減少的MET也相當(dāng)可觀(guān)。在劇烈運(yùn)動(dòng)情景下，針對(duì)問(wèn)題1提出的區(qū)域劃分策略，縮小搜索面積，節(jié)省了在劇烈運(yùn)動(dòng)情景下的搜索時(shí)間；在微運(yùn)動(dòng)情況下，針對(duì)問(wèn)題2提出的提前情景分類(lèi)策略，自適應(yīng)地選擇搜索模型，提高了微運(yùn)動(dòng)情景下的搜索效率。同時(shí)，5×5搜索模型也改進(jìn)效果明顯。

圖8，圖9分別表示了兩組不同運(yùn)動(dòng)強(qiáng)度測(cè)試序列的性能，由圖可知，改進(jìn)后算法在微運(yùn)動(dòng)、劇烈運(yùn)動(dòng)情景下均縮減了一定比例的運(yùn)動(dòng)估計(jì)時(shí)間，且隨著編碼幀數(shù)的增加，縮減比例也增加；同時(shí)，改進(jìn)算法在率失真方面與UmhexagonS、EPZS算法基本一致，說(shuō)明本算法保持了與原算法同樣的率失真性能。

圖9 Akiyo與Football在3種算法上率失真對(duì)比

4 結(jié)束語(yǔ)

本文以UmhexagonS算法在預(yù)測(cè)最優(yōu)運(yùn)動(dòng)矢量過(guò)程中仍存在較長(zhǎng)運(yùn)動(dòng)估計(jì)時(shí)間的問(wèn)題展開(kāi)。通過(guò)對(duì)比現(xiàn)有算法，提出了一種包含運(yùn)動(dòng)情景提前分類(lèi)、大范圍模型區(qū)域劃分、5×5搜索順序改進(jìn)的3種改進(jìn)策略的SCUMH算法。實(shí)驗(yàn)結(jié)果表明，對(duì)比UmhexagonS算法，在保證PSNR與碼率基本不變的前提下，SCUMH算法不僅在劇烈運(yùn)動(dòng)情景中縮減了大量的運(yùn)動(dòng)估計(jì)時(shí)間，且在微運(yùn)動(dòng)情景下縮減時(shí)間也相當(dāng)可觀(guān)，可適應(yīng)各種復(fù)雜多變的運(yùn)動(dòng)情景。

另外，SCUMH算法仍存在需要完善的地方：①本文采取的時(shí)間域預(yù)測(cè)方式(前后參考幀預(yù)測(cè))可改進(jìn)為在空間域的預(yù)測(cè)，因?yàn)樵谶\(yùn)動(dòng)矢量預(yù)測(cè)過(guò)程中后者更為精確；②EDR運(yùn)動(dòng)情景分類(lèi)模型過(guò)于粗糙，無(wú)法準(zhǔn)確表示出中心點(diǎn)與周?chē)忺c(diǎn)的偏離程度。