一種基于曼哈頓距離的幀間加權(quán)預(yù)測算法

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

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

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

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

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

1 視頻編碼中的合并模式

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

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

具體地，建立合并候選列表的步驟如圖3所示。其輸出結(jié)果是當(dāng)前塊的合并候選列表，每個候選項具有不同的運動信息，被用于當(dāng)前編碼塊的運動補償預(yù)測。合并模式中，候選列表的個數(shù)由參數(shù)MaxNumMergeCands控制，其包含在碼流中傳輸?shù)浇獯a端，在HEVC中設(shè)置合并列表數(shù)為5，在VVC的開發(fā)過程中，該候選列表數(shù)增加到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）中相應(yīng)位置可用的PU生成，按照A1、B1、B0、A0、B2的順序檢測每個位置運動信息的可用性，若某個位置的PU是幀內(nèi)預(yù)測方式或其位于別的Slice中，則其不可用。另外還有2種特殊的情況，運動信息不可用。一種情況是檢測到當(dāng)前相鄰塊的運動信息與之前已檢測相鄰塊的運動信息相同，則標(biāo)記為不可用，也就是合并列表不添加重復(fù)的運動信息。另一種情況是若CU劃分為左右2個PU或上下2個PU，則右邊PU或下方PU建立空域運動矢量列表時，對應(yīng)于圖2（a）中的A1或B1不可用，這是因為左右2個PU運動信息相同或上下2個PU運動信息相同等價于CU采用了2N×2N的PU劃分模式。最終按檢測順序至多選擇4個可用的運動信息生成空域運動矢量列表。

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

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

3）生成附加的候選列表

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

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

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

2 加權(quán)預(yù)測算法

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

2.1 合并模式中預(yù)測殘差的分布

合并模式?jīng)Q策過程中，每一個候選列表項的運動信息被用于運動補償預(yù)測獲得當(dāng)前PU的殘差塊，如下：

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

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

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

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

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

2.2 基于曼哈頓距離的加權(quán)預(yù)測

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

1）檢測鄰域合并候選塊

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

2）運動補償預(yù)測

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

3）加權(quán)預(yù)測

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

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

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

所提附加合并候選項的預(yù)測塊由式（4）加權(quán)得到：

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

4）最佳合并模式選擇

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

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

表1 不同位置候選塊對應(yīng)的權(quán)重設(shè)置Table 1 Weight setting for candidates at different locations

3 實驗驗證

為驗證本文算法的有效性，將提出的基于曼哈頓距離加權(quán)預(yù)測算法集成到聯(lián)合探索測試模型JEM 7.0，該測試軟件是由JVET在HEVC測試模型（HEVC Test Model，HM）基礎(chǔ)上開發(fā)的，用于評估新的編碼工具和技術(shù)改進(jìn)。測試序列使用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種編碼器配置，依據(jù)CTC設(shè)置QP分別為37、32、27、22編碼每一個測試序列。需要說明的是，Class E是會議視頻序列，根據(jù)CTC建議，RA配置下測試序列不包括Class E中的3個視頻。以原始的JEM 7.0編碼器作為基準(zhǔn)，計算本文算法輸出Y、U、V分量的BDBR，BDBR表示在相同的峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）條件下，測試算法相對于基準(zhǔn)算法的碼率節(jié)省百分比，若其值為負(fù)則表示性能增益，反之表示性能損失。

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

LDP編碼配置下部分測試序列的率失真性能提升很大，如測試序列BQTerrace的碼率節(jié)省高達(dá)6.98%。圖6給出了性能改善較為顯 著 的 測 試 序 列 BQTerrace、BasketballDrill、BQSquare、Johnny的率失真曲線對比?？煽闯觯疚乃惴ㄔ诘痛a率和高碼率下均優(yōu)于原始的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 結(jié) 論

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

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

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