一種基于寬鉆石搜索的改進(jìn)TZS算法

但鴻鍵，汪 偉

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

1 引 言

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

HEVC標(biāo)準(zhǔn)沿用了目前所廣泛使用的H.264視頻編碼標(biāo)準(zhǔn)的結(jié)構(gòu)框架，并在此編碼框架基礎(chǔ)上對(duì)H.264的各個(gè)環(huán)節(jié)都進(jìn)行了不同程度的改進(jìn)，使得總體編碼效果得到大幅度的提升，在同等視頻質(zhì)量情況下降低了50%的碼率.但是，編碼效果提升的同時(shí)也帶來了計(jì)算復(fù)雜度過高的問題[1-3].

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

提前終止策略是一種有效減少尋找最佳匹配點(diǎn)搜索次數(shù)的方法.Purnachand等提出一種基于TZS算法的全局搜索提前終止策略，對(duì)當(dāng)前塊的空間相鄰塊和時(shí)間相鄰塊的代價(jià)值進(jìn)行存儲(chǔ)，并將其中最小的值作為終止的閾值，有效地減少了算法的搜索耗時(shí)[4]；針對(duì)運(yùn)動(dòng)劇烈程度不同的視頻序列，余登超等利用統(tǒng)計(jì)學(xué)的概率來設(shè)置DS搜索的步長參考值，適當(dāng)?shù)靥^不必要的搜索，即通過選擇不同的閾值來提前結(jié)束搜索[5].

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

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

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

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

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

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

2 TZS標(biāo)準(zhǔn)算法流程

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

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

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

(1)

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

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

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

圖1 TZS標(biāo)準(zhǔn)算法初始網(wǎng)格搜索Fig.1 Initial grid search of TZS standard algorithm

在初始網(wǎng)格搜索中，搜索的最大點(diǎn)數(shù)如式(2)和式(3)所示：

NDS=8×floor(log2R)-4

(2)

NSq=8×floor(log2R)

(3)

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

當(dāng)搜索到最佳匹配塊、搜索到范圍的邊界或者在三次搜索后仍不能找到率失真更小的點(diǎn)時(shí)停止初始網(wǎng)絡(luò)搜索.然后，以最佳匹配塊與當(dāng)前塊的距離來決定是否進(jìn)行下一步的柵格搜索.

2.3 柵格搜索

在TZS標(biāo)準(zhǔn)搜索算法里，柵格搜索只會(huì)在最佳候選塊的距離大于設(shè)定的柵格搜索參數(shù)值時(shí)才會(huì)進(jìn)行的一種下采樣全搜索，柵格搜索是用于運(yùn)動(dòng)矢量與起始位置的距離過遠(yuǎn)時(shí)的搜索方法.在HM-16.14中，柵格搜索在一個(gè)正方形的范圍內(nèi)，搜索方式如圖2所示.

圖2 TZS標(biāo)準(zhǔn)算法柵格搜索Fig.2 Raster search ofclassical TZS standard algorithm

一般來說，柵格搜索參數(shù)值設(shè)定為5，是搜索范圍內(nèi)的采樣距離.若從初始網(wǎng)格搜索中獲得的最佳距離為0時(shí)，則停止搜索；若該最佳距離小于柵格采樣參數(shù)值時(shí)，則直接進(jìn)行精細(xì)搜索；若該最佳距離大于柵格采樣參數(shù)值時(shí)，就執(zhí)行柵格掃描，掃描的步長為柵格采樣參數(shù)值.

柵格搜索會(huì)在完整搜索范圍內(nèi)執(zhí)行，搜索范圍如式(4)所示，其所需的搜索點(diǎn)數(shù)如式(5)所示：

SR=N×N

(4)

(5)

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

2.4 精細(xì)搜索

為了確保搜索得到的運(yùn)動(dòng)矢量為全局最優(yōu)，需要對(duì)之前搜索所獲得的最佳候選塊進(jìn)行星型或柵格精細(xì)搜索.

1)星型精細(xì)搜索在優(yōu)化運(yùn)動(dòng)矢量的過程中，執(zhí)行步長為2的鉆石搜索或正方形搜索，直到搜索最佳運(yùn)動(dòng)矢量為1或者到搜索范圍的邊界時(shí)停止步長為2的鉆石或正方形搜索.若最佳運(yùn)動(dòng)矢量為1時(shí)，進(jìn)行兩點(diǎn)搜索找出最佳匹配塊；

2)柵格精細(xì)搜索執(zhí)行以2為搜索步長的柵格搜索，直到運(yùn)動(dòng)矢量為1或者到搜索范圍的邊界時(shí)，停止步長為2 的柵格搜索.若最佳運(yùn)動(dòng)矢量為1時(shí)，采取兩點(diǎn)搜索找出最佳匹配塊.

精細(xì)搜索是最終確定最佳匹配點(diǎn)的關(guān)鍵步驟，由精細(xì)搜索得出的搜索點(diǎn)代表了當(dāng)前幀中的運(yùn)動(dòng)物體在下一幀圖片上的最佳匹配位置.

3 改進(jìn)的TZS搜索算法

目前，在HM-16.14中使用的是TZS標(biāo)準(zhǔn)搜索算法，此算法與全搜索算法相比有著良好的運(yùn)算速度，同時(shí)也保證了視頻質(zhì)量.本文對(duì)TZS標(biāo)準(zhǔn)算法的搜索策略和搜索模型作了進(jìn)一步改進(jìn)，提出了一種改進(jìn)的TZS搜索算法，并于本小節(jié)對(duì)改進(jìn)算法進(jìn)行具體闡述.

本文提出的改進(jìn)算法具體流程如圖3所示.

圖3 改進(jìn)的TZS搜索流程圖Fig.3 Flow chat of modified TZS search

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

繼續(xù)沿用TZS標(biāo)準(zhǔn)算法中的確定起始點(diǎn)的方法，先預(yù)測當(dāng)前塊的運(yùn)動(dòng)矢量，再從預(yù)測的運(yùn)動(dòng)矢量中選取SAD匹配標(biāo)準(zhǔn)下最小值的位置，最后以該位置作為下一步搜索的起始搜索點(diǎn).

3.2 基于WDS的初始網(wǎng)格搜索

TZS標(biāo)準(zhǔn)算法比全搜索算法在運(yùn)動(dòng)估計(jì)時(shí)間和計(jì)算復(fù)雜度上有著顯著的降低，然而在運(yùn)動(dòng)估計(jì)中仍然存在大量的耗時(shí)和計(jì)算復(fù)雜度.尤其在找到最佳匹配點(diǎn)之前，需要進(jìn)行的搜索點(diǎn)數(shù)量還是有些龐大.

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

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

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

1)在搜索范圍內(nèi)，先搜索起始搜索點(diǎn)距離為1的上下左右4個(gè)點(diǎn)；

2)先使用水平方向步長為1，垂直方向?yàn)樗椒较虿介L兩倍的WDS搜索模式進(jìn)行塊匹配搜索，然后在之后每一次搜索的步長均以2的次冪增長，直到搜索至范圍邊界或3次搜索后仍無法得到率失真更小的最佳匹配點(diǎn)時(shí)，結(jié)束網(wǎng)格搜索；

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

在搜索匹配點(diǎn)后，檢測該匹配點(diǎn)是否為最佳的匹配點(diǎn).比較每次WDS搜索方法得到的最佳匹配候選點(diǎn)的率失真代價(jià)，逐步找到最佳匹配點(diǎn).若得到的最佳候選點(diǎn)與起始點(diǎn)的距離為1或2時(shí)，適當(dāng)?shù)乇容^該候選點(diǎn)周圍的幾個(gè)點(diǎn)來檢測該點(diǎn)是否是最佳匹配點(diǎn).

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

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

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

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

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

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

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

例如1.1為最佳候選點(diǎn)，比較1.1和3.8、3.11、3.12的左側(cè)、上側(cè)、右上的塊的運(yùn)動(dòng)矢量和零塊運(yùn)動(dòng)矢量的SAD值，將SAD值最小的那個(gè)點(diǎn)作為下次搜索的起點(diǎn).當(dāng)搜索3輪之后還沒找出比SAD值更小的點(diǎn)，停止網(wǎng)格搜索過程.

3.3 基于OARP的柵格搜索

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

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

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

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

圖5 改進(jìn)的TZS柵格搜索Fig.5 Raster search of modified TZS

HM-16.14中柵格搜索是一種步長為5的下采樣全搜索，使得PU塊的搜索在一個(gè)完整搜索過程中占用50%到90%的搜索時(shí)間.由圖中可知，運(yùn)動(dòng)矢量大多分布在搜索點(diǎn)的周圍、水平和垂直方向，而在距搜索點(diǎn)較遠(yuǎn)的非水平垂直方向幾乎沒有運(yùn)動(dòng)矢量分布.因此，可以適當(dāng)?shù)匾瞥@些距離較遠(yuǎn)的非水平垂直區(qū)域進(jìn)行柵格搜索，采用更小更高效的區(qū)域作為搜索范圍.

根據(jù)運(yùn)動(dòng)矢量分布特性，采用OARP搜索模板來進(jìn)行TZS算法中耗時(shí)最多的柵格搜索，縮小柵格搜索的范圍，確定最佳的匹配塊的分布情況.

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

采用OARP搜索模板保留了柵格搜索的規(guī)律性，不需要用到復(fù)雜的算法來自適應(yīng)調(diào)節(jié)最佳匹配塊的位置范圍，使得算法更易于在硬件平臺(tái)上實(shí)現(xiàn).

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

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

2)在第一步得到的范圍基礎(chǔ)上，去掉該正方形區(qū)域內(nèi)的左上、左下、右上、右下的4個(gè)角落區(qū)域；

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

3.4 精細(xì)搜索

經(jīng)過WDS網(wǎng)格搜索和OARP柵格搜索后，沿用TZS標(biāo)準(zhǔn)算法中的精細(xì)搜索方法，采用星型/柵格精細(xì)搜索找出最佳匹配候選點(diǎn)，作為最終確定的最佳匹配點(diǎn).

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

4.1 實(shí)驗(yàn)設(shè)定

4.1.1 測試數(shù)據(jù)庫

為了驗(yàn)證本文算法有效性，在參考軟件HM-16.14下實(shí)現(xiàn)該算法.由于要驗(yàn)證本文提出的算法的編碼性能，故測試了5類HEVC標(biāo)準(zhǔn)的測試序列，序列均為YUV格式.

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

4.1.2 算法評(píng)價(jià)指標(biāo)

為評(píng)定使用算法的優(yōu)劣，本文采取從算法的搜索時(shí)間和視頻質(zhì)量兩個(gè)方面來進(jìn)行分析和評(píng)價(jià)，分別對(duì)TZS標(biāo)準(zhǔn)搜索算法、基于OARP的TZS算法[15]和本文提出的改進(jìn)TZS搜索算法進(jìn)行了實(shí)驗(yàn)結(jié)果對(duì)比.

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

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

(6)

(7)

其中ΔTproposed和ΔTOARP分別為本文算法、基于OARP的TZS算法與HM-16.14中TZS標(biāo)準(zhǔn)算法的編碼時(shí)間變化.

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

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

實(shí)驗(yàn)中所使用的硬件平臺(tái)為酷睿I5-4200H處理器、2.8 GHz主頻和8GB的內(nèi)存.對(duì)應(yīng)的軟件配置為Windows1064位操作系統(tǒng)、yuvplayer視頻序列播放器以及Elecard HEVC Anlyzer編碼視頻檢測工具.

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

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

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

為了驗(yàn)證本文算法的效果，在上述的實(shí)驗(yàn)環(huán)境中進(jìn)行4組不同QP值的TZS標(biāo)準(zhǔn)搜索、基于OARP的TZS搜索[13]和本文的改進(jìn)搜索，4組不同QP值的實(shí)驗(yàn)結(jié)果的參數(shù)平均值如表1所示，PSNR為YUV視頻序列的峰值信噪比，Bitrate為編碼的碼率，T為TZS搜索的時(shí)間.

表1 不同TZS算法實(shí)驗(yàn)結(jié)果(QP=22，27，32，37)Table 1 Experimental results of different TZS algorithms(QP=22，27，32，37)

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

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

圖6是表示本文算法、基于OARP的TZS算法和TZS標(biāo)準(zhǔn)算法的編碼時(shí)間的柱狀圖.從圖6中可以清楚的看出，本文算法在搜索時(shí)間上的耗時(shí)要低于TZS標(biāo)準(zhǔn)搜索算法和基于OARP改進(jìn)的TZS的算法，展現(xiàn)出了本文算法良好的編碼速度.

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

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

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

4.3 實(shí)驗(yàn)分析

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

1)引入了WDS搜索，改進(jìn)了搜索方式，減少了初始網(wǎng)格搜索最佳點(diǎn)的次數(shù)，相比于DS搜索在相同PSNR時(shí)所需的Bitrate更少，在相同Bitrate時(shí)得到的PSNR更高.

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

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

但是本文算法也存在缺點(diǎn)，無法搜索到光柵搜索中某些運(yùn)動(dòng)復(fù)雜且不規(guī)則的物體在OARP模式外有極低概率存在的最佳匹配點(diǎn)，會(huì)將局部最佳匹配點(diǎn)當(dāng)成全局最佳匹配點(diǎn)，造成微小的視頻質(zhì)量損失.

5 結(jié)束語

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