陳清坤,施隆照,黃 博,高小虹

(福州大學物理與信息工程學院,福建 福州 350116)

0 引言

視頻編碼技術(shù)廣泛應用于視頻會議、安防監(jiān)控和遠程醫(yī)療等領域. 隨著視頻分辨率的提高,視頻編碼標準H.264的壓縮效率已經(jīng)無法滿足需求. 新一代視頻編碼標準HEVC通過引入一系列新技術(shù),在H.264基礎上提高了一倍的壓縮效率,但也造成較高的復雜度[1]. 在視頻編碼過程中,運動估計也是最具挑戰(zhàn)和編碼時間最高的部分. 在和運動估計相關(guān)的運算中,HEVC與上一代壓縮標準H.264相比增加更靈活的特征,包括高級運動矢量預測技術(shù)AMVP(advanced motion vector prediction),更多不同尺寸預測單元PU (prediction unit)，以及更大的PU等[2]. 這些新特征提高了運動估計編碼效率,但也增加了運動估計復雜度. 同時,由于AMVP和更大的PU的出現(xiàn),編碼器硬件需要更大的內(nèi)存空間. 因此,針對硬件實現(xiàn)設計快速算法降低運動估計過程的復雜度,用硬件加速運動估計過程是非常有必要的.

目前已有的HEVC運動估計算法優(yōu)化思想可分為三類: 一是基于HEVC參考軟件中提供的TZ(test zone search)快速搜索的優(yōu)化算法,例如, 文[3]用旋轉(zhuǎn)六邊形搜索模板替代鉆石搜索模板,文[4]用三種不同模板替換細化搜索的模板,文[5]優(yōu)化了起始搜索過程,這些文獻都是通過減少搜索點數(shù),降低TZ搜索的復雜度,但優(yōu)化后的搜索策略仍然過于復雜,并沒考慮硬件實現(xiàn)的難易程度； 二是基于經(jīng)典運動估計快速搜索的改進算法,例如, 文[6]是基于傳統(tǒng)六邊形搜索的快速搜索算法,文[7]在傳統(tǒng)鉆石搜索的基礎上提出的star diamond搜索算法,盡管這些文獻都能有效減少運動估計時間,但并未考慮HEVC引入更大預測單元,不同塊大小的迭代搜索復雜度差異較大,不利于硬件電路設計等問題； 三是新提出的綜合優(yōu)化快速搜索算法,例如, 文[8-10]使用運動矢量預測、自適應搜索模板和提前終止等多種技術(shù)減少運動估計復雜度,而都保持性能基本不損失,但不確定的搜索路徑、不規(guī)則的數(shù)據(jù)讀取和不適合并行處理都無法發(fā)揮硬件的優(yōu)點. 因此,已有HEVC運動估計算法多基于軟件平臺考慮,仍不適合硬件實現(xiàn).

目前已有的運動估計硬件架構(gòu)的設計思路主要有兩種. 一種是基于全搜索算法的硬件架構(gòu),例如, 文[11]通過分層全搜索架構(gòu)來減少復雜度和片內(nèi)帶寬,文[12]提出的架構(gòu)能有效提高吞吐率,但這些文獻優(yōu)化后的架構(gòu)仍然需要很長的處理時鐘周期. 另一種是基于快速搜索算法的硬件架構(gòu),例如, 文[13-15]提出的架構(gòu)都能夠用較少的時鐘數(shù)完成運動估計,但仍然存在很多不足. 其中, 文[13]過高的并行度和較低的數(shù)據(jù)復用,造成很高的片內(nèi)存儲器訪問； 文[14]提出的架構(gòu)最大只支持16 px×16 px的預測單元,無法支持HEVC最大64 px×64 px的預測單元; 文[15]需要頻繁讀取參考像素,造成了較大的片外存儲器帶寬,同時增大了硬件功耗. 因此,現(xiàn)有的架構(gòu)仍無法滿足HEVC中運動估計的要求.

針對上述討論,本研究提出確定共享搜索區(qū)域的方法,硬件中使用較大的共享搜索區(qū)域,提高數(shù)據(jù)復用率,減少頻繁數(shù)據(jù)訪問和龐大的數(shù)據(jù)讀取對帶寬的壓力. 進而,在傳統(tǒng)鉆石搜索算法的基礎上,提出面向HEVC且適合于硬件實現(xiàn)的改進的鉆石搜索算法,同時算法性能損失基本可以忽略. 最后,提出改進的鉆石搜索算法的硬件架構(gòu),通過減少數(shù)據(jù)讀取時間、提高硬件資源利用率以及采用并行處理的方式加速運動估計過程,使周期數(shù)比現(xiàn)有文[14-15]更少.

1 共享搜索區(qū)域的確定

在硬件設計中,參考幀緩存需要較大的存儲空間,所以一般存儲在外部的大容量DRAM中. 在運動估計過程中,所需要的搜索區(qū)域像素需要提前緩存到片內(nèi)的SRAM中. 不同預測塊的搜索起始點隨著預測矢量dmvp的改變而變化,每一塊的搜索區(qū)域并不相同. 頻繁的數(shù)據(jù)訪問將造成巨大的片外參考像素帶寬,更嚴重增加了硬件系統(tǒng)功耗. 為提高數(shù)據(jù)復用和減少片外參考像素帶寬,硬件實現(xiàn)時可以用較大的SRAM存儲更大的搜索區(qū)域,使CTU(coding tree unit)中不同PU能夠復用該區(qū)域,實現(xiàn)搜索區(qū)域的共享[16]. 但實現(xiàn)共享搜索區(qū)域需要限制PU的搜索范圍,從而可能會造成編碼性能的降低,因此需要合理設計確定共享搜索區(qū)域的大小和位置.

本共享搜索區(qū)域方案是利用空間域相鄰塊運動矢量的相關(guān)性預測當前CTU內(nèi)像素整體的運動趨勢. 假設以當前CTU為中心,搜索區(qū)域上下左右偏移范圍各為Npx,同時CTU大小為Mpx. 在寬度為(2×N+M) px的正方形搜索區(qū)域基礎上,將中心點相對CTU偏移dmv_CTUpx,其中dmv_CTU由鄰塊A、B、C、D和E運動矢量(如圖1所示)的中值確定. 利用空間域相鄰塊運動矢量的相關(guān)性預測當前CTU內(nèi)像素整體的運動趨勢,通過共享搜索區(qū)域的整體偏移,減小視頻內(nèi)容對N的影響. 共享搜索區(qū)域的大小需要根據(jù)統(tǒng)計分析確定N. 實驗統(tǒng)計在編碼過程中,不同N時PU的運動矢量dmv在共享搜索區(qū)域內(nèi)的頻率. 實驗結(jié)果如圖2所示,N從0到100 px增加的過程中,dmv在共享搜索區(qū)域內(nèi)的頻率不斷增加. 當N大于64 px時,不同視頻內(nèi)dmv在共享搜索區(qū)域內(nèi)的頻率都超過98%. 綜合考慮性能增益和硬件資源消耗,將N、M均設為64 px,此時,共享搜索區(qū)域為寬度192 px的正方形搜索區(qū)域.

圖1 CTU鄰塊Fig.1 CTU adjacent block

圖2 dmv在共享搜索區(qū)域內(nèi)的頻率分布Fig.2 Frequency distribution of dmv in region

2 改進的鉆石搜索算法

鉆石搜索算法是經(jīng)典的快速搜索算法,采用先大鉆石搜索后小鉆石搜索的搜索策略,可以減少搜索點數(shù),降低運動估計復雜度. 但由于HEVC使用更大的預測單元,大鉆石搜索在迭代過程中,每次迭代大尺寸(64 px×64 px) PU的復雜度會遠大于小尺寸(8 px×4 px) PU. 其次,沒有限制的迭代次數(shù)是不適合于硬件時序安排的. 因此,在傳統(tǒng)鉆石搜索算法的基礎上,提出改進的鉆石搜索算法.

搜索模板對算法的復雜度和硬件實現(xiàn)都有關(guān)鍵性影響. 在硬件實現(xiàn)中,往往采用并行的方式實現(xiàn)運動估計,因此處理運動估計的處理單元(PE)是給定的. 針對這個特點,大塊的CU(coding unit)使用小鉆石搜索模板,小塊CU采用米字型搜索模板,如圖3和圖4所示. 首先,CU為64 px×64 px、32 px×32 px和16 px×16 px時,PU尺寸較大,單次絕對誤差和SAD(sum of absolute difference)計算復雜度較高. 因此,選用5點小鉆石搜索模板. 當CU為8 px×8 px時使用9點的米字型搜索模板,SAD計算復雜度低, 通過增加搜索點數(shù)減少迭代次數(shù). 其次,通過自適應模板選擇,平衡不同塊大小搜索迭代過程的復雜度,便于硬件電路兼顧處理速度和高硬件資源利用率. 再者,由于兩種模板上下左右偏移一個像素,對于npx×mpx的PU,兩種搜索模板需要讀取的有效參考像素均為(1+n+1)×(1+m+1)px. 兩種模板有相同的有效數(shù)據(jù)量和很高的數(shù)據(jù)復用率,因此能進一步簡化硬件中數(shù)據(jù)預讀取過程和減少片內(nèi)參考像素帶寬.

圖3 小鉆石搜索Fig.3 Small diamond search

圖4 米字型搜索Fig.4 Meter-shaped search

圖6 算法流程圖Fig.6 Flow chart of algorithm

本文算法的搜索過程. 選擇以AMVP技術(shù)得到的dmvp作為搜索起始點. AMVP技術(shù)能使起始點更接近于全局最優(yōu)點,從而能減少搜索的點數(shù)和避免陷入局部最優(yōu)對性能的影響[1]. 為使dmvp落在共享搜索區(qū)域內(nèi),需要對dmvp預處理. 在迭代過程中,使用式(1)為搜索模板的各個點估計率失真代價選擇最優(yōu)的搜索點. 當代價最小點出現(xiàn)的位置在每次迭代中搜索模板的中心點或者搜索區(qū)域邊界時結(jié)束搜索. 同時,由于普通圖像不同塊之間的運動具有相關(guān)性,分析運動矢量差值dmvd,設置了最大迭代次數(shù),避免不必要的迭代過程. 實驗統(tǒng)計編碼過程中f(x, |dmvd|≤x)的頻率分布情況. 實驗結(jié)果如圖5所示,隨著x的增加,f(x, |dmvd|≤x)的頻率先迅速增加,后增速變緩. 綜合考慮復雜度和f(x, |dmvd|≤x)的頻率的分布情況,因此將最大迭代次數(shù)設置為64次.

J=SAD(dmv)+λ=motionR(dmv-dmvp)

(1)

圖5 f (x, |dmvd|≤x)的頻率分布Fig.5 f (x, |dmvd|≤x) frequency distribution

改進的鉆石搜索算法根據(jù)預測單元大小自適應選擇米字型搜索模板和小鉆石搜索模板,使用了共享搜索區(qū)域,設置最大迭代次數(shù),具體搜索過程如下,算法流程如圖6所示.

1) 初始化vbest_mv、Jbest和Citeration.

2) 根據(jù)CU大小選擇搜索模板,分別估計模板各點率失真代價. 當CU為8 px×8 px時使用米字型搜索模板,當CU為64 px×64 px、32 px×32 px和16 px×16 px時使用小鉆石搜索模板.

3) 迭代判決. 根據(jù)代價最小值所在的位置、最優(yōu)塊是否在搜索區(qū)域邊界和Citeration判斷是否結(jié)束搜索.

3 改進的鉆石搜索算法仿真和性能分析

表1 比較編碼性能

以HEVC參考軟件HM16.7作為實驗測試平臺,采用BD-rate[17]來評估算法性能. 為驗證算法的魯棒性,視頻序列包括了不同的分辨率和運動情況的公共測試視頻序列[18]. 量化參數(shù)選擇22,27,32和37,視頻編碼100幀,配置文件選擇lowdelay_P. 實驗結(jié)果如表1所示,在PartyScene和KristenAndSara等運動緩慢的視頻序列中,編碼性能基本與原始HM16.7性能一致. 本算法相比原始HM16.7平均BD-rate(Y)僅僅增加0.5%. 對于最壞的情況下,在RaceHorses (832 px×480 px)視頻內(nèi)物體運動劇烈,由于共享搜索區(qū)域?qū)λ阉鲄^(qū)域的限制會影響性能,但相比原始HM16.7,BD-rate(Y)僅增加1.2%. 因此,證明本編碼器性能基本不損失, 但本算法更適合于硬件實現(xiàn).

為進一步證明本算法性能的有效性,將本算法與文[6]做比較. 與文[6]的編碼性能對比如表1所示. 文[6]相比原始編碼器平均BD-rate(Y)增加1.2%,平均性能損失高于本算法. 且在不同視頻序列中,本算法編碼性能都能優(yōu)于文[6]. 因此,證明本編碼器性能的有效 性.

4 改進的鉆石搜索算法的硬件架構(gòu)

傳統(tǒng)鉆石搜索常采用9個PE的硬件架構(gòu)[14]. 首先,該架構(gòu)每個PE處理1個搜索點的SAD,對于大鉆石搜索9個點,但對小鉆石搜索5個點時,此時有4個PE處于空閑狀態(tài). 其次,該架構(gòu)主要針對最大預測單元為16 px×16 px,無法支持預測單元64 px×64 px. 另外,該架構(gòu)需要頻繁的數(shù)據(jù)預讀取,對帶寬、功耗和運動估計效率都是不利的.

4.1 新的硬件架構(gòu)

在傳統(tǒng)鉆石搜索硬件架構(gòu)的基礎上,針對本算法進一步提出新的硬件架構(gòu),如圖7所示. 主要包括控制模塊、初始化PU模塊、地址生成模塊、參考像素RAM、原始像素RAM、參考像素預處理模塊、原始像素預處理模塊、多個PE模塊、計算運動矢量差值代價模塊、運動矢量生成模塊、比較模塊和迭代判決模塊.

圖7 硬件架構(gòu)Fig.7 Hardware architecture

新硬件架構(gòu)采用10個PE. 根據(jù)PU的尺寸大小,既可以每個PE單獨處理一個搜索點的SAD,又可以2個PE組合成更大的處理單元計算一個搜索點SAD. 使用米字型模板搜索時,每個PE處理1個搜索點,此時只有PEC1模塊是空閑的. 使用小鉆石搜索模板時,PEU和PEUL、PEB和PEBR、PEL和PEBL、PER和PEUR、PEC0和PEC1分別組成更大的處理單元,分別計算5個搜索點的SAD,此時所有的PE都處于工作狀態(tài).

處理單元PE模塊是核心計算模塊,綜合考慮處理能力、利用率和片內(nèi)存儲架構(gòu),PE選擇用加法樹完成8 px (寬度)×4 px (高度) SAD累加.在CU為8 px×8 px中,當PU寬度為4時,PE只有50%的資源利用率. 但當PU寬度不為4時,PE有100%的資源利用率. 同時為了能夠?qū)崿F(xiàn)所有2Npx×2Npx,2Npx×Npx和Npx×2Npx形式PU的復用,8 px×4 px SAD計算結(jié)果還需要累加才能得到更大尺寸PU的SAD. 另外,對于CU大小大于8 px×8 px,可以通過組合兩個PE為更大16 px×4 px SAD的處理單元. 因連續(xù)的行讀取比較方便,這樣只要讀取4行的數(shù)據(jù)就可以了. 這種靈活的處理方式,使PE在處理從8 px×8 px到64 px×64 px的PU時,都有較高的處理效率,PE模塊結(jié)構(gòu)如圖8所示.

對于其它的模塊,設計思路如下：

① 控制模塊使用狀態(tài)機控制狀態(tài)轉(zhuǎn)換； ② 初始化PU模塊根據(jù)CTU和CU信息計算當前PU寬度、高度和位置等信息； ③ 參考像素RAM存儲192 px×192 px； ④ 原始像素RAM需要存儲64 px×64 px； ⑤ 地址生成模塊產(chǎn)生參考像素RAM和原始像素RAM的地址信號； ⑥ 參考像素預處理模塊和原始像素預處理模塊,為每個PE單元選擇對應的參考塊像素和當前塊像素； ⑦ 比較模塊用于確定代價最小值所在的位置; ⑧ 迭代判決模塊判斷是否需要繼續(xù)迭代; ⑨ 計算運動矢量差值代價模塊計算各個搜索點的dmvd代價.

4.2 時序安排

整個運動估計時序安排包括初始化、SAD計算和迭代判決. 圖7硬件架構(gòu)中,初始化過程需要3個時鐘周期,用于計算搜索起始點和初始化PU的相關(guān)信息. 另外,每個CTU需要額外48個時鐘更新參考像素RAM和原始像素RAM內(nèi)數(shù)據(jù).

SAD計算時間取決于PU塊大小. 本架構(gòu)使用8 px×4 px SAD和16 px×4 px SAD作為基本處理單元,8級全流水實現(xiàn)PE數(shù)據(jù)獲取到SAD的計算. 當PU為8 px×4 px和16 px×4 px時,SAD計算都只需要8個時鐘周期. 當PU為64 px×64 px時,基本處理單元選擇16 px×4 px SAD,需要8+(4×16)-1=71個周期完成SAD計算. PU越大,SAD計算時間越長. 在計算SAD的同時,還并行計算搜索點dmvd的代價.

表2 迭代次數(shù)

迭代判決需要7個周期. 首先SAD與dmvd代價求和得到總的代價,然后需要3個周期比較代價最小值所在的位置,最后還需要3個周期判斷是否繼續(xù)迭代. 完整運動估計的周期還和迭代次數(shù)有關(guān),迭代次數(shù)越多,周期越長. 實驗統(tǒng)計搜索迭代次數(shù)I和迭代次數(shù)小于等于3的頻率P,統(tǒng)計結(jié)果如表2所示.

平均迭代次數(shù)只要2.248 3次,迭代次數(shù)小于等于3的頻率達到了86.33%,即對于大部分PU最多3次迭代就能找到最優(yōu)匹配塊. 迭代次數(shù)以3為例,不同尺寸PU的運動估計周期數(shù)如表3所示.

表3 不同尺寸PU的周期數(shù)

5 改進的鉆石搜索算法的硬件架構(gòu)綜合結(jié)果

以Synopsys VCS工具驗證功能的正確性,運用FPGA器件(Stratix IV系列中EP4S40G2F40I1芯片)在QUARTUS II開發(fā)平臺中完成綜合. 綜合結(jié)果表明,僅需要17 622個ALUTs,14 122個registers,memory 425.984 kbits,4個DSP(18 bit)的硬件資源,最高工作頻率達到317.56 MHz.

編碼實時性分析. 如果只考慮對稱劃分模式,且只有單一參考幀,處理一個64 px×64 px CTU需要26 523個時鐘周期. 1 080 px分辨率視頻圖像一幀需要13.4 M個時鐘周期. 720 px分辨率視頻圖像一幀需要6.0 M個時鐘周期. 本架構(gòu)能實現(xiàn)1 080 px @23.7幀·s-1或者720 px @53.2 幀·s-1. 編碼性能如表1所示,相對HM性能基本沒有損失.

表4為本實驗結(jié)果與相關(guān)文獻比較情況,文獻[14-15]都是在鉆石搜索算法基礎上提出的改進算法和硬件架構(gòu),但只處理16 px×16 px的PU塊,因此比較了PU為16 px×16 px的時鐘數(shù).

表4 與不同文獻硬件架構(gòu)比較

文[14]運動估計每次只要170個時鐘周期,因為合理安排時序,將大部分的預讀取時間隱藏在流水線中,但仍然有20個周期是用來等待預讀取數(shù)據(jù)結(jié)束. 并且該架構(gòu)只能支持固定16 px×16 px的PU尺寸. 本架構(gòu)通過共享搜索區(qū)域,不需要頻繁預讀取像素,僅需要66個周期,就能完成16 px×16 px塊的預測,且能夠支持所有對稱劃分模式.

文[15]搜索區(qū)域為96 px×96 px,對固定16 px×16 px的PU進行4∶1的下采樣,減少硬件資源和復雜度,存儲資源僅僅用46 kbits. 而本研究最大支持64 px×64 px的PU,共享搜索區(qū)域為192 px×192 px,更大的PU和更大的搜索范圍,因此需要較大的存儲資源. 而本研究邏輯資源略低于文[15],能夠用更少的時鐘周期完成運動估計,且本架構(gòu)有更高的主頻.

6 結(jié)語

1) 提出一種結(jié)合算法和硬件實現(xiàn)的優(yōu)化運動估計方法. 該方法根據(jù)硬件資源消耗和預測單元大小自適應地選擇搜索模板,通過硬件搜索區(qū)域共享實現(xiàn)有效數(shù)據(jù)復用,并減少參考像素帶寬.

2) 基于該自適應搜索算法,進一步提出新的硬件架構(gòu). 新硬件架構(gòu)采用10個處理單元的架構(gòu),PE既可以作為獨立的處理單元計算一個搜索點的SAD,又能夠?qū)?個PE組合成更大處理單元. 通過靈活處理單元的選擇,對從8 px×8 px到64 px×64 px不同尺寸的PU,該架構(gòu)都有較高的處理速度和資源利用率.

3) 仿真結(jié)果表明,本算法與參考代碼HM16.7相比較,編碼性能基本不損失,但更適合于硬件實現(xiàn). 用Altera的 Stratix IV系列芯片在QUARTUS II里邏輯綜合, 得到的最大工作頻率為317.56 MHz,能夠?qū)崿F(xiàn)1 080 px @23.7幀·s-1的吞吐率.