面向點云無損壓縮的快速細節(jié)層次優(yōu)化方法

魏磊,萬帥,2,王哲誠,丁曉斌,張偉

(1.西北工業(yè)大學電子信息學院,710129,西安;2.皇家墨爾本理工大學工程學院,VIC3001,澳大利亞墨爾本;3.西安電子科技大學通信工程學院,710071,西安)

近年來,隨著3D傳感和捕獲技術的飛速發(fā)展,點云在虛擬現實、自動駕駛、數字城市和3D打印等領域得到了廣泛的應用[1-2]。作為一種新型空間數據類型,點云非常適合用來表示3D模型和空間,并且可以非常高效地用于計算和處理,已經成為了一種用于顯示和存儲三維信息的流行方法。點云是由三維空間中一系列非均勻采樣的點組成的,每個點除了空間坐標外,還附著有若干屬性信息,比如顏色、反射率和法線等,因此點云具有數據量巨大的特點,為其處理和傳輸帶來挑戰(zhàn)。高效的點云壓縮是點云相關應用實用化的關鍵,通常將幾何信息和屬性信息分別進行壓縮。

針對點云的屬性信息的壓縮,目前已經提出了多種有效的方法。文獻[3]提出了一種用于編碼點云中屬性塊的圖形變換方法,要求將點云捕捉或排列到規(guī)則網格上;文獻[4]將點云采樣到統(tǒng)一的網格中,然后將網格劃分為塊以便直接應用圖變換,進而進行三維塊內預測;文獻[5]提出了一種基于圖變換的屬性壓縮方法,利用k近鄰擴展生成更有效的圖;文獻[6]提出了一種基于層次變換和算術編碼的點云顏色信息的壓縮方法,該變換是一種分層子帶變換,類似于Haar小波的自適應變化,已被收于動態(tài)圖像專家組(MPEG)的基于幾何的點云壓縮(G-PCC)標準[7]中。另一種重要的基于層次變換的方法為細節(jié)層次(LoD),由Clark于1976年首次提出[8],已廣泛用于計算機圖形的實時3D技術中。目前,關于LoD的工作大多集中在生成方案上:文獻[9]提出了一種新的基于二叉樹的LoD生成方案;文獻[10]提出了一種基于聚類的LoD生成方法;文獻[11]則是針對圖形學中的幾何模型的簡化工作;文獻[12-13]提出了一種基于距離的LoD生成方法。G-PCC提出了利用LoD對點云屬性信息進行壓縮的方法,同時為可伸縮編碼提供了可能性[7]。文獻[14]將LoD與圖變換結合,利用圖變換對預測殘差進行變換編碼,進一步去除冗余?，F階段LoD在點云壓縮中的主要作用是屬性信息的預測編碼。

這些文獻中的工作并沒有解決如何實現最優(yōu)LoD劃分的問題。對于基于距離的LoD,影響編碼性能的因素主要有3個:初始采樣距離、各層之間的采樣距離比和LoD層數[15]。其中,以LoD層數最為關鍵,除了影響壓縮后碼率外,還直接關系到編解碼時間。本文在理論分析的基礎上,建立了基于LoD的預測殘差和距離的數學模型,通過該模型對編碼性能進行優(yōu)化;面向點云無損壓縮,基于該模型提出了一種通過設置終止閾值優(yōu)化編碼性能的快速方法。

1 點云壓縮中的LoD

1.1 LoD及預測

LoD結構是將點云劃分為一系列的增強層(Ai)i=1,2,…,N-1和頂端的細節(jié)層LN,如圖1所示。定義Li為第i個細節(jié)層,對Li層進行下采樣可以得到更為稀疏的Li+1層,剩余的點則組成i個增強層,即Ai。

圖1 LoD金字塔結構Fig.1 LoD pyramid structure

類似于視頻預測編碼,點云通過預測來去除點之間的相關性,利用特定的預測方式來表征點之間的相互關系。預測編碼是指利用已編碼的一個或幾個樣本值,根據某種模型或方法,對當前的樣本值進行預測,并將樣本真實值和預測值之間的差值進行編碼,從而有效提高壓縮性能[16]。

在點云壓縮中,常用的預測方法是從已編碼點中找到若干個距離當前點最近的點作為參考點,將這些參考點的屬性重建值進行基于距離的加權平均作為當前點的屬性預測值。

與一般的方法相比,基于LoD的預測方法在每個LoD層都具有不同的參考點選擇范圍,可以分為以下兩類:①在對圖1中細節(jié)層LN進行編碼時,其參考點只能在本層中已編碼的點中選擇,記為細節(jié)層的預測;②對于增強層(Ai)i=1,2,…,N-1,不僅可以選擇本層中已編碼的點,還可以選擇此前已編碼過的細節(jié)層中的點,記為增強層的預測。對于增強層的預測,劃分LoD所帶來的變化較大。以劃分兩層來進行說明,如圖2所示。對于P3點的參考點選擇:在不劃分LoD時,預測編碼按照原始編碼順序進行,因此參考點都分布在受限于該順序的方向上,如圖2a所示;在劃分LoD后,P3位于增強層A1中,其參考點除本層內已編碼的點外,還包含已編碼的L2中的點,位于空間上的多個方向,如圖2b所示。劃分LoD的預測通常使得預測的效果更好,從而提升了編碼性能。

(a)未劃分LoD的預測

(b)劃分LoD的預測圖2 未劃分LoD及劃分兩層LoD的參考點范圍對比Fig.2 Comparison of the reference points range between the unbuilt LoD and the 2-layer LoD

1.2 預測殘差與碼率的關系

為了優(yōu)化LoD的生成,需要獲取每一層的碼率,而在當前基于LoD的點云壓縮方案中,并未對每一層LoD進行獨立編碼,很難獲得其相應的碼率,因此本文使用預測殘差來代替碼率進行建模。

為了研究預測殘差的分布情況以及與碼率的關系,從G-PCC的靜態(tài)對象與場景數據庫Cat1-A[17]中選擇了basketball_player_vox11和dancer_vox11點云作為分析數據集,如圖3所示。

(a)basketball_player_vox11 (b)dancer_vox11圖3 分析數據集Fig.3 The analysis dataset

對分析數據集進行基于LoD的無損壓縮,統(tǒng)計點云中每個點的預測殘差情況,并將預測殘差的分布擬合為拉普拉斯分布,擬合精度由相關系數的平方(R2)來度量,結果如圖4所示。圖中,p(e)為概率,e為預測殘差。

(a)basketball_player_vox11

(b)dancer_vox11圖4 預測殘差的分布Fig.4 Distribution of prediction residuals

(1)

式中Me為預測殘差e的平均絕對誤差。

Me和熵是單調遞增的關系。因此,將熵或碼率的最小化問題轉化為Me的最小化問題是合理的。

對分析數據集分別設置不同的參數進行無損壓縮,得到碼率和預測殘差的關系,如圖5所示?？梢钥闯?碼率隨著Me的增大而增大。所以,本文利用Me的最小化來等效碼率的最小化是可行的,與理論推導一致。

(a)basketball_player_vox11

(b)dancer_vox11圖5 預測殘差與碼率的關系Fig.5 Relationship between prediction residual and bitrate

在LoD劃分中,每一個細節(jié)層相當于對原始點云不同程度的均勻采樣,其預測殘差也服從拉普拉斯分布。以點云basketball_player_vox11為例,細節(jié)層L3的預測殘差分布及擬合結果如圖6所示。

圖6 basketball_player_vox11細節(jié)層L3的預測殘差分布Fig.6 Distribution of prediction residuals in the detail layer L3 of basketball_player_vox11

對于增強層中的預測殘差的分布,以點云basketball_player_vox11為例。增強層A6和A8的預測殘差分布及擬合結果如圖7所示?？梢钥闯?對應的增強層的預測殘差也服從拉普拉斯分布。因此,本文使用各LoD層的預測殘差來代替碼率進行建模。

(a)增強層A6

(b)增強層A8圖7 basketball_player_vox11增強層的預測殘差分布 Fig.7 Distribution of the prediction residuals in the refinement layers of basketball_player_vox11

2 預測殘差模型及性能優(yōu)化

2.1 預測殘差模型及性能分析

LoD對點云壓縮性能的影響來自于不同的預測方式,因此本小節(jié)主要針對此問題進行分析。

以LoD第一次劃分為例,在經過一次采樣后,點云被劃分為了細節(jié)層L2和增強層A1。按照LoD的順序,首先對L2中的點進行預測編碼,其可用參考點仍然具有原始點云的特點,即位于受限于編碼順序的空間方向上。同時,又由于經過采樣,相鄰點之間的最小距離變大,使得它們之間的相關性減弱,導致預測的效果變差,從而造成編碼性能的損失。對于其后進行編碼的A1中的點,參考點不僅可以選擇本層中已編碼的點,還可以選擇已編碼的L2中的點,因此參考點的可選范圍更大,且位于空間中的多個方向,同時相鄰點之間的最小距離與原始點云一致,由此提高了預測的準確度,提升了編碼性能。對于整個點云,若A1的性能增益大于L2的性能損失,則LoD劃分可以提升預測編碼性能。

為了準確分析LoD劃分前后的性能變化情況,利用預測殘差建立數學模型。設A1中的點數占L1(原始點云)的比例為r1,那么L2占L1的比例則為1-r1。L1在劃分LoD后的預測殘差平均絕對誤差可以表示為

(2)

式中:EL2為L2的預測殘差平均絕對誤差;EA1為A1的預測殘差平均絕對誤差。

與不劃分LoD時L1的預測殘差平均絕對誤差(記為EL1)相比,預測殘差的變化記為Δ1,有

(3)

(4)

式中:rN為AN占LN的比例;ELN+1為LN+1的預測殘差平均絕對誤差;EAN為AN的預測殘差平均絕對誤差。

LN的預測殘差變化ΔN可表示為

(1-rN)(ELN+1-ELN)+rN(EAN-ELN)

(5)

式中ELN為LN未進一步劃分LoD時的預測殘差平均絕對誤差。

令δ1=ELN+1-ELN,δ2=EAN-ELN,可得

ΔN=(1-rN)δ1+rNδ2

(6)

由于LN+1是對LN的采樣,因此LN+1中相鄰點之間的距離要大于LN,其相關性更差,有δ1>0,即隨著LoD的劃分,新的細節(jié)層通常會有性能的損失。對于δ2,可以認為是AN中的點使用何種預測方式最優(yōu)的問題。根據2.1小節(jié)前半部分中的分析,對于增強層的預測方式,參考點的分布更加廣泛并且具有全向性,可以提高預測的準確度和編碼性能,因此EAN

綜合分析δ1和δ2帶來的性能變化可知,式(6)為0時的編碼性能最優(yōu),此后的劃分都不會帶來編碼性能的增益,反而會造成性能損失,如圖8所示。

圖8 ΔN與劃分層數N的關系Fig.8 Curves of ΔN vs. number of LoD layers N

(7)

式中pN為LN中的點占全部點的比例,公式為

(8)

其中ri為Ai占Li的比例,與初始采樣距離和各層之間的采樣距離比有關。

當式(7)為0時,編碼性能達到最優(yōu)。為了求解最優(yōu)值,需對兩種預測方式下的預測殘差進行擬合。

由空間相關性可知,預測殘差與距離相關,因此將它們表示為距離的函數。對于細節(jié)層Lj,設

ELj=f(d1,j)(j=1,2,…,N)

(9)

式中d1,j是Lj中相鄰點之間的距離。

對于增強層Ai,設

EAi=g(d2,i)(i=1,2,…,N)

(10)

式中d2,i是Ai中相鄰點之間的距離。

點云dancer_vox11兩種預測方式的對比如圖9所示。將ELj和EAi的擬合結果代入式(7),可得

圖9 dancer_vox11中兩種預測方式的對比Fig.9 Comparison of prediction methods in dancer_vox11

(11)

式中:d1,N和d1,N+1分別為細節(jié)層LN和LN+1中相鄰點的距離;d2,N為增強層AN中相鄰點的距離。

將式(6)代入式(7),可得

(12)

2.2 面向點云無損壓縮的快速LoD劃分方法

由于當前基于LoD的點云壓縮方案適用于均勻采樣或者平滑的點云,對于非均勻采樣和噪聲點云并不適用[15],因此本文主要針對均勻采樣或者平滑的點云,并由此簡化2.1小節(jié)中所建立的模型式(11)。

在實際中,點云中的點都位于物體表面,因此在較小區(qū)域內點云可以被視為二維平面,如圖10所示。

圖10 點云表面小區(qū)域內點的分布示意Fig.10 Points in a small region of surface in point cloud

在G-PCC中,相鄰兩次采樣距離比都固定為2[7],因此除第一次采樣比r1以外,其余每次采樣比ri(i>1)都幾乎相同,約為3/4。式(11)可以簡化為

(13)

圖與劃分層數N的關系Fig.11 Graph of and the number of LoD layers N

圖12 所提方法流程Fig.12 Flow chart of the proposed method

對點云進行LoD劃分,在每一層的采樣結束后,計算當前細節(jié)層Li占原始點云的比例,并判斷是否小于終止閾值θ。若小于θ,則結束LoD劃分,進行預測編碼;若不小于θ,那么判斷當前LoD層數i是否小于編碼端預設的LoD層數N,若小于,則繼續(xù)LoD劃分,否則結束劃分,進行預測編碼。

3 實驗與分析

3.1 數據集

在第3節(jié)中,進行了大量的實驗來評估所提方法。實驗選取了G-PCC的靜態(tài)對象與場景數據庫Cat1-A[18]作為測試集(分析數據集中的點云除外),這些點云也被廣泛應用于評估各類點云壓縮方法性能的實驗中[6,18-20]。

3.2 評價指標

為了評估壓縮的性能,本文對比了碼率比R′、編碼時間比TE、解碼時間比TD共3種指標。碼率比R′的計算公式為

(14)

式中:Rp是點云按照所提方法進行無損壓縮后的屬性碼率;RG為點云根據G-PCC的通用測試條件(CTC)進行無損壓縮后的屬性碼率。

編碼時間比TE為所提方法的編碼時間與G-PCC(參數參照CTC設置)的編碼時間的比值;解碼時間比TD為所提方法的解碼時間與G-PCC(參數參照CTC設置)的解碼時間的比值。

3.3 結果分析

將所提方法與G-PCC(參數參照CTC設置)進行比較,對測試集使用G-PCC TMC13 v9點云壓縮平臺[7]進行無損壓縮,結果如表1所示?？梢钥闯?當閾值θ=0.003時,與設置為CTC時相比,碼率沒有增加,而編解碼時間則顯著減少,平均節(jié)省了約4%的編碼時間和6%的解碼時間。

表1 所提方法與CTC的性能對比

對于絕大多數點云,在通過本文閾值終止LoD劃分時,其性能已經達到最優(yōu),與CTC一致,因此碼率比R′為100%。若進一步劃分LoD,新的細節(jié)層中相鄰點的距離呈指數增大,使得其相關性急劇下降,性能損失較大;對于新的增強層,雖然對改善預測的準確性有一定的效果,但所帶來的增益與細節(jié)層的損失相互抵消,因此無法進一步減小碼率。同時,這部分點的比例又足夠小,兩個因素綜合起來使得壓縮后的碼率維持不變,達到最小。

對個別的點云,碼率比R′略微大于100%,例如loot_vox12的100.01%,表明所提方法的碼率大于CTC的碼率。這是由于本文方法使用了統(tǒng)一的閾值,可能造成一定的誤差,使得LoD較早結束了劃分。此時,最頂端的細節(jié)層中的點還存在一定的相關性,若再繼續(xù)劃分LoD,還會有一定的性能增益,但是由于這部分點的數量已經非常少,根據2.1小節(jié)中的分析,其影響也非常有限。

另外還有一種很少見的情況,例如ULB_Unicorn_vox13的碼率比R′小于100%,即此時本文方法的碼率小于CTC的碼率。這類點云的內容較為復雜,相似點大多集中在較小的范圍內,如圖13所示。

圖13 ULB_Unicorn_vox13點云Fig.13 Point cloud ULB_Unicorn_vox13

在達到閾值后,若再進一步劃分LoD,由于新的細節(jié)層中相鄰點的距離呈指數增大而使得其相關性急劇下降,性能損失較大。另一方面,新的增強層對提升預測準確性的效果甚微,甚至反而會降低預測準確性,因此本文方法性能會有一定的下降,碼率比R′小于100%。

表2對比了CTC中的LoD層數NG和本文方法實際劃分的LoD層數N*?？梢钥闯?對于測試集的每一個點云,N*都遠遠小于NG,因此避免了不必要的LoD劃分過程,節(jié)省了寶貴的編解碼時間。

表2 LoD層數對比

本文提出了通過設置終止閾值優(yōu)化LoD劃分的方法,無需考慮各層LoD的采樣距離。實驗中使用的閾值僅是通過兩個分析點云進行簡單統(tǒng)計得到的,將其用于均勻采樣或者平滑點云的測試集已經獲得了較好的效果。當然,閾值的設置并不僅限于此,可以通過更多的訓練得到更優(yōu)的閾值。

4 結 論

本文針對基于LoD的點云無損壓縮,通過分析LoD中增強層與細節(jié)層的預測方式對編碼性能的影響,并結合空間相關性的原理,建立了基于預測殘差的LoD優(yōu)化模型。在實際應用中,特別是對編碼端的實時性要求較高的場合,對每個未知點云都進行預編碼或在線計算是不現實的,為了降低實現復雜度,本文提出了一種基于均勻采樣及平滑點云特性的模型參數簡化方法,并在此基礎上實現了一種基于閾值的LoD劃分快速方法。實驗結果表明,在通用測試條件下,所提方法與G-PCC相比,在碼率未增加的同時,節(jié)省了約4%的編碼時間和6%的解碼時間。

本文方法避免了對點云進行預編碼或在線計算的復雜過程,提高了所建模型的實用性。僅通過閾值控制實現LoD的性能優(yōu)化,在達到最小編碼碼率的同時避免了無效的LoD劃分,節(jié)省了編解碼時間,提高了點云壓縮的實時性。

下一步將研究快速和高效的預編碼和在線計算的方法,實現對任意未知點云編碼性能的自適應優(yōu)化。另外,本文所建立的模型并不僅限于點云的無損壓縮,還可擴展至點云有損壓縮的率失真優(yōu)化。