??? 摘 要： 針對視頻壓縮標(biāo)準(zhǔn)H.264中運動估計" title="運動估計">運動估計算法的特點,，在兼顧視頻圖像" title="視頻圖像">視頻圖像質(zhì)量和算法運行時間的基礎(chǔ)上，提出了基于視頻壓縮的快速自適應(yīng)菱形搜索" title="菱形搜索">菱形搜索算法,。實驗結(jié)果表明,，該算法與菱形搜索算法相比，搜索時間平均減少了1.5ms, 信噪比平均提高了1.3dB,。
??? 關(guān)鍵詞： 視頻壓縮? 自適應(yīng)? 運動估計? 菱形搜索
?
??? 在多媒體傳輸和存儲中,，表示視頻信息的數(shù)字需要大量的位數(shù)，對信道帶寬和存儲空間提出了很高的要求,。相鄰兩幀之間存在很大的時間相關(guān)性,，即時間冗余，而基于塊匹配的運動估計算法是減少時間冗余的有效方法,。目前視頻壓縮標(biāo)準(zhǔn)中[1]的經(jīng)典運動估計技術(shù)有全搜索算法（ES）,、三步搜索" title="三步搜索">三步搜索算法(TSS)及菱形搜索算法(DS)等。全搜索算法在所有運動估計算法中性能最好,，但計算量過于龐大,，實時性不很理想；三步搜索算法在搜索速度和效率上比全搜索法提高了許多,，但沒有窮盡所有的點,，因而搜索誤差較大，搜索精度和性能受到很大的影響,；菱形搜索算法對于所有的視頻序列,，在搜索最佳點時，廣度搜索和梯度下降搜索同時進(jìn)行,，即同等地對待搜索區(qū)域的各部分,，造成較大的搜索冗余，影響了算法的搜索速度,。為此,，針對視頻編碼標(biāo)準(zhǔn)H.264中運動估計技術(shù)的特點，在兼顧視頻圖像質(zhì)量和搜索時間的基礎(chǔ)上,，提出一種新的改進(jìn)搜索算法——基于視頻壓縮的快速自適應(yīng)菱形搜索算法ADS(fast adaptive diamond search algorithm),，減少了計算的復(fù)雜度并提高了運動補(bǔ)償后的圖像質(zhì)量。
1 經(jīng)典菱形搜索算法
??? 經(jīng)典菱形搜索算法采用兩種搜索模式：大菱形搜索模式和小菱形搜索模式,。大菱形搜索模式由一個中心點和它周圍的8個搜索點構(gòu)成,，步長為2,。這9個點組成一個菱形，小菱形搜索模式由5個搜索點構(gòu)成,，步長為1。搜索步驟：第1步,，最初的大菱形搜索模式以搜索窗口中心為中心點,，計算大菱形的9個搜索點的誤差函數(shù)。若誤差函數(shù)最小的搜索點位于中心,，則跳到第3步,；否則跳到第2步。第2步,，以第1步搜索的9個點中最小點為大菱形的中心點,，計算大菱形的9個搜索點的誤差函數(shù)。若誤差函數(shù)最小的搜索點位于中心,，則跳到第3步,；否則，跳到第2步,。第3步,，以上一步搜索的9個點中的最小點為中心點，計算小菱形的5個點的誤差函數(shù),。誤差函數(shù)最小的塊為最佳匹配快,。
??? 菱形搜索算法雖然計算量少，但實現(xiàn)比較復(fù)雜,，而且由于在搜索區(qū)中存在大量的搜索空區(qū)[2,，3]，所以存在搜索到非最優(yōu)點的情況,，從而使得幀間預(yù)測誤差增大,。針對實時性與估計精度[4-6]這一對矛盾，提出一種基于視頻壓縮的快速自適應(yīng)菱形搜索算法,，根據(jù)運動矢量的時空相關(guān)性和中心偏向特性,，預(yù)測當(dāng)前塊的運動矢量，減小了搜索的盲目性,，較好地實現(xiàn)了視頻圖像的運動估計,。
2 快速自適應(yīng)菱形搜索算法
2.1 中心偏向性
??? 從研究一幅視頻圖像運動矢量的分布情況可以看出，在一定的門限判定條件下,，（0,，0）這個零矢量出現(xiàn)的概率極大。采用全搜索算法,，搜索范圍為（-15,，-15）到（15，15），中心處為（0,，0）矢量位置,，在此處出現(xiàn)極大單峰。這一特性說明,，在運動不太劇烈的情況下,，運動矢量大量積聚在零矢量處，在預(yù)測下一幀當(dāng)前塊的運動矢量時可以優(yōu)先考慮零矢量,。
2.2 搜索模式的選擇
??? 許多算法的搜索范圍是固定的,，搜索效率并不是很高。因為在視頻圖像序列的兩幀之間,，只有少部分有很大的運動,，而且有相當(dāng)一部分是沒有運動的，如固定背景,。若能根據(jù)不同的塊運動情況而采用不同的搜索范圍,，則可節(jié)省計算量，所以應(yīng)首先判斷搜索起點的運動類型,。
??? 因為搜索起點的絕對誤差" title="絕對誤差">絕對誤差總和反映了該塊某種程度的運動,，搜索起點的絕對誤差總和越大，意味著當(dāng)前幀與前一幀之間的差異越大,，這一塊的位移可能越大,，同時為在前一幀中找到最小的誤差塊，就需要對這一塊做出大范圍的搜索,，否則只需要做出小范圍的搜索,。基于這樣一個思想,，初始運動矢量的絕對誤差總和就可作為一個判斷運動類型的依據(jù),，從而根據(jù)不同的運動類型，確定對應(yīng)于各種預(yù)測結(jié)果所應(yīng)采取的搜索范圍以及搜索模式,。絕對誤差總和（SAD）由下式?jīng)Q定：
??? 
??? 式中,，F(xiàn)(i，j)為被壓縮的(m×n)宏塊,；G(i,，j)為基準(zhǔn)(m×n)宏塊；(dx,，dy)為搜索處的運動矢量,，且dx={-p，p},，dy={-p,，p},；p是搜索范圍參數(shù)。
??? 根據(jù)絕對誤差總和,，把運動類型分為三類：當(dāng)SAD
2.3閾值的選取
??? 首先計算當(dāng)前幀所選塊與參考幀中的相同位置處的對應(yīng)塊的絕對誤差總和,，記為prev_SAD。則設(shè)
??? 
式中,，α一般取為0.9<α<1.4,，β取為1.2<β<2.5，且α<β,，α,、β屬于經(jīng)驗值。
??? 若當(dāng)前幀為第一幀,，則不存在prev_SAD,。通過大量的實驗，在不影響視頻圖像質(zhì)量并且考慮傳輸實時性的情況下,，T1取500左右,，T2取800左右。
3 仿真分析
??? 為了比較快速自適應(yīng)菱形搜索算法的效果,，采用8bit的視頻圖像序列對全搜索法,、三步搜索法、菱形法以及快速自適應(yīng)菱形搜索法在相同的條件下進(jìn)行計算機(jī)仿真,。
3.1 重建幀的比較
??? 采用susie（352×240）序列,，塊的大小為16×16，搜索范圍P為7,。以第五幀作為參考幀,，分別用全搜索算法以及快速自適應(yīng)菱形搜索算法得到第七幀的重建幀,。可以看出,，快速自適應(yīng)菱形搜索算法重建的視頻圖像非常接近視頻圖像的原始幀, 結(jié)果如圖1所示,。
?
?
3.2 誤差幀的比較
??? 為了直觀地觀察新算法的效果，用峰值信噪比(PSNR)和均方誤差(MSE)來衡量各種運動估計技術(shù)的性能,。對于8bit的視頻圖像來說,，PSNR定義為：
??? 
式中，MSE表示均方誤差,，由下式?jīng)Q定：
??? 
式中,，f(i，j)是視頻圖像序列的原始幀,，g(i,，j)是利用運動矢量重建的幀。仍然采用susie（352×240）序列的第一幀作為參考幀,，塊的大小采用16×16,，搜索范圍P為7。分別用ES算法,、TSS算法,、DS算法及ADS算法得到第二幀的誤差幀。圖2中所示為ADS算法和DS算法產(chǎn)生的誤差幀,。
?
?
3.3 性能的比較
??? 以MSE和PSNR作為衡量搜索算法性能的標(biāo)準(zhǔn),，通過用相應(yīng)的搜索算法得到各自的性能，采用susie（352×240）序列為視頻測試序列,，塊的大小為16×16,，搜索范圍p為7，分別用各種搜索方法計算視頻序列中連續(xù)20幀的MSE和PSNR,，實驗結(jié)果如圖3所示,。
?
?
3.4 搜索匹配時間的比較
??? 采用missamerican（360×288）序列的第五幀作為參考幀，塊的大小采用16×16,，搜索范圍P為7,。在同樣的環(huán)境下，分別用ES算法,、TSS算法,、DS算法以及ADS算法進(jìn)行匹配得到恢復(fù)的第六幀，搜索匹配時間分別如表1所示,。
?
?
??? 在上面的實驗1中,，采用susie（352×240）序列的第五幀，用ADS算法對其第七幀進(jìn)行重建,，從主觀上看,，ADS算法的重建視頻圖像非常接近原始的視頻圖像,；在實驗2中，采用susie(352×240)序列對誤差幀進(jìn)行比較,，可以看出ADS算法比DS算法產(chǎn)生的誤差平均降低了約300個數(shù)量級,；在實驗3中，采用susie（352×240）序列對算法進(jìn)行性能比較,，可得ADS算法的性能曲線都優(yōu)于DS算法的性能曲線,，峰值信噪比比DS算法平均提高了1.3dB，相應(yīng)地均方誤差也降低了,。對于運動緩慢的視頻序列,，新算法的性能幾乎逼近全搜索算法；在實驗4中,，用各種算法對missamerican(360×288)序列進(jìn)行匹配,，比較可得改進(jìn)算法的搜索匹配時間比DS算法平均減少了約1.5ms。
??? 基于視頻壓縮的快速自適應(yīng)菱形搜索算法,，充分利用了視頻圖像序列的時空相關(guān)特性，采用了大小菱形搜索模式,，實現(xiàn)了運動矢量高速而較精確的估計,。仿真結(jié)果表明，與全搜索算法,、三步搜索算法,、菱形搜索算法等一些優(yōu)秀算法相比，新算法的運動估計準(zhǔn)確性高,、預(yù)測質(zhì)量好,。在可視電話、終端會議等的實時視頻通信中,，該算法可取得較好的效果,。
參考文獻(xiàn)
[1] 朱秀昌，劉峰,，胡棟.數(shù)字圖像處理與圖像通信[M].北京：北京郵電大學(xué)出版社,，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.