李本齋，吳從中，陳家銀

（合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009）

1 引言

H.264標(biāo)準(zhǔn)的編碼效率與之前的視頻壓縮標(biāo)準(zhǔn)相比有了明顯提高，但這是以運(yùn)算復(fù)雜度的增加為代價(jià)的。其中，可變塊大小的全搜索運(yùn)動(dòng)估計(jì)的運(yùn)算量在整個(gè)編碼運(yùn)算量中占約60%～80%。因此，如何提高運(yùn)動(dòng)估計(jì)的效率成為實(shí)時(shí)編碼的關(guān)鍵。塊匹配是運(yùn)動(dòng)估計(jì)最流行的方法[1]，其基本思想是將圖像序列的每一幀分成許多互不重疊的宏塊，并認(rèn)為宏塊內(nèi)所有像素的位移量都相同，然后對(duì)每個(gè)宏塊到參考幀某一給定特定搜索范圍內(nèi)，根據(jù)一定的匹配準(zhǔn)則找出與當(dāng)前塊最相似的塊，即匹配塊。匹配塊與當(dāng)前塊的相對(duì)位移即為運(yùn)動(dòng)矢量。視頻壓縮時(shí)，只需保存運(yùn)動(dòng)矢量和殘差數(shù)據(jù)就可以完全恢復(fù)出當(dāng)前塊。它被廣泛應(yīng)用于各種視頻編碼標(biāo)準(zhǔn)中，但算法復(fù)雜度和龐大的運(yùn)算量一直是視頻編碼實(shí)時(shí)實(shí)現(xiàn)的瓶頸。因此，算法研究人員研究利用快速算法降低計(jì)算的復(fù)雜度，而硬件設(shè)計(jì)人員致力于利用并行流水線技術(shù)開發(fā)有效的硬件加速器。筆者對(duì)運(yùn)動(dòng)估計(jì)算法進(jìn)行優(yōu)化，提出了兩種適合于硬件實(shí)現(xiàn)的運(yùn)動(dòng)估計(jì)算法，設(shè)計(jì)出合理的硬件結(jié)構(gòu)和加速器，構(gòu)建基于PowerPC的驗(yàn)證平臺(tái)，并驗(yàn)證該加速器數(shù)據(jù)處理能力的正確性。

2 H.264運(yùn)動(dòng)估計(jì)算法優(yōu)化

在H.264標(biāo)準(zhǔn)的搜索算法中[2]，圖像序列的當(dāng)前幀被劃分成互不重疊的16×16大小的子塊，而每個(gè)子塊又可劃分成更小的子塊，當(dāng)前子塊按一定的塊匹配準(zhǔn)則在參考幀中對(duì)應(yīng)位置的一定搜索范圍內(nèi)尋找最佳匹配塊，由此得到運(yùn)動(dòng)矢量和匹配誤差。運(yùn)動(dòng)估計(jì)的估計(jì)精度和運(yùn)算復(fù)雜度取決于搜索策略和塊匹配準(zhǔn)則，常用的匹配準(zhǔn)則是MAD，因?yàn)樗鼪]有乘除操作，不需要做乘法運(yùn)算，實(shí)現(xiàn)簡單方便。通常使用求和絕對(duì)誤差（SAD）代替MAD，（i，j）點(diǎn)的絕對(duì)誤差值定義如下

式中：（i，j）為運(yùn)動(dòng)矢量（MV）的坐標(biāo)，fk和 fk-1分別為當(dāng)前幀和上一幀圖像的相應(yīng)像素。將對(duì)應(yīng)最小的SADmin的塊用于預(yù)測(cè)。運(yùn)動(dòng)矢量定義為

為提高運(yùn)動(dòng)估計(jì)的效率，出現(xiàn)了很多快速搜索算法，如三步法、磚石搜索法、對(duì)數(shù)搜索和等級(jí)搜索等，這些算法減少了搜索點(diǎn)數(shù)，降低了運(yùn)算量，但數(shù)據(jù)流的不規(guī)則性和估計(jì)運(yùn)算時(shí)間的不確定性使它們很難在硬件中實(shí)現(xiàn)。目前，硬件設(shè)計(jì)人員多采用全搜索的方法[3]，即搜索前一幀搜索范圍內(nèi)的所有可能搜索點(diǎn)，給出最佳匹配點(diǎn)和運(yùn)動(dòng)矢量，它具有規(guī)則的數(shù)據(jù)流，有很好的搜索效果，但龐大的運(yùn)算量需要很多硬件資源，降低了處理速度。如編碼 1 920×1 250@50 f/s（幀/秒）的圖像，搜索窗為16×16 時(shí)，計(jì)算量約為：3×1 024×1 920×1 250×50=3 686.4×108次/秒（每秒3 686.4億次的運(yùn)算）。為減少計(jì)算量，現(xiàn)對(duì)運(yùn)動(dòng)估計(jì)算法進(jìn)行優(yōu)化，提出以下兩種適合硬件實(shí)現(xiàn)的方法：

方法1：在搜索窗口內(nèi)以步長2進(jìn)行抽樣搜索，即每隔1個(gè)像素點(diǎn)選1個(gè)候選宏塊，根據(jù)匹配準(zhǔn)則得到最佳匹配塊和運(yùn)動(dòng)矢量，如圖1所示。這種方法有規(guī)整的數(shù)據(jù)流，易于硬件實(shí)現(xiàn)，搜索精度會(huì)有所降低，但可減少一半的計(jì)算量。

圖1 每隔1個(gè)像素抽樣搜索

方法2：采用兩步搜索：1）在搜索窗口內(nèi)以步長4進(jìn)行初定位，即每隔3個(gè)像素點(diǎn)選1個(gè)候選宏塊，根據(jù)匹配準(zhǔn)則得到初定位點(diǎn)。2）在初定位點(diǎn)相鄰的4×4區(qū)域上進(jìn)行全搜索，得到最佳匹配塊和運(yùn)動(dòng)矢量，如圖2所示，這種方法與全搜索相比約減少1-（1/4+1/16）=11/16的計(jì)算量。

圖2 初定位方式抽樣搜索

3 塊匹配運(yùn)動(dòng)估計(jì)結(jié)構(gòu)及加速器設(shè)計(jì)

3.1 PE結(jié)構(gòu)

圖3為PE（Processing Element）的內(nèi)部結(jié)構(gòu)。PE處理單元[4]的設(shè)計(jì)通常是先對(duì)C（當(dāng)前塊）和S（參考?jí)K）進(jìn)行差值絕對(duì)值運(yùn)算，然后再將得到的結(jié)果直接與上次的SAD值累加。該P(yáng)E結(jié)構(gòu)主要由1個(gè)運(yùn)算模塊、1個(gè)SAD值的鎖存器（Latch）、1個(gè)累加單元（ALU）和1個(gè)輸出寄存器（REG）組成。運(yùn)算單元主要完成C和S的絕對(duì)差值計(jì)算，將得到的SAD值鎖存在Latch中，同時(shí)將當(dāng)前存于Latch中的SAD值送入累加單元進(jìn)行累加。當(dāng)編碼宏塊數(shù)據(jù)被掃描完一次后，累加單元中的SAD值將被送入其他單元做進(jìn)一步處理，并置累加器為0，進(jìn)行下一次塊匹配運(yùn)算。

圖3 PE結(jié)構(gòu)

3.2 速度優(yōu)先的硬件結(jié)構(gòu)

在FPGA設(shè)計(jì)中，速度和資源是一對(duì)對(duì)立統(tǒng)一的矛盾體，要求一個(gè)系統(tǒng)同時(shí)具有較少的資源消耗和較高的運(yùn)行頻率是不現(xiàn)實(shí)的。速度和資源的互換常常在FPGA設(shè)計(jì)中被用到。圖4中的速度優(yōu)先的硬件結(jié)構(gòu)[5]是以資源的犧牲為代價(jià)換取高的運(yùn)行速度，同時(shí)數(shù)據(jù)帶寬相應(yīng)增加。該結(jié)構(gòu)利用16個(gè)PA（PE Array）來并行完成1個(gè)匹配點(diǎn)的計(jì)算，每個(gè)PA由4×4 PE組成，這樣就能同時(shí)產(chǎn)生16×16個(gè)當(dāng)前塊數(shù)據(jù)和搜索區(qū)數(shù)據(jù)的SAD計(jì)算，對(duì)于1個(gè)16×16搜索范圍，256個(gè)搜索點(diǎn)采用全搜索需要256個(gè)周期完成，采用方法1需要128個(gè)周期，方法2只需要80個(gè)周期，有較快的運(yùn)行速度。

圖4 速度優(yōu)先的硬件結(jié)構(gòu)

3.3 資源優(yōu)先的硬件結(jié)構(gòu)

圖5中的資源優(yōu)先的硬件結(jié)構(gòu)是二維的脈動(dòng)陣列結(jié)構(gòu)[6]，相比于前一種結(jié)構(gòu)具有低硬件資源開銷、存儲(chǔ)帶寬小的優(yōu)點(diǎn)。利用4×4 PE陣列分時(shí)計(jì)算完1個(gè)16×16宏塊的16個(gè)4×4子塊，計(jì)算時(shí)，搜索區(qū)數(shù)據(jù)以總線方式輸入到PE的緩存中，當(dāng)前塊數(shù)據(jù)由寄存器裝入，16個(gè)PE輸出的絕對(duì)差值，被一起送入并行加法器中得到1個(gè)4×4塊的SAD。4×4 PE陣列每個(gè)周期計(jì)算1個(gè)4×4塊的SAD，在16個(gè)周期內(nèi)完成16個(gè)SAD值計(jì)算，累加得到16×16宏塊的SAD值。對(duì)于1個(gè)16×16搜索范圍，256個(gè)搜索點(diǎn)采用全搜索需要4 096個(gè)周期完成，而采用方法1需要2 048個(gè)周期，方法2僅需要1 280個(gè)周期。運(yùn)行速度變慢，但所需資源和數(shù)據(jù)帶寬都相應(yīng)減少。

圖5 資源優(yōu)先的硬件結(jié)構(gòu)

3.4 加速器總體設(shè)計(jì)

加速器[7]的總體結(jié)構(gòu)如圖6所示，包括存儲(chǔ)模塊、地址產(chǎn)生模塊、PE陣列、控制單元和輸出比較模塊。存儲(chǔ)模塊用于緩存當(dāng)前塊和參考幀數(shù)據(jù)；地址產(chǎn)生模塊產(chǎn)生讀取所需數(shù)據(jù)的相應(yīng)地址；PE陣列完成宏塊的SAD值計(jì)算；控制單元完成整個(gè)處理過程的控制和調(diào)度。MVbest為搜索到的最佳運(yùn)動(dòng)矢量，SADmin是對(duì)應(yīng)的最小SAD值。

圖6 加速器總體結(jié)構(gòu)

4 運(yùn)動(dòng)估計(jì)硬件加速器驗(yàn)證平臺(tái)

筆者在Xilinx Virtex-II PRO開發(fā)板上對(duì)設(shè)計(jì)的硬件加速器進(jìn)行驗(yàn)證，驗(yàn)證平臺(tái)結(jié)構(gòu)[8]如圖7所示。其中，PowerPC405是1個(gè)32位的定點(diǎn)硬核，負(fù)責(zé)總線的調(diào)度和各個(gè)模塊的協(xié)調(diào)工作；JTAG是調(diào)試接口，用于對(duì)程序的調(diào)試，系統(tǒng)有32 Mbyte的在片RAM和可擴(kuò)展的DDR存儲(chǔ)控制器，有PLB總線和OPB總線，可以通過總線橋進(jìn)行數(shù)據(jù)交互。

圖7 驗(yàn)證平臺(tái)系統(tǒng)框圖

驗(yàn)證時(shí)，首先使用EDK10.2構(gòu)建PowerPC的最小系統(tǒng)，然后將硬件加速器集成到該系統(tǒng)中，編譯通過后由USB口下載到目標(biāo)板，系統(tǒng)開始運(yùn)行后通過RS-232從上位機(jī)下載待編碼的圖像數(shù)據(jù)，下載的數(shù)據(jù)保存在目標(biāo)板上的256 Mbyte DDR SDRAM中。數(shù)據(jù)下載完畢后程序?qū)⒋幋a數(shù)據(jù)依次寫入加速器并啟動(dòng)，并將處理完的數(shù)據(jù)再寫入DDR SDRAM，待全部數(shù)據(jù)處理完畢，Power-PC將處理結(jié)果一起發(fā)送給上位機(jī)。上位機(jī)將結(jié)果與本機(jī)C代碼執(zhí)行結(jié)果相比較，最終確認(rèn)硬件加速器的數(shù)據(jù)處理能力是否正確。

5 實(shí)驗(yàn)結(jié)果分析

將文中所提到的兩種優(yōu)化算法用foreman，football，news序列在AVC下與全搜索進(jìn)行了對(duì)比，結(jié)果見表1。可見，方法1僅有平均0.45 dB的PSNR下降卻減少了50%的計(jì)算量，方法2有平均0.67 dB的PSNR下降，減少了約68.7%的計(jì)算量。

當(dāng)塊尺寸為 16，搜索范圍[-8，7]，CIF@30 Hz時(shí)，對(duì)兩種硬件結(jié)構(gòu)的處理速度和資源消耗等性能進(jìn)行了對(duì)比，結(jié)果見表2。

表1 優(yōu)化算法與全搜索性能對(duì)比

表2 兩種結(jié)構(gòu)性能對(duì)比

本文對(duì)H.264運(yùn)動(dòng)估計(jì)算法進(jìn)行優(yōu)化，提出兩種適合硬件實(shí)現(xiàn)的搜索方法，表1的實(shí)驗(yàn)數(shù)據(jù)表明，在不損失圖像質(zhì)量的同時(shí)，明顯減少了運(yùn)算量，提高了速度。同時(shí)與硬件相結(jié)合，給出速度優(yōu)先和資源優(yōu)先的兩種結(jié)構(gòu)，兩種結(jié)構(gòu)在速度和資源方面各有優(yōu)勢(shì)，設(shè)計(jì)出運(yùn)動(dòng)估計(jì)的硬件加速器，在Xilinx XUP Virtex-II PRO開發(fā)板中做了驗(yàn)證，結(jié)果表明該加速器能正確完成H.264運(yùn)動(dòng)估計(jì)的數(shù)據(jù)處理功能。

[1]畢厚杰.新一代視頻壓縮編碼標(biāo)準(zhǔn)——H.264/AVC[M].北京：人民郵電出版社，2005.

[2]YANG KM，SUNM T，WU L.A family of VLSIdesigns for themotion compensation block-matching algorithm[J].IEEE Trans.Circuits and Systems，1989，36（10）：1317-1325.

[3]CHENCY，HUANGCT，CHENYH，etal.LevelC+data reuse scheme formotion estimation with corresponding coding orders[J].IEEE Trans.Circuits and Systems for Video Technology，2006，16（4）：553-558.

[4]王睿，林濤，林爭輝，等.一種H.264運(yùn)動(dòng)估計(jì)器的VLSI設(shè)計(jì)[J].微電子學(xué)與計(jì)算機(jī)，2004（11）：153-157.

[5]黃衛(wèi)鋒，桑紅石，鄭兆青，等.用于H.264的高性能整像素運(yùn)動(dòng)估計(jì) VLSI的設(shè)計(jì)[J].微電子學(xué)，2007（4）：260-264.

[6]CHENTC，HUANGYW，CHENLG.Analysisand design ofmacroblock pipelining for H.264/AVC VLSIarchitecture[EB/OL].[2009-12-20].http://ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F9255%2F29377%2F01329261.pdf%3Farnumber%3D1329261&authDecision=-203.

[7]HSU Meiyun，CHANG Haochieh，WANG Yichu，et al.Scalable module-based architecture for MPEG-4 BMA motion estimation[EB/OL].[2009-12-20].http://ntur.lib.ntu.edu.tw/bitstream/246246/2007041910021255/1/00921053.pdf.

[8]石磊，林濤，焦孟草.H.264/AVC硬件解碼器設(shè)計(jì)及其驗(yàn)證策略[J].微電子學(xué)，2006（2）：16-19.