復雜曲面點云非均勻簡化技術研究

高紅衛，劉慶剛

（1.寶雞文理學院機電工程系，陜西 寶雞721016；2.濟寧職業技術學院機電工程系，山東 濟寧272037）

0 引言

逆向工程是以產品實物、模型作為研究對象，根據測量三維點云數據通過幾何建模方法重構實物模型的過程。在三維數據測量和曲面重建過程中借助計算機硬件設施及相關軟件為研究平臺，充分利用數字化優勢，有利于產品設計向智能化、集成化方向發展，是一種產品設計的新手段［1］。實物模型表面信息由大量三維坐標數據來精確描述，數以百萬的冗余數據，使得數據運算速度降低、曲面重構難度增大。因此，點云數據簡化非常必要。近些年來，人們在點云簡化方面做了大量研究［2－5］。通常，對于簡單規則點云數據精簡方法較多，容易實現，但對于曲率變化大的復雜曲面，點云直接進行簡化時容易出現特征點丟失等問題、有時甚至難以直接簡化。

針對復雜曲面點云簡化問題，提出按照曲率分塊，自動劃分特征區域的非均勻數據精簡方法。通過建立點云之間拓撲關系，按照曲率大小進行數據分塊，劃分特征點區域，點云曲率較大的細節特征區盡可能多保留數據，較非特征區域數據將被大量簡化，從而可以解決數據精簡時特征點丟失問題。

1 點云拓撲關系的建立

通常海量點云數據之間相互獨立，沒有任何聯系；如果在同一坐標系中，把每一個點看作構成整個物體的分子，通過計算鄰近關系點，來進一步表達點在整個點云模型中的幾何性質，構成點云數據的模型就像分子與分子之間關系一樣，使孤立點云形成一個相互聯系的整體，建立點云之間的關系。

點云拓撲關系建立采用最鄰近分類算法［6］。思路如下：在定義類決策上由待分樣本所屬的類別依據最鄰近的一個或者幾個樣本類別來決定（假設所選擇的鄰近點都是已正確分類的對象），主要根據周圍有限的鄰近樣本來確定所屬類別。在類別決策時，只與少量相鄰樣本有關。因此，該方法適合于類域的交叉或重疊較多的待分樣本集。

KNN算法數學描述：給定數據集D，可根據KNN（q）＝｛｜pi－q｜≤｜p－q｜，pi∈D｝，pi，（i＝1，2，3，…，k）計算得到q的鄰近點。首先把點云數據按空間位置將每一維進行區間劃分，通常劃分成n個子區間，再把每一個區域進行編碼，最后根據編碼尋找落在鄰近區域中的點，直到找出數據點q的k個最近的點，計算流程如圖1所示。

圖1 算法流程

2 點云曲率計算數學模型

2.1 點云曲率

曲率用來度量幾何體的不平坦程度，能夠表示曲線彎曲的程度。即L＝lim｜Δα／Δd｜，Δd趨向于0時，定義L為曲率；當角度和弧長同時趨近于0時，就是光滑曲線曲率的定義。對于點云模型而言，數據點之間是離散的，無法對單獨一個點計算曲率；通常點云曲率定義為點與點之間形成的曲線（或者曲面）的彎曲度［7］。因此，計算離散點云的曲率時，首先計算采樣點的K最鄰近點，利用鄰近點形成的局部曲面計算曲率信息。在連續曲線中，平面曲線曲率是指曲線上某個點的切線方向角對弧長的偏離程度；若曲率值越小，則曲線越平坦；反之，曲線彎曲度越大［7］。

2.2 曲面微分法計算點云曲率

在對離散點云建立拓撲關系后，得到樣點k個鄰近點，對k＋1個點進行局部曲面擬合、微分即可求得點的曲率。為了達到較好擬合效果，采用雙三次B樣條曲面微分法計算點云曲率［8］，其定義為：

Bi，j為曲面控制點；Ni，k與 Mj，l分別為u 和v 方向的三次B樣條基函數。Ni，l（u）與 Ni，k（u）可分別用下式來表示，即

Mj，I（v）定義與 Ni，k（u）類似，為曲面的另一基函數，根據式（1）建立B樣條曲面方程為：

對鄰近點進行擬合得到局部曲面，并對曲面進行偏導得到點的一階導數二階導數和混合偏導，結果為：

根據一階、二階導數、混合偏導及微分幾何中曲率的定義，計算采樣點的平均曲率為：

（A B C ）＝［Wu×Wv］［WuuWuvWvv］，計算出的點云平均曲率和曲面面積的第一積分密切相關，點云曲率變化越大，則說明曲面越復雜。

3 特征點區域劃分方法

點云特征點是描述復雜曲面幾何特征信息的關鍵元素，在簡化點云時保留特征點尤為重要。通過計算點云曲率對點云分塊，進行特征區域自動劃分。在非特征點區域，按照均勻取樣法進行數據精簡；在特征點區域隨著點云曲率的減小精簡率依次增大，實現根據曲率變化進行非均勻簡化。為了有效提取點云模型曲率較大的特征點，可根據K鄰近點坐標集構造函數［9］，即

np為p 點的法矢；｛xj｝（1≤j≤k）為p的K 鄰近點pi的坐標集；｜（x－xj）·np｜為pj到p 點處切平面的距離。在計算特征點過程中，選擇不同的K值可得到不同簡化效果。一般情況下，c（p）計算值越大，則點云在該處的曲率就越大；為了劃分點云特征點區，可以通過改變δ值（δ＝α／N∑c（pi））的范圍來確定特征點。其中，N為點云數目，α為特征點調節系數；當α改變時，δ值可隨之成正比變化。點云特征區域劃分原則：如果c（p）大于閥值δ，則判定p為特征點；否則，認為p為非特征點。大量實驗表明，當α值取22≤α≤28時，點云具有較好的簡化效果。通過改變調節系數α的大小，來設置特征點區域范圍。

當α＝22時，設定為特征點上限區，如圖2所示。若曲率值過大，點云光順性不僅變差，且該處點云可能存在噪聲點，應按非特征點對待。當α＝28時，設定為點云特征點下限區，如圖3所示。處于點云特征點上限區①與下限區④之間的點都劃分為特征點區，如圖4所示。曲率值小于下限區④時劃分為非特征點區域，曲率值較小，點云處于較平坦區域，該處點云應被大量簡化。

圖2 α較小時特征點上限區

圖3 α較大時特征點下限區

圖4 點云特征點區域范圍

4 點云簡化效果分析

通過將OpenGL圖形庫函數嵌入到VS2008中，完成三維空間的點云數據在二維環境中計算和轉化及處理。空間散亂點云的每個點都有3個數據，即X，Y，Z坐標，每個點云對應1個ASCII值，可將每個點云數據信息存儲在預先定義的一個共同體內，對共同體中定義的數據進行分析，并可以將其存入相應的數組來實現［10］。因此，以米奇面部點云模型為例，分別采用系統算法和均勻取樣法進行簡化，對結果對比分析。

米奇面部點云特征復雜、原始點數多達38 431個，如圖5所示。在耳根處、眼部及嘴部周圍點云曲率較大，特征點較多，局部細節特征明顯。通過建立點云拓撲關系，分析面部點云曲率。根據曲率大小自動進行區域劃分，紅色區域點云曲率較大，屬于特征點區域范圍；在其耳部中心區、額頭及嘴唇等處點云較為平坦，如圖6中虛線選擇區域，屬于非特征點區。顯然，劃分結果與實際面部特征較為吻合。

圖5 米奇面部特征點云

圖6 面部點云非特征點區域

表1 實驗參數

按照表1中實驗參數，采用文中算法簡化后點云數為9 213個，精簡率為76%，如圖7所示。采用均勻取樣法，精簡率為77.4%，簡化效果如圖8所示。通過分析發現，2種方法都能完成點云精簡。在精簡率相近時，均勻取樣法視覺效果較好，但特征點丟失較多，影響后續曲面重構精度；顯然通過比較簡化效果，本文方法能實現在曲率較大處點云密度也大，特征點被更多保留，簡化方法更加合理。

圖7 本文算法點云簡化效果

圖8 均勻采樣法點云簡化效果

5 結束語

針對復雜曲面點云簡化，均勻取樣法簡化時不能預測哪些點將被去除，點云密度大小僅由取樣間隔決定，容易造成曲面點云簡化失真等問題；通過分析曲率云圖，進行特征區域劃分，點云密度大小隨著曲率的減小而降低，在非特征點區域精簡率最大。實驗結果表明，當特征點調節系數α值在22≤α≤28范圍內時，點云簡化效果較好，精簡率達76%，該方法針對復雜曲面點云簡化具有一定的研究應用價值。

［1］ 單 巖，謝斌飛.Imageware逆向造型技術基礎［M］.北京：清華大學出版社，2006.

［2］ Chen Y H，Neg C T，Wang Y Z.Data reduction in jntegrated reverse engineering and rapid prototyping［J］.Intemational Journal of Computer Integrated Manufacture，1999，12（2）：97－103.

［3］ Sun W，Bradley C，Zhang Y F.Cloud data modeling em ploying a unifed non－redundant triangle mesh［J］.Computer Aided Design，200l，33（2）：183－193.

［4］ 馬 磊，彭國華，耿東方.基于八叉樹的海量測量數據的非均勻簡化［J］.計算機應用，2007，27（8）：2027－2029.

［5］ 王宏濤，張麗艷，杜 佶，等.測量點集的簡化及其隱式曲面重建誤差分析［J］.中國圖象圖形學報，2007，12（11）：2114－2118.

［6］ Vries A D，Mamoulis N，Nes N，et al.Efficient KNN search on vertically decomposed data［C］.Proceedings of the 2002ACM SIGMOD International Conference on Management of Data，Madison，Wisconsin.Madison：ACM press，2002：322－333.

［7］ 賀美芳，周來水，神會存.散亂點云數據的曲率估算及應用［J］.南京航空航天大學學報，2005，36（4）：516－519.

［8］ 吳劍煌，劉偉軍.點采樣曲面的曲率估計［J］.儀器儀表學報，2006，27（12）：1557－1564.

［9］ Song H，Feng H Y.A progressive point cloud simplification algorithm with preserved sharp edge data［J］.O－riginal Article，2009，45：583－592.

［10］ 張樹森，鄭成志，肖勝兵，等.基于 MFC環境下利用OpenGL函數實現點云數據拼合［J］.機床與液壓，2006，（2）：76－78.