一種基于曼哈頓距離的幀間加權預測算法

郭紅偉，朱策，李帥，王永華

（1.紅河學院 工學院，蒙自661100； 2.電子科技大學 信息與通信工程學院，成都611731）

隨著電子信息技術的高速發展和各種視頻數據采集方式的使用，數字視頻成為了多媒體信息的主要載體。然而，未經壓縮的數字視頻數據量非常巨大，如分辨率為4 000×2 000的8 bit RGB彩色視頻，幀率為30 Hz，則其每小時的數據量高達2531 GB。如此之大的數據量給視頻的傳輸和存儲帶來巨大的挑戰，因此自20世紀90年代以來，視頻壓縮技術持續成為國內外研究和應用的熱點領域［1］。現代視頻編碼器采用一個包括預測、變換、量化和熵編碼等多種壓縮工具的混合視頻編碼框架，能有效去除視頻數據中的空域冗余、時域冗余、視覺冗余等，從而實現較高的數據壓縮。預測編碼包括幀內預測和幀間預測，其中幀間預測利用了視頻圖像幀間相關性，根據運動矢量（Motion Vector，MV）和參考索引從重建幀中獲得當前編碼塊的預測像素值。進一步地，相鄰編碼塊的運動信息之間存在相關性，為了去除這種相關性從而減少用于編碼運動信息的比特數，高效視頻編碼（High Efficiency Video Coding，HEVC）引入了高級運動矢量預測（Advanced Motion Vector Prediction，AMVP）、合并模式（merge mode）和跳過模式（skip mode）等技術［2］。視頻編碼器通過率失真優化（Rate Distortion Optimization，RDO）［3-5］為當前編碼塊選擇最佳的預測模式，其數學表述為：min｛J｝，J=D+λmodeR。其中：J稱為率失真代價；D和R分別為選擇某一模式編碼時得到的編碼失真和編碼碼率（或比特數）；λmode為拉格朗日乘子。模式選擇過程中，率失真代價最小的預測模式被選擇用于編碼當前塊。

如果當前編碼塊選擇了合并模式，則其采用相鄰塊的運動矢量從參考幀中獲得預測像素，因此不需要重復編碼運動信息。合并模式節省了編碼運動信息的比特數，在HEVC中實現了較高的率失真性能提升［6］，該技術已被擴展應用到了下一代視頻編碼標準的開發中，新標準在聯合視頻專家組（Joint Video Experts Team，JVET）第10次會議后被正式命名為多功能視頻編碼（Versatile Video Coding，VVC）。近年來，研究人員針對視頻編碼中的合并模式提出了一些算法改進。HEVC采用基于四叉樹的靈活塊劃分結構，每個編碼樹單元（Coding Tree Unit，CTU）被迭代地劃分為許多編碼單元（Coding Unit，CU），每個CU又進一步劃分為1～2個預測單元（Prediction Unit，PU）。因此，針對大量預測塊的模式選擇需要極高的運算量。為了降低HEVC編碼器的運算復雜度，文獻［7-9］提出了不同的早期合并模式決策方法。在文獻［7］中，根據不同劃分深度子CU的模式與最大編碼單元（Largest Coding Unit，LCU）最佳模式之間的相關性，設計快速算法。文獻［8］提出基于率失真代價的統計模型用于早期合并模式決策，其減少了近一半的編碼時間，但率失真性能損失較大。文獻［9］分析了不同CU深度和量化系數值對應的率失真代價變化特點，采用自適應閾值減少合并模式候選進行RDO的次數，以降低編碼器運算復雜度。為了便于合并模式在硬件編碼器中的實現，文獻［10］提出能減少運算量和存儲要求的合并模式設計方法。針對三維高效視頻編碼（3D-HEVC），文獻［11-13］提出了相應的早期合并模式判決方法。大部分關于合并模式的改進算法［14-16］都是以損失率失真性能為代價，降低編碼器運算復雜度。以提升編碼器率失真性能為目的的合并模式改進方法［17］相對較少。

通過分析合并模式的運動補償預測殘差分布特性，本文提出了一個附加的合并模式候選項，其預測像素值由空、時域候選的預測塊加權得到。附加的合并模式候選項能獲得更精確的預測像素值，減小了預測殘差，從而節省編碼殘差變換系數的比特數。實驗結果顯示，本文算法能有效地改善編碼器壓縮性能。

1 視頻編碼中的合并模式

雖然靈活的四叉樹塊劃分結構更好地適應了視頻內容，能有效去除時域冗余，然而細致的劃分也導致需要編碼的運動信息增加。為此，HEVC中提出了一種新的模式，即合并模式［6］。合并模式利用了空域和時域相鄰編碼塊的運動相關性，不需要進行運動估計（Motion Estimation，ME），當前待編碼塊直接使用已編碼塊的運動信息進行運動補償預測（Motion Compensation Prediction，MCP）。編碼過程中，選擇合并模式的PU僅需編碼鄰域PU復用索引，有效地減少了比特消耗。圖1為合并模式的流程。首先，根據空域和時域相鄰已編碼塊的可用運動信息建立合并候選列表；然后，采用每個候選項的運動矢量對當前塊進行運動補償預測并編碼計算率失真代價，其率失真代價最小的運動信息對應候選項即為最佳合并模式。

合并模式候選列表來自于空域、時域已編碼塊的可用運動信息和附加生成的列表項，空域和時域中采用的相鄰塊位置如圖2所示。空域運動矢量候選有5個，時域運動矢量候選有2個，在HEVC中最多生成4個空域和1個時域合并候選列表。

具體地，建立合并候選列表的步驟如圖3所示。其輸出結果是當前塊的合并候選列表，每個候選項具有不同的運動信息，被用于當前編碼塊的運動補償預測。合并模式中，候選列表的個數由參數MaxNumMergeCands控制，其包含在碼流中傳輸到解碼端，在HEVC中設置合并列表數為5，在VVC的開發過程中，該候選列表數增加到7個。參照圖2和圖3，HEVC中合并候選列表的生成過程描述如下：

圖1 合并模式流程圖Fig.1 Flowchart of merge mode

圖2 合并模式候選塊位置Fig.2 Location of merge mode candidates

圖3 建立合并候選列表Fig.3 Construction of merge candidate list

1）生成空域運動矢量列表

空域運動矢量列表由圖2（a）中相應位置可用的PU生成，按照A1、B1、B0、A0、B2的順序檢測每個位置運動信息的可用性，若某個位置的PU是幀內預測方式或其位于別的Slice中，則其不可用。另外還有2種特殊的情況，運動信息不可用。一種情況是檢測到當前相鄰塊的運動信息與之前已檢測相鄰塊的運動信息相同，則標記為不可用，也就是合并列表不添加重復的運動信息。另一種情況是若CU劃分為左右2個PU或上下2個PU，則右邊PU或下方PU建立空域運動矢量列表時，對應于圖2（a）中的A1或B1不可用，這是因為左右2個PU運動信息相同或上下2個PU運動信息相同等價于CU采用了2N×2N的PU劃分模式。最終按檢測順序至多選擇4個可用的運動信息生成空域運動矢量列表。

2）生成時域運動矢量列表

時域運動矢量列表由圖2（b）中鄰近已編碼幀的同位PU生成，首先檢測TB位置的運動信息是否可用，若TB位置PU采用幀內預測或與其左上角PU不在同一個CTU內，則其運動信息不可用，然后檢測TC位置PU的運動信息可用性。合并候選列表中僅生成一個時域運動矢量列表項，該時域運動矢量需要根據當前幀和同位PU所屬幀各自與其參考幀之間的距離進行縮放。

3）生成附加的候選列表

如果生成的空域運動矢量列表和時域運動矢量列表總數小于MaxNumMergeCands，則需要生成附加的候選列表，以使合并候選列表補齊到Max-NumMergeCands。對于B Slice，利用之前空域和時域生成的運動信息組合生成附加的候選運動矢量對。若之前步驟生成的合并候選列表長度仍小于MaxNumMergeCands，則添加0運動矢量使列表長度達到MaxNumMergeCands。

在進行RDO選擇最佳合并候選項的過程中，每個候選列表項對應的當前塊像素值由相應運動矢量通過運動補償預測得到。式（1）表示單向預測中的運動補償預測：

式中：P（x，y）和Fref（x，y）分別為預測圖像和參考圖像；（i，j）為合并候選項中的運動矢量。雙向預測則需要由2個運動矢量和對應的參考索引采用加權2個方向的預測值獲得。

2 加權預測算法

合并模式不需要進行耗時的運動估計，通過復用領域PU的運動矢量極大地節省了編碼運動信息的比特數，從而為視頻編碼帶來顯著的壓縮性能提升。然而合并模式仍然有進一步優化以提升編碼性能的空間，因為合并模式中的運動補償預測不夠準確。直觀地，更準確的運動補償預測能減小PU的預測殘差，從而降低編碼中的量化失真，減少編碼量化系數的比特數。本節首先分析了合并模式中預測殘差的分布特征，然后提出了一種基于曼哈頓距離的加權預測作為合并模式的附加候選項，以進一步改善合并模式的性能。

2.1 合并模式中預測殘差的分布

合并模式決策過程中，每一個候選列表項的運動信息被用于運動補償預測獲得當前PU的殘差塊，如下：

式中：B（x，y）、F（x，y）和P（x，y）分別為當前PU的殘差塊、原始像素塊和預測像素塊。

直觀地，2個像素點的運動相關性隨著它們之間距離的增大逐漸變小，因此當前PU中的像素點運動矢量與合并候選項的運動矢量相關性隨著像素點到鄰域候選塊的距離增大而減小。如式（1）所示的運動補償預測中，越接近候選塊的像素點將能獲得越準確的預測像素值，反之，離候選塊較遠的像素點的預測誤差會較大。

以圖2（a）中空域候選塊B2為例，由于B2位于當前PU的左上方，當采用B2的運動矢量為當前PU進行運動補償預測，則其殘差塊的殘差幅度將呈現從上到下、從左到右逐漸增大的趨勢。類似的不均勻分布也將出現在其他合并候選項的運動補償預測殘差塊中。

為了驗證如上分析，采用VVC開發過程中的聯合探索測試模型（Joint Exploration Test Model 7.0，JEM 7.0）［18］編碼視頻序列Basketball-Drill，編碼器配置為低延遲P，量化參數（Quantization Parameter，QP）設置為22，編碼幀數設置為前100幀。統計編碼過程中使用合并模式，運動矢量來自同一空域候選位置的所有8×8殘差塊的殘差絕對值之和，該統計數據能反映出殘差幅度的分布特點。圖4（a）～（c）分別為運動矢量來自圖2（a）中候選塊B2、B0、A0時的殘差幅度統計分布。盡管由于不同位置的候選塊被選擇作為最佳合并模式的次數不同，導致圖4中的統計數值差異較大，但它們的殘差幅度分布規律與前面的分析基本一致。即隨著像素點位置與候選塊的距離增加，相應的預測殘差幅度變大。

圖4 不同位置合并候選項進行運動補償預測后的殘差幅度統計分布Fig.4 Statistical distribution for residual magnitudes after MCP of merge candidates at different locations

2.2 基于曼哈頓距離的加權預測

從2.1節的分析可知，由于當前PU中不同像素點運動與候選塊運動相關程度不同，導致合并模式中的運動補償預測不夠精確。為了充分利用像素間隨著距離變化的運動相關性，本節提出一種基于曼哈頓距離的加權預測作為合并模式的附加候選項，其預測塊由可用的不同位置候選項預測塊加權得到。所提出附加合并候選項的流程如圖5所示，具體步驟如下：

1）檢測鄰域合并候選塊

如圖2中合并模式候選塊位置所示，按A1、B1、B0、A0、B2、TB的順序檢測不同位置候選塊是否可用，并生成相應的運動矢量。如果生成的運動矢量數小于2，則不執行本文算法，否則執行本文算法。需要指出的是，時域候選塊TC并不包括在所提加權算法中，因為TC與當前PU中所有像素點的距離相同。

2）運動補償預測

采用步驟1）生成的運動矢量根據式（1）進行運動補償預測獲得相應的預測塊，記為Pi（x，y）。

3）加權預測

根據2.1節的分析可知，由步驟2）得到的多個預測塊具有不同的殘差幅度分布特點，隨著像素點位置與候選塊的距離越遠，殘差幅度相對變得越大。因此，本文提出使用曼哈頓距離度量像素間隨著距離變化的運動相關性。

曼哈頓距離表示2個點在標準坐標系上的絕對軸距之和，二維平面上兩點a（x1，y1）與b（x2，y2）之間的曼哈頓距離定義為

圖5 附加合并候選項的流程圖Fig.5 Flowchart of additional merge candidate

所提附加合并候選項的預測塊由式（4）加權得到：

式中：Wi（x，y）為每個預測塊Pi（x，y）對應的權重，其設置與候選塊的位置有關。每個像素點的權重值隨著它與候選塊的曼哈頓距離增大而減小，具體設置如表1所示，其中H和W 分別為當前預測塊的高和寬。

4）最佳合并模式選擇

計算所提附加候選項的率失真代價，并與原始合并候選列表中的率失真代價對比選擇出最佳合并模式。在聯合探索測試模型JEM 7.0中，合并候選項的索引號范圍為0～6，因此所提附加候選項索引號設置為7。若所提附加候選項最終被選擇作為當前PU的編碼模式，則相應的合并索引號7被編碼并傳至解碼端，解碼端將采用與編碼端一致的加權方法重建編碼塊。

需要說明是的，若當前PU最終選擇所提附加合并候選項編碼，則當前PU沒有明確的運動信息。為便于后續編碼過程中當前PU被用于導出其他編碼塊的運動矢量，需要對當前PU設置一個確定的運動矢量，本文算法采用步驟1）中檢測到的第一個可用候選塊運動信息作為當前PU的運動信息。

表1 不同位置候選塊對應的權重設置Table 1 Weight setting for candidates at different locations

3 實驗驗證

為驗證本文算法的有效性，將提出的基于曼哈頓距離加權預測算法集成到聯合探索測試模型JEM 7.0，該測試軟件是由JVET在HEVC測試模型（HEVC Test Model，HM）基礎上開發的，用于評估新的編碼工具和技術改進。測試序列使用JVET通用測試條件（Common Test Conditions，CTC）和軟件參考配置［19］建議的Class B、Class C、Class D、Class E中的16個視頻和Class F的4個可選視頻。實驗測試了低延遲P（Low Delay P，LDP）、低延遲B（Low Delay B，LDB）、隨機接入（Random Access，RA）3種編碼器配置，依據CTC設置QP分別為37、32、27、22編碼每一個測試序列。需要說明的是，Class E是會議視頻序列，根據CTC建議，RA配置下測試序列不包括Class E中的3個視頻。以原始的JEM 7.0編碼器作為基準，計算本文算法輸出Y、U、V分量的BDBR，BDBR表示在相同的峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）條件下，測試算法相對于基準算法的碼率節省百分比，若其值為負則表示性能增益，反之表示性能損失。

表2列出了3種編碼器配置下的全部測試序列BDBR，數據顯示本文算法在3種編碼器配置下都獲得了率失真性能提升。其中，LDP的性能平均提升達1.34%，比LDB和RA配置的性能提升大許多，這是因為B幀采用的雙向預測比P幀的單向預測準確，對于B幀可提升的預測準確度空間比較有限。另外，Class F是屏幕內容視頻，其編碼塊中的像素運動相關性很強，基本不隨距離大小變化。因此，對于Class F本文基于距離的加權預測獲得性能改善不顯著。對于實驗數據中顯示在LDB和RA配置下，個別測試序列出現率失真性能損失，其原因是由于本文算法為傳輸附加合并候選索引，增加了合并模式的編碼比特，而對于這些特殊的視頻，基于距離的加權預測提高的預測精確度比較小。

LDP編碼配置下部分測試序列的率失真性能提升很大，如測試序列BQTerrace的碼率節省高達6.98%。圖6給出了性能改善較為顯 著 的 測 試 序 列 BQTerrace、BasketballDrill、BQSquare、Johnny的率失真曲線對比。可看出，本文算法在低碼率和高碼率下均優于原始的JEM 7.0。

表2 三種編碼器配置下本文算法相比于JEM 7.0的BDBRTable 2 BDBR for proposed algorithm compar ed with JEM 7.0 under three configurations of encoder %

圖6 率失真曲線對比Fig.6 Comparison for rate-distortion curves

4 結 論

1）本文分析了合并模式空域、時域不同候選塊運動信息與當前待編碼PU中不同位置像素點運動信息的相關性，并通過實驗統計證實隨著PU中像素點距候選塊的距離增加，運動補償預測后的殘差幅度增大。

2）提出了一種基于曼哈頓距離的加權預測算法生成附加合并候選項，其充分利用了所有可用候選塊的運動信息，根據每個可用候選塊與當前待編碼PU中像素點的曼哈頓距離設置加權預測的權重，該加權預測獲得了更準確的預測塊，從而減小量化失真和編碼量化系數的比特數。

3）實驗結果顯示，在LDP、LDB和RA編碼結構下，本文算法均獲得了率失真性能提升。特別地，對于LDP配置，相比原始JEM 7.0編碼器，本文算法獲得了平均1.34%的碼率節省，最高達到6.98%。