高 瑞，李瀧杲，黃 翔，李 棟

（1. 南京航空航天大學(xué)機電學(xué)院，南京 210016；2. 航空工業(yè)江西洪都航空工業(yè)集團有限責(zé)任公司，南昌 330024）

零件的加工及檢測是飛機、汽車等機械生產(chǎn)過程中的重要環(huán)節(jié)。零件的加工質(zhì)量將直接影響部件及產(chǎn)品的質(zhì)量與性能。而幾何特征是零件幾何模型的重要組成部分，對于幾何模型的外觀描述、模型重建及準確表達具有重要作用[1]。對于一些復(fù)雜曲面零件，采用樣板、模胎等人工比對的傳統(tǒng)檢測方式，其評價精度取決于技工經(jīng)驗，無法獲得精確的數(shù)字量描述，而且效率低。然而，隨著三維激光掃描技術(shù)的迅速發(fā)展，獲得高精度、高密度的點云數(shù)據(jù)已經(jīng)十分迅捷。因此，通過分析處理零件表面的點云數(shù)據(jù)，提取出零件的特征，可以實現(xiàn)零件加工質(zhì)量的定量描述及特征的逆向重構(gòu)。

點云特征點提取及特征線擬合的研究主要集中兩方面，一是基于網(wǎng)格模型的特征提取，二是基于散亂點云的特征提取。

網(wǎng)格模型的特征線提取方法可以分為自動提取與半自動提取。自動提取方法通常是尋找出網(wǎng)格上曲率的突變點作為特征點，然后將這些離散特征擬合成特征線。Yang等[2]通過擬合局部二次曲面計算主曲率與主方向，實現(xiàn)特征線提取，但該方法對噪聲點云或稀疏點云不適用。上官寧等[3]通過主成分分析的方法獲得主特征方向，沿特征點生長方向?qū)ふ液罄^特征點，實現(xiàn)特征線的提取。劉倩等[4]將點云數(shù)據(jù)進行高斯映射形成點集聚類，獲得曲率和法向量發(fā)生突變的點作為特征點。半自動提取是用戶交互選取特征線方向的多個點，鄰近點相連形成初始特征點，最后采用優(yōu)化方法優(yōu)化初始特征線。劉勝蘭等[5]采用追蹤投影法確定初始特征線，通過Sanke變形滿足主動輪廓能量最小實現(xiàn)特征線優(yōu)化，但是點云模型的網(wǎng)格重建耗時長，網(wǎng)格的成形質(zhì)量對特征線的提取影響較大。

相比較于網(wǎng)格模型的特征線提取，散亂點云沒有任何拓撲信息。目前，直接從散亂點云中提取特征的研究相對較少。Gumhold等[6]提出的方法是根據(jù)鄰域點的協(xié)方差矩陣的特征向量的特征值給每一點一個權(quán)重，將點區(qū)分為邊界點、折點、平面點和角點，利用點鄰域邊權(quán)值生成最小生成樹，剪除樹枝，最終得到平滑的曲線。Pauly等[7]在Gumhold的基礎(chǔ)上，采用了一種多尺度的點云特征提取算法，該算法在不同尺度上提取特征，這種方法更為抗噪穩(wěn)健。Weber等[8]提出了基于高斯映射的點云聚類的方法提取尖銳特征的方法，在其算法中，首先計算一點及其鄰域點所構(gòu)成的所有三角形，并計算出三角形的法矢，將法矢映射到高斯球上后通過高斯聚類的方法統(tǒng)計判斷是否為特征點，為了避免噪聲的影響，他們也提出了一種自適應(yīng)的閾值計算方法；然而，該算法受噪聲影響較大，一個點若因為噪聲的影響而形成錯誤的三角形，會導(dǎo)致錯誤的聚類，從而不能進行正確的判斷；同時，計算點云中每個點與其鄰域點的三角形，會產(chǎn)生很大的時間開銷。龐曉旭等[9]通過擬合局部的最小二乘曲面的多項式來計算每個點的主曲率，將主曲率絕對值較大的點標識為谷脊特征點，將特征點投影到潛在特征線上得到增強特征點，最后經(jīng)過平滑處理得到谷脊線，該方法計算相對復(fù)雜，但對稀疏點云模型具有較好的處理效果。王小超等[10]提出了基于局部重建的點云特征提取算法，首先通過協(xié)方差分析獲得初始特征點，在初始特征點的基礎(chǔ)上在局部區(qū)域進行三角形重建，通過法向聚類形成局部數(shù)據(jù)點的分類，將分類點進行平面擬合，并判斷是否落在多個平面上進行特征點的提取。張雨禾等[11]同樣采用基于局部重建的提取方法，不同的是最后依據(jù)Weingarten映射性質(zhì)來進行谷脊特征點提取。吾守爾·斯拉木等[12]提出了一種基于平均曲率運動的尖銳特征提取方法，但仍需要人工調(diào)節(jié)自由參數(shù)。

基于上述分析，本文提出了復(fù)雜曲面零件散亂點云特征點的提取方法，旨在將零件的幾何特征提取出來，一方面可以為后續(xù)零件的數(shù)字化檢測提供依據(jù)，另一方面可以作為曲面重建的約束條件。

算法分析及實現(xiàn)

首先，對點云建立基于KD樹的拓撲關(guān)系，實現(xiàn)快速檢索每一點的k近鄰點；然后，采用基于高斯權(quán)重的主成分分析法完成對點云模型的初始標記；最后，通過基于標記的自動識別法實現(xiàn)特征點的檢測，聚類處理完善特征，如圖1所示。

圖1 方法流程Fig.1 Flow of the proposed method

1 點云拓撲關(guān)系的建立

散亂點云分布無任何規(guī)律，且沒有任何拓撲連接信息，單點無法提供任何有效的特征信息。為了能夠從點云中提取特征點，點云中的每一個點必須從它的臨近點中收集信息。因此，需要檢索點云的k近鄰點。k近鄰的搜索方法通常有3種：空間柵格法、八叉樹法與KD樹法?？臻g柵格法，方法簡單但受點云采樣密度的影響較大；八叉樹法，將空間分為8個卦限，非葉子節(jié)點繼續(xù)分為8個卦限，在葉子節(jié)點中存儲信息，但占用的空間較大，存在冗余現(xiàn)象，不適合存儲數(shù)量較多的點云；而KD樹法相對簡單，它的最差復(fù)雜度是o(3N2/3)，平均復(fù)雜度是o(log/n )[13]。因此，利用KD樹可以加快近鄰點的搜索，可以改善算法的運行時間，提高效率。本文不詳述KD樹的建立過程。

2 基于高斯權(quán)重的主成分分析法

在傳統(tǒng)主成分分析的基礎(chǔ)上，本文提出基于高斯權(quán)重的主成分分析法。

散 亂 點 集 p={p1,p2,p3,…,pn}，pi∈R3，i=1,2,3,…,n，定義 Np為采樣點pi∈p的k近鄰點集，C為點pi的近鄰點的構(gòu)成的協(xié)方差矩陣：

（1）散亂點云中每一點與其近鄰點的距離并不相同，顯然離中心點較近的點對中心點的影響更大，應(yīng)占有更大的權(quán)重因子，而公式（1）中近鄰點對中心點的影響權(quán)重是一樣的。因此，采用高斯權(quán)重可以根據(jù)距離中心點的遠近賦予不同的權(quán)重因子。

（2）點云密度是影響特征點提取的關(guān)鍵因素之一，而高斯權(quán)重函數(shù)包含了點云密度這一影響參數(shù)。

3 點云特征提取

3.1 點云初始標記

圖2 不同區(qū)域位置的點的特征指標Fig.2 Feature index of points in different regions

由圖2可以看出：位于平面處的紅色點來說，隨著k值的變化，特征指標變化不大，全部近似為零；位于棱邊處的藍色點，其特征指標比較大，且隨著k值的增加相對穩(wěn)定，特征指標全部大于0.1；而對于靠近特征點的一些點（圖2中綠色點）來說，由于當(dāng)近鄰點增加時可能會包含棱邊處的特征點，所以隨著k值的增加，特征指標存在突變。因此，對于鄰近棱邊處的點pi來說，當(dāng)與的差值較大時，將終止迭代，并將ωkpi作為點pi的最佳特征指標，在算法中將作為迭代終止條件。為避免陷入無限循環(huán)，需要限制迭代的次數(shù)，如果迭代10次仍然沒有滿足終止條件，算法就自動停止迭代，并以最后一次的特征指標作為最佳指標。

雖然ωp反映了一個點是否為特征點的可能性，但在試驗中發(fā)現(xiàn)很難確定一個合適的閾值來得到完整的特征點集。本文通過選取兩個較為寬松的閾值，對點云進行初始的標記，盡可能地保留潛在特征點，在后續(xù)的特征點完善中精確提取。假設(shè)兩個閾值 ω_＜ ω+，對于任一點 pi的特征指標 ωpi，如果 ωpi≤ ω_，則認為該點不是特征點并標記為0；如果ωpi≥ω_，則認為該點是特征點并標記為 2；如果 ω_＜ ωpi＜ ω+，則認為該點為潛在特征點并標記為1，最后進一步識別與完善。

3.2 特征點識別與完善

點云數(shù)據(jù)在全局閾值ω_與ω+的條件判斷下，初始區(qū)分為特征點集、非特征點集與潛在特征點集。潛在的特征點采用基于標記的自動識別法實現(xiàn)特征點的提取。對于潛在特征點集中的任一點Pi來說，依次考慮以下4種情況。

（1）若該點的近鄰點的標記全部為2，即全為特征點，則認為該點是特征點，將標記置為2。

（2）若該點的近鄰點的標記全部為0，即全為非特征點，則認為該點是非特征點，將標記置為0。

（3）若該點的近鄰點的標記為0或1，即潛在特征點與非特征點，則進行以下判斷：

如果 ωpi≥ max{ωp1,ωp2…ωpk}，即該點的特征權(quán)重是其所有近鄰點的特征權(quán)重的最大值，則認為該點是特征點，將標記置為2。

（4）若該點的近鄰點的標記中既有特征點（標記為2）且至少含有兩個特征點，又有其他類型的點(非特征點或者潛在特征點)。為了判別該點是否是特征點，本文提出一種基于歐式距離的識別方法，具體步驟如下：

步驟1，計算潛在點p近鄰點中任意兩個特征點之間的歐式距離，。

步驟2，計算潛在點p與近鄰特征點之間的歐式距離，且Tm=2。

步驟 3，如果 min{dpm}＜min{dij}，則認為潛在點p為特征點，將標記置為2。

對潛在特征點集中的每一個點進行上述處理后，獲得初步的特征點集。然而，當(dāng)點云模型表面的曲率較大時，因受曲率的影響，曲面上的一些點的特征權(quán)重較大而被誤判為特征點，如圖3所示，因此需要將這些點去除掉來完善特征的提取。試驗發(fā)現(xiàn)，這些異常點在提取的特征模型中相對比較孤立，且特征點之間的距離一般小于初始點云的平均點間距；基于上述特點進行聚類處理，其步驟如下：

步驟1，將特征點集F中的所有點初始標記為未分類，記作flag=False;

步驟2，取特征點集中的任意一點fi,且flag(fi)=False。在特征點集中尋找fi的最近鄰點fi.min，計算di=║fifi.min║。若，則將兩點fi, fi.min歸為一類Ci；否則，劃分為兩個類。上述分類后，flag=True。

步驟3，再從特征點集中再取一未被標記的點fj，flag(fj)=false。在特征點集中尋找fj的最近鄰點fj.min，計算 dj=║fj-fj.min║，有以下 3 種情況 ：

（1）若，且 fi.min∈ C'（C'為已存在的類）,則點fj劃歸到類C'中。

（2）若,且flag(fi.min)=False,則將兩點fj, fj.min劃歸為一類Cj。

（3）若，則將兩點fj, fj.min分為兩個類。

上述分類后，flag=True。

步驟4，重復(fù)步驟3，直到特征點集中的每一點的flag全部為True。

通過上述的聚類處理，特征點集已經(jīng)被劃分為幾個類，若類中點的數(shù)量小于10個點，則刪除這個類及類中的點，剩余的點集即為最終的提取結(jié)果。圖3顯示了聚類處理過程。

圖3 特征點聚類處理Fig.3 Feature points clustering

試驗結(jié)果與討論

先對本文方法的參數(shù)選擇進行說明，然后在不同的點云模型進行試驗驗證。與傳統(tǒng)的PCA方法、Web[8]方法進行比較，本文方法更加簡單有效。試驗在Visual Studio 2010編程環(huán)境下進行，硬件環(huán)境為奔騰處理器，雙核，工作頻率為3.06GHZ，內(nèi)存為4G，PC機。

1 參數(shù)選擇策略

通過上述分析，本文中的參數(shù)主要是兩個初始閾值ω_,ω+及初始的近鄰點數(shù)k；對于初始的近鄰點數(shù)一般取8～15個點，如果近鄰點數(shù)取得過小，擬合后幾乎全是微小平面，求得特征指標近似為零，不能有效地提取特征點；當(dāng)近鄰點數(shù)取得過大時，由高斯函數(shù)的意義可知，對于離中心點很遠的點來說，高斯權(quán)重幾乎為零，對結(jié)果不會產(chǎn)生太大的影響，卻增加了算法的計算代價。因此，本文主要討論初始閾值對提取效果的影響及其選擇策略。

對于閾值下限ω_，主要是保證去除平面點，可以將數(shù)值選取的稍微小一些，這樣既可以保證去除的點完全屬于平面點，又不會去除潛在的特征點，通過試驗發(fā)現(xiàn)ω_在0.005～0.010之間取值時較為適宜；對于閾值上限ω+，則取值應(yīng)該稍微大一些，保證特征指標大于該值的點全部為特征點。試驗中ω+分別取0.01、0.05、0.10、0.15、0.20、0.25、0.30，ω_取 0.005，并統(tǒng)計各自提取的特征點的數(shù)量，如表1所示，特征點的提取效果如圖4所示。分析特征點的提取結(jié)果可知，當(dāng)特征指標取得較小時，如ω+ = 0.01，ω+ = 0.05，提取的特征點數(shù)量比較多，保留了大部分的特征點，卻也包含了許多非特征點，容易使特征變模糊；當(dāng)特征指標取較大值時，如0.10、0.15等，特征點數(shù)量減少的同時較好地保留了點云模型特征，便于后續(xù)的點云處理；當(dāng)進一步增大初始閾值，由圖5可以看出特征點的數(shù)量幾乎不再變化。因此，可以根據(jù)實際情況進行初始閾值的選擇，當(dāng)提取的特征要求不是特別精細時，可以適當(dāng)減小初始閾值。本文建議初始閾值上限在0.10～0.30之間進行選擇。

圖4 不同閾值下的特征點提取效果Fig.4 Feature point extraction under different thresholds

表1 不同閾值下特征點數(shù)量統(tǒng)計

2 試驗結(jié)果分析

以扇盤（Fandisk）模型為例，該模型不僅有比較顯著的曲線、直線特征，還包含相對弱的特征（扇形區(qū)域的曲線特征），因此對該模型的提取結(jié)果能夠有效反映算法的處理效果。在參數(shù)選擇上，本文選取ω_= 0.003，ω+ = 0.10，初始的近鄰點k = 8；PCA方法分別設(shè)置閾值ωp= 0.01、0.05、0.10。試驗結(jié)果如圖6所示。當(dāng)閾值取得較小時，如圖6（d）所示，雖然點云的處理結(jié)果保留了大部分的特征點，但可以看到特征點附近的很多點被誤判為特征點，致使特征變得模糊；當(dāng)閾值較大時，如圖6（e）、6（f）所示，雖然特征更加清晰，在一定程度上緩解了閾值較小時所帶來的問題，但有一部分特征點沒有識別出來，致使特征不夠完整。采用本文的方法，如圖6（b）所示，處理結(jié)果一次提取就較為完整地識別出了全部的特征點，而且有效地去除了一些對特征點識別貢獻不大的點，使提取的特征更加清晰；同時該方法在處理過程中不需要過多人為修改參數(shù)。本文也與Web方法[8]進行了比較，采用Web方法中的局部自適應(yīng)閾值識別法，設(shè)置初始閾值參數(shù)，近鄰點數(shù)k = 8,敏感性參數(shù)σ = 0.1，提取結(jié)果如圖6（c）所示，由于Web方法在構(gòu)造初始三角形集合時存在三角形大量跨越特征區(qū)域的問題，故而會導(dǎo)致弱特征丟失的現(xiàn)象。

本文方法又在復(fù)雜曲面零件錐形齒輪與整體葉盤的點云模型上進行了試驗驗證，特征點提取結(jié)果良好。

圖7（a）是錐形齒輪的原始點云模型，模型共有46300個點。圖7（b）顯示了本文方法提取的特征點，共有2606個點。軸心的圓形特征點提取效果明顯，輪齒處的特征點略顯粗糙，但基本完整。

圖8（a）是整體葉盤的原始點云模型，模型共有290762個點。圖8（b）顯示了利用本文方法提取的特征點，共有6932個點，可以看到葉片曲面處的復(fù)雜曲線特征點得到了完整的提取。圖8（c）顯示了特征點集與CAD數(shù)模的粗配準，特征點的提取位置基本準確。

圖5 不同閾值下特征點數(shù)量變化Fig.5 Variation of feature point number under different thresholds

圖6 Fandisk點云模型特征點提取Fig.6 Feature point extraction of Flandisk model

圖7 錐形齒輪點云模型特征點提取Fig.7 Feature point extraction of bevel gear model

圖8 整體葉盤點云模型特征點提取Fig.8 Feature point extraction ofblisk model

結(jié)論

本文提出了一種復(fù)雜曲面零件散亂點云特征點提取的方法。首先，通過本文提出的基于高斯權(quán)重的主成分分析法估計局部曲面的變化程度，對點云模型進行特征點的初始標記；然后，基于標記的自動識別法進行特征點的檢測提??；最后，通過特征點聚類處理的方式完善了提取的特征點。試驗結(jié)果表明，本文方法直接操作于散亂點云，無需進行點云的三角網(wǎng)格重建，處理過程簡單有效且無需過多的參數(shù)調(diào)整，特征點提取較為完整，對于復(fù)雜曲面零件的數(shù)字化檢測及逆向重建具有重要意義。然而，必須指出的是，當(dāng)點云模型的采樣質(zhì)量較差，點云分布十分不均，采樣點過于稀疏時，本文方法的處理結(jié)果并不理想，因此這將是下一步的研究重點。同時，基于特征點實現(xiàn)特征曲線的擬合也是希望實現(xiàn)的目標。

參考文獻

[1]胡事民,楊永亮，來煜坤.數(shù)字幾何處理研究進展[J]．計算機學(xué)報，2009, 32(8)：1-18．

HU Shimin, YANG Yongliang, LAI Yukun. Research progress of digital geometry processing[J]. Chinese Journal of Computers，2009，32(8)：l-18.

[2]YANG M, LEE E. Segmentation of measured point data using a parametric quadric surface approximation[J]. Computer-Aided Design, 1999, 31(7)：449-457.

[3]上官寧, 劉斌. 三角網(wǎng)格模型特征線提取方法[J]. 華僑大學(xué)學(xué)報(自然科學(xué)版),2010, 31(5)：487-490.

SHANGGUAN Ning, LIU Bin. Investigation of feature line extration triangular mesh model[J].Journal of Huaqiao University(Natural Science),2010, 31(5)：487-490.

[4] 劉倩, 耿國華, 周明全, 等. 基于三維點云模型的特征線提取算法[J]. 計算機應(yīng)用研究 , 2013, 30(3)：933-937.

LIU Qian, GENG Guohua, ZHOU Mingquan,et al. Algorithm for feature line extration based 3D point cloud models[J]. Application Research of Computers, 2013, 30(3)：933-937.

[5]劉勝蘭, 周儒榮, 張麗艷. 用主動輪廓模型優(yōu)化網(wǎng)格曲面上的特征線[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2004,16(4)：439-443.

LIU Shenglan, ZHOU Rurong, ZHANG Liyan. Feature line optimization on triangular sufaces using active contour model[J]. Journal of Computer-Aided Design and Computer Graphics,2004, 16(4)：439-443.

[6]GUMHOLD S, WANG X, MACLEOD R. Feature extraction from point clouds[C]//Proceedings of the 10th Internation Meshing Roundtable, Newport Beach, 2001.

[7]PAULY M, KEISER R, GROSS M. Multiscale feature extraction on point-sampled surfaces[J].Computer Graphics Forum, 2003, 22(3)：281-289.

[8]WEBER C, HAHMANN S, HAGEN H. Sharp feature detection in point clouds[C]//Shape Modeling International Conference, IEEE Computer Society, 2010：175-186.

[9]龐旭芳, 龐明勇, 肖春霞. 點云模型谷脊特征的提取與增強算法[J]. 自動化學(xué)報,2010, 36(8)：1073-1083.

PANG Xufang, PANG Mingyong, XIAO Chunxia. An algorithm for extraction and enhancing valley-ridge feature from point sets[J].Acta Automatica Sinica, 2010, 36(8)：1073-1083.

[10]王小超, 劉秀平, 李寶軍,等. 基于局部重建的點云特征點提取[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2013, 25(5)：659-665.

WANG Xiaochao, LIU Xiuping, LI Baojun,et al. Feature detection on point cloud via local reconstruction [J]. Journal of Computer-Aided Design and Computer Graphics, 2013, 25(5)：659-665.

[11]張雨禾, 耿國華, 魏瀟然. 散亂點云谷脊特征提取[J]. 光學(xué)精密工程, 2015,23(1)：310-318.

ZHANG Yuhe, GENG Guohua, WEI Xiaoran. Valley-ridge feature extraction from point clouds[J]. Optics and Precision Enginering,2015, 23(1)：310-318.

[12]吾守爾·斯拉木, 曹巨明. 一種新的散亂點云尖銳特征提取方法[J]. 西安交通大學(xué)學(xué)報 , 2012, 46(12)：1-5.

WUSHOUR Slam, CAO Juming. An extraction algorithm for sharp feature from point clouds[J]. Journal of Xi’an Jiaotong University,2012, 46(12)：1-5.

[13]LEE D T, WONG C K. Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees[J]. Acta Informatica, 1977, 9(1)：23-29.

[14]PAULY M, GROSS M, KOBBELT L P. Efficient simplification of point-sampled surfaces[C]// Visualization conference,IEEE(2002), Boston, 2002.