梁 標(biāo)，李瀧杲，黃 翔，李 根，彭 云

（1.南京航空航天大學(xué)機電學(xué)院，南京 210016；2.南京航空航天大學(xué)蘇州研究院，蘇州 215000）

飛機設(shè)計性能的不斷提升對飛機制造提出了更高的裝配要求，出現(xiàn)了基于實測模型的預(yù)裝配分析技術(shù)[1–2]，該技術(shù)以實際測量點云數(shù)據(jù)重構(gòu)的CAD模型代替理論模型進行虛擬裝配分析。模型重構(gòu)的前提是需要將實測點云劃分為只含有單一幾何特征的拓撲結(jié)構(gòu)區(qū)域。但飛機裝配零部件數(shù)量多、結(jié)構(gòu)復(fù)雜[3]，對大規(guī)模點云數(shù)據(jù)按照設(shè)計意圖開發(fā)智能自動分割算法難度很大，因此如何精確且高效地實現(xiàn)點云分割成為飛機預(yù)裝配分析研究中亟待解決的問題之一。

國內(nèi)外對點云分割技術(shù)進行了許多研究。董明曉等[4]提出了一種基于數(shù)據(jù)點曲率變化的區(qū)域分割方法，即先對每一條掃描線上的數(shù)據(jù)點求取曲率值，然后將其中曲率值變化較大的點提取出來作為邊界點，將封閉邊界包圍的區(qū)域作為分割的結(jié)果，但該方法曲率閾值選取比較困難且只能適用于掃描線格式的點云數(shù)據(jù)。Besl等[5]最早提出了基于面的區(qū)域生長分割方法，該方法從具有特征的某一或多個數(shù)據(jù)點開始，圍繞具有相似幾何性質(zhì)的相鄰點生長，重復(fù)向外搜索直到分割出所有滿足該特征類型和生長參數(shù)的點。但需要人工交互選取種子點、確定生長初始參數(shù)以及區(qū)域生長允許誤差。k–means聚類分割算法[6]以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結(jié)果。但需要預(yù)先估計并給定聚類數(shù)量，對初始聚類中心點的選取也較為敏感。趙夫群等[7]提出了基于改進隨機抽樣一致性 （Random sample consensus，RANSAC）的點云分割算法，通過改進初始點數(shù)據(jù)的選取方式和判斷準則使RANSAC算法對點云數(shù)據(jù)分割的準確度提高，但僅能從點云數(shù)據(jù)集中分割出平面數(shù)學(xué)模型，不適用于含有多種幾何特征的復(fù)雜點云數(shù)據(jù)分割。并且針對不同密度信息的點云數(shù)據(jù)，判斷閾值δ需要人工計算后設(shè)置。Hao等[8]提出了基于CAD模型驅(qū)動先驗?zāi)０宓那嬷貥?gòu)方法，即給定一個CAD模型，提取其中的幾何元素，以幾何元素為基本單位進行網(wǎng)格劃分，構(gòu)建基于CAD模型的先驗?zāi)０?。并提取網(wǎng)格節(jié)點處的法向量，對引導(dǎo)點法線附近的原始掃描點云數(shù)據(jù)進行搜索，得到的搜索點的高斯加權(quán)平均值代表零件在引導(dǎo)點處的實際幾何參數(shù)。

基于以上分析，本文結(jié)合用于虛擬預(yù)裝配分析的飛機零部件具有理論數(shù)模的特點，以具有理論數(shù)模的零部件實測點云數(shù)據(jù)為研究對象，提出了一種基于特征模板的點云數(shù)據(jù)精確分割技術(shù)方法。該方法通過提取理論曲面并構(gòu)建特征模板實現(xiàn)由特征模板含有的原始信息驅(qū)動規(guī)模點云數(shù)據(jù)精確分割出屬于目標(biāo)曲面特征的點云數(shù)據(jù)，技術(shù)路線如圖1所示。本文提出的方法已在CATIA的二次開發(fā)平臺CAA（Component application architecture）上開發(fā)了相關(guān)程序，并通過后段肋實例驗證了方法的有效性和精確性。

圖1 基于特征模板的點云精確分割技術(shù)路線Fig.1 Technical route of precise point cloud segmentation based on feature template

1 理論曲面特征模板構(gòu)建

當(dāng)前飛機零件的曲面特征多采用自由造型設(shè)計，其數(shù)學(xué)表達式的求解不僅煩瑣且效率低，難以將其直接存儲在數(shù)據(jù)庫中[9]，因此通過對理論模型待識別曲面特征構(gòu)建特征模板，將其解構(gòu)為數(shù)據(jù)庫可存儲模式。特征模板構(gòu)建過程如圖2所示，首先對理論曲面特征進行提取命名并放入特征提取集中，對特征提取集中的所有理論曲面特征逐一離散獲得離散點集，將離散點作為頂點三角網(wǎng)格化并計算每個三角面片的法向量。最終由曲面離散點集合Pi、三角網(wǎng)格集合Mi、三角面片法向量集合nF共同組成特征模板并存儲至特征模板數(shù)據(jù)庫中。

圖2 理論曲面特征模板構(gòu)建過程Fig.2 Theoretical surface feature template construction process

特征模板的構(gòu)建過程簡單方便且靈活，編號相同的零件能夠共用同一組特征模板，減少了特征模板重復(fù)構(gòu)建的工作量，降低了數(shù)據(jù)庫的內(nèi)存使用率。

1.1 曲面特征離散

曲面特征離散過程如圖3所示，先按照設(shè)定的離散間距參數(shù)采用截交線法[10]將理論曲面特征依次離散為一組截交線，得到的截交線有序集合為L（S） = {Li，i=1，2，…，nL}，對截交線Li通過等弧長法[11]離散，保證相鄰離散點之間的弧長相等，并且計算過程簡單、效率高。通過CATIA軟件開放的二次開發(fā)接口函數(shù)CATCrvParam獲取理論截交線的參數(shù)方程，得到的參數(shù)表達式為

圖3 曲面特征離散Fig.3 Surface feature discretization

則曲線弧長的計算方程為

給定初始弧長l0，完成單條截交線L的數(shù)字化離散，得到有序離散點集合為

整個理論曲面特征離散點集合為所有截交線有序特征離散點的并集，即

式中，i為曲面特征離散截交線的條數(shù)；j為第i條截交線上的離散點個數(shù)；nP為截交線上總離散點數(shù)；nL為曲面上總離散截交線條數(shù)。

1.2 三角面片法向量計算

采用三角化算法將曲面特征有序離散點作為三角形頂點連接成三角網(wǎng)格。三角網(wǎng)格是計算機圖形學(xué)中用于描述不規(guī)則實體建立三維數(shù)字化模型的一種數(shù)據(jù)結(jié)構(gòu)，可以表示為頂點、邊、面的集合M= [V，E，F(xiàn)]，其中V為網(wǎng)格頂點的集合，E為網(wǎng)格邊的集合，F(xiàn)為網(wǎng)格面的集合。

式中，nV為三角網(wǎng)絡(luò)頂點個數(shù)；nE為三角網(wǎng)格邊的個數(shù)；nF為三角網(wǎng)格面的個數(shù)。

為了給后續(xù)點云分割提供精確的初始參數(shù)以及生長依據(jù)，需要提取三角網(wǎng)格模型的面片法向量。三角面片法向量有兩個方向，為了避免出現(xiàn)歧義，需要保證三角面片法向量方向的唯一性，如圖4所示。

圖4 三角面片法向量定義Fig.4 Triangular face normal vector definition

設(shè)兩個三角面片分別為f1（P21，P22，P11）和f2（P12，P11，P22），以三角面片f1為例，非公共邊的頂點P21作為起始點，同一條截交線的另一個頂點P22作為終點，構(gòu)建向量根據(jù)右手定則和幾何中向量積的定義，由三角形邊的向量積求出三角面片f1法向量并單位化。

理論曲面特征的三角面片法向量集合為

2 特征模板驅(qū)動的點云數(shù)據(jù)粗分割

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

點云數(shù)據(jù)通常具有大規(guī)模和無序的特點，所以建立點云間的拓撲關(guān)系對點云數(shù)據(jù)分割至關(guān)重要。根據(jù)本研究使用的特征模板，為實現(xiàn)特征模板驅(qū)動的點云數(shù)據(jù)粗分割目標(biāo)，采用空間柵格法[12]建立點云拓撲關(guān)系?？臻g柵格法是利用空間立體柵格來近似表示點云的空間結(jié)構(gòu)和幾何形狀，基本原理如圖5所示：設(shè)xmax、ymax、zmax、xmin、ymin、zmin為點云中x、y、z的最大、最小坐標(biāo)，給定柵格擴展閾值ε，以點（xmax+ε，ymax+ε，zmax+ε）和點（xmin–ε，ymin–ε，zmin–ε）為對角點且表面平行于空間坐標(biāo)系的空間六面體構(gòu)建點云的空間包圍盒，將空間包圍盒作為柵格劃分的總空間，以預(yù)設(shè)寬度λ作為單位長度并對包圍盒進行均等劃分，其中柵格劃分寬度λ的取值根據(jù)數(shù)字化掃描設(shè)備設(shè)置的點分辨率確定，柵格擴展閾值ε可設(shè)置為λ的0.5倍。沿x、y、z方向的柵格數(shù)量分別為

圖5 空間柵格劃分原理Fig.5 Principle of spatial grid division

符號[]表示向上取整。三維立體柵格劃分完成后，每個柵格是一個微小正方體；用柵格坐標(biāo) （u，v，h）表示所有柵格，u、v、h分別代表在x、y、z方向的柵格序號，則有u∈[0，l– 1]，v∈[0，m– 1]，h∈[0，n– 1]。然后將點云數(shù)據(jù)點按坐標(biāo)值放入對應(yīng)柵格內(nèi)，有點的柵格稱為實格，無點的柵格稱為空格；柵格之間的鄰域關(guān)系間接代表了點云的拓撲關(guān)系。

2.2 實格質(zhì)心點粗分割

為提高點云數(shù)據(jù)處理效率，并充分利用特征模板的理論信息，將三維點云數(shù)據(jù)與理論數(shù)模對齊后，由特征模板驅(qū)動包含有多種特征的原始點云完成粗分割，剔除不屬于特征模板的點云數(shù)據(jù)。具體算法步驟如下：

（1）通過空間柵格法建立全部點云拓撲關(guān)系；

（2）按照特征模板中三角面片頂點集合計算并構(gòu)建曲面特征空間包圍盒{Bi（S），i=1，2，…，n}，S為提取的曲面特征，n為特征模板的數(shù)量；

（3）建立空的點云數(shù)據(jù)粗分割塊{Ci，i=1，2，…，n}，其中Ci用于存放柵格坐標(biāo)；

（4）檢索空間柵格Gk（u，v，h），若Gk是實格，則以質(zhì)心點代表柵格實格內(nèi)所有點，其質(zhì)心點坐標(biāo)為，y，z）；

（5）遍歷所有曲面特征空間包圍盒，若柵格的質(zhì)心點Gk（u，v，h）能成功投影到某一三角面片fi上且投影距離小于εd，則認為質(zhì)心點（u，v，h）在曲面特征空間包圍盒Bi（S）內(nèi)部，即（x，y，z）∈Bi（S），并把柵格坐標(biāo)Gk（u，v，h）存入對應(yīng)的分割塊Ci中；

（6）重復(fù)步驟（4）和（5），直到空間柵格全部遍歷完畢，完成點云數(shù)據(jù)實格質(zhì)心點粗分割。

曲面特征的空間包圍盒具體構(gòu)建方法如下。

設(shè)特征模板三角網(wǎng)格M={V，E，F(xiàn)}中的任一三角面片fi=（Vi1，Vi2，Vi3），Vi1、Vi2、Vi3分別為三角面片fi的3個頂點。將（Vi1，Vi2，Vi3）分別沿nF（fi）和–nF（fi）方向移動εd構(gòu)成正偏距三角面片fi′=（Vi1′，Vi2′，Vi3′）和負偏距三角面片fi″=（Vi1″，Vi2″，Vi3″），其中nF（fi）為三角面片fi的法向量，εd為包圍盒容忍閾值。以fi′和fi″為上底面和下底面，Vi1′Vi1″、Vi2′Vi2″、Vi3′Vi3″為3條棱構(gòu)成的封閉三棱柱作為單個三角面片fi的空間包圍盒B（fi），即

曲面特征的空間包圍盒B（S）為特征模板中所有三角面片包圍盒的并集組成，即

式中，n為三角面片的個數(shù)。

圖6 空間包圍盒建立與質(zhì)心點粗分割Fig.6 Spatial bounding box establishment and coarse division of centroid points

3 基于面的自適應(yīng)區(qū)域生長細分割

對獲得的粗分割點云塊進一步進行細分割，由特征模板數(shù)據(jù)庫離散點集合確定理想種子點，理想種子點的理論法向量作為生長分割初始參數(shù)向外擴展，搜索種子點的k近鄰點，采用主成分分析方法對點云中每一點法向量進行估計，并基于鄰域方向一致性傳播的調(diào)整方法來統(tǒng)一所有點云法向估計的方向，若滿足過渡夾角閾值條件的點作為生長點繼續(xù)生長，若生長到點云邊界則停止生長。

3.1 種子點選取

讀取存儲在數(shù)據(jù)庫的特征模板對應(yīng)的離散點集信息，選擇Pi=P[nL/2][np/2]作為細分割理想種子點Pseed。其中nL為曲面上總離散截交線條數(shù)；np為截交線上總離散點數(shù)；[]表示向下取整。Pseed為有序離散點集的中間點，保障了其所屬點云區(qū)域的準確性，確保種子點從曲面特征中心由內(nèi)向外開始生長。

同時根據(jù)特征模板數(shù)據(jù)庫索引關(guān)系檢索理想種子點Pseed作為共享頂點的所有三角面片的編號，所有三角面片法向量的矢量和單位化后作為Pseed的法向量nseed（圖7），賦予Pseed精確的初始生長分割參數(shù)，能夠有效利用理論曲面特征信息引導(dǎo)點云精確分割。

圖7 理想種子點法向量定義Fig.7 Definition of ideal seed point normal vector

3.2 點云法向量估計

為了給后續(xù)點云數(shù)據(jù)細分割提供生長依據(jù)，需要對點云法向量進行估計。本研究采用基于局部表面擬合的方法[13]對大規(guī)模散亂點云的法向量進行初始估計。

對于點云{Vi，i=1，2，…，n}中的某一點xi∈{Vi}，通過空間柵格法建立的拓撲關(guān)系搜索點云中距離點xi最近的k個點，即點xi的k鄰域，記作kNb（xi），對kNb（xi）最小二乘擬合局部切平面P，P的法向量記作n，點xi到坐標(biāo)系原點的歐式距離記作di，則局部切平面P可以表示為

采用主成分分析方法 （Principal component analysis，PCA）[14]求解切平面法向。對式（13）的求解問題就可以轉(zhuǎn)化為對式（14）中的半正定協(xié)方差矩陣M的特征值求解問題。

式中，為kNb（xi）的質(zhì)心點，將M分解為奇異值，得到的最小主成分系數(shù)作為P的法向量n，使得

式中，U為左奇異矩陣，由正交向量組成；Σ對角線的元素為奇異值；V為右奇異矩陣，由正交向量組成。V的列向量是變換后的新的主成分向量，即兩個相切向量和一個垂直于曲面的向量。

通過主成分分析法計算得到的點云法向量有可能指向點云模型外部或者內(nèi)部，為了避免產(chǎn)生歧義，需要對點云法向量的方向進行一致性調(diào)整。本文采用基于鄰域方向一致性傳播的調(diào)整方法：首先以點云中種子點Pseed的法向量nseed為基準，點Pseed的k鄰域為kNb（pseed）={pi，j=1，…，k}，點Pseed的相鄰點pi的單位法向量為ni，兩點之間的法向量的夾角為θ= arccos（nseed·ni），0≤θ≤π，θ越小表示兩點的法向量方向一致程度越高。設(shè)置法向量夾角閾值θmax，若θ∈[0，θmax]，表示兩點法向量方向是一致的，則ni保持不變；若θ∈[π –θmax，則把ni反向，得到調(diào)整后的法向量ni；若θ∈（θmax，π –θmax），表示兩點法向量方向沒有關(guān)聯(lián)。種子點Pseed的k鄰域法向量方向全部調(diào)整完畢后，再以pi調(diào)整后的法向量為基準對pi的k鄰域kNb（pi）中未調(diào)整法向量方向的點進行調(diào)整，不停傳播下去直到所有點云數(shù)據(jù)的法向量方向調(diào)整完畢。具體原理如圖8所示。

圖8 點云法向量一致性調(diào)整Fig.8 Point cloud normal vector consistency adjustment

圖9為采用主成分分析法對Fandisk點云模型進行法向量估計的結(jié)果，從局部放大圖可以看出，點云在光滑區(qū)域、邊界處和拐角處的法向量估計結(jié)果均接近理論狀態(tài)，且經(jīng)過法向一致性調(diào)整能實現(xiàn)點云法向量均指向Fandisk點云模型外側(cè)。

圖9 Fandisk點云模型法向量估計結(jié)果Fig.9 Fandisk point cloud model normal vector estimation results

3.3 自適應(yīng)區(qū)域生長

為了得到精確的點云生長分割結(jié)果，避免區(qū)域生長分割過程中人工確定初始種子點和反復(fù)嘗試分割參數(shù)，同時結(jié)合曲面特征內(nèi)部局部點云法向量變化相對平滑和邊界處點云法向量突變明顯的特點，本文提出了基于面的自適應(yīng)區(qū)域生長方法實現(xiàn)點云的細分割，即通過柵格實格質(zhì)心點粗分割過程實現(xiàn)與其所屬三角面片及法向量建立索引關(guān)系，便于后續(xù)實格質(zhì)心點歸屬關(guān)系查詢。從選定的理想種子點Pseed開始，若相鄰兩點的法向量夾角小于各自歸屬的三角網(wǎng)格面片間的法向量夾角，則作為新的種子點繼續(xù)生長；伴隨著生長點不斷向外搜索擴張，允許生長的過渡夾角閾值參數(shù)也隨著曲面三角面片的幾何性質(zhì)和類型不斷自適應(yīng)調(diào)整，無需通過已生長點逼近不同類型曲面識別特征屬性；若生長點的法向量與所屬的三角面片法向量夾角大于投影夾角閾值則認為區(qū)域生長到達了邊界處，如圖10所示，曲面S點云內(nèi)部的相鄰兩點P1和P2過渡夾角較小，但邊界點P3的投影夾角較大。

圖10 曲面特征點云過渡夾角和投影夾角分布Fig.10 Distribution of transition angle and projection angle of feature point cloud on curved surface

基于面的自適應(yīng)區(qū)域生長點云細分割曲面特征細分割具體步驟如下。

定義種子點容器Seed和細分割點云塊集合C細。

（1）原始點云經(jīng)過粗分割得到的粗點云塊C粗和選取細分割理想種子點Pseed，在C粗中找到距離Pseed最近點作為初始種子點p1并加入種子點容器Seed中。

（2）從Seed中的種子點p1開始，通過空間柵格法建立的點云拓撲關(guān)系查找點p1的k近鄰點pk，并遍歷所有k近鄰點pk。

（3）計算pk內(nèi)的點與點p1的法向量偏差en，其中過渡夾角en= arccos（np1·npk），np1和npk分別為點p1和pk估計的單位法向量。

（4）計算pk內(nèi)的點法向量與其歸屬的三角面片的法向量nF（fi） 偏差ep，其中投影夾角ep= arccos（npk·nppk），npk和nppk分別為點pk的單位法向量和其歸屬三角面片法向量。

（5）若pk C細且同時滿足en<ε（en）和ep<ε（ep），則把pk同時放入C細和Seed的末位；若pk C細但只滿足en<ε（en），則只將pk放入C細的末位。ε（en）和ε（ep）分別為過渡夾角閾值和投影夾角閾值。

（6）遍歷完種子點p1的所有k鄰域點pk后，從Seed中刪除p1。

（7）重復(fù)執(zhí)行步驟（2）～（6），直到Seed內(nèi)無種子點，點云細分割完畢。

4 軟件系統(tǒng)開發(fā)與實例驗證

在航空工業(yè)中，國內(nèi)大多數(shù)企業(yè)采用CATIA三維數(shù)字化軟件，因此本文在CATIA二次開發(fā)平臺CAA中開發(fā)了基于特征模板的點云數(shù)據(jù)精確分割軟件并實現(xiàn)了預(yù)期功能，軟件界面如圖11所示，共包含曲面特征提取模塊、特征模板構(gòu)建存儲模塊和點云精確分割模塊3個模塊。

圖11 基于特征模板的點云精確分割軟件界面Fig.11 Software interface for precise point cloud segmentation based on feature template

試驗測試中，使用激光跟蹤儀+T–Probe測量后段肋零件工裝定位面上不共線的3個點建立測量坐標(biāo)系OM，激光跟蹤儀+T–Scan掃描后段肋零件表面獲取的點云數(shù)據(jù)位于測量坐標(biāo)系OM下，將實測點云數(shù)據(jù)xi轉(zhuǎn)換到理論CAD模型所在零件坐標(biāo)系OP下以實現(xiàn)與理論CAD模型的對齊。

式中，xi'為轉(zhuǎn)換后的點云數(shù)據(jù)；R和T分別為測量坐標(biāo)系OM變換到零件坐標(biāo)系OP的旋轉(zhuǎn)矩陣和平移向量。

圖12給出了應(yīng)用本研究點云數(shù)據(jù)精確分割軟件對某飛機后段肋實測點云的精確分割實例。后段肋零件理論三維模型如圖12（a）所示；圖12（b）對后段肋所有待識別曲面特征進行提取命名并加入到特征提取集內(nèi)；圖12（c）將特征提取集內(nèi)的所有曲面特征構(gòu)建成特征模板并將構(gòu)建過程獲得的曲面離散點集合、三角網(wǎng)格集合和三角面片法向量集合等信息儲存至特征模板數(shù)據(jù)庫中；圖12（d）顯示了測量坐標(biāo)系和零件坐標(biāo)系在空間中的相對位置關(guān)系；圖12（e）為坐標(biāo)系對齊后實測點云數(shù)據(jù)的偏差分析彩圖，所含點數(shù)85456；圖12（f）顯示了劃分空間柵格的參數(shù)設(shè)置和建立點云間拓撲關(guān)系的具體過程；由特征模板驅(qū)動的點云粗分割結(jié)果如圖12（g）所示；圖12（h）給出了粗分割點云法向量估算和一致性調(diào)整后的結(jié)果；圖12（i）給出了實測點云數(shù)據(jù)精確分割的最終結(jié)果，用不同顏色區(qū)分識別不同曲面特征的點云數(shù)據(jù)并注明每個點云分割塊內(nèi)所含點數(shù)。結(jié)果表明特征模板內(nèi)的所有待識別特征點云全部完成精確分割。

圖12 后段肋實測點云數(shù)據(jù)精確分割實例Fig.12 An example of accurate segmentation of measured point cloud data of posterior rib

5 結(jié)論

本文提出了一種基于特征模板的點云數(shù)據(jù)精確分割方法。用該方法對某型飛機后段肋零件實測點云中對待識別曲面特征的點云進行了精確分割。實例驗證表明該方法可以按照操作人員的意愿定制特征模板，并通過特征模板驅(qū)動和引導(dǎo)分割出點云數(shù)據(jù)中屬于目標(biāo)曲面特征的點云數(shù)據(jù)，在滿足分割效率和自動化要求的情況下提高了點云分割準確性，能夠得到精確的分割結(jié)果。

使用本方法時需要注意：分割過程中依賴點云數(shù)據(jù)與理論曲面特征模板的空間位置關(guān)系判定，因此實測點云數(shù)據(jù)分割前應(yīng)與理論三維模型進行配準，并且配準的精度會在一定程度上影響后續(xù)點云分割結(jié)果。