一種基于寬鉆石搜索的改進TZS算法

但鴻鍵，汪 偉

(上海理工大學 光電信息與計算機工程學院，上海 200093)

1 引 言

近年來，隨著對短視頻和視頻直播中高清視頻、超清視頻需求量的迅速增長，視頻信息已經成為數字化生活中不可或缺的一部分.然而，由于原始視頻所具備的高分辨率和高幀頻特性，使得其包含的數據量十分龐大，給數據存儲和數據傳輸帶來了巨大的壓力.因而提高視頻的編碼性能和效率成為了該領域內的研究熱點，而高效視頻編碼(High Efficiency Video Coding，HEVC)所具備的優秀性能，使得該編碼標準得到了迅速的發展.

HEVC標準沿用了目前所廣泛使用的H.264視頻編碼標準的結構框架，并在此編碼框架基礎上對H.264的各個環節都進行了不同程度的改進，使得總體編碼效果得到大幅度的提升，在同等視頻質量情況下降低了50%的碼率.但是，編碼效果提升的同時也帶來了計算復雜度過高的問題[1-3].

在HEVC標準中，塊匹配運動估計中的TZS(Test Zone Search)標準算法是目前運動估計算法中應用最廣泛的方法之一，而TZS搜索算法的高計算復雜度在一定程度上影響了算法搜索效率，如何提升TZS的搜索效率是當前研究的熱點之一.目前，對TZS算法搜索效率的提升主要是從以下幾個方面來改進：提前終止策略、最佳搜索點的搜索方式、自適應調整搜索范圍和柵格搜索模式.通過各個方面的改進，能夠有效地減少TZS搜索算法的計算復雜度.

提前終止策略是一種有效減少尋找最佳匹配點搜索次數的方法.Purnachand等提出一種基于TZS算法的全局搜索提前終止策略，對當前塊的空間相鄰塊和時間相鄰塊的代價值進行存儲，并將其中最小的值作為終止的閾值，有效地減少了算法的搜索耗時[4]；針對運動劇烈程度不同的視頻序列，余登超等利用統計學的概率來設置DS搜索的步長參考值，適當地跳過不必要的搜索，即通過選擇不同的閾值來提前結束搜索[5].

此外，采用搜索效率更高的搜索方式也可有效地縮短算法運行時間.Li 等將TZS標準算法中的鉆石搜索(Diamond Search，DS)和正方形搜索用六邊形搜索來替代[6]；JEA等提出在初始網格搜索和精細搜索階段，使用旋轉五邊形搜索(Rotating pentagon search，RPS)算法，使用更少的搜索點來尋找最佳匹配點[7]；Purnachand等在TZS算法的網格搜索階段和精細搜索階段使用步長逐漸變大的水平和垂直六邊形搜索

1https：//vcgit.hhi.fraunhofer.de/jct-vc/HM/-/tree/HM-16.14

來代替鉆石搜索，即采用的旋轉六邊形搜索模式也取得了較好的效果[8]，該搜索方式相比于DS搜索具有更高的搜索效率；Abdelrahman等先進行三次DS搜索，再采用半像素六邊形搜索(Half-Pel Hexagon Search)最佳匹配點，保留了算法的搜索精度[9]；Nguyen 等提出用旋轉寬鉆石搜索算法代替TZS標準算法中的鉆石搜索和正方形搜索，用可變步長采樣搜索方式，從而有效減少搜索最佳匹配點的次數[10].

除上述兩類方法外，自適應地減少搜索范圍也是一種有效地減少TZS算法中搜索點數目的方法.Varma等提出在編碼幀和參考幀中分別使用自適應外部和內部搜索范圍縮減的算法，該算法根據空間相鄰塊的運動矢量差(Motion Vector Difference，MVD)和搜索中心的絕對差累加值(Sum of Absolute Difference，SAD)來自適應變化搜索范圍[11]；Zhang等通過在預測精度內自適應地調整搜索范圍，并利用運動矢量殘差估計來達到提升編碼效率的目的[12].

需要著重指出的是，柵格搜索是TZS算法中最耗時的步驟，提高柵格搜索效率是減少編碼時間的重要環節.Goncalves等提出一種八邊形-十字柵格模式(Octagonal-Axis Raster Pattern，OARP)的柵格搜索，根據運動矢量的分布規律調整柵格搜索范圍，有效地提升了算法在柵格搜索中的搜索效率[13]；Nghia等將柵格搜索范圍分成多個區域，按照順序進行分區柵格搜索，當檢測到匹配點時就退出柵格搜索的遍歷過程，有效地減少柵格搜索總體的搜索點數量[14].

本文為降低搜索過程中的計算復雜度，縮短編碼時間，在HM-16.141的TZS標準算法的基礎上進行了如下創新：首先，在初始網格搜索階段，創新性地引入了搜索效率更高的寬鉆石搜索(Wide Diamond Search，WDS)代替DS搜索，從而能以更少的搜索次數搜索出最佳匹配候選點.其次，在柵格搜索階段，通過分析全搜索過程中運動矢量的十字中心偏置分布的特點，提出OARP的柵格搜索模型，能減少近75%的柵格搜索點數，有效地縮短了運動估計過程中算法的搜索時間，提高了視頻編碼效率.實驗證明，對TZS標準算法改進后，能提高運動估計的搜索效率，并保持搜索算法的規律性，使算法易于在硬件上實現.

2 TZS標準算法流程

2.1 起始搜索點確定

找到起始搜索點是運動估計的前提，此過程需要先計算當前預測塊左側、上側、右上的運動矢量，再對零塊運動矢量和當前塊運動矢量進行比較，最后從所有的運動矢量中選擇SAD值最小的點，并以該點作為TZS搜索算法下一步搜索的起始搜索點.

SAD的計算方法如式(1)所示：

(1)

其中(i，j)是搜索點在相鄰兩幀之間的位移矢量，fk和fk-1分別是當前幀和前一幀的灰度值，M和N是當前塊的長和寬，m和n是像素坐標值.

2.2 初始網格搜索

在TZS標準搜索算法里，初始網格搜索是在特定的搜索范圍內，使用搜索步長為2n(n=0，1，2，3…)的鉆石或正方形的搜索模式進行塊匹配搜索，從而獲得最佳的候選塊，具體如圖1(a)和圖1(b)所示.

圖1 TZS標準算法初始網格搜索Fig.1 Initial grid search of TZS standard algorithm

在初始網格搜索中，搜索的最大點數如式(2)和式(3)所示：

NDS=8×floor(log2R)-4

(2)

NSq=8×floor(log2R)

(3)

其中，NDS是表示鉆石搜索的搜索點數，NSq是表示正方形搜索的點數，floor是向下取整數，R表示搜索范圍邊長.

當搜索到最佳匹配塊、搜索到范圍的邊界或者在三次搜索后仍不能找到率失真更小的點時停止初始網絡搜索.然后，以最佳匹配塊與當前塊的距離來決定是否進行下一步的柵格搜索.

2.3 柵格搜索

在TZS標準搜索算法里，柵格搜索只會在最佳候選塊的距離大于設定的柵格搜索參數值時才會進行的一種下采樣全搜索，柵格搜索是用于運動矢量與起始位置的距離過遠時的搜索方法.在HM-16.14中，柵格搜索在一個正方形的范圍內，搜索方式如圖2所示.

圖2 TZS標準算法柵格搜索Fig.2 Raster search ofclassical TZS standard algorithm

一般來說，柵格搜索參數值設定為5，是搜索范圍內的采樣距離.若從初始網格搜索中獲得的最佳距離為0時，則停止搜索；若該最佳距離小于柵格采樣參數值時，則直接進行精細搜索；若該最佳距離大于柵格采樣參數值時，就執行柵格掃描，掃描的步長為柵格采樣參數值.

柵格搜索會在完整搜索范圍內執行，搜索范圍如式(4)所示，其所需的搜索點數如式(5)所示：

SR=N×N

(4)

(5)

其中，SR是柵格搜索范圍，N是搜索范圍的邊長，Nraster是柵格搜索需要搜索的最大點數，floor是向下取整，R是柵格搜索的步長.

2.4 精細搜索

為了確保搜索得到的運動矢量為全局最優，需要對之前搜索所獲得的最佳候選塊進行星型或柵格精細搜索.

1)星型精細搜索在優化運動矢量的過程中，執行步長為2的鉆石搜索或正方形搜索，直到搜索最佳運動矢量為1或者到搜索范圍的邊界時停止步長為2的鉆石或正方形搜索.若最佳運動矢量為1時，進行兩點搜索找出最佳匹配塊；

2)柵格精細搜索執行以2為搜索步長的柵格搜索，直到運動矢量為1或者到搜索范圍的邊界時，停止步長為2 的柵格搜索.若最佳運動矢量為1時，采取兩點搜索找出最佳匹配塊.

精細搜索是最終確定最佳匹配點的關鍵步驟，由精細搜索得出的搜索點代表了當前幀中的運動物體在下一幀圖片上的最佳匹配位置.

3 改進的TZS搜索算法

目前，在HM-16.14中使用的是TZS標準搜索算法，此算法與全搜索算法相比有著良好的運算速度，同時也保證了視頻質量.本文對TZS標準算法的搜索策略和搜索模型作了進一步改進，提出了一種改進的TZS搜索算法，并于本小節對改進算法進行具體闡述.

本文提出的改進算法具體流程如圖3所示.

圖3 改進的TZS搜索流程圖Fig.3 Flow chat of modified TZS search

3.1 起始搜索點確定

繼續沿用TZS標準算法中的確定起始點的方法，先預測當前塊的運動矢量，再從預測的運動矢量中選取SAD匹配標準下最小值的位置，最后以該位置作為下一步搜索的起始搜索點.

3.2 基于WDS的初始網格搜索

TZS標準算法比全搜索算法在運動估計時間和計算復雜度上有著顯著的降低，然而在運動估計中仍然存在大量的耗時和計算復雜度.尤其在找到最佳匹配點之前，需要進行的搜索點數量還是有些龐大.

為進一步提高視頻編碼效率，本文引入了基于WDS的初始網格搜索策略，將前兩次DS搜索過程中所需要遍歷的搜索點數減小了一半，從而極大地減小了搜索算法的計算復雜度.

使用WDS快速搜索算法代替初始網格搜索算法中使用的鉆石搜索算法，如圖4(a)所示.

圖4 WDS搜索示意圖Fig.4 Search steps for WDS

1)在搜索范圍內，先搜索起始搜索點距離為1的上下左右4個點；

2)先使用水平方向步長為1，垂直方向為水平方向步長兩倍的WDS搜索模式進行塊匹配搜索，然后在之后每一次搜索的步長均以2的次冪增長，直到搜索至范圍邊界或3次搜索后仍無法得到率失真更小的最佳匹配點時，結束網格搜索；

3)最后比較最佳搜索距離與柵格采樣參數的大小，根據比較結果來判斷是否進行柵格搜索.

在搜索匹配點后，檢測該匹配點是否為最佳的匹配點.比較每次WDS搜索方法得到的最佳匹配候選點的率失真代價，逐步找到最佳匹配點.若得到的最佳候選點與起始點的距離為1或2時，適當地比較該候選點周圍的幾個點來檢測該點是否是最佳匹配點.

最佳匹配點的具體檢測示例如圖4(b)所示.

·若1.1為最佳候選點，將此點與3.8、3.11、3.12比較；

·若1.2為最佳候選點，將此點與3.4、3.5、3.6、3.7比較；

·若1.3為最佳候選點，將此點與3.9、3.10、3.13比較；

·若1.4為最佳候選點，將此點與3.14、3.15、3.16、3.17比較；

·若2.1為最佳候選點，將此點與3.1、3.2、3.3比較；

·若2.2為最佳候選點，將此點與3.18、3.19、3.20比較.

例如1.1為最佳候選點，比較1.1和3.8、3.11、3.12的左側、上側、右上的塊的運動矢量和零塊運動矢量的SAD值，將SAD值最小的那個點作為下次搜索的起點.當搜索3輪之后還沒找出比SAD值更小的點，停止網格搜索過程.

3.3 基于OARP的柵格搜索

由于柵格搜索需要進行全搜索模式下的子采樣搜索，且覆蓋整個搜索范圍，這是整個搜索過程中最復雜的步驟，該步驟所耗費的平均搜索時間在全部TZS搜索過程中占用約80%的比例.另外，由研究表明[15]，運動矢量的分布具有中心

2https：//hevc.hhi.fraunhofer.de/

十字偏置的特性，如圖5(a)所示，即在初始搜索點周圍、水平和垂直方向上分布了絕大多數的運動矢量.然后對TZS搜索算法的復雜度進行分析，并于尺寸不同的預測單元中分析整個算法在各個步驟中的耗時時長.

圖5(a)是3個具有代表性的高分辨率YUV視頻序列的運動矢量平均分布圖，即BQTerrace、YachtRide和Cactuse序列.像素灰度值代表不同的運動矢量分布概率，在搜索范圍中心的附近區域和水平垂直方向上的區域的運動矢量分布最為密集.隨著與搜索中心的距離增加，運動矢量分布概率在逐漸減小.

圖5 改進的TZS柵格搜索Fig.5 Raster search of modified TZS

HM-16.14中柵格搜索是一種步長為5的下采樣全搜索，使得PU塊的搜索在一個完整搜索過程中占用50%到90%的搜索時間.由圖中可知，運動矢量大多分布在搜索點的周圍、水平和垂直方向，而在距搜索點較遠的非水平垂直方向幾乎沒有運動矢量分布.因此，可以適當地移除這些距離較遠的非水平垂直區域進行柵格搜索，采用更小更高效的區域作為搜索范圍.

根據運動矢量分布特性，采用OARP搜索模板來進行TZS算法中耗時最多的柵格搜索，縮小柵格搜索的范圍，確定最佳的匹配塊的分布情況.

雖然OARP搜索模板使用的搜索范圍約為原搜索范圍的25%，卻覆蓋了絕大多數的最佳匹配塊.OARP搜索模板顯著降低了TZS算法的復雜度，大概率地覆蓋了最佳匹配塊所在區域，保證了運動估計編碼的效率.

采用OARP搜索模板保留了柵格搜索的規律性，不需要用到復雜的算法來自適應調節最佳匹配塊的位置范圍，使得算法更易于在硬件平臺上實現.

OARP搜索模板的形狀如圖5(b)所示：

1)OARP搜索模板選取原搜索范圍的正中央的25%的區域作為搜索范圍；

2)在第一步得到的范圍基礎上，去掉該正方形區域內的左上、左下、右上、右下的4個角落區域；

3)在第二步的范圍基礎上加上水平和垂直的區域作為最終的搜索范圍.

3.4 精細搜索

經過WDS網格搜索和OARP柵格搜索后，沿用TZS標準算法中的精細搜索方法，采用星型/柵格精細搜索找出最佳匹配候選點，作為最終確定的最佳匹配點.

4 實驗結果與分析

4.1 實驗設定

4.1.1 測試數據庫

為了驗證本文算法有效性，在參考軟件HM-16.14下實現該算法.由于要驗證本文提出的算法的編碼性能，故測試了5類HEVC標準的測試序列，序列均為YUV格式.

5類序列分別為A類(2560×1080)，B 類(1920×720)，C 類(832×480)，D 類(416×240)以及E類(1280×720)，A類、B類、D類和E類包含兩個不同運動激烈程度的序列，C類中包含了兩個運動程度類似的序列，總共10個序列.

4.1.2 算法評價指標

為評定使用算法的優劣，本文采取從算法的搜索時間和視頻質量兩個方面來進行分析和評價，分別對TZS標準搜索算法、基于OARP的TZS算法[15]和本文提出的改進TZS搜索算法進行了實驗結果對比.

實驗中分別收集了編碼時間、Bitrate和PSNR(peak signal-to-noise rate)等參數，并基于HM-16.14的編碼器上的編碼時間變化ΔT、BDBR(Bj?ntegaard delta bit rate)、BDPSNR(Bj?ntegaard delta peak signal-to-noise rate)2等數據來分析編碼效果[16].

1)本文基于編碼時間來比較算法的編碼速度，其編碼時間變化ΔT計算方法如式(6)、式(7)所示：

(6)

(7)

其中ΔTproposed和ΔTOARP分別為本文算法、基于OARP的TZS算法與HM-16.14中TZS標準算法的編碼時間變化.

2)BDBR表示相同PSNR條件下碼率的變化百分比，BDPSNR表示相同碼率條件下PSNR的變化量，兩者參數都是用于視頻編碼質量和算法編碼性能的比對.

4.1.3 實驗環境及參數設定

實驗中所使用的硬件平臺為酷睿I5-4200H處理器、2.8 GHz主頻和8GB的內存.對應的軟件配置為Windows1064位操作系統、yuvplayer視頻序列播放器以及Elecard HEVC Anlyzer編碼視頻檢測工具.

使用的測試序列A類、B類、C類、E類序列的測試幀數為100幀，D類的BQSquare使用600幀，BlowingBubbles使用500幀.

HM-16.14中配置參數設置如下：QP的值為37、32、27、22，其它配置參數保留默認值(最大CU尺寸為64×64，最大劃分深度為4).

4.2 實驗結果

為了驗證本文算法的效果，在上述的實驗環境中進行4組不同QP值的TZS標準搜索、基于OARP的TZS搜索[13]和本文的改進搜索，4組不同QP值的實驗結果的參數平均值如表1所示，PSNR為YUV視頻序列的峰值信噪比，Bitrate為編碼的碼率，T為TZS搜索的時間.

表1 不同TZS算法實驗結果(QP=22，27，32，37)Table 1 Experimental results of different TZS algorithms(QP=22，27，32，37)

以此實驗結果對比基于OARP的TZS算法和本文算法，表2中是4組不同QP值的基于OARP的TZS算法、本文算法和TZS標準算法的平均實驗對比結果，結果表明本文算法比TZS標準算法平均減少約26.59%的編碼耗時，在Tennis 和PeopleOnStreet運動復雜的高分辨率序列中甚至減少40%以上耗時，BDBR平均減少了0.023%，BDPSNR平均增長了0.0149dB.與基于OARP的TZS算法[13]相比，本文算法也顯著縮短了編碼耗時，并且BDBR和BDPSNR的平均變化量更小，以更少的Bitrate表現出相同的PSNR，體現出了更加優異的視頻編碼效果.

表2 不同TZS算法平均對比結果(QP=22，27，32，37)Table 2 Averageresults comparison of different TZS algorithms(QP=22，27，32，37)

圖6是表示本文算法、基于OARP的TZS算法和TZS標準算法的編碼時間的柱狀圖.從圖6中可以清楚的看出，本文算法在搜索時間上的耗時要低于TZS標準搜索算法和基于OARP改進的TZS的算法，展現出了本文算法良好的編碼速度.

圖6 3種不同算法搜索算法的搜索時間對比柱狀圖Fig.6 Search time comparison bar chart of 3 different search algorithms

圖7為3種搜索算法的RD曲線圖.由于10個序列中各算法的RD曲線都十分接近，因此，從中取4組典型曲線作為代表.由RD曲線可以看出，本文提出的改進TZS搜索算法與其它兩種算法，在同等碼率的情況下，PSNR幾乎保持不變.圖7說明了本文算法能夠在明顯縮短編碼時間的情況下仍保持了良好的視頻質量.

圖7 4種不同序列的RD曲線Fig.7 RD of curve of 4 different sequences

4.3 實驗分析

通過分析實驗結果，本文提出改進的TZS搜索算法可有效縮短TZS標準算法在同等客觀視頻質量下的搜索耗時.與TZS標準算法、基于OARP的TZS算法在PSNR相同情況下，所需要的Bitrate有著少量的減少，但保持了幾乎相同的視頻質量.本文算法之所以能夠縮短搜索耗時并保持視頻質量基本不受影響的主要原因在于：

1)引入了WDS搜索，改進了搜索方式，減少了初始網格搜索最佳點的次數，相比于DS搜索在相同PSNR時所需的Bitrate更少，在相同Bitrate時得到的PSNR更高.

2)OARP搜索模板的使用，減少了近75%的低效搜索區域，使得搜索的效率得到明顯的提高.

3)對最佳候選點精細搜索，確定全局最佳匹配點，為編碼序列的視頻質量提供了有效保障.

但是本文算法也存在缺點，無法搜索到光柵搜索中某些運動復雜且不規則的物體在OARP模式外有極低概率存在的最佳匹配點，會將局部最佳匹配點當成全局最佳匹配點，造成微小的視頻質量損失.

5 結束語

針對HEVC幀間預測的運動估計中的高復雜度和高耗時問題，基于HM-16.14中的TZS標準算法搜索結構，本文提出了一種改進TZS搜索算法.一方面，在初始網格搜索中，用WDS搜索代替DS搜索；另一方面，在柵格搜索中，用OARP的搜索模板進行下采樣全搜索縮小了光柵搜索的范圍，減少了搜索過程中的搜索點數，提高了視頻的編碼效率.實驗結果表明，本文提出的改進TZS搜索算法提高了搜索效率，較好的縮短了編碼耗時；同時，BDPSNR和BDBR沒有明顯變化，視頻質量保持良好.總之，該算法對視頻編碼有著一定的實際應用價值.