改進的十字—菱形運動估計搜索算法研究與實現

摘要：提出了一種改進的十字—菱形搜索(ICDS)算法，給出了在搜索的初始階段使用小十字搜索模型對小的運動矢量搜索并在相繼的搜索過程中使用具有方向性的菱形搜索模型對大運動矢量進行搜索的步聚。介紹了該算法的實現結構，并分析了該算法搜索性能。

關鍵詞：塊匹配運動估計； 改進型十字菱形搜索算法； 十字中心偏置特性

中圖分類號：TP391文獻標志碼：A

文章編號：1001－3695(2007)08－0212－03

隨著計算機技術與通信技術的發展，圖像處理與傳輸，特別是視頻圖像傳輸成為人們獲取信息的主要途徑。然而表達視頻圖像所需要的巨大數據量與有限的傳輸通道成為視頻信息交換的主要障礙，因此視頻壓縮是視頻傳輸之前的重要任務。運動估計是視頻壓縮技術中非常重要的組成部分，其估計方法直接決定了視頻圖像壓縮編碼的運行速度。運動估計的方法很多，其中基于塊匹配的運動估計算法(BMA)由于實現較簡單且容易而受到廣泛關注。全搜索(FS)作為BMA的一種原始算法雖然搜索精度極高，但所需計算量相當大，很難適應實際應用， 特別是實時應用的要求。為了改善搜索速度，在過去的二十年中出現了大量快速BMA。比較有代表性的算法有三步搜索法(3SS)和二維對數法(2LOGS)等。這些算法主要利用運動矢量的均勻分布模式進行搜索，其搜索步長較大，因此可能導致搜索方向的不確定性和搜索的局部性。為了解決上述問題，人們提出了利用現實圖像序列運動矢量空間分布中心偏置特性的算法，如四步搜索法(4SS)、新三步搜索法(N3SS)。由于這些算法充分考慮了運動矢量概率(MVP)分布，因此在保持與FS相當的圖像質量的同時，很大程度地提高了搜索速度。在此基礎上，出現了大量的非矩形搜索模型的算法，如菱形搜索算法(DS)[1，2]和六邊形搜索算法(HEXBS)[3]等。其中：DS算法被MPEG－2/4標準所采用[4]。除了搜索模型的形狀對搜索的影響之外，搜索模型的大小以及搜索策略對搜索速度和圖像質量同樣有影響。為此，近來出現了十字—菱形搜索(CDS)算法[5]、十字—菱形—六邊形搜索(CDHS)算法[6]等。但這些算法沒有充分考慮運動矢量概率分割的方向性，在搜索過程中需要比較多的搜索點數，為了進一步體現真實序列的偏置特性，加快搜索速度，本文提出了改進的十字—菱形搜索(ICDS)算法。

1搜索算法

1．1 搜索模型

以MVP的統計分布特性為基礎的模型設計方法是獲得最大搜索性能改善的方法之一，因此本文對16個含有不同運動特性的QIF格式和SIF格式的序列進行測試，并使用FS算法以絕對誤差和(SAD)作為塊失真測量(BDM)標準來計算序列在搜索窗口內MV的平均概率分布（MVP）。根據測試結果可以發現運動矢量分布的中心偏置性滿足如下結論：

從式（2）可知：半徑|p|>2的DSP對于大的運動矢量的搜索是有效的。因此，文獻[1，2]中使用DSP進行搜索。但對于現實的運動序列而言，其水平運動和垂直運動幾率大，這種情況可以從MVP分布圖1的整體分布角度得到驗證， MVP的分布是具有極強的沿中心水平和垂直軸偏置分布的方向性。從圖1可以看出，半徑為2的菱形是不同于MVP分布的分解線，因此對半徑為2的菱形上各點的MVP討論是決定使用不同模型搜索的關鍵。測試的數據可知，菱形上四個頂點的MVP之和大于其他點上的MVP之和。為此，模型設計和搜索步驟決定于這四個頂點搜索。圖2給出了兩個條件：a)最初確定最小BDM位于點(±2， 0)；b)最小BDM位于點(0， ±2)下，最終搜索到MV在不同位置上的概率。其中：圖1（b）為條件a）下最終搜索到MV的概率分布；圖1（c） 為條件b）下最終搜索到MV的概率分布結果。根據該結果可知概率分布具有極強的方向性。

基于此特性，當搜索大運動矢量時，首先使用大十字模型（LCSP）對其四個頂點進行搜索，如圖2（a）所示，獲得搜索方向，然后可以使用具有方向的菱形搜索模型（DDSP）代替大菱形搜索模型，如圖2（b）所示。該模型包括垂直和水平兩個形式，即VDSP與HDSP。

1．3 算法分析

通過理論計算，可得到ICDS算法搜索每個MV所需要的最小搜索點數， 如圖4(a)所示。

(a) ICDS算法每個運動矢量所需的最少搜索點數(b) 與DS算法相比最大節省搜索點數

圖4搜索點數統計

根據圖4可看出，每個MV所需要的搜索點數與其平均MV的概率分布成反比，這一點完全符合實際設計要求。為了更好地分析ICDS算法的有效性，圖4(b)顯示了在±4的區域中，ICDS相對DS算法所節省的最大搜索點數量。可以觀察到，ICDS算法相對DS算法而言中心位置(0，0)上每塊可以節省八個搜索點，在半徑p=1的正方形邊上每點最多可節省兩個點，而在兩個正交軸上所節省的點數隨著距離的增加而增加，這充分體現了算法所強調的搜索方向性。而ICDS算法相對于DS算法每塊搜索點的統計平均增益可以通過如下的定量分析[5]：

其中：Pp(S)是半徑為p的正方形分布；n為該正方形邊上每個位置所節省的平均搜索點數。根據統計數據Pp(S)，理論上可計算出ICDS相對于DS算法每塊平均節省搜索點為G=4．14。

同樣，可以根據 ICDS相對于CDS節省的最大搜索點數，理論上計算出ICDS算法相對于CDS算法的平均增益，大約是每塊節省2.78個搜索點。

2算法的硬件實現

該算法所有的搜索模型上只有五個搜索點，為了體現硬件實現的實時性，在使用可編程器件實現該算法時，采用了如圖5所示的并行結構。該算法的實現結構使用了五個并行失真誤差計算模塊和一個比較器。

3實驗結果與分析

為了驗證所提出的ICDS算法，使用了典型序列進行測試。給出了對較小運動CIF格式的序列 “Mother Daughter”和較大運動的CIF格式序列“Stefan”的結果，如表1所示。在所有的測試過程中，平均絕對差(SAD)作為BDM標準，塊的大小為6，搜索窗口為w=±7。表1給出了這兩個序列從四個方面與其他五個BMA比較：FS、3SS、4SS、DS、CDS。

從表1可以發現ICDS算法與其他MBA相比，所需要的搜索點數最少，而平均PSNR幾乎保持不變或稍微小一點。如與DS比較，ICDS在每塊中節省的搜索點大約為4．59~6．84，它比理論估計值4.14要大。同樣與CDS比較，它每塊平均節省搜索點數大約為1.86~4.56。可得出不同算法每塊的平均搜索點數量的關系是ICDS

從這兩個序列的實驗結果可以看出，在速度改善的同時，ICDS算法平均PSNR與其他算法相比小運動序列“MatherDaughter”幾乎保持不變，而運動大的序列“Stefan”只有微小的減少。這說明ICDS算法在保持同樣性能的前提下，很大程度上提高了搜索速度。

根據表1可計算出ICDS相對CDS與DS的平均速度改善率(SIR)和平均PSNR的變化。對于視頻會議序列，如“MatherDaughter”，由于在中心點附近有高的中心偏置特性，ICDS相對CD和CDS算法分別可達到84%與64%的速度改善。對于相對大的運動序列，“Stefan”所得到的速度改善分別為48%、38%。圖6(a)和7(a)分別顯示了序列“MD”和“Stefan”的平均的搜索點數曲線。這些曲線清楚地表明了ICDS算法的搜索點數比其他MBA減少很多。圖6(b)和圖7(b)顯示了兩個序列相應PSNR性能與不同BMA的比較。這些圖說明了ICDS算法的失真錯誤稍微大于3SS、4SS、DS和CDS。

4結束語

本文通過對運動矢量分布的分析，強調了MV的CCB特性以及條件分布的方向性，提出了改進的十字—菱形塊匹配運動估計算法。該算法使用了SCSP對小的運動矢量進行搜索，使所需要的搜索點盡可能地少，加快對靜止或準靜止塊的搜索。在后繼的搜索步驟中使用了變形的菱形搜索模型，充分考慮搜索的方向性，加速對大運動矢量的搜索。本文的實驗結果顯示了該算法不僅保持與DS和CDS算法相當的失真性能，而且可以提高大約60%和35%的搜索速度。總之，ICDS算法與其他快速BMA相比，搜索速度更快，魯棒性更強，適合視頻應用的廣泛領域，特別是低比特率的視頻會議系統和可視電話等。

參考文獻：

［1］THAM J Y， RANGANATH S， RANGANATH M， et al. A novel unrestricted centerbiased diamond search algorithm for block motion estimation[J]. IEEE Trans Circuits Syst Video Technol， 1998，8(4):369－377.

[2］ZHU S， MA K K. A new diamond search algorithm for fast blockmatching motion estimation[J]. IEEE Trans Image Process， 2000，9(2):287－290.

[3］ZHU Ce， LIN Xiao， CHAU L P， et al. A novel hexagonbased search algorithm for fast block motion estimation [C]//Proc of IEEE Int Conf Acoust， Speech， Signal Processing.Singapore:[s.n.]， 2001:15931596.

[4］FUKUNAGA S， NAKAYA Y， SON S H， et al. ISO/IECJ TCI/SC29/WG11 MPEG99/N2932， MPEG－4 video verification model version 14.0 [S]. Victoria， Australia:[s.n.]， 1999.

[5］CHEUNG C H， PO L M. A novel crossdiamond search algorithm for fast block motion estimation[J]. IEEE Trans Circuits Syst Vi￣deo Technol， 2002，12(12):1168－1177.

[6］CHEUNG C H， PO L M. Novel crossdiamondhexagonal search algorithms for fast block motion estimation [J]. IEEE Trans Multime￣dia， 2005，7(1):16－22.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”