羅 隆，施隆照，洪曉劍，嚴丹鈺

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

0 引言

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

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

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

1 系統(tǒng)概述

1.1 分像素搜索過程

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

分像素搜索的示意圖如圖1所示，圖中標識了其中的9個整像素點，8個1/2像素點以及8個1/4像素點.

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

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

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

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

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

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

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

2.1 Wallace樹壓縮器

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

本設(shè)計考慮了多種壓縮器結(jié)構(gòu)，權(quán)衡了壓縮級數(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ù)進行3-2壓縮的過程Fig.4 The process of 3-2 compression of k bits

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

sum=d0⊕d1⊕d2

(1)

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

(2)

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

2.1.24-2壓縮器

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

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

2.1.37-2壓縮器

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

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

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

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

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

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

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

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

對于濾波系數(shù)的處理，為避免使用乘法器產(chǎn)生高延時，將乘法計算轉(zhuǎn)換成移位和加法操作.以A～H表示輸入的8個整像素，首先考慮水平方向濾波系數(shù)的拆分，因為計算1/4和3/4分像素值的硬件電路可以復用，下面僅考慮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)

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

豎直方向濾波系數(shù)的拆分思路與水平方向類似.

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)

為了充分利用前文幾種壓縮器的壓縮特性，對式(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)

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

2.2.2Wallace樹壓縮算法插值濾波單元

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

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

3 實驗結(jié)果

表2 本研究實驗結(jié)果與其他文獻對比

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

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

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

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

4 結(jié)語

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

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