一種用于移動可視電話的快速運動估計算法

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

關鍵詞： 移動終端； H.264； 運動估計； 算法

中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228（2013）03-32-03

0 引言

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

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

移動終端硬件設備的處理能力相對PC機來說有很大的差距，這使得其對視頻編解碼的運算量提出了極高的要求。因此，針對移動終端設備計算能力不足的特點，對H.264編碼器作相應的改進以降低編碼復雜度，是十分必要的。

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

1 運動矢量相關性驗證

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

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

表1 最佳匹配矢量分布表

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

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

2 本文自適應搜索的快速運動估計算法

2.1 本文算法搜索策略設計

本文采用中值法來確定預測搜索起始點，其基本思想是：選取參考塊MB1、MB2、MB3的匹配矢量的中值來預測搜索起始點。采用中值法預測得到的搜索起始點都是相鄰某一塊的運動矢量，因此最終搜索所得的運動矢量場較為平滑，節(jié)省了對運動矢量編碼所需的碼率。當前塊MB0的預測矢量Vp的計算如公式⑴所示。

其中，Vp為當前塊MB0的預測矢量，即預測的運動估計搜索起始點；V1、V2和V3分別為MB1、MB2、MB3的等三個參考塊的運動矢量。

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

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

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

2.2 本文算法搜索流程

本文基于模板自適應的快速運動估計算法流程圖如圖4所示，具體搜索過程如下。

⑴ 若V1=V2=V3，即三個參考塊的運動矢量相等，則表明當前塊所在區(qū)域的運動特性一致。因此，當前塊只需在預測搜索起始點的周圍做小范圍搜索，就極有可能找到全局最優(yōu)匹配塊。即使用小模板在預測搜索起始點周圍進行匹配計算，直至最小SAD出現(xiàn)，搜索結(jié)束；否則，轉(zhuǎn)⑵。

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

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

對于|Vpy|>|Vpx|的情況，采用垂直大模板進行搜索，具體搜索方法與步驟⑶中水平大模板類同。

3 實驗結(jié)果與分析

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

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

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

4 結(jié)束語

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

在本文算法中，對不同運動強度的視頻序列可以通過設置閾值T來改進算法性能。但是，針對不同運動強度和量化級別情況下的閾值設置還需要作進一步的研究，并將該整象素快速運動估計算法應用于亞象素的快速運動估計搜索中。

參考文獻：

[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