0 引言

H.264采用了減少視頻圖像各幀間冗余度的運動估計算法。運動估計算法傳統的有全搜索(FS)、三步搜索(TSS)、新三步搜索(NTSS)、四步搜索(FSS)等;常用的是鉆石搜索(DS)和非對稱十字交叉多層次六邊形格點運動搜索算法(UMHexagonS)。運動估計是整個視頻編碼中運算量最大的模塊，可占整個軟件編碼器運算量的70%以上。因此視頻系統中編碼器的復雜部分取決于運動估計算法體系結構的復雜性。

1 運動估計算法分析

1.1 鉆石搜索(DS)算法

DS算法即鉆石搜索算法，被MPEG-4國際標準采用并收入驗證模型VM(Verification Model)中，是MPEG-4建議采用的快速運動估計算法。 DS算法采用了兩種搜索模板，分別是有9個檢測點的大模板和有5個檢測點的小模板。搜索時先用大模板LDSP在搜索區域中心及周圍8個點處進行匹配計算，當最小塊誤差出現在中心點處時，將大模板LDSP換為SDSP，再進行匹配計算，這時5個點中的MBD(Minimum Block Distortion)即為最優匹配點;否則，改變中心位置，仍用LDSP重復計算。

1.2 菱形十字搜索(DCS)算法

菱形十字搜索算法(DCS)算法是在DS算法基礎上改進而來，DCS的匹配模板是建立在兩種不同的搜索模板之上的，即大菱形十字型(LDCSP)和小菱形十字型(SDCSP)，如圖1所示。其中，十字型可以對應于實際的運動的矢量分布，而交叉型則是為了加速搜索效果。

DCS算法在進行運動估計匹配運算時，有三種可能的情況：

(1)若MBD點位于LDCSP中心位置，說明圖像是靜止的，DCS算法一步結束;

(2)若MBD點位于LDCSP小十字位置，說明圖像的運動較小，則在此基礎上按照SDCSP模板反復進行交叉搜索。

(3)若MBD點位于LDCSP大十字位置，說明圖像的運動較大，則在此基礎上按照LDCSP模板反復進行交叉搜索。

由此可以看出，DCS算法的優點是，可以根據圖像的運動類型(如上述三種情況)，白適應選擇下一步相應的搜索模板，使搜索與圖像內容有關(基于內容的搜索)，從而得到較好的搜索效果；DCS算法的搜索并不一定要經歷模板由大到小的必然過程，有時一步即可完成搜索；用DCS搜索時，十字形模板對應于實際的運動矢量分布，交叉形模板則有準確性“聚焦”特性，這從本質上體現了DCS是粗定位和準確定位的有效結合。

Script type=text/javascript> function ImgZoom(Id)//重新設置圖片大小防止撐破表格 { var w =$(Id).width; var m = 650; if(w m){return;} else{ var h = $(Id).height; $(Id).height = parseInt(h*m/w); $(Id).width = m; } } window.onload = function() { var Imgs = $(content).getElementsByTagName(img); var i=0; for(;i　　視頻圖像的運動矢量大部分為零矢量或運動很小的矢量。運動矢量為零的塊稱為靜止塊；運動矢量很小的塊(以搜索窗口中心為圓心，兩像素為半徑的圓內)稱為準靜止塊：而其他的稱為運動塊。如果有超過80％運動矢量很小的塊可被看作靜止或準靜止塊。因此，可設一個閥值T，當運動矢量的值小于T時，可用SDCSP搜索法直接進行精確定位，找出最優點；當運動矢量的值大于T時，可用LDCSP搜索算法找出最優點。運動矢量空間域的預測方式有運動矢量中值預測、空間域的上層塊模式運動矢量；在時間域的預測方式有前幀對應塊運動矢量預測和時間域的鄰近參考幀運動矢量預測。本文采用運動矢量中值預測方式。根據與當前E塊相鄰的左邊A塊，上邊B塊和右上邊C塊的運動矢量，取中值作為當前塊的預測運動矢量。如圖2所示。

設當前要編碼塊E的運動矢量為MVp。如果運動矢量的值MVp≥T，則與E塊相鄰的各塊間運動的相關性較高，表明該區域的變化比較平緩；如果運動矢量的值MVpT，則與E塊相鄰的各塊間運動的相關性較低，表明該區域變化比較劇烈。通過對missa、grandmother、carphone、salesman的檢測可知，取閾值T=2。3 自適應運動估計算法結合上述DCS算法和閾值的確定，可采取先對視頻圖像的運動塊進行閾值的判斷，再根據判斷結果進行最佳匹配塊的搜索。具體搜索步驟描述如下：　　Step 1：判斷當前塊運動矢量MVp和閾值確大小。若MVp≥T，則進入Step 2；若MVpT，則進入Step 5。

Step 2：用LDCSP在搜索區域中心及周圍8個點進行匹配運算，然后判斷，找出MBD點。若MBD點位于中心點，說明宏塊是靜止的，DCS算法一步結束，得到最優匹配塊；否則進行Step 3。　　Step 3：若MBD點為LDCSP模版的小十字處，以該點為中心構建SDCSP進行匹配計算，若MBD點位于中心點，所得MBD點為所求。否則，進入Step 4。　　Step 4：若MBD點為LDCSP模版的大十字處，以該點為中心構建LCSP進行匹配計算，進入step 2。　　Step 5：用LDCSP在搜索區域中心及周圍5個點進行匹配運算，然后判斷，找出MBD點。若MBD點位于中心點，所得MBD點為所求；否則繼續Step 5。

算法流程圖如圖3所示

type=text/javascript> function ImgZoom(Id)//重新設置圖片大小 防止撐破表格 { var w =$(Id).width; var m = 650; if(w m){return;} else{ var h = $(Id).height;$(Id).height = parseInt(h*m/w); $(Id).width = m; } } window.onload = function(){ var Imgs = $(content).getElementsByTagName(img); var i=0; for(;i4 實驗結果及說明用搜索時間和PSNR值兩個指標來驗證DCS的性能。本節實驗用到的所有視頻文件均為QCIF(Quartet commonintermediate format)格式。實驗以主頻1.8GHz的PC機上運行的VisualC++6.0為平臺。測試對象為：missa、salesman、news、grandmother、foreman、carphone、claire，搜索范圍為16×16的矩形框，量化范圍為2～12，測試序列中每幀圖像的大小為176×144。4.搜索時間的比較為了時間測試的準確性，測試時采用的是VC++提供的兩個精確時間函數：QueryPerformanceFrequency()和OuerPerformanceCounter()精度對標準測試序列missa、salesman、news、grandmother、foreman、carphone進行精確測定，得表1(數據均為三次測量所求得的平均值)。

實驗結果及說明

用搜索時間和PSNR值兩個指標來驗證DCS的性能。本節實驗用到的所有視頻文件均為QCIF(Quartet commonintermediate format)格式。實驗以主頻1.8GHz的PC機上運行的VisualC++6.0為平臺。測試對象為：missa、salesman、news、grandmother、foreman、carphone、claire，搜索范圍為16×16的矩形框，量化范圍為2～12，測試序列中每幀圖像的大小為176×144。

4.1 搜索時間的比較

為了時間測試的準確性，測試時采用的是VC++提供的兩個精確時間函數：QueryPerformanceFrequency()和OuerPerformanceCounter()精度對標準測試序列missa、salesman、news、grandmother、foreman、carphone進行精確測定，得表1(數據均為三次測量所求得的平均值)。

從表1可知：a.FS搜索效果最佳，但耗時太長；DS算法有較大改進，可以實現實時壓縮；DCS比DS，運行時間都有不同程度的減少，故DCS算法 在搜索速度有優勢。b.從單個序列來看，DCS算法對missa和salesman時間優化最為顯著，分別只占FS算法的7.42％、7.50％和DS算 法的98.17％、97.49％；對carphone序列的搜索速度也有很大優化，占FS搜索算法的7.97％和DS算法的97.82％。綜合視頻特性可 知：DCS算法針對運動平緩的視頻對象搜索速度優化明顯。

4.2 信噪比的比較

對標準測試序列claire和carphone序列進行測定，計算PSNR得表2。

表 2中FS的平均PSNR最高，達到42.38，但搜索時間最長；DS的PSNR最低，為42.31，而DCS為42.35，高于DS算法，且僅低于FS算 法0.03dB。從單個序列來看，DCS算法對claire的優化程度最大，超過了FS的PSNR值，說明DCS算法身體靜止僅面部表情運動特點視頻適 用。用DCS算法計算得到的carphone的PSNR值雖然低于FS算法，但高于DS算法；missa序列的DCS算法的PSNR值和FS、DS法的相 差不大。故DCS算法在搜索速度、圖像質量上均有保證。

5 結束語

本文從搜索時 間和圖像質量兩方面對各種塊匹配運動估計算法進行了性能分析比較。實驗結果表明，將菱形十字交叉搜索算法和閾值判斷結合，在搜索速度方面，有很大程度的優化，而且能得到與FS、DS搜索算法相當的圖像質量。DCS算法針對運動平緩的視頻作用明顯，由此推知該算法適用于電視電話、遠程教育等實時視頻壓縮。

...........................................................

與非深度解讀系列:

半導體公司“大學計劃”的追問和真相

大環境的不景氣是就業環境惡化的元兇，但是也讓我們不禁追問半導體公司的大學計劃對于學子們的真正意義。廠商們的大學計劃都在做些什么？那么多的聯合實驗室有得到充分利用嗎？大學計劃的直接體驗者--老師和學生們是否真正從中受益…….【專欄作者：高揚】

本土IC公司調查筆記

全球經濟不景氣的大環境下一些本土IC公司的創新能力、管理能力、抗風險能力、盈利能力，甚至公司創立的動機都受到一些質疑。一方面官方的消息總是告訴我們中國的半導體產業得到了長足的進步；而街巷小道中又不絕流傳多少本土IC公司倒閉，多少公司靠欺騙，根本沒有核心競爭力….真相只有一個，也許會隨《本土IC公司調查筆記》慢慢開啟…【專欄作者：岳浩】

電子屌絲的技術人生系列

在這個系列里，每個故事都會向你展示一個普通工程師的經歷，他們的青蔥歲月和技術年華，和我們每個人的的生活都有交集。對自己、對公司、對產業、對現在、對未來、對技術、對市場、對產品、對管理的看法，以及他們的經歷或正在經歷的事情，我們可以看到自己的影子，也看清未來的樣子……【專欄作者：任亞運】

細說電子分銷江湖的那些事

對于從事電子分銷行業的同仁們來說這是一個最壞的年代，也是一個最好的年代，我們即面臨國際分銷巨頭在管理、資金、貨源等方面對我們造成的沖擊，又迎來本土集成電路的崛起，個性化服務盛行的機遇，通過這個系列，我想以“第一現場”的經歷帶大家一起了解國內集成電路分銷的那些年、那些事，以及哪些感慨…..【專欄作者：張立恒】

與非網專欄作者申請

聯系人：高揚

郵箱：gaoyang@eefocus.com

關鍵詞： H 264 視頻壓縮 DCS算法 視頻編碼 運動估計