一種基于局部曲率特征的點云精簡算法

麻衛(wèi)峰，周興華，徐文學(xué)，潘光江

（1．山東科技大學(xué) 測繪科學(xué)與工程學(xué)院，山東 青島266510；2．國家海洋局第一海洋研究所，山東 青島266061）

三維激光掃描技術(shù)具有非接觸、速度快、效率高等優(yōu)點，近年來逐步發(fā)展為實物數(shù)字化的主要方法之一。但激光掃描產(chǎn)生的點云數(shù)量巨大，遠(yuǎn)遠(yuǎn)超過了研究掃描物特性所需要的點云數(shù)量，同時海量的點云數(shù)據(jù)嚴(yán)重降低了數(shù)據(jù)處理效率。因此如何在保證精度的前提下有效精簡壓縮點云數(shù)據(jù)，用較少的點描述掃描物的屬性特征成為點云數(shù)據(jù)處理過程中的重要環(huán)節(jié)。

曲率精簡原理是利用曲率的變化，采用一定的判斷原則決定點的保留與刪除（曲率大的地方保留足夠多的點，曲率小的地方保留較少的點）［1］。目前國內(nèi)針對曲率的點云精簡算法主要利用斜率、距離以及角度等進(jìn)行精簡。劉春，吳杭彬等利用斜率變化描述曲率變化，提出基于斜率變化的點云精簡方法［2］；喜文飛，方源敏等［3］針對點云三角網(wǎng)模型中相鄰兩三角形頂點與邊的關(guān)系，提出基于相鄰三角形法向夾角為閾值的精簡方法，認(rèn)為三角形與鄰接三角形的夾角決定了該區(qū)域的平滑度，夾角越大說明區(qū)域曲率變化越大，區(qū)域變化越復(fù)雜，保留點越多；張麗艷［4］等人研究了用Riemann圖建立散亂測點間的鄰域關(guān)系，分別提出了基于簡化后的數(shù)據(jù)集中點個數(shù)、數(shù)據(jù)集中點的密度閾值及刪除一點引起法向誤差的閾值準(zhǔn)則的數(shù)據(jù)精簡方法，但存在對臨近點個數(shù)k的選取依賴過大的缺點；王玉國，周來水等人提出基于曲線曲率和采樣的自適應(yīng)精簡壓縮方法［5］。上述算法只考慮掃描線或者點曲率變化，沒有考慮某個范圍內(nèi)的曲率變化，不能綜合某個范圍內(nèi)的表面特征進(jìn)行精簡。針對這種情況，本文利用局部曲率中誤差大小來衡量局部區(qū)域內(nèi)的曲率變化，并設(shè)置局部曲率中誤差變化閾值，當(dāng)局部曲率中誤差大于閾值時，認(rèn)為該區(qū)域是復(fù)雜區(qū)域，應(yīng)保留較多點 否則為平緩區(qū)域 保留較少點 最后統(tǒng)計每個點的精簡概率，根據(jù)精簡概率判定點的取舍。

1 曲率計算

曲率反應(yīng)曲面性質(zhì)的重要特性，也是曲面特征識別的主要依據(jù)之一。目前曲率計算的常用方法有：圖像梯度求解法［6］，三角格網(wǎng)法［7］，二次曲面擬合法［8－9］。二次曲面擬合法穩(wěn)定性較強(qiáng)且計算步驟比較簡單，本文使用該方法計算曲率，其基本思想為：取點云中任意一點Pi（1≤i≤n，n為點云個數(shù)），利用點Pi的k個臨近點擬合二次拋物面Z（X，Y），通過計算Z（X，Y）的主曲率及主方向確定點Pi的曲率。

1．1 K鄰域構(gòu)建

由于散亂點云沒有明顯的幾何分布特征，呈散亂無序狀態(tài)，為了能最大限度地提取出原始數(shù)據(jù)中有用的信息，需要建立數(shù)據(jù)點之間的空間關(guān)系，即空間數(shù)據(jù)點之間的空間拓?fù)潢P(guān)系和鄰域信息［10］。國內(nèi)外已有很多點云拓?fù)潢P(guān)系的研究，常見的有3種方法：基于八叉樹的空間劃分、空間包圍盒法和K－d tree法［11］。由于空間包圍盒法具有較高的搜索效率，本文采用該方法建立點Pi的鄰域集合，即與點Pi的歐式距離最近的k個點構(gòu)成的集合，記為｛k－NB（Pi）｝，其中1≤i≤k。國內(nèi)外學(xué)者對鄰域數(shù)據(jù)量k的確定做了大量實驗，證明k取24～30為最佳，太小不能滿足精度要求，太大影響計算效率［12］，本文k取28，即｛28－NB（Pi）｝。

1．2 空間二次曲面擬合

建立點Pi的28鄰域集合后，對其鄰域集合內(nèi)任一點Pj∈｛28－N（Pi）｝，根據(jù)最小二乘原理，須使式（1）取最小值，即

對式（2）中系數(shù)a，b，c分別求導(dǎo)，并使其為0，則有

聯(lián)立式（3）可求出方程系數(shù)a，b，c的值。

1．3 空間點平均曲率計算

對于拋物面Z（X，Y），根據(jù)微分幾何關(guān)系求解其微分算子，可得到曲面一階偏導(dǎo)數(shù)ZX，ZY；二階偏導(dǎo)數(shù)ZXX，ZYY，ZXY。

拋物面Z（X，Y）第一基本量

拋物面Z（X，Y）第二基本量

式中n是點Pi的單位法向量

點Pi的平均曲率為

2 點云精簡算法

每個點處于不同的鄰域范圍內(nèi)（設(shè)鄰域個數(shù)為Su m），由于不同鄰域范圍的復(fù)雜程度不一樣，同一點不同鄰域的精簡結(jié)果不同（設(shè)點保留次數(shù)為Flag），精簡概率即是同一點不同鄰域的保留次數(shù)占總鄰域個數(shù)的百分比，即：q＝Flag／Su m。本算法的基本思想如下：通過計算鄰域范圍內(nèi)的局部平均曲率中誤差σi并與設(shè)置的閾值比較。當(dāng)平均曲率中誤差大于閾值時，保留平均曲率大于曲率平均值λ倍的點（λ為比例系數(shù)）；當(dāng)平均曲率中誤差小于閾值時，保留平均曲率最接近曲率平均值的點。同時將點標(biāo)記累加1（即保留次數(shù)增加1次），最后計算每個點的精簡概率，判定點的取舍。具體步驟如下：

Step1：定義點Pi（1≤i≤n，n為點云數(shù)）的結(jié)構(gòu)體變量：

Str uct｛

Hi＝0 %定義每個點的平均曲率初值 Pi＝［x，y，z］； %點坐標(biāo)存儲；

Flagi＝0； %點標(biāo)記初值

Su mi＝0； %點計算次數(shù)初值

Delect＝｛1，0｝；%計算結(jié)果，1則表示刪除該點；0表示保留該點

｝。

Step2：計算所有點的平均曲率H。

Step3：對點云中點Pi及其鄰域集合內(nèi)任一點Pu∈｛28－N（Pu）｝，求平均曲率的平均值＝Hu，其中1≤u≤k，Hu是點Pu的平均曲率值。

Step5：當(dāng)σi≥σ時，保留平均曲率Hu≥λ的點，刪除平均曲率Hu≤λ的點；當(dāng)σi＜σ時，保留點平均曲率Hu最接近曲率平均值的點。同時將保留點標(biāo)記累加1，即Flagu＝Flagu＋1，為后續(xù)計算點精簡概率，鄰域范圍內(nèi)所有點計算次數(shù)累加1，即Su mu＝Su mu＋1；其中1≤u≤k。

Step6：遍歷所有點云，統(tǒng)計每個點的精簡概率q，q＝Flagu／Su mu。精簡概率q大于等于0．5時，保留該點即delect＝0；精簡概率q小于0．5時，刪除該點即delect＝1。

3 實驗驗證

點云精簡率是精簡刪除的點云數(shù)與原始點云數(shù)的百分比，是點云精簡效果的重要指標(biāo)。為了驗證本文的精簡算法，本文基于matlab語言進(jìn)行了編程實現(xiàn)，采用兩組數(shù)據(jù)進(jìn)行實驗，并將處理結(jié)果與點云處理軟件Geo magic的點云精簡結(jié)果進(jìn)行了對比

Geomagic軟件是美國Rain Drop Geo magic軟件公司推出的逆向工程軟件。該軟件是目前市面上對點云處理及三維曲面構(gòu)建功能最強(qiáng)大的軟件，其中點云精簡模塊有以下4種方法：

1）曲率精簡法：減少平坦區(qū)域內(nèi)點數(shù)目，保留高曲率區(qū)域內(nèi)的點以保留細(xì)節(jié)。

2）柵格簡化法：通過設(shè)置均勻的間距，不考慮曲率和密度，減少無序點數(shù)量。

3）隨機(jī)采樣法：從無序的點云中隨機(jī)抽取一定比例的點。

4）統(tǒng)一采樣法：使平坦曲面上點的數(shù)目減少量一致，但以規(guī)定密度減少曲面上點的數(shù)目。

實驗數(shù)據(jù)1：來源于www．Pudn．co m網(wǎng)站兔子點云數(shù)據(jù)，原始激光點數(shù)目為35 947，分別取λ＝0．9，σ＝20；λ＝1．2，σ＝100；λ＝1．5，σ＝120三組參數(shù)進(jìn)行實驗，實驗結(jié)果分別如圖1（b）、圖1（c）、圖1（d）所示；Geo magic軟件曲率精簡法、柵格簡化法、隨機(jī)采樣法、統(tǒng)一采樣法處理結(jié)果分別如圖2（a）、圖2（b）、圖2（c）、圖2（d）所示。

圖1 兔子點云在不同參數(shù)下的精簡效果

圖2 兔子點云在Geomagic軟件不同方法的精簡效果

實驗數(shù)據(jù)2采用瑞士Leica公司生產(chǎn)的HDS4500型三維激光掃描儀獲取的某古建筑獅子雕像點云數(shù)據(jù)，原始激光點數(shù)目為46 500，分別取λ＝0．9σ＝0．1λ＝1．5σ＝0．8λ＝0．9σ＝0．8三組參數(shù)進(jìn)行實驗，實驗結(jié)果分別如圖3（a）、圖3（b）、圖3（c）、圖3（d）所示。

圖3 獅子雕像在不同參數(shù)下的精簡效果

圖1和圖2分別是利用本文方法和Geo magic軟件處理兔子點云的結(jié)果對比，圖3是獅子雕像點云在本文方法下的處理結(jié)果。由圖1可知，對于曲面變化較多的兔子點云，隨著λ和σ值不斷增大，精簡率不斷增加，但點云邊緣部位仍保持很好的輪廓；對比圖1與圖2可知，在相同的精簡比例下，如圖1中（b）與圖2中（a），本文方法比Geo magic軟件更能保持邊界點，尤其是尖銳部位，比如兔子耳朵邊緣部位；另外，在保持相同精簡效果的情況下，本文方法具有更高的精簡率。表1所示，對比以上兩組不同數(shù)據(jù)的精簡結(jié)果可知，對于曲率變化較小的兔子點云數(shù)據(jù)，局部區(qū)域內(nèi)曲率中誤差的變大是由于特征點（如尖銳點耳朵部位等）曲率偏大引起的，因此應(yīng)設(shè)置較大的曲率中誤差閾值σ與λ，將更多范圍內(nèi)的點云當(dāng)做平緩區(qū)域處理，在保證效果的前提下獲取更大的壓縮率；對于曲率變化的較大的獅子雕像點云，局部曲率中誤差偏大是因為更多的復(fù)雜點曲率變化引起的，因此應(yīng)設(shè)置較小的曲率中誤差閾值σ，同時增大λ，可以在保持特征點的情況下保留特征邊緣，如圖3（c）與圖3（d），以便后續(xù)特征線識別和特征重構(gòu)。由于本文方法在計算點的K鄰域、空間二次曲面擬合以及點云精簡等方面都具有較大的計算量，嚴(yán)重影響了點云簡化的速度，下一步可以研究如何在保證點云精簡精度的前提下提高精簡效率。

表1 本文方法與Geomagic方法對兔子點云精簡結(jié)果指標(biāo)對比

4 結(jié)束語

本文介紹了點云曲率精簡的常用方法，分析了當(dāng)前曲率精簡算法存在的不足，并基于現(xiàn)狀提出采用平均曲率中誤差來衡量局部區(qū)域內(nèi)曲面特征變化，將曲面劃分為復(fù)雜曲面和緩和曲面，最后計算每個點的精簡概率，判定點的刪除與保留，避免了有些重要的特征點可能被錯誤刪除的情況，保證了精簡結(jié)果的準(zhǔn)確性與穩(wěn)定性。通過實驗驗證以及與傳統(tǒng)方法對比可以看出，本文算法對點云數(shù)據(jù)具有較好的精簡效果。

［1］ FU Jing，JOSHI S B，SI MPSON T W．Shape differention of freefor m surfaces using a si milarity measure based on an integral of Gaussian cur vature［J］．Co mputer－Aided Design，2008（40）：311－323．

［2］ 吳杭彬，劉春．三維激光掃描點云數(shù)據(jù)的空間壓縮［J］．遙感信息，2006（2）：22－24．

［3］ 喜文飛，方源敏，李帥，等．一種新的激光點云數(shù)據(jù)精簡方法［J］．測繪工程，2012，21（4）：38－40．

［4］ 張麗艷，周儒榮，蔡煒斌，等．海量測量數(shù)據(jù)簡化技術(shù)研究［J］．計算機(jī)輔助設(shè)計與圖形學(xué)報，2001，13（11）：1019－1023．

［5］ 王玉國，周來水，安魯陵．一種基于曲線擬合與采樣的點云數(shù)據(jù)壓縮方法［J］．機(jī)械科學(xué)與技術(shù)，2006，25（8）：989－992．

［6］ HU Xin，XI Juntong，JIN Ye．Geometric Feature Extraction and Model Reconstr uction Based on Scatted Data［J］．Journal of Donghua University，2004（4）：33－37．

［7］ HUANG J，MENG C H．Auto matic data seg mentation for feo maric feature extraction f or m unorganized 3－D coor dinate points［J］．IEEE Transactions on robotics and Auto mation，2001，7（3）：268－279．

［8］ MILROY M J，BRADLEY C，VICKERS G W．Segmentation of a wrap－around model using an active contour［J］．Computer Aided Design，1997，29（4）：299－320．

［9］ 周煜，張萬兵，杜發(fā)榮，等．散亂點云數(shù)據(jù)的曲率精簡算法［J］．2010，30（7）：785－789．

［10］高志國，海量點云數(shù)據(jù)濾波處理方法研究［J］．測繪工程，2013，22（1）：35－38．

［11］劉艷豐，王守彬，湯仲安，等．基于K－d樹的機(jī)載LIDAR點云濾波處理［J］．測繪工程，2009，18（5）：59－62．

［12］柯映林，單東日．基于邊特征的點云數(shù)據(jù)區(qū)域分割［J］．浙江大學(xué)學(xué)報：工學(xué)版，2005，39（3）：377－382．