點云特征型面的邊界曲線擬合及曲面裁剪算法

陳華偉，袁小翠，伍 權，徐衛(wèi)平

（1.貴州師范大學機電工程學院，貴州 貴陽 550025；2.南昌工程學院江西省精密驅動與控制重點實驗室，江西 南昌 330099）

1 引言

對機械零件點云模型而言，經過分割的分片點云是零件模型表面特征型面的點云表達，對分片點云進行樣條或NURBS等曲面擬合可以獲得對應的曲面表達，從而為CAD軟件所識別。分片點云是零件表面的特征型面，其曲面重構過程主要包括曲面擬合和邊界裁剪兩個過程，其中擬合曲面是特征型面的依托面，裁剪邊界是特征型面的邊界。曲面裁剪算法很多，但快速而準確的曲面裁剪是一個難點問題，很多商業(yè)軟件中的裁剪算法仍然是商業(yè)機密[1]。算法研究上，文獻[2]針對N邊域問題，采用在域周圍曲面上構造曲線，對周圍曲面進行裁剪獲得大四邊域，對大四邊域曲面進行重采樣和曲面逼近，再對其進行裁剪得到裁剪曲面，該方法能保持各曲面間的G1連續(xù)；文獻[1]使用參數變換和開花（Blossoming）工具對多項式曲面展開多項式曲線裁剪，通過區(qū)域分割，該算法能對復雜曲面進行裁剪；文獻[3]將B樣條曲面轉換為陣列式T樣條曲面，然后利用局部細分和控制點移除法得到裁剪曲面；文獻[4]使用OpenGL實現了NURBS曲面裁剪算法，該算法只考慮了簡單曲面；文獻[5]通過UG二次開發(fā)實現了點云曲面擬合和邊界裁剪算法，并對汽車頂蓋模型進行了測試驗證。對點云逆向建模應用而言，存在復雜曲面復雜邊界，曲面裁剪應更多地考慮點云曲面重構和邊界提取問題，而且，對于特征顯著的機械零件曲面，還應優(yōu)先考慮特征保留問題。

對此，將以機械零件模型的典型型面為研究對象，展開曲面裁剪方法研究，并重點研究裁剪邊界的提取算法。邊界裁剪法的輸入是待裁剪曲面及其裁剪邊界，在逆向建模中，兩者均以點云型面為輸入，通過幾何擬合構造。研究思路，如圖1所示。

圖1 曲面邊界裁剪的思路Fig.1 Flowchart of Surface Boundary Trimming

點云型面是特征型面的點云表達，其邊界提取需經過邊界點識別、邊界點排序和邊界點擬合三個步驟。擬采用文獻[6]的場力法識別分片點云邊界，但是場力法所提取的邊界點是無序點，需要進行排序才便于曲線擬合。有界曲面的邊界為閉合曲線，而復雜閉合曲線難以通過整體逼近獲取，對此，擬采用分段擬合和拼接方式加以解決。提取邊界線之后，即可進行曲面裁剪。

2 預處理

邊界線提取是曲面裁剪的前提條件，點云邊界提取質量直接影響曲面裁剪的效果。經過識別的邊界點，構成了特征邊界的線狀點云表達，為獲得高質量的點云邊界，還需要經過去噪、排序、分段、擬合、拼接等多個步驟。

邊界線進行提取之前應對邊界點云進行去噪、排序等預處理操作，其目的是消減邊界點識別中的誤差，為邊界線提取提供更好的線狀點云質量。

2.1 近點移除

近點是指距離非常靠近的點，通常情況下，點云導入時只對重復點進行過濾，但不會過濾近點。大量近點的存在會降低點云處理效率甚至導致錯誤，線狀點云處理中，近點的存在不僅降低了點云處理速度，還會導致后續(xù)排序、去噪、曲率計算、分段等功能出錯，因此，必須事先去除近點。

設定距離值在距離誤差ε范圍內的點為近點，然后采用先標記后刪除的方法刪除近點。具體做法是：構造點云鄰域，遍歷每個點，計算鄰域點至當前點的距離d，如果d<ε，則將鄰域點標記為近點。遍歷結束后，再一次性刪除所有近點。

2.2 點云排序

采用最短距離法對無序邊界點進行排序，并通過對邊界點集構造鄰域結構，限定在鄰域內搜索最短距離點，從而提高點云排序搜索效率。

任選一點Pstart=P0∈V為排序起點，V為邊界點集，置P0為當前點，其鄰域記為Neib0，遍歷Neib0內所以節(jié)點，將與P0距離最近的點作為下一排序點，記為P1。置P0=P1，Neib0=Neib1，重復上述過程。記排序后的有序點集為V′，直至V中的所有元素進入V′?？紤]到曲面裁剪對閉合邊界的要求，上述搜索排序完成后，還需追加Pstart至V′，即可保證有序點集V′表達了閉合邊界。

2.3 去噪

線狀點云排序后，在排序路徑上，會出現一些鋸齒尖點，如圖2中的點3，這類點是邊界點的噪聲點。顯然，噪聲點直接影響線狀點云曲率估算和曲線擬合的精度，應進行去除。尖點處邊界方向會出現折回現象，因此可通過對邊界方向連續(xù)性判斷標記出邊界尖點。程序實現中，使用方向夾角Ai的范圍T進行限定，當Ai>T時，判定當前點Pi為噪聲點，予以刪除，具體實現見EdgePtDenoise函數。

圖2 排序邊界點集中的噪聲Fig.2 Noise in the Point Cloud of Sorted Boundary

同時，噪聲中尖點的存在，還會導致邊界線的自交，如圖3所示。在曲面裁剪算法中，自交邊界是非法邊界，將導致曲面裁剪失敗。為此，采用修改方向夾角閾值T，多次調用去噪算法的方法規(guī)避這一問題。T<90°表示允許邊界線中出現鈍角，這也表示邊界線只能為凸曲線；T=90°表示允許邊界線中出現直角；T>90°表示允許邊界線中出現銳角，即邊界線中允許出現凹曲線，用戶操作時，應根據當前點云邊界的特點，設定合適的不同的T值，多次調用EdgePtDenoise函數，從而達到邊界點集去噪的最佳效果，如圖3所示。

圖3 邊界線的自交與多次去噪Fig.3 Self Intersection of Boundaries and Multi-step Denoising

3 曲線分段和擬合

曲線擬合中，控制點數難以確定，整體逼近或者擬合時，甚至出現奇異值致使曲線變形和打結，從而導致曲面無法裁剪。為了更準確地描述邊界曲線，提高邊界點擬合精度，應分段擬合邊界線，然后拼接形成完整閉合邊界曲線。曲線上的特征點是分段曲線的連接點，如果能夠準確找到邊界特征點，就能實現邊界分段。

3.1 邊界點集曲率估算

曲線在特征點處分段，特征點附近曲線會發(fā)生曲率突變。因此，進行邊界點集分段的前提就是點集曲率的計算。采用多項式曲線擬合法估算離散點曲率，算法主要步驟為：

（1）構造鄰域結構Neib。對排序點集，每個節(jié)點前和后各取k/2個點作為其鄰域點，k為鄰域點數量；

（2）對每個節(jié)點i，在對應鄰域Neibi內擬合最小二乘平面PLi；

（3）Neibi內所有點向PLi投影得到投影點集

（5）多項式函數曲線在節(jié)點i處的曲率值作為節(jié)點i的曲率，其計算公式為

接下來，將提取曲率突變點。對所有節(jié)點曲率進行降序排列，設定突變點比例數r，將前N×（rN為節(jié)點數）個高曲率值對應的節(jié)點標記為曲率突變點。

3.2 邊界分段與擬合

以曲率突變點為備選特征點，通過對突變點的左右曲線歸屬判斷，去除偽特征點，最終在相鄰曲線間保留一個特征點作為分段點。顯然，分段點應該是距兩曲線距離和最小的點，以此為準則提取曲線分段特征點，算法偽代碼列于EdgePtSegment函數，該算法依次調用Preprocess、Compute和Postprocess子函數，分別為曲線分段的預處理、分段計算和后置處理三個部分，其中子函數內容以注釋形式加以說明。

排序點集，如圖4所示。其中點5可經過去噪處理去除，如果不做去噪處理，則會作為曲率突變點進入分段處理。點集［0，1，2］、［7，8，9］分別為左、右曲線點，中間點集［3，4，5，6］為備選分段點，點2為左曲線末點，其切向線為LL，點7為右曲線首點，其切向線為LR。通過計算中間點集中各點至LL和LR的垂直距離之和，可知點4具有最短距離值。點4作為左右曲線的特征分段點繼續(xù)保留在中間點集，其左點3歸入左曲線，右點5和6順序歸入右曲線。最終分段結果為左、右曲線點集分別為［0，1，2，3］、［5，6，7，8，9］。

圖4 線性點集特征分段Fig.4 Feature Segmentation for Linear Point Cloud

分段后，對各分段點集分別擬合NURBS曲線，然后分段邊界曲線進行C0拼接，形成閉合邊界曲線。采用Piegl的NURBS曲線擬合和拼接算法[7]。

4 曲面裁剪

樣條曲線、曲面均為雙參數表示，分別記為 S（u，v）、C（u，v），但是兩者的u，v參數是相互獨立的，可通過投影計算，將C（u，v）投影至 S（u，v），從而獲得 C 在 S上的投影曲線 C′，C′即為 S的裁剪曲線。具體做法是：（1）C的所有控制點P（ixi，yi，z）i向S投影，獲得對應投影點；（2）置換 C 的所有控制點為新的控制點

曲面的裁剪和保留是由邊界方向確定的，不失一般地，設定內、外邊界分別為順時針和逆時針方向，內外邊界之間地曲面為保留曲面，其它部分曲面則予以裁剪。無孔洞的曲面只有外邊界，無內邊界。由于邊界裁剪曲線C′的方向并未事先規(guī)定，因此應對其方向進行判定，對不符合方向規(guī)定的進行反向操作。

二維（u，v）點集的方向判斷可直接使用多邊形法，算法代碼可參考文獻[8]。該算法沿用三維點叉乘法，對二維點進行叉乘操作，統(tǒng)計叉乘結果符號，結果為正，則判定邊界方向為逆時針，否則為順時針。該算法適用于這里時，還需要注意以下兩個問題：（1）直線段邊界點集的叉乘結果趨于0，對方向判斷無貢獻。閉合邊界的方向性并不由直線邊界決定，因此，只需要對叉乘結果在0值誤差范圍內的共線點集予以過濾即可。（2）多邊形法在點集為凸包時有效，但是如果點集中大部分分段為凹包點，則會導致判斷錯誤。觀察到特征點構成的多邊形方向直接反映了邊界的凸包性，代表了邊界方向，因此以特征點集替換整體邊界點集，既可規(guī)避局部噪聲對凸包性的影響，又可最大程度上減少整體點集對邊界方向判斷的錯誤。如前述，對曲面進行外邊界裁剪時，如果曲線為順時針方向，則應對曲線進行反向。反向算法參考文獻[7]，該算法的核心是對節(jié)點和控制點進行反向。

5 實驗

在VC和OpenGL開發(fā)環(huán)境下開發(fā)實現了上述算法，其中NURBS曲線擬合、拼接、反向等算法均通過集成nurbs++開源算法庫實現。NURBS曲線擬合算法中控制點數太少，曲線擬合誤差大，控制點太多，在邊界點集不光滑的情況下，易致曲線出現鋸齒形狀，為了保證曲線擬合的效果，算法將控制點數設置為輸入點集數的1/3。模型實驗中，固定或交互設定算法參數，其中距離誤差ε=0.001，曲率突變比例r=0.1，即邊界點集中10%的節(jié)點為曲率突變點，方向夾角閾值T根據邊界點集特點設定。

以fandisk模型的頂面為例進行說明，如圖5所示。該面的擬合面為平面，點云分割和面擬合在文獻[9-10]中已有詳細論述，此處不再贅述。經分割后的部分點云特征面，如圖5（b）所示。提取的頂面點云邊界，如圖5（c）所示。點云邊界排序后可串聯為多邊形邊界，最短距離法進行邊界點排序，能過濾部分離群點，但還是因非離群噪聲點的存在而形成鋸齒形邊界，必須經過去噪處理后鋸齒現象才能得到很好的去除。圖5（d），圖5（e）中非邊界多邊形上的點為離群點，邊界多邊形的1、2、3處分別給出了放大圖，從中可以看到去噪前后的對比效果。圖5（f）矩形框中的節(jié)點是從曲率突變點中識別的邊界線特征點，該圖也表達了邊界分段的效果。圖 5（g）中，1、4、6 分段處為凹曲線，3、5 分段處為直線段，只有2處為凸曲線段，為了規(guī)避密集點集的凹凸不確定性，采用邊界特征點進行曲線方向的判斷，圖5（h）標號處為用于曲線方向判斷的主要邊界特征點。在獲得滿意的邊界特征線之后，即可對擬合面進行裁剪，圖5（i）顯示了fandisk頂面的裁剪結果。根據以上算法，完成了對fandisk模型的主要特征型面邊界的識別、分段擬合和曲面裁剪，如圖 5（j）～圖 5（l）所示。

圖5 算法實例Fig.5 Case Study of the Algorithm

文獻[5]給出的汽車頂蓋曲面擬合和裁剪實例，如圖6所示。該曲面只需要一個四邊域即可裁剪車頂曲面（中間的曲面）。文獻[4]也只是給出了簡單邊界圓形邊界的裁剪實例。相比之下，fandisk實例點云曲面多且復雜，曲面邊界凹凸不平，裁剪算法適應性更強。

圖6 文獻[5]中的實例Fig.6 Case Study in Literature[5]

6 結論

對邊界點集進行預處理和分段擬合，可獲得高質量的邊界曲線，從而獲得良好的曲面裁剪效果，論文通過算法和實例研究驗證了這一思路。針對機械零件的復雜邊界，應以特征識別為核心，重點識別邊界線上的特征點，才能很好地進行邊界線分段和擬合。擬合邊界線的方向性也是曲面裁剪的一個關鍵，以特征點集替代整體點集進行方向判斷的方法也取得了預想的結果。從圖5（i）所示的裁剪結果看，曲面邊界還是存在不光滑的現象，這是由于邊界線未做平滑處理。從原理上看，前述算法同樣適用于非平面曲面、多孔洞曲面等更復雜曲面的裁剪，這也是論文的下一步研究工作。