一種HEVC整像素運動估計優化算法

崔巖松，趙佳瑜，任維政

(北京郵電大學智能交通信息與網絡技術實驗室，北京100876)

HEVC/H.265視屏編解碼標準是新一代視頻編解碼國際標準，由ISO與ITU共同制定，它主要是為在保證視頻質量的情況下提高壓縮率、降低網絡帶寬，支持更大的視頻尺寸，更精細的編碼控制，用于對視頻要求更高的場合［1-2］。但是，HEVC由于其復雜度高，很難具有實用的效果，所以必須進行優化加速。本文以研究HEVC標準為基礎，在加深HEVC標準理解的基礎上，著手對測試模型HM進行優化加速。

和現有的視頻編碼標準類似［3］，HEVC保留混合編碼的基本體系結構［4-5］。一個顯著的區別在于用類似四叉樹(quadtree)的結構替代了傳統的宏塊(macroblock)［6］。HEVC編碼流程可分解為預測、變換、量化和熵編碼4部分［7］。預測部分將對編碼器性能產生很大的影響［1］。預測分為幀間預測(inter prediction)，和幀內預測(intra prediction)［1］，幀內預測消除視頻序列的空間相關性，用于編碼I幀圖像［8-9］，幀間預測消除視頻序列的時間相關性，用于編碼P幀圖像［8，10］。其中，幀間預測的大致流程為:輸入像素塊與前一幀參考幀進行運動估計后［11-12］，先進行整像素運動估計、分像素內插和分像素運動估計，產生運動矢量，之后對已獲得的運動矢量進行運動補償得到預測數據塊［1，13］。所以相比幀內預測，幀間預測消除的時間相關性對視頻壓縮的壓縮比有很大的關聯［14］。本文主要對整像素運動估計所采用的算法進行優化。

1 整像素運動估計優化算法

HEVC中快速運動的估計首先進行整像素運動估計，運用搜索模板找到最佳匹配的整像素點;之后進行分像素內插，再進行分像素運動估計，在整像素運動估計所找到的最佳匹配點的周圍進行，檢測其1/2和1/4像素點，找到最佳匹配的分像素點，主要通過調用底層的函數來實現［16］。整像素運動估計得到的是運動矢量的整像素值，決定了運動矢量的大致方向，因此，對其進行優化是十分必要的。

本文主要針對整像素運動估計采用的EPZS算法進行優化。HEVC沿用了H.264/AVC的EPZS作為默認的快速運動估計算法。該算法主要由運動矢量選擇、提前終止策略、運動矢量提取3部分組成。文獻中測試顯示，EPZS算法比全搜索算法加速比最大達6倍［15］，且能保證良好的壓縮性能和圖像質量。HEVC整像素運動估計中采用的EPZS算法可以簡述為:在大小為64×64的搜索框中，使用步長(l)從1開始，以2的指數遞增的8點菱形搜索，當SAD小于設定的閾值時停止搜索，得到運動矢量。在快速算法中，不同類型和尺寸的搜索模板一定程度上決定了搜索的效果。根據視頻序列的中心偏移性(MVD)，其運動矢量分布通常集中在搜索窗的中心位置附近，即大多數圖像序列的運動都是平穩和緩慢的。8點菱形搜索適合搜索步長適中的點，對于搜索步長較小的點或較大的點，得到的搜索效果并不理想。因此，應該更改開始和提前終止的策略，優化搜索模板。

為此，在提出運動矢量搜索優化算法之前，需要統計現實序列運動矢量的分布，根據統計結果進行類型劃分和調整搜索模板，減少搜索次數和運動估計計算量。由于搜索終止步長分布可以間接反映運動矢量分布情況，且數據易于得到、統計方便，本文模板優化的依據為搜索終止步長的統計分布。

通過測試得到176×144(qcif)測試序列搜索終止步長的統計分布和176×144(qcif)測試序列搜索終止步長的統計分布，如表1和表2所示。

表1 176×144(qcif)測試序列搜索終止步長的統計百分比 %

表2 1 920×1 080(class E)測試序列搜索終止步長的統計百分比 %

根據以上分析，提出一種EPZS優化算法及搜索模板，搜索模板見圖1。搜索框尺寸保持默認值64，調整的EPZS搜索點為3類:4點的菱形搜索，8點的菱形搜索和16點的菱形搜索。當步長小于2時使用4點菱形搜索模板，如圖1a所示;當步長在2～4時使用8點菱形搜索模板，如圖1b所示;當步長大于8時使用精度大的16點菱形搜索模板，如圖1c所示。開始整像素運動估計算法之后，從距離為1開始對起始搜索點附近的點進行搜索，每次搜索步長以2的冪次增長，每次搜索根據步長選擇對應的模板。即4點菱形搜索只是搜索距離為1時的搜索模板，8點菱形搜索是搜索距離為2，4，8的時的搜索模板，16點菱形搜索是搜索距離為16，32，64的時候的搜索模板。

圖1 4點、8點和16點菱形搜索模板

2 測試結果

根據優化算法，對測試模型HM進行優化，并使用不同格式的視頻序列對優化后的編碼器進行了測試，下面給出了尺寸為176×144(qcif)和1 920×1 080(class E)的幾個視頻序列的測試結果。

測試視頻序列配置如下:測試序列尺寸為176×144(qcif)，編碼幀數為60幀，幀率為155 f/s(幀/秒)，序列比特深度為8;測試視頻序列尺寸為1 920×1 080(classE)，編碼幀數為5，幀率為25 f/s，序列比特深度為8。

表3顯示了尺寸176×144(qcif)測試視頻序列優化前后比較結果，其中編碼幀數60，幀率5 f/s，序列比特深度為8。

表3 176×144格式圖像編碼優化測試前后的性能變化 %

表4顯示了尺寸1 920×1 080(class E)測試視頻序列優化前后比較結果，其中編碼幀數60，幀率5 f/s，序列比特深度為8。

表4 1 920×1 080格式圖像編碼優化測試前后性能變化百分比 %

3 結束語

根據表3和表4，可以得到結論如下:

對于尺寸為176×144測試視頻序列，優化后，對于視頻質量的客觀值，亮度分量Y平均下降0.005 0 dB，色度分量U平均下降0.043 4 dB，色度分量V平均下降0.072 6 dB，編碼后碼流比特率最多上升2.21%，耗時最少下降3.03%。

對于尺寸為1 920×1 080測試視頻序列，優化后，對于視頻質量的客觀值，亮度分量Y平均上升0.008 1 dB，色度分量U平均下降0.014 9 dB，色度分量V平均下降0.047 7 dB，編碼后碼流比特率最多上升0.40%，耗時最少下降1.25%。

因此，可以確定該算法對尺寸為176×144和1 920×1 080視頻序列的編碼實現了優化。在保證視頻質量不變和編碼后碼流略微上升的前提下，降低了編碼耗時，且在每一次視頻序列測試中，編碼耗時下降程度超過了編碼后比特率的上升程度。

［1］ SULLIVAN G，OHM J，HAN W，et al.Overview of the high efficiency video coding(HEVC)Standard ［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1649-1668.

［2］ ZHOU M，GAO W，JIANG M，et al.HEVC lossless coding and improvements［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1839-1843.

［3］ OHM J，SULLIVAN G，SCHWARZ H，et al.Comparison of the coding efficiency of video coding standards-including high efficiency video coding(HEVC)［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1669-1684.

［4］ KIM I，MIN J，LEE T，et al.Block partitioning structure in the HEVCstandard ［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1697-1706.

［5］ High efficiency video coding［EB/OL］.［2014-06-05］.http://en.wikipedia.org/wiki/High_Efficiency_Video_Coding.

［6］ HELLE P，OUDIN S，BROSSB，et al.Block merging for quadtreebased partitioning in HEVC［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1720-1731.

［7］ OHM J，SULLIVAN G，WIEGAND T，et al.Introduction to the special section on the HEVC standard ［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1647-1648.

［8］林福宗.多媒體技術教程［M］.北京:清華大學出版社，2009.

［9］ LAINEMA J，BOSSEN F，HAN W，et al.Intra coding of the HEVC standard ［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1792-1801.

［10］ KAMP S，WIEN M.Decoder-side motion vector derivation for block-based video coding［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1732-1745.

［11］ LI H，LI B，XU J.Rate-distortion optimized reference picture management for high efficiency video coding［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1844-1857.

［12］ SJOBERG R，CHEN Y，FUJIBAYASHI A，et al.Overview of HEVC high-level syntax and reference picture management［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1858-1870.

［13］ YUAN Y，KIM I，ZHENG X，et al.Quadtree based nonsquare block structure for inter frame coding in high efficiency video coding［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1707-1719.

［14］ BOSSEN F，BROSS B，SüHRING K，et al.HEVC complexity and implementation analysis［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1685-1696.

［15］徐榮飛.HEVC編解碼算法的CUDA優化［D］.北京:北京郵電大學，2013

［16］ CHI C，ALVAREZ-MESA M，JUURLINK B，et al.Parallel scalability and efficiency of HEVC parallelization approaches［J］.IEEE Trans.Circuits and Systems for Video Technology，2012，12(22):1827-1838.