基于多特征匹配的雙向運動估計幀率提升算法

薛春玲，李 然，朱秀昌

(1.黃河科技學院，河南 鄭州 450063；2.南京郵電大學 江蘇省圖像處理與圖像通信重點實驗室，江蘇 南京 210003)

基于多特征匹配的雙向運動估計幀率提升算法

薛春玲1，李 然2，朱秀昌2

(1.黃河科技學院，河南 鄭州 450063；2.南京郵電大學 江蘇省圖像處理與圖像通信重點實驗室，江蘇 南京 210003)

視頻幀紋理區域含有的大量周期重復模式常導致雙向運動估計發生視頻塊的錯匹配，從而導致幀率提升算法重建的內插視頻質量衰退。為了克服該問題，提出提取視頻幀的多個特征加入到塊匹配中，以降低錯匹配發生的可能性。由于視頻天然具有彩色信息，因此色差分量首先被加入到塊匹配中。另外，人眼對圖像邊緣較敏感，因此，由簡單的Sobel算子計算出的梯度被使用去反應邊緣特征并融入至塊匹配。多特征匹配盡管可有效地提高運動估計精度，但也引入了較高的計算復雜度。為了減少計算復雜度，一個特殊模板被設計去將多特征合并到單平面上，那么，只需進行一次塊匹配運算就可完成多特征的匹配，在節省計算復雜度的同時也提高了運動估計精度。仿真實驗表明，該算法以較低的計算復雜度獲得了良好的內插幀主客觀質量。

圖像處理；幀率提升算法；雙向運動估計；多特征匹配

幀率提升(Frame Rate Up-conversion，FRUC)具有廣泛的應用前景，例如，低比特率視頻通信和液晶顯示(LCD)運動去模糊等[1]。簡單的幀率提升算法通過幀復制和幀平均實現，由于其忽略了幀間的運動信息，經常會導致物體的運動模糊和畫面抖動。考慮幀間運動的運動補償幀率提升(Motion-Compensated Frame Rate Up-conversion，MC-FRUC)可有效地提高內插幀質量，因此獲得了廣泛關注。

運動補償幀率提升由運動估計(Motion Estimation，ME)和運動補償內插(Motion Compensated Interpolation，MCI)兩部分組成。運動估計首先計算出幀間的運動矢量場，接著運動補償內插根據運動矢量場利用前后參考幀估計出內插幀[2]。由于經常出現有多個或無運動軌跡通過內插幀中的某些塊，因此導致空洞和重疊現象，使內插幀質量衰退。為了解決上述問題，雙向運動估計(Bidirectional Motion Estimation，BME)被提出利用運動對稱性假設為內插幀各塊分配唯一運動矢量，而解決了空洞和重疊問題[3]。但是由于視頻幀的紋理區域常含有大量的周期重復模式，而雙向運動估計中內插幀的缺失會造成在該區域內塊的錯匹配，因此，文獻[4]通過計算相鄰塊間的重疊塊運動增加運動矢量場密度，盡最大可能逼近真實運動矢量，文獻[5]則通過在塊匹配準則中增加可反映當前運動單向可靠度的正則化項來提高運動估計精度，上述方法盡管均能夠提升內插幀質量，但卻引入了較高的計算復雜度。

為了能夠以較低計算復雜度克服紋理區域的錯匹配問題，本文提出提取視頻幀多個特征進行塊匹配以提高雙向運動估計精度。視頻幀具有亮度分量Y、色差分量U和V，利用這些分量進行塊匹配，可更準確地追蹤物體運動軌跡。又由于人眼對物體邊緣特征較敏感，通過提取視頻幀的邊緣圖，并將與邊緣特征相關的正則化項融入塊匹配準則，可進一步地提高運動估計精度。然而，多特征共同進行匹配，勢必會成倍地增加運算成本，為了避免高計算復雜度，本文算法設計特殊模板將多個特征合并到單平面上，那么，只需進行一次塊匹配便可完成多特征匹配，從而以較低計算復雜度實現了高質量視頻幀內插。

1 本文算法

傳統的雙向運動估計算法使用絕對差和(Sum of Absolute Differences，SAD)在既定的搜索范圍內尋找最相似塊。傳統SAD僅使用了亮度分量，然而對于視頻信號除了具有亮度分量外，仍包含色差分量，例如，4∶2∶0的YUV視頻取樣格式存在色差分量U和V，但它們的采樣點個數在水平和垂直方向都是亮度Y的一半。由于相鄰像素間的色差分量變化經常小于亮度分量，加之彩色亞采樣導致彩色信息缺失，因此，在傳統視頻壓縮領域中，基于SAD的運動估計被廣泛使用。

對于幀率提升算法，高質量視頻內插依賴于準確的運動矢量。忽略了彩色信息的SAD往往并不能有效地追蹤物體運動，尤其是對于紋理細節豐富的視頻序列。在視頻的紋理區域，盡管存在大量的周期重復模式，但這些模式僅在亮度上具有較大相似性，而彩色特征往往具有很大差別。如圖1所示(原圖為彩色)，圖1a中的方框為Flower視頻序列第37幀的紋理區域，其內容是顏色各異的花朵與綠葉，由圖1b可觀察到通過顏色很容易區分紋理細節，而通過圖1c顯示的亮度圖卻不易區分紋理細節，尤其是觀察不出黃花與綠葉的區別。

圖1 視頻紋理區域周期重復模式的彩色與亮度圖視覺對比

因此，在SAD中加入彩色特征的匹配，可有效地避免SAD在紋理區域的錯匹配。那么，融入彩色特征的SAD可按式(1)計算

(1)

式中：v是當前塊Bt的候選運動矢量；p為在Bt內的像素位置；Yt-1(·)，Ut-1(·)和Vt-1(·)是前參考幀ft-1的亮度和色差分量；Yt+1(·)，Ut+1(·)和Vt+1(·)是后參考幀ft+1的亮度和色差分量。考慮到相鄰幀像素間色差分量的差值常小于亮度分量的差值，因此，U和V分量的SAD值被乘以平衡因子W以使Y，U和V三分量的差值對式(1)具有均等的貢獻。對于4∶2∶0的YUV視頻，色差分量U和V的取樣個數僅是Y分量的1/4，為了保證任一候選匹配塊和當前塊均有相同像素位置的色差分量，因此在計算式(1)之前首先使用雙立方插值算法[6]放大U和V分量至Y分量的尺寸。

彩色特征雖然能夠緩解紋理區域錯匹配帶來的不利影響，但其無法準確地描述物體的邊緣特征。由于邊緣包含了準確塊匹配的顯著信息，且在邊緣區域的匹配誤差與視覺理解是十分相似的，所以在SAD中加入與邊緣特征相關的項也可有效地提升運動估計精度。梯度可反映圖像邊緣，且計算圖像梯度的方法較多，但為了不引入過多的計算復雜度，簡單的Sobel算子[7]被用來計算視頻幀梯度，如圖2所示，通過Sobel算子計算出的梯度圖(圖2b所示)可清晰地展現原始幀的邊緣特征，因此其可被使用描述邊緣特征，并按式(2)融入到基于SAD的塊匹配準則

(2)

式中：ΔYt-1和ΔYt+1為由Sobel算子計算的前后參考幀ft-1和ft+1的梯度圖。由于梯度匹配誤差與亮度匹配誤差具有一定差別，因此需要加入平衡因子α去權衡各項對式(2)的影響。

圖2 Sobel算子提取的視頻幀梯度圖

使用式(2)進行塊匹配，雖然可綜合不同特征的匹配誤差，但也引入了較高的計算復雜度。為了以較低的計算復雜度完成多個特征的匹配，本文算法將亮度特征、彩色特征和邊緣特征通過特殊模板融合至單平面上，該特殊模板如圖3所示。

圖3 融合多特征的特殊模板

圖3中Y代表亮度像素點，G代表梯度像素點，U和V代表色差像素點，由圖3可看出，4種特征點均分了每個匹配塊的所有像素，且均勻地分布在整個匹配塊平面上，這相當于將當前塊分成了同樣尺寸的4層，每一層均是原始匹配塊尺寸的1/4。由于視頻具有層間相似性(圖像金字塔)，即下采樣獲得的圖像仍會保持與原始特征相似的特征[8]，所以通過該特殊模板融合而成的多特征塊仍會近似保持原始匹配塊的特征。那么，通過使用所提出的特殊模板，式(2)可被改進為

(3)

(4)

式中：BtY，BtU，BtV和BtG分別是當前塊Bt的Y，U，V和G的像素點集合。通過使用式(3)進行塊匹配運算，其計算復雜度與傳統SAD相同，但卻兼顧了多個特征的匹配，因此可在較低的計算復雜度下提高運動估計的精度。對于平衡因子W和α的選取，若干真實視頻序列在不同的W和α取值下被測試，圖4顯示了內插幀的平均峰值信噪比隨W和α變化的曲線，可看出當α固定為0.1時，最大的PSNR值出現在W= 8附近，當W固定為8時，最大的PSNR值出現在α= 0.1附近，因此，在本文中W和α分別取8和0.1。

圖4 隨W和α變化的PSNR曲線

上述改進的塊匹配準則將被使用在雙向運動估計中計算當前幀的運動矢量場，為了進一步的加快運動估計速度，三維遞歸搜索(3-D Recursive Search，3DRS)[9]被使用在雙向運動估計中。得到當前幀的運動矢量場后，再使用重疊塊運動補償(Overlapped Block Motion Compensated，OBMC)[10]計算出最后的內插幀。

2 實驗結果

實驗數據選取了4個4∶2∶0的YUV格式的CIF標準測試序列來驗證本文算法的有效性，它們包括：Foreman，Mobile，Flower和Football，其中Foreman前景背景分明且背景有輕微晃動，Mobile包含物體縮放和平移、旋轉等復雜運動，Flower包含豐富的彩色紋理細節，Football含有大量快速運動。為了測試內插幀的主客觀質量，每個測試序列的前50個偶幀被去除，并再次利用各種幀率提升算法從剩余51個奇幀中重建。插幀客觀質量通過內插幀和原始幀的PSNR衡量。為了評比本文算法的性能，對比了其他3種算法：文獻[4]提出的EBME算法(塊大小為8×8，全搜索半徑為4)；文獻[5]提出的Dual ME算法(塊大小為8×8，全搜索半徑為16)；文獻[9]提出的雙向3DRS運動估計法(分塊大小為8×8)。本文算法的分塊尺寸為8×8，且其與Dual ME算法和雙向3DRS算法均使用重疊尺寸為4的OBMC算法計算出最后的內插幀，對于EBME算法則使用文獻[4]提出的補償方法。

由表1可見，本文算法除Foreman序列外均超過了對比算法的最優者，尤其是對于包含復雜和快速運動的序列。對于Foreman序列，本文算法比雙向3DRS算法略低0.08 dB，這是因為Foreman序列具有較清晰的邊緣且紋理細節簡單，這使得傳統SAD就可保證高精度的運動估計。對于具有復雜和快速運動的Mobile和Football序列，本文算法分別超出對比算法中最優者2.00 dB和0.46 dB，這表明了本文算法可有效地追蹤復雜快速運動。對于色彩豐富的Flower序列，本文算法也超出了雙向3DRS算法0.39 dB，這表明本文算法可較好地區分彩色紋理細節。對于計算復雜度，表1也顯示了在Intel Core i5 3.20 GHz， 8 Gbyte內存PC平臺上的平均內插時間，可看出本文算法內插出一幀平均需要0.42 s， 其遠低于EBME算法。對于Dual ME算法，本文算法平均縮短了0.27 s，且獲得了4.49 dB的PSNR增益。由于本文算法與雙向3DRS算法的不同僅在于：雙向3DRS算法使用了傳統SAD；而本文算法使用了基于多特征的SAD，那么，本文算法盡管在塊匹配上與雙向3DRS算法有相同的計算復雜度，但由于需要一定的計算量提取邊緣特征和內插U，V分量，這造成了其平均內插時間高于雙向3DRS算法0.14 s，但相比于雙向3DRS算法，其可有效地改善內插幀質量，平均獲得了0.86 dB的PSNR增益。

表1 不同序列下各算法的平均PSNR和平均內插時間

圖5顯示了不同算法重建Flower序列第90幀的主觀視覺質量對比。首先可看到在路燈附近(左邊方框圈定)，Dual ME算法和雙向3DRS算法均出現了不同程度的模糊與變形，而本文算法能夠更好地保護路燈的邊緣特征，而對于路旁鮮花區域(右邊方框圈定)，對比算法均無法保證清晰的紋理細節，產生了一定程度的模糊，尤其是對于雙向3DRS算法，但本文算法很好地復原了紋理細節，獲得了更好的主觀視覺質量。

圖6顯示了不同算法重建Foreman序列第72幀的主觀視覺質量對比。對于雙眼和鼻子區域(方框圈定)，EBME算法和Dual ME算法均出現了不同程度的塊效應。對于雙向3DRS算法，其內插幀的左眼角紋理細節丟失，造成了一定的視覺質量衰退。本文算法能夠有效地抑制塊效應且可保護紋理細節，獲得了良好的主觀視覺質量。

圖5 Flower序列在不同算法下的主觀視覺效果(第90幀)

圖6 Foreman序列在不同算法下的主觀視覺效果(第72幀)

3 小結

本文提出了可融合多個特征的塊匹配方法以在較低的計算復雜度前提下有效改善雙向運動估計的錯匹配問題。由于視頻天然具有彩色信息，因此色差分量可作為一種特征融入到塊匹配過程。人眼往往對圖像邊緣較敏感，邊緣區域的匹配誤差可有效地反映視覺差別，因此，本文利用簡單的Sobel算子提取視頻幀的梯度信息，將可反映邊緣特征的梯度項加入塊匹配過程。盡管多特征匹配的融入可有效提高運動估計精度，但也引入了較高的計算復雜度。為了減少多特征匹配引入的計算復雜度，本文設計了特殊模板將多個特征合并到單平面上，如此就可以只進行一次塊匹配就完成多特征的匹配，實現了在低計算復雜度下運動估計精度的提高。仿真實驗也表明了本文算法可在較短的時間內完成內插幀重建，且可有效地改善視頻的主客觀質量。

[1]HWANG J，CHOI Y，CHOE Y. Frame rate up-conversion technique using hardware-efficient motion estimator architecture for motion blur reduction for TFT-LCD[J]. IEICE Trans. Electronic，2011(5)：896-904.

[2]LIU H，XIN R，ZHAO D，et al. Multiple hypotheses bayesian frame rate up-conversion by adaptive fusion of motion-compensated interpolations[J]. IEEE Trans. Circuits System Video Technology，2012，22(8)：1188-1198.

[3]CHOI B，LEE S，KO S. New frame rate up-conversion using bi-directional motion estimation[J]. IEEE Trans. Consume Electronic，2000，46(3)：603-609.

[4]KANG S，CHO K，KIM Y. Motion compensated frame rate up-conversion using extended bilateral motion estimation[J]. IEEE Trans. Consume Electronic，2007，53(4)：1759-1767.

[5]KANG S，YOO S，KIM Y. Dual motion estimation for frame rate up-conversion[J]. IEEE Trans. Circuits System Video Technology，2010，20(12)：1909-1914.

[6]KEYS R. Cubic convolution interpolation for digital image processing[J]. IEEE Trans. Acoustical Speech Signal Processing，1981(6)：1153-1160.

[7]朱秀昌，劉峰，胡棟.數字圖像處理與圖像通信[M].北京：北京郵電大學出版社，2002.

[8]GONZALEZ R C，WOODS R E. Digital Image Processing[M]. 3rd ed. Upper Saddle River，NJ：Prentice Hall，2008.

[9]徐洪峰，孫為平，丁玉琴，等. 一種改進的三維遞歸搜索視頻去隔行算法[J].計算機應用，2007，27(5)：1153-1155.

[10]ORCHARD M，SULLIVAN C. Overlapped block motion compensation：an estimation-theoretic approach[J]. IEEE Trans. Image Processing，1994，3(9)：693-699.

薛春玲(1983— )，女，講師，主要研究方向為圖像和視頻編碼；

李 然(1988— )，博士生，主要研究方向為圖像處理與多媒體通信；

朱秀昌(1947— )，教授，博士生導師，長期從事圖像通信方面的科研和教學工作。

責任編輯：時 雯

Multiple Features Matching Based Bidirectional Motion Estimation for Frame Rate Up-conversion

XUE Chunling1，LI Ran2，ZHU Xiuchang2

(1.HuangheScience&TechnologyCollege，Zhengzhou450063，China；2.JiangsuProvinceKeyLabonImageProcessing&ImageCommunication，NanjingUniversityofPostsandTelecommunications，
Nanjing210003，China)

It usually results in the quality degradation of the interpolated frame in frame rate up-conversion that lots of periodical repetitive patterns in the texture region of video frame lead to the mismatch of video blocks for bidirectional motion estimation. To overcome this problem，this paper proposes to extract multiple features of video frame and add them into the process of block-matching，and thus the probability of appearing mismatch is lowered. Since the video sequence naturally contains color information，the chrominance component is firstly mixed into the block-matching. Besides，human's eyes is obviously sensitive to image edges，and therefore the gradient component，which is computed by the simple Sobel operator，is used to reveal the edge feature and mixed into the block-matching. Although the multiple features matching can effectively improve the accuracy of motion estimation，it introduces also the higher computational complexity. To reduce the computational complexity of multiple features matching，a special template is designed to combine multiple features into a single panel，thereby completing multiple features matching by performing only a block-matching operation，which improve the accuracy of motion estimation while guaranteeing a low computational complexity. Experimental results show that the proposed algorithm can improve the both subjective and objective quality of the interpolated frame with a low computational complexity.

image processing；frame rate up-conversion；bidirectional motion estimation；multiple features matching

國家自然科學基金項目(61071091)；“通信工程”江蘇省高校優勢學科建設工程項目；江蘇省研究生創新項目(CXZZ12_0466)；鄭州市嵌入式系統應用技術重點實驗室項目(121PYFZX177)；鄭州市重點建設實驗室項目(鄭教高[2013]109號)

TN911.73

A

10.16280/j.videoe.2015.01.005

2014-02-20

【本文獻信息】薛春玲，李然，朱秀昌.基于多特征匹配的雙向運動估計幀率提升算法[J].電視技術,2015，39(1).