楊 通，姚 山，薛凱華

(大連理工大學(xué) 材料科學(xué)與工程學(xué)院，遼寧 大連 116023)

1 問題的提出

增材制造(也稱3D打印)由三維模型分層得到的切片數(shù)據(jù)直接驅(qū)動(dòng)。隨著三維掃描使用成本的降低，點(diǎn)云直接分層因可避免網(wǎng)格重建和修復(fù)等耗時(shí)過程[1]而漸受關(guān)注，然而由于缺少拓?fù)湫畔ⅲc(diǎn)云分層的效率和容錯(cuò)性仍然遠(yuǎn)不及傳統(tǒng)的網(wǎng)格分層[2]。

點(diǎn)云分層大多遵循“點(diǎn)投影到分層平面—曲線重建”兩步計(jì)算的范式[3-4]。對于單個(gè)分層平面，首先將其附近的三維點(diǎn)垂直投影，獲得二維帶狀樣本(如圖1a)，然后用樣本逐層構(gòu)造曲線。Javidrad等[5]采用自頂向下的方式對樣本迭代精簡后識(shí)別出關(guān)鍵點(diǎn)，由此擬合樣條曲線；Chen等[6]則利用動(dòng)態(tài)估算的曲率引導(dǎo)種子線段沿樣本推進(jìn)，自底向上構(gòu)造多邊形。這類早期工作主要關(guān)注曲線誤差，僅重建光滑曲線或單條曲線。Xu等[7]以平面投影所得樣本的輪廓作為初始估計(jì)并檢測多條曲線，然后迭代更新輪廓頂點(diǎn)得到最終多義線。點(diǎn)投影操作后，點(diǎn)云分層歸約為曲線重建這一欠定問題，對于曲線重建問題，基于Delaunay/Voronoi的算法族是第一個(gè)被嚴(yán)格證明的方法[8]。雖然多條線、離群點(diǎn)、稀疏/非均勻樣本、尖角等復(fù)雜情形的重建能力[9-10]不斷增強(qiáng)，但是投影導(dǎo)致的樣本厚度不均勻給成百上千層曲線的自動(dòng)重建帶來挑戰(zhàn)。用局部擬合的二次曲面代替平面進(jìn)行投影可改善樣本的均勻性[11]，也可以采用虛擬邊與分層平面求交生成減薄的樣本[12](如圖1b)，其均勻性優(yōu)于平面投影方法。虛擬邊采樣法還可與平面直接投影法混合使用來平衡采樣密度和精度[13]。

另一類方法將點(diǎn)云像素化后在圖像空間構(gòu)造曲線[14]。程效軍等[15]將投影后的樣本轉(zhuǎn)為二值圖，抽取形態(tài)學(xué)骨架并擬合樣條；Percoco等[16]用遺傳算法生成非空像素的最短遍歷路徑；Huang等[17]通過Marching Square獲得初始多邊形，然后用拉普拉斯算子消除褶皺。圖像類方法須謹(jǐn)慎確定像素尺寸，以平衡計(jì)算負(fù)荷和曲線的精度。為提高精度，可將分層平面與點(diǎn)云的移動(dòng)最小二乘(Moving Least Square, MLS)曲面求交，得到隱式的交線[18]?；贛LS的擴(kuò)展方法用Reeb圖將點(diǎn)云沿分層方向分割為若干拓?fù)洳蛔兊膮^(qū)間，然后分別分層[19],解決了隱式曲線的拓?fù)浣Y(jié)構(gòu)在相鄰層發(fā)生突變的問題。MLS方法因隱式曲面和曲線固有的平滑性而具有一定容噪能力，但未對尖角的重建效果進(jìn)行檢驗(yàn)。

Yaman等[20]和Minetto等[21]分別報(bào)道了立體光刻(Stereolithography, STL)網(wǎng)格模型的增量分層算法，他們都利用了連續(xù)層片在多數(shù)情況下拓?fù)渫咧话l(fā)生輕微幾何變化的特性，將分層平面自底向上掃過模型時(shí)，算法依據(jù)網(wǎng)格鄰接關(guān)系更新已有曲線的坐標(biāo)，并由網(wǎng)格拓?fù)渥兓录那€連接關(guān)系，避免重頭構(gòu)建每層曲線。雖然這類算法因依賴網(wǎng)格拓?fù)湫畔⒍鵁o法用于點(diǎn)云分層，但是受相鄰層形狀相似性的啟發(fā)，本文提出一種點(diǎn)云增量分層方法。首先通過虛擬邊采樣法[12]準(zhǔn)備分層平面上的二維樣本點(diǎn)，然后采用所提非監(jiān)督神經(jīng)網(wǎng)絡(luò)按增量方式逐層學(xué)習(xí)樣本的局部主成分，并建立其多義線表達(dá)作為輸出。該網(wǎng)絡(luò)稱為競爭型主成分分析(Competitive Principal Components Analysis, CPCA)模型，其參照成長型單元結(jié)構(gòu)(Growing Cell Structures, GCS)[22]，但重新設(shè)計(jì)了邊的增長/刪除、頂點(diǎn)移動(dòng)、拓?fù)涓淖?、屬性更新等機(jī)制，以便利用層間相似性快速重建和跟蹤成百上千層曲線。

2 點(diǎn)云分層算法

2.1 生成樣本點(diǎn)

如圖1所示為生成用于單層曲線重建樣本點(diǎn)的常用方法，其中較稀疏的點(diǎn)為密度降低到5%后的原始點(diǎn)云，密集分布的點(diǎn)為得到的樣本。直接投影法在截面拓?fù)浣Y(jié)構(gòu)復(fù)雜時(shí)會(huì)導(dǎo)致相鄰曲線無法分辨，虛擬邊采樣法可生成厚度均勻且拓?fù)浣Y(jié)構(gòu)可分辨的樣本[12]，因此本文采用后者。虛擬邊采樣法在當(dāng)前分層平面Z附近(距離小于d)隨機(jī)查找上下最近鄰點(diǎn)對[pa,pb]，連接兩點(diǎn)的線段記為虛擬邊ea,b，若ea,b與Z相交，則交點(diǎn)為一個(gè)有效樣本[12]。為提高樣本密度，當(dāng)交點(diǎn)不存在時(shí)，本文繼續(xù)依次查詢pa的2～4近鄰點(diǎn)pc；若ea,c與Z相交于點(diǎn)p且‖pa-p‖<3‖pa-pb‖，則認(rèn)為該交點(diǎn)也是一個(gè)有效樣本。

2.2 競爭型主成分分析網(wǎng)絡(luò)模型

CPCA是一個(gè)動(dòng)態(tài)變化的無向圖。頂點(diǎn)集V中每個(gè)成員vi保存坐標(biāo)wi，邊集E={ei,j(θ)=(wi+wj)/2+θ(wi-wj)/2|θ∈[-1,1]}表示首尾順序連接的線段，構(gòu)成數(shù)條多義線。任意頂點(diǎn)最多有兩條邊。網(wǎng)絡(luò)初始化為一個(gè)隨機(jī)的三角形，然后從依次輸入的樣本中學(xué)習(xí)并更新網(wǎng)絡(luò)屬性，根據(jù)網(wǎng)絡(luò)屬性動(dòng)態(tài)添加或刪除邊和頂點(diǎn)。給定當(dāng)前輸入樣本p，其到邊的距離

(1)

使式(1)取下確界的θ稱為點(diǎn)到邊的投影φ(p,ei,j)，邊上對應(yīng)的點(diǎn)為投影點(diǎn)PP(p,ei,j)，投影點(diǎn)到樣本的向量為誤差向量EV(p,ei,j)。為確定樣本與邊的對應(yīng)關(guān)系，令邊的感受野

Ai,j={p|D(p,ei,j)≤D(p,ex,y),?ex,y∈E}。

(2)

網(wǎng)絡(luò)目標(biāo)函數(shù)衡量樣本到邊的總偏差為

(3)

其與最優(yōu)輸運(yùn)曲線重建算法[10]中的Wasserstein誤差法向分量相同，取最優(yōu)值時(shí)任意邊需滿足

(4)

即邊重合于感受野內(nèi)樣本所確定的主軸

(5)

(6)

兩個(gè)特征值分別稱為樣本的信號(hào)和噪聲。誤差最優(yōu)條件可簡要描述為：任意頂點(diǎn)坐標(biāo)等于其所在兩條邊的主軸的交點(diǎn)。

邊用于表達(dá)其感受野內(nèi)的樣本，學(xué)習(xí)時(shí)不斷向主軸移動(dòng)以減小誤差，添加新邊也可以減小誤差。為確定何時(shí)及如何增長邊，需判定感受野內(nèi)是否包含更精細(xì)的子結(jié)構(gòu)，因此將其細(xì)分為左(L)、右(R)、上(T)、下(B)4個(gè)子感受野，如圖2所示。任意頂點(diǎn)也定義了感受野Ai，等于所在邊的感受野的并集。每條邊最終都與7個(gè)感受野關(guān)聯(lián)，即

Gi,j={Ai,j,Li,j,Ri,j,Ti,j,Bi,j,Ai,Aj}。

(7)

g={a,l,r,t,b,ai,aj}。

(8)

后文約定，當(dāng)X表示某感受野時(shí)，x表示其對應(yīng)的主軸。所有主軸默認(rèn)的θ的范圍為[-1，1]，也可用x([θ1,θ2])的形式顯示指定為其他范圍。因主軸和邊都代表線段，在式(1)及其導(dǎo)出的投影、誤差向量等函數(shù)中可相互替換使用。

感受野定義的6個(gè)屬性需要在學(xué)習(xí)過程中更新。為此，網(wǎng)絡(luò)找到當(dāng)前樣本的最近邊em,n，更新覆蓋該樣本的感受野F(p)={A,L,T,Am,An}∈Gm,n的所有屬性。高斯參數(shù)可按如下隨機(jī)梯度下降法[23]更新：

ΔΣ=β[Δp(Δp)T-Σ]。

(9)

(10)

式中：s的初始值取0；p′為該感受野上一次收到的樣本，在每個(gè)學(xué)習(xí)周期后更新為當(dāng)前樣本。感受野后兩個(gè)屬性wp和ag分別稱作獲勝概率和年齡，用于控制邊的增長、刪除和移動(dòng)，初值也取0。

2.3 主軸競爭與邊增長

em,n及其7個(gè)主軸可劃分為5組，即祖父單元[am,an]、父單元a和e、子單元[l,r]和[t,b]，每一組均可表達(dá)局部樣本的分布，獲勝概率衡量哪一種表達(dá)方式誤差較小。當(dāng)前樣本通過比較自身到不同單元的距離來估算F(p)每個(gè)成員X的獲勝概率：

(11)

據(jù)上述分析，當(dāng)min[wp(L),wp(R)]-s(A)>50%且大于兩祖父單元感受野的獲勝概率時(shí)，應(yīng)觸發(fā)左右分裂。同理，T和B滿足該條件時(shí)執(zhí)行上下分裂。偏置s(A)抑制樣本稀疏區(qū)域增長邊。當(dāng)樣本分布較復(fù)雜時(shí)，增長條件成立的可能性低，因此引入圖3c中的點(diǎn)分裂，將頂點(diǎn)投影到兩個(gè)相鄰邊的主軸以產(chǎn)生新邊。2.2節(jié)得出理想頂點(diǎn)應(yīng)重合于所在邊的主軸交點(diǎn)，因此若兩主軸所在直線的交點(diǎn)與頂點(diǎn)vm的距離d始終較大，則表明局部區(qū)域欠擬合或過擬合。由圖3c可知，欠擬合時(shí)主軸比彼此約束的邊更貼近樣本，故獲勝概率會(huì)超過50%，而過擬合會(huì)產(chǎn)生較大的wp(Am)。欠擬合區(qū)別于過擬合的另一特點(diǎn)是噪聲λ2(Am)大于兩主軸噪聲之和(記為∑λ)。由以上分析可知欠擬合的特征如下：

d2>λ2(Am)>∑λ；

wp(Am,n)>50%>wp(Am)+2s(Am,n)。

(12)

為避免統(tǒng)計(jì)的不確定性，僅當(dāng)式(12)在多次學(xué)習(xí)中持續(xù)成立才分裂vm，用ag(Am)記錄該持續(xù)性。若式(12)成立，則將ag(Am)增加β(1-ag)，否則重置為0，當(dāng)ag(Am)>50%時(shí)觸發(fā)點(diǎn)分裂。

2.4 頂點(diǎn)的移動(dòng)和刪除

CPCA采用Winner-Take-All原則移動(dòng)當(dāng)前樣本最近邊em,n的頂點(diǎn)vm。式(4)給出誤差隨機(jī)梯度下降的方向?yàn)関a=EV(p,e)。為抑制隨機(jī)性，當(dāng)該方向使邊向獲勝概率大于50%的主軸靠近時(shí)才移動(dòng)vm。可表達(dá)邊的全體樣本的主軸包括a及其兩個(gè)祖父單元，對于三者中的每一個(gè)x，邊向其靠近的方向?yàn)関b(x)=EV[PP(p,x),e]。通過va和vb的夾角可以調(diào)節(jié)移動(dòng)量，將3個(gè)主軸的貢獻(xiàn)加權(quán)求和得到總移動(dòng)量：

(13)

f(u,v)=

(14)

式中截?cái)嗪瘮?shù)Ω(y)在y>0時(shí)取y，否則取0。式(13)表明：某主軸頻繁獲勝時(shí)，會(huì)使邊迅速與其對齊；無過擬合時(shí)祖父單元的貢獻(xiàn)量為0，滿足誤差最優(yōu)條件后wp(A)≈50%且vb(a)≈0，因此頂點(diǎn)僅在σ2|σ→0范圍內(nèi)震蕩。如圖4所示，過擬合時(shí)，祖父單元貢獻(xiàn)的移動(dòng)使頂點(diǎn)所在的兩邊趨于平直，為進(jìn)一步消除褶皺，可按GCS網(wǎng)絡(luò)策略沿vc=p-wm方向移動(dòng)[22]，從而產(chǎn)生等長邊。與Δwm類似，為抑制隨機(jī)性，需確認(rèn)該方向趨于減小兩邊的長度差。為此，查找當(dāng)前樣本次近鄰邊em2,n2。當(dāng)m=m2時(shí)得到長度差減小的方向vd=EV[(wn2+wn)/2，am，n]，由此導(dǎo)出另一移動(dòng)分量

(15)

當(dāng)m≠m2時(shí)，該式為0。

2.5 邊競爭與拓?fù)渥兓?/h3>

Δag=[s(L)-1]ag。

(16)

否則所有邊的ag(A)增加[1-s(Lm,n)]/|E|，除數(shù)為總邊數(shù)。上述不等式條件成立的概率與邊長無關(guān)。

若當(dāng)前樣本到最近和次近邊的距離差值d較小，則其中一邊可能是冗余邊[24]，用[ag(L)，ag(R)]估計(jì)該可能性。此時(shí)樣本到邊的距離已不能有效判定樣本歸屬，因此認(rèn)為兩邊中使夾角p′(A)-p,e取較小值的邊與樣本分布更一致，另一邊記為ei,j。若ei,j的樣本稀疏性較顯著且前述d值較小，即則將左感受野的年齡ag(Li,j)增加

Δag=β(1-ag)，

(17)

否則將ag(Lm,n)降低β×ag(Lm,n)。左右感受野及邊感受野的年齡之和稱為邊的年齡，記作

age(e)=ag(A)+ag(L)+ag(R)。

(18)

age(e)綜合考慮了邊在全局范圍(第1項(xiàng))和局部范圍(后兩項(xiàng))的比較結(jié)果，代表邊的有效性，age(e)>1表示e為無效邊。對于CPCA的任意頂點(diǎn)，若其所有鄰邊均無效，則執(zhí)行圖4中的頂點(diǎn)刪除算子。

頂點(diǎn)被刪除后不改變多義線的拓?fù)浣Y(jié)構(gòu)，然而CPCA還需跟蹤不同分層平面上的拓?fù)渥兓?.2節(jié)表明，理想頂點(diǎn)應(yīng)與兩鄰邊主軸的交點(diǎn)重合，與此相反，若非拓?fù)溧忂叺闹鬏S相交，則可能存在拓?fù)溴e(cuò)誤，由此導(dǎo)出圖5中的頂點(diǎn)合并算子。與CHL(competitive Hebbian learning)規(guī)則[23]一樣，合并的兩頂點(diǎn)為當(dāng)前樣本的最近和次近頂點(diǎn)[vp,vq]，本文在CHL基礎(chǔ)上添加了兩條約束。首先，兩頂點(diǎn)各自均僅存在一條有效邊(age<1)，記作ep,i和eq,j；其次，這兩邊的主軸近似相交。令d為ap,i([0,1+s(Ap,i)])與aq,j([0,1+s(Aq,j)])間的最短距離，當(dāng)d2≤2λ2(Ap,i)時(shí)認(rèn)為近似相交。用s擴(kuò)展主軸參數(shù)范圍以處理較稀疏的樣本，用距離閾值代替相交條件可辨別兩邊共線的特殊情形，這兩個(gè)條件成立時(shí)便可合并當(dāng)前樣本的最近和次近頂點(diǎn)，合并后的新頂點(diǎn)位于與兩主軸距離之和最近的位置。

2.6 分層計(jì)算流程

將各計(jì)算過程組合得到點(diǎn)云分層流程：

輸入：點(diǎn)云P。

輸出：各層上的多義線。

步驟1初始化分層面Z和CPCA(為隨機(jī)三角形)。

步驟2準(zhǔn)備一個(gè)樣本點(diǎn)作為CPCA輸入(2.1節(jié))。

步驟3通過邊競爭(2.5節(jié))和主軸競爭(2.3節(jié))更新屬性。

步驟4根據(jù)屬性觸發(fā)邊增長/刪除/拓?fù)渥儞Q算子。

步驟5移動(dòng)頂點(diǎn)(2.4節(jié))。

步驟6邊平均學(xué)習(xí)次數(shù)n=n+1/|E|，若其比上次檢查時(shí)的增量達(dá)到10次，則檢查網(wǎng)絡(luò)是否收斂，是則輸出當(dāng)前層多義線，并將Z移動(dòng)到下一層。

步驟7迭代步驟2～步驟6，直到Z超過結(jié)束位置。

步驟8按Z倒序逐層檢查并修復(fù)可能的拓?fù)溴e(cuò)誤。

步驟6中，網(wǎng)絡(luò)收斂需滿足3個(gè)條件：①多義線數(shù)量在[n-20，n]時(shí)間段內(nèi)始終恒定；②邊數(shù)量在該時(shí)間段內(nèi)的變化率小于β；③所有邊的噪聲λ2(A)的平均值在連續(xù)3次收斂檢查時(shí)的變化率小于β。當(dāng)前層收斂后，CPCA不重置網(wǎng)絡(luò)結(jié)構(gòu)，直接切換到下一層繼續(xù)學(xué)習(xí)，因此避免了從頭構(gòu)建下一層多義線。

由于統(tǒng)計(jì)學(xué)習(xí)具有隨機(jī)性，無法保證成百上千層多義線中無任何拓?fù)溴e(cuò)誤，因此用步驟8按照Z倒序逐層檢查。檢查過程中，若某層存在開線或無效邊(age>1)，則用下一層(Z+層厚)結(jié)果重新初始化CPCA并學(xué)習(xí)，直至收斂。若收斂后所得封閉線數(shù)量減開線數(shù)量比正向分層時(shí)大，則替換原有結(jié)果。

步驟2中計(jì)算虛擬邊需查詢最近鄰點(diǎn)對，步驟3需查詢當(dāng)前樣本的最近和次近邊及頂點(diǎn)，算法采用可動(dòng)態(tài)擴(kuò)展/收縮的均勻網(wǎng)格[25]保存邊、頂點(diǎn)及分層平面附近的點(diǎn)云，以加快查詢速度。由于相鄰層形狀具有相似性，網(wǎng)格在分層平面移動(dòng)時(shí)不用頻繁地?cái)U(kuò)展或收縮。

3 實(shí)驗(yàn)結(jié)果與分析

為評價(jià)分層效率及多義線重建的幾何誤差和拓?fù)溴e(cuò)誤，將本文算法與基于平面最小二乘投影(Planar Least-Squares Projection, PLSP)的分層算法[7]進(jìn)行比較。PLSP采用圖1中的直接投影法準(zhǔn)備樣本，然后用滾球法抽取其外輪廓，最后迭代移動(dòng)輪廓頂點(diǎn)，以最小化樣本到頂點(diǎn)的加權(quán)距離和。與PLSP不同，本文目標(biāo)函數(shù)衡量樣本到邊的距離和，類似于最優(yōu)輸運(yùn)(Optimal Transport, OT)[10]曲線重建算法。OT算法從樣本點(diǎn)的Delaunay剖分開始，不斷合并對誤差貢獻(xiàn)較小的邊，同時(shí)移動(dòng)頂點(diǎn)以得到多義線。OT代表常用的基于Delaunay剖分的曲線重建算法族，因此也作為對比算法，其樣本同樣用虛擬邊方法生成。所有算法都采用C++實(shí)現(xiàn)，其中PLSP的實(shí)現(xiàn)來自文獻(xiàn)[7]，OT來自開源程序[10]，所有實(shí)驗(yàn)運(yùn)行環(huán)境為Intel(R)Core(TM)i7-4790 CPU@ 3.6 GHz。為測試容噪性，在理想曲線上采樣無偏差樣本后，按高斯分布N(0，kε2)作隨機(jī)移動(dòng)，其中k控制噪聲幅度，ε為最近鄰樣本點(diǎn)對的平均距離。用理想曲線C(θ)和重建多義線間的偏差衡量重建誤差，每條邊的誤差按其感受野內(nèi)曲線與邊的Hausdorff距離計(jì)算：

式中Diag為整體樣本外包圍盒對角線的長度。計(jì)算誤差統(tǒng)計(jì)值時(shí)采用手動(dòng)刪除拓?fù)溴e(cuò)誤，并用試錯(cuò)法優(yōu)選對比算法的運(yùn)行參數(shù)。

首先用不同噪聲幅度k及不同分布的4組樣本測試CPCA的基本特性，得到如圖6～圖9所示的結(jié)果。所有圖中都列出了CSR，OT，PLSP 3種算法的對比輸出，圖中的數(shù)字標(biāo)號(hào)表示局部放大區(qū)，用于觀察散亂分布的樣本與重建曲線的擬合情況。圖6和圖7分別表示樣條曲線和組合曲線兩種典型的應(yīng)用場景。在圖6算例中，曲線既包含細(xì)長的尖角，也包含光順區(qū)域，樣本含10 000個(gè)點(diǎn)，噪聲k=2，6；在圖7算例中，樣本有兩個(gè)漢字，各采樣7 000點(diǎn)，k=2，4。圖6和圖7表明：①當(dāng)樣本噪聲較小時(shí)，CPCA輸出逼近目標(biāo)曲線的高精度多義線，曲線的光順部分和尖角部分均得到重建；②CPCA和OT的尖角重建效果優(yōu)于PLSP，這是因?yàn)榍皟烧叩哪繕?biāo)函數(shù)優(yōu)化樣本到邊的距離，而PLSP優(yōu)化樣本到頂點(diǎn)的距離，所以PLSP重建具有尖角特征的曲線時(shí)誤差較大(如表1)；③噪聲增加時(shí)，CPCA的輸出由精變粗，精度隨之下降，該特性與圖6c～圖6d中OT的重建結(jié)果表現(xiàn)一致，但OT為避免拓?fù)溴e(cuò)誤而生成了更簡化的多義線。

表1 多義線重建幾何誤差的比較 %

圖8和圖9的算例驗(yàn)證了CPCA處理非均勻和稀疏樣本的能力，樣本點(diǎn)采用圖1中的直接投影法得到，分別包含2 062和791個(gè)點(diǎn)。3種算法在圖8和圖9中的對比結(jié)果表明，CPCA和PLSP均可處理投影點(diǎn)云帶寬度不均勻的情形，而OT在寬度較大的區(qū)域生成分叉邊。PLSP采用直接投影法生成樣本，因此可能導(dǎo)致相鄰曲線無法分辨，在與分層平面接近于平行的區(qū)域采樣時(shí)，需要減小圖1中的參數(shù)d，或調(diào)整用于識(shí)別相鄰曲線的距離參數(shù)，這樣的用戶干預(yù)導(dǎo)致成百上千層曲線的自動(dòng)重建較困難，而本文采用的虛擬邊采樣方法避免了這一問題。如圖9a的樣本分布所示，當(dāng)樣本存在局部缺失時(shí)，CPCA仍可得到圖9b中正確的拓?fù)浣Y(jié)構(gòu)，但已無法重建曲線的細(xì)節(jié)特征。對于這種特殊情形，可對多義線進(jìn)行擬合得到光滑的樣條曲線[12]。

為驗(yàn)證CPCA對實(shí)測點(diǎn)云的分層效果，使用形創(chuàng)HandySCAN(TM)掃描儀獲取圖10a中的4組點(diǎn)云，分別為720°螺旋葉輪、傳動(dòng)螺桿、狗雕塑、鞋模。由于采用非接觸式測量，點(diǎn)云在自相遮擋區(qū)域存在部分缺失。點(diǎn)云4的分層方向垂直于圖像平面，前3個(gè)點(diǎn)云沿圖像列方向分層，圖10b～圖10e所示為分層結(jié)果，其中的層片每間隔數(shù)層顯示1層。為衡量CPCA的增量分層特性，將邊按其創(chuàng)建的先后順序編號(hào)，執(zhí)行增長、刪除和拓?fù)渌阕訒r(shí)，若既有移除邊也有新增邊，則后者編號(hào)繼承自前者。若第k層的某邊在k-1層也存在，則稱為繼承邊，單層上繼承邊的占比稱作繼承比，邊在單層上的平均學(xué)習(xí)次數(shù)簡稱為平均學(xué)習(xí)，表2所示為繼承比和平均學(xué)習(xí)次數(shù)在所有層上的均值。另外，將連接相鄰層相同編號(hào)邊的曲線稱為層間映射線。

表2 點(diǎn)云分層基準(zhǔn)測試

葉輪模型兩端是平行于分層方向的中軸，層厚為1 mm時(shí)，端部約30 mm范圍內(nèi)(圖11a曲線上的箭頭標(biāo)識(shí))CPCA快速收斂，繼承比大于98%；螺旋上升的葉片部分的繼承比在90%～98%之間波動(dòng)，平均學(xué)習(xí)次數(shù)與繼承比呈反相關(guān)。圖12所示為繼承邊的運(yùn)動(dòng)軌跡，其中多數(shù)繼承關(guān)系延續(xù)數(shù)十層不間斷。圖10c所示為螺桿層片的側(cè)視圖，螺桿的外輪廓呈圓柱形，但上下兩端存在齒槽導(dǎo)致的拓?fù)浣Y(jié)構(gòu)變化，對應(yīng)圖11d平均學(xué)習(xí)曲線上標(biāo)識(shí)的尖峰，因此拓?fù)渫蛔儽韧咦冃胃臅r(shí)。另外，螺桿點(diǎn)云的平均學(xué)習(xí)曲線呈U型下降后上升，與圓柱輪廓截面的變化趨勢一致，即單層收斂時(shí)間隨同胚變形量增長。由圖10e可見，點(diǎn)云4鞋底有復(fù)雜的花紋，其在表2中的平均學(xué)習(xí)次數(shù)顯著高于其他3組數(shù)據(jù)。以上對不同層及不同點(diǎn)云的比較表明，本文算法可有效利用層間形狀的相似性來提高分層效率。

為進(jìn)一步驗(yàn)證CPCA增量分層對效率的貢獻(xiàn)，對不同分層方式的運(yùn)行時(shí)長進(jìn)行比較，得到表3所列數(shù)據(jù)。表中的分層時(shí)間包括了圖1中樣本生成方法的耗時(shí)和后續(xù)的曲線重建耗時(shí)。為獲得有意義的比較結(jié)果，兩個(gè)階段都需要合理設(shè)置影響耗時(shí)的參數(shù)，樣本生成時(shí)參數(shù)d(如圖1)統(tǒng)一取1.3 mm。在曲線重建時(shí)，PLSP，OT，CPCA具有不同的參數(shù)。其中，PLSP構(gòu)建初始輪廓時(shí)按建議值[7]取k近鄰為40，移動(dòng)頂點(diǎn)時(shí)，當(dāng)其振幅小于平均邊長的5%后停止迭代；OT迭代刪除邊直到數(shù)量與CPCA輸出相同，將其加速選項(xiàng)全部打開，而且構(gòu)造初始Delaunay剖分時(shí)僅使用15%樣本；CPCA除學(xué)習(xí)率外無其他參數(shù)，取默認(rèn)值5%。

表3 分層時(shí)間比較 s

由表3可知，當(dāng)點(diǎn)云1的層厚由1 mm降低到0.5 mm時(shí)，CPCA整體耗時(shí)僅略為增長，即單層耗時(shí)減半，而PLSP和OT的單層耗時(shí)與層厚無關(guān)。比較表明，CPCA增量分層較每層從頭構(gòu)建多義線的方法(PLSP和OT)縮短了計(jì)算時(shí)間，而且效率優(yōu)勢隨層厚的降低更加顯著，這是由于CPCA的邊平均學(xué)習(xí)次數(shù)與層厚相關(guān)。如圖11c和圖11f所示，層厚為0.1 mm時(shí)多數(shù)層片在1～2次檢查后便收斂，邊平均學(xué)習(xí)10～20次?，F(xiàn)有的選擇性光固化、數(shù)字光投影、選擇性激光熔融等增材制造方法已將層厚降至數(shù)十微米，因此CPCA在實(shí)際應(yīng)用中具有極低的邊平均學(xué)習(xí)次數(shù)，可以利用層間相似性顯著加速分層過程。雖然較非增量式的點(diǎn)云分層方式大幅提高了效率，但是CPCA仍不及網(wǎng)格分層[21]，若不考慮點(diǎn)云轉(zhuǎn)換為STL模型的復(fù)雜性及手動(dòng)修復(fù)網(wǎng)格的耗時(shí),表3算例中等價(jià)的網(wǎng)格模型分層耗時(shí)均小于1 min。

表4統(tǒng)計(jì)了不同分層方式下拓?fù)溴e(cuò)誤的數(shù)量，包括非封閉多義線、相交邊、分叉線(某頂點(diǎn)連接到多于兩條邊的情形)。除這3類拓?fù)溴e(cuò)誤外，還將點(diǎn)云重構(gòu)為STL文件后使用Minetto[21]的開源程序進(jìn)行分層處理，網(wǎng)格分層與點(diǎn)云分層所得多義線數(shù)量的差值也計(jì)入表4中的拓?fù)溴e(cuò)誤數(shù)量。在CPCA輸出中未發(fā)現(xiàn)相交邊和分叉線，表4列出了其步驟8修復(fù)前/修復(fù)后的錯(cuò)誤數(shù)。點(diǎn)云1～點(diǎn)云3的分層錯(cuò)誤均被修復(fù)，點(diǎn)云4鞋底花紋區(qū)遺留了部分開線，這些開線歸因于統(tǒng)計(jì)學(xué)習(xí)的非確定性，花紋部位點(diǎn)云密度不足會(huì)加劇非確定性。在所有測試案例中，點(diǎn)云4的樣本數(shù)量最少，實(shí)驗(yàn)特意選定了一個(gè)使截面輪廓拓?fù)渥兓顒×业姆謱臃较?，即使采用點(diǎn)云重建網(wǎng)格+網(wǎng)格分層的處理方式，花紋部分也需用耗時(shí)的網(wǎng)格手動(dòng)修復(fù)才能避免拓?fù)溴e(cuò)誤。由表4可知，本文的增量分層方法通過繼承相鄰層的學(xué)習(xí)結(jié)果降低了拓?fù)溴e(cuò)誤發(fā)生的概率(修復(fù)前)，而且步驟8進(jìn)一步利用層間的相似性修復(fù)了可能的拓?fù)溴e(cuò)誤。對于層間相似性小的低密度點(diǎn)云，可多次迭代執(zhí)行步驟8，從而用降低算法效率換取拓?fù)湔_性。另外，實(shí)際應(yīng)用中可通過縫合開線的最近鄰端點(diǎn)對來閉合多義線，但該操作在處理復(fù)雜拓?fù)浣Y(jié)構(gòu)時(shí)可能需要手動(dòng)修復(fù)。圖13所示為點(diǎn)云4分層數(shù)據(jù)(0.1 mm層厚)經(jīng)過修復(fù)后用SLA打印得到的樹脂件。

表4 拓?fù)溴e(cuò)誤的數(shù)量比較

CPCA僅開放學(xué)習(xí)率這一參數(shù)，所有實(shí)驗(yàn)取默認(rèn)值5%。較大的學(xué)習(xí)率可加快網(wǎng)絡(luò)收斂，但會(huì)增加需要步驟8修復(fù)的拓?fù)溴e(cuò)誤。由于點(diǎn)云3和點(diǎn)云4的截面輪廓變化較大，PLSP和OT很難通過固定參數(shù)得到拓?fù)溴e(cuò)誤較少的結(jié)果。在表4中，實(shí)驗(yàn)將兩組點(diǎn)云沿Z方向手動(dòng)分割為數(shù)個(gè)區(qū)間，并單獨(dú)調(diào)整每個(gè)區(qū)間的參數(shù)，發(fā)現(xiàn)OT中控制輸出邊數(shù)量的參數(shù)和PLSP中分辨多條曲線的參數(shù)對拓?fù)溴e(cuò)誤起主導(dǎo)作用。雖然引入了手動(dòng)干預(yù)，但是OT和PLSP方法的拓?fù)溴e(cuò)誤數(shù)仍高于CPCA。在重建成百上千層曲線時(shí)，參數(shù)優(yōu)選成為不可忽視的問題，現(xiàn)有文獻(xiàn)[3-19]對此關(guān)注較少，而增量分層利用層間相似性為其提供了可能的解決思路。

4 結(jié)束語

本文提出一種非監(jiān)督學(xué)習(xí)網(wǎng)絡(luò)CPCA，由點(diǎn)云增量式地構(gòu)造增材制造用的各層曲線。CPCA設(shè)計(jì)了一套移動(dòng)、增長、刪除、拓?fù)渥儞Q學(xué)習(xí)機(jī)制，在對輸入點(diǎn)云假定最少先驗(yàn)知識(shí)的條件下，可連續(xù)追蹤變化的曲線，并利用相鄰層片的拓?fù)浜蛶缀蜗嗨菩员苊鈴念^構(gòu)造每層曲線，該相似性用于從噪聲、數(shù)據(jù)缺失等異常輸入中恢復(fù)尖角、凹凸性等顯著特征，以及從學(xué)習(xí)歷史中繼承正確的拓?fù)潢P(guān)系。實(shí)驗(yàn)將CPCA與非增量式PLSP和OT算法相比，結(jié)果表明CPCA可提高成百上千層密集堆疊層片的構(gòu)造效率，且在無用戶干預(yù)下重建拓?fù)浣Y(jié)構(gòu)較復(fù)雜的截面輪廓。然而，作為統(tǒng)計(jì)學(xué)習(xí)網(wǎng)絡(luò)，CPCA的輸出是非確定的，后續(xù)研究將通過增加迭代次數(shù)、批量學(xué)習(xí)等策略來完全消除復(fù)雜模型的拓?fù)溴e(cuò)誤。