基于數據類型轉換的點云快速有損壓縮算法

律　帥， 達飛鵬， 黃　源

(東南大學自動化學院，江蘇 南京 210096)

基于數據類型轉換的點云快速有損壓縮算法

律帥， 達飛鵬， 黃源

(東南大學自動化學院，江蘇 南京 210096)

針對海量三維點云數據為計算機存儲和傳輸增加沉重負擔的問題，提出一種基于數據類型轉換的點云快速有損壓縮算法。首先設計出一種數據類型轉化規則-FtoI規則，根據 FtoI規則將浮點數類型點云轉換成整數類型點云，然后將整數類型點云切分成許多小單元面塊，每一單元點云生成最小生成樹，按廣度優先的順序對樹形結構進行編碼。同時，按照樹形結構對父子節點的差值進行編碼，把整型差值分成兩部分編碼，符號一部分，其絕對值一部分，其中絕對值部分采用算術編碼進行壓縮。實驗表明該文算法在保證整個三維點云模型的質量情況下，具有不錯的壓縮速度和壓縮率。

三維點云；有損壓縮；浮點數；最小生成樹；算術編碼

點云數據是物體三維掃描后其三維坐標的數據信息，還可能記錄了RGB、深度等信息。隨著三維掃描系統精度和速度的提升，掃描后點云數據量將達到幾百萬甚至更大的數量級，對其網格化的時間開銷增大，網格化模型的內存開銷也隨之增大，管理操作網格拓撲信息存在諸多問題，計算機在處理多邊形網格模型的復雜度急劇增加；此外，當多邊形網格模型在屏幕中網格數量大于屏幕分辨率時，用點作為模型數據的基本單元比多邊形網格有更加明顯的效率優勢。因此基于點的圖形學在1985年，由Levoy和Whitted[1]提出，并逐漸成為計算機圖形學的研究熱點[2-4]。目前，海量點云數據為計算機存儲和傳輸增加沉重的負擔，因此研究點云數據的壓縮具有重要的意義。

點模型壓縮通常由頂點數據壓縮和屬性數據壓縮[5]兩部分組成，本文壓縮算法主要針對點模型的頂點數據進行壓縮。點模型數據的壓縮根據接收數據的方式通常分為2種：漸進式壓縮和單分辨率壓縮，漸進壓縮是低精度的粗網格模型，是從邊傳送邊顯示精細細節信息，需要構造多分辨率的層次結構，導致數據冗余，從而影響數據壓縮效果，何辰[6]的基于形狀分析的三維點云模型壓縮方法是漸進壓縮方法中一個典型的代表。點模型的單分辨率壓縮只接受整個點模型數據后才進行壓縮編碼，相對于漸進壓縮有較高壓縮率，缺點是時間效率較低，如Gumhold等[7]的壓縮編碼算法。同時點模型數據的壓縮根據能否完整的還原點云數據分為無損壓縮和有損壓縮，其中無損壓縮如王鵬杰等[8]的基于局部最小生成樹的快速無損壓縮算法，算法有較高的時間效率。由于無損壓縮率較低，多數點云壓縮算法都是有損壓縮，點云模型去除一部分點云也可以很好地保留物體的三維信息[9-10]，同時點模型的位置坐標信息都是用浮點數表示，浮點數表示的精度很大，在工程實踐中不需要很高的精度，可以降低浮點數精度，總體來說有損壓縮在壓縮率上要優于無損壓縮。

點模型數據壓縮算法為了提高壓縮率，需要在預測之后和熵編碼算法進行有效的結合，如Chen 等[11]的算法由于沒有與熵編碼算法有效結合，得到的壓縮率相對較低，而Isenburg等[12]提出了一種浮點數熵編碼壓縮算法，可以有效地提高點云數據的壓縮率。

工程實踐中對壓縮實時性和壓縮率的要求越來越高，因此本文提出一種基于數據類型轉換的點云快速有損壓縮算法，該算法是一種單分辨率點模型壓縮算法，同時結合算術編碼，有效地提高壓縮率，實驗結果表明該算法在保證整個三維點云模型的質量情況下，有著較高的壓縮速度和壓縮率，可以滿足在工程實踐中對實時性和高壓縮率的要求。

1　點云壓縮算法簡介

本文點云壓縮算法流程如圖1所示。首先本文提出一種數據類型轉換規則(float to integer, FtoI)，將浮點數轉換成對應的整數，接著將整個模型分割成多個小塊模型單元，對于點云模型切分的大小決定了點云數據壓縮時間和壓縮率的大小，單元切分的過大，導致最小生成樹的時間開銷過大，時間效率低，最大預測誤差會增大，而單元切分的過小，會導致編碼不連續性，使算法壓縮率過低，下文實驗證明單元點云數70為最佳。點云模型切分后，對每一單元再采用最小生成樹算法，對點云數據進行預測，對于最小生成樹樹形結構采用算術編碼進行編碼壓縮。對于整數類型的頂點數據，根據最小生成樹，把子父節點的差值拆成兩部分，符號位部分和絕對值部分，對絕對值部分進行算術編碼壓縮。

圖1　算法流程圖

2　點云有損壓縮算法

2.1浮點數簡介

現今計算機系統中普遍采用1985年IEEE協會發布的二進制浮點數算術標準(IEEE754)[13]，該標準定義了被廣泛使用的32位二進制浮點數(單精度) 和64位二進制浮點數(雙精度)的存儲格式。單精度浮點數在計算機中的存儲方式如圖2所示，一個單精度浮點數可分為3部分：符號位(1 Bit)、指數位(8 Bit)、尾數位(23 Bit)。

圖2　IEEE標準下浮點數存儲方式示意圖

任意二進制浮點數的數值由下式表示：

浮點數真實指數值e表示為：e=E-127。

圖3為浮點數之間的符號位、指數位和尾數位關系圖，橫坐標為實數坐標軸，縱坐標為實數對應的浮點數，如圖3所示，0.3、0.7和6.3、6.7的差值都是 0.4，但浮點數的尾數位差值分別為ox199999和ox0ccccc，表明在相同誤差下，不同的指數段，尾數位差值是不同的，指數位越大，尾數位差值越小。

圖3　浮點數符號位、指數位和尾數位關系圖

2.2FtoI規則

對于點云的三維坐標信息，用浮點數表示，其指數位不盡相同，為了直觀顯示點云的指數位部分，圖4是Bunny點云數據模型指數位的直觀示意圖，紅綠根據x坐標方向浮點數的指數位變化而變化。根據浮點數的特點，其指數位不同，因此其精度也不相同，指數位越小，表示數值的精度就越高。對于一個點云模型的數據顯示，各方向中指數位最大的坐標數據精度最低。

圖4　點云模型指數位的示意圖

如果點云的測量精度小于點云數據表示的最低精度，那么對于指數位低的高精度數據即多余的二進制數相當于估計值，沒有實際意義，可以忽略不計。相反如果點云的測量精度大于點云數據表示的最低精度，雖然指數位低的數據比指數位大的數據對模型表示更加準確，但三維重建后[14]，模型與實際物體之間誤差在指數位高的區域較大，在指數位低的區域較小，對于整個模型的質量來說由指數位高的區域決定。因此指數位較小的區域可以降低精度，使整個模型誤差達到相對的平衡。

基于以上分析，對于指數位小的點云數據無需保留太高的精度，統一將點云數據轉換成最大指數位的精度，設計出一種點云FtoI規則，將浮點數轉換成對應的整數。

FtoI規則：

(1) 將點云x, y, z坐標浮點型數據，拆成符號位、指數位、尾數位3部分，其中x, y, z各坐標最大的指數位記為Exmax，Eymax，Ezmax。

(2) 各方向坐標系的數據，根據其指數位和最大指數位的差值dif，將尾數位最左端補加一個1，即尾數位變成24位，再右移dif位，將尾數位轉換成整型。

(3) 整型數據符號位和對應的浮點數符號位相同。

FtoI規則將浮點數類型點云數據統一精度，然后轉化成整數類型，浮點數和整數可以相互轉化。FtoI規則會損失部分精度，但不會影響整個點云模型的質量，圖 5(a)為原始點云模型，圖 5(b)是經FtoI規則轉換后的點云模型；圖5(c)是原點云模型和 FtoI規則轉換后的點云模型的合并模型，可以看出在中部有很少的綠色點云，表明原點云模型和規則轉換后的點云模型幾乎完全重合，只有中部存在少部分偏差，總體說明 FtoI規則不會影響整個點云模型的質量。浮點數轉化整型有 2大優勢：①整型數據運算相比浮點數效率高，提高時間效率；②轉化后的整型數據相比浮點數去除了指數位的信息，有利于后續的壓縮和保存，減少內存開銷。

圖5　Bunny點云模型

為了定量分析有損壓縮后的模型與原模型的差別，本文提出點距誤差比的概念記為kdis，即某點與其對應有損壓縮點之間的歐幾里得距離與該點與其最近點的歐幾里得距離的比值。點與其對應有損壓縮點之間的歐幾里得距離記為diss，點與其最近點的歐幾里得距離記為disr，則：

在圖6中，a′點表示a點經過有損壓縮后的點，b點表示離a點最近的點，a點的kdis為，當三維模型重建時，線段 ab是原模型上的一條線段，而線段a′b是有損壓縮后模型上的一條線段，如果kdis比較小，說明ab和a′b越接近，有損壓縮后的模型與原模型越接近。

圖6　點距誤差比示意圖

把點云模型中點距誤差比最大的稱為最大點距誤差比，所有點距誤差比的平均值稱為平均點距誤差比，最大點距誤差比和平均點距誤差比越小，表明有損壓縮后的模型與原模型越接近。

2.3點云模型切分

為了方便后續處理，需要對點云模型進行切分，首先利用八叉樹算法進行粗切分，然后根據坐標軸依次切分。八叉樹是一種三維數據結構，如圖7所示，由Hunter[15]于1978年在其博士論文中首次提出，八叉樹的主要優點在于可以非常方便地實現集合運算，有很強的空間分解能力，可以有效地處理大量的點云數據[16]，被廣泛用于點云數據壓縮中。

圖7　八叉樹簡圖

以下是八叉樹切分算法：

(1) 記錄點云在三維坐標中，各方向最大和最小值 Xmax，Xmin，Ymax，Ymin，Zmax，Zmin。以為中心，邊長分別為最大值的最小立方體包圍盒進行八叉樹切分。

(2) 當八叉樹父節點非空，且點云數量大于N，繼續切分，否則停止切分，并設最大遞歸深度為depth，防止無窮切割。

(3) 重復步驟(2)，直至切分完畢或達到最大遞歸深度。

因為八叉樹分割時無法保證每個葉節點內的點云數量符合要求，會出現很多碎片立方體，只含有很少點云，所以要進行適當的合并處理，本文采用同一個父節點內的點云x、y、z坐標排序的方法解決這種問題，具體步驟如下：

首先假設m個點云作為一組，則取N=50 m，而最大遞歸深度根據文獻[17]分析，取 depth=20。對于一個點云模型八叉樹切分后，每個節點內點云數量在50 m以下，對于點云數量m以下的節點合并到同一父節點相鄰節點內，整個點云模型分成很多塊，記為Surfacei。

對于每個 Surfacei內的點云再進行遞歸深度為2的八叉樹切分，找出所有非空子節點中離Surfacei最小包圍盒中心最近的子節點，從子節點任意取一個點記為o，并找出離o點最近的10個點，記為qi，利用這10個點對該單元點云擬合平面進行粗估計。求矩陣：

最小特征值的特征向量，記為v，v=(xv, yv, zv)做為擬合粗平圖的法向量，點o為擬合平面上一點，如圖8所示。對xv，yv，zv的絕對值進行升冪排列。假設 Surfacei內點云數量為num，法向量v的升冪排列為yv，xv，zv，取。首先全部 num個點云按照v中絕對值最小的方向分量yv升冪排列，沿y坐標從小到大每L×m個點云一組，接著對每一組點云按照v中絕對值第二小的方向分量xv升冪排列，沿著x坐標從小到大每m個點云一組，對于最后的一組點云數量可能小于m，如果小于合并到前一組，否則單獨一組，至此點云切分完畢。

圖8　點云粗擬合平面

2.4最小生成樹生成與壓縮

在點云模型切分之后，首先需要對每個單元內點云進行預測編碼，然后進行編碼壓縮處理。文獻[7]首次將最小生成樹應用點云預測壓縮中，取得明顯壓縮效果。本文采用最小生成樹進行預測，具體以每個單元內點云之間的曼哈頓距離作為權值，采用Prim算法[18]生成單元最小生成樹。

本文Prim算法流程如下：

設G=(V, E)，其最小生成樹S=(U, TE)。

(1) U，TE為空，從V中取出一點o加入U。

(2) 查找V和U中權值最小的兩點記為x和y，從V取出x加入U，邊(x, y)加入TE中。

(3) 重復步驟(2)直到V為空。

對于點云數據的預測壓縮需要最小生成樹的信息，在對點云數據解壓時，也需要用最小生成樹的信息對其進行解碼，因此，可單獨對最小生成樹編碼壓縮，記錄父節點的子節點個數。如圖9所示，1號節點有2個子節點2和3，2號節點有1個子節點 4，采用算術編碼[19]依次記錄父節點的子結點個數。2.5頂點數據壓縮

圖9　最小生成樹示意圖

點云頂點數據首先經 FtoI規則由浮點數類型轉換成整數類型，頂點數據壓縮是對于整型數據的壓縮，具體步驟分3步：

(1) 對于每個單元塊內的點云根據其最小生成樹求對應父子節點的差值，對整型的差值進行編碼壓縮，編碼順序為最小生成樹寬度優先。樹形結構如圖9所示，編碼順序：首先編碼1號節點的原值，其次2、3號節點與1號節點的差值。然后4號節點與2號節點的差值，5、6、7號與3號節點的差值。最后8號節點與5號節點的差值，9、10號節點與7號節點的差值。

(2) 由于三維點云數存在3個坐標方向，對x、y、z 3個坐標數據分別編碼壓縮。如果直接對 32位整數差值進行編碼壓縮，會影響壓縮效果，為了提高壓縮率，減少每一個差值所占用的Bit位，在每一個單元內，求每個方向絕對值最大的差值Max，絕對值部分采用n位Bit存儲，其中n滿足以下條件：

而符號部分采用1位Bit存儲。把整型差值分成兩部分編碼，符號一部分，其絕對值一部分，整個差值所占Bit位為n+1。

(3) 為了達到更好地壓縮效果，對差值部分進行算術編碼壓縮。由于符號位部分的值0和1分布隨機，采用算術編碼沒有明顯的壓縮效果，而且增加了時間開銷，因此對符號部分直接存儲。而絕對值部分，其值小于Max，統一采用n位Bit記錄，其中一些值遠小于Max，高位中0的出現概率大于1的出現概率，因此采用算術編碼壓縮會達到較好地壓縮效果。由于大多數計算機最多支持的 80位或差不多的浮點數，必須在每次完成有限個符號后重新開始，采用增量轉換方法來代替浮點數，形成一個較大的單數取代對應的浮點數，這個單數的位數可以很大，從而解決了浮點數位數有限的不足。

3　實驗結果與分析

在CPU2.2 GHz，2 G內存，W indows 7系統的電腦上實現本文算法，點云模型采用Stanford大學標準的點云模型。

對于點云模型切分的大小決定了點云數據壓縮時間和壓縮率的大小，單元切分的過大，導致最小生成樹的時間開銷過大，時間效率低下，而單元切分的過小，會導致編碼不連續性，使算法壓縮率過低。對于單元點數的選擇，通過對Bunny模型進行實驗分析，其含40 257個點云數據。實驗數據見表1，圖10是壓縮率和壓縮時間對應趨勢的曲線圖，由圖 10可看出，隨著每單元點云數量增加，壓縮時間相應增加，而壓縮率先提高再降低。綜合數據分析，為達到壓縮時間和壓縮率的最優平衡，選點云數量為70的壓縮塊。壓縮時間以ms為單位，壓縮率以bpp(bits per point)為單位，即每個點數據所占二進制位數。

表2是3個標準點云模型的最大點距誤差比和平均點距誤差比，其中點距誤差比在10-4以下，表明有損壓縮后的點云模型與原始點云模型幾乎一致。

表3和圖11給出本文算法(簡稱New)和傳統7zip以及文獻[8]算法(簡稱Wang)壓縮率的比較，表明本文在壓縮率方面有良好的表現。同時本文算法在壓縮速度方面也有不俗的表現，平均壓縮速度約為200 k點/s，而7zip壓縮速度約為1.5 M/s，轉換成統一速度單位點/s，對于二進制文件格式點云，壓縮速度約為130 k點/s，對于文本文件格式點云，壓縮速度約為 45 k點/s，Wang算法壓縮率約為25 k點/s。同時本文解壓縮不需要壓縮時的前期處理，在時間上明顯小于壓縮時間，約為其八分之一，解壓縮平均速度為1 600 k點/s。

表1　不同點云數量對算法壓縮率和壓縮時間的影響

圖10　本文方法的壓縮率和壓縮時間隨點云數量變化曲線圖

表2　不同點云模型的點距誤差比

表3　3種算法壓縮率的對比

圖11　3種算法壓縮率的比較圖

4　結論與展望

本文提出了一種基于 FtoI規則的點云快速有損壓縮算法，該算法對部分點云的精度損失極其微小，不會影響整個三維點云模型的整體質量。FtoI規則首先將浮點數統一精度，然后轉換成整數，可以有效地減少了計算復雜度和內存開銷。實驗結果表明該算法有較好地壓縮速度和壓縮率。

浮點數表示的精度很高，但在工程實踐中有時候不需要很高的精度。本文的點云快速有損壓縮算法可以實現不同精度的壓縮，在點距誤差比很小時，可以適當降低精度，從而達到更高的壓縮率。在今后研究中可以結合點云精簡技術，根據需求對整個模型的點云數量進行處理，盡量減少壓縮時間和內存開銷。

[1] Levoy M, Whitted T. The use of points as a display primitive [R]. Chapel Hill: University of North Carolina, 1985.

[2] Kobbelt L, Botsch M. A survey of point-based techniques in computer graphics [J]. Computer & Graphics, 2004, 28(6): 801-814.

[3] Gross M, Pfister H. Point-based graphics [M]. San Francisco: Morgan Kaufman Publisher, 2007.

[4] 王鵬杰, 潘志庚, 劉勇奎. 基于點的三維模型壓縮技術研究進展[J]. 計算機輔助設計與圖形學學報, 2009, 21(10): 1359-1367.

[5] Zhang C, Florêncio D, Loop C. Point cloud attribute compression with graph transform [C]//Image Processing (ICIP), 2014 IEEE International Conference on. New York: IEEE Press, 2014: 2066-2070.

[6] 何辰. 基于形狀分析的三維點云模型壓縮[D]. 濟南:山東大學, 2014.

[7] Gumhold S, Karni Z, Isenburg M, et al. Predictive point cloud compression [C]//Proceedings of SIGGRAPH Sketches. New York: ACM Press, 2005: 137.

[8] 王鵬杰, 潘志庚, 徐明亮, 等. 基于局部最小生成樹的點模型快速無損壓縮算法[J]. 計算機研究與發展, 2011, 48(7): 1263-1268.

[9] Morell V, Orts S, Cazorla M, et al. Geometric 3D point cloud compression [J]. Pattern Recognition Letters, 2014, 50: 55-62.

[10] 范然, 金小剛. 大規模點云選擇及精簡[J]. 圖學學報, 2013, 34(3): 12-19.

[11] Chen D, Chiang Y J, Memon N. Lossless compression of point-based 3D models [J]. Proceedings of Pacific Graphics, 2005: 124-126.

[12] Isenburg M, Lindstrom P, Snoeyink J. Lossless compression of floating-point geometry [J]. Journal of Computer-Aided Design, 2005, 37(8): 869-877.

[13] IEEE 754-1985, Standard for binary floating point arithmetic [S]. New York: The Institute of Electrical and Electronic Engineers Inc, 1985.

[14] Fabio R. From point cloud to surface: the modeling and visualization problem [J]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2003, 34(5): W 10.

[15] Hunter G M. Efficient computation and data structures for graphics [D]. Princeton: Department of Electrical Engineering and Computer Science, Princeton University, 1978.

[16] Elserberg J, Borrmann D, Nuchter A. One billion points in the cloud-an octree for efficient processing of 3D laser scans [J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2013, 76: 76-88.

[17] Schnabel R, Klein R. Octree-based point-cloud compression [C]//SPBG’06 Proceeding of the 3rd Eurographics. New York: IEEE Press, 2006: 111-120.

[18] Cormen H, Leiserson E. Introduction to algorithms [M]. 3rd ed. Cambridge: The M IT Press, 2009: 624-643.

[19] Witten I H, Neal R M, Cleary J G. Arithmetic coding for data compression [J]. Communications of the ACM, 1987, 30(6): 520-540.

A Fast and Lossy Com pression A lgorithm for Point-Cloud Models Based on Data Type Conversion

Lv Shuai,Da Feipeng,Huang Yuan

(School of Automation, Southeast University, Nanjing Jiangsu 210096, China)

In order to solve computer storage and transmission problem due to massive 3D point cloud, a fast and lossy compression algorithm for point-cloud models based on data type conversion is proposed. Firstly, a data type conversion rule-FtoI rule is designed. According to the FtoI rule, float-point type point cloud is converted to integer type point cloud, then the integer type point-based surface is split into many sized surface patches, the points of every patches construct a minimum spanning tree, which is encoded in breadth first order. Besides we encode the difference between father node and son node according to the minimum spanning tree, the difference is split into two parts, one is sign, another is absolute value, which is encoded by arithmetic coding. Experiments show that this compression algorithm has a nice compression speed and compression ratio without losing the quality of point-cloud model.

3D point cloud; lossy compression; float; the m inimum spanning tree; arithmetic coding

TP 391.41

10.11996/JG.j.2095-302X.2016020199

A

2095-302X(2016)02-0199-07

2015-09-24；定稿日期：2015-10-20

國家自然科學基金項目(61405034, 51175081, 51475092)；教育部博士點基金項目(20130092110027)

律帥(1989–)，男，山東濟寧人，碩士研究生。主要研究方向為三維數據壓縮。E-mail：lssoutheast@163.com

達飛鵬(1968–)，男，江蘇南通人，教授，博士，博士生導師。主要研究方向為三維精密測量研究與應用。E-mail：dafp@seu.edu.cn