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