薛春玲，李 然，朱秀昌

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

基于多特征匹配的雙向運(yùn)動(dòng)估計(jì)幀率提升算法

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

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

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

圖像處理；幀率提升算法；雙向運(yùn)動(dòng)估計(jì)；多特征匹配

幀率提升(Frame Rate Up-conversion，F(xiàn)RUC)具有廣泛的應(yīng)用前景，例如，低比特率視頻通信和液晶顯示(LCD)運(yùn)動(dòng)去模糊等[1]。簡(jiǎn)單的幀率提升算法通過幀復(fù)制和幀平均實(shí)現(xiàn)，由于其忽略了幀間的運(yùn)動(dòng)信息，經(jīng)常會(huì)導(dǎo)致物體的運(yùn)動(dòng)模糊和畫面抖動(dòng)?？紤]幀間運(yùn)動(dòng)的運(yùn)動(dòng)補(bǔ)償幀率提升(Motion-Compensated Frame Rate Up-conversion，MC-FRUC)可有效地提高內(nèi)插幀質(zhì)量，因此獲得了廣泛關(guān)注。

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

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

1 本文算法

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

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

圖1 視頻紋理區(qū)域周期重復(fù)模式的彩色與亮度圖視覺對(duì)比

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

(1)

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

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

(2)

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

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

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

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

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

(3)

(4)

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

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

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

2 實(shí)驗(yàn)結(jié)果

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

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

表1 不同序列下各算法的平均PSNR和平均內(nèi)插時(shí)間

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

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

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

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

3 小結(jié)

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

[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]朱秀昌，劉峰，胡棟.數(shù)字圖像處理與圖像通信[M].北京：北京郵電大學(xué)出版社，2002.

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

[9]徐洪峰，孫為平，丁玉琴，等. 一種改進(jìn)的三維遞歸搜索視頻去隔行算法[J].計(jì)算機(jī)應(yīng)用，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— )，女，講師，主要研究方向?yàn)閳D像和視頻編碼；

李 然(1988— )，博士生，主要研究方向?yàn)閳D像處理與多媒體通信；

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

責(zé)任編輯：時(shí) 雯

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

國(guó)家自然科學(xué)基金項(xiàng)目(61071091)；“通信工程”江蘇省高校優(yōu)勢(shì)學(xué)科建設(shè)工程項(xiàng)目；江蘇省研究生創(chuàng)新項(xiàng)目(CXZZ12_0466)；鄭州市嵌入式系統(tǒng)應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室項(xiàng)目(121PYFZX177)；鄭州市重點(diǎn)建設(shè)實(shí)驗(yàn)室項(xiàng)目(鄭教高[2013]109號(hào))

TN911.73

A

10.16280/j.videoe.2015.01.005

2014-02-20

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