3DRS運動估計算法的FPGA實現(xiàn)

唐 坤，陳穎琪，陳 立，高志勇

(上海交通大學圖像通信與網(wǎng)絡(luò)工程研究所，上海200240)

目前在消費電子領(lǐng)域，隨著視頻技術(shù)的發(fā)展，所使用的視頻格式從之前的標清提升到現(xiàn)在的高清、超高清視頻格式，在用戶獲得越來越好的觀看體驗的同時，也給視頻的傳輸和處理提出了新的挑戰(zhàn)。視頻格式提升，相應(yīng)的數(shù)據(jù)率也提高了數(shù)倍，在帶寬有限的情況下，往往在視頻編碼端對視頻進行降采樣，以降低圖像幀率的代價降低了傳輸所用的帶寬，這樣帶來的后果就是視頻解碼端獲得的圖像運動不連續(xù)，質(zhì)量退化，幀率低。同時低幀率的視頻在液晶顯示器上播放將帶來一系列觀看體驗的問題，例如卡頓。為了解決這一問題，可以對視頻接收端對解碼得到的視頻采用插幀的方法，提高視頻的幀率，也就是幀率上變換技術(shù)。

為了達到幀率上變換的目的，目前主流的做法是采用運動補償內(nèi)插法(Motion Compensated Interpolation，MCI)。MCI方法首先進行運動估計，估計出原始序列的真實運動矢量，從而獲得正確的內(nèi)插矢量，并產(chǎn)生內(nèi)插幀。在眾多的MCI方法中，三維遞歸搜索(3-Dimension Recursive Search，3DRS)方法［1］是運動估計矢量可收斂、計算復(fù)雜度低、硬件可實現(xiàn)的算法，因此被廣泛應(yīng)用于視頻的幀率上變換的實時處理領(lǐng)域中。

3DRS算法是塊匹配算法，其中心思想是利用圖像的運動在空間和時間上的相關(guān)性，對每一個估計塊使用其空間上的相鄰塊和時間上的相鄰塊已經(jīng)獲得的估計矢量來生成當前估計塊的候選矢量，并篩選獲得最佳的運動矢量，將其作為該估計塊的預(yù)測矢量。但是3DRS算法使用單向搜索矢量，容易導(dǎo)致抖動，并且在某些運動序列情況下很難獲取正確的預(yù)測運動矢量。

本文基于3DRS算法，利用視頻運動的連續(xù)性［2］，結(jié)合文獻［3］中提到的雙向運動估計搜索方法，對圖像分塊完成運動估計操作。

1 運動估計算法

3DRS算法使用單向運動估計搜索矢量，即運動矢量只使用前一幀的原始像素塊來重建新的內(nèi)插圖像，這樣容易導(dǎo)致視頻處理時傳遞誤差的累積，使得處理效果惡化，并且重建圖像中對應(yīng)原始圖像完全靜止的部分也可能會出現(xiàn)抖動［4］。

雙向運動估計基于前后兩幀原始圖像的像素來重建新的圖像，其處理如圖1所示。

圖1 雙向運動估計示意圖

對于內(nèi)插圖像的當前處理塊，3DRS算法采用光柵掃描的順序處理，并參考文獻［5］中3DRS的空間和時間參考塊的配置方案，如圖2所示。

圖2 DRS矢量選取方案

圖2 中表示的3DRS矢量選取方案處理了4種情況，分別考慮了圖像處理的方向(自頂向下處理圖像和自底向上處理圖像)和圖像的位置(奇塊和偶塊，奇塊和偶塊的定義將在第2節(jié)中給出)。

參考塊的最佳運動矢量將作為當前處理塊的參考矢量，本文將圖2中的3個候選矢量進行處理擴充后獲得10個候選矢量，如下所示:

1) 零運動矢量;

2) 空間中值失量;

3) 空間矢量A;

4) 空間矢量A+小抖動;

5) 空間矢量A+大抖動;

6) 空間矢量B;

7) 空間矢量B+小抖動;8) 空間矢量B+大抖動;9) 時間矢量;10)動量矢量。

上述候選集合中，空間和時間矢量利用了圖像運動在空間和時間上的連續(xù)性，大抖動矢量有利于加速收斂，小抖動矢量有利于保持矢量場的平滑性，動量矢量代表了物體運動的慣性，零運動矢量的作用在于快速恢復(fù)最佳矢量，空間中值矢量有利于保持矢量場的平滑性。

算法通過對10個運動估計候選矢量對應(yīng)的像素塊做SAD(絕對值差和)，并篩選出SAD值最小的運動估計矢量，將其作為當前處理塊的最佳運動矢量。

2 硬件設(shè)計方案

2.1 總體框架

3DRS運動估計算法硬件設(shè)計的總體框架如圖3所示。

圖3 算法硬件結(jié)構(gòu)

每個塊處理開始時，由運動矢量產(chǎn)生模塊根據(jù)當前塊的位置產(chǎn)生出10個候選矢量，片上緩存訪問模塊安排候選矢量依次訪問片上緩存，由片上緩存取出對應(yīng)的像元數(shù)據(jù)后發(fā)送給SAD模塊，進行SAD計算，最后由矢量分析模塊根據(jù)SAD計算結(jié)果篩選出最佳的運動矢量，并將結(jié)果存入運動矢量產(chǎn)生模塊，更新其存儲的最佳運動矢量。

硬件實現(xiàn)框架中的各個模塊設(shè)計功能如下:

1)運動矢量產(chǎn)生模塊:維護圖像中塊處理的順序，根據(jù)塊在圖像中的位置，產(chǎn)生對應(yīng)的10個運動估計候選矢量，并存儲最佳運動矢量;

2)片上緩存訪問模塊:接收運動候選矢量，并安排其訪問片上緩存;

3)片上緩存:存儲像元數(shù)據(jù)，接收運動矢量，并在約定時鐘周期內(nèi)取出數(shù)據(jù)發(fā)送給SAD模塊，同時訪問外存DDR，更新緩存內(nèi)容;

4)SAD模塊:接收像元數(shù)據(jù)，計算其SAD值(絕對值差和);

5)矢量分析模塊:接收SAD結(jié)果，篩選出最優(yōu)運動矢量，并發(fā)送給運動矢量產(chǎn)生模塊。

2.2 塊組設(shè)計

傳統(tǒng)的3DRS算法都是按行的掃描順序來處理圖像，例如光柵掃描［1］或者曲線掃描［6］。而本設(shè)計采用塊組的掃描處理方法，可以大幅度減少帶寬開銷。

塊組組成及數(shù)據(jù)更新方式如圖4所示。

圖4 塊組組成及數(shù)據(jù)更新示意圖

圖4 a表示塊組的組成，按照標號順序來依次處理塊，標號為偶數(shù)的稱為偶數(shù)塊，標號為奇數(shù)的稱為奇數(shù)塊。圖4b表示塊組的數(shù)據(jù)更新，中間表示當前和下一處理塊組位置，黑色虛線表示當前處理塊組的搜索區(qū)，右邊白色塊區(qū)表示處理下一個塊組時需要更新的數(shù)據(jù)區(qū)域。

由圖4b可得當處理同一個塊組的不同塊時，不需要額外更新數(shù)據(jù)，只有當處理塊組變化時才需要更新數(shù)據(jù)。那么平均到每個塊的相對更新數(shù)據(jù)量為(圖像格式為YUV4 228 bit)

式中:Ratioblock表示更新數(shù)據(jù)相對于塊大小的倍數(shù);N表示塊大小為N×N;y表示搜索區(qū)豎直方向大小。

2.2.1 帶寬分析

3DRS運動估計算法的帶寬需求體現(xiàn)在片上緩存的更新數(shù)據(jù)上。該操作需要訪問外存DDR，并以塊組為單位來更新數(shù)據(jù)。

式(1)給出了平均每個塊更新數(shù)據(jù)量相對于塊本身大小的倍數(shù)，則處理完一幀所需要更新的數(shù)據(jù)量為

式中:Dpic表示一幀圖像的數(shù)據(jù)量。而考慮傳統(tǒng)的光柵掃描或者曲線掃描方式，其更新一幀的數(shù)據(jù)量為

采用塊組的處理方法后，系統(tǒng)帶寬相對于傳統(tǒng)處理方式節(jié)省帶寬的百分比為

在設(shè)計中，若分塊大小為32×32，搜索范圍設(shè)定為192 pixel×108 pixel，則由式(4)可得節(jié)省帶寬約73%。

2.3 片上緩存

考慮搜索范圍為192 pixel×108 pixel，圖像為4 228 bitYUV格式，片上緩存數(shù)據(jù)存儲及更新方式如圖5所示。

圖5 片上緩存數(shù)據(jù)存儲及更新方式示意圖

圖5 中tile是片上緩存的一個分割單元，其寬度等于一個塊組的寬度，高度等于塊組高度加上豎直搜索區(qū)。圖中白色區(qū)域為當前處理塊組所需要使用的像素區(qū)域。而斜體方塊區(qū)域表示更新數(shù)據(jù)存儲區(qū)域。

片上緩存在一個塊組處理過程中的工作內(nèi)容包括兩方面:接收運動矢量，在當前搜索范圍內(nèi)找到匹配的像素塊，并輸出給SAD計算模塊;更新下一個塊組所需的像素值到更新數(shù)據(jù)存儲區(qū)域。

2.3.1 RAM組織

RAM是片上緩存存儲數(shù)據(jù)的主體，設(shè)計中采用單口RAM(雙口RAM由于有雙通道邏輯以及安全保護措施，因此面積比單口RAM大許多，不予采用)。

每次運動估計矢量訪問片上緩存，需要前后幀共2×32×32 pixel的Y數(shù)據(jù)，處理該數(shù)據(jù)設(shè)計時鐘越短，所需RAM片數(shù)越多，后端SAD處理模塊越大，在設(shè)計中約定16拍處理一個運動估計矢量(既能滿足系統(tǒng)的時鐘約束，同時也減少了設(shè)計所需的面積)。

在此約束下，采用128 bit位寬的RAM，前后向各8片RAM，每拍輸出2×32×2 pixel的Y數(shù)據(jù)，RAM的組織方式見圖6。

圖6 RAM組織方式

圖6 中標號0～7的RAM為一組RAM(前向有一組RAM，后向也有一組RAM)，同組RAM共用地址，水平和豎直方向復(fù)制RAM的組織方式即可。圖中虛線填充區(qū)域表示運動矢量需求數(shù)據(jù)的一種形式，黑色實線框表示實際取數(shù)。

RAM深度為

式中:第一項表示tile的高度除以RAM的行數(shù)，因子2表示YUV像素的數(shù)據(jù)率是單通道Y像素數(shù)據(jù)率的2倍(其中UV信息僅用于重建圖像)，因子8表示總計8個tile。

系統(tǒng)所需RAM的總?cè)萘繛?/p>

2.3.2 RAM取數(shù)與更新

由圖6可知一組RAM位寬512 bit，保證了一組RAM取數(shù)可以拼湊出所需的32 pixel數(shù)據(jù)，因此對于一個運動估計向量，取數(shù)過程如下:

1)接收運動矢量，根據(jù)該運動矢量計算出RAM取數(shù)的基址以及每片RAM取數(shù)的地址偏移;

2)每拍取出2×512 bit×2的數(shù)據(jù)，并更新RAM取數(shù)基址，取數(shù)操作持續(xù)16拍完成;

3)將前級獲得數(shù)據(jù)拼接后得到2×256 bit×2的數(shù)據(jù)，輸出到SAD模塊。

一組RAM的數(shù)據(jù)水平位寬為512 bit，與塊組的水平位寬相等，因此對于數(shù)據(jù)更新而言，其過程更加簡單，步驟如下所示:

1)由當前塊組坐標計算出下一個塊組坐標，并計算其需更新數(shù)據(jù)在外存DDR中的基地址;

2)一次從外存DDR中讀取512 bit數(shù)據(jù)，存入RAM，并更新外存訪問基地址和RAM地址;

3)反復(fù)從DDR中讀取數(shù)據(jù)，直到tile更新完成。

3 硬件實現(xiàn)結(jié)果

采用Virtex6-760芯片，M2N2G64TU8HG5B-AC內(nèi)存(容量 2 Gbyte，頻率為 400 MHz)，使用 Verilog 語言［7］，對設(shè)計進行了驗證和實現(xiàn)。

使用ISE工具綜合得到的3DRS運動估計模塊的結(jié)果如表1所示。

表1 系統(tǒng)FPGA綜合結(jié)果

此外，設(shè)計綜合頻率可達75.4 MHz，每秒可處理高清視頻60幀，處理超高清視頻15幀。

另外，使用Cadence公司的RC工具在65 nm條件下對系統(tǒng)代碼進行綜合，作為ASIC設(shè)計的參照結(jié)果，其綜合面積如表2所示。

表2 系統(tǒng)硬件綜合面積(TSMC 65 nm)

同時系統(tǒng)的FPGA驗證平臺及結(jié)果可見圖7。

圖7 FPGA驗證平臺及連接方式

FPGA驗證平臺，HDMI輸入由計算機顯卡輸出，視頻經(jīng)處理后通過子板輸出到顯示器上，如圖4a所示。圖4b中FPGA驗證板右側(cè)為HDMI輸入輸出子板，左側(cè)為代碼下載器。

4 小結(jié)

本文給出了3DRS運動估計算法的一種實現(xiàn)方法，在硬件設(shè)計上對帶寬作了針對性的優(yōu)化設(shè)計，并給出了詳細的片上緩存組織與設(shè)計，最后使用Xilinx公司的V6 FPGA驗證了整個系統(tǒng)。

該算法在FPGA上實現(xiàn)了高清的實時處理，優(yōu)點是設(shè)計頻率為74.5 MHz，易于實現(xiàn);并且采用了塊組的處理方法，大大降低了系統(tǒng)的帶寬需求。缺點是片上緩存面積較大，存在優(yōu)化的余地。一個可行的優(yōu)化方案是加入壓縮模塊，對輸入片上緩存的視頻數(shù)據(jù)進行壓縮，再對輸出像元緩存的視頻數(shù)據(jù)進行解壓縮，這樣可以有效減少片上緩存的面積。

［1］ DE HAAN G，BIEZEN PWA C，HUIJGEN H，et al.True-motion estimation with 3-D recursive search block matching［J］.IEEE Trans.Circuits and Systems for Video Technology，1993，3(5):368-379.

［2］李珂，高志勇，陳立.基于運動連續(xù)性的幀率上變換算法［J］.電視技術(shù)，2013，37(11):61-65.

［3］賈茜，肖進勝，易本順.基于三維遞歸搜索的多級運動估計視頻幀率上轉(zhuǎn)換方法［J］.電子與信息學報，2012，34(10):2336-2341.

［4］徐洪峰，孫為平，丁玉琴.一種改進的三維遞歸搜索視頻去隔行算法［J］.計算機應(yīng)用，2007，27(5):1153-1155.

［5］毛韌，陳穎琪，高志勇，等.基于運動連續(xù)性的幀率上變換算法［J］.電視技術(shù)，2012，36(19):23-26.

［6］ AL-KADI G，HOOGERBRUGGE J，GUNTURS，et al.Meanderingbased parallel 3DRSalgorithm for the multicore era［C］//Digest of Technical Papers International Conferenceon Consumer Electronics(ICCE).Las Vegas:IEEE Press，2010:21-22.

［7］夏宇聞.Verilog HDL數(shù)字設(shè)計與綜合［M］.2版.北京:電子工業(yè)出版社，2012.