運動估計是去除視頻序列" title="視頻序列">視頻序列相鄰幀之間冗余信息的有效方法，對整個視頻編碼效果有重要的影響。由兩大國際標準化組織(ISO/IEC的MPEG和ITU-T的VCEG)共同制定的最新的國際視頻編碼標準H.264/AVC仍然采用成熟的基于塊的混合編碼框架^[1]，但由于引入了很多新的編碼技術，如多參考幀預測運動估計，從而可以提供更高的編碼效率" title="編碼效率">編碼效率^[2]。
　　以前的視頻編碼標準如MPEG-4和H.263等都只支持一個參考幀預測。H.264不同于以前的標準，采用了多參考幀預測技術，使得運動搜索范圍從原來的一個參考幀擴展為多個解碼后的參考幀，這樣通常能找到更精確的匹配，從而有助于獲得更高的編碼效率。但是多參考幀預測技術同時也存在一些缺點，對存儲空間和計算能力要求更高^[3]。
　　H.264中引入的拉格朗日率失真最優策略采用窮盡搜索在所有候選參考幀中選擇率失真成本最低的參考幀。拉格朗日率失真最優模式選擇問題可表述為[4～5]:
　　
　　其中m=(m_x,m_y)^T表示某個運動矢量，REF表示某個參考幀，J_motion(s,c,m,REF∣λ_motion)表示在運動矢量m和參考幀REF下的率失真成本，s為原始的視頻信號，c(m,REF)為在運動矢量m和參考幀REF下的重構視頻信號，λ_motion為拉格朗日乘子，R(m-P)表示編碼運動矢量m的比特數,R(REF)表示編碼參考幀REF的比特數，SAD(s,c(m,REF))(Sum Absolute Difference) 為原始信號和重構信號之間的絕對差和，采用(2)式計算:
　　
　　其中B₁,B₂表示塊的水平和垂直像素數，可以取值16, 8或4。
　　設m表示運動矢量搜索范圍，若只允許一個參考幀進行預測，那么每個宏塊" title="宏塊">宏塊需要搜索(2×m+1)²個候選點；若允許N個參考幀進行預測，那么每個宏塊總共有N×(2×m+1)²個候選搜索點。這意味著，運動搜索的計算量、編碼時間隨著預測中總參考幀數成倍增長^[6]。允許的參考幀數越多，運動搜索的計算量、編碼時間就越大。
　　為了減少上述多參考幀預測技術中存在的問題，本文利用相鄰幀間很高的相關性提出了一種低復雜度的快速多參考幀選擇算法。
1 快速多參考幀預測算法
　　在H.264運動估計中，多參考幀運動搜索過程在7種不同的塊大小和形狀條件下進行，按照從16×16到4×4的順序依次進行。對于每一個塊編碼大小，需要在所有可能的參考幀中找出率失真成本最低的參考幀和其相應的運動矢量。多參考幀運動搜索過程首先從概率較高的參考幀REF(0)開始，一直進行到距離當前編碼幀最遠的參考幀REF(N-1)。
　　由于視頻序列相鄰幀間存在很強的時域相關性，一般情況下，最優的匹配通常位于與當前編碼幀緊密相鄰的參考幀，本文采用REF(0)表示這一參考幀；其余的參考幀(在本文中表示為REF(i), i=1,2,...,N-1，設允許的最大參考幀數為N)被選中的概率遠遠小于第一個參考幀REF(0)。
　　為了進一步了解不同參考幀在實際視頻序列中被采納的情況，本文選擇了幾個典型的視頻測試序列，并利用拉格朗日率失真最優搜索策略，在不同參考幀數條件下統計不同參考幀的被選中概率，實驗數據如表1所示。從表1可以看出，在所有參考幀中，REF(0)成為最優參考幀的概率最高，概率高達88.67%，而其余所有參考幀被選中的概率遠遠小于REF(0)。
　　從上述分析可知，參考幀REF(0)成為最終預測幀的概率最高，在這一參考幀中獲得的運動搜索結果對整個編碼性能" title="編碼性能">編碼性能有著重要的影響。因此，可以認為在REF(0)中的搜索范圍越大，對整個編碼性能的改善也會越大。相比較，由于其余的參考幀被選中的概率很低，而且每增加一個參考幀就會增加很大一部分計算量，所以在一定條件下合理地減少在這些參考幀中運動搜索的計算量，對整個編碼性能不會產生顯著影響。由于相鄰幀間存在很強的時域相關性，前一個參考幀中運動搜索后得到的運動信息可以用來預測下一個參考幀的搜索中心。根據運動矢量的中心偏置定理，最優的運動矢量通常位于搜索中心周圍的小范圍里，利用螺旋搜索順序，只需搜索這一小部分區域。

　　減少多參考幀預測計算量的思路如圖1所示。在最重要的參考幀REF(0)中，搜索范圍較大以保證取得較高的預測精度；而在其余不很重要的參考幀中，可以選擇較小的搜索范圍，同時利用前一幀已得到的運動信息預測下一幀的搜索中心。這樣既能減少計算量，同時又不會顯著影響整個編碼性能。

　　本文提出了一種減少多參考幀預測計算量的快速算法。本算法不僅利用了運動矢量的空域相關性來預測第一個參考幀REF(0)的搜索中心，即利用當前宏塊周圍的三個空域相鄰塊的中值運動矢量來預測REF(0)的搜索中心；而且利用了運動矢量的時域相關性，即利用前一幀REF(i-1)所得到的運動信息對下一個參考幀REF(i)的搜索中心進行修正。由于相鄰幀間存在很高的時域相關性，下一幀的最優運動矢量很可能就位于修正后的搜索中心附近，只需對搜索中心周圍的很少一部分候選點進行匹配運算。這樣就省略了很大一部分運算量。
2 模擬結果和分析
　　為了測試本文算法的性能，本文采用H.264參考軟件JM7.0作為實驗平臺。實驗參數設置如下：6個典型的視頻測試序列(Silent、Mobile、Foreman、Template、Bus 和Suzi)、CIF(352×288) 或QCIF(176×144) 圖像格式，每個序列150 幀, 幀率為30f/s，運動矢量搜索范圍為16，量化參數為32, 采用Hadamard transform，GOP結構為IPPP。

　　表2列出了本文提出的算法與原始的采用窮盡搜索的拉格朗日率失真最優模式選擇方法的比較結果。在表2中，△PSNR表示平均峰值信噪比(PSNR)下降值，單位為dB，△bits表示平均碼率增長百分數，△time表示運動估計編碼時間的減少百分數。△time和△bits分別采用式(3)和式(4)得到：
　　
　　其中T_original和B_original分別表示采用原始方法時所用的運動估計編碼時間和總比特數；T_proposed和B_proposed分別表示采用本文提出的方法時所用的運動估計編碼時間和總比特數。
　　從表2中的實驗數據可以看出，與原始的采用窮盡搜索的拉格朗日率失真最優模式選擇方法相比，本文提出的算法可以使運動估計編碼時間平均減少15.18%，同時平均PSNR僅僅下降0.077dB，碼率增長僅僅1.56%(5個參考幀情況下)。此外，對比不同參考幀數的實驗結果，很容易發現允許的參考幀數越多，節省的編碼時間就越多。
　　模擬結果表明本文提出的算法可以節省H.264多參考幀運動預測的計算復雜度，同時對率失真性能的影響很小。這對H.264編碼的實時實現很有利。
參考文獻
1 Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG:Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification.Doc.JVT-G050. 2003
2 Iain Richardson.H.264 and MPEG-4 video compression, video coding for next-generation multimedia.Wiley, UK.2003
3 Yu Wen Huang, Bing-Yu Hsieh, Tu-Chih Wang, etc.Analysis and reduction of reference frames for motion estima-tion MPEG-4 AVC/JVT/H.264. Proceedings International Conference on Multimedia and Expo, ICME, 2003;2(3):145～148
4 H.Chung, D.Romacho, A.Ortega.Fast long-term motion esti- mation for H.264 using multiresolution search. Proceedings. 2003 International Conference on Image Processing, 2003;1:905～908
5 X.Li, E.Q.Li, Y.K.Chen.Fast multi-frame motion estimation algorithm with adaptive search strategies in H.264. ICASSP, Proceedings. (ICASSP ′04). IEEE International Conference on Acoustics, Speech, and Signal Processing, 2004;3:369～372
6 M.J.Chen, Y.Y.Chiang, H.J.Li, M.C.Chi.Efficient multi-frame motion estimation algorithms for MPEG-4 AVC/JVT/H.264.Proceedings of the 2004 International Symposium on Circuits and Systems, ISCAS ′04.,2004;3:737～740