聶宇鑫，施隆照，黃霖

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

0 引言

隨著短視頻的興起和5G技術(shù)的普及，人們對超高清視頻的需求越來越高.因此高效視頻編碼標準(high efficiency video coding, H.265/HEVC)應(yīng)運而生.H.265/HEVC與上一代H.264相比同樣采取混合編碼框架，包括變換、 量化、 熵編碼、 幀內(nèi)預(yù)測、 幀間預(yù)測和環(huán)路濾波等模塊[1].不同之處在于編碼單元能夠進行自適應(yīng)四叉樹劃分，同時提升了幀內(nèi)預(yù)測的精確度.幀間模式也引入了先進的運動矢量預(yù)測技術(shù)(advanced motion vector predictor，AMVP)[2].因此，在相同視頻質(zhì)量的情況下，HEVC編碼后的碼流大小僅為H.264的一半.在HEVC編碼過程中，幀間預(yù)測約占整個編碼時間的70%[3].因此對幀間預(yù)測的優(yōu)化是提升編碼器性能的關(guān)鍵.

目前HEVC編碼器常見的搜索算法主要有： 全搜索算法(Full-search)、 TZ-Search、 二維對數(shù)搜索法[4]、 三步搜索法[5]、 四步搜索法[6]等.不同的算法就是在尋找速度和性能之間的平衡點.文獻[7]提出一種快速CU尺寸決策算法，通過3種基于運動均勻性、 率失真代價(RD-COST)和SKIP模式的早期終止方法來跳過對不必要CU尺寸的運動估計，但是對于運動劇烈的圖像編碼效率較低.

也有許多研究人員提出了一些硬件友好型的運動估計算法.文獻[8]提出一種改進版菱形算法，對中心區(qū)域細選，外圍區(qū)域粗選，同時采用SAD樹同時記錄下全部PU的代價數(shù)據(jù).但是硬件資源開銷較大.文獻[9]對128 px×128 px的區(qū)域進行S型全搜索，對參考像素的存儲使用移位寄存器的方式，搜索左右移動時丟棄一列像素，因此能在一個時鐘內(nèi)完成參考像素的切換，但是這種做法模塊整體時鐘周期過長.文獻[10]將GOP中QP值最小一幀和前一幀同位置CTU深度合并，決定當前CTU計算的最大深度，將CTU的深度決策路徑從4個深度縮減到3個深度，能夠有效減少運算復(fù)雜度，但是性能損失并不理想.文獻[11]提出一種可變搜索范圍的快速算法，利用LCU的MV通過經(jīng)驗公式，估計出子塊PU的搜索范圍，能夠有效減少運動估計過程中的搜索點數(shù).但是對于一些特定序列效果并不理想.

本研究基于小菱形搜索算法，在硬件實現(xiàn)的架構(gòu)上對算法做一定調(diào)整，利用流水線處理和并行處理的方式，對AMVP和IME模塊進行流水處理，同時對PU和CU的處理順序進行調(diào)整，解決因為AMVP和IME互相參考導(dǎo)致流水線停滯的問題.硬件電路對小尺寸PU并行處理，進一步減少整個模塊周期數(shù).

1 算法簡述

1.1 小菱形搜索算法

一幀畫面中，每個PU的運動矢量(MV)都與其相鄰PU有著緊密相連的關(guān)系，因此HEVC引入AMVP算法，用于確定搜索起點，加快搜索過程.小菱形搜索算法搜索過程如圖1所示，圖中數(shù)字代表搜索的順序，搜索起點由AMVP的結(jié)果確定.一次搜索需計算包括中心點在內(nèi)的上下左右一共5個點所對應(yīng)的SAD(像素差值的絕對值和)代價.一次搜索結(jié)束后，進行代價比較來判斷是否需要迭代還是可以進行下一塊PU的搜索.判斷的條件是代價最小的點是否是中心點，如果不是則以代價最小的點作為中心點進行迭代搜索，直到代價最小的點為中心點或者達到最大迭代次數(shù)為止(本研究最大迭代次數(shù)設(shè)置為64次).小菱形搜索算法與視頻編碼標準代碼HM16.7中TZ-Search搜索算法相比，BD-rate平均只增加0.5%，搜索的點數(shù)卻平均減少了72.9%[12].因此小菱形搜索算法能夠大幅度減少搜索數(shù)據(jù)量，提高硬件的處理速度.

表1 關(guān)閉非對稱模式后性能對比

在HM16.7平臺上，CU非對稱模式劃分的占比僅為6.43%[13].利用HM16.7對關(guān)閉CU非對稱劃分模式后進行性能測試，得到的結(jié)果如表1所示.從表中可知，關(guān)閉非對稱模式整體編碼時間平均減少13.2%，BD-rate平均增長了0.687%.HM中并非全部PU都去執(zhí)行非對稱模式，只有對尺寸為32 px×32 px和16 px×16 px的CU才啟動非對稱模式[15]，并且不同的劃分方式對應(yīng)不同的非對稱模式，2Npx×Npx的PU只做2Npx×nDpx和2Npx×nUpx兩種非對稱劃分，Npx×2Npx的PU只做nLpx×2Npx和nRpx×2Npx兩種非對稱劃分，2Npx×2Npx的PU需要做上述四種非對稱劃分.所以關(guān)閉非對稱模式，復(fù)雜度只減少了13.2%，但對于硬件實現(xiàn)，只要有PU需要進行非對稱處理，就要為其準備相應(yīng)的硬件電路，但對于大多數(shù)PU無需做非對稱模式，這樣會造成硬件電路利用率低，硬件資源浪費； 其次，關(guān)閉非對稱模式后，一個CU需要處理的PU數(shù)量從13個減少到5個，對于尺寸64 px ×64 px的CTU，經(jīng)過四叉樹劃分可分為85個CU，因此處理一個CTU，遍歷的PU數(shù)由1 105降低至425個，在性能損失較小的情況下可有效縮減處理時間.綜上所述，運動估計模塊只對CU進行對稱劃分.

文獻[12]基于小菱形搜索算法做了硬件實現(xiàn)，對于PU的IME過程采用串行計算的方式，根據(jù)當前PU迭代判斷的結(jié)果來判斷下一個處理的是新的PU塊還是當前PU塊的迭代.這種處理方式邏輯清晰、 實現(xiàn)簡單，但是硬件各模塊由于等待迭代判斷的結(jié)果導(dǎo)致模塊內(nèi)數(shù)據(jù)處理斷斷續(xù)續(xù)，硬件工作效率不高.同時文獻[12]對CU采取按層搜索，每層按照Z掃描的方式順序執(zhí)行，CU內(nèi)包含的5個PU也為順序執(zhí)行.由于相鄰CU會互相參考IME的結(jié)果，這也會引起硬件處理的停滯.

對于高幀率、 高清晰度視頻，要實現(xiàn)實時編碼的功能，采用文獻[12]的硬件處理架構(gòu)是不可行的.文獻[12]中處理的CTU尺寸為16 px×16 px，內(nèi)部一共包括25個PU，整體數(shù)據(jù)量偏小.本研究要處理尺寸為64 px×64 px的CTU，其包含425個PU，因此如果采取上述方法不能達到理想的吞吐率目標.本研究基于小菱形搜索算法在PU和CU的處理方式上進行了優(yōu)化，對CU、 PU的處理順序進行調(diào)整，有效提高了硬件處理效率.

2 基于小菱形搜索的硬件架構(gòu)設(shè)計

本研究提出的硬件框架結(jié)構(gòu)如圖2所示，對一個PU的處理主要分為AMVP處理和IME搜索兩大過程.

兩個過程中間用FIFO進行數(shù)據(jù)的緩存，達到兩個過程并行計算的目的.AMVP處理主要包括候選列表的建立和代價計算比較模塊.IME過程主要包括PU對應(yīng)的原始像素和參考像素地址計算，SAD代價計算模塊和迭代判斷模塊.

2.1 PU的處理順序

從圖2中可以看出，對于一個PU的處理首先要進行AMVP過程，然后利用AMVP的結(jié)果進行IME搜索，因此為了高效處理一個PU，將AMVP和IME過程修改為流水處理，同時PU的處理順序也做了調(diào)整.對于一個CU包含三種劃分方式下的5個PU，如圖3所示.由于序號為3的PU塊進行AMVP處理需要依賴序號為2的PU塊的IME結(jié)果(序號4和序號5的PU塊同理)，因此對于PU塊的處理順序做了如下調(diào)整.將CU下5個PU可以分為MV互相沒有參考關(guān)系的3組，塊1為一組，塊2、 4為一組，塊3、 5為一組.

將PU塊的處理順序調(diào)整為塊2、 4、 1、 3、 5，由于塊2和4之間的AMVP沒有參考關(guān)系，因此在對塊2進行IME處理的同時可以對塊4進行AMVP處理.同理本研究的PU處理順序在兩個有參考關(guān)系的塊中(例如塊2、 3)插入了兩個不相關(guān)的塊，因此能夠有效解決因為等待IME的結(jié)果導(dǎo)致AMVP處理停滯的現(xiàn)象，減少整個模塊的時鐘數(shù).

2.2 CU的處理順序

文獻[12]的CU處理順序為分層處理，每層按照Z掃描的順序.這種處理方法導(dǎo)致下一個CU必須等待前一個CU處理結(jié)束后才能啟動.CU計算結(jié)束后的處理過程包括不同劃分方式的代價比較和更新IME到CTU_MV_TABLE_RAM中，這樣會造成IME處理模塊在CU切換時的停滯.因此利用不同層CU之間MV互不參考的規(guī)律，提出了一種新的CU處理順序，如圖4所示.圖4中數(shù)字代表CU的處理順序，將不同層或非相鄰位置的CU插入兩個相鄰CU的處理過程中間.這種方式保證了相鄰CU之間處理的流暢性，從后續(xù)的仿真波形可以看出，本研究提出的PU和CU處理順序能夠使IME中SAD模塊達到全流水狀態(tài).

2.3 IME模塊PU交替計算與流水線處理

IME處理簡單來說包括3個步驟： ① 根據(jù)PU的信息計算對應(yīng)的原始像素和參考像素地址； ② 按行輸入的原始像素和參考像素經(jīng)過裁剪后計算SAD代價； ③ 比較一次搜索過程中5個搜索點對應(yīng)PU的代價，判斷結(jié)束當前PU的IME過程或者進行迭代搜索.

由于迭代機制的存在，在迭代過程結(jié)束之前并不能確定下一個需要處理的過程是當前PU的迭代搜索還是下一個PU的搜索.因此，PU的串行處理會導(dǎo)致模塊的處理時間增長，且各個子模塊內(nèi)部的數(shù)據(jù)流時斷時續(xù)，時序示意圖如圖5所示.

為了解決這個問題，將PU的處理方式修改為三級流水線處理，并且為了壓縮判斷是否迭代而引起的時鐘周期浪費，保證模塊內(nèi)部始終有數(shù)據(jù)進行計算，在兩次迭代之間插入下一個PU的計算.如圖6所示，在PU1的SAD計算過程中就對PU2的地址進行計算，當PU1的迭代處理結(jié)束時，如果需要迭代就將PU1的信息存入到迭代FIFO中，因此IME的數(shù)據(jù)有兩個來源，一個是存有下一個PU信息的FIFO，一個是存儲迭代PU信息的FIFO，且迭代FIFO的優(yōu)先級更高，每次IME開始之前都會判斷兩個FIFO的數(shù)據(jù)存儲情況，來判斷從哪個FIFO中獲取數(shù)據(jù).

2.4 IME_SAD代價計算

遍歷CU包含的5個PU進行IME處理后，要比較3種不同劃分的代價來決定CU的最終劃分方式，計算代價的公式為J=D+λR+cost.其中： 殘差D在IME過程中用SAD表示；λ為拉格朗日因子與外部配置參數(shù)QP值有關(guān)，在本研究硬件中采用查表的方式獲得；R是當前MV與MVP差值(MVD)的編碼比特數(shù)； cost表示代價.

64 px×64 px的CTU一共包含425個PU，其中寬度為64 px的PU僅有3個，為了避免在處理小塊PU時，對邏輯資源利用的不完全造成的資源浪費，選擇每個時鐘周期同時計算32個像素點運算器.對于寬度為64 px的PU塊，分兩次進行代價計算，因此在AMVP模塊將寬度為64 px的PU信息和MVP連續(xù)存兩次到AMVP和IME的緩存FIFO中.然而對于16 px×16 px與8 px×8 px的PU，將有一半以上的處理單元處于空閑狀態(tài)，為了提高硬件資源的利用率，將32點運算器分為兩個互相獨立的運算器，每個運算器可以處理寬度為16 px的PU塊，也可以合并起來處理32點的PU，所以對于寬度為16 px和寬度為8 px的CU，可以同時處理2Npx×2Npx和上方2Npx×Npx大小的PU塊.

2.5 IME存儲單元設(shè)計

要實現(xiàn)運算單元的并行度，首要任務(wù)是存儲單元要能夠及時提供需要的數(shù)據(jù).首先說明一下存儲單元的需求，原始像素RAM中按行暫存著一個CTU的原始像素數(shù)據(jù)，其寬度為(64×8)bit，深度為64.本研究的搜索框設(shè)定是CTU周圍擴展32個像素點，同時考慮到進行分像素插值還需要向外擴展4個像素點，因此采用的搜索框大小是136 px×136 px.參考像素RAM寬度為(136×8)bit，深度為136.

IME地址計算模塊根據(jù)當前處理PU塊在CTU和搜索框中的坐標.根據(jù)y坐標作為地址輸出給參考像素和原始像素RAM，輸入到SAD的參考像素和原始像素分別為136 px和64 px，由x坐標值對按行輸入的像素進行篩選.然后二者相減并進行絕對值計算，由PU寬度選擇合適的SAD值進行相加，得到一個PU塊最終SAD值.為了提高一個PU塊的處理速度，硬件選擇同時計算5個搜索點的SAD代價.由于5個搜索點之間的位置關(guān)系是確定的，因此對參考像素和原始像素進行一遍讀取便可以計算5個點的代價，具體實現(xiàn)如圖7所示.圖中黑點表示需要同時搜索的5個搜索點，實線和虛線框表示每個搜索點對應(yīng)的PU塊.以搜索中心點左上角的像素點坐標作為首地址.第一個時鐘周期，第一行參考像素和原始像素差值的絕對值和得到上方搜索點第一行的SAD代價.第二個時鐘周期，第二行參考像素和打一拍的第一行原始像素差值的絕對值和能夠得到中間3個搜索點第一行的SAD值，3個搜索點只需要對參考像素進行不同的篩選，同理第二行參考像素和原始像素差值的絕對值和得到上方搜索點第二行的SAD代價.按照上述計算方式，5個搜索點得到最后一行的代價僅相差兩個時鐘周期，且對參考像素和原始像素只進行一次讀取，提高了數(shù)據(jù)交互的效率.

2.6 AMVP與IME的五級流水處理

根據(jù)前面的安排，IME模塊的SAD計算過程可以實現(xiàn)不斷流全流水，因此AMVP模塊也要達到這個速率，才能匹配IME模塊的處理速度.為此，AMVP模塊應(yīng)盡量提前將數(shù)據(jù)準備好，存在FIFO中等IME模塊讀取.流水線結(jié)構(gòu)如圖8所示，每個PU的處理需要經(jīng)過五級處理，其中AMVP分為候選列表建立和代價比較兩級，IME分為IME地址計算，SAD代價計算，代價比較和迭代判斷三級.總體來看AMVP的處理時間小于IME的處理時間，因此本研究重新設(shè)計了PU的處理順序，使相鄰處理的兩個PU不存在MV參考關(guān)系，AMVP模塊無需等待IME的結(jié)果即可對下一塊PU進行計算，然后將MVP等信息存儲在FIFO中，IME模塊結(jié)束后將得到的IMV更新到CTU_MV_TABLE中后判斷緩存FIFO是否為空，如果FIFO中存在數(shù)據(jù)即可自啟動下一塊PU的IME處理.AMVP和IME內(nèi)部每級流水之間也采用FIFO進行數(shù)據(jù)緩存.

3 硬件電路綜合結(jié)果

硬件框架采用Verilog語言設(shè)計，在Linux系統(tǒng)下使用Synopsys VCS軟件對RTL代碼進行仿真和編譯，利用Verdi軟件對波形進行時序調(diào)整.首先用Matlab打印出硬件所需要的激勵數(shù)據(jù)，包括參考像素、 原始像素、 上方和左側(cè)CTU的參考MV.利用Testbench將激勵數(shù)據(jù)從文本文件存入RAM中后發(fā)出起始信號，并且將硬件電路中IME的代價值和CU劃分方式與Matlab中的數(shù)據(jù)進行比對來驗證電路的正確性.之后利用QuartusII軟件，選擇Arria10AX115N3F40E2SG型號開發(fā)板，模塊資源測試結(jié)果詳見表2.

文獻[9]對搜索區(qū)域采取全搜索的方式，采用移位存儲器的方式存儲數(shù)據(jù)，搜索點上下移動時丟棄一行像素，搜索點左右移動時每個移位寄存器移動一位，只需要一個時鐘即可完成參考像素的切換，蛇形全搜索兩點之間數(shù)據(jù)重復(fù)率很高.但全搜索計算復(fù)雜度很高，需要處理的數(shù)據(jù)量龐大，導(dǎo)致硬件資源開銷較大，處理所需周期數(shù)較多.文獻[14]采用分層搜索加并行處理的方式進行搜索，并行計算很大程度提高了處理速度，但是硬件資源開銷較大.文獻[16]首先進行一次粗選，通過粗選得到的步長決定第二次搜索的方式，很大程度上減少了搜索的點數(shù)，但是需要的存儲資源和硬件資源較大.從表2可以看出，本研究主頻略低于文獻[9]和文獻[14]，但在硬件資源開銷上明顯小于上述3篇論文，在吞吐率與硬件資源開支上取得較高的性價比.

表2 本研究與其他文獻資源對比

表中的周期數(shù)為處理一個CTU所消耗的時鐘數(shù)，本研究平均周期數(shù)為5 800個時鐘周期，為了直觀地看到所提方法的有效性，還測試了在不改變CU和PU處理順序的條件下，處理一個64 px×64 px CTU平均消耗周期數(shù)為9 918個時鐘周期.這是因為不改變PU/CU處理順序?qū)е孪噜徧幚淼膬蓚€PU/CU塊之間有MV參考關(guān)系，需要等待上一個PU塊IME計算結(jié)束后才能進行當前PU塊的AMVP，并且需要等待AMVP模塊處理結(jié)果.因此本研究的設(shè)計方案與正常順序的做法相比，處理一個CTU平均減少了41.5%的時鐘數(shù).

4 結(jié)語

在視頻編碼中，幀間運動估計占據(jù)了編碼的大部分時間.因此如果想進一步提高編碼器的處理效率，就要在搜索方式或硬件實現(xiàn)方式上對運動估計進行優(yōu)化.搜索框中代價最小的點一定存在，如何利用搜索算法快速定位到它，如何利用硬件設(shè)計高效計算每一個點的代價就是研究人員的最終目標.在硬件架構(gòu)上對小菱形搜索算法進行優(yōu)化，重新對CU和PU的處理順序進行設(shè)計，采用PU交替處理和流水線的方式，盡量使IME模塊達到全流水的目標.同時對小尺寸PU進行并行處理，進一步縮減了模塊的周期數(shù).通過QuartusII平臺對RTL代碼進行綜合和編譯，提出的硬件架構(gòu)處理一個64 px×64 px的CTU平均消耗5 800個時鐘周期，主頻能夠達到186 MHz，綜合性能達到1080P@61 f·s-1.