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

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

基于HEVC六邊形運(yùn)動(dòng)估計(jì)算法的VLSI設(shè)計(jì)

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

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

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

HEVC; 運(yùn)動(dòng)估計(jì)；六邊形搜索；VLSI

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

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

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

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

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

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

(1)

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

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

圖2 預(yù)測(cè)起始搜索點(diǎn)示意圖

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

圖3 六邊形搜索過(guò)程示意圖

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

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

(2)

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

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

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

圖4 六邊形搜索點(diǎn)編號(hào)

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

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

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

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

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

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

3 六邊形運(yùn)動(dòng)估計(jì)算法的VLSI設(shè)計(jì)

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

圖6 運(yùn)動(dòng)估計(jì)整體VLSI結(jié)構(gòu)示意圖

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

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

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

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

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

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

圖7 PE陣列及SAD值運(yùn)算示意圖

3.3 控制器設(shè)計(jì)

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

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

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

4 性能分析

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

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

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

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

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

5 結(jié)束語(yǔ)

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

[1] 萬(wàn)帥,楊付正.新一代高效視頻編碼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運(yùn)動(dòng)估計(jì)改進(jìn)六邊形算法及FPGA設(shè)計(jì)[J].微電子學(xué),2013(5):694-697.

[7] 商迪,王明江,鄭海東,等.六邊形運(yùn)動(dòng)估計(jì)算法的 VLSI實(shí)現(xiàn)[J].微電子學(xué)與計(jì)算機(jī),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ùn)動(dòng)矢量預(yù)測(cè)的六邊形塊運(yùn)動(dòng)估計(jì)搜索算法[J].信號(hào)處理,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視頻編碼中的運(yùn)動(dòng)估計(jì)算法及其VLSI設(shè)計(jì)。何衛(wèi)鋒(1976-)，男，副研究員。研究方向：SoC設(shè)計(jì)與系統(tǒng)集成。毛志剛(1962-)，男，教授。研究方向：系統(tǒng)級(jí)芯片設(shè)計(jì)。

10.16180/j.cnki.issn1007-7820.2017.09.035

TN919.81

A

1007-7820(2017)09-130-05