基于AVS的多參考幀快速運動搜索算法

李媛媛

（太原理工大學 電氣與動力工程學院，山西 太原 030024）

0 引言

AVS（Advanced Audio－Video Coding－Decoding Standard）標準，是我國“數字音視頻編解碼技術標準工作組”自主研發的，擁有自主知識產權的第二代視頻壓縮標準［1－3］，它也是目前最先進的音視頻壓縮編解碼標準之一。AVS技術標準主要包括系統、視頻、音頻和數字版權管理等4個方面。AVS視頻編碼部分具有計算復雜度低、壓縮比高、圖像質量高、專利授權費用低等優點，對于我國實施自主發展的多媒體產業具有非常重要的經濟意義和社會意義。

視頻編碼算法主要包括運動估計、運動補償、DCT 變換、量化、熵編碼、濾波等模塊［4－6］。其中運動估計主要包括運動搜索和模式選擇兩部分。運動搜索是通過一定的匹配準則在參考幀中搜索得到當前塊的最佳匹配塊，盡可能地消除幀間冗余，減少編碼信息量，從而提高編碼效率。為了尋找到最優匹配塊，AVS視頻編碼標準從已編碼的兩幀中搜索最佳匹配塊，使得運動搜索的計算復雜度大大增加。模式選擇是對編碼模式通過代價值的比較選取代價值最小的模式為當前塊的最佳編碼模式。因此，降低運動搜索運算量是提高AVS視頻編碼器編碼性能的重要內容。本文提出了一種新的菱形搜索形式，該方法主要是根據參考幀的位置不同而選用不同形狀的菱形搜索模式，在保證視頻質量不變的情況下使搜索點數大大減少。

1 AVS運動估計過程

在AVS視頻編碼中，幀間預測編碼就是找出當前塊在參考幀中的位置，兩者空間位置的相對偏移量就是運動矢量。運動估計就是得到運動矢量的過程，運動估計又包括運動搜索和模式選擇兩個步驟。傳統的運動搜索算法有全搜索法和快速搜索法。快速搜索法主要包括菱形搜索（DIA）、六邊形搜索（HEX）、非對稱十字六邊形搜索（UMH）等。

AVS幀間預測模式有4 種：16＊16 模式、16＊8模式、8＊16模式和8＊8模式。由運動搜索得到當前塊在參考幀中的最佳匹配塊，計算匹配塊和當前塊的代價值，通過代價值的比較選出以上4種預測模式中代價值最小的模式做為最佳預測模式。

1.1 DIA 搜索和模式選擇介紹

1.1.1 運動搜索

AVS的運動搜索是基于塊的搜索，最佳匹配塊由運動搜索的率失真函數Bcost（x，y）進行選擇：

其中：SA（T）D（x，y）為當前塊x 和匹配塊y 的像素差經過哈達瑪變換后所得到的系數之和；IMOTION為運動估計的拉格朗日乘子；△mv為預測運動矢量與實際運動矢量的差值，b（△mv）為編碼△mv 所需比特數［7］。Bcost（x，y）值最小的候選塊就是當前塊的最佳匹配塊。

在運動搜索算法中，根據運動矢量分布的中心偏移特性而得到的菱形搜索算法（DIA）搜索模型較簡單，并且運算量也較小。DIA 搜索算法流程如圖1所示。

圖1 DIA 搜索算法流程圖

DIA 算法中，候選搜索起始點是利用當前塊與鄰近塊的空間相關性和與參考幀中對應位置的時間相關性預測得到；通過將每次菱形搜索得到的最優點和上次得到的最優點比較看其是否相同確定搜索是否結束，最優點對應的塊就是當前塊的最佳匹配塊。

1.1.2 模式選擇

4種預測模式通過運動搜索得到最佳匹配塊后，由公式（2）根據已有的最佳匹配塊確定4種預測模式中的最佳預測模式。模式選擇的率失真函數J（s，c，MODE／QP）表示如下：

其中：D（s，c，MODE／QP）為待編碼塊c和重建塊s 的差值平方和，MODE 為預測模式，QP 為量化參數；λMODE為預測模式的拉格朗日乘子；R（s，c，MODE／QP）為編碼殘差所用的比特數。J（s，c，MODE／QP）取值最小的預測模式即為當前塊的最佳預測模式。

1.2 最佳參考幀選擇的概率分析

AVS視頻編碼標準中P 幀和B 幀最多可有兩幀參考圖像。P幀可參考前向的兩幀，B 幀可參考一前一后的兩幀。根據時間相關性可推測時間相差越小的兩幀相關性越強。

非對稱十字形多層次六邊形格點搜索是一種優秀的搜索算法，該算法能夠保證較高的視頻質量、較低的碼率。本文采用UMHexagonS 搜索方法，為了驗證當前幀的前一幀和當前幀的相關性最強、被選為最佳參考幀的幾率較大，分別對分辨率為352×288的CIF格式和分辨率為176×144的QCIF 格式的測試序列進行了實驗統計，實驗中所用測試序列均為標準序列（如news、mobile、foreman等）。統計結果見表1和表2。

從表1和表2可以看出，第1幀i＿ref0被選為當前幀參考幀的概率最大，平均可達92.33%，而第2幀i＿ref1被選為當前幀參考幀的概率僅為7.67%。也就是說，距離當前幀越近的參考幀被選為當前幀優秀參考幀的概率越大。

表1 CIF格式參考幀被選用的概率統計結果

表2 QCIF格式參考幀被選用的概率統計結果

2 變換菱形搜索算法

2.1 兩種菱形搜索模板

運動搜索算法中的UMHexagonS搜索是一種多種搜索模型混合使用的搜索算法，它能夠有效地避免運動搜索過早陷入局部最優，并且保持了良好的率失真性能，但是由于搜索模型較復雜，搜索點數較多，使得運算量大大增加。傳統的菱形搜索法搜索模型較簡單、計算量較小，視頻質量和UMHexagonS搜索算法相比有明顯下降。本文提出了一種新的菱形搜索方法，對不同參考幀采用不同的菱形搜索模板。

具體搜索模板如圖2所示，模板0中心點周圍有8個搜索點，模板1中心點周圍有4個搜索點，模板1是在模板0的基礎上減少外圍的4個搜索點形成的。模板0用于對參考幀i＿ref0進行匹配塊搜索，較大范圍的搜索可以得到較好的運動矢量。模板1用于對參考幀i＿ref1進行搜索，在前面運動矢量的基礎上參考幀i＿ref1使用縮小的菱形模板進行搜索。

圖2 變換的菱形模板

2.2 算法實現

針對已編碼的兩幀參考幀采用上述模板0和模板1進行菱形搜索，搜索流程如圖3所示。

變形菱形搜索中，候選搜索點是根據當前塊與鄰近塊的空間相關性和當前塊與參考幀的時間相關性預測而得到的。對于和當前幀相關性更強的參考幀i＿ref0采用模板0進行搜索，參考幀i＿ref1采用較簡單的模板1進行搜索。如果搜索到的新的最優點和上一搜索中心點相同則結束搜索，否則繼續使用該搜索模板進行搜索。

圖3 變換菱形搜索流程圖

3 實驗結果與分析

本文分別從峰值信噪比（PSNR）和搜索點數兩個方面對上述優化算法和UMHexagonS搜索算法進行了比較。主要參數設置如下：參考幀為2 幀；I幀（只采用幀內預測模式）的量化參數設為30，P 幀（采用幀內和幀間預測模式，幀間預測時用前向參考）的量化參數設為32，B幀（采用幀內和幀間預測模式，幀間預測時用雙向參考）的量化參數設為34；編碼序列為IPBBPBB格式。測試了不同格式和不同運動劇烈程度的測試序列的峰值信噪比和搜索點數的變化，實驗數據見表3和表4。

表3 QCIF格式的實驗結果

在表3和表4中，“－”號表示降低。由測試結果可以看出，在所有測試序列信噪比降低不超出0.12dB的情況下，搜索點數明顯減少，最多可以減少92.12%?？傮w來看，在峰值信噪比變化不明顯的情況下，優化算法的搜索點數大幅度減少，進而運動搜索計算量和搜索時間也都大大降低，提高了編碼器的性能，更好地滿足了視頻壓縮編碼的實時性要求。

表4 CIF格式的實驗結果

4 結束語

本文通過對AVS編碼器中兩幀參考幀被選為優秀參考幀概率的深入分析和研究，提出了一種低復雜度的變換菱形搜索算法。對距離當前幀不同的參考幀采用不同的搜索模板，從而在保證視頻質量的條件下，運動搜索的計算量大大降低，大幅度提高了AVS 視頻編碼速度，更有利于AVS編碼器的硬件實現和實時性要求。

［1］ 周波，王力波，劉東華，等.用于AVS視頻編碼的快速子像素運動搜索算法［J］.計算機應用研究，2008，25（7）：2238－2240.

［2］ 紹娟，張衛寧，陳棟，等.AVS中B 幀宏塊模式選擇快速方法［J］.計算機工程與應用，2011，47（5）：179－181，245.

［3］ 畢厚杰.視頻壓縮編碼標準——H.264／AVC［M］.北京：人民郵電出版社，2005.

［4］ 張新安，宮彥軍，陳愛武，等.一種AVS－M 運動搜索快速算法［J］.計算機工程，2011，37（9）：260－262.

［5］ 康慧斌.AVS視頻編碼中子像素運動估計算法的優化研究［J］.控制工程，2010（7）：14－17.

［6］ 葉文龍，袁友偉，汪世瑜，等.H.264 塊匹配運動估計中UMHexagonS算法的優化［J］.計算機工程與應用，2011，47（25）：133－136.

［7］ 楊春玲，王華興.基于結構相似度的H.264 快速運動估計算法［J］.華南理工大學學報（自然科學版），2008，36（8）：28－32.