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

麻衛峰，周興華，徐文學，潘光江

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

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

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

1 曲率計算

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

1．1 K鄰域構建

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

1．2 空間二次曲面擬合

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

對式（2）中系數a，b，c分別求導，并使其為0，則有

聯立式（3）可求出方程系數a，b，c的值。

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

對于拋物面Z（X，Y），根據微分幾何關系求解其微分算子，可得到曲面一階偏導數ZX，ZY；二階偏導數ZXX，ZYY，ZXY。

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

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

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

點Pi的平均曲率為

2 點云精簡算法

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

Step1：定義點Pi（1≤i≤n，n為點云數）的結構體變量：

Str uct｛

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

Flagi＝0； %點標記初值

Su mi＝0； %點計算次數初值

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

｝。

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

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

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

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

3 實驗驗證

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

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

1）曲率精簡法：減少平坦區域內點數目，保留高曲率區域內的點以保留細節。

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

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

4）統一采樣法：使平坦曲面上點的數目減少量一致，但以規定密度減少曲面上點的數目。

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

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

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

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

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

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

表1 本文方法與Geomagic方法對兔子點云精簡結果指標對比

4 結束語

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

［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］ 吳杭彬，劉春．三維激光掃描點云數據的空間壓縮［J］．遙感信息，2006（2）：22－24．

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

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

［5］ 王玉國，周來水，安魯陵．一種基于曲線擬合與采樣的點云數據壓縮方法［J］．機械科學與技術，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］ 周煜，張萬兵，杜發榮，等．散亂點云數據的曲率精簡算法［J］．2010，30（7）：785－789．

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

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

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