點云編碼綜述

李厚強 李禮 李竹

摘要：點云編碼是支撐點云廣泛應用的關鍵技術之一，是近期技術研究和標準化領域的熱點。對點云幾何信息和屬性信息編碼技術演進進行了回顧，并針對稠密點云和稀疏點云的幾種典型編碼方法的編碼效率進行了比較。未來點云編碼研究將集中于利用幀間預測去除動態點云的不同幀之間的相關性，以及端到端點云編碼、任務驅動的點云編碼等方面。

關鍵詞：3D點云編碼；幾何信息編碼；屬性信息編碼

Abstract： 3D point cloud compression is one of the key technologies supporting the widespread use of point clouds. Recently， it is one of the focuses for both research and standardization groups. The latest advance of the compression technologies for both the 3D point cloud geometry and attribute information is reviewed. Compression efficiencies of several typical compression technologies for both the 3D dense and sparse point clouds are compared. In the future， more studies will focus on inter-frame prediction to exploit the correlations between different frames in 3D dynamic point clouds， end-to-end point cloud compression， and task-driven point cloud compression.

Keywords： 3D point cloud compression； geometry information coding； attribute information coding

點云是一系列高維空間點（例如三維空間點）的集合。每一個點包含幾何信息（x， y， z）以及顏色和反射率等屬性信息。根據點云中點的密度，點云可以粗略地分為稠密點云和稀疏點云。稠密點云可以用來精細重建3D物體例如人物等，可被廣泛應用于虛擬現實和增強現實。稠密點云重建的 3D物體支持6自由度，相比360°全景視頻僅能支持3自由度，可以給用戶帶來更好的視覺體驗。稀疏點云可以高精度重建3D場景，結合2D攝像頭采集的高清圖像視頻，可被用于自動駕駛和機器人視覺等應用中。由于點云數據量巨大，點云編碼成為了上述應用中不可或缺的一環。相比成熟的圖像視頻編碼技術，點云編碼由于其獨有的特點成為近期的研究熱點。圖像視頻中的像素在2D空間中均勻分布，而點云中的點在3D空間的分布是稀疏且無規律的。點云的稀疏性是指3D空間僅有很小一部分3D位置被點占用。從壓縮的角度來看，相比于編碼整個3D空間，僅僅編碼被占用的部分信息會更加高效。同時，點云的無規律性使得點云的不同點之間的相關性難以被有效去除。點云編碼可以根據其包含的信息分為兩個部分：幾何信息編碼指明空間中哪些位置存在3D點，屬性信息編碼指明空間中3D點的顏色和反射率等屬性信息。在大部分點云編碼算法中，都是先編碼幾何信息，然后基于重建的幾何信息和原始點云對點云進行重著色，最后編碼重著色之后的屬性信息。

1 幾何信息編碼

幾何信息編碼主要分為3類：基于樹結構的方法、基于表面近似的方法、基于映射的方法。下面我們將分別對這些方法進行詳細介紹。

1.1 基于樹結構的方法

基于樹結構的方法是最直接的幾何信息編碼方法。其基本思想是對包含點云的最小立方體以樹的形式進行迭代劃分，如果劃分完的子立方體包含點，則編碼“1”，且會被進一步劃分；不包含點，則編碼“0”，且不會被進一步劃分。在基于樹結構的方法中，使用的樹結構通常為八叉樹和二叉樹。

早在21世紀初，基于八叉樹的方法就被用于編碼點云[1]。基于八叉樹的方法首先迭代地把包含點云的最小立方體劃分為8個子正方體，然后用一個字節編碼8個子正方體是否包含點這一信息。由于父節點和子節點，以及相鄰節點的字節之間存在很強的相關性，通常使用基于上下文的算術編碼進一步去除該相關性。由于該方法簡單有效，它在國際動態圖像專家組征集的所有稀疏點云編碼方法中取得了優勝，最終發展成為基于幾何信息的點云編碼標準之一[2]。為了進一步提升編碼效率，我們提出了使用該字節中1的個數和組合來代表該字節，1的個數和組合也可以使用父節點和鄰近節點近似成的面來估計[1]。八叉樹的主要缺點是表征八叉樹需要的比特數會隨著樹深度的增加而急劇增加，所以使用二叉樹來編碼幾何信息的方法被提出[3]。點云編碼使用基于數據的二叉樹可以一定程度上緩解因深度增加所需要的比特數，但是基于數據而非空間的二叉樹需要編碼分割節點信息，尤其在樹的深度較淺時會消耗大量比特。

1.2 基于表面近似的方法

因為完整點云很難被近似成一個參數化的表面，所以基于表面近似的方法通常與基于樹的方法結合使用。首先使用八叉樹或二叉樹把點云分割成互不包含的小立方體，然后小立方體被近似成表面以進一步編碼。表面近似的方法的本質是降維，編碼一個小立方體相當于編碼三維信息，而把小立方體近似成一個表面則僅需要編碼二維信息。

在所有基于表面近似的方法中，最常用的表面是平面。我們首先對點云進行八叉樹劃分，劃分到一定的深度后，再使用平面對立方體中的點進行近似，編碼平面與立方體的交點來代表平面，最后對平面進行采樣恢復最終的點。該方法在國際運動圖像專家組征集的所有靜態稠密點云編碼方法中取得了優勝，最終發展成為基于幾何信息的點云編碼標準之一 [2]。除了使用八叉樹作為樹分割的方式，二叉樹也可以作為一種樹分割的方式來使用。除了使用采樣來恢復最終的點，也可以使用四叉樹對近似形成的平面進行基于樹結構的編碼[3]。基于平面的編碼方法相比于基于樹的編碼方法，在低碼率上可以帶來明顯的性能提升，但是由于平面近似始終存在誤差，基于平面的編碼方法無法實現無損編碼。除此之外，為了進一步提升表面近似精度，二階曲面也被用于表面近似[4]，但是二階曲面相比平面需要傳輸更多的頭信息，這會導致編碼性能提升有限。

1.3 基于映射的方法

基于映射的方法最初是針對網格（mesh）編碼設計的。近些年來，基于映射的方法逐漸開始被用于點云編碼。基于映射的方法的基本思想是把點云從3D空間映射到2D空間，然后使用成熟的2D圖像視頻編碼方法進行編碼。此方法的核心在于找到一種合適的映射，既能在投影的過程中減少點的損失，又能使投影之后的圖像視頻具有較高的時空相關性以更好地利用2D圖像視頻編碼方法中高效的預測技術。

為了盡可能在投影過程中減少點的丟失，我們以一定順序掃描點云八叉樹，把3D點云轉化為2D圖像或視頻[5]。這種投影方式不會造成任何點的丟失，但形成的2D圖像視頻時空相關性弱，編碼效率低。為了提高2D圖像視頻的時空相關性，我們提出把點云完整地投影到包圍著該點云的圓柱體或立方體上[6]。此方法的2D圖像視頻編碼效率高，但會造成部分被遮擋的連續點丟失，從而導致3D點云質量較差。為了兼顧投影點的數量和2D圖像視頻編碼效率，我們提出把具有相似法向量的點按片投影到包圍該點云的立方體上，不同的點云會形成幾十到數百個片[2]。此基于片的投影不會導致被遮擋的連續大量點丟失，因為它們會形成一個新的片投影到2D空間。此外，基于片的投影方法把具有相似法向量的點投影成一個片，使得屬于同一個片的點的深度方差較小，有利于提升編碼效率。該方法在國際運動圖像專家組征集的所有動態點云編碼方法中取得了優勝，最終發展成為基于視頻的點云編碼標準[2]。

2 屬性信息編碼

屬性信息編碼主要可以分為3類：基于變換的方法、基于預測的方法、基于映射的方法。下面我們將分別對這些方法進行詳細介紹。

2.1 基于變換的方法

變換是編碼中一種常用的去相關方法。基于變換的屬性信息編碼方法的基本思想是利用重建的幾何信息來設計一個內容自適應的屬性信息變換，以去除屬性信息之間的相關性。去除相關性之后的屬性信息經過量化和熵編碼后形成屬性信息碼流。

為了充分利用已經編碼的幾何信息，我們提出使用圖變換的方法對屬性信息進行變換編碼[7]。首先根據點與點之間的距離構建圖，然后對圖拉普拉斯矩陣進行特征值分解，最后使用特征向量構建的變換對屬性信息進行變換。除此之外，我們還提出使用高斯過程來近似點與點之間的關系，推導出高斯過程對應的K-L變換來編碼屬性信息[8]。上述方法能達到較好的編碼性能，但是需要進行復雜的特征值分解。這會導致很高的復雜度，不利于實際使用。為了更好地取得編碼性能和復雜度之間平衡，我們提出使用基于區域的自適應分層變換對屬性信息進行編碼[9]。基于區域的自適應分層變換本質上是加權Haar小波變換。根據八叉樹的每一個子節點包含的點的數量，對屬性信息進行加權小波變換，以利用幾何信息。基于區域的自適應分層變換被基于幾何信息的點云編碼標準采納，成為被推薦的靜態點云屬性編碼方法[2]。除了以上常規的基于變換的編碼方法，基于幾何信息的稀疏表達變換也被用于壓縮屬性信息[10]，但是稀疏位置信息的編碼限制了其效率。

2.2 基于預測的方法

除了變換以外，預測也是一種常用于編碼的去相關方法。不同于變換對信號進行旋轉使得其更適合編碼，預測本質上是以已編碼的信息作為條件，使用條件熵代替原信號的熵，從而提升編碼效率。和變換一樣，預測之后的信號經過量化和熵編碼后形成碼流。

在圖像視頻編碼中，基于鄰近已重建圖像塊對當前圖像塊進行預測，在各代圖像視頻編碼標準中一直沿用。在基于八叉樹的幾何信息編碼中，點云被分割成多個等大的小立方體，基于鄰近已經重建的小立方體的屬性信息對當前小立方體進行預測，是2D預測編碼到3D預測編碼的一個簡單擴展[11]。但是一方面，點云的稀疏性導致鄰近可用預測塊較少，3D預測不如2D預測有效；另一方面，如果想要使3D預測和2D預測一樣精細，在3D空間進行預測編碼需要使用比2D空間多得多的預測方向。因此，針對3D點云進行類似圖像視頻的預測并不高效。3D點云屬性信息預測通常使用分層預測[2]。我們把點云屬性信息分成不同的層進行逐層編碼，并使用已經編碼的層對待編碼的層進行加權預測。在此種方法的發展過程中，涌現出了多種點云分層方式：基于點與點之間距離的分層方法，以及基于二叉樹的分層方法等。

除此之外，我們還提出了基于提升的方式使用編碼殘差來進一步修正層間預測，以更好地提升性能[2]。由于分層預測的方法在編碼性能和復雜度之間取得了很好的均衡，該方法被基于幾何信息的點云編碼標準采納，成為了推薦的屬性壓縮方法之一。

2.3 基于映射的方法

大部分屬性信息編碼方法利用幾何信息去除屬性信息之間的相關性，以提升編碼效率；但是基于映射的屬性編碼方法則有所不同，它采用與基于映射的幾何編碼方法相同的投影方式，然后使用成熟的視頻編碼技術對重著色之后的屬性視頻進行編碼。從基本的流程上來說，基于映射的屬性編碼方法和基于映射的幾何編碼方法并沒有太大不同。在不使用幾何信息的情況下，基于高效成熟的2D圖像視頻編碼技術已經能夠取得非常好的性能。基于已經編碼的幾何信息，我們對屬性2D圖像視頻編碼器進行運動矢量預測率，并對失真方面進行優化[12]，這使得基于映射的屬性視頻編碼方法取得了進一步的性能提升。基于映射的屬性信息壓縮方法和基于映射的幾何信息壓縮方法組成了基于視頻的點云編碼標準[2]。

3 點云傳統編碼方法的比較

3.1 幾何信息壓縮性能

基于映射的方法和基于表面近似的方法都不適合稀疏點云，所以稀疏點云幾何信息幾乎只能使用基于樹的方法進行壓縮。不同于稀疏點云，稠密點云幾何信息可以使用上述3種方法進行壓縮。表1給出了相對于表面近似的方法，基于映射的方法、基于樹結構的方法壓縮稠密點云幾何信息的率失真性能結果。表1中，D1表示點到點的距離，D2表示點到平面的距離；數字表示相同點云幾何信息質量下的碼率變化。從表1可以看出，針對稠密點云，基于映射的方法會比基于表面近似的方法帶來顯著的性能提升，在相同的點到點和點到平面的距離下，基于映射的方法分別會帶來近80%和70%的碼率節省。此外，基于樹的方法相比于基于表面近似的方法，需要額外90%和70%的比特數。綜上所述，基于映射的方法可以帶來最好的稠密點云幾何信息壓縮效果。

3.2 屬性信息壓縮性能

針對稠密點云屬性信息，基于變換、預測和映射的方法均可以使用。但是基于映射的屬性信息壓縮方法通常和基于映射的幾何信息壓縮方法結合起來使用，而基于變換和預測的方法通常和基于樹和表面的幾何信息壓縮方法結合起來使用。不同的幾何信息壓縮方法會帶來不同的重著色之后的點云，所以很難單獨對基于映射的方法和基于預測和變換的方法進行直接對比。表2給出了使用基于變換的方法和基于預測的方法壓縮稠密點云屬性信息的率失真性能比較。從表2可以看出，相比于基于預測的方法，基于變換的方法對于亮度分量會帶來大約3.6%的碼率增加，對于色度分量的性能損失則更加明顯。因此，針對稠密點云，基于預測的方法可以帶來比基于變換的方法更好的屬性信息壓縮性能。

針對稀疏點云屬性信息，基于映射的方法難以使用，所以我們主要對基于變換的方法和基于預測的方法進行了對比，率失真性能如表3所示。從表3可以看出，針對稀疏點云屬性信息，相比基于預測的方法，基于變換的方法能帶來大約3%的碼率節省。綜上所述，基于變換的方法是目前業界效果比較好的稀疏點云屬性信息壓縮方法。

4 點云編碼最新進展和發展方向

近幾年來，點云幾何和屬性信息編碼技術的發展取得了長足進步，但是和傳統的圖像視頻編碼標準所能達到的編碼效率相比，仍有較大的距離。如何進一步提升編碼性能是點云編碼未來發展的目標之一。

幀間預測是傳統視頻編碼中提升壓縮效率最顯著的部分，但是對于動態點云而言，幀間預測效率目前還遠遠不夠。對于稠密動態點云幀間預測，基于片的映射方法取得了目前最優的性能，但基于片的映射方法仍存在兩個問題：首先，點云按片映射到2D視頻的過程復雜度很高，不同于視頻編碼存在成熟的市場優化方案，此映射過程目前還不適合實時應用；另外，按片映射過程不可避免地破壞了視頻的時空相關性。盡管一些人們嘗試在視頻編碼過程中通過尋找3D空間對應塊來解決此問題[12]，但如何從更源頭產生時空更連續的視頻仍然是稠密動態點云編碼中一個非常關鍵的問題。對于稀疏動態點云幀間預測，需要直接在3D空間進行運動估計和運動補償。但由于相鄰點云幀點數不完全相同，且不同點之間不存在和視頻中像素一樣的一一對應關系，所以3D運動估計和運動補償是業界一個非常困難的問題，目前還沒有一個成熟的解決方案。

基于深度學習的端到端圖像視頻編碼近期取得了長足的進步，幾乎達到或超越了傳統圖像視頻編碼的性能，這就促進了以端到端的方式對點云進行壓縮編碼的方法的使用。端到端點云幾何屬性信息壓縮是目前的研究熱點[13]。幾何信息編碼使用3D普通或稀疏卷積神經網絡來編碼每個空間位置是否存在3D點這一信息；屬性信息編碼使用神經網絡結合坐標信息編碼對應的顏色和反射率等。目前端到端點云編碼僅在稠密靜態點云方面取得了較好的效果，而針對稀疏點云和動態點云，目前都沒有較好的解決方案。另外，稀疏點云主要針對機器視覺，易于被端到端點云壓縮利用，也是未來非常值得嘗試的方向。

5 結束語

點云幾何和屬性信息編碼是支撐點云廣泛應用的關鍵技術之一。點云幾何和屬性信息編碼近些年來取得了長足的進步，但在幀間預測、編碼應用等方面仍有許多懸而未決的問題。未來人們需要進一步研究幀間預測、基于深度學習的端到端點云編碼等技術，以更高層的應用為目標設計更高效的點云幾何和屬性信息壓縮技術。

參考文獻

[1] SCHNABEL R， KLEIN R. Octree-based pointcloud compression [C]//IEEE VGTC conference on Point-Based Graphics. Goslar， Germany： IEEE VGTC， 2006， （6）： 111-120

[2] SCHWARZ S， PREDA M， BARONCINI V， et al. Emerging MPEG standards for point cloud compression [J]. IEEE journal on emerging and selected topics in circuits and systems， 2019， 9（1）： 133-148. DOI：10.1109/jetcas.2018.2885981

[3] KATHARIYA B， LI L， LI Z， et al. Scalable point cloud geometry coding with binary tree embedded quadtree [C]//2018 IEEE International Conference on Multimedia and Expo（ICME）. San Diego， CA， USA： IEEE， 2018： 1-6. DOI：10.1109/icme.2018.8486481

[4] XU Y Z， ZHU W J， XU Y L， et al. Dynamic point cloud geometry compression via patch-wise polynomial fitting [C]//ICASSP 2019-2019 IEEE International Conference on Acoustics， Speech and Signal Processing （ICASSP）. Brighton， United Kingdom： IEEE， 2019： 2287-2291. DOI：10.1109/icassp.2019.8682413

[5] BUDAGAVI M， FARAMARZI E， HO T， et al. Samsungs response to CfP for point cloud compres- sion （Category 2） [R]. Macau， China， 2017

[6] HE L Y， ZHU W J， XU Y L. Best-effort projection based attribute compression for 3D point cloud [C]//2017 23rd Asia-Pacific Conference on Communications （APCC）. Perth， Australia： IEEE， 2017： 1-6. DOI：10.23919/ apcc.2017.8304078

[7] ZHANG C， FLORENCIO D， LOOP C. Point cloud attribute compression with graph transform [C]//2014 IEEE International Conference on Image Processing （ICIP）. Paris， France： IEEE， 2014： 2066-2070. DOI：10.1109/ icip.2014.7025414

[8] DE QUEIROZ R L， CHOU P A. Transform coding for point clouds using a Gaussian process model [J]. IEEE transactions on image processing， 2017， 26（7）： 3507-3517. DOI：10.1109/tip.2017.2699922

[9] DE QUEIROZ R L， CHOU P A. Compression of 3D point clouds using a region-adaptive hierarchical transform [J]. IEEE transactions on image processing， 2016， 25（8）： 3947-3956. DOI：10.1109/tip.2016.2575005

[10] GU S， HOU J H， ZENG H Q， et al. 3D point cloud attribute compression using geometry-guided sparse representation [J]. IEEE transactions on image processing， 2020， 29： 796-808. DOI：10.1109/tip.2019.2936738

[11] COHEN R A， TIAN D， VETRO A. Point cloud attribute compression using 3-D intra prediction and shape-adaptive transforms [C]//2016 Data Compression Conference （DCC）. Snowbird， UT， USA： IEEE， 2016： 141-150. DOI：10.1109/dcc.2016.67

[12] LI L， LI Z， ZAKHARCHENKO V， et al. Advanced 3D motion prediction for video-based dynamic point cloud compression [J]. IEEE transactions on image processing， 2020， 29： 289-302. DOI：10.1109/tip.2019.2931621

[13] QUACH M， VALENZISE G， DUFAUX F. Learning convolutional transforms for lossy point cloud geometry compression [C]//2019 IEEE International Conference on Image Processing （ICIP）. Taipei， Taiwan， China： IEEE， 2019： 4320-4324. DOI：10.1109/icip.2019.8803413

作者簡介

李厚強，中國科學技術大學教授；主要研究領域為視頻編碼與通信、圖像處理與計算機視覺、多媒體信息檢索等；主持國家基金委重點項目、“973”項目、“863”項目等國家級科研項目10余項；獲2019年國家技術發明二等獎（排名第2）、2015年國家自然科學二等獎（排名第2）、2012年安徽省科學技術一等獎（排名第1）；發表論文200余篇，獲授權發明專利60余項，被視頻編碼國際標準采納提案45項。

李禮，中國科學技術大學特任研究員；主要研究領域為圖像視頻編碼、3D點云編碼等；獲2019國家技術發明二等獎（排名第5）；發表論文50余篇，獲授權發明專利9項，被視頻編碼國際標準采納提案8項。

李竹，美國密蘇里大學堪薩斯分校副教授；主要研究領域為圖像視頻編碼、圖像視頻處理、圖像視頻通信等；獲國際會議ICIP 2006最佳論文獎；發表論文100余篇，獲授權美國發明專利40余項。