基于條件判據改進的提前終止運動估計算法

朱鑫磊　汪偉

關鍵詞：運動估計；塊匹配提前終止；八邊形-“十”字柵格搜索；精細搜索

中圖分類號：TP391 文獻標識碼：A

1引言（Introduction）

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

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

2運動估計標準算法（Motion estimation standardalgorithm）

2.1確定起始搜索點

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

2.2初始網格搜索

HEVC標準算法中，初始網格搜索階段首先將起始搜索點作為當前塊匹配搜索的中心，接著以步長為1、2、4、8、16、32、64進行鉆石搜索（Diamond Search）[16]或者柵格搜索，選取率失真代價最小的點作為初始網格搜索階段的預測矢量。鉆石搜索如圖1（a）所示，柵格搜索如圖1（b）所示。

2.3兩點搜索

若初始網格所得到最佳候選點步長為1，就會導致該點周圍有兩個點沒有搜索到，于是補充兩點搜索，若得到的最佳點大于某個閾值，則以該點為起點，在一定范圍進行全搜索，找到率失真代價最小點。

2.4精細搜索

以兩點搜索所得最優點為新的起始搜索點，繼續跳轉到初始網格搜索步驟中進行精細搜索，直到兩次得到的精細搜索結果為一致時，停止搜索[17]，此時得到的就是最優預測矢量。

3改進后的運動估計算法（Improved motionestimation algorithm）

3.1起始搜索點的確定

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

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

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

當一個劃分深度為d 的編碼單元塊進行完整的編碼步驟，終止編碼剩余深度的選擇過程等價于在率失真優化過程中采用的候選集：

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

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

八邊形-“十”字柵格搜索模板選取標準柵格搜索正中央25％的區域作為搜索范圍，在此基礎上，進一步縮小搜索范圍，將這25％的柵格搜索區域四個角的范圍忽略不計，因為這四個角落與中心搜索點距離較遠，并且所含的運動矢量很少。同時，增加水平和垂直方向上的搜索，使得搜索更加精確，節約了搜索時間。按照該方式進行柵格搜索，可以在保證視頻質量的情況下，節約一些搜索時間。八邊形-“十”字柵格搜索模型如圖3所示。

3.4精細搜索

精細搜索經過分析，決定采取鉆石搜索或者柵格搜索的方式來完成。為了找到率失真代價最小的點，所以將會首先以搜索步長1進行鉆石搜索，然后在此基礎上采取步長為2、4、8、16、32、64……這種方式繼續進行鉆石搜索，最終將會有兩種情況出現，一種是搜索到了邊界，不得已結束搜索模式，另一種是找到了最佳運動矢量為1的點，這樣也可以停止精細搜索，將找到的最優矢量為1的點再進行兩點搜索，這樣就找到了最佳匹配塊，以這種方式對其他塊進行搜索，就可以完成對圖片幀的精細搜索。

當遇到了搜索邊界，不得以停止搜索的情況時，將會采取柵格搜索方式，將初始網格搜索得到的點與閾值進行比較，將大于閾值的點找出來[21]，并且將該點作為中心，進行步長為2的柵格搜索，遍歷搜索區域，得到的率失真代價最小點就是最優點。該方式雖然相對煩瑣并且會浪費一定的搜索時間，但是準確率在很大程度上得到滿足，并且基本不會發生重復搜索的情況，保證了搜索的準確率。

4實驗結果與分析（Experimental results andanalysis）

4.1建立測試數據庫

4.1.1 最優預測點測試數據庫

為驗證算法的有效性， 選取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）四組視頻編碼測試序列，根據最佳匹配點為預測矢量點的次數在運動估計算法調用總次數中所占的比重，判斷該方法的有效性。

4.1.2編碼單元塊提前終止策略測試數據庫

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

4.1.3改進后運動估計算法測試數據庫

采用與“ 4 . 1 . 2 ” 部分中相同的測試數據庫， 即選取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）四組視頻編碼測試序列，測試序列幀數均為500 幀。

4.2實驗參數及環境設置

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

4.3算法評估指標

采用最佳匹配點為最優預測點的次數在運動估計中調用總次數中所占的比重，判斷最優預測點與最佳匹配點的相近程度。

4.4 實驗結果

4.4.1 最優預測點為最佳匹配點概率

由表1計算可知，改進之后得到的最優預測點為最佳匹配點的平均概率為71.51％，尤其是圖像中存在很多相對靜止和相對平坦區域的Vidyo4序列，最優預測點為最佳匹配點的概率達到了75.15％，體現了很好的改進效果。

4.4.2編碼單元塊提前終止策略測試結果

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

4.4.3改進后的運動估計算法實驗結果

為了驗證本文提出算法的效果，在實驗環境中進行四組不同量化參數值的運動估計標準搜索和本文改進搜索，編碼得到四組不同量化參數值的峰值信噪比（PSNR）、比特率和運動估計搜索時間的參數平均值，Bitrate為編碼的碼率，T為運動估計搜索時間。由實驗結果可知，改進后的算法在基本不影響視頻質量的情況下，提高了編碼速度，降低了算法的計算復雜度，節約了時間。具體結果如表3所示。

5結論（Conclusion）

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

作者簡介：

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

汪偉（1979-），男，博士，講師.研究領域：醫療影像處理與分析，醫用機器人.