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

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

0 引言

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

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

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

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

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

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

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

1 三維幀間配準(zhǔn)預(yù)測的算法改進

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

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

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

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

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

3) 模塊3. 重復(fù)三維配準(zhǔn)預(yù)測和可靠性的分類，并更新最后的分類結(jié)果，當(dāng)點云分割后的點云數(shù)目小于一定的閾值則停止分割，得到最后的四類點云.

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

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

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

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

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

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

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

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

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

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

(1)

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

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

1.2 基于配準(zhǔn)的三維幀間運動估計方法

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

(2)

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

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

(3)

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

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

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

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

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

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

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

2 實驗仿真與分析

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

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

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

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

表1 BD-BR結(jié)果

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

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

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

3 結(jié)語

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

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