HEVC的異構(gòu)鉆石模板快速搜索算法

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

西安郵電大學(xué) 自動化學(xué)院，西安 710121

1 引言

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

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

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

2 TZSearch搜索算法

TZSearch搜索算法步驟如下：

（1）運(yùn)動矢量預(yù)測：從中值預(yù)測運(yùn)動矢量、當(dāng)前PU的左、上、右上運(yùn)動矢量、零點(diǎn)運(yùn)動矢量中選擇SAD值最小的點(diǎn)的作為TZSearch搜索的起始點(diǎn)。

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

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

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

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

3 基于異構(gòu)鉆石模板的快速搜索算法

3.1 運(yùn)動矢量分布規(guī)律

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

（1）運(yùn)動矢量具有中心偏移性。如圖1所示，采用全搜索算法對 Akiyo、Football、Table Tennis和 Flower Garden等不同特征序列的運(yùn)動矢量概率分布進(jìn)行實(shí)驗(yàn)統(tǒng)計(jì)。圖1中原點(diǎn)處為最優(yōu)點(diǎn)的概率最大，約為67%，最優(yōu)點(diǎn)處于1×1區(qū)域的概率大約為12%，最優(yōu)點(diǎn)處于2×2區(qū)域中的概率大約為5%。

圖1 運(yùn)動矢量的分布情況

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

3.2 異構(gòu)鉆石模板

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

圖2 異構(gòu)鉆石模板

異構(gòu)鉆石算法搜索過程如下：

第一階段：異構(gòu)鉆石搜索，以當(dāng)前點(diǎn)為中心并搜索包括中心點(diǎn)在內(nèi)的17點(diǎn)，確定匹配標(biāo)準(zhǔn)SAD的最小值發(fā)生位置。然后轉(zhuǎn)到階段二。

第二階段：以異構(gòu)鉆石搜索后的最小匹配標(biāo)準(zhǔn)點(diǎn)為中心，分別按照六邊形或者大菱形進(jìn)行搜索。最小匹配標(biāo)準(zhǔn)點(diǎn)即SAD最小的點(diǎn)分為A、B、C。根據(jù)最佳點(diǎn)所屬的類型，可以分為以下三類：

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

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

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

圖3 垂直水平六邊形模板

3.3 算法流程及步驟

算法的具體步驟如圖4。

圖4 基于異構(gòu)鉆石的TZSearch搜索算法

（1）從相鄰預(yù)測運(yùn)動矢量和零運(yùn)動矢量中確定起始搜索點(diǎn)。

（2）選取步驟（1）中求的最優(yōu)點(diǎn)作為搜索起點(diǎn)，進(jìn)行異構(gòu)鉆石模板搜索，得到當(dāng)前最優(yōu)點(diǎn)。若當(dāng)前最優(yōu)點(diǎn)屬于搜索模板中的A類時(shí)，結(jié)束整個搜索過程，當(dāng)前最優(yōu)點(diǎn)為全局最優(yōu)點(diǎn)，得到最優(yōu)運(yùn)動矢量。若當(dāng)前最優(yōu)點(diǎn)屬于B類，跳轉(zhuǎn)至步驟（3）。若當(dāng)前最優(yōu)點(diǎn)屬于C類，跳轉(zhuǎn)至步驟（4）。

（3）若當(dāng)前最優(yōu)點(diǎn)位于水平方向（與中心點(diǎn)平行），跳轉(zhuǎn)執(zhí)行步驟（5）。若當(dāng)前最優(yōu)點(diǎn)位于垂直方向（與中心點(diǎn)垂直），跳轉(zhuǎn)執(zhí)行步驟（6）。

（4）用當(dāng)前最優(yōu)點(diǎn)當(dāng)作搜索中心執(zhí)行大鉆石搜索，并且不斷的將搜索中心更新為當(dāng)前最優(yōu)匹配點(diǎn)，直到最優(yōu)點(diǎn)不再變化，執(zhí)行一次小鉆石搜索進(jìn)行精細(xì)定位，得到最優(yōu)點(diǎn)，確定最終的運(yùn)動矢量。

（5）用當(dāng)前最優(yōu)點(diǎn)當(dāng)作搜索中心執(zhí)行半徑廣和效率高的水平六邊形模板，并且不斷地將搜索中心更新為當(dāng)前最優(yōu)匹配點(diǎn)，直到最佳匹配點(diǎn)位于六邊形中心。跳轉(zhuǎn)到步驟（7）。

（6）以當(dāng)前最優(yōu)點(diǎn)作為搜索中心執(zhí)行半徑廣和效率高的垂直六邊形模板，并且不斷地將搜索中心更新為當(dāng)前最優(yōu)匹配點(diǎn)，直到最佳匹配點(diǎn)位于垂直六邊形中心。跳轉(zhuǎn)到步驟（7）。

（7）以當(dāng)前最優(yōu)點(diǎn)為搜索中心，執(zhí)行步長為1的正方形搜索進(jìn)行精細(xì)定位，確定最優(yōu)點(diǎn)位置，得到運(yùn)動矢量。

4 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文算法的有效性，在HEVC參考軟件HM14.0上實(shí)現(xiàn)本文算法。在Intel酷睿i5處理器，8 GB的內(nèi)存，Windows 64位的操作系統(tǒng)的硬件條件下進(jìn)行實(shí)驗(yàn)，采用的編碼幀結(jié)構(gòu)是IPPPP，搜索區(qū)域的窗口設(shè)置為64×64，QP 從22變化到37（22、27、32和37）。測試序列為5類HEVC標(biāo)準(zhǔn)測試序列A類（2 560×1 080），B類（1 920×720），C類（832×480），D類（416×240）以及E類（1 280×720），測試幀數(shù)為100幀。

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

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

圖5 QP=32時(shí)BasketBallPass每幀所需搜索的點(diǎn)數(shù)和RaceHorses每幀所需搜索的點(diǎn)數(shù)

表1 本文算法與HM14.0算法的對比結(jié)果

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

產(chǎn)生此實(shí)驗(yàn)結(jié)果原因是本文只進(jìn)行一次異構(gòu)鉆石搜索，改進(jìn)了最耗時(shí)的搜索模塊，其次當(dāng)異構(gòu)鉆石搜索到最佳點(diǎn)位于中心位置，直接退出整個搜索過程，設(shè)置了提前退出搜索的條件。

5 結(jié)束語

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

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