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