??? 摘 要： 針對視頻壓縮標準H.264中運動估計" title="運動估計">運動估計算法的特點，在兼顧視頻圖像" title="視頻圖像">視頻圖像質量和算法運行時間的基礎上，提出了基于視頻壓縮的快速自適應菱形搜索" title="菱形搜索">菱形搜索算法。實驗結果表明，該算法與菱形搜索算法相比，搜索時間平均減少了1.5ms, 信噪比平均提高了1.3dB。
??? 關鍵詞： 視頻壓縮? 自適應? 運動估計? 菱形搜索
?
??? 在多媒體傳輸和存儲中，表示視頻信息的數字需要大量的位數，對信道帶寬和存儲空間提出了很高的要求。相鄰兩幀之間存在很大的時間相關性，即時間冗余，而基于塊匹配的運動估計算法是減少時間冗余的有效方法。目前視頻壓縮標準中[1]的經典運動估計技術有全搜索算法（ES）、三步搜索" title="三步搜索">三步搜索算法(TSS)及菱形搜索算法(DS)等。全搜索算法在所有運動估計算法中性能最好，但計算量過于龐大，實時性不很理想；三步搜索算法在搜索速度和效率上比全搜索法提高了許多，但沒有窮盡所有的點，因而搜索誤差較大，搜索精度和性能受到很大的影響；菱形搜索算法對于所有的視頻序列，在搜索最佳點時，廣度搜索和梯度下降搜索同時進行，即同等地對待搜索區域的各部分，造成較大的搜索冗余，影響了算法的搜索速度。為此，針對視頻編碼標準H.264中運動估計技術的特點，在兼顧視頻圖像質量和搜索時間的基礎上，提出一種新的改進搜索算法——基于視頻壓縮的快速自適應菱形搜索算法ADS(fast adaptive diamond search algorithm)，減少了計算的復雜度并提高了運動補償后的圖像質量。
1 經典菱形搜索算法
??? 經典菱形搜索算法采用兩種搜索模式：大菱形搜索模式和小菱形搜索模式。大菱形搜索模式由一個中心點和它周圍的8個搜索點構成，步長為2。這9個點組成一個菱形，小菱形搜索模式由5個搜索點構成，步長為1。搜索步驟：第1步，最初的大菱形搜索模式以搜索窗口中心為中心點，計算大菱形的9個搜索點的誤差函數。若誤差函數最小的搜索點位于中心，則跳到第3步；否則跳到第2步。第2步，以第1步搜索的9個點中最小點為大菱形的中心點，計算大菱形的9個搜索點的誤差函數。若誤差函數最小的搜索點位于中心，則跳到第3步；否則，跳到第2步。第3步，以上一步搜索的9個點中的最小點為中心點，計算小菱形的5個點的誤差函數。誤差函數最小的塊為最佳匹配快。
??? 菱形搜索算法雖然計算量少，但實現比較復雜，而且由于在搜索區中存在大量的搜索空區[2，3]，所以存在搜索到非最優點的情況，從而使得幀間預測誤差增大。針對實時性與估計精度[4-6]這一對矛盾，提出一種基于視頻壓縮的快速自適應菱形搜索算法，根據運動矢量的時空相關性和中心偏向特性，預測當前塊的運動矢量，減小了搜索的盲目性，較好地實現了視頻圖像的運動估計。
2 快速自適應菱形搜索算法
2.1 中心偏向性
??? 從研究一幅視頻圖像運動矢量的分布情況可以看出，在一定的門限判定條件下，（0，0）這個零矢量出現的概率極大。采用全搜索算法，搜索范圍為（-15，-15）到（15，15），中心處為（0，0）矢量位置，在此處出現極大單峰。這一特性說明，在運動不太劇烈的情況下，運動矢量大量積聚在零矢量處，在預測下一幀當前塊的運動矢量時可以優先考慮零矢量。
2.2 搜索模式的選擇
??? 許多算法的搜索范圍是固定的，搜索效率并不是很高。因為在視頻圖像序列的兩幀之間，只有少部分有很大的運動，而且有相當一部分是沒有運動的，如固定背景。若能根據不同的塊運動情況而采用不同的搜索范圍，則可節省計算量，所以應首先判斷搜索起點的運動類型。
??? 因為搜索起點的絕對誤差" title="絕對誤差">絕對誤差總和反映了該塊某種程度的運動，搜索起點的絕對誤差總和越大，意味著當前幀與前一幀之間的差異越大，這一塊的位移可能越大，同時為在前一幀中找到最小的誤差塊，就需要對這一塊做出大范圍的搜索，否則只需要做出小范圍的搜索?；谶@樣一個思想，初始運動矢量的絕對誤差總和就可作為一個判斷運動類型的依據，從而根據不同的運動類型，確定對應于各種預測結果所應采取的搜索范圍以及搜索模式。絕對誤差總和（SAD）由下式決定：
??? 
??? 式中，F(i，j)為被壓縮的(m×n)宏塊；G(i，j)為基準(m×n)宏塊；(dx，dy)為搜索處的運動矢量，且dx={-p，p}，dy={-p，p}；p是搜索范圍參數。
??? 根據絕對誤差總和，把運動類型分為三類：當SAD
2.3閾值的選取
??? 首先計算當前幀所選塊與參考幀中的相同位置處的對應塊的絕對誤差總和，記為prev_SAD。則設
??? 
式中，α一般取為0.9<α<1.4，β取為1.2<β<2.5，且α<β，α、β屬于經驗值。
??? 若當前幀為第一幀，則不存在prev_SAD。通過大量的實驗，在不影響視頻圖像質量并且考慮傳輸實時性的情況下，T1取500左右，T2取800左右。
3 仿真分析
??? 為了比較快速自適應菱形搜索算法的效果，采用8bit的視頻圖像序列對全搜索法、三步搜索法、菱形法以及快速自適應菱形搜索法在相同的條件下進行計算機仿真。
3.1 重建幀的比較
??? 采用susie（352×240）序列，塊的大小為16×16，搜索范圍P為7。以第五幀作為參考幀，分別用全搜索算法以及快速自適應菱形搜索算法得到第七幀的重建幀。可以看出，快速自適應菱形搜索算法重建的視頻圖像非常接近視頻圖像的原始幀, 結果如圖1所示。
?
?
3.2 誤差幀的比較
??? 為了直觀地觀察新算法的效果，用峰值信噪比(PSNR)和均方誤差(MSE)來衡量各種運動估計技術的性能。對于8bit的視頻圖像來說，PSNR定義為：
??? 
式中，MSE表示均方誤差，由下式決定：
??? 
式中，f(i，j)是視頻圖像序列的原始幀，g(i，j)是利用運動矢量重建的幀。仍然采用susie（352×240）序列的第一幀作為參考幀，塊的大小采用16×16，搜索范圍P為7。分別用ES算法、TSS算法、DS算法及ADS算法得到第二幀的誤差幀。圖2中所示為ADS算法和DS算法產生的誤差幀。
?
?
3.3 性能的比較
??? 以MSE和PSNR作為衡量搜索算法性能的標準，通過用相應的搜索算法得到各自的性能，采用susie（352×240）序列為視頻測試序列，塊的大小為16×16，搜索范圍p為7，分別用各種搜索方法計算視頻序列中連續20幀的MSE和PSNR，實驗結果如圖3所示。
?
?
3.4 搜索匹配時間的比較
??? 采用missamerican（360×288）序列的第五幀作為參考幀，塊的大小采用16×16，搜索范圍P為7。在同樣的環境下，分別用ES算法、TSS算法、DS算法以及ADS算法進行匹配得到恢復的第六幀，搜索匹配時間分別如表1所示。
?
?
??? 在上面的實驗1中，采用susie（352×240）序列的第五幀，用ADS算法對其第七幀進行重建，從主觀上看，ADS算法的重建視頻圖像非常接近原始的視頻圖像；在實驗2中，采用susie(352×240)序列對誤差幀進行比較，可以看出ADS算法比DS算法產生的誤差平均降低了約300個數量級；在實驗3中，采用susie（352×240）序列對算法進行性能比較，可得ADS算法的性能曲線都優于DS算法的性能曲線，峰值信噪比比DS算法平均提高了1.3dB，相應地均方誤差也降低了。對于運動緩慢的視頻序列，新算法的性能幾乎逼近全搜索算法；在實驗4中，用各種算法對missamerican(360×288)序列進行匹配，比較可得改進算法的搜索匹配時間比DS算法平均減少了約1.5ms。
??? 基于視頻壓縮的快速自適應菱形搜索算法，充分利用了視頻圖像序列的時空相關特性，采用了大小菱形搜索模式，實現了運動矢量高速而較精確的估計。仿真結果表明，與全搜索算法、三步搜索算法、菱形搜索算法等一些優秀算法相比，新算法的運動估計準確性高、預測質量好。在可視電話、終端會議等的實時視頻通信中，該算法可取得較好的效果。
參考文獻
[1] 朱秀昌，劉峰，胡棟.數字圖像處理與圖像通信[M].北京：北京郵電大學出版社，2002.
[2] KELLER Y，AVERBUCH A.Fast motion estimation using?bidirectional gradient methods[J].IEEE Trans.Image Processing，2004，13：1042-1054.
[3] ZHU S，MA K K.A new diamond search algorithm for fast block-matching motion estimation[J].IEEE Trans on Image Processing.2000，9：287-290.
[4] ELAD M，HEL-OR Y.A fast super-resolution reconstruction algorithm for pure translational motion and common space?invariant blur[J].IEEE Trans.Image Processing，2001，10：1187-1193.
[5] ALTUNBASAK Y，PATTI A，MERSEREAU R.Super-resolution still and video reconstruction from mpeg-coded video[J].IEEE Trans.Circuits Syst.Video Technol.，2002，12：217-226.
[6] LIAW Y C，LAI J Z C，LO W.Image restoration of compressed image using classified vector quantization[J].Pattern?Recognit.，2002，35：181-192.