基于HEVC六邊形運動估計算法的VLSI設(shè)計

閆博冉，何衛(wèi)鋒，毛志剛

(上海交通大學(xué) 微納電子學(xué)系,上海 200240)

基于HEVC六邊形運動估計算法的VLSI設(shè)計

閆博冉，何衛(wèi)鋒，毛志剛

(上海交通大學(xué) 微納電子學(xué)系,上海 200240)

運動估計是HEVC中計算量最大、耗時最多的模塊。為了加速編碼過程，設(shè)計了適用于HEVC運動估計的六邊形搜索算法的VLSI架構(gòu)。該架構(gòu)支持HEVC標(biāo)準(zhǔn)中的尺寸可變塊設(shè)計，并且充分考慮六邊形模板的數(shù)據(jù)復(fù)用特點，在PE陣列中使用流水線的組織策略，有效降低了片上緩存的訪問次數(shù)。采用SMIC 65 nm工藝綜合該電路，最高工作頻率可達(dá)100 MHz，電路規(guī)模101 k門，能夠滿足高清視頻(1 920×1 080,60幀/秒)的實時編碼要求。

HEVC; 運動估計；六邊形搜索；VLSI

與之前的視頻編碼標(biāo)準(zhǔn)相比，HEVC標(biāo)準(zhǔn)具有更高的編碼效率。靈活的塊分割結(jié)構(gòu)是HEVC提升編碼效率的重要技術(shù)之一。在HEVC中，最大編碼單元(LCU)尺寸為64×64，LCU會根據(jù)四叉樹結(jié)構(gòu)繼續(xù)劃分成編碼單元(CU)，CU的最小尺寸為8×8。與每個CU相關(guān)的有預(yù)測單元(PU)和變換單元(TU)[1-3]。

運動估計是HEVC編碼中最關(guān)鍵的模塊之一。參與運動估計的塊是預(yù)測單元(PU)，與之前的編碼標(biāo)準(zhǔn)中單一的預(yù)測單元尺寸相比，HEVC引入了共36種不同尺寸的預(yù)測單元，如圖1所示，其中N=8,16或32，最大尺寸為64×64，最小為4×8和8×4， AMP為不對稱劃分。編碼器可以根據(jù)視頻的內(nèi)容特性，對平滑的圖像區(qū)域采用較大尺寸的塊來進(jìn)行預(yù)測，以此提高壓縮率；對變化劇烈的圖像區(qū)域采用較小的塊來預(yù)測，以此來保證圖像細(xì)節(jié)[4]。

圖1 HEVC中預(yù)測單元的尺寸及劃分模式

在支持可變塊的快速運動估計算法的VLSI設(shè)計中，文獻(xiàn)[10～15]分別采用了菱形搜索算法和三步搜索算法，六邊形搜索算法的VLSI實現(xiàn)很少[6-8]。但是文獻(xiàn)[5]指出六邊形算法相對于其他快速算法，有以下3個顯著優(yōu)勢：(1)找到最優(yōu)匹配點需要的搜索步數(shù)更少；(2)六邊形模板更接近于圓形，不會漏掉圖像的某個運動方向；(3)模板步長較大，避免了陷入局部最優(yōu)?；谏鲜隹紤]，本文采用六邊形算法完成HEVC中運動估計的VLSI設(shè)計。

1 預(yù)測型六邊形算法分析

六邊形算法是一種基于塊匹配的快速運動估計算法，使用絕對誤差和(Sum of Absolute Difference, SAD)作為塊匹配的判斷準(zhǔn)則。假設(shè)塊的大小為M×N，Pi和Pi-1分別表示當(dāng)前塊和參考塊的像素值，(x,y)表示運動向量(Motion Vector, MV)的分量，SAD的定義如下

(1)

其中，SAD值最小點即為當(dāng)前塊的最優(yōu)匹配塊。

在快速搜索算法中，一般以3個相鄰塊的MV的平均值作為當(dāng)前塊的起始搜索點[9]，但是除以3在硬件中實現(xiàn)過于復(fù)雜。本文增加了圖2所示的左上方的MV4，除以4可以通過操作數(shù)右移2位實現(xiàn)。

圖2 預(yù)測起始搜索點示意圖

圖3給出了預(yù)測型六邊形算法的搜索示例，首先得到起始搜索點之后，以六邊形模板去搜索最優(yōu)匹配塊，如果最優(yōu)匹配塊出現(xiàn)在六邊形模板的中心處，則再搜索菱形的4個點，如圖3中的第5步，此時得到SAD值最小塊即為最終的匹配塊，對應(yīng)的MV為(-1,-3)。

圖3 六邊形搜索過程示意圖

搜索算法確定之后，需要確定搜索范圍。根據(jù)式(2)，參考幀片上緩存RAM的大小與搜索范圍成平方關(guān)系，所以需要在保證運動估計質(zhì)量的情況下，盡量減小搜索的范圍。

參考幀RAM容量=(搜索范圍×2+64)2

(2)

在HEVC的官方標(biāo)準(zhǔn)HM.15的仿真模型中，通過將搜索范圍設(shè)為[-64,64]來統(tǒng)計運動較為劇烈的高清視頻Basketball的MV的分布情況，結(jié)果95%的MV均分布在[-32,32]之內(nèi)，80%的MV分布在[-16,16]之內(nèi)，54%的MV分布在[-8,8]之內(nèi)，其他測試視頻得到的MV分布統(tǒng)計都是類似的。因此本文確定搜索范圍為[-32,32]。

2 六邊形算法的數(shù)據(jù)復(fù)用分析

圖4中每個網(wǎng)格線的交點代表1個像素點，0號～6號代表六邊形模板的搜索點，7號～10號代表菱形的搜索點。

圖4 六邊形搜索點編號

在對每一個不同大小的塊進(jìn)行六邊形搜索的過程中，SAD值的計算都是獨立的，所以根據(jù)所有塊尺寸的最小長度為4，最小寬度為4，確定每次計算當(dāng)前塊中大小為4×4的塊的SAD值，通過累加得到更大尺寸塊的SAD值。由于不同搜索點之間有參考像素的重疊，從參考幀緩存中讀出8行×8列像素即可得到4×4塊的11個搜索點的SAD值。

為了減少處理單元的個數(shù)，本文采用流水線的設(shè)計方法，每個周期讀入?yún)⒖級K像素共8行×1列，這樣經(jīng)過4個周期后可以得到0號位置的SAD值，第5個周期得到1號、2號和7號位置的SAD值，以此類推。當(dāng)計算到當(dāng)前4×4塊位于6號位置的SAD值時，此時處理單元(PE)中的參考塊恰好是右側(cè)相鄰4×4的塊的0號位置的參考塊，所以為了進(jìn)一步增加數(shù)據(jù)的復(fù)用率，同時不打亂PE陣列的流水線結(jié)構(gòu)，PE陣列中會寄存當(dāng)前塊中的2個左右相鄰的4×4塊，在第8個周期時，會同時計算第1個4×4塊在6號位置的SAD值和第2個4×4塊在0號位置的SAD值。從第9個周期開始，計算下一個4×4塊的SAD值。直至當(dāng)前塊中所有處于同一行的4×4塊的SAD值計算完成，然后開始計算下一行的4×4塊的SAD值。

下面以8×8塊的一次六邊形搜索為例，說明SAD值的計算過程。如圖5所示，8×8的塊可以分解為(0,0)，(1,0)，(0,1)，(1,1)共4個4×4的塊，整個8×8塊的參考像素個數(shù)為12×12。表1列出了整個8×8塊在1次六邊形搜索中的完整數(shù)據(jù)流。

圖5 8×8塊在1次六邊形搜索中所需要的參考像素

表1 8×8塊在1次六邊形搜索的完整數(shù)據(jù)流

通過上述流水線式的數(shù)據(jù)組織方式，可以不斷將新的1列參考幀像素讀入PE陣列中，每個周期都會得到新搜索點的SAD值，避免為了新的搜索點再次去緩存中讀取之前已經(jīng)讀過的數(shù)據(jù)。

3 六邊形運動估計算法的VLSI設(shè)計

本文提出的電路結(jié)構(gòu)如圖6所示，其中片外存儲器提供視頻信息的讀取接口。

圖6 運動估計整體VLSI結(jié)構(gòu)示意圖

該電路結(jié)構(gòu)與文獻(xiàn)[7]中的結(jié)構(gòu)相比，沒有采用并行的7個處理單元，而是采用同一個PE陣列流水線式完成所有搜索點的SAD值計算，有效降低了電路面積。另外，文獻(xiàn)[7]中的電路結(jié)構(gòu)在每次新一輪六邊形搜索時，都會讀取片外存儲器，這大幅增加了訪存的功耗，由于不同搜索點之間的參考幀像素是有重疊的，這樣會造成重復(fù)性訪問片外的同一數(shù)據(jù)，尤其是針對當(dāng)前幀中同一位置的不同尺寸塊均需要進(jìn)行六邊形搜索的情況，片外訪存的次數(shù)是難以接受的，因此本文的參考幀緩存采取將所需要的參考幀像素全部緩存到片上，減少對片外存儲器的訪問次數(shù)。

3.1 當(dāng)前幀和參考幀緩存

最大塊尺寸為64×64，因此當(dāng)前幀緩存為4KB。PE陣列要求當(dāng)前幀像素可以在一個周期內(nèi)更新4行×4列，設(shè)計當(dāng)前幀緩存器由4個獨立的單口RAM構(gòu)成，存儲策略為：第1個RAM存第1行、第5行、…、第61行，第2個RAM存第2行、第6行、…、第62行，以此類推，第4個RAM存第4行、第8行、…、第64行，如此可以讀出連續(xù)的4行像素。

根據(jù)搜索范圍為[-32,32]，得到所有參考像素共32+64+32=128行，緩存共16 kB。PE陣列的數(shù)據(jù)更新是每個周期讀8行×1列的參考像素，因此參考幀緩存器由8個獨立的單口RAM構(gòu)成，存儲策略為：第1個RAM存第1行、第9行、…、第121行，第2個RAM存第2行、第10行、…、第122行，以此類推，第8個RAM存第8行、第16行、…、第128行，如此可以讀出任意的連續(xù)8行。

3.2 PE陣列結(jié)構(gòu)

PE陣列大小為8×4，每個周期更新8行×1列的參考幀像素，即為圖7中PE0～PE7的參考像素，后續(xù)PE的參考像素來自前一級的PE。利用加法樹結(jié)構(gòu)，對PE中得到的像素差值進(jìn)行累加，依次得到1×4、 2×4的SAD值，然后組合得到搜索模板中0號～6號和7號～10號的4×4塊的SAD值。SAD值存儲在指定的寄存器中，由控制器狀態(tài)機標(biāo)識其更新、累加或保持原值。

圖7 PE陣列及SAD值運算示意圖

3.3 控制器設(shè)計

如圖8所示，主控制器接收到外部的幀開始信號，然后電路將當(dāng)前塊像素寫入當(dāng)前幀緩存，將參考像素寫入?yún)⒖紟彺?。?dāng)參考幀像素寫入完成后，電路開始對當(dāng)前塊不同尺寸的劃分塊逐個進(jìn)行六邊形搜索，找到每個塊在參考幀中的最優(yōu)匹配塊，并記錄最優(yōu)匹配塊的運動向量MV和SAD值。

圖8 狀態(tài)機切換示意圖

假設(shè)當(dāng)前塊的高為H，寬為W，根據(jù)第3部分的數(shù)據(jù)流分析，當(dāng)前塊進(jìn)行1次六邊形搜索需要的周期數(shù)為(W+4)×(H/4)，電路在搜索點的轉(zhuǎn)換過程中, 利用計數(shù)器統(tǒng)計當(dāng)前的周期數(shù)，控制每個4×4塊的SAD值的計算和累加，同時根據(jù)當(dāng)前塊的地址和MV，產(chǎn)生參考幀緩存的讀地址。

4 性能分析

本文的電路結(jié)構(gòu)與文獻(xiàn)[6～8]的不同之處主要體現(xiàn)在3個方面：(1)可支持HEVC標(biāo)準(zhǔn)中靈活的塊分割結(jié)構(gòu)；(2)充分考慮六邊形模板的數(shù)據(jù)復(fù)用特點，沒有采用文獻(xiàn)[6～7]中的7個并行處理單元的數(shù)據(jù)流組織方式，而是采用了1個處理單元，通過流水線依次得到7個參考點的結(jié)果，提高了參考幀像素的復(fù)用率，使得PE陣列的大小從112降低到32；(3)增加了起始點預(yù)測功能，使得搜索的第一步就比較接近最優(yōu)匹配點，有效降低了搜索步數(shù)。

實現(xiàn)上述VLSI結(jié)構(gòu)后，利用Snopsys Design Complier工具，SMIC 65 nm工藝庫進(jìn)行綜合，結(jié)果如表2所示。

表2 電路綜合結(jié)果

注：等效邏輯門數(shù)=總面積/單元庫中NAND2門的面積

與文獻(xiàn)[7]相比，本文的電路面積有所增加，但是在性能方面，本文面向的是當(dāng)下最新的HEVC標(biāo)準(zhǔn)，既可以支持更多尺寸的劃分塊，又可以支持更大的搜索范圍，并且在數(shù)據(jù)復(fù)用率方面優(yōu)于文獻(xiàn)[7]。

5 結(jié)束語

本文設(shè)計了適用于HEVC運動估計的六邊形搜索算法的VLSI架構(gòu)。該架構(gòu)流水線的數(shù)據(jù)組織策略可以增加參考幀數(shù)據(jù)的復(fù)用率，缺點是需要將參考幀數(shù)據(jù)全部緩存到片上，今后可以利用計算機體系結(jié)構(gòu)中多級Cache的思想，只緩存最有可能用到的參考像素，從而減小片上緩存的大小。本文也為后續(xù)圖像編碼的進(jìn)一步研究提供了參考。

[1] 萬帥,楊付正.新一代高效視頻編碼H.265/HEVC[M].北京:電子工業(yè)出版社,2014.

[2] Sullivan G J,Ohm J R,Han W J,et al.Overview of the high efficiency video coding (HEVC) standard[J]. IEEE Transactions on Circuits and Systems for Video Technology,2012,22(12):1649-1668.

[3] Ohm J R,Sullivan G J,Schwarz H,et al.Comparison of the coding efficiency of video coding standards—including high efficiency video coding (HEVC)[J].IEEE Transactions on Circuits and Systems for Video Technology,2012,22(12):1669-1684.

[4] Li X,Wang R,Wang W,et al.Fast motion estimation methods for HEVC[C].Beijing:2014 IEEE International Symposium on Broadband Multimedia Systems and Broadcasting,IEEE,2014.

[5] Zhu C,Lin X,Chau L P.Hexagon-based search pattern for fast block motion estimation[J].IEEE Transactions on Circuits and Systems for Video Technology,2002,12(5):349-355.

[6] 王巍,林濤,謝玉亭,等.H.264運動估計改進(jìn)六邊形算法及FPGA設(shè)計[J].微電子學(xué),2013(5):694-697.

[7] 商迪,王明江,鄭海東,等.六邊形運動估計算法的 VLSI實現(xiàn)[J].微電子學(xué)與計算機,2009,26(4):50-53.

[8] Muzammil M,Ali I,Sharif M,et al.An efficient FPGA architecture for hardware realization of hexagonal based motion estimation algorithm[C]. Shanghai:IEEE International Conference on Consumer Electronics-Taiwan (ICCE-TW),IEEE,2015.

[9] 李子印,朱善安.基于運動矢量預(yù)測的六邊形塊運動估計搜索算法[J].信號處理,2006,22(2):193-197.

[10] Ndili O,Ogunfunmi T.Algorithm and architecture co-design of hardware-oriented,modified diamond search for fast motion estimation in H.264/AVC[J]. IEEE Transactions on Circuits and Systems for Video Technology,2011,21(9):1214-1227.

[11] Tseng C F,Lai Y T,Lee M J.A VLSI architecture for three-step search with variable block size motion vector[C].Nanjing:The 1st IEEE Global Conference on Consumer Electronics IEEE,2012.

[12] Mukherjee R,Sheth K,Dhar A S,et al.High performance vlsi architecture for three-step search algorithm[J].Circuits,Systems and Signal Processing, 2015,34(5):1595-1612.

[13] Muzammil M,Raja G,Ali I.Field programmable gate array (FPGA) architecture of diamond search motion estimation algorithm for real-time video applications[J].Ned University Journal of Research, 2015(9):355-360.

[14] Porto M S,Sanchez G,Noble D,et al.An efficient ME architecture for high definition videos using the new MPDS algorithm[C].Nanjing:Proceedings of the 24th Symposium on Integrated Circuits and Systems Design,ACM,2011.

[15] Shah N N,Dalal U D.Hardware efficient double diamond search block matching algorithm for fast video motion estimation[J].Journal of Signal Processing Systems,2016,82(1):115-135.

A VLSI Architecture of Hexagonal Search Motion Estimation for HEVC

YAN Boran，HE Weifeng，MAO Zhigang

(Department of Microelectronics and Nanoscience，Shanghai Jiao Tong University，Shanghai 200240,China)

Motion Estimation is the most time consuming module in HEVC with high computational complexity. In order to speed up the encoding process, a VLSI architecture of hexagon-based motion estimation search for HEVC is proposed. This architecture can support variable-sized blocks in the HEVC standard and fully considerers the data multiplexing of hexagon search. The PE array uses the pipeline organization strategy to significantly reduce the on-chip cache access times. Using SMIC 65 nm technology, the proposed architecture is synthesized at the maximum operating frequency of 100 MHz with 101 thousand gates. Simulation result shows that the architecture is able to process 1 920 × 1080 p video at 60 f/s.

HEVC; motion estimation; hexagon-based search; VLSI

2016- 11- 25

閆博冉(1991-)，女，碩士研究生。研究方向：HEVC視頻編碼中的運動估計算法及其VLSI設(shè)計。何衛(wèi)鋒(1976-)，男，副研究員。研究方向：SoC設(shè)計與系統(tǒng)集成。毛志剛(1962-)，男，教授。研究方向：系統(tǒng)級芯片設(shè)計。

10.16180/j.cnki.issn1007-7820.2017.09.035

TN919.81

A

1007-7820(2017)09-130-05