三維幀間配準預測的V-PCC改進算法

王適，鄭明魁，陳建，王澤峰，邱鑫

(福州大學物理與信息工程學院，福建 福州 350108)

0 引言

傳統圖像是像素的集合，每個像素由三個彩色分量或者一個灰度值表示. 與圖像類似，3D點云是空間中一系列點的集合，每個點由坐標位置和屬性信息(例如顏色、反射率、法向量等)構成. 由于點云可以準確重建一個真實的物體或者場景，目前已經廣泛應用于虛擬現實[1]、增強現實[2]以及自動駕駛[3]等領域. 根據不同的應用場合，可以分為單個物體或場景形成的點云，進一步可以分為靜態點云和動態點云. 本研究主要針對運動的物體形成的點云(dynamic point cloud，DPC)，對于典型的由8i[4]采集的DPC數據，每一幀點云通常包含近百萬個點，每個點由30個比特表示幾何信息(x,y,z)以及24個比特表示顏色信息(r,g,b)，因此一幀點云大小約為6 Mbyte，對于30幀s-1的點云序列，則碼率大小為180 Mbytes-1，所以有效的壓縮方法對于點云的存儲和傳輸是極其重要的.

為了有效壓縮DPC, 目前的方法主要是利用幀與幀之間的相關性去除冗余信息，主要分為兩大類方法： 3D的幀間預測方法和3D點云投影成2D視頻的幀間預測方法. 對于3D的幀間預測方法, Kammerl等[5]首先提出編碼相鄰幀八叉樹差異，相比直接編碼，更有效地壓縮了DPC. Thanou等[6]對一幀點云用八叉樹分塊，對每一塊使用頻譜圖小波變換將3D運動估計轉換為特征匹配問題. Mekuria等[7]采用和2D視頻編碼類似的思想，把一幀點云均勻劃分為N·N·N的宏塊，根據每一塊與對應塊的顏色方差和點數的差異大小決定是否使用迭代最近點(ICP)估計其運動信息. Queiroz等[8]把一幀點云均勻分割成N·N·N的用0和1表示的體素，對一塊體素計算其與對應體素的相關性大小從而選擇幀內編碼或者幀間編碼. Xu等[9]用k-means把點云聚類成M塊，采用ICP估計幾何信息的運動矢量，對屬性信息則用圖的傅里葉變換模型估計其運動矢量. 然而時變的點云幀與幀之間存在點數差異、沒有明確對應以及部分點云不存在對應，因此這些方法的幀間預測不夠準確，未充分利用時間相關性，點云的壓縮效率沒有得到顯著提高.

由于2D視頻編碼具有靈活和成熟的算法，一些工作嘗試將DPC從3D投影到2D以壓縮DPC. 例如，Lasserre等[10]提出使用基于八叉樹的方法將DPC投影到2D空間，而Budagavi等[11]則提出一種直接對3D中的點進行排序以組織2D視頻的方法，然后使用HEVC壓縮2D視頻. 但是，這些投影方法會導致投影生成的2D視頻發生形狀變化，無法充分利用幀間預測技術. 為了解決這個問題，Schwarz和He等[12-13]建議使用圓柱或立方體將DPC投影到2D視頻，提高了視頻壓縮效率，但是由于遮擋而損失了一些點. 為了在投影點數和使用2D視頻編碼之間取得更好的平衡，Mammou等[14]提出使用基于patch的投影方法，將DPC分解為2D的patch, 形成視頻并使用視頻編碼的方法對其壓縮.

基于patch的投影方法(V-PCC)成為MEPG-I制定的對于DPC壓縮的標準[15]. V-PCC首先通過計算每個點的法向量把三維點云投影到包圍盒的6個平面，形成幾何圖像和紋理圖像，進一步對在同一個平面且在三維幾何坐標是相鄰的點進行聚類形成幾何patch和紋理patch，把patch按照一定順序插入到網格形成了有空隙的紋理圖像和幾何圖像，為了平滑圖像便于后續視頻編碼壓縮，對空隙進行填充，為了區分填充像素和點云投影形成的像素，又引入了0和1的占用圖，對紋理圖像和幾何圖像形成的序列采用視頻編碼壓縮，占用圖和其它輔助信息則直接熵編碼. 但基于patch的投影破壞了3D對象固有的連續性，導致幀間預測編碼效率顯著下降[16].

對此，Li等[16]通過在編碼端重建三維點云，根據三維點云幀與幀之間的對應關系修正2D視頻編碼的運動矢量，但是對于幾何patch，由于點云發生了旋轉和平移，因此形成的深度圖像具有較大差異，導致無法進行有效的2D幀間運動估計. Kim等[17]提出結合三維和二維的幀間編碼，把DPC序列劃分為I幀和P幀，I幀采用V-PCC編碼，通過I幀進行3D幀間運動估計從而恢復P幀，該方法可能使得P幀的殘差過大，不能保證高效的幀間預測. 本研究提出一種優先采用三維配準幀間預測和結合V-PCC幀間預測的改進方法. 三維配準幀間預測： 當前塊在已編碼的參考幀中尋找最佳匹配的塊，進一步優化當前塊和最佳匹配塊的誤差. 因此三維配準幀間預測僅需要編碼更小的殘差，所以本研究優先采用三維配準幀間預測. 為保證點云配準時點云運動具有一致性和準確的對應性，首先提出一種運動一致性的二叉樹粗分割和八叉樹細分割的方法； 為度量三維配準幀間預測的可靠性，計算三維配準幀間預測的誤差，對于不能有效進行三維配準幀間預測的點云使用高效的V-PCC幀間預測，有效結合三維配準幀間預測和V-PCC的視頻編碼的幀間預測，形成一種基于分割的混合幀間的預測方法. 所提出的方法主要包括以下貢獻：

1) 提出一種用于三維配準幀間預測的分割方法. 保證了分割后塊點云相對運動的一致性和對應性.

2) 提出一種三維配準幀間預測結合視頻編碼幀間的預測方法. 該方法優先采用可靠的三維配準幀間預測，剩下點云融合并使用V-PCC的幀間預測方法.

1 三維幀間配準預測的算法改進

三維配準幀間預測是通過最小化參考幀和當前幀的誤差，從而求解對應的旋轉矩陣和平移向量生成預測幀. 所以三維配準幀間預測僅需編碼更小的殘差，提出了優先三維配準幀間預測的V-PCC改進方法. 然而時變的點云同一幀不同位置發生不同運動以及幀與幀之間存在點數差異，而配準的前提是同一幀點云發生相同的旋轉和平移，且當前幀和參考幀具有準確的對應. 因此，首先要分割出具有相同運動的點云且保證分割后的對應性. 對此，本研究提出了基于運動一致性的二叉樹粗分割和進一步八叉樹細分割的方法. 進一步對分割后的每一塊點云優先采用三維配準幀間預測，為了保證三維配準幀間預測的可靠性，對分割后的每一塊點云進行三維配準幀間預測并計算誤差，當誤差小于一定的閾值，則該塊點云只需編碼塊索引和運動信息，對剩下點云融合并使用V-PCC的幀間預測.

圖1 編碼框圖Fig.1 Architecture of the encoder

如圖1所示，本編碼框架由七個模塊組成.

1) 模塊1. 對輸入的當前點云序列采用了一種基于運動一致性的二叉樹粗分割方法，分割出具有一致性運動和對應性的點云塊.

2) 模塊2. 對分割后的點云塊進行三維配準幀間預測并根據可靠性分類，計算配準幀間預測后的誤差大小把點云分成4個類別，分別為不需要編碼的一類點云, 可以通過三維配準幀間預測的二類、三類點云，以及不能被三維配準幀間預測的四類點云. 此時分析四類點云不能配準的原因如下： ① 點云幀與幀之間差異過大，導致對應關系較差； ② 點云分割后的塊過大，塊內的相對運動仍然并非一致. 所以提出了進一步細分割的方法，基于此時點云有較好的關系，所以采用了相比二叉樹更高效的八叉樹分割方法，形成了模塊3.

3) 模塊3. 重復三維配準預測和可靠性的分類，并更新最后的分類結果，當點云分割后的點云數目小于一定的閾值則停止分割，得到最后的四類點云.

4) 模塊4(熵編碼). 根據模塊2的可靠性判斷，一類點云只需要編碼塊索引，二、三類點云需要編碼塊索引和旋轉矩陣以及平移向量.

5) 模塊5. 對四類點云融合并使用V-PCC的幀間預測.

圖2 解碼框圖Fig.2 Architecture of the decoder

6) 模塊6. 參考幀是已編碼的前一幀在編碼端的重構，所以分割的點云再次融合形成了模塊6. 點云重構并融合.

7) 模塊7. 參考幀點云.

解碼的框圖如圖 2所示，其與編碼對應. 首先根據分割信息分割已解碼的前一幀點云，進一步根據一類點云的索引找到相應的塊，從而恢復一類點云； 由二、三類的索引找到相應的塊以及運動信息R和T恢復二、三類點云； 對于四類點云則直接通過V-PCC解碼； 最后融合一、二、三、四類點云，恢復出最終的解碼點云.

1.1 基于運動一致性的二叉樹分割方法

目前對于點云三維配準幀間預測的分塊方法主要有兩種： 1) 基于k-means的方法把點云聚類成M塊； 2) 參考視頻編碼的思路把點云均勻分成N·N·N的立方體. 這兩種方法不能保證分割后的點云運動的一致性和塊的對應性. 對此，受點云質量評估的啟發，通過計算當前幀相對前一幀的最近點誤差衡量點云幀間的相對運動，由于具有相同運動的局部點云其幾何位置接近，發生相同旋轉和平移之后的數值也接近，因此誤差的數值接近. 所以具有一致性運動的相鄰點云，其誤差分布相似. 為度量誤差分布的離散程度，引入統計學中的離散系數作為衡量指標. 因此誤差的離散系數大小對應了點云是否具有一致性運動.

為使點云分割后參考幀和當前幀的塊之間一一對應，引入了二叉樹的思想. 例如，當一幀點云沿著維度x均勻分割成兩塊時，通過比較兩塊點云中x的相對大小，得到了對應關系.同時考慮點云運動的一致性和對應性，沿著不同的維度分割，對應不同大小的誤差的離散系數.離散系數越小，說明此時分割后的點云運動更具有一致性.因此, 構建分割后的兩塊點云的離散系數之和作為選擇不同分割維度的代價函數S(d)，其中d=x,y,z，S(d)最小時對應的分割維度即為所求的分割維度.

對于當前幀點云矩陣Pcur，Pcur沿著維度d(d=x,y,z)均勻分割后的代價函數為S(d)，定義為

(1)

對分割后的點云進行多次分割，分割M次之后，得到了2M塊點云, 如圖 3所示，當M=5時，即把點云分割為32塊，8i的數據中RedAndBlack數據集隨機選取的分割結果展示. 圖3(a)為參考幀分割結果，圖3(b)為當前幀對應的分割結果，可以看到分割后參考幀與當前幀有較好的對應.

圖3 RedAndBlack序列相鄰幀的分割結果Fig.3 Segmentation results of adjacent frames or test sequence RedAndBlack

1.2 基于配準的三維幀間運動估計方法

本三維配準算法采用迭代最近點算法(ICP)，對每一個點云塊用ICP估計其旋轉矩陣R和平移向量T, ICP通過最下化當前幀和參考幀的誤差E(R,T)求解相應的R和T.

(2)

式中:E(R,T)為均方誤差；Pref為參考幀點云矩陣；Pcur為當前幀點云矩陣；Ncur為當前幀點云Pcur的點數；R*和T*即為參考幀和當前幀誤差最小時對應的旋轉矩陣和平移向量.

為進一步說明優先采用三維配準幀間預測的優勢，計算三維配準幀間預測的誤差與非配準幀間預測時的誤差并比較. 首先，非配準的幀間預測定義為： 當前塊在已編碼的參考幀中根據誤差大小尋找最佳匹配的塊.

(3)

此時，式(3)右邊是非配準幀間預測的誤差對應了旋轉矩陣為單位矩陣I、平移向量為0時的誤差函數E(R,T)的函數值； 左邊表示了三維配準幀間預測時的誤差，三維配準幀間預測的誤差對應為誤差函數E(R,T)的最小值.由于一個函數的最小值是小于等于其它變量對應的函數值，所以三維配準幀間預測改善了參考幀和預測幀的誤差.因此，優先對V-PCC采用三維配準幀間預測.

為保證三維配準幀間預測的可靠性. 首先，需要設定三維配準幀間預測誤差的閾值mseth，記mseref和msepre分別表示參考點云和預測點云相對于當前點云的均方誤差. 進一步判斷參考點云配準前后的均方誤差和誤差閾值的相對大小，對于近似靜止的點云塊有兩種結果： ① 點云是靜止的，配準之后沒有改進； ② 點云是近似靜止的，配準之后改善了參考點云與當前點云的誤差. 對于運動的點云也有兩種結果： ① 配準之后形成的預測點云與當前點云的均方誤差小于等于閾值； ② 配準之后形成的預測點云與當前點云的均方誤差大于閾值； 因此，分塊之后的點云被分成了如下4個類別.

1) 一類. 當mseref≤mseth, mseref≤msepre，說明該塊點云是靜止的，參考點云和預測點云之間差異較小，配準之后誤差沒有改善.

2) 二類. 當mseref≤mseth, mseref≥msepre，說明該塊點云近似是靜止的，參考點云和預測點云之間差異較小，配準之后的預測點云和當前點云的誤差進一步減小.

3) 三類. 當mseref≥mseth, mseth≥msepre，說明該塊點云是運動的，參考點云和預測點云之間差異較大，但是通過配準之后形成的預測點云與當前點云的均方誤差是小于閾值的.

4) 四類. 當mseref≥mseth, mseth≤msepre，說明該塊點云是運動的，參考點云和預測點云之間差異較大，通過配準之后的預測點云與當前點云仍存在較大的差異.

因此，針對一類點云只需要編碼塊的索引. 對于二類和三類點云需要編碼塊的索引、旋轉矩陣R和平移向量T. 對于四類點云，配準之后均方誤差過大的原因是整塊點云的運動不一致，即此時的四類點云包含有其他3個類別的點云. 于是對四類點云提出了進一步細分割的方法?；诖藭r經過粗分割后的點云有較好的對應關系，因此采用了相比二叉樹更高效的八叉樹分割方法，當有一塊點云的數目小于閾值則停止分割. 對進一步分割完成后的點云進行配準，計算誤差分類，并更新分類結果. 最后對所有四類點云融合并使用V-PCC進行編碼.

2 實驗仿真與分析

為評估算法的性能，將本方法與最新的Test Model Category 2 version 12.0 of MPEG PCC[18]、經典算法[7]以及V-PCC改進的幀間編碼方法[16-17]比較了BD-rate. 對于RD曲線，由于缺乏其它文獻的數據則只和V-PCC對比. 測試數據為V-PCC CTC[19]中定義的5個DPC. 分別從幾何失真和屬性失真兩個方面評估點云質量. 幾何失真用點對點的均方距離D1和點對平面的均方距離D2的峰值信噪比(PSNR)作為衡量指標； 屬性質量則用顏色信息的(y,u,v)三個分量的PSNR作為衡量指標. 其中BD-rate的計算參考視頻編碼[20].

根據V-PCC CTC，QP參數分別為VPCC參考軟件里面的5個等級，分割時M=5，八叉樹分割停止時的點數為2 000，由于量化參數分為5個等級，對應均方誤差的閾值也設置為5個等級，從小到大分別是0.50、0.55、0.60、0.65、0.65對應從小到大的5個量化步長. 如圖 4分別展示了本方法和V-PCC的Queen數據集屬性質量的PSNR、幾何質量的PSNR和碼率關系的RD曲線圖. 從圖4(a)～(c)可以看出，不同QP量化下，本方法相比V-PCC在同等屬性質量下碼率均有降低，隨著碼率增加，配準性能進一步提高，因此減少了更多點的壓縮，所以性能相比具有更多的提升. 相比圖4(a)～(c)可以發現, 圖4(d)～(e)在同等幾何質量下降低了更多的碼率. 因為基于配準的幀間估計主要針對幾何信息，所以相比屬性信息改善更大.

圖4 Queen序列率失真曲線圖Fig.4 Rate-distortion curves for selected test sequences Queen

表1展示了不同測試序列下BD-rate的改善情況. 對于同等幾何質量，基于D1和D2的平均碼率分別降低20.70%和40.73%； 對于同等屬性質量下，基于y、u、v三個屬性，平均碼率分別降低了21.61%、29.74%、20.90%. Soldier和Queen數據集同等幾何質量下碼率分別減少88%和51%，RedAndBlack數據集同等幾何質量碼率減少為13.53%和77.50%，相比較數值變小了，Loot 和Longdress數據集同等幾何質量下碼率反而上升了. 觀察圖5可以發現，Soldier和Queen數據集的對象是人為創作的，屬于非自然的，幀與幀之間運動比較有限，可以通過三維配準幀間預測出大部分當前幀的點云，具有較大的性能提升. 而Loot 、Longdress和RedAndBlack數據集對象是真實的人，運動更為復雜，例如，當衣服抖動時，發生旋轉、平移、伸縮，通過配準的誤差較大，不利于三維配準幀間預測.

表1 BD-BR結果

圖5 展示5個測試序列中的一幀示例視圖[4]Fig.5 Example views rendered from one frame of the five test sequences[4]

表2是在同一數據集，不同的方法相對V-PCC在同等質量下的平均碼率. 根據表中數據可以看到，本方法性能是遠超經典的編碼方法Mekuria等[7]采用八叉樹和圖像幀內編碼幾何信息和屬性信息, 幀間則把點云劃分為N·N·N的宏塊并使用ICP配準. Kim等[17]對I幀通過V-PCC編碼，P幀則通過點云3D搜索I幀中最佳匹配的點從而恢復，但由于點云是運動的，幀間存在較大差異時需要編碼較大的殘差. Li等[16]通過在編碼端重建三維點云彌補了因為投影產生的連續性被破壞的問題，有效提高了屬性信息的編碼，但是，幀與幀之間的幾何信息由于經過旋轉和平移，對應點云投影后生成的圖像本身存在較大的差異，此時幀間估計后具有較大的殘差. 本研究首先提出的分割方法保證了幀與幀之間的對應性和運動的一致性，使得可以有效進行后續的三維配準幀間預測，進一步根據三維配準幀間預測的可靠信分類，篩選出可以有效地通過三維配準幀間預測的點云，減少大量點的編碼，進一步提高了V-PCC的性能.

表2 不同的方法相對V-PCC的BD-BR結果

3 結語

本研究提出一種優先采用三維配準幀間預測以及結合V-PCC的幀間預測的改進方法. 首先針對點云幀與幀之間存在點數差異、一幀點云不同位置運動不盡相同，導致不能進行有效的點云配準，提出了一種基于運動一致性的二叉樹的粗分割，進一步的八叉樹細分割方法，自適應地分割具有相同運動的相鄰點云，且保證了分割后參考點云和當前點云的對應性. 為了保證三維配準幀間預測的可靠性，對分割后的點云使用ICP估計運動信息并計算誤差，對于運動估計后誤差小于一定閾值的點云，則只需編碼塊索引和運動信息，對于誤差較大不能被有效地三維配準幀間預測的點云，則融合并用高效的V-PCC的幀間預測，形成一種基于分割的混合幀間預測的方法.

相比V-PCC的編碼，本方法在保證點云質量的同時減少了大量點的編碼. 通過實驗驗證，本算法進一步改進了V-PCC的編碼性能. 本研究的下一步目標分為兩步： 1) 使用深度學習的點云生成的方法替代ICP的點云配準方法，這樣可以避免由于點云存在較大差異時，幀間預測可靠性較差的問題； 2) 把上述分割和配準后的點云重新投影到圖像，并添加到視頻編碼的參考幀，進一步提高編碼的可靠性.