賈 茜 肖進勝 易本順 甘良才

(武漢大學(xué)電子信息學(xué)院 武漢 430072)

1 引言

盡管目前視頻傳輸中的編解碼技術(shù)已經(jīng)可以獲得很高的壓縮比，然而為了適應(yīng)一些網(wǎng)絡(luò)帶寬的限制，通常將視頻信號的時空分辨率降低使數(shù)據(jù)量更少，在時域中可以通過編碼端跳幀來實現(xiàn)。這樣，在解碼端的低幀率視頻必然會引起運動不連續(xù)、圖像質(zhì)量的退化，尤其是在快速運動和復(fù)雜場景中更為明顯。為此，可以在解碼端采用視頻插幀，即幀率上轉(zhuǎn)換技術(shù)來恢復(fù)原始幀率以提高視頻圖像的主觀視覺效果，該技術(shù)也可用于不同幀率視頻格式之間的轉(zhuǎn)換。由于簡單的幀重復(fù)、幀平均會產(chǎn)生運動抖動和模糊，因此在實際中幀率上轉(zhuǎn)換通常采用的方法是基于塊匹配的運動補償內(nèi)插(Motion-Compensated Interpolation, MCI)，該方法所獲得的內(nèi)插幀質(zhì)量取決于運動矢量估計的精度。已存在的 MCI算法按照運動矢量的來源不同可以分為兩類：第1類方法基于壓縮域，直接對解碼端得到的碼流中的運動矢量和殘差信號進行分析和處理[1,2]。由于省去了重新運動估計的步驟，計算量顯著降低，然而該類算法對壓縮標(biāo)準(zhǔn)有依賴。第2類方法基于像素域，對解碼后的圖像序列相鄰幀重新進行運動矢量估計，得到面向插幀應(yīng)用的運動矢量[3-11]，再進行分析和處理。本文主要討論第2類算法。

在MCI中需要解決以下3個問題：(1)估計的運動矢量必須正確地反映真實的運動才能準(zhǔn)確地重構(gòu)插值幀。大多數(shù)的MCI算法利用塊匹配算法做運動估計，基于塊匹配的各種模板搜索快速算法大幅度地減小了計算量。然而，與視頻壓縮不同的是，MCI中的運動估計不是為了最小化殘差信號的能量，而是為了找到代表真實運動的矢量場，使重構(gòu)的內(nèi)插幀獲得符合主觀視覺的圖像信息。目前，已存在眾多運動估計的快速搜索算法，利用運動矢量場的相關(guān)性預(yù)測當(dāng)前塊的運動，自適應(yīng)地選擇不同搜索模板和搜索策略，可以在一定程度上進一步提高搜索速度和精確度，典型算法如：預(yù)測運動矢量自適應(yīng)搜索技術(shù)[3](Predictive Motion Vector Field Adaptive Search Technique, PMVFAST)。由于傳統(tǒng)的塊匹配搜索算法得到的運動矢量最優(yōu)解常與真實的運動不符，為了提高運動矢量場的時空一致性，獲得代表真實運動的運動矢量，文獻[4]提出了3維遞歸搜索(3-D Recursive Search, 3-D RS)算法，該算法追求的是平滑的運動矢量場，而且其收斂快速，復(fù)雜度低，所以在面向幀率上轉(zhuǎn)換應(yīng)用的運動估計中受到重視。(2)傳統(tǒng)的塊匹配算法是前后兩幀“單向”搜索，使得中間內(nèi)插幀的一個像素可能有多個運動軌跡通過，或者沒有運動軌跡通過，而分別產(chǎn)生“重疊”和“空洞”問題。而雙向運動估計[5,6]是以內(nèi)插幀中的塊作為定位基準(zhǔn)，在前后幀中對稱地搜索匹配塊，這樣在插值補償中間幀時就不會存在單向運動估計方法所帶來的像素“重疊”和“空洞”。(3)塊匹配方法是基于塊內(nèi)所有的像素點具有一致運動狀態(tài)的假設(shè)，當(dāng)一個塊包含多個不同運動時，會使內(nèi)插幀出現(xiàn)“塊效應(yīng)”。國內(nèi)外研究者提出了許多方法來提高運動估計精度，或者改進運動補償策略，以減小塊效應(yīng)，例如：文獻[2]將中值濾波作為矢量后處理步驟，在運動補償時采用類似于 H.264和 MPEG4中所用到的重疊塊運動補償技術(shù)(Overlapped Block Motion Compensation, OBMC)來減小塊效應(yīng)；由于傳統(tǒng)的中值濾波算法計算量較大，文獻[3]提出了一種簡化的中值濾波方法；文獻[6]通過K-均值聚類對運動對象進行分割，再采用可變尺寸塊運動補償(Variable-Size Block Motion Compensation, VS-BMC)和自適應(yīng)的OBMC以克服傳統(tǒng)OBMC帶來的圖像過平滑，獲得了較好的內(nèi)插效果，但是該算法在運動估計和對象分割時需要反復(fù)迭代，計算較為復(fù)雜。

本文力求用低復(fù)雜度的算法獲得好的內(nèi)插圖像質(zhì)量，提出了一種基于 3-D RS的多級運動估計幀率上轉(zhuǎn)換算法。該算法將3-D RS與雙向運動估計算法相結(jié)合，在相鄰的前后兩幀中計算初始運動矢量；然后按照塊的尺寸對初始運動矢量“由粗到細(xì)”逐級精確修正，并利用簡化的中值濾波器對矢量場進一步平滑；再通過時域線性插值補償產(chǎn)生中間幀。該算法在不產(chǎn)生“重疊”與“空洞”的同時，提高了雙向運動估計準(zhǔn)確性和運動矢量一致性，有效減小了塊效應(yīng)，并且復(fù)雜度低、易于實現(xiàn)，可應(yīng)用于高清視頻的實時處理。

2 基于3-D RS的多級運動估計幀率上轉(zhuǎn)換算法

在視頻編解碼領(lǐng)域已有很多成熟的塊匹配算法。但是，如前所述，在視頻插幀應(yīng)用中要求運動信息能夠反映物體的真實運動，僅靠匹配誤差確定的運動矢量有可能與真實的運動截然不同，使運動補償?shù)膬?nèi)插幀產(chǎn)生與主觀視覺不符的圖像信息。由于視頻對象的運動具有連續(xù)性，因此運動矢量間也存在時空相關(guān)性。由此，出現(xiàn)了遞歸搜索的方法，它是利用運動場時空相關(guān)性預(yù)測的搜索算法，不僅能獲得更為平滑的運動矢量場，同時也減少了計算開銷。

2.1 雙向3維遞歸搜索的運動估計

3維遞歸搜索包括空間遞歸和時間遞歸，即認(rèn)為當(dāng)前塊與當(dāng)前幀中的空間相鄰塊以及前一幀中時間相鄰塊在運動上具有相關(guān)性，當(dāng)前塊的運動矢量可由時空相關(guān)矢量“傳播”得來。應(yīng)當(dāng)注意的是，當(dāng)前塊的運動矢量與其時間、空間相鄰塊運動矢量相近，但并非完全相同，如果所有的候選矢量都來自相鄰塊運動矢量的原始值，則不符合實際情況。因此，給原始運動矢量加上一個更新矢量，得到的候選運動矢量將更接近實際、更準(zhǔn)確。傳統(tǒng)的 3-D RS算法中運動估計誤差準(zhǔn)則[4]由式(1)計算：

其中F(x,t)是t幀中像素點x的亮度，T是幀數(shù)間隔，B(X)代表參考幀中的塊，X為塊的位置，C為候選矢量，U(X,t)為更新矢量，α為常數(shù)。式(1)即首先計算相鄰兩幀中塊內(nèi)像素的絕對差和(Sum of Absolute Differences, SAD)，再加上一個依賴更新矢量大小的懲罰值，誤差最小的運動矢量即為估計值。

在搜索匹配塊時，如果按照單向運動估計獲得的運動矢量線性補償插值可能會有像素“重疊”和“空洞”問題，如圖 1(a)所示。而雙向運動估計是以內(nèi)插幀中待插塊的坐標(biāo)為基準(zhǔn)，在相鄰的前后兩幀中對稱地搜索匹配塊，如圖1(b)所示，從而巧妙地解決了該問題。

由于原始的3-D RS利用SAD作為匹配準(zhǔn)則，這與其他單向運動估計的經(jīng)典搜索算法一致，為了同時利用 3-D RS和雙向運動估計各自的優(yōu)點，將它們進行結(jié)合時需要對匹配準(zhǔn)則進行修改，故本文用雙向運動估計中的匹配準(zhǔn)則“雙向絕對差和”SBAD(Sum of Bilateral Absolute Differences)來代替原來的SAD。

圖1 單向運動估計與雙向運動估計示意圖

其中Bi,j代表內(nèi)插幀中的塊，s為內(nèi)插幀中的像素點，v為運動矢量，fn-1和fn+1是與內(nèi)插幀相鄰的前后兩幀。為了減小搜索時的計算量，可以減少候選矢量的個數(shù)[7]，在本文運動估計算法中，對于第n幀中位置為X=[X,Y]T的塊，其時空相關(guān)預(yù)測中候選運動矢量d(·,·)的集合CS表示如下：

其中Vx,Vy是水平和垂直方向的單位向量；d(·,n)表示空間相關(guān)預(yù)測矢量；d( ·,n-1)表示時間相關(guān)預(yù)測矢量；k交替地取-1和1;US為更新矢量，從以下集合中依次選?。?/p>

由于實際中水平方向上的大運動比垂直方向的大運動發(fā)生概率更高，所以更新矢量中水平分量變化要比垂直分量大[5]。這樣，候選的預(yù)測矢量共有6個，如圖 2所示，包括：內(nèi)插幀中Bi,j的左邊、上邊塊和左上塊(或右上塊)；前一個內(nèi)插幀中的Bi,j塊，以及其右邊和下邊塊。

圖2 3-D RS時空預(yù)測候選矢量

式(1)中加上的懲罰值主要是用以區(qū)分不同類型候選矢量的優(yōu)先權(quán)。為簡化計算，本文在算法中對空間預(yù)測、時間預(yù)測、更新矢量預(yù)測的匹配誤差加上的懲罰值分別由小到大設(shè)置為 3個不同的常數(shù)，也可以區(qū)分不同類型候選矢量的優(yōu)先權(quán)，即：若在搜索的過程中出現(xiàn)了相等SBAD的候選矢量，則優(yōu)先次序為空間預(yù)測、時間預(yù)測、更新矢量預(yù)測。這樣，運動矢量最優(yōu)估計值為

其中Penalty對于空間預(yù)測、時間預(yù)測、更新矢量預(yù)測分別取常數(shù)0,2,4。為了提高好的運動估計結(jié)果的傳播，改變掃描順序可能會有所幫助。有兩種可行的機制：第1種是在“先左后下”掃描一遍之后，再反向掃描一遍；第 2種是“曲徑”(meandering)掃描，即“從左至右”的掃描完一行之后，下一行“從右至左”的掃描；也可以同時采用這兩種機制[8]。本文算法中用的是第1種方法，即第1次“先左后下”掃描，第2次再“先右后上”的反向掃描，如果搜索到更好的匹配則更新矢量估計值。需要指出的是，式(3)列舉的只是“先左后下”的掃描順序所代表的預(yù)測矢量，第2遍“先右后上”的掃描時，由于循序掃描并不是所有的空間預(yù)測矢量都能立即獲得，空間預(yù)測矢量要選取那些已估計的塊，可以通過將空間預(yù)測與時間預(yù)測塊位置互換來獲得。

2.2 多級運動矢量處理

當(dāng)一個塊包含多個不同運動對象時，無法得到正確描述運動的估計矢量。這時可以采用多級塊匹配和多分辨率塊匹配[8]，它們都是基于“由粗到細(xì)”的搜索思想，上一層的運動矢量可以傳播到下一層，而下一層的估計值是對上一層估計結(jié)果的進一步細(xì)化。如圖 3(a)所示，多級法在每一級上圖像大小相同，而塊的尺寸不同。當(dāng)某些塊不能得到好的匹配時將其塊拆分成小塊進行搜索，每一級可以使用不同的塊匹配搜索算法，如3-D RS、鉆石搜索(DS)、六邊形搜索(HS)等。而多分辨率法如圖3(b)所示，是在多尺度圖像上進行搜索，塊的大小保持不變，但每個層次上的圖像分辨率不同。低分辨率層可以對高分辨率層下采樣得到，或者構(gòu)建圖像金字塔。

圖3 多級塊匹配與多分辨率塊匹配

(1)多級塊匹配運動估計 本文運動估計算法采用多級法，以16×16塊作為初始搜索，通過三級運動估計逐步得到4×4塊的運動矢量。設(shè)塊匹配預(yù)測誤差門限閾值為threshold_SAD，處理步驟如下：

(a)首先用 16×16塊匹配搜索，對大于threshold_SAD塊進行標(biāo)記；

(b)將16×16塊拆分為8×8塊繼承上一級運動估計的結(jié)果，對上一步中標(biāo)記的塊重新搜索，更新估計值；對大于threshold_SAD/4的塊再次標(biāo)記；

(c)將8×8塊拆分4×4塊繼承上一級運動估計的結(jié)果；對上一步中標(biāo)記的塊再次重新搜索，更新估計值；對大于threshold_SAD/16的塊運動矢量由其周圍的塊運動矢量中值濾波的結(jié)果直接分配。

在本文設(shè)計的三級運動估計中，前兩級是用上一節(jié)介紹的基于3-D RS的雙向運動估計算法，第3級是HS算法。

由于傳統(tǒng)的矢量中值濾波計算量較大，本文采用一種簡化的中值濾波器[3]對運動估計得到的矢量進行處理。該算法是通過對鄰域內(nèi)初始的運動矢量的水平、垂直分量分別進行排序，并按大小賦予權(quán)值，找出總權(quán)值最小的一對矢量作為窗口內(nèi)矢量的中值。該算法實際上是簡化了矢量中值的甄選過程。在實驗中，我們發(fā)現(xiàn)執(zhí)行該算法過程中當(dāng)總權(quán)值最小的矢量對不唯一時，可能甄選出的中值矢量并不是最佳的，最終使最后插值幀出現(xiàn)了“塊效應(yīng)”，如圖 4(a)所示。因此，本文算法中在甄選中值矢量時對水平、垂直賦予 2組不同大小的權(quán)值：{4,3,2,1,0,1,2,3,4}和{20,15,10,5,0,5,10,15,20}，保證選出的最佳矢量對的唯一性。賦值的依據(jù)是先判斷運動矢量水平分量和垂直分量的大小，較大者賦予第2組權(quán)值。甄選出的中值矢量'mv是否要替換原始窗口中心的mv，是通過兩者之間的差異以及窗口的尺寸來決定的：

圖4 Bowing序列第64幀內(nèi)插結(jié)果

本文在三級運動估計的每一級完成之后進行上述的運動矢量中值濾波處理，“由粗到精”地逐步修正運動矢量，最終得到4×4的塊運動矢量。最后利用式(7)的線性插值運動補償重構(gòu)中間幀。

3 實驗結(jié)果與分析

實驗數(shù)據(jù)選取了8個4:2:0的YUV格式的標(biāo)準(zhǔn)測試序列來驗證本文算法的有效性，包括7個CIF序列：Football, Bowing, Susan, Carphone, News,Silent和Forman，以及1個HD序列Sunflower。其中，F(xiàn)ootball有大量快速運動，Bowing 和Silent背景靜止，前景人物有復(fù)雜運動；Susan前景有大面積運動；Carphone與Forman類似，前景運動比較復(fù)雜，背景有微小晃動，而 Forman序列后半部分還存在背景的全局運動；News圖像中間部分有復(fù)雜運動；Sunflower存在局部和全局同時運動。

實驗中對每個序列時域下采樣，跳過偶數(shù)幀后，采用本文提出的幀率上轉(zhuǎn)換算法對相鄰幀進行內(nèi)插，重構(gòu)出跳過的幀，恢復(fù)原始幀率。插幀客觀質(zhì)量通過內(nèi)插幀與原始幀的PSNR值來衡量。為了評價本文算法的性能，對比了其他3種算法：方法 1是全搜索(Full Search, FS)雙向運動估計結(jié)合傳統(tǒng)的中值濾波方法；方法2是PMVFAST自適應(yīng)雙向運動估計算法[3]；方法3是拋物線運動模型自適應(yīng)運動矢量選擇算法[12]。在方法1中，雙向運動估計的塊大小為16×16，全搜索半徑設(shè)置為8，對應(yīng)到單向運動估計的搜索范圍為±16。以上算法對不同測試序列的內(nèi)插幀平均PSNR值如表1所示。

表1 各算法對測試序列內(nèi)插幀平均PSNR(dB)

由表1可見，本文提出的算法對于大部分序列內(nèi)插幀PSNR值，超過或者接近參考算法中的最優(yōu)者。對于Carphone和Forman序列，本文算法PSNR值略低于全搜索而高于其他算法；對于 News序列方法3的PSNR值最高，本文算法次之；對于HD序列Sunflower, PMVFAST算法略優(yōu)于本文算法與全搜索。

圖5是內(nèi)插幀主觀質(zhì)量的對比。由圖5可以看出，本文算法得到的Carphone序列第72個內(nèi)插幀，人的嘴巴、鼻子、頭發(fā)部分更為清晰。

在計算復(fù)雜度方面，由于本文采取 3-D RS為核心的搜索算法，根據(jù)式(3)和式(4)，對于一個塊的運動估計正向、反向兩次掃描需搜索28個位置。據(jù)實驗統(tǒng)計，第1級16×16塊對于圖像大部分區(qū)域已經(jīng)能夠取得比較好的匹配結(jié)果，拆分小塊進行后面兩級搜索只是少數(shù)塊，所以即使算法中進行了三級運動估計，其計算開銷也并無大幅增加。方法2的PMVFAST算法是以當(dāng)前塊空間相關(guān)的3個塊的矢量作為預(yù)測矢量，根據(jù)預(yù)置的SAD閾值和計算出的矢量距離選擇合適的模板再進行搜索。PMVFAST在搜索中為了減小計算量加入了提前終止策略，預(yù)先不能確定計算量。方法3的拋物線運動模型和自適應(yīng)運動矢量選擇使在已知初始運動矢量，利用拋物線對運動軌跡建模，修正時間不連續(xù)的運動矢量，得到正確的“雙向運動矢量對”。由于該方法討論的是已知初始的運動矢量之后的進一步處理，并未討論初始運動矢量如何得到，所以在本文算法處理速度對比實驗中方法3沒有參與比較。

圖5 Carphone序列第72幀內(nèi)插幀主觀質(zhì)量對比

為了評估本文算法的效率，在 Intel Core i5-2500K (CPU@3.30 GHz), 3 GB內(nèi)存的PC平臺上分別運行方法 1、方法 2和本文算法，對于不同測試序列的平均處理時間如表2所示。在處理HD序列時，為了減小計算量，在實驗中先對HD序列每一幀進行空間圖像下采樣。由表2可見，相對于CIF序列，HD序列由于其數(shù)據(jù)量更大，本文算法在處理速度方面的優(yōu)勢更加明顯，計算時間明顯少于其他兩種算法，對于HD序列有足夠的處理能力。

表2 各算法對測試序列插幀的平均處理時間(ms)

4 結(jié)論

本文提出了一種基于3-D RS多級運動估計的幀率上轉(zhuǎn)換算法，采用了多級時空相關(guān)預(yù)測的雙向運動估計和運動矢量校正。由于3-D RS搜索點少，且矢量校正部分采用了簡化的中值濾波器，所以該方法計算量小，易于實現(xiàn)。文中先介紹了該方法原理和處理流程，然后通過實驗對比了其他3種方法來評價本文算法的性能，驗證了算法的有效性。實驗結(jié)果表明，本文算法獲得的內(nèi)插幀客觀指標(biāo)和主觀效果均令人滿意，在保證內(nèi)插幀質(zhì)量的同時，算法復(fù)雜度低，大幅度提高了處理速度，對于高清序列插幀速度可以達(dá)到15 fps以上，適用于高清甚至更高分辨率的視頻幀率上轉(zhuǎn)換的實時處理。

[1]Huang A M and Nguyen T Q. A multistage motion vector processing method for motion-compensated frame interpolation[J].IEEE Transactions on Image Processing,2008, 17(5): 694-707.

[2]Zhai J, Yu K, Li J,et al.. A low complexity motion compensated frame interpolation method[C]. International Symposium on Circuits and Systems, Kobe, Japan, 2005, (5):4927-4930.

[3]李莉, 侯正信. 一種自適應(yīng)幀頻提升算法研究[J]. 計算機應(yīng)用研究, 2009, 26(4): 1575-1577.

Li Li and Hou Zheng-xin. Research on adaptive algorithm for frame rate up conversion[J].Application Research of Computers, 2009, 26(4): 1575-1577.

[4]Haan G D, Biezen P W, Huijgen H,et al.. True-motion estimation with 3-D recursive search block matching [J].IEEE Transactions on Circuits and Systems for Video Technology, 1993, 3(5): 368-379.

[5]Choi B T, Lee S H, and Ko S J. New frame rate up-conversion using bi-directional motion estimation[J].IEEE Transactions on Consumer Electronics, 2000, 46(3): 603-609.

[6]Chio B D, Han J W,et al.. Motion-compensated frame interpolation using bilateral motion estimation and adaptive overlapped block motion compensation[J].IEEE Transactions on Circuits and Systems for Video Technology,2007, 17(4): 407-415.

[7]侯正信, 李娜, 張麗曉, 等. 幀率提升中的三維遞歸搜索塊匹配改進算法[J]. 計算機工程與應(yīng)用, 2011, 17(33): 169-171.

Hou Zheng-xin, Li Na, Zhang Li-xiao,et al.. Improved 3-D recursive search block matching algorithm in frame rate up conversion[J].Computer Engineering and Applications, 2011,17(33): 169-171.

[8]Heinrich A, Bartel C,et al.. Optimization of hierarchical 3DRS motion estimators for picture rate conversion[J].IEEE Journal of Selected Topics in Signal Processing, 2011, 5(2):263-264.

[9]Wang D, Zhang L, and Vincent A. Motion-compensated frame rate up-conversion part I: fast multi-frame motion estimation[J].IEEE Transactions on Broadcasting, 2010,56(2): 133-141.

[10]李淼, 李迅波, 魏海龍. 基于運動矢量場預(yù)測的自適應(yīng)多模板塊運動估計算法[J]. 電子測量技術(shù), 2010, 33(10): 36-39.

Li Miao, Li Xun-bo, and Wei Hai-long. Multi-pattern block motion estimation search algorithm based on predictive motion vector field[J].Electronic Measurement Technology,2010, 33(10): 36-39.

[11]張少嫻, 俞瓊. 基于時空相關(guān)性預(yù)測的運動估計的優(yōu)化[J]. 計算機技術(shù)與發(fā)展, 2010, 20(1): 104-107.

Zhang Shao-xian and Yu Qiong. An optimization method for spatiotemporal predictive motion estimation[J].Computer Technology and Development, 2010, 20(1): 104-107.

[12]Choi K S and Hwang M C. Motion-compensated frame interpolation using a parabolic motion model and adaptive motion vector selection[J].ETRI Journal, 2011, 33(2):295-298.