許志勇，張 云，王亞平

（1.北方工業(yè)大學(xué)，北京 100043；2.北京航空航天大學(xué)，北京 100191）

渦輪葉片是航空發(fā)動機關(guān)鍵的熱端部件，其加工質(zhì)量決定了整機的性能與壽命。渦輪葉片制造工藝復(fù)雜，其精鑄精度要求高（如某型號葉片型面輪廓度要求0.2mm，[–0.1 mm，+0.1 mm]），首先通過鎳基高溫合金等材料精鑄而成，隨后在快速、精確配準(zhǔn)定位的前提下，進(jìn)行數(shù)控加工、特種加工等工序。其中，配準(zhǔn)定位是通過尋找渦輪葉片測量點云與CAD 模型間最佳相對位姿實現(xiàn)的。

配準(zhǔn)定位方面應(yīng)用最為廣泛的是ICP 算法及其改進(jìn)之后的算法[1–2]，其關(guān)鍵步驟中，預(yù)對齊和匹配點集搜索關(guān)系到ICP 算法求解的精度和效率。預(yù)對齊算法可為ICP配準(zhǔn)提供較好的初始位姿，避免陷入局部最優(yōu)。目前，常見的預(yù)對齊方法有重心重合法[3]、6 點對齊法[4]、標(biāo)簽法[5]主成分分析法[6]、特征提取法[5]等。而匹配點集搜索則是為了提高ICP 配準(zhǔn)效率，Li 等[7]使用三角網(wǎng)格搜索匹配點集，通過減少搜索最近點集的時間來提高算法效率。Geng 等[8]則采用了基于鄰域約束的空間投影法。程軍等[9]構(gòu)建kd–tree 將點云空間劃分為多個子空間，并利用并行計算加速查詢匹配點集。

為此，本研究針對渦輪葉片配準(zhǔn)定位的實際需求，分析了預(yù)對齊和匹配點集搜索的重要性；在自主研發(fā)CAD/CAM 軟件平臺上以Visual studio 2015 為開發(fā)工具，使用基于主成分分析、手工關(guān)聯(lián)兩種預(yù)對齊算法實現(xiàn)測量點云與CAD 模型具有較好的初始位姿；對網(wǎng)格法、賦范空間投影法、基于kd–tree 快速搜索法3 種匹配點集搜索算法進(jìn)行效率對比，并確定了最優(yōu)的渦輪葉片配準(zhǔn)定位方案。

1 ICP 配準(zhǔn)定位算法分析

經(jīng)典的ICP 算法[10]是由McKay 和Besl 提出的，其核心思想是迭代調(diào)姿使距離偏差最小化，目標(biāo)函數(shù)如式（1）所示，利用奇異值分解法[11]和四元組法[12]找出測量點云與CAD 模型匹配點集的空間變換矩陣，多次迭代直至目標(biāo)函數(shù)滿足一定的精度為止。

式中，pi（i=0，1，…，n）為待配準(zhǔn)的測量點；qi（i=0，1，…，n）為pi在CAD 模型上的匹配點；（qi，pi）為匹配點集；R、T分別為待求的旋轉(zhuǎn)矩陣與平移矩陣。

針對渦輪葉片實際應(yīng)用情況，通常測量點云依靠光學(xué)掃描設(shè)備獲取，且初始點云位姿與渦輪葉片CAD 模型相差懸殊，直接對兩者進(jìn)行配準(zhǔn)定位，往往會陷入局部最優(yōu)，并且效率較低。為此，在使用ICP 算法時提出如下需求。

（1）避免初始位置依賴性。

初始位置對ICP 算法的求解結(jié)果影響很大，其收斂速度及收斂解直接受制于求取的匹配點集是否精確。為此，在第2 節(jié)采用基于主成分分析預(yù)對齊與手工關(guān)聯(lián)預(yù)對齊方式保證測量點云與葉片CAD 模型間較好的初始位姿。

（2）避免匹配點計算效率低。

ICP 算法迭代過程中需要頻繁計算測量點與CAD模型間的最近點，即匹配點集搜索，搜索效率決定了配準(zhǔn)定位的計算效率。為此，在第3 節(jié)對3 種點到曲面最近點的算法進(jìn)行比較，包括網(wǎng)格法、賦范空間投影法和基于kd–tree 快速搜索法。

如圖1 所示，以典型渦輪葉片光學(xué)測量點云為數(shù)據(jù)源，以葉片CAD 模型為目標(biāo)源進(jìn)行上述配準(zhǔn)定位中預(yù)對齊和匹配點集搜索算法的應(yīng)用研究。

圖1 渦輪葉片測量點云與CAD 模型Fig.1 Turbine blade measurement point cloud and CAD model

2 預(yù)對齊方式對比分析

開展ICP 精確配準(zhǔn)定位最基礎(chǔ)的是預(yù)對齊，為了便于后續(xù)匹配點集的快速搜索，測量點云盡量逼近CAD模型。

2.1 手工關(guān)聯(lián)預(yù)對齊

手工預(yù)對齊方法是通過手工建立多組點–對應(yīng)面的關(guān)聯(lián)關(guān)系，具體流程如下：

（1） 通過交互界面，手工建立測量點云P={p1，…，pi，…，pm}和CAD 模型面片F(xiàn)={f1，…，fj，…，ft}的關(guān)聯(lián)關(guān)系Mij=（pi，fj）；

（2）計算各個關(guān)聯(lián)Mij中（pi，fj）形成的匹配點Q={q1，…，qi，…，qm}；

（3）使用ICP 算法配準(zhǔn)對齊（P，Q）。

執(zhí)行過程如圖2 所示，相應(yīng)結(jié)果在2.3 節(jié)中進(jìn)行對比分析。

圖2 手工預(yù)對齊Fig.2 Manual pre-alignment

2.2 基于主成分分析的預(yù)對齊

基于主成分分析 （PCA）的預(yù)對齊是通過計算測量點云的協(xié)方差矩陣，求得該協(xié)方差矩陣特征值所對應(yīng)的特征向量，以兩兩垂直的3 個特征向量為空間坐標(biāo)系的3 個坐標(biāo)軸，以點云數(shù)據(jù)的重心為坐標(biāo)原點，建立該點云的特征坐標(biāo)系。通過將測量點云和CAD 模型離散點云的特征坐標(biāo)系調(diào)整到一致來達(dá)到快速預(yù)對齊的目的。

具體實施步驟：

（1）對CAD 模型進(jìn)行離散，得到離散點云Q={q1，…，qj，…，qn}。

（2）計算P和Q的重心坐標(biāo)gp與gq，分別對P和Q內(nèi)各點進(jìn)行去均值標(biāo)準(zhǔn)化處理。

pi=pi–gp（i=1，2，…，m）

qj=qj–gq（j=1，2，…，n）

（3）點云依坐標(biāo)值進(jìn)行矩陣轉(zhuǎn)置為PT= [p1，…，pm]T=[Xp，Yp，Zp]，QT= [q1，…，qn]T= [Xq，Yq，Zq]，分別求PT、QT的協(xié)方差矩陣，即

（4） 計算covp、covq特征向量[α1，α2，α3]和[β1，β2，β3]，并以gp與gq為原點建立特征坐標(biāo)系Wp與Wq。

（5）經(jīng)過旋轉(zhuǎn)矩陣R和平移向量T使得Wp與Wq重合，從而實現(xiàn)基于主成分分析的預(yù)對齊。

執(zhí)行過程如圖3 所示，相應(yīng)結(jié)果在2.3 節(jié)中進(jìn)行對比分析。

圖3 基于主成分分析的預(yù)對齊Fig.3 Pre-alignment based on principal component analysis

2.3 預(yù)對齊方式對比分析

在2.1 與2.2 節(jié)中針對初始位姿差異較大的測量點云與CAD 模型，詳細(xì)介紹了手工關(guān)聯(lián)和基于主成分分析的預(yù)對齊方法，相應(yīng)配準(zhǔn)定位精度結(jié)果如表1 所示。可知，基于本次手工選點所得到的配準(zhǔn)手工關(guān)聯(lián)對齊結(jié)果較主成分分析對齊結(jié)果理想，但人工參與后降低了預(yù)對齊的效率。手工關(guān)聯(lián)預(yù)對齊的各個關(guān)聯(lián)形成匹配點的計算并不復(fù)雜，可以較快進(jìn)行對齊配準(zhǔn)，而主成分分析是計算測量點云的協(xié)方差矩陣，計算過程復(fù)雜，因此手工關(guān)聯(lián)預(yù)對齊相較于主成分法耗時短。

表1 預(yù)對齊各軸偏移結(jié)果較理論值差異對比Table 1 Comparison of deviation results of pre-aligned axes with theoretical values

3 匹配點集搜索算法對比分析

因葉片后續(xù)工藝需求，經(jīng)過預(yù)對齊之后，采用ICP算法進(jìn)一步精確配準(zhǔn)定位葉片自由曲面CAD 模型及其相應(yīng)測量點云的空間相對位姿。其中，匹配點集的計算效率問題是ICP 算法的主要問題。

3.1 網(wǎng)格法搜索匹配點集

網(wǎng)格法求取測量點到自由曲面最近點的基本思路是將自由曲面的參數(shù)域D={（u，v）|umin≤u≤umax，vmin≤v≤vmax}分別沿著u向和v向等分成m份和n份，參數(shù)域上的m×n個網(wǎng)格中心點參數(shù)值為Eij= {（ui，vj），i= 1，2，…，m；j= 1，2，…，n}，自由曲面上所對應(yīng)的三維坐標(biāo)點為qij，選取其中最小的距離作為最短距離，并對該中心點所對應(yīng)的參數(shù)域網(wǎng)格繼續(xù)細(xì)化，重復(fù)以上網(wǎng)格劃分求取最近點的過程，直到前后兩次最近點的差值小于一定的迭代精度終止。網(wǎng)格法細(xì)分曲面，求取最近點的原理如圖4 所示。

圖4 網(wǎng)格法計算匹配點原理圖Fig.4 Schematic diagram of calculating matching points by grid method

3.2 賦范空間投影法搜索匹配點集

賦范空間投影法是在充分考慮曲面的局部微分性質(zhì)的基礎(chǔ)上，利用迭代逼近的方法求取空間點到自由曲面的極值距離。但是，在復(fù)雜曲面邊界處或者封閉曲面上進(jìn)行最近點搜索匹配時，該方法極易不收斂。為此，對該方法進(jìn)行改進(jìn)：在不考慮自由曲面邊界的前提下，使用迭代法求解空間點在曲面上的垂足點，判定垂足點是否在曲面的位置。若在曲面內(nèi)，那么垂足點就是最近點；若不在曲面內(nèi)，則根據(jù)垂足點Q的uv參數(shù)進(jìn)行處理分析，使得最近點落在相應(yīng)的曲面邊界上，其基本原理如圖5 所示，將最終的迭代最近點Q（u，v）后置到了Q'（u'，v'）處。

圖5 賦范空間投影法邊界處理示意圖Fig.5 Boundary treatment diagram of normed space projection method

在圖5 中，F(xiàn)為自由曲面，P為空間點，Q（u0，v0）為F上的迭代初始點，向量，空間向量n、dv、du分別是Q（u0，v0）處的法矢量、u向切矢和v向切矢，在Q（u0，v0）處形成了放射坐標(biāo)系框架，Q（u，v）為P在放射坐標(biāo)系dv、du面上的投影點。設(shè) （Δu，Δv）為參數(shù)（u，v）與參數(shù) （u0，v0）的差值，l為向量r在法矢量n上的投影，則

式 （2）兩側(cè)分別乘以du、dv，且由于n·du= 0，n·dv= 0，令r·du=A，r·dv=B，du·du=E，du·dv=F，dv·dv=G，則式 （2）變換成

du、dv是曲面F在初始迭代點Q（u0，v0）處的局部微分信息，，至此，可以順利求出未知量Δu和Δv，從而確定投影點Q（u+Δu，v+Δv）的坐標(biāo)，再以Q（u+Δu，v+Δv）作為初始迭代點，重復(fù)執(zhí)行以上過程，直到 （Δu）2+（Δv）2≤ε時，迭代終止，垂足點Q就是空間點P到曲面F的最近點。而曲面都是有邊界的，所以垂足點Q有可能不落在曲面F內(nèi)部。當(dāng)垂足點Q落在F內(nèi)部時，Q就是所求的最近點，|PQ|就是最短距離；當(dāng)垂足點Q不在F內(nèi)部時，最近點不再是垂足點Q，而應(yīng)該在自由曲面邊界上。

3.3 基于kd–tree 快速搜索匹配點集

kd–tree 搜索算法是一種高維空間中最近鄰與近似最近鄰的快速查找技術(shù)，它將整個高維空間按照一定的原則、遞歸地進(jìn)行劃分，然后查詢點根據(jù)kd–tree 建立的規(guī)則，在特定空間內(nèi)進(jìn)行查詢與回溯操作，從而找到距離函數(shù)最小的匹配點?；趉d–tree 快速搜索匹配點集算法分為兩大部分，即kd–tree 的建立和基于kd–tree 最近點的快速搜索。

創(chuàng)建kd–tree 流程如圖6 所示，具體步驟如下。

圖6 創(chuàng)建kd–tree流程圖Fig.6 Flowchart of creating kd–tree

（1）在K維數(shù)據(jù)集合M中計算并選出最大方差的維度SplitDim，而后對該維度SplitDim 上的數(shù)據(jù)進(jìn)行升序排列，取其中值MidVal 對該數(shù)據(jù)集合M進(jìn)行劃分，得到兩個子集合Mleft和Mright；同時創(chuàng)建一個樹節(jié)點KDTreeNode 來存儲中值MidVal 所對應(yīng)的高維數(shù)據(jù)點。

（2）遞歸地對兩個子集合重復(fù)步驟（1）的過程，直至所有子集合都不能再劃分為止。

而快速搜索的基本思路是基于kd–tree 這種平衡排序樹的數(shù)據(jù)結(jié)構(gòu)，在kd–tree 上進(jìn)行比較分析確定搜索路徑，從而鎖定查詢的極小空間區(qū)域。隨后進(jìn)行回溯操作以確定最近點。因此kd–tree 搜索算法計算效率較好。算法的具體實施步驟如下：

（1）在kd–tree 上進(jìn)行二分查找，形成搜索路徑；

（2）用搜索路徑中的最后一個節(jié)點（葉節(jié)點）作為當(dāng)前最近點；

（3）回溯查找，沿著搜索路徑由下而上進(jìn)行回溯搜索，更新最近點；

（4）當(dāng)查詢點的鄰域與當(dāng)前節(jié)點的分割超平面相交時，需要用當(dāng)前節(jié)點另一側(cè)的子分支，跳轉(zhuǎn)到步驟（1），補充新的搜索路徑。

3.4 匹配點計算效率的比較

對圖1 所示算例進(jìn)行上述3 種匹配點集的搜索，情況如表2 所示，可知，網(wǎng)格法的計算效率最低，同等條件下，計算耗時約為賦范空間投影法的3 倍；基于kd–tree搜索算法的效率最高，并且測試點數(shù)越多效果越明顯。

表2 匹配點集計算時間對比Table 2 Comparison of calculation time of matching point set

由此，采用手工關(guān)聯(lián)預(yù)對齊、基于kd–tree 快速搜索匹配點集和ICP 方法對圖1 所示算例進(jìn)行配準(zhǔn)定位，在自主研發(fā)CAD/CAM 軟件平臺上定位效果如圖7 所示。實例測量點云與CAD 模型差異區(qū)間為[–0.06 mm，+0.1 mm]，符合渦輪葉片精鑄精度情況。

圖7 渦輪葉片定位前與最優(yōu)定位效果Fig.7 Before turbine blade positioning and optimal positioning effect

4 結(jié)論

本文研究了渦輪葉片精鑄后測量點云與CAD 模型的配準(zhǔn)定位技術(shù)，重點對比分析了影響配準(zhǔn)精度的預(yù)對齊方法，以及影響配準(zhǔn)效率的匹配點集搜索方法，得到如下結(jié)論。

（1）分析了利用ICP 算法進(jìn)行配準(zhǔn)定位的特點和難點問題，指出了提高配準(zhǔn)精度的預(yù)對齊以及提高配準(zhǔn)效率的匹配點集搜索需求。

（2）針對初始位姿不好的測量點云，實現(xiàn)了基于主成分分析的預(yù)對齊和手工關(guān)聯(lián)預(yù)對齊，對比分析表明手工關(guān)聯(lián)預(yù)對齊具有更好的配準(zhǔn)精度，但人工參與不可避免帶來預(yù)對齊效率的降低。

（3）針對匹配點計算效率較低的問題，實現(xiàn)3 種匹配點的計算方法，通過比較分析，基于kd–tree 搜索算法計算效率較好。在此基礎(chǔ)上，確定了手工關(guān)聯(lián)預(yù)對齊、基于kd–tree 快速搜索匹配點集和ICP 方法的配準(zhǔn)方案。

（4）優(yōu)化出了一種配準(zhǔn)算法組合。配準(zhǔn)完成之后使得整體型面的余量滿足后續(xù)加工要求，配準(zhǔn)定位后可以保證用戶指定的余量要求。