基于三維遞歸搜索的多級運動估計視頻幀率上轉換算法

賈 茜 肖進勝 易本順 甘良才

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖2 3-D RS時空預測候選矢量

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

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

2.2 多級運動矢量處理

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

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

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

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

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

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

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

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

圖4 Bowing序列第64幀內插結果

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

3 實驗結果與分析

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

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

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

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

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

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

圖5 Carphone序列第72幀內插幀主觀質量對比

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

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

4 結論

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

[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]李莉, 侯正信. 一種自適應幀頻提升算法研究[J]. 計算機應用研究, 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]. 計算機工程與應用, 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]李淼, 李迅波, 魏海龍. 基于運動矢量場預測的自適應多模板塊運動估計算法[J]. 電子測量技術, 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]張少嫻, 俞瓊. 基于時空相關性預測的運動估計的優化[J]. 計算機技術與發展, 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.