羅 隆，施隆照，洪曉劍，嚴(yán)丹鈺

(福州大學(xué)物理與信息工程學(xué)院，福建 福州 350108)

0 引言

智能手機(jī)和數(shù)碼設(shè)備的快速發(fā)展，推動(dòng)了視頻影像的大量傳播.HEVC/H.265是目前最新的視頻編碼標(biāo)準(zhǔn)，其中的幀間預(yù)測(cè)通過(guò)減少時(shí)域冗余能夠有效地壓縮視頻大小.分像素插值作為幀間預(yù)測(cè)中的一部分，在提高運(yùn)動(dòng)估計(jì)精度的同時(shí)引入較多的計(jì)算量，增加了編碼器的復(fù)雜程度.據(jù)統(tǒng)計(jì)，在編碼端分像素插值模塊占據(jù)了約1/4的復(fù)雜度，在解碼端則占據(jù)了約50%的復(fù)雜度[1].

當(dāng)前有不少降低分像素插值模塊復(fù)雜程度的研究，普遍做法是將乘法計(jì)算轉(zhuǎn)換成移位和加法操作，加法器的數(shù)量很大程度反映了模塊硬件資源的使用情況.減少加法器數(shù)量的方法可以歸納為以下幾類(lèi)： 一是復(fù)用濾波器中公有因式，這是HEVC編碼標(biāo)準(zhǔn)初定時(shí)期許多文獻(xiàn)都會(huì)采用的一種方法，以文[2-4]等為代表；二是對(duì)濾波系數(shù)進(jìn)行拆分，在加法器前級(jí)加入選擇器對(duì)濾波器類(lèi)型進(jìn)行選擇，使3種濾波器共用1種硬件架構(gòu)，以文[5]等為代表；三是將濾波器系數(shù)進(jìn)行一定程度的縮放，甚至是忽略一些權(quán)重影響較小的濾波系數(shù)，從而減少插值過(guò)程中需讀取的參考像素點(diǎn)數(shù)，同時(shí)也減少了濾波系數(shù)拆分成2的冪次項(xiàng)的個(gè)數(shù)，以文[6]等為代表.

上述研究雖然采用按行流水的插值架構(gòu)，在減少硬件面積的同時(shí)維持了一定的吞吐率，但在面積與性能上都達(dá)不到人們的期望值.在分像素搜索過(guò)程中需要進(jìn)行多次分像素插值操作，若插值模塊的最高工作頻率太低，將嚴(yán)重影響編碼器的工作效率.針對(duì)此問(wèn)題，本研究在采用按行流水插值架構(gòu)的基礎(chǔ)上，使用Wallace樹(shù)壓縮算法對(duì)分像素插值計(jì)算過(guò)程中的各項(xiàng)進(jìn)行壓縮，只在最終輸出結(jié)果的一級(jí)使用加法器.相比于傳統(tǒng)方法不僅減少了硬件面積，而且提高了模塊可工作的最高頻率.所提算法在硬件上得到驗(yàn)證，硬件設(shè)計(jì)以Verilog HDL語(yǔ)言進(jìn)行描述，使用Modelsim進(jìn)行功能仿真驗(yàn)證，在Synopsys Design Compiler上使用SAED 32 nm標(biāo)準(zhǔn)單元庫(kù)進(jìn)行綜合.

1 系統(tǒng)概述

1.1 分像素搜索過(guò)程

圖1 分像素搜索Fig.1 Sub-pixel accuracy search

分像素搜索的示意圖如圖1所示，圖中標(biāo)識(shí)了其中的9個(gè)整像素點(diǎn)，8個(gè)1/2像素點(diǎn)以及8個(gè)1/4像素點(diǎn).

分像素搜索過(guò)程中以PU(prediction unit)為單元求殘差，對(duì)殘差進(jìn)行SATD(sum of absolute transformed difference)變換后，結(jié)合編碼比特?cái)?shù)以及拉格朗日算子進(jìn)行率失真代價(jià)計(jì)算，取率失真代價(jià)最小的像素點(diǎn)為最優(yōu)點(diǎn).

分像素搜索的流程如下： 1)在最優(yōu)整像素點(diǎn)(以序號(hào)0像素點(diǎn)為例)周?chē)?個(gè)1/2分像素位置依次對(duì)參考像素塊進(jìn)行插值操作，取8個(gè)搜索點(diǎn)以及0像素點(diǎn)中率失真代價(jià)最小的點(diǎn)為最優(yōu)點(diǎn).假設(shè)圖1中序號(hào)1分像素點(diǎn)為1/2分像素位置的最優(yōu)點(diǎn).2)對(duì)1/2分像素位置最優(yōu)點(diǎn)周?chē)?個(gè)1/4像素點(diǎn)繼續(xù)進(jìn)行1/4最優(yōu)點(diǎn)的搜索，搜索過(guò)程與1/2分像素位置最優(yōu)點(diǎn)類(lèi)似，最終得到率失真代價(jià)最小的1/4像素點(diǎn)為最優(yōu)點(diǎn)，保存其運(yùn)動(dòng)矢量及率失真代價(jià).至此，一個(gè)PU的分像素搜索過(guò)程結(jié)束.

1.2 按行流水插值架構(gòu)

HEVC中PU大小從4 px × 4 px至64 px × 64 px[7]分布，故選擇合適的最小插值PU單元實(shí)現(xiàn)硬件的最大程度復(fù)用是需要仔細(xì)考慮的問(wèn)題.文[4]和文[8]從參考像素利用率、硬件面積等方面考慮了最小插值PU單元的選擇，最終論證了選擇8 px × 8 px大小PU作為最小插值單元最為理想，PSNR的損失極小同時(shí)有利于硬件實(shí)現(xiàn).本研究同樣選擇8 px × 8 px PU作為最小插值單元.對(duì)于大于 8 px × 8 px PU的插值，可通過(guò)多次復(fù)用8 px × 8 px PU插值單元實(shí)現(xiàn).以16 px × 8 px大小PU為例，可劃分為兩個(gè)8 px × 8 pxPU塊進(jìn)行插值.

以行輸入一次可以插值8個(gè)像素的分像素插值濾波處理器如圖2所示.將分像素插值過(guò)程分解為水平方向插值和豎直方向插值，實(shí)現(xiàn)的濾波模塊由8個(gè)8抽頭的水平方向?yàn)V波器hf0～hf7、8個(gè)8抽頭的豎直方向?yàn)V波器vf0～vf7組成，中間用了8 ×8個(gè)寄存器作緩沖.為插值8 px × 8 px PU，需要在左邊和上邊多讀入3個(gè)參考像素，右邊和下邊多讀入4個(gè)參考像素，即共讀入15×15個(gè)參考像素.這些參考像素將在每個(gè)時(shí)鐘周期以行為單位輸入分像素插值濾波處理器.其中水平濾波器hf0將讀入Y0～Y7共8個(gè)參考像素，hf1讀入Y1～Y8，…，hf7讀入Y7～Y14.在讀入對(duì)應(yīng)的參考像素后水平濾波器將通過(guò)選擇器選擇某1個(gè)分像素位置塊進(jìn)行濾波，分像素位置的控制信息來(lái)自于上層模塊.每個(gè)時(shí)鐘周期所有水平濾波器共產(chǎn)生8×1個(gè)分像素并存入中間的寄存器組，寄存器組整體向下移一個(gè)單元.8個(gè)時(shí)鐘周期后所有寄存器都被填滿，豎直濾波器讀入寄存器中的分像素并開(kāi)始工作.豎直濾波器計(jì)算過(guò)程需2個(gè)時(shí)鐘周期，流水操作除第1個(gè)時(shí)鐘周期外，每列每1個(gè)時(shí)鐘都可以完成1組數(shù)據(jù)計(jì)算.在豎直分像素計(jì)算的同時(shí)，水平分像素依舊每個(gè)時(shí)鐘周期更新一行.在輸出最終結(jié)果前，水平分像素和豎直分像素會(huì)通過(guò)選擇器進(jìn)行篩選，插值過(guò)程結(jié)束將得到8×8的分像素.因此，本方案有9個(gè)時(shí)鐘周期處于等待狀態(tài).在此之后，如果參考像素持續(xù)不斷地輸入，每17個(gè)時(shí)鐘周期將計(jì)算192個(gè)分像素，吞吐率可以達(dá)到11.3 px/時(shí)鐘周期.

圖2 按行流水插值架構(gòu)Fig.2 Pipeline architecture for interpolation by row

2 基于Wallace樹(shù)壓縮算法的分像素插值單元

2.1 Wallace樹(shù)壓縮器

Wallace樹(shù)壓縮算法的提出最初是服務(wù)于乘法器的部分積計(jì)算的，基本的思想是采用樹(shù)形結(jié)構(gòu)減少累加進(jìn)位的傳遞，充分利用諸如全加器3-2壓縮的特性，隨時(shí)將可利用的所有輸入和中間結(jié)果及時(shí)并行計(jì)算,大大減少了計(jì)算延時(shí)[9].

本設(shè)計(jì)考慮了多種壓縮器結(jié)構(gòu)，權(quán)衡了壓縮級(jí)數(shù)與硬件資源的關(guān)系，使用3-2壓縮器,4-2壓縮器,7-2壓縮器[10].

2.1.13-2壓縮器

圖3 3-2壓縮器Fig.3 3-2 compressor

圖4 k位數(shù)進(jìn)行3-2壓縮的過(guò)程Fig.4 The process of 3-2 compression of k bits

3-2壓縮器的核心單元是全加器[11].3-2壓縮器的功能是將3個(gè)1位輸入d0、d1、d2壓縮成2個(gè)1位的sum和carry，其功能示意圖如圖3所示.如果用邏輯表達(dá)式可以表示為

sum=d0⊕d1⊕d2

(1)

carry=d0·d1+d1·d2+d0·d2

(2)

對(duì)于k位(k=2,3,4,…)的3個(gè)數(shù)相加，則使用k個(gè)3-2壓縮器并行處理，如圖4所示，方格里的序號(hào)表示對(duì)應(yīng)數(shù)據(jù)用二進(jìn)制表示時(shí)的各個(gè)位.3個(gè)數(shù)相同權(quán)重的位用一個(gè)3-2壓縮器壓縮得到各個(gè)的{carry,sum}，記為Cn與Sn(n=0～k-1)，則可構(gòu)成2個(gè)新的數(shù)S與C，C的權(quán)重比S大一倍，為了方便最后兩數(shù)相加，C最低位補(bǔ)0，S最高位補(bǔ)0，各形成k+1位的數(shù).

2.1.24-2壓縮器

4-2壓縮器可用兩個(gè)3-2壓縮器組成，4-2壓縮器的示意圖如圖5所示.因?yàn)?個(gè)1位數(shù)相加結(jié)果最大為4，二進(jìn)制表示為3’b100，占據(jù)了3位，需要傳遞進(jìn)位，否則無(wú)法滿足最后只有兩個(gè)數(shù)相加的規(guī)則.

從圖5中可以看出，向高位的進(jìn)位Cout與結(jié)果中的carry權(quán)重是一樣的，sum的權(quán)重則低于carry一級(jí),與1位輸入d0～d3以及低位的進(jìn)位Cin是同一級(jí).

2.1.37-2壓縮器

7-2壓縮器是文[10]里提出的，由5個(gè)3-2壓縮器組成，如圖6所示.其中:d0～d6表示外部的7個(gè)1位輸入;Cin1和Cin0分別表示來(lái)自鄰近低位和次低位的進(jìn)位;Cout0和Cout1分別為權(quán)重高于sum 1位和2位的進(jìn)位;Sn和Cn(n=0,1,2)表示不同3-2壓縮器壓縮后的sum和carry.文[10]相比同類(lèi)型其他Wallace樹(shù)結(jié)構(gòu)組成的壓縮器，具有3%的速度優(yōu)勢(shì)[12]，有利于減少分像素插值過(guò)程中的延時(shí).

圖5 4-2壓縮器Fig.5 4-2 compressor

圖6 7-2壓縮器Fig.6 7-2compressor

2.2 使用壓縮器進(jìn)行插值單元設(shè)計(jì)

2.2.1濾波系數(shù)優(yōu)化

表1 HEVC亮度插值濾波系數(shù)

HEVC亮度插值的濾波系數(shù)如表1所示.不難看出1/4、3/4分像素位置的濾波系數(shù)互為逆序關(guān)系，故它們的硬件結(jié)構(gòu)可以復(fù)用.

本研究的濾波處理分成水平方向?yàn)V波和豎直方向?yàn)V波兩步.由于計(jì)算1個(gè)豎直分像素前需要至少緩存8個(gè)水平分像素，且同一次豎直濾波過(guò)程中，計(jì)算同一列的3個(gè)分像素依賴的水平分像素是相同的，為兼顧系統(tǒng)吞吐率與硬件面積的平衡，對(duì)于水平方向?yàn)V波將使用選擇器選擇濾波1個(gè)分像素位置的像素，豎直方向?yàn)V波則同時(shí)輸出3個(gè)分像素位置的像素.

對(duì)于濾波系數(shù)的處理，為避免使用乘法器產(chǎn)生高延時(shí)，將乘法計(jì)算轉(zhuǎn)換成移位和加法操作.以A～H表示輸入的8個(gè)整像素，首先考慮水平方向?yàn)V波系數(shù)的拆分，因?yàn)橛?jì)算1/4和3/4分像素值的硬件電路可以復(fù)用，下面僅考慮1/4和1/2濾波系數(shù)的拆分：

F1/4=-A+4B-10C+58D+17E-5F+G

=-A+4B-(8+2)C+(32+8)D-F+(16+2)D+(16+1)E-4F+G

(3)

F1/2=-A+4B-11C+40D+40E-11F+4G-H

=-A+4B-(8+2)C+(32+8)D-F-C-(8+2)F+(32+8)E+4G-H

(4)

提取式(3)和式(4)公有子式

T=-A+4B-(8+2)C+(32+8)D-F

(5)

則式(3)、式(4)可變形為

F1/4=T+(16+2)D+(16+1)E-4F+G

(6)

F1/2=T-C-(8+2)F+(32+8)E+4G-H

(7)

非公有子式可以通過(guò)選擇器進(jìn)行處理，達(dá)到共用加法器的目的，如式(6)的(16+1)E可以與式(7)的(32+8)E通過(guò)選擇器共用1個(gè)加法器.

豎直方向?yàn)V波系數(shù)的拆分思路與水平方向類(lèi)似.

F1/4=-A+4B-10C+58D+17E-5F+G

=-A+4B-(8+2)C+(32+8)D-F-4F+(16+1)E+G+(16+2)D

(8)

F1/2=-A+4B-11C+40D+40E-11F+4G-H

=-A+4B-(8+2)C+(32+8)D-F-(8+2)F+(32+8)E+4G-H-C

(9)

F3/4=B-5C+17D+58E-10F+4G-H

=B-4C+(16+1)D+(16+2)E-(8+2)F+(32+8)E+4G-H-C

(10)

為了充分利用前文幾種壓縮器的壓縮特性，對(duì)式(8)～式(10)做如下處理：

提取式(8)和式(9)公有子式

V12=-A+4B-(8+2)C+(32+8)D-F

(11)

提取式(9)和式(10)公有子式

V23=-(8+2)F+(32+8)E+4G-H-C

(12)

將式(8)～式(10)變形為

F1/4=V12-4F+(16+1)E+G+(16+2)D

(13)

F1/2=V23+V12

(14)

F3/4=V23+B-4C+(16+1)D+(16+2)E

(15)

對(duì)于負(fù)數(shù)項(xiàng)的運(yùn)算需要使用補(bǔ)碼.一個(gè)負(fù)數(shù)的補(bǔ)碼等于它的反碼加1，如果加1操作緊隨取反操作，將增加濾波項(xiàng)生成的延時(shí)，故將所有加1操作統(tǒng)一相加成1項(xiàng)，和其他濾波項(xiàng)共同加入到壓縮器的輸入端.

2.2.2Wallace樹(shù)壓縮算法插值濾波單元

采用Wallace樹(shù)壓縮算法進(jìn)行設(shè)計(jì)的插值濾波單元U1和U2如圖7所示.其中U1是水平方向?yàn)V波器3種分像素的計(jì)算單元以及豎直方向?yàn)V波器1/2分像素的計(jì)算單元；U2是豎直方向?yàn)V波器1/4和3/4像素的計(jì)算單元.U2單元的“取反加1之和”部分包含在了7-2壓縮器輸入的7項(xiàng)之中.兩種單元都只在最后一級(jí)使用到一個(gè)加法器.

圖7 Wallace樹(shù)壓縮算法插值濾波單元Fig.7 Interpolation filter unit based on Wallace tree

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

表2 本研究實(shí)驗(yàn)結(jié)果與其他文獻(xiàn)對(duì)比

本設(shè)計(jì)使用Verilog HDL語(yǔ)言描述，功能仿真在Modelsim 完成.通過(guò)Matlab調(diào)用HM 16.7代碼編譯后的可執(zhí)行程序，打印出分像素插值模塊的輸入輸出數(shù)據(jù)，將輸入數(shù)據(jù)送入待測(cè)模塊，查看其輸出是否與事先打印的輸出數(shù)據(jù)一致即可驗(yàn)證模塊功能是否正確.經(jīng)過(guò)多個(gè)序列的測(cè)試，本設(shè)計(jì)的電路功能正確.

將本算法對(duì)應(yīng)的硬件設(shè)計(jì)綜合情況與其他同類(lèi)型文獻(xiàn)進(jìn)行對(duì)比，結(jié)果如表2所示.為更好地說(shuō)明本算法的優(yōu)勢(shì)，使用Verilog HDL語(yǔ)言編寫(xiě)了與本架構(gòu)完全一致的加法器版本作為對(duì)照組.兩個(gè)版本的設(shè)計(jì)均使用SAED 32nm的標(biāo)準(zhǔn)單元庫(kù)在Synopsys Design Compiler平臺(tái)完成綜合.

由表2可知，與文[4]相比，本設(shè)計(jì)吞吐率為其2.65倍，同時(shí)邏輯門(mén)數(shù)減少66.6%；本設(shè)計(jì)吞吐率與文[8]相當(dāng)，但邏輯門(mén)數(shù)比文[8]減少11.4%；與作為對(duì)照組的加法器版本相比，本設(shè)計(jì)最高工作頻率提高40.1%，邏輯門(mén)數(shù)減少29.1%.

由此可見(jiàn)，本設(shè)計(jì)可在硬件面積更小的情況下達(dá)到更高的工作頻率，這一點(diǎn)在與對(duì)照組的對(duì)比過(guò)程中尤為明顯.加法器版本如果要達(dá)到更低的延時(shí)，電路結(jié)構(gòu)會(huì)從以串行進(jìn)位加法器等為代表的面積小但延時(shí)大的加法器轉(zhuǎn)變成以超前進(jìn)位加法器等為代表的延時(shí)小但面積大的加法器，而Wallace樹(shù)壓縮器由于并行程度高于串行進(jìn)位加法器并且只在最后一級(jí)使用了加法器，故可以用更小的硬件面積達(dá)到更高的工作頻率.

4 結(jié)語(yǔ)

提出基于Wallace樹(shù)優(yōu)化的HEVC分像素插值濾波算法的實(shí)現(xiàn)方案，不僅提高了模塊可工作的最高頻率，還有效減少了硬件面積.同時(shí)由于采用了按行流水插值架構(gòu)，將插值過(guò)程分解為水平方向和豎直方向插值，使模塊維持了較高的吞吐率.

本方案的分像素插值模塊以8 px × 8 px大小PU為最小插值單元，使用Verilog HDL語(yǔ)言進(jìn)行描述，在Modelsim上通過(guò)功能仿真驗(yàn)證，并在Synopsys Design Compiler上使用SAED 32 nm標(biāo)準(zhǔn)單元庫(kù)進(jìn)行綜合，綜合后模塊的最高工作頻率為636.9 MHz，邏輯門(mén)數(shù)為32 960，吞吐率為11.3 px/時(shí)鐘周期，在同樣采用按行流水插值架構(gòu)的文獻(xiàn)中具有明顯的優(yōu)勢(shì).