姜肇海，胡園園，司丹丹，干宗良

(南京郵電大學江蘇省圖像處理與圖像通信重點實驗室，江蘇南京210003)

一種改進的三維遞歸搜索幀率上轉換算法

姜肇海，胡園園，司丹丹，干宗良

(南京郵電大學江蘇省圖像處理與圖像通信重點實驗室，江蘇南京210003)

提出了一種改進的三維遞歸搜索(3－Dimension Recursive Search，3DRS)幀率上轉換算法。相較于3DRS算法，在3個方面提出改進:首先，調整候選運動矢量的選擇，充分利用運動失量的空間相關性;其次，增加一次逆序運動估計，加速運動失量收斂;最后，提出一種新的匹配準則以進一步提高運動估計的準確性。實驗結果表明，該算法有效提高了運動估計的準確性，所得結果在主客觀均取得較好的效果。

三維遞歸搜索;運動估計;幀率上轉換

幀率上轉換(Frame Rate Up－Conversion，F(xiàn)RUC)也稱為幀頻提升，主要是通過在相鄰兩幀圖像中間估計內(nèi)插幀，實現(xiàn)視頻幀率的提高。幀率上轉換算法最早起源于20世紀80年代，用于解決幀率為24/25 Hz的電影片源轉換為50/60 Hz以在普通電視中播放的問題。在視頻通信中，幀率上轉換技術可以有效提高系統(tǒng)的圖像傳輸質量。例如，當通信網(wǎng)絡波動，或者帶寬受限時，發(fā)送端可以通過減低幀頻來降低傳輸速率，在接收端可以通過幀率上轉換來估計丟棄的圖像幀，這樣可以有效解決低幀率視頻導致的視覺上的停滯感和跳躍感。

目前幀率上轉換中廣泛采用考慮視頻中物體運動信息的運動補償內(nèi)插算法，即運動補償幀插方法(Motion Compensation Frame Interpolation，MCFI)，它可以有效減輕非運動補償內(nèi)插算法引起的視頻模糊和抖動等現(xiàn)象［1］。運動補償內(nèi)插算法主要包括2步:運動估計和運動補償。由于運動估計的準確性直接影響內(nèi)插幀的效果，因此很多算法都致力于得到更加真實的運動矢量場。Haan等［2］提出了一種三維遞歸搜索(3－Dimension Recursive Search，3DRS)塊匹配運動估計算法。該算法主要基于連續(xù)視頻序列中幀與幀之間不存在運動突變和同一物體內(nèi)部運動場保持一致的觀點，利用當前宏塊的時間和空間相鄰塊運動矢量估計當前塊的運動矢量。Wang等［3］在此基礎上提出了僅利用3個時空候選矢量的運動估計算法，它降低了運動估計所需的復雜度。雖然這兩種算法得到的運動矢量場有很好的平滑性，但由于更新矢量范圍的限制，它們都不能保證運動矢量快速收斂，而且存在錯誤矢量傳遞的現(xiàn)象。

本文針對3DRS算法在幀率上轉換中存在的問題，對其進行了改進。首先，通過調整候選矢量選取，舍棄可能引入錯誤運動矢量的時間預測矢量，充分利用空間相鄰塊的運動矢量。其次，利用一次逆序運動估計加速運動矢量收斂。最后，提出一種新的匹配準則，匹配誤差的計算考慮到噪聲的影響，同時通過引入高頻信息，增加了對圖像邊緣運動估計的準確性。實驗結果表明，本文算法處理效果較好。

1 3DRS算法

3DRS算法假設圖像中物體尺寸比匹配塊尺寸大，且物體具有慣性。這兩個假設保證了圖像中某塊的最佳位移矢量可以從其時空相鄰塊的運動矢量中找到，從而沒有必要搜索所有可能的位移矢量，相比于要搜索整個區(qū)域的普通塊匹配算法而言，大大減少了計算復雜度。

取當前幀圖像的前一幀為參考幀，則當前塊和時空候選塊的相對位置如圖1所示。

假設當前塊為B(X)，其中X=(Xx，Xy)，代表當前塊左上角像素點的位置。圖像塊尺寸為M×N，則

圖1 當前塊與空間、時間候選塊的相對位置

當前幀中塊SD和參考幀中塊TD的運動矢量構成時空預測集CSa(X，n)

Sb和Tb的運動矢量構成時空預測集CSb(X，n)

CSa(X，n)和CSb(X，n)構成當前塊B(X)運動矢量候選集

使匹配誤差SAD最小的候選矢量即為當前塊的運動矢量

式中:fn(x)，fn″(x－D)分別代表當前幀和參考幀在x，x－D處的灰度值。

2 改進的3DRS算法

2.1 候選矢量的改變

3DRS算法僅利用2個空間相鄰塊和2個時間候選塊的運動矢量進行運動估計，提高了運動矢量場的平滑性，在幀率上轉換中得到了廣泛應用［4－5］。但當當前塊運動相對于匹配塊尺寸來說較小且當前塊所屬運動物體相對于匹配塊并不太大時，時間候選矢量由于距離當前塊較遠，因此它的運動和當前塊的相關性可能并不大。此外，對于場景切換的情況，時間候選矢量預測效果也不好。為了解決上述問題，本文算法改變候選失量的選擇。如圖2所示，舍棄時間候選矢量，同時增加空間候選矢量個數(shù)，取當前塊左方以及上方一共4個相鄰塊的運動矢量及其各自的更新值構成候選矢量集，充分利用了運動的空間相關性。

圖2 改進的3DRS運動矢量候選塊相對位置

2.2 增加逆序運動估計

由于3DRS算法中運動矢量更新值較小，因此一旦候選塊與當前塊的運動相差較大，將會導致不能正確得到當前塊的運動矢量。雖然可以通過迭代解決這一問題，但由于3DRS算法采用固定的掃描順序、候選塊，對于存在劇烈運動的塊需要迭代多次才能收斂到正確的值，而且迭代過程中可能由于某次找到的錯誤運動矢量導致之后迭代得到的運動矢量錯誤收斂。由于3DRS算法是遞歸搜索，位于當前塊之后的塊經(jīng)過多次遞歸可能已經(jīng)得到正確的運動矢量。因此，本算法通過一次候選塊取相反位置的逆序估計修正之前可能錯誤的運動矢量。即從圖像右下角，按照從右向左、從下向上的方向重新進行一次運動估計，同時構成候選失量的候選塊也取相反位置，如圖3所示，即選擇當前塊右方的1個相鄰塊以及下方的3個相鄰塊作為候選塊。

2.3 匹配誤差的更新

3DRS算法利用式(6)的SAD作為匹配準則尋找最佳匹配塊，由于圖像不可避免地含有噪聲，因此SAD最小并不一定對應真實的運動矢量。為了盡可能找到真實的運動矢量，本文算法對匹配準則做出調整。匹配誤差計算中忽略人眼不敏感的灰度值在3以下的匹配誤差，同時給予兩像素間匹配誤差大于25的點較大權值，這樣就減輕了噪聲對運動矢量準確度的影響。此外，由于圖像邊緣對內(nèi)插圖像質量的影響較大，本文算法通過對原始圖像進行高通濾波提取出圖像的邊緣信息，在匹配誤差計算中引入高頻項，提高了圖像邊緣處運動估計的可靠度。調整后的匹配準則為

圖3 逆向估計候選塊相對位置

式中:ffn，ffn″分別代表當前幀和參考幀的高頻信息。

3 實驗結果

實驗選取了4組幀率為30 Hz的標準CIF(352×288)格式序列:Bus，City，F(xiàn)oreman，Paris。這些序列包含不同的運動，例如Bus包含復雜紋理，F(xiàn)oreman前景運動豐富而背景有微小晃動。在所有實驗中，匹配塊尺寸都設為8×8。為了驗證本文算法效果，跳過測試序列的偶數(shù)幀，然后分別利用本文算法、文獻［2］的3DRS算法、文獻［8］的TF算法和文獻［9］的HD算法重構偶數(shù)幀，對下采樣后的測試序列進行幀率上轉換，并對處理結果進行比較。

表1、表2分別給出了各測試序列利用不同算法得到的前50內(nèi)插幀的平均PSNR、FSIM值。從表中可以看出，對各測試序列，采用本文算法得到的內(nèi)插幀的平均PSNR、FSIM值相對于另外3種算法，均有不同程度的提高。

圖4給出了Foreman序列中原始圖像及利用各種幀率上轉換算法得到的相應內(nèi)插圖像。其中圖4a是原始的中間幀，圖4b、圖4c、圖4d、圖4e分別是利用3DRS算法、TF算法、HD算法以及本文算法仿真得到的內(nèi)插圖像。從圖中可以看出，3DRS、HD得到的內(nèi)插圖像都有明顯的塊效應，這是由于錯誤的運動估計引起的，TF算法得到的內(nèi)插圖像由于過度平滑，在嘴部和帽子的頂部都存在一定的模糊。本文算法得到的內(nèi)插圖像比其他3種算法得到的結果更加清晰，這是由于本文算法利用一次逆序估計，修正了之前錯誤的運動矢量。

表1 不同序列各種算法下的PSNR

表2 不同序列各種算法下的FSIM

圖4 不同算法內(nèi)插出的Foreman序列

圖5是利用不同算法得到的City內(nèi)插幀，可以看出，本文算法得到的內(nèi)插圖像不僅在紋理較多的區(qū)域處得到準確的運動矢量，而且在底部建筑物存在對稱圖案的區(qū)域同樣得到比較好的效果，這是由于本文算法的匹配準則中引入了圖像的高頻信息，而且考慮了人眼對噪聲的敏感程度。

圖5 不同算法內(nèi)插出的City序列

4 小結

針對3DRS算法在幀率上轉換中存在的問題，本文提出了一種改進算法。首先通過調整候選矢量的選擇，排除了可能引入錯誤運動矢量的時間候選矢量，同時通過4個空間候選塊，充分利用了運動矢量的空間相關性。其次，增加了一次逆序運動估計，加速運動矢量正確收斂。此外，本文提出了一種新的匹配準則，匹配準則考慮了噪聲對運動估計的影響，同時通過引入圖像高頻成分提高了運動估計在邊緣處的準確性。文章對具有不同特點的視頻序列進行處理，并與其他算法在主、客觀兩個方面進行對比。實驗結果表明，本文算法得到的內(nèi)插圖像邊緣更加清晰，有效地減小了運動模糊以及塊效應，同時PSNR， FSIM也均有不同程度的提高。

［1］YANG Y，TUNG Y，WU J.Quality enhancement of frame rate up-converted video by adaptive frame skip and reliable motion extraction［J］. IEEE Trans.Circuits and Systems for Video Technology，2007，17(22): 1700-1713.

［2］HAAN G，BIEZEN P，HUIJGEN H，et al.True-motion estimation with 3-d recursive search blockmatching［J］.IEEE Trans.Circuits and Systems for Video Technology，1993，3(5):368-379.

［3］WANG J，WANG D，ZHANGW.Temporal compensatedmotion estimation with simple block-based prediction［J］.IEEE Trans.Broadcasting，2003，49(2):241-248.

［4］JEON B，LEE G，LEE S，et al.Coarse-to-fine frame interpolation for frame rate up-conversion using pyramid structure［J］.IEEE Trans.Consumer Electronics，2003，49(3)499-508.

［5］LEE G，JEON B，PARK R，et al.Hierarchicalmotion compensated frame rate up-conversion based on the gaussian/laplacian pyramid［C］//Proc. IEEE International Conference on Consumer Electronics.［S.l.］:IEEE Press，2003:350-351.

［6］WANG C，ZHANG L，HE Y，etal.Frame rate up-conversion using trilateral filtering［J］.IEEE Trans.Circuits and Systems for Video Technology，2010，20(6):886-893.

［7］HAN R，MEN A.Frame rate up-conversion for high-definition video applications［J］.IEEE Trans.Consumer Electronics，2013，59(1):229-236.

［8］KANG S，YOO S，KIM Y.Frame rate up-conversion using trilateral filtering［J］.IEEE Trans.Circuits and Systems for Video Technology，2010，20(6):886-893.

［9］HAN R，MEN A.Frame rate up-conversion for high-definition video applications［J］.IEEE Trans.Consumer Electronics，2013，59(1): 229-236.

Frame Rate Up－conversion Algorithm Based on Im proved 3D Recursive Search

JIANG Zhaohai，HU Yuanyuan，SIDandan，GAN Zongliang
(Jiangsu Provincial Key Lab.of Image Processing and Image Communication，Nanjing University of Posts and Telecommunications，Nanjing 210003，China)

A frame rate up－conversion algorithm based on improved 3D Recursive Search(3DRS)is presented.Compared with 3DRS algorithm，improvements from the following three aspectsare proposed:firstly，adjust the selection ofmotion vector candidates tomake fulluse ofmotion vector’s spatial correlation;then，add a reversemotion estimation to acceleratemotion vector’s convergence;finally，a new matching criterion is put forward so as to further improve the accuracy ofmotion estimation.Experimental results show that the algorithm in this paper effectively improves the accuracy ofmotion estimation and the results achieve better effects both subjectively and objectively.

3DRS;motion estimation;frame rate up－conversion

TN949.198

A

?? 雯

2013－08－10

【本文獻信息】姜肇海，胡園園，司丹丹，等.一種改進的三維遞歸搜索幀率上轉換算法［J］.電視技術，2014，38(13).