甘斌

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

引言

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

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

1 理論與方法

1.1 曲度

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

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

1.2 曲率計(jì)算

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

二次曲面參數(shù)方程：

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

二次曲面方程可表示為：

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

其中Z 表示該點(diǎn)的鄰域矩陣。

求解計(jì)算二次參數(shù)曲面r（u，v）的偏導(dǎo)數(shù)ru，rv，ruu，rur，rvv曲面的單位法向量n 為：

1.3 自適應(yīng)八叉樹點(diǎn)云分割

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

圖1 普通八叉樹與自適應(yīng)八叉樹對比

圖2 自適應(yīng)八叉樹流程

1.4 壓縮率

點(diǎn)云數(shù)據(jù)的壓縮率R 表示去除的點(diǎn)云數(shù)目與原始點(diǎn)云數(shù)目的比值，公式如下：

R：壓縮率；

N：原始點(diǎn)云數(shù)目；

Nk：表示壓縮后剩余的點(diǎn)云數(shù)目。

2 壓縮過程

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

圖3 點(diǎn)云壓縮流程圖

3 實(shí)驗(yàn)分析

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

圖4 本算法壓縮結(jié)果

圖5 Geomagic 壓縮處理結(jié)果

表1 本算法與Geomagic 點(diǎn)云壓縮性能對比

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

在時(shí)間壓縮過程需要用戶確定兩個(gè)輸入?yún)?shù)，即網(wǎng)格內(nèi)點(diǎn)云數(shù)目閾值和預(yù)計(jì)壓縮比，通過該參數(shù)的調(diào)整能夠直接影響點(diǎn)云的壓縮結(jié)果和壓縮效率。采用唯一變量的實(shí)驗(yàn)方法，基于不同參數(shù)對兔子點(diǎn)云數(shù)據(jù)進(jìn)行壓縮，壓縮結(jié)果與耗時(shí)統(tǒng)計(jì)如表2 所示。對結(jié)果進(jìn)行統(tǒng)計(jì)分析，結(jié)果如圖6、7所示。

表2 不同參數(shù)點(diǎn)云壓縮性能

在本算法中通過唯一變量的實(shí)驗(yàn)原則，在保持網(wǎng)格內(nèi)點(diǎn)云數(shù)目閾值λ不變，更改預(yù)計(jì)壓縮率ε的值逐漸變化，通過表2和圖6 可以發(fā)現(xiàn)，隨之預(yù)計(jì)壓縮率ε 值得不斷增大，點(diǎn)云的實(shí)際壓縮率也不短增大，同時(shí)壓縮時(shí)間逐漸減少；當(dāng)預(yù)計(jì)壓縮率ε不變時(shí)，隨著點(diǎn)云數(shù)目閾值λ 的增大，實(shí)際壓縮率與壓縮時(shí)間同步逐漸增大。

圖6 λ=50，點(diǎn)云壓縮性能圖

4 結(jié)論

圖7 ε=0.5，點(diǎn)云壓縮性能圖

在曲率壓縮的基礎(chǔ)上進(jìn)一步采用曲度作為評判標(biāo)準(zhǔn)進(jìn)行點(diǎn)云數(shù)據(jù)的壓縮，能夠很好地保持點(diǎn)云的特征信息，保證良好的壓縮質(zhì)量；本算法基于八叉樹的結(jié)構(gòu)進(jìn)行點(diǎn)云數(shù)據(jù)的抽稀壓縮，能夠基于八叉樹的索引結(jié)構(gòu)極大地提高點(diǎn)云的壓縮效率，同時(shí)點(diǎn)云的八叉樹索引結(jié)構(gòu)對點(diǎn)云數(shù)據(jù)的存儲(chǔ)、傳輸、以及其他應(yīng)用具有一定的參考價(jià)值。本算法在程序性能上還能夠繼續(xù)優(yōu)化改進(jìn)，下一步研究將在算法實(shí)現(xiàn)的程序上進(jìn)一步改進(jìn)，從而提高點(diǎn)云的壓縮效率和壓縮速度。