基于條件判據(jù)改進(jìn)的提前終止運(yùn)動(dòng)估計(jì)算法

朱鑫磊　汪偉

關(guān)鍵詞：運(yùn)動(dòng)估計(jì)；塊匹配提前終止；八邊形-“十”字柵格搜索；精細(xì)搜索

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

1引言（Introduction）

隨著5G網(wǎng)絡(luò)通信技術(shù)的迅速發(fā)展，以及人們對(duì)視頻質(zhì)量要求的提高，促使編碼標(biāo)準(zhǔn)不斷改進(jìn)和完善。高效率視頻編碼（H.265/HEVC）[1]作為應(yīng)用最廣泛的視頻編碼標(biāo)準(zhǔn)，滿足了大部分領(lǐng)域的應(yīng)用條件。與高度壓縮數(shù)字視頻編解碼器標(biāo)準(zhǔn)（H.264/AVC）[2]相比，H.265/HEVC可以在使用H.264/AVC一半碼流的情況下，解碼重建出與其在主觀上有著相同畫面質(zhì)量的高清視頻，其更加優(yōu)秀的壓縮比可以在相同網(wǎng)絡(luò)帶寬的環(huán)境下傳輸清晰度更高的視頻。雖然H.266標(biāo)準(zhǔn)已經(jīng)被提出，其在深度學(xué)習(xí)和多特征融合方面展現(xiàn)了良好的效果，并且相較于HEVC，壓縮率約提高了一倍[3]，但是HEVC仍然是目前使用最為廣泛的視頻編碼標(biāo)準(zhǔn)，其針對(duì)機(jī)器學(xué)習(xí)中編碼單元塊的預(yù)測(cè)仍然很有效果[4]。運(yùn)動(dòng)估計(jì)算法作為高效視頻編碼中占比最高、時(shí)間處理最長(zhǎng)的步驟，在視頻編碼中占據(jù)著舉足輕重的地位。

近年來(lái)，熵編碼[5]的應(yīng)用，使得編碼更加靈活，也更加多元。運(yùn)動(dòng)估計(jì)（ME）作為基于塊的視頻編碼器的重要組成部分之一，其對(duì)編碼算法的要求最高、最復(fù)雜、最苛刻。塊匹配運(yùn)動(dòng)估計(jì)算法是H.265/HEVC中應(yīng)用最廣泛的算法之一，XU等[6]提出一種針對(duì)HEVC測(cè)試區(qū)域的搜索模式，通過對(duì)編碼單元塊進(jìn)行塊內(nèi)復(fù)制，借助對(duì)編碼內(nèi)容的擴(kuò)展，達(dá)到選中最佳匹配塊的目的，但是該算法仍然存在很多的計(jì)算冗余。YANG等[7]提出基于方向的快速運(yùn)動(dòng)搜索方法，通過改進(jìn)搜索方式減少搜索參考?jí)K的個(gè)數(shù)和計(jì)算次數(shù)，以此達(dá)到減少編碼所需時(shí)間的目的，但是該算法存在計(jì)算量大的問題，而且視頻編碼運(yùn)算中對(duì)實(shí)時(shí)性的要求無(wú)法較好地滿足。CHUNG等[8]針對(duì)塊匹配運(yùn)動(dòng)估計(jì)中存在運(yùn)動(dòng)偽影的問題，提出了一種將運(yùn)動(dòng)估計(jì)和圖像重建的離散問題建模為可分離的非線性最小二乘問題的方法，使得編碼質(zhì)量獲得提升。ABDELAZIM等[9]利用鉆石搜索的方式，在三次鉆石搜索后采取半像素六邊形搜索，保留了算法的搜索精度。MADHUVAPPAN等[10]提出了增強(qiáng)型測(cè)試區(qū)域搜索算法，對(duì)一定的搜索區(qū)域采取下采樣遍歷搜索，可以在一定程度上減少局部最優(yōu)的情況，提高了編碼的質(zhì)量。唐浩漾等[11]通過研究運(yùn)動(dòng)矢量分布規(guī)律，提出一種基于HEVC的異構(gòu)鉆石模板快速搜索算法，提高了搜索精度。蔡于涵等[12]提出一種基于運(yùn)動(dòng)矢量細(xì)化的幀率上變換與HEVC結(jié)合的視頻壓縮算法，通過結(jié)合算法細(xì)化運(yùn)動(dòng)矢量，提高了重建速度。為了能夠更好地適配硬件，張志勇等[13]提出一種基于并行螺旋搜索算法的整像素運(yùn)動(dòng)估計(jì)硬件架構(gòu)，采取共享搜索過程的方式減少了搜索周期數(shù)。秦傳義等[14]提出一種基于FPGA的運(yùn)動(dòng)估計(jì)算法，減小了系統(tǒng)架構(gòu)的內(nèi)部資源消耗，使得FPGA上資源利用率獲得提升。基于現(xiàn)有的塊匹配提前終止策略與運(yùn)動(dòng)估計(jì)改進(jìn)算法的研究，本文提出了一種基于條件判據(jù)改進(jìn)的提前終止運(yùn)動(dòng)估計(jì)算法，并且通過實(shí)驗(yàn)得出結(jié)論，在基本不影響視頻質(zhì)量的情況下，改進(jìn)之后的算法相比原有標(biāo)準(zhǔn)算法，平均降低了42％的編碼時(shí)間。

2運(yùn)動(dòng)估計(jì)標(biāo)準(zhǔn)算法（Motion estimation standardalgorithm）

2.1確定起始搜索點(diǎn)

研究人員利用先進(jìn)運(yùn)動(dòng)矢量預(yù)測(cè)技術(shù)（AMVP）選出最小預(yù)測(cè)運(yùn)動(dòng)矢量MVP、當(dāng)前預(yù)測(cè)單元塊左側(cè)、上側(cè)、右上及零向量共五個(gè)候選矢量，并從中選出匹配誤差最小點(diǎn)作為起始搜索點(diǎn)[15]。匹配誤差（SAD）最小點(diǎn)計(jì)算公式如式（1）所示：

2.2初始網(wǎng)格搜索

HEVC標(biāo)準(zhǔn)算法中，初始網(wǎng)格搜索階段首先將起始搜索點(diǎn)作為當(dāng)前塊匹配搜索的中心，接著以步長(zhǎng)為1、2、4、8、16、32、64進(jìn)行鉆石搜索（Diamond Search）[16]或者柵格搜索，選取率失真代價(jià)最小的點(diǎn)作為初始網(wǎng)格搜索階段的預(yù)測(cè)矢量。鉆石搜索如圖1（a）所示，柵格搜索如圖1（b）所示。

2.3兩點(diǎn)搜索

若初始網(wǎng)格所得到最佳候選點(diǎn)步長(zhǎng)為1，就會(huì)導(dǎo)致該點(diǎn)周圍有兩個(gè)點(diǎn)沒有搜索到，于是補(bǔ)充兩點(diǎn)搜索，若得到的最佳點(diǎn)大于某個(gè)閾值，則以該點(diǎn)為起點(diǎn)，在一定范圍進(jìn)行全搜索，找到率失真代價(jià)最小點(diǎn)。

2.4精細(xì)搜索

以兩點(diǎn)搜索所得最優(yōu)點(diǎn)為新的起始搜索點(diǎn)，繼續(xù)跳轉(zhuǎn)到初始網(wǎng)格搜索步驟中進(jìn)行精細(xì)搜索，直到兩次得到的精細(xì)搜索結(jié)果為一致時(shí)，停止搜索[17]，此時(shí)得到的就是最優(yōu)預(yù)測(cè)矢量。

3改進(jìn)后的運(yùn)動(dòng)估計(jì)算法（Improved motionestimation algorithm）

3.1起始搜索點(diǎn)的確定

為了減少尋找起始搜索點(diǎn)所需時(shí)間，先進(jìn)運(yùn)動(dòng)矢量預(yù)測(cè)技術(shù)應(yīng)運(yùn)而生，它能夠有效地去除運(yùn)動(dòng)信息之間的冗余，一般算法步驟為從候選的五個(gè)位置中選取兩個(gè)候選預(yù)測(cè)矢量，分別是當(dāng)前塊的左側(cè)和上側(cè)，以這兩個(gè)候選預(yù)測(cè)矢量為中心，進(jìn)行步長(zhǎng)為1的鉆石搜索，如果一次鉆石搜索之后能夠檢測(cè)到一個(gè)可用的運(yùn)動(dòng)矢量，那么直接選用該矢量作為候選預(yù)測(cè)矢量，不再檢測(cè)其他剩余的候選，這就使得預(yù)測(cè)運(yùn)動(dòng)矢量的時(shí)間縮短了很多。將先進(jìn)運(yùn)動(dòng)矢量預(yù)測(cè)技術(shù)選出的率失真代價(jià)最小的預(yù)測(cè)運(yùn)動(dòng)矢量MVP與以該點(diǎn)為中心進(jìn)行步長(zhǎng)為1和2的鉆石搜索選出的最佳匹配點(diǎn)P進(jìn)行對(duì)比，判斷是否一致，若一致，則搜索終止，完成運(yùn)動(dòng)估計(jì)；若不一致，則按照原來(lái)的標(biāo)準(zhǔn)算法進(jìn)行起始搜索點(diǎn)的確定。該步驟主要目的就是利用快速搜索的方式，提前確定一些相對(duì)靜止區(qū)域的最佳匹配點(diǎn)，不必再將這些預(yù)測(cè)矢量采取標(biāo)準(zhǔn)算法中的復(fù)雜步驟。具體流程如圖2所示。

3.2基于編碼單元塊提前終止策略的初始網(wǎng)格搜索

在HEVC中，一幅圖像被劃分為許多個(gè)編碼樹單元，每個(gè)編碼樹單元又被劃分為一個(gè)或者是多個(gè)編碼單元[18]，在編碼單元的基礎(chǔ)上，又可以被劃分為多個(gè)預(yù)測(cè)單元和變換單元。CU作為編碼單元，在HEVC中是基于四邊形的編碼單元，其最大尺寸為64×64像素，編碼單元用來(lái)確定預(yù)測(cè)矢量是幀內(nèi)模式還是幀間模式。PU為預(yù)測(cè)單元，包括幀內(nèi)預(yù)測(cè)和幀間預(yù)測(cè)兩類。TU為變換單元，用來(lái)變換和量化的基本單元，尺寸受編碼單元的限制。

當(dāng)一個(gè)劃分深度為d 的編碼單元塊進(jìn)行完整的編碼步驟，終止編碼剩余深度的選擇過程等價(jià)于在率失真優(yōu)化過程中采用的候選集：

3.3八邊形-“十”字柵格搜索

根據(jù)GONCALVES等[20]提出運(yùn)動(dòng)估計(jì)算法的復(fù)雜度分析，運(yùn)動(dòng)矢量的分布具有中心“十”字偏置的特性，運(yùn)動(dòng)矢量基本都分布在搜索點(diǎn)的水平方向、垂直方向及搜索中心的周圍，在搜索點(diǎn)比較遠(yuǎn)的地方，基本沒有運(yùn)動(dòng)矢量的分布。由于此特性的存在，搜索時(shí)可以適當(dāng)移除距離較遠(yuǎn)的非水平和垂直區(qū)域的柵格搜索，對(duì)于水平和垂直區(qū)域來(lái)說，運(yùn)動(dòng)矢量分布較多，不能忽略該搜索區(qū)域，如果忽略，雖然搜索時(shí)間減少了一點(diǎn)，但是有可能會(huì)使得運(yùn)動(dòng)矢量陷入局部最優(yōu)。因此提出一種八邊形-“十”字柵格搜索（Octagon-crossraster search）模板用于縮小柵格搜索的范圍，以此節(jié)約搜索時(shí)間，提高搜索的效率。

八邊形-“十”字柵格搜索模板選取標(biāo)準(zhǔn)柵格搜索正中央25％的區(qū)域作為搜索范圍，在此基礎(chǔ)上，進(jìn)一步縮小搜索范圍，將這25％的柵格搜索區(qū)域四個(gè)角的范圍忽略不計(jì)，因?yàn)檫@四個(gè)角落與中心搜索點(diǎn)距離較遠(yuǎn)，并且所含的運(yùn)動(dòng)矢量很少。同時(shí)，增加水平和垂直方向上的搜索，使得搜索更加精確，節(jié)約了搜索時(shí)間。按照該方式進(jìn)行柵格搜索，可以在保證視頻質(zhì)量的情況下，節(jié)約一些搜索時(shí)間。八邊形-“十”字柵格搜索模型如圖3所示。

3.4精細(xì)搜索

精細(xì)搜索經(jīng)過分析，決定采取鉆石搜索或者柵格搜索的方式來(lái)完成。為了找到率失真代價(jià)最小的點(diǎn)，所以將會(huì)首先以搜索步長(zhǎng)1進(jìn)行鉆石搜索，然后在此基礎(chǔ)上采取步長(zhǎng)為2、4、8、16、32、64……這種方式繼續(xù)進(jìn)行鉆石搜索，最終將會(huì)有兩種情況出現(xiàn)，一種是搜索到了邊界，不得已結(jié)束搜索模式，另一種是找到了最佳運(yùn)動(dòng)矢量為1的點(diǎn)，這樣也可以停止精細(xì)搜索，將找到的最優(yōu)矢量為1的點(diǎn)再進(jìn)行兩點(diǎn)搜索，這樣就找到了最佳匹配塊，以這種方式對(duì)其他塊進(jìn)行搜索，就可以完成對(duì)圖片幀的精細(xì)搜索。

當(dāng)遇到了搜索邊界，不得以停止搜索的情況時(shí)，將會(huì)采取柵格搜索方式，將初始網(wǎng)格搜索得到的點(diǎn)與閾值進(jìn)行比較，將大于閾值的點(diǎn)找出來(lái)[21]，并且將該點(diǎn)作為中心，進(jìn)行步長(zhǎng)為2的柵格搜索，遍歷搜索區(qū)域，得到的率失真代價(jià)最小點(diǎn)就是最優(yōu)點(diǎn)。該方式雖然相對(duì)煩瑣并且會(huì)浪費(fèi)一定的搜索時(shí)間，但是準(zhǔn)確率在很大程度上得到滿足，并且基本不會(huì)發(fā)生重復(fù)搜索的情況，保證了搜索的準(zhǔn)確率。

4實(shí)驗(yàn)結(jié)果與分析（Experimental results andanalysis）

4.1建立測(cè)試數(shù)據(jù)庫(kù)

4.1.1 最優(yōu)預(yù)測(cè)點(diǎn)測(cè)試數(shù)據(jù)庫(kù)

為驗(yàn)證算法的有效性， 選取B Q M a l l （ 8 3 2 × 4 8 0 ） 、V i d y o 4 （ 1 2 8 0 × 7 2 0 ） 、C a c t u s （ 1 9 2 0 × 1 0 8 0 ） 、PeopleOnStreet（2560×1600）四組視頻編碼測(cè)試序列，根據(jù)最佳匹配點(diǎn)為預(yù)測(cè)矢量點(diǎn)的次數(shù)在運(yùn)動(dòng)估計(jì)算法調(diào)用總次數(shù)中所占的比重，判斷該方法的有效性。

4.1.2編碼單元塊提前終止策略測(cè)試數(shù)據(jù)庫(kù)

建立A 類（ 8 3 2 × 4 8 0 ） 、B 類（ 1 2 8 0 × 7 2 0 ） 、C 類（1920×1080）、D類（2560×1600）四組視頻編碼測(cè)試序列，序列均為YUV格式，測(cè)試序列幀數(shù)均為500 幀。

4.1.3改進(jìn)后運(yùn)動(dòng)估計(jì)算法測(cè)試數(shù)據(jù)庫(kù)

采用與“ 4 . 1 . 2 ” 部分中相同的測(cè)試數(shù)據(jù)庫(kù)， 即選取YUV格式的視頻序列，并且選取BQMall（832×480）、V i d y o 4 （ 1 2 8 0 × 7 2 0 ） 、C a c t u s （ 1 9 2 0 × 1 0 8 0 ） 、PeopleOnStreet（2560×1600）四組視頻編碼測(cè)試序列，測(cè)試序列幀數(shù)均為500 幀。

4.2實(shí)驗(yàn)參數(shù)及環(huán)境設(shè)置

該實(shí)驗(yàn)所采用的硬件平臺(tái)為酷睿I 5 - 8 2 5 0U處理器、8GB的內(nèi)存和2.8 GHz的主頻。軟件配置為Windows 10 64位操作系統(tǒng)、Elecard HEVC Anlyzer編碼視頻檢測(cè)工具和yuvplayer視頻序列播放器。HM-16.14中配置的量化步長(zhǎng)序號(hào)為37、32、27、22，其他配置為默認(rèn)值。

4.3算法評(píng)估指標(biāo)

采用最佳匹配點(diǎn)為最優(yōu)預(yù)測(cè)點(diǎn)的次數(shù)在運(yùn)動(dòng)估計(jì)中調(diào)用總次數(shù)中所占的比重，判斷最優(yōu)預(yù)測(cè)點(diǎn)與最佳匹配點(diǎn)的相近程度。

4.4 實(shí)驗(yàn)結(jié)果

4.4.1 最優(yōu)預(yù)測(cè)點(diǎn)為最佳匹配點(diǎn)概率

由表1計(jì)算可知，改進(jìn)之后得到的最優(yōu)預(yù)測(cè)點(diǎn)為最佳匹配點(diǎn)的平均概率為71.51％，尤其是圖像中存在很多相對(duì)靜止和相對(duì)平坦區(qū)域的Vidyo4序列，最優(yōu)預(yù)測(cè)點(diǎn)為最佳匹配點(diǎn)的概率達(dá)到了75.15％，體現(xiàn)了很好的改進(jìn)效果。

4.4.2編碼單元塊提前終止策略測(cè)試結(jié)果

在運(yùn)動(dòng)估計(jì)過程中，用Depth L表示劃分深度為0或1的大尺寸編碼單元塊，用Depth S表示劃分深度為2或3的小尺寸編碼塊。表2中的HR_L代表運(yùn)動(dòng)估計(jì)中使用Depth L劃分的編碼單元塊，HR_S代表運(yùn)動(dòng)估計(jì)中使用Depth S劃分的編碼單元塊。量化步長(zhǎng)序號(hào)分別設(shè)置為22、27、32、37，以此判斷不同量化參數(shù)時(shí)有效命中概率的準(zhǔn)確性。從表2中可以看出，改進(jìn)的基于編碼單元塊劃分的提前終止運(yùn)動(dòng)估計(jì)算法的有效性。

4.4.3改進(jìn)后的運(yùn)動(dòng)估計(jì)算法實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文提出算法的效果，在實(shí)驗(yàn)環(huán)境中進(jìn)行四組不同量化參數(shù)值的運(yùn)動(dòng)估計(jì)標(biāo)準(zhǔn)搜索和本文改進(jìn)搜索，編碼得到四組不同量化參數(shù)值的峰值信噪比（PSNR）、比特率和運(yùn)動(dòng)估計(jì)搜索時(shí)間的參數(shù)平均值，Bitrate為編碼的碼率，T為運(yùn)動(dòng)估計(jì)搜索時(shí)間。由實(shí)驗(yàn)結(jié)果可知，改進(jìn)后的算法在基本不影響視頻質(zhì)量的情況下，提高了編碼速度，降低了算法的計(jì)算復(fù)雜度，節(jié)約了時(shí)間。具體結(jié)果如表3所示。

5結(jié)論（Conclusion）

針對(duì)編碼器復(fù)雜度比較高、標(biāo)準(zhǔn)算法計(jì)算冗余的問題，提出一種基于條件判據(jù)改進(jìn)的提前終止運(yùn)動(dòng)估計(jì)算法。首先利用先進(jìn)運(yùn)動(dòng)矢量預(yù)測(cè)技術(shù)（AMVP）選出最優(yōu)點(diǎn)MVP，并且以該點(diǎn)為中心進(jìn)行步長(zhǎng)1和2的鉆石搜索，得到最佳匹配點(diǎn)P，判斷MVP與P是否一致。其次利用條件判據(jù)，在最優(yōu)點(diǎn)為最佳匹配點(diǎn)的情況下跳出循環(huán)，在不一致的情況下先采取標(biāo)準(zhǔn)算法中的方式確定初始搜索點(diǎn)，然后按照編碼單元塊提前終止策略進(jìn)行初始網(wǎng)格搜索。在最佳候選塊距離大于5的情況下，進(jìn)行條件判據(jù)。最后使用八邊形-“十”字柵格搜索與精細(xì)搜索完成算法改進(jìn)。由實(shí)驗(yàn)結(jié)果可知，該方法所得最優(yōu)點(diǎn)與最佳匹配點(diǎn)相同的平均概率為71.51％，編碼單元塊有效命中概率的平均值超過97.83％，并且在基本不影響視頻質(zhì)量的情況下，平均節(jié)約了42.47％的運(yùn)動(dòng)估計(jì)搜索時(shí)間，體現(xiàn)了良好的改進(jìn)效果。

作者簡(jiǎn)介：

朱鑫磊（1997-），男，碩士生.研究領(lǐng)域：視頻編碼，圖像處理.

汪偉（1979-），男，博士，講師.研究領(lǐng)域：醫(yī)療影像處理與分析，醫(yī)用機(jī)器人.