摘 要： 針對(duì)移動(dòng)通信終端計(jì)算能力的不足，提出了一種適用于可視電話(huà)視頻壓縮編碼的快速運(yùn)動(dòng)估計(jì)算法。根據(jù)當(dāng)前塊運(yùn)動(dòng)矢量類(lèi)型和可視電話(huà)視頻對(duì)象的運(yùn)動(dòng)特點(diǎn)，自動(dòng)選擇不同的搜索策略進(jìn)行運(yùn)動(dòng)估計(jì)搜索。該算法在保證圖像主客觀質(zhì)量的前提下，有效地減少了運(yùn)動(dòng)估計(jì)的時(shí)間，大大降低了編碼計(jì)算量。通過(guò)對(duì)不同類(lèi)型的視頻序列進(jìn)行測(cè)試表明，該算法計(jì)算復(fù)雜度降低了55.4%～69.6%，且對(duì)于不同運(yùn)動(dòng)類(lèi)型的視頻具有較強(qiáng)的適應(yīng)性。

關(guān)鍵詞： 移動(dòng)終端； H.264； 運(yùn)動(dòng)估計(jì)； 算法

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2013）03-32-03

0 引言

移動(dòng)終端和網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，為移動(dòng)視頻業(yè)務(wù)的推廣提供了必要條件。市場(chǎng)需求和技術(shù)進(jìn)步共同推動(dòng)著移動(dòng)視頻業(yè)務(wù)的發(fā)展，并使其成為移動(dòng)運(yùn)營(yíng)商、設(shè)備制造商和內(nèi)容提供商的關(guān)注焦點(diǎn)之一。目前，消費(fèi)市場(chǎng)對(duì)移動(dòng)視頻業(yè)務(wù)的認(rèn)可程度和期望值很高，預(yù)計(jì)在未來(lái)幾年內(nèi)移動(dòng)視頻業(yè)務(wù)將是推動(dòng)3G網(wǎng)絡(luò)發(fā)展的源動(dòng)力。

H.264是由ISO/IEC與ITU-T組成的聯(lián)合視頻組（JVT）制定的新一代視頻壓縮編碼標(biāo)準(zhǔn)，具有較高的圖像質(zhì)量、較強(qiáng)的抗誤碼性和良好的網(wǎng)絡(luò)親和性[1]。H.264目前已廣泛地應(yīng)用在移動(dòng)通信、無(wú)線(xiàn)網(wǎng)絡(luò)、衛(wèi)星廣播、電視會(huì)議、遠(yuǎn)程監(jiān)控、遠(yuǎn)程教育醫(yī)療、IPTV等領(lǐng)域。H.264基本檔（baseline）的使用不涉及版權(quán)，這對(duì)商業(yè)應(yīng)用和普及推廣具有重要的意義。

移動(dòng)終端硬件設(shè)備的處理能力相對(duì)PC機(jī)來(lái)說(shuō)有很大的差距，這使得其對(duì)視頻編解碼的運(yùn)算量提出了極高的要求。因此，針對(duì)移動(dòng)終端設(shè)備計(jì)算能力不足的特點(diǎn)，對(duì)H.264編碼器作相應(yīng)的改進(jìn)以降低編碼復(fù)雜度，是十分必要的。

運(yùn)動(dòng)估計(jì)（Motion Estimation，ME）是H.264編碼器的核心模塊，H.264編碼器的架構(gòu)結(jié)構(gòu)如圖1所示。視頻編碼時(shí)，只需根據(jù)ME搜索結(jié)果保存運(yùn)動(dòng)矢量和殘差數(shù)據(jù)，即可完全恢復(fù)當(dāng)前編碼塊。根據(jù)實(shí)驗(yàn)測(cè)試分析得知，ME模塊的運(yùn)算量占整個(gè)編碼器運(yùn)算量的60%-90%[2]。因此，要想降低H.264編碼器的計(jì)算復(fù)雜度，提高其編碼速度，應(yīng)首先考慮優(yōu)化ME算法模塊。

1 運(yùn)動(dòng)矢量相關(guān)性驗(yàn)證

頭肩序列是可視電話(huà)中最常見(jiàn)的一種圖像模式。頭肩序列具有運(yùn)動(dòng)緩慢、背景相對(duì)靜止等特點(diǎn)，頭肩部的運(yùn)動(dòng)一般是左右搖擺，上下方向的運(yùn)動(dòng)幅度要小于水平方向，因此很大一部分相鄰塊的運(yùn)動(dòng)矢量會(huì)具有相似或基本相同的特點(diǎn)。利用這些特點(diǎn)設(shè)計(jì)新的運(yùn)動(dòng)估計(jì)搜索方案，可以大大降低計(jì)算復(fù)雜度，提高編碼速度。

本文對(duì)forman、missa等測(cè)試序列作了統(tǒng)計(jì)，實(shí)驗(yàn)結(jié)果如最佳運(yùn)動(dòng)矢量分布表（表1）所示。表1中“相鄰相等”指三個(gè)參考?jí)K的運(yùn)動(dòng)矢量相等，“相同”指在相鄰塊運(yùn)動(dòng)矢量相同的基礎(chǔ)上，當(dāng)前塊最終運(yùn)動(dòng)矢量與預(yù)測(cè)運(yùn)動(dòng)矢量相同的條件概率；“1×1”指最終運(yùn)動(dòng)矢量分布在以預(yù)測(cè)矢量為中心，1為半徑的區(qū)域內(nèi)的條件概率。這些數(shù)據(jù)都是在H.264的JM85模型上用全搜索算法統(tǒng)計(jì)的結(jié)果。

表1 最佳匹配矢量分布表

[序列名稱(chēng)＼相鄰相等＼相同＼1×1＼foreman＼69.2%＼60.8%＼96.1%＼missa＼84.0%＼96.9%＼99.6%＼]

由表1的實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果可知，利用時(shí)空上相鄰塊的運(yùn)動(dòng)矢量來(lái)預(yù)測(cè)搜索起始點(diǎn)，能減少搜索范圍，提高搜索速度，減少陷入局部最優(yōu)的可能性。因此，本文選取當(dāng)前待編碼塊MB0的左邊MB1、上邊MB2、右上邊MB3等三個(gè)相鄰塊的運(yùn)動(dòng)矢量來(lái)預(yù)測(cè)預(yù)測(cè)搜索起始點(diǎn)，如圖2所示。

2 本文自適應(yīng)搜索的快速運(yùn)動(dòng)估計(jì)算法

2.1 本文算法搜索策略設(shè)計(jì)

本文采用中值法來(lái)確定預(yù)測(cè)搜索起始點(diǎn)，其基本思想是：選取參考?jí)KMB1、MB2、MB3的匹配矢量的中值來(lái)預(yù)測(cè)搜索起始點(diǎn)。采用中值法預(yù)測(cè)得到的搜索起始點(diǎn)都是相鄰某一塊的運(yùn)動(dòng)矢量，因此最終搜索所得的運(yùn)動(dòng)矢量場(chǎng)較為平滑，節(jié)省了對(duì)運(yùn)動(dòng)矢量編碼所需的碼率。當(dāng)前塊MB0的預(yù)測(cè)矢量Vp的計(jì)算如公式⑴所示。

其中，Vp為當(dāng)前塊MB0的預(yù)測(cè)矢量，即預(yù)測(cè)的運(yùn)動(dòng)估計(jì)搜索起始點(diǎn)；V1、V2和V3分別為MB1、MB2、MB3的等三個(gè)參考?jí)K的運(yùn)動(dòng)矢量。

考慮到可視電話(huà)頭肩序列的運(yùn)動(dòng)特性，本文設(shè)計(jì)了如圖3所示的三種搜索模板。其中，大模板是為了快速向最佳匹配點(diǎn)逼近，提高算法的位移跟蹤能力，減少搜索次數(shù)；而小模板則用以進(jìn)行局部微調(diào)和精確定位，保證搜索精度。同時(shí)由表1的統(tǒng)計(jì)數(shù)據(jù)可知，當(dāng)相鄰塊的匹配矢量相同時(shí)，最佳匹配點(diǎn)應(yīng)在預(yù)測(cè)的搜索起始點(diǎn)附近，本文算法對(duì)這種情況采用小模板搜索。

資料顯示各種塊匹配函數(shù)的性能差別不顯著，為了使計(jì)算復(fù)雜度能夠更低，便于硬件實(shí)現(xiàn)，本文采用運(yùn)算量最小的絕對(duì)差之和（Sum of Absolute Difference，SAD）作為搜索算法的匹配準(zhǔn)則，其計(jì)算如公式⑵所示。

通常，可視電話(huà)視頻序列采用QCIF格式，像素精度為8bit。因此，本文采用的平均峰值信噪比（PSNR）的計(jì)算如公式⑶所示：

2.2 本文算法搜索流程

本文基于模板自適應(yīng)的快速運(yùn)動(dòng)估計(jì)算法流程圖如圖4所示，具體搜索過(guò)程如下。

⑴ 若V1=V2=V3，即三個(gè)參考?jí)K的運(yùn)動(dòng)矢量相等，則表明當(dāng)前塊所在區(qū)域的運(yùn)動(dòng)特性一致。因此，當(dāng)前塊只需在預(yù)測(cè)搜索起始點(diǎn)的周?chē)鲂》秶阉鳎蜆O有可能找到全局最優(yōu)匹配塊。即使用小模板在預(yù)測(cè)搜索起始點(diǎn)周?chē)M(jìn)行匹配計(jì)算，直至最小SAD出現(xiàn)，搜索結(jié)束；否則，轉(zhuǎn)⑵。

⑵ 繼續(xù)比較Vd=max（|Vpx|，|Vpy|）與預(yù)設(shè)閾值T的大小。若滿(mǎn)足Vd

⑶ 由于Vd≥T，當(dāng)前塊所在區(qū)域的運(yùn)動(dòng)較大，則需繼續(xù)判別是水平方向運(yùn)動(dòng)還是垂直方向運(yùn)動(dòng)。若|Vpx|>|Vpy|，表明水平方向的運(yùn)動(dòng)強(qiáng)度要比垂直方向大，則對(duì)當(dāng)前塊采用水平大模板進(jìn)行搜索，直至最小SAD點(diǎn)出現(xiàn)。然后擴(kuò)展搜索水平大模板中心點(diǎn)的左右兩點(diǎn)，若最小SAD點(diǎn)仍在中心點(diǎn)，則搜索結(jié)束；若最小SAD點(diǎn)發(fā)生偏移，則搜索此最小SAD點(diǎn)的上下兩點(diǎn)，所得最小SAD點(diǎn)即為最終的搜索結(jié)果。

對(duì)于|Vpy|>|Vpx|的情況，采用垂直大模板進(jìn)行搜索，具體搜索方法與步驟⑶中水平大模板類(lèi)同。

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

為了分析、比較各算法的性能，本文從以下幾個(gè)方面進(jìn)行實(shí)驗(yàn)比較：平均搜索點(diǎn)數(shù)，平均ME耗時(shí)，碼率，平均信噪比（PSNR）等指標(biāo)。這些比較實(shí)驗(yàn)都是在H.264測(cè)試模型JM85的baseline上進(jìn)行的，由于JM代碼本身是為算法研究及標(biāo)準(zhǔn)的發(fā)展提供的統(tǒng)一測(cè)試平臺(tái)，提供各種實(shí)驗(yàn)研究所需的測(cè)試參數(shù)。對(duì)于本文研究的運(yùn)動(dòng)估計(jì)模塊，JM平臺(tái)也提供了專(zhuān)門(mén)的時(shí)間統(tǒng)計(jì)數(shù)據(jù)。具體實(shí)驗(yàn)參數(shù)設(shè)置為：Intraperiod=10，QP=30，1個(gè)參考幀，F(xiàn)rameRate=25，塊匹配范圍為-8～+8，采用七種塊模式及CAVLC熵編碼。PC機(jī)操作系統(tǒng)為Windows XP， CPU為Pentium Ⅳ 3G，1G內(nèi)存，編譯軟件為Visual C++6.0。

從以上實(shí)驗(yàn)測(cè)試結(jié)果可知，按搜索點(diǎn)數(shù)計(jì)算，本文算法相對(duì)其他快速搜索算法的計(jì)算復(fù)雜度降低55.4%～69.6%。按平均ME耗時(shí)計(jì)算，本文算法相對(duì)其他快速搜索算法的計(jì)算復(fù)雜度降低42.3%～55.7%。同時(shí)，解碼圖像的平均信噪比，本文算法都要優(yōu)于菱形搜索法DS、新三步法NTSS和四步法FSS。而且本文算法的計(jì)算復(fù)雜度較低，搜索點(diǎn)數(shù)和塊匹配時(shí)間大幅下降，這是其他幾種算法無(wú)法比擬的。實(shí)驗(yàn)中，對(duì)兩組測(cè)試序列都存在本文算法的PSNR遠(yuǎn)高于其他算法的現(xiàn)象，其原因在于本文快速搜索算法得到的匹配矢量場(chǎng)比其他算法的更為均勻、平滑，從而減少了對(duì)矢量場(chǎng)編碼所需的比特?cái)?shù)，即可留出更多的比特?cái)?shù)用于編碼殘差數(shù)據(jù)等信息，從整體上提高了重建圖像的信噪比。

在本文算法中，閾值T的選取也是一個(gè)很重要的問(wèn)題。隨著門(mén)限閾值的增加，使用小模板搜索的概率增加，搜索點(diǎn)數(shù)會(huì)有所下降，得到的矢量場(chǎng)更為均勻，但塊匹配誤差也隨之增加。使用閾值T的優(yōu)點(diǎn)在于，對(duì)不同變化強(qiáng)度的數(shù)據(jù)片序列可以通過(guò)設(shè)置閾值T來(lái)改進(jìn)算法性能，對(duì)于快速變化序列更是如此。恰當(dāng)?shù)剡x擇閾值T的大小，將有助于加快搜索速度，提高塊匹配精度；本實(shí)驗(yàn)里設(shè)置T=4。

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

本文分析了可視電話(huà)視頻對(duì)象的特性，提出了一種適用于可視電話(huà)硬件實(shí)現(xiàn)的低復(fù)雜度快速運(yùn)動(dòng)估計(jì)算法，獲得了良好的率失真性能，大大降低了計(jì)算復(fù)雜度。本算法以運(yùn)動(dòng)矢量相關(guān)性為根據(jù)，引入簡(jiǎn)單有效的視頻分類(lèi)方法，使本文算法能根據(jù)視頻序列的運(yùn)動(dòng)類(lèi)型自適應(yīng)地選擇搜索模板，且對(duì)于不同運(yùn)動(dòng)類(lèi)型具有較強(qiáng)的適應(yīng)性。本文算法可直接應(yīng)用于極低復(fù)雜度實(shí)時(shí)視頻編碼軟件，經(jīng)過(guò)適當(dāng)修改可供DSP或制成ASIC用于實(shí)時(shí)視頻編碼硬件系統(tǒng)。

在本文算法中，對(duì)不同運(yùn)動(dòng)強(qiáng)度的視頻序列可以通過(guò)設(shè)置閾值T來(lái)改進(jìn)算法性能。但是，針對(duì)不同運(yùn)動(dòng)強(qiáng)度和量化級(jí)別情況下的閾值設(shè)置還需要作進(jìn)一步的研究，并將該整象素快速運(yùn)動(dòng)估計(jì)算法應(yīng)用于亞象素的快速運(yùn)動(dòng)估計(jì)搜索中。

參考文獻(xiàn)：

[1] PENGQ， ZHANGL， YANGTW. Key-frame reference selection for

non-feedback video communication[J]. The Journal of China Universities of Posts and Telecommunications，2009.16（5）：92-102

[2] ZHU SP， TIAN J. An improved fast fractional pel motion

estimation algorithm based on H.264[c]//IEEE. 2010 IEEE International Conference on Industrial Technology. Washington， DC： IEEE Press，2010：179-182

[3] The H.264/AVC Advanced Video Coding Standard： Overview

and Introduction to the Fidelity Range Extensions，Gary J. Sullivan， Pankaj ToPiwala， and Ajay Luthra. Microsoft Corporation，One Microsoft way Redmond， WA98052 Fast VDO LLC， 7150RiverwoodDr.， Columbia， MD21046 Motorola Ine.， BCS， 6420 Sequence Dr.， San Diego，CA9212.

[4] HENG Z J， FENG Z W. A new fast motion estimation method for

H.264[c].//IEEE. International Conference on Image and signal processing. Washington， DC： IEEE Press，2009：1-4