一種融合曲度的自適應八叉樹點云壓縮算法

甘斌

（西安市勘察測繪院，陜西 西安）

引言

隨著激光掃描技術發展，三維點云的獲取方法越來越多、精度越來越高。同時，數據量越來越大，其中也包含著大量的冗余點。冗余點對點云配準和模型重建過程中影響模型精度和效率，因此對點云進行簡化壓縮處理十分必要[1-4]。點云壓縮是保留數據中的重要特征點，剔除一般冗余數據點。近年來，國內許多外學者對點云數據的壓縮進行了研究，在一定程度上解決了點云冗余數據量大的問題。常用壓縮方法主要是基于距離、角度、曲率、法向量等參數，采用網格、曲面擬合等方法進行點云數據的壓縮[5-6]。Song 等[7]基于幾何數據分析提出一種平滑點和邊界點的區分方法，需預先進行數據平滑處理；Lan 等[8]將點云數據分配到均勻網格中，確定網格的中心點，通過中心點曲率與網格內其余點曲率對比，刪除曲率差值小于曲率閾值的數據點，實現點云壓縮，但存在壓縮效率低的問題；龐衛峰等人[9]基于K 鄰域擬合的二次曲面計算每一個點的平均曲率，以鄰域區域內點的平均曲率中誤差為閾值對點云進行簡化壓縮，壓縮速度較快，但是壓縮效果一般。采用點云抽稀和數理統計方法的點云抽稀壓縮方法壓縮速度較快，但是壓縮效果一般；基于距離、提取中心等簡單壓縮算法普遍存在壓縮過度、點云損失嚴重、導致模型失真等問題；基于曲率、法向量的壓縮方法能夠彌補簡單壓縮方法壓縮過度的問題，但是存在壓縮效率低、內存消耗大、壓縮時間長等問題。

實驗采用最優八叉樹的分割方法對原始點云數據進行劃分，保證八叉樹葉子結點（立方體網格）內的點云數目合理，提高點云壓縮的速度和質量。對點云數據進行曲面擬合，計算每一個點的最大曲率k1、最小曲率k2、綜合曲率kp，進而計算曲度Cp[10-12]，根據網格內所有點的曲度分布情況確定壓縮閾比ε，按比例闡述刪除曲度值小的數據點，完成點云壓縮，很好地解決了傳統壓縮算法在點云壓縮的質量和速度問題，并通過實驗進行分析與評價。

1 理論與方法

1.1 曲度

曲面的彎曲程度主要由曲率表示，曲率分為平均曲率、主曲率和高斯曲率。綜合平均曲率和高斯曲率的相關特性，對兩者進行綜合利用，采用曲度來描述曲面的彎曲程度[10]。曲面中任意一點p 的曲度定義如下：

式中，Cp表示p 點的曲度，H（p）為曲面中P 點的平均曲率，K（p）為曲面中P 點的高斯曲率。

1.2 曲率計算

曲率計算主要包括平均曲率計算和高斯曲率計算，平均曲率指曲面中一點的兩個主曲率的平均值，高斯曲率指曲面中一點兩個主曲率的乘積。平均曲率和高斯曲率均反映曲面某一位置的彎曲程度。在本文中采用二次曲面擬合的方法進行點云曲率的計算，進而計算點云的曲度。局部點云二次曲面擬合及曲率計算方法參考文獻[13、14]，計算步驟包括：確定局部曲面、計算高斯曲率K（p）和平均曲率H（p），計算方法如下：

二次曲面參數方程：

本文運用Yang[15]提出的二次參數曲面逼近法得到適合的二次曲面參數方程，令

二次曲面方程可表示為：

點云u、v 參數值可以由局部參數化方法求出，式（6）中a,b,c 的下標表示Q 中的行列號。通過最小二乘法，使鄰域內個點到二次曲面的距離之和最小，推算出系數矩陣Q：

其中Z 表示該點的鄰域矩陣。

求解計算二次參數曲面r（u，v）的偏導數ru，rv，ruu，rur，rvv曲面的單位法向量n 為：

1.3 自適應八叉樹點云分割

八叉樹是由四叉樹在三維空間上擴展取得的，最早由Hunter 博士提出，八叉樹結構可應用于多個方面，如空間物體分割、索引建立、金字塔模型構建等[16]。實驗主要采用八叉樹結構對點云數據進行空間劃分，普通八叉樹分割算法對點云數據進行分割，形成的子網格數目由遞歸深度決定，由于原始點云密度分布不均勻，在點云分割過程中容易形成網格中點云數目較少、甚至空網格，造成不必要的空間和時間的浪費。為解決這個問題，在普通八叉樹的基礎上提出自適應八叉樹，根據網格內點云數目閾值停止八叉樹分割，避免空網格的出現，如圖1 所示，即當前網格點云數目小于點云數目閾值時停止該網格的繼續分割，其它分支網格根據內部點云數目判斷是否繼續分割，進而建立一個基于點云數目的自適應八叉樹，如圖2 所示。

圖1 普通八叉樹與自適應八叉樹對比

圖2 自適應八叉樹流程

1.4 壓縮率

點云數據的壓縮率R 表示去除的點云數目與原始點云數目的比值，公式如下：

R：壓縮率；

N：原始點云數目；

Nk：表示壓縮后剩余的點云數目。

2 壓縮過程

實驗采用曲度與八叉樹相結合的方式進行點云數據的壓縮，首先基于散亂點云的K 鄰域進行曲面擬合，計算點云中每一個點的平均曲率和高斯曲率，根據曲度計算公式計算點云中每一點的曲度值。對點云數據進行最優八叉樹分割，設置最小八叉樹網格內點云數目閾值，當網格內點云數目小于閾值時停止八叉樹分割，建立點云均勻分布的八叉樹網格。最后對每一個葉子結點網格內的點云基于曲度值進行排序，根據用戶輸入的預計壓縮比ε 刪除網格內曲度值較小的點云，完成網格內點云壓縮。最后遍歷所有葉子結點，完成全部點云數據的壓縮，如圖3 所示。

圖3 點云壓縮流程圖

3 實驗分析

基于曲度的最優八叉樹精簡算法是基于散亂點云的曲度Cp和預計壓縮比ε 進行點云數據的壓縮。點云的曲度信息能夠準確反應點云表面的特征信息，基于曲度的點云壓縮能夠提高點云的壓縮質量，基于最優八叉樹結構的點云壓縮能夠極大地提高點云的壓縮速度，在保證壓縮質量的前提下提高點云的壓縮速度，將壓縮質量與壓縮速度完美結合。實驗在Windows 平臺上采用C++語言編寫實現，計算機硬件配置為4G 內存、4 核3.30GHz 的intel 處理器。將本算法與Geomagic Studio 軟件中的曲率壓縮算法、柵格壓縮算法和隨機壓縮算法進行對比分析。實驗數據采用www.pudn.com 網站提供的兔子點云數據，兔子點云是經典的算法測試點云，共有35947 個數據點，采用本算法對兔子點云數據進行壓縮，最小網格內點云數目閾值ε 設置為50，壓縮比分別設置為0.1、0.3、0.5、0.8 時，壓縮結果如圖4（a、b、c、d、e）所示。采用Geomagic 軟件的曲率壓縮算法、柵格壓縮算法和隨機壓縮算法進行兔子點云壓縮處理，結果如圖5 所示，壓縮性能如表1 所示。

圖4 本算法壓縮結果

圖5 Geomagic 壓縮處理結果

表1 本算法與Geomagic 點云壓縮性能對比

通過對圖4 可以發現，點云的實際壓縮率與預計壓縮率成正比例關系，隨著預計壓縮率的增大點云的時間壓縮率也逐漸增大。通過本算法對兔子點云壓縮效果與Geomagic 軟件中幾種不同壓縮算法的比較，在壓縮率相同時，本算法的壓縮效果比Geomagic 軟件中柵格壓縮算法和隨機壓縮算法的效果都好，基于曲度的壓縮算法能夠較好的保持點云的特征信息；壓縮率相同時，壓縮效果與Geomagic 軟件中的曲率壓縮算法相似，都能夠很好的保持點云的特征信息，通過表1 可知在兔子點云的壓縮過程中，由于本算法采用八叉樹結構完成點云數據壓縮，本算法比Geomagic 軟件中的曲率壓縮算法耗時更短，效率更高。

在時間壓縮過程需要用戶確定兩個輸入參數，即網格內點云數目閾值和預計壓縮比，通過該參數的調整能夠直接影響點云的壓縮結果和壓縮效率。采用唯一變量的實驗方法，基于不同參數對兔子點云數據進行壓縮，壓縮結果與耗時統計如表2 所示。對結果進行統計分析，結果如圖6、7所示。

表2 不同參數點云壓縮性能

在本算法中通過唯一變量的實驗原則，在保持網格內點云數目閾值λ不變，更改預計壓縮率ε的值逐漸變化，通過表2和圖6 可以發現，隨之預計壓縮率ε 值得不斷增大，點云的實際壓縮率也不短增大，同時壓縮時間逐漸減少；當預計壓縮率ε不變時，隨著點云數目閾值λ 的增大，實際壓縮率與壓縮時間同步逐漸增大。

圖6 λ=50，點云壓縮性能圖

4 結論

圖7 ε=0.5，點云壓縮性能圖

在曲率壓縮的基礎上進一步采用曲度作為評判標準進行點云數據的壓縮，能夠很好地保持點云的特征信息，保證良好的壓縮質量；本算法基于八叉樹的結構進行點云數據的抽稀壓縮，能夠基于八叉樹的索引結構極大地提高點云的壓縮效率，同時點云的八叉樹索引結構對點云數據的存儲、傳輸、以及其他應用具有一定的參考價值。本算法在程序性能上還能夠繼續優化改進，下一步研究將在算法實現的程序上進一步改進，從而提高點云的壓縮效率和壓縮速度。