針對HEVC編碼單元的二分深度劃分算法①

曹騰飛, 史媛媛

1(青海大學 計算機技術與應用系, 西寧 810016)

2(西安電子科技大學 計算機學院, 西安 710071)

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

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

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

1 HEVC的CU深度決策

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

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

其中, SSE表示使用預測模式計算的殘差平方和, λ表示拉格朗日系數; bits表示使用當前預測模式下進行編碼的碼率.

步驟2. 將64×64的編碼單元劃分為4個32×32的子CU, 每個子 CU的尺寸大小是 32×32, 深度Depth=1. 同理對每個子單元進行預測編碼, 并計算各自的率失真代價值. 如此遞歸的劃分下去, 直至劃分到最小的編碼單元8×8, 深度Depth=3時便不再劃分.

圖1 四叉樹結構

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

圖2 CU的深度分割示意圖

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

2 算法介紹

2.1 幀間時空域的相關性

由于在視頻序列是由連續的圖像序列幀構成, 則相鄰幀之間具有很強的關聯性, 即空間相關性的存在.由于存在空間相關性, 因此HEVC編碼幀與編碼幀之間CU的分割方式也存在極強的關聯性. 為了分析時空相鄰CU劃分深度的相關性, 首先通過5類官方的測試序列ClassA～E進行編碼測試, 測試詳情如表1所示. 時空相鄰CU劃分深度的相關統計結果如表2所示[14].

表1 通用測試序列的詳細情況

通過表2的數據分析可知, 當前CU的最優化分深度與前一幀相同位置的CU之間有較強的相關性,因此可以利用前一幀相同位置的CU的劃分深度對當前LCU的最優四叉樹結構進行預測.

表2 時空相鄰CU的相關性(單位: %)

2.2 二分深度劃分決策算法

在HEVC視頻編碼標準中, 當視頻圖像比較平坦,內容變化緩慢時, 針對它的編碼單元大多選擇了大尺寸類型; 當視頻圖像比較復雜, 細節比較豐富時, 針對它的編碼單元大多選擇了小尺寸類型; 使用HEVC測試模型HM15.0下對5類官方的測試序列ClassA～E進行編碼測試, 通過統計分析出不同量化參數QP下編碼單元CU的分布情況, 見表3.

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

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

2.3 二分深度劃分算法

整體算法描述如下:

1) 利用前一幀相同位置的CU的劃分深度對當前LCU的最優四叉樹結構進行預測.

2) 首先將二分深度CU(即CU的大小為16×16,Depth=2)的最佳預測模式作為最優RDcost模式, 以二分劃分深度的CU作為最小CU結構.

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

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

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

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

進行比較: 若合并后CU的SRDcost較小, 則以合并后

CU為最小CU結構, 并繼續對周圍相鄰的4個CU進行合并; 若最優RDcost較小, 則停止當前CU子塊的劃分, 以當前CU作為最優結構.

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

3 實驗結果與分析

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

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

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

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

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

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

表4 編碼性能的對比

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

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

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

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

4 結論

為降低算法遍歷 HEVC編碼單元CU結構的計算復雜度, 本文提出一種改進的HEVC編碼單元CU快速劃分算法. 本文算法首先預測當前CU的最優深度,再通過二分深度劃分算法進行深度遍歷, 選出最優深度. 實驗結果表明, 與HM15.0相比, 在編碼質量幾乎沒有變化的情況下, 編碼時間減少55.4%,能有效降低HEVC的編碼復雜性.