曹騰飛, 史媛媛

1(青海大學(xué) 計(jì)算機(jī)技術(shù)與應(yīng)用系, 西寧 810016)

2(西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院, 西安 710071)

隨著智能終端的普及使得視頻應(yīng)用越來越多樣化,涉及的視頻內(nèi)容豐富多樣, 人們對(duì)視頻分辨率的要求也隨之水漲船高[1], 對(duì)視頻編碼壓縮和傳輸提出更高的要求. 2013年JCT-VC (Joint Collaborative Team on Video Coding)正式發(fā)布了新一代高效視頻編碼標(biāo)準(zhǔn)(High Efficiency Video Coding, HEVC)標(biāo)準(zhǔn)[2], 又稱H.265, 由于新標(biāo)準(zhǔn)HEVC采用了靈活的四叉樹自適應(yīng)存儲(chǔ)結(jié)構(gòu)、35種的幀內(nèi)預(yù)測(cè)(包括planner 模式和 DC模式)模式、包括運(yùn)動(dòng)信息融合技術(shù)(Merge)以及基于Merge的Skip模式的幀間預(yù)測(cè)模式、自適應(yīng)環(huán)路濾波等新技術(shù)[3], 這些技術(shù)的改進(jìn)使得HEVC比H.264節(jié)省了50%左右的編碼率[4]. 這些新的編碼技術(shù)在提高編碼效率的同時(shí), 也增加了計(jì)算復(fù)雜度, 特別是編碼器為獲得最佳CU四叉樹劃分所采用的全深度搜索方法需要大量的計(jì)算時(shí)間, 這極大地提高了HEVC編碼器的復(fù)雜度.

目前已經(jīng)有一些研究學(xué)者針對(duì)CU四叉樹劃分計(jì)算復(fù)雜度高的問題提出眾多優(yōu)化算法來降低計(jì)算復(fù)雜度. 文獻(xiàn)[5]提出了自適應(yīng) CU 深度遍歷的算法, 利用空域相關(guān)性來預(yù)測(cè)當(dāng)前編碼塊的深度值, 而大部分的編碼塊還是要遍歷3個(gè)CU以上的深度, 所以該方法節(jié)省的時(shí)間相當(dāng)有限. 文獻(xiàn)[6]通過比較時(shí)空相鄰 CU 的深度, 來判斷是否可以跳過當(dāng)前深度 CU 的預(yù)測(cè)編碼.文獻(xiàn)[7]采用時(shí)域空域相結(jié)合的預(yù)測(cè)方式, 通過相鄰編碼塊深度值加權(quán)方式來預(yù)測(cè)當(dāng)前編碼塊的深度值. 雖然這種方法在很大程度上減少了遍歷范圍, 但沒有考慮到不同視頻序列之間的差異性. 文獻(xiàn)[8]根據(jù)空域相關(guān)性自適應(yīng)地決定當(dāng)前 CU 深度的最大值和最小值.顯然, 這種僅根據(jù)空域的相關(guān)性的方法降低的復(fù)雜度是有限的, 且其預(yù)測(cè)深度值的準(zhǔn)確度也不高. 文獻(xiàn)[9–11]通過提前終止四叉樹劃分的遍歷對(duì)CU結(jié)構(gòu)進(jìn)行快速?zèng)Q策, 依據(jù)當(dāng)前待編碼CU的率失真代價(jià)(RDcost)與閾值Thre間的大小, 判斷是否要進(jìn)行下一步的遞歸劃分, 但當(dāng)圖像細(xì)節(jié)較多時(shí)提高的效率不高.文獻(xiàn)[12]在幀內(nèi)預(yù)測(cè)前利用相鄰已編碼CU的深度對(duì)當(dāng)前CU的深度進(jìn)行預(yù)判斷; 在幀內(nèi)預(yù)測(cè)時(shí)利用當(dāng)前CU的率失真代價(jià)與預(yù)先定義的閾值進(jìn)行對(duì)比判斷, 跳過一些不合適所屬區(qū)域內(nèi)容的編碼單元尺寸類型的編碼過程. 文獻(xiàn)[13]提出一種基于時(shí)空相關(guān)性的編碼單元深度決策算法. 融合關(guān)聯(lián)幀編碼單元的深度信息及當(dāng)前幀相鄰編碼單元的深度信息, 從而預(yù)測(cè)當(dāng)前編碼單元的深度范圍.

針對(duì)以上問題, 本文綜合考慮了編碼效率和時(shí)間損耗, 通過優(yōu)化CU四叉樹結(jié)構(gòu)劃分的遍歷過程, 提出了一種CU結(jié)構(gòu)快速劃分算法. 通過考慮時(shí)空域的相關(guān)性和二分法的高效性對(duì)編碼單元深度決策算進(jìn)行改進(jìn)法, 使得優(yōu)化后的結(jié)果在基本不改變圖像的質(zhì)量與輸出碼率的情況下, 提高了編碼時(shí)間.

1 HEVC的CU深度決策

為了靈活有效的表示視頻編碼內(nèi)容, HEVC為圖像的劃分定義了一套全新的分割模式, 包括編碼單元(Coding Unit, CU)、預(yù)測(cè)單元 (Prediction Unit, PU)和變換單元(Transform Unit, TU)3個(gè)概念描述整個(gè)編碼過程.其中CU類似于 H．264 中的宏塊或子宏塊, 每個(gè)CU均為2N×2N的像素塊, 是HEVC編碼的基本單元, 目前可變范圍為64×64至8×8. 圖像首先以最大編碼單元(LCU, 如64×64塊)為單位進(jìn)行編碼, 在LCU內(nèi)部按照四叉樹結(jié)構(gòu)進(jìn)行子塊劃分, 直至成為最小編碼單元(SCU, 如8×8塊)為止, 對(duì)應(yīng)的分割深度分別為 0、1、2 和 3, 如圖1 所示. 在 HEVC 的編碼過程中, 通過比較四叉樹結(jié)構(gòu)(圖2)中本層CU 與下層 4個(gè)子CU的 RDcost 大小來決定 CU 是否需要?jiǎng)澐? 進(jìn)而決定 LCU 的最終劃分方式, 如圖2所示每一個(gè)CTU的四叉樹遞歸劃分過程如下.

步驟1. 首先進(jìn)行CU的劃分過程. 對(duì)于每個(gè)64×64深度Depth=0的最大編碼單元LCU進(jìn)行預(yù)測(cè)編碼, 同時(shí), 該CU還要進(jìn)行各種PU預(yù)測(cè)和相應(yīng)的模式選擇, 最終根據(jù)公式(1)得到率失真代價(jià).

其中, SSE表示使用預(yù)測(cè)模式計(jì)算的殘差平方和, λ表示拉格朗日系數(shù); bits表示使用當(dāng)前預(yù)測(cè)模式下進(jìn)行編碼的碼率.

步驟2. 將64×64的編碼單元?jiǎng)澐譃?個(gè)32×32的子CU, 每個(gè)子 CU的尺寸大小是 32×32, 深度Depth=1. 同理對(duì)每個(gè)子單元進(jìn)行預(yù)測(cè)編碼, 并計(jì)算各自的率失真代價(jià)值. 如此遞歸的劃分下去, 直至劃分到最小的編碼單元8×8, 深度Depth=3時(shí)便不再劃分.

圖1 四叉樹結(jié)構(gòu)

步驟3. 從Depth為0的CU開始進(jìn)行CU深度劃分過程, 如果4個(gè)32×32大小的子CU的率失真代價(jià)之和大于于其對(duì)應(yīng)的64×64大小的CU的率失真代價(jià),則選擇 64×64 的 CU; 否則, 選擇 32×32 的 CU. 如此遞歸下去, 直到選到Depth為0的 CU. 至此, 當(dāng)前LCU的深度決策過程完成.

圖2 CU的深度分割示意圖

為了能夠獲取最佳的塊劃分方式, HEVC編碼器使用全深度搜索方法. 在確定一個(gè)LCU的最終深度算法中, 需要對(duì)CU深度進(jìn)行0～3次的全遍歷,總共需要進(jìn)行1+4+4×4+4×4×4=85次CU尺寸選擇的率失真代價(jià)計(jì)算, 而每個(gè)CU還要進(jìn)行各種PU預(yù)測(cè)和模式選擇的率失真代價(jià)計(jì)算. 這使得編碼器的復(fù)雜度過高, 無法滿足編碼器的實(shí)時(shí)應(yīng)用, 因此降低編碼器的復(fù)雜度, 提高編碼速度具有非常重要的應(yīng)用價(jià)值.

2 算法介紹

2.1 幀間時(shí)空域的相關(guān)性

由于在視頻序列是由連續(xù)的圖像序列幀構(gòu)成, 則相鄰幀之間具有很強(qiáng)的關(guān)聯(lián)性, 即空間相關(guān)性的存在.由于存在空間相關(guān)性, 因此HEVC編碼幀與編碼幀之間CU的分割方式也存在極強(qiáng)的關(guān)聯(lián)性. 為了分析時(shí)空相鄰CU劃分深度的相關(guān)性, 首先通過5類官方的測(cè)試序列ClassA～E進(jìn)行編碼測(cè)試, 測(cè)試詳情如表1所示. 時(shí)空相鄰CU劃分深度的相關(guān)統(tǒng)計(jì)結(jié)果如表2所示[14].

表1 通用測(cè)試序列的詳細(xì)情況

通過表2的數(shù)據(jù)分析可知, 當(dāng)前CU的最優(yōu)化分深度與前一幀相同位置的CU之間有較強(qiáng)的相關(guān)性,因此可以利用前一幀相同位置的CU的劃分深度對(duì)當(dāng)前LCU的最優(yōu)四叉樹結(jié)構(gòu)進(jìn)行預(yù)測(cè).

表2 時(shí)空相鄰CU的相關(guān)性(單位: %)

2.2 二分深度劃分決策算法

在HEVC視頻編碼標(biāo)準(zhǔn)中, 當(dāng)視頻圖像比較平坦,內(nèi)容變化緩慢時(shí), 針對(duì)它的編碼單元大多選擇了大尺寸類型; 當(dāng)視頻圖像比較復(fù)雜, 細(xì)節(jié)比較豐富時(shí), 針對(duì)它的編碼單元大多選擇了小尺寸類型; 使用HEVC測(cè)試模型HM15.0下對(duì)5類官方的測(cè)試序列ClassA～E進(jìn)行編碼測(cè)試, 通過統(tǒng)計(jì)分析出不同量化參數(shù)QP下編碼單元CU的分布情況, 見表3.

表3 不同QP下編碼單元CU的分布(單位: %)

從表3可以看出, 在測(cè)試序列中最小劃分深度CU結(jié)構(gòu)(64×64)僅僅占10%左右. 而在HM15.0中從劃分深度最小的CU結(jié)構(gòu)開始遍歷, 那么大部分CU需要花費(fèi)大量的時(shí)間效率進(jìn)行層層遍歷, 計(jì)算復(fù)雜度高.因此通過對(duì)CU四叉樹結(jié)構(gòu)的遍歷過程進(jìn)行優(yōu)化, 提出了一種二分深度劃分決策算法, 從二分深度Depth=2(即CU的大小為16×16)開始遍歷, 并在每一步遍歷之前, 判斷是否提前終止遍歷.

2.3 二分深度劃分算法

整體算法描述如下:

1) 利用前一幀相同位置的CU的劃分深度對(duì)當(dāng)前LCU的最優(yōu)四叉樹結(jié)構(gòu)進(jìn)行預(yù)測(cè).

2) 首先將二分深度CU(即CU的大小為16×16,Depth=2)的最佳預(yù)測(cè)模式作為最優(yōu)RDcost模式, 以二分劃分深度的CU作為最小CU結(jié)構(gòu).

3) 將預(yù)測(cè)深度Depthpre和二分深度Depth進(jìn)行比較(流程如圖3所示). 若預(yù)測(cè)深度Depthpre≥二分深度Depth, 則進(jìn)行向下劃分遍歷, 跳轉(zhuǎn)到4); 反之, 則進(jìn)行向上合并遍歷, 跳轉(zhuǎn)到5).

圖3 二分深度劃分算法流程

4) 若預(yù)測(cè)深度Depthpre＞=二分深度Depth, 則進(jìn)行向下劃分遍歷(流程如圖4所示). 首先以二分深度CU的最佳預(yù)測(cè)模式作為最優(yōu)RDcost模式, 再對(duì)二分深度CU結(jié)構(gòu)進(jìn)行四叉樹劃分, 求解每一個(gè)子CU的最優(yōu)RDcost, 并將最優(yōu)RDcost與4個(gè)子CU的最小RDcost之和SRDcost進(jìn)行比較: 若SRDcost較小, 則以4個(gè)子CU的最小RDcost之和作為最優(yōu)RDcost, 以4個(gè)子CU作為最小CU結(jié)構(gòu); 若最優(yōu)RDcost較小, 則停止當(dāng)前CU子塊的劃分, 以當(dāng)前CU作為當(dāng)前CU子塊的最優(yōu)結(jié)構(gòu).5)若預(yù)測(cè)深度Depthpre＜二分深度Depth, 則進(jìn)行向上合并遍歷(流程如圖5所示). 對(duì)4個(gè)CU結(jié)構(gòu)進(jìn)行合并, 求解合并后CU的SRDcost, 并將其與最優(yōu)RDcost

圖4 向下劃分遍歷算法流程

進(jìn)行比較: 若合并后CU的SRDcost較小, 則以合并后

CU為最小CU結(jié)構(gòu), 并繼續(xù)對(duì)周圍相鄰的4個(gè)CU進(jìn)行合并; 若最優(yōu)RDcost較小, 則停止當(dāng)前CU子塊的劃分, 以當(dāng)前CU作為最優(yōu)結(jié)構(gòu).

圖5 向上合并遍歷算法流程

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

為了驗(yàn)證本文所提出算法的效率, 以HEVC的軟件測(cè)試模型HM15.0為參照進(jìn)行實(shí)驗(yàn). 實(shí)驗(yàn)平臺(tái)為Inter(R)酷睿雙核CPU, 主頻2.60 GHz, 內(nèi)存4.00 GB,操作系統(tǒng)Windows7. 在此實(shí)驗(yàn)平臺(tái)上采用11個(gè)通用序列分別進(jìn)行驗(yàn)證, 測(cè)試QP(量化參數(shù))為: 22, 27, 32,37和42, 每個(gè)序列各測(cè)試100幀. 本文主要從所提出算法的編碼效率以及付出的相應(yīng)代價(jià)來考慮算法的性能.

通過比較編碼效率的參數(shù)指標(biāo)有峰值信噪比增量(ΔPSNR)、碼率增量(ΔBitrate)和編碼時(shí)間增量(ΔTime):

ΔPSNR是指本文所提快速算法與HM15.0算法的視頻峰值信噪比之差, 即:

ΔBitrate是指本文所提快速算法視頻的平均碼率與HM15.0算法視頻的平均碼率之差, 即:

ΔTime是指本文所提快速算法視頻的平均編碼時(shí)間與HM15.0算法視頻的平均編碼時(shí)間之差, 即:

從表4可以看出, 本文所提出的快速算法與HM15.0相比, 編碼時(shí)間平均縮短了55.4%, 而編碼碼率平均僅增加了0.56%, 視頻峰值信噪比僅降低了0.019%, 主觀圖像質(zhì)量基本沒有變化. 由此可見,HEVC編碼CU快速劃分算法在保證視頻質(zhì)量的前提下, 縮短了編碼時(shí)間, 提高了編碼效率.

表4 編碼性能的對(duì)比

圖6顯示了本文提出的快速算法與HM15.0編碼算的性能對(duì)比情況. 文中算法與HM15.0的率失真代價(jià)(RD)曲線基本重合, 表明本文算法與HM15.0的編碼性能相比沒有明顯差異, 由此證明本文所提算法的有效性.

表5是本文快速算法以其他幾種典型算法的編碼性能對(duì)比. 根據(jù)表5 的對(duì)比, 不論是編碼質(zhì)量、碼率,還是編碼時(shí)間, 本文提出的CU快速劃分算法性能要比其他2種更優(yōu), 這得益于本文提出的二分深度劃分技術(shù), 降低了當(dāng)前CU劃分的時(shí)間消耗.

圖6 RaceHorse的率失真代價(jià)(RD)曲線圖

表5 本文快速算法與各典型算法的性能比較

4 結(jié)論

為降低算法遍歷 HEVC編碼單元CU結(jié)構(gòu)的計(jì)算復(fù)雜度, 本文提出一種改進(jìn)的HEVC編碼單元CU快速劃分算法. 本文算法首先預(yù)測(cè)當(dāng)前CU的最優(yōu)深度,再通過二分深度劃分算法進(jìn)行深度遍歷, 選出最優(yōu)深度. 實(shí)驗(yàn)結(jié)果表明, 與HM15.0相比, 在編碼質(zhì)量幾乎沒有變化的情況下, 編碼時(shí)間減少55.4%,能有效降低HEVC的編碼復(fù)雜性.