HEVC的異構鉆石模板快速搜索算法

唐浩漾，程穎濤，郭 娜，孫梓巍，王 婧

西安郵電大學 自動化學院，西安 710121

1 引言

HEVC（High Efficiency Video Coding）是新一代的視頻編碼標準[1]，在同等視頻質量下減少50%的碼率[2]。其中幀間預測的運動估計在HEVC編碼過程中大約占據了一半的編碼時間和運算復雜度[3]。對于運動估計精度影響最大的主要有塊匹配準則[4]和搜索策略，為此學者們對其進行了大量的研究與優化[5-11]。

HEVC參考軟件HM14.0中運動估計采用TZSearch算法，眾多學者對此算法進行了改進和優化。文獻[12]將光柵掃描算法模型使用直線鉆石、小鉆石或者水平鉆石模板替換。文獻[13]采用半徑不斷擴大的水平垂直六邊形和旋轉六邊形代替鉆石搜索方案，并設置閾值提前終止搜索。文獻[14]采用旋轉六邊形模板用于在初始網格階段和細化階段替換鉆石圖案來找到全局最小值。但是文獻[13-14]兩種方案在最優點距離起始點較遠的情況下，最優點的位置精度會下降。盡管這些算法對于減少HEVC編碼復雜度均有一定的效果，但是以上算法往往以速率為第一目標，忽略或者很少考慮整體編碼性能。

本文通過運動矢量的分布特性并結合TZSearch算法搜索模板中存在的問題，提出基于異構鉆石模板的TZSearch快速搜索算法，在其中加入垂直水平六邊形模板，使其更適合于水平和垂直紋理的圖像，縮短運動估計模塊的耗時，提高了編碼的整體效率。

2 TZSearch搜索算法

TZSearch搜索算法步驟如下：

（1）運動矢量預測：從中值預測運動矢量、當前PU的左、上、右上運動矢量、零點運動矢量中選擇SAD值最小的點的作為TZSearch搜索的起始點。

（2）初始網格搜索：在搜索窗內進行2的次冪增長的8點鉆石或者正方形搜索（步長依次為2、4、8……64）。每次搜索之后都將SAD的最小值的搜索點作為下一步搜索的中心點，SAD最小的搜索點距離中心的距離即最佳步長。此步中需要確定搜索點總數如式（1），其中S是搜索窗的大小，P為模板中每次需要搜索的點數（六邊形時P=6，鉆石模板時P=8），floor為向下取整函數。

（3）柵格搜索：柵格搜索是對搜索窗進行一種下采樣式全搜索。HM14.0設置的柵格掃描的單位為5，該參數作為搜索窗的采樣參數。當之前搜索得到的最佳步長大于采樣參數時進行柵格掃描，最佳步長被賦值為采樣參數。如式（2），在柵格掃描時每一行/列需要搜索的點是ceil(S/R)，其中R是采樣參數的值，n2的最大值為此步需要搜索的點數。如果條件不滿足，將跳過此步。

（4）柵格/星型精細搜索：修正過程是為了確保最佳運動矢量的全局最優性，即當之前步驟得到的最佳步長大于0時用于對運動矢量的修正。一般情況下，只有一種修正模式（柵格修正或星型修正）是開啟狀態。星形修正過程中使用步長為2的次冪增長的8點鉆石搜索或8點正方形進行搜索，直到最佳步長為1。柵格修正是通過對之前步驟得到的最佳步長作以2為單位的下采樣操作，并以此作為步長進行鉆石或正方形搜索，直到最佳步長為1。無論選擇哪種修正方式，當最佳步長為1的時候都需要進行兩點搜索。

HM14.0中的TZSearch搜索算法與FS算法相比，TZSearch算法提供了良好的率失真性能，編碼時間提高了60%以上。但是TZSearch仍然存在不足之處：在搜索模板上，TZSearch沒有根據視頻存在的固有特性進行有區別的搜索，以2次冪為步長依次擴大的鉆石搜索執行了8次，增加編碼復雜度，但對于運動矢量水平垂直方向分布概率高于其他方向這種情況并未考慮在內，在編碼時間和編碼效率仍可以提高。

3 基于異構鉆石模板的快速搜索算法

3.1 運動矢量分布規律

運動矢量的分布規律是匹配圖像運動特征模板的重要因素。運動矢量具有以下分布特性：

（1）運動矢量具有中心偏移性。如圖1所示，采用全搜索算法對 Akiyo、Football、Table Tennis和 Flower Garden等不同特征序列的運動矢量概率分布進行實驗統計。圖1中原點處為最優點的概率最大，約為67%，最優點處于1×1區域的概率大約為12%，最優點處于2×2區域中的概率大約為5%。

圖1 運動矢量的分布情況

（2）運動矢量具有十字中心偏置特性。文獻[15-16]研究表明運動矢量出現在水平和垂直方向的概率高于其他方向。

3.2 異構鉆石模板

根據運動矢量的分布規律，本文采用一種新的異構鉆石搜索模板，如圖2所示。此模板在水平和垂直方向盡可能搜索更多的點來提高搜索精度。整個搜索過程分兩個階段，第一階段包括由17點組成的異構鉆石搜索，第二階段按照第一階段的搜索結果分別按照由7點組成的垂直水平六邊形或者大菱形搜索。

圖2 異構鉆石模板

異構鉆石算法搜索過程如下：

第一階段：異構鉆石搜索，以當前點為中心并搜索包括中心點在內的17點，確定匹配標準SAD的最小值發生位置。然后轉到階段二。

第二階段：以異構鉆石搜索后的最小匹配標準點為中心，分別按照六邊形或者大菱形進行搜索。最小匹配標準點即SAD最小的點分為A、B、C。根據最佳點所屬的類型，可以分為以下三類：

（1）如果最佳點屬于A類，也就是位于中心點，停止整個搜索過程。

（2）當最佳匹配點出現在B類，此時最佳點所處的方向決定了后序搜索采取的模板。當處于垂直方向時執行半徑廣和效率高的垂直六邊形模板（如圖3（a）），不斷將搜索中心更新為當前最佳匹配點，直到最佳匹配點位于中心時，在執行一次步長為1的正方形搜索進行精細定位，確定最終的最佳匹配點。同樣，若位于水平方向（與中心點水平）采用水平六邊形搜索模板（如圖3（b）），直到最佳點位于中心位置時，執行一次正方形搜索進行精細定位。

（3）當最佳匹配點歸類為C類的時候，選用大鉆石模板，不斷更新搜索中心的位置，直到最佳匹配點不變。最后進行一次小菱形搜索進行精細定位，選擇確立最佳的搜索點位置。

圖3 垂直水平六邊形模板

3.3 算法流程及步驟

算法的具體步驟如圖4。

圖4 基于異構鉆石的TZSearch搜索算法

（1）從相鄰預測運動矢量和零運動矢量中確定起始搜索點。

（2）選取步驟（1）中求的最優點作為搜索起點，進行異構鉆石模板搜索，得到當前最優點。若當前最優點屬于搜索模板中的A類時，結束整個搜索過程，當前最優點為全局最優點，得到最優運動矢量。若當前最優點屬于B類，跳轉至步驟（3）。若當前最優點屬于C類，跳轉至步驟（4）。

（3）若當前最優點位于水平方向（與中心點平行），跳轉執行步驟（5）。若當前最優點位于垂直方向（與中心點垂直），跳轉執行步驟（6）。

（4）用當前最優點當作搜索中心執行大鉆石搜索，并且不斷的將搜索中心更新為當前最優匹配點，直到最優點不再變化，執行一次小鉆石搜索進行精細定位，得到最優點，確定最終的運動矢量。

（5）用當前最優點當作搜索中心執行半徑廣和效率高的水平六邊形模板，并且不斷地將搜索中心更新為當前最優匹配點，直到最佳匹配點位于六邊形中心。跳轉到步驟（7）。

（6）以當前最優點作為搜索中心執行半徑廣和效率高的垂直六邊形模板，并且不斷地將搜索中心更新為當前最優匹配點，直到最佳匹配點位于垂直六邊形中心。跳轉到步驟（7）。

（7）以當前最優點為搜索中心，執行步長為1的正方形搜索進行精細定位，確定最優點位置，得到運動矢量。

4 實驗結果與分析

為了驗證本文算法的有效性，在HEVC參考軟件HM14.0上實現本文算法。在Intel酷睿i5處理器，8 GB的內存，Windows 64位的操作系統的硬件條件下進行實驗，采用的編碼幀結構是IPPPP，搜索區域的窗口設置為64×64，QP 從22變化到37（22、27、32和37）。測試序列為5類HEVC標準測試序列A類（2 560×1 080），B類（1 920×720），C類（832×480），D類（416×240）以及E類（1 280×720），測試幀數為100幀。

采用同等客觀質量下的碼率BDBR（Bj?ntegaard Delta Bit Rate）、同等碼率下的峰值信噪比BDPSNR（Bj?ntegaard Delta Peak Signal-to-Noise Rate）[17]和編碼時間變化率ΔTime作為快速算法的評價指標。BDBR和BDPSNR分別表示相同PSNR條件下碼率的變化百分比和相同碼率條件下PSNR的變化量。ΔTime計算方法如下：

其中HM和proposed分別代表HM14.0和本文算法。圖5給出序列RaceHorses和BasketballPass使用HM14.0的搜索策略每幀需要搜索的平均點數分別大致在180和120周圍波動，而使用本文提出的搜索模板搜索平均每幀需要搜索的點數分別在40和45左右波動，說明采用本文的搜索策略可使每幀搜索的點數進一步減少，繼而減少編碼時間。從表1可以看出本文算法總的編碼時間減少了大約26.30%，最大可減少33.05%，而BDBR僅增加1.172%，BDPSNR也只降低了0.051 dB。

圖5 QP=32時BasketBallPass每幀所需搜索的點數和RaceHorses每幀所需搜索的點數

表1 本文算法與HM14.0算法的對比結果

圖6給出序列（BasketBallPass和RaceHorses）的RD曲線，從曲線圖中可以看出所提出的TZSearch快速搜索算法與原始TZSearch搜索算法結果相差不大，保持了原有的編碼性能。

產生此實驗結果原因是本文只進行一次異構鉆石搜索，改進了最耗時的搜索模塊，其次當異構鉆石搜索到最佳點位于中心位置，直接退出整個搜索過程，設置了提前退出搜索的條件。

5 結束語

本文針對HEVC幀間預測的運動估計高耗時問題，提出了一種快速的搜索算法。首先根據異構鉆石搜索后最佳點所在位置的不同采取不同的搜索模板改進了TZSearch中的鉆石搜索，其次去掉了TZSearch中最耗時的柵格搜索模塊。實驗結果表明，本文的算法與HM14.0的算法比較，編碼時間最大可減少33.05%，同時BDPSNR僅下降了0.051 dB，具有一定的實用價值。

圖6 BasketBallPass和RaceHorses序列在不同QP（22，27，32，37）下的RD曲線