一種自適應幀頻提升算法研究
2009-01-01 00:00:00李莉侯正信
計算機應用研究 2009年4期
（天津大學 電子信息工程學院， 天津 300072）
摘 要：為減小幀頻提升算法中內插幀的誤差，提高提升后視頻序列的整體觀看質量，提出了一種新的自適應幀頻提升算法，將基于經驗閾值的自適應可變尺寸塊與雙向運動估計相結合，并對估計得到的運動矢量場進行逐級平滑以減小誤差累積，解決了幀頻提升中存在的重疊、空洞等問題，減少了塊效應，比其他自適應算法簡單且易于實現。對標準測試序列的實驗結果表明，算法較其他方法不僅降低了計算量，而且內插圖像的主觀和客觀質量均有所提高。
關鍵詞：幀速率上轉換; 自適應; 雙向運動估計; 可變尺寸塊
中圖分類號：TP391文獻標志碼：A
文章編號：1001-3695(2009)04-1575-03
Research on adaptive algorithm for frame rate up conversion
LI Li， HOU Zheng-xin
( School of Electronic Information Engineering， Tianjin University， Tianjin 300072， China)
Abstract:In order to decrease the error in interpolated frames for frame rate up conversion and improve the overall visual quality of the video sequences after the frame rate up conversion， this paper presented a novel adaptive frame rate up conversion algorithm .Incorporated the variable-size block motion compensation based on pre-knowledge thresholding into bilateral motion estimation， and adopted the adapted multi-stage motion vector processing so as to avoid the cumulation of motion estimation error. As a result， the problems of overlapping and hole are resolved and block artifacts are decreased. Compared with other adaptive method， the proposed algorithm is simple and easy to be implemented. Experimental results show that the proposed algorithm provides a better image quality than other methods both objectively and subjectively， and improves the computation efficiency.
Key words：fame rate up conversion(FRUC); adaptive; bilateral motion estimation; variable-size block
幀頻提升(FRUC)主要用來實現不同幀速率視頻掃描格式之間的轉換。如在液晶顯示器中，通過將幀頻提升至100/120 fps，以減小液晶顯示屏的保持時間，從而消除液晶電視在顯示動態畫面時容易出現的拖尾現象，確保更加流暢的動態效果。此外，為了將以24 fps拍攝得到的電影膠片在50/60 fps高清晰度電視上播放需進行分數倍的幀頻提升。
本文算法屬于運動補償內插（motion compensated interpolation， MCI）方法，且主要討論幀頻的兩倍提升。在MCI中，需要根據已知幀建立運動模型，估計內插幀相對參考幀的運動，從而重構內插幀。對這類方法來說，運動估計準確度至關重要。在一些應用中，如將視頻序列傳送到手持設備（如手機）上觀看，因無法重新進行運動估計而直接利用解碼得到的運動矢量重構內插幀，觀看效果通常非常差，因此這類應用側重于對運動矢量的校正處理[1]，該類問題比本文討論的離線FRUC更有難度。本文提出的算法將基于經驗閾值的自適應可變尺寸塊與雙向運動估計相結合，并采用改進的逐級矢量場平滑和自適應插幀算法，解決了重疊、空洞問題，減小了塊效應且保證了較高的運算速度。
1 相關工作
1.1 傳統FRUC模型
幀頻提升中內插幀的每一像素值只能通過其前后兩幀的信息獲得。如圖1所示，fn-1 、fn和fn+1分別表示前一幀、內插幀和后一幀，而s是一個表示像素空間位置的二維向量，則fn幀的s像素內插值為
f^n[s]=a×fn-1[s-v]+b×fn+1[s+v](1)
其中：v是估計到的內插像素s的運動矢量；fn[s]表示第n幀s像素的原始灰度值。不同FRUC算法對應不同a、b取值及運動矢量的估計方法。
如果令v=0，則是沒有運動估計的簡單線性內插法。 其中：a=0.5，b=0.5為幀平均法；a=1，b=0則為幀重復法。幀重復法容易產生運動突變現象，而幀平均法則會使運動物體邊緣模糊。傳統MCI-FRUC令v為fn+1相對fn-1運動矢量的一半，a=0.5，b=0.5，但這類算法[2]只適合勻速運動。
最優時域濾波器幀內插法[3]則將t=(a，b)作為時域內插濾波器，通過運動矢量誤差統計模型獲得其最佳估計值。
1.2 MCI-FRUC中的運動估計問題及改進
值得注意的是FRUC中的運動估計與視頻編碼中的運動估計大為不同。前者是為了內插出質量好的中間幀圖像，后者是為了得到最小的殘差圖像；前者一般在解碼后進行，是通過前后兩幀圖像估計出未知的中間幀圖像相對于它們的運動，后者在編碼端進行，估計的是已知的預測幀與參考幀之間的運動。因此，FRUC中的運動估計比視頻編碼中的運動估計更有難度。如將傳統的基于塊匹配算法（block matching algorithm， BMA）的運動估計算法直接用于FRUC，內插幀的一個像素可能對應多個運動矢量，也可能沒有運動矢量與之對應，分別產生重疊問題或者空洞問題；當一個塊中包含多個不同運動對象時，對象邊界與塊邊界不一致，相鄰塊可能會有差別很大的運動矢量，塊效應也將影響內插幀的質量。而且，傳統的塊運動估計只適合普通平移運動，不適合旋轉、縮放、變形等復雜運動。
為提高MCI-FRUC質量，Lee等人提出了加權自適應運動補償內插(weighted-adaptive motion compensated interpolation， WAMCI)[4]，在運動補償時將運動分為四類分別進行插值，但其計算量比較大，特別是運動復雜的視頻序列會頻繁調用WAMCI，計算量急劇增大，同時造成圖像的模糊。
Orchard等人提出了一種重疊的塊運動補償內插(overlapped block motion compensation， OBMC)[5]，有效地減少了運動矢量不連續造成的塊邊緣失真，取得了較好的視覺效果。但是，OBMC算法本身也存在著一些問題：a)對存在錯誤的運動估計塊使用OBMC才能提高視頻質量。而對原本估計正確的運動矢量使用OBMC，則會造成圖像的模糊，反而影響了視頻質量。因此，需要一些自適應算法或者運動分析算法配合OBMC完成對運動矢量的甄別，這樣就增加了算法的復雜度，從而增加了處理時間。b)OBMC算法的思想是充分利用空間相關性來消除局部錯誤運動估計矢量的影響，但實際情況常常是，錯誤的運動估計塊周圍塊的運動估計也是不可靠的，OBMC可能造成誤差累計，影響整體效果。
Choi等人提出了專門用于FRUC的雙向運動估計(bilate-ral motion compensated interpolation， BMCI)[6，7]，其直接由前后兩幀預測中間內插幀的運動矢量，成功地解決了FRUC中運動估計存在的重疊和空洞問題。
在雙向運動估計中，對于內插幀的一個塊，通過比較其前一幀中一定位移處的塊與其后一幀相反位移處的塊，找到使兩者最相似的位移作為該塊的運動矢量。如圖1所示，Bi，j表示內插幀的一個塊，可以假設其運動矢量在[-a，a]內。對此范圍內的每一個候選運動矢量v，計算該塊在前幀中移動-v后和在后幀移動+v后對應塊每個像素的雙向絕對差和（sum of bilateral absolute difference， SBAD）：
SBAD[Bi，j，v]=∑s∈Bi，j｜fn-1[s-v]-fn+1[s+v]｜(2)
在[-a，a]內搜索到SBAD最小的v即為該塊的運動矢量估計值。
2 本文算法
2.1 總體結構
基于對前人工作的分析，設計了總體結構如圖2所示的本文算法。其中，雙向運動估計分三種塊尺寸逐級進行，每一級均有矢量校正處理。為簡化可變尺寸塊雙向運動估計的實現，采用了經驗閾值，最后通過一種簡化的自適應運動補償插幀獲得內插幀。
2.2 可變尺寸塊雙向運動估計
在BMA中，當一個塊中包含多個不同運動對象時，對象邊界與塊邊界不一致，無法得到正確的運動估計矢量。同時，運動估計塊尺寸的選取也存在著矛盾，尺寸選取過大會出現不匹配的情況，尺寸選取過小會出現誤匹配的情況。實驗證明，前者會導致塊效應，而后者會造成視頻畫面的視覺抖動感。因此，需要根據內插幀內各區域的運動復雜程度選擇不同的塊尺寸。
由于內插幀信息未知，無法合適地選取運動估計塊的大小。若采取自適應方法由已知幀信息獲得內插幀雙向運動估計塊尺寸，將使算法復雜度大幅增加。為此，本文提出了一種不用增加運算代價的簡化方法，即通過對大量序列測試統計，確定經驗閾值，進行塊尺寸的選擇。對于大多數中等細節的視頻序列，確定閾值SAD16為8 000、閾值SAD8為2 000，閾值SAD4為500。
三級自適應可變尺寸塊運動估計具體步驟如下：
a)以16×16的運動估計塊對fn-1和fn+1進行雙向運動估計。
b)運動估計時，對SBAD大于SBAD16的16×16運動估計塊拆分為8×8運動估計塊進行運動估計；對SBAD大于SBAD8的8×8運動估計塊拆分為4×4運動估計塊進行運動估計。
c)對SBAD依然大于SBAD4的4×4運動估計塊，可以認為運動估計失敗，取其左邊、上邊和右上三個運動估計塊的運動矢量的中值作為其運動矢量。
2.3 可預測運動矢量場自適應搜索技術
在進行雙向搜索時采用了可預測運動矢量場自適應搜索技術(predictive motion vector field adaptive search technique，PMVFAST)[8，9]。PMVFAST充分利用了視頻序列的時空相關性，與其他運動搜索技術相比，具有明顯提高的運算速度。視頻壓縮編碼實驗表明，對各種視頻測試序列，在搜索窗口為32時、碼率相同的條件下，標準PMVFAST算法速度比三步搜索法、新三步搜索法和菱形搜索法分別快約4.5倍、4.8倍和4倍，而PSNR比它們分別提高約0.87、0.81和0.73[10]。雖然其針對視頻壓縮編碼提出，但也可用于雙向運動估計。
2.4 逐級矢量校正
在傳統BMA中，常因為圖像噪聲、遮擋、運動復雜（如放大、旋轉、變形）、運動邊緣等原因造成運動估計的失敗；或者，由于搜索策略的局限性僅得到運動矢量的局部最優解而非全局最優解，從而使運動矢量沒有指向正確的位置。由此進行運動補償插值，就會出現塊效應。常用OBMC修正運動估計錯誤，但是該方法復雜度太高，且與本文方案采用的可變尺寸塊運動估計相沖突。因此，選擇較簡單的矢量校正方法消除塊效應。
本方案對傳統的矢量中值濾波器進行簡化，設計了一種適合于可變尺寸塊運動估計的逐級矢量場校正方法。針對本方案的可變尺寸塊運動估計，將矢量濾波安排在每一級運動估計之后，如圖2所示，從而避免了運動估計誤差積累，提高了重構視頻質量。
傳統矢量中值濾波[11]是在滑動窗口中尋找一個距離其他像素矢量最近的矢量，并以此矢量替代原中心矢量。如果有多個矢量都為最小值，則選擇離滑動窗中心最近的矢量。本文設計了簡化的矢量中值濾波器，避免復雜的運算，在不影響處理質量的前提下，節省了處理時間。具體步驟如下：
a)以當前運動估計塊的大小為單位，矢量中值濾波的滑動窗口大小設計為3×3。
b)分別對窗口內的九個運動估計矢量的水平分量和豎直分量進行從大到小的排列，并按大小賦予權值：{4，3，2，1，0，1，2，4，3}。
c)將每一個運動估計矢量的水平分量權值和豎直分量權值相加得到該運動估計矢量的權值，記錄權值最小的運動矢量。
d)將記錄的運動矢量與窗口中心的運動矢量相比較，如果有較大差別，可以認為窗口中心的運動矢量有誤，則以記錄的運動矢量更新窗口中心的運動矢量，以達到校正矢量場的目的。
2.5 自適應運動補償插幀
對于本方案所應用的雙向運動估計算法，在運動補償插幀時存在的問題是：如圖1所示，由fn-1幀運動補償插幀得到的f^1n幀和由fn+1幀反向運動補償插幀得到的f^2n幀在運動估計比較準確的時候是基本相同的，但是當運動估計欠準確時，則兩個預測幀差別較大。針對這一矛盾，本文設計了簡化的自適應運動補償插值方案：
f^n=med[f^1n，f^2n，0.5(f^1n+f^2n)](3)
當運動向量比較精確時， f^1n和f^2n幀中對應的兩個像素具有相近的像素值，中值濾波器可選其中任一個像素值作為輸出；當運動向量不再可靠時，中值濾波器就會選擇輸出f^1n和f^2n幀中對應的兩個像素的平均值作為一種性能上的妥協。
3 實驗
實驗中對原始視頻序列下采樣，使幀速率降為原來的一半，然后再利用本算法將幀速率還原。選用四個標準測試序列news、foreman、tennis和garden進行測試。其中：news攝像機靜止，背景有小部分運動；foreman背景具有微小晃動，前景運動比較復雜；tennis攝像機具有縮放運動，同時前景為局部劇烈運動；garden攝像機全局運動。
為驗證本文算法的有效性，分別與WAMCI [4]、OBMC[5] 及BMCI [7]進行了比較。Foreman和news序列用本文算法及與上述三種算法內插前42幀的PSNR比較分別如圖3、4所示。將這四種算法應用于以上四個標準測試序列，前50幀的平均峰值信噪比如表1所示。
用本文算法和文獻[7]中BMCI算法內插forman序列中一幀圖像的主觀效果比較如圖6所示。可以看出本文算法能夠有效地減少塊效應。
從以上實驗可看出，采用本文算法的內插幀主觀和客觀質量均優于其他典型方法，且考慮到FRUC算法的大部分處理時間都用于運動估計，而本文所使用的PMVFSAT運動估計法相對于其他快速算法具有時間上的明顯優勢，因此可以認為：在處理時間上，本文方法也不遜于其他方法。
4 結束語
本文提出了一種運算效率高、內插效果好的自適應幀頻提升算法。該算法將可變尺寸塊雙向運動估計、自適應插幀等自適應算法進行簡化的同時又采用逐級矢量校正，避免了誤差累計，在運算復雜度和內插效果之間達到較好的平衡，適合硬件實現。該算法還存在一些不足，如雙向運動估計實際將運動估計的精度降低為雙像素，在下一步的工作中可考慮將視頻壓縮編碼中的分數像素運動估計與雙向運動估計相結合，進一步提高雙向運動估計的準確性；此外，本文算法只適用于幀頻的兩倍提升，不適合任意整數倍或者分數倍數提升。在下一步的工作中應考慮在具體的應用中怎樣進一步提高幀頻提升算法的準確性和運算速度。
參考文獻：
［1］
HUANG Ai-mei，NGUYEN T. A novel multi-stage motion vector processing method for motion compensated frame interpolation[C]//Proc of International Conference on Image Processing. 2007:389-392.
［2］HILMAN K， PARK H-W， KIM Y-M. Using motion compensated frame-rate conversion for the correction of 3∶2 pulldown artifacts in video sequences [J]. IEEE Trans on Circuits and Systems for Video Technology，2000，10(6): 896-877.
［3］DANE G， NGUYEN T Q. Optimal temporal interpolation filter for motion-compensated frame rate up conversion[J].IEEE Trans on Image Processing，2006，15(4):978-991.
［4］LEE S-H， KWON O， PARK R-H. Weighted-adaptive motion compensated frame rate up-conversion [J].IEEE Trans on Consumer Electronics，2003， 49(3): 485-495.
［5］ORCHARD M T，SULLIVAN G J.Overlapped block motion compensation: an estimation-theoretic approach [J].IEEE Trans on Image Processing，1994， 3(5): 693-699.
［6］CHOI B D， HAN J W， KIM C S， et al. Motion-compensated frame interpolation using bilateral motion estimation and adaptive overlapped block motion compensation[J].IEEE Trans on Circuit， and Systems for Video Technology，2007， 17(4):407-416.
［7］CHOI B-T， LEE S-H， KO S-J. New frame rate up-conversion using bi-directional motion estimation [J].IEEE Trans on Consumer Electronics，2000， 46(3):603-609.
［8］ALEXIS M， OSCAR C， LIOU M. Predictive motion vector field adaptive search technique (PMVFAST):enhancing block based motion estimation [C]//Proc of International Society for Optical Engineering.San Jose，CA:[s.n]， 2001:378-384.
［9]黎鐵軍，沈承東，李思昆. 一種支持PMVFAST運動估計算法的VLSI體系結構[J]. 計算機研究與發展， 2005，42(4): 536-543.
[10]ISO/IEC/JTC1/SC29/WG11MPEG2000/M5866，Fast block-matching motion estimation using predictive motion vector field adaptive search technique(PMVFAST)[S].2000.
［11］金良海，李德華.一種基于空間距離加權的自適應矢量中值濾波器[J].中國圖象圖形學報，2007， 12(6):970-976.
