3DRS運(yùn)動估計(jì)算法的FPGA實(shí)現(xiàn)

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

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

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

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

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

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

1 運(yùn)動估計(jì)算法

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

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

圖1 雙向運(yùn)動估計(jì)示意圖

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

圖2 DRS矢量選取方案

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

參考塊的最佳運(yùn)動矢量將作為當(dāng)前處理塊的參考矢量，本文將圖2中的3個(gè)候選矢量進(jìn)行處理擴(kuò)充后獲得10個(gè)候選矢量，如下所示:

1) 零運(yùn)動矢量;

2) 空間中值失量;

3) 空間矢量A;

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

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

6) 空間矢量B;

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

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

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

2 硬件設(shè)計(jì)方案

2.1 總體框架

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

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

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

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

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

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

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

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

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

2.2 塊組設(shè)計(jì)

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

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

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

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

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

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

2.2.1 帶寬分析

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

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

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

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

在設(shè)計(jì)中，若分塊大小為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是片上緩存的一個(gè)分割單元，其寬度等于一個(gè)塊組的寬度，高度等于塊組高度加上豎直搜索區(qū)。圖中白色區(qū)域?yàn)楫?dāng)前處理塊組所需要使用的像素區(qū)域。而斜體方塊區(qū)域表示更新數(shù)據(jù)存儲區(qū)域。

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

2.3.1 RAM組織

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

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

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

圖6 RAM組織方式

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

RAM深度為

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

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

2.3.2 RAM取數(shù)與更新

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

1)接收運(yùn)動矢量，根據(jù)該運(yùn)動矢量計(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)由當(dāng)前塊組坐標(biāo)計(jì)算出下一個(gè)塊組坐標(biāo)，并計(jì)算其需更新數(shù)據(jù)在外存DDR中的基地址;

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

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

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

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

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

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

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

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

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

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

圖7 FPGA驗(yàn)證平臺及連接方式

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

4 小結(jié)

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

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

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

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

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

［5］毛韌，陳穎琪，高志勇，等.基于運(yùn)動連續(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è)計(jì)與綜合［M］.2版.北京:電子工業(yè)出版社，2012.