基于SVM的填充輪廓分類方法

周波，李論，田同同，趙吉賓

(1.中國科學(xué)院沈陽自動化研究所，遼寧沈陽 110016；2.中國科學(xué)院機器人與智能制造創(chuàng)新研究院，遼寧沈陽 110169)

0 前言

傳統(tǒng)復(fù)雜工件增材制造的路徑規(guī)劃方式主要有以下幾種：等距輪廓偏置(CPO)、往復(fù)(Zig-Zag)、單方向。這些傳統(tǒng)的路徑填充方法的優(yōu)點是計算簡單、算法成熟、易于實現(xiàn)；而缺點是填充效率偏低，Zig-Zag還容易在邊緣產(chǎn)生鋸齒痕跡，影響填充質(zhì)量。目前，科研人員提出了更高效、新穎的填充路徑，如雙螺旋填充[1]及直骨架填充[2]，它們在提高填充效率以及填充質(zhì)量方面各有特點與優(yōu)勢。

上述填充路徑有不同的填充輪廓特征，如：雙螺旋路徑要求填充多邊形盡量“圓潤”，而棱角分明的填充區(qū)域很明顯會存在較多的填充空白區(qū)域，并不適合這種填充路徑；適合直骨架的填充區(qū)域特征是中軸線兩側(cè)的區(qū)域比較均勻，為“狹長”型區(qū)域。圖1所示為適合于CPO、雙螺旋路徑及直骨架路徑的待填充多邊形區(qū)域。

圖1 待填充區(qū)域

對不同形狀的待填充多邊形而言，分類的關(guān)鍵問題在于歸納適應(yīng)填充路徑的特征。填充路徑僅有前述幾種，但是填充多邊形與適應(yīng)路徑的對應(yīng)關(guān)系較為復(fù)雜，只有研究準確的多邊形分類方法再以對應(yīng)的路徑進行填充，才能實現(xiàn)高效率、高精度填充?；诖?，本文作者提出一種基于SVM(Support Vector Machines)的填充輪廓分類方法，具體算法流程如圖2所示。該方法避免了逐一分析復(fù)雜的輪廓參數(shù)，而是利用填充過程中總結(jié)出的經(jīng)驗，歸納出填充輪廓分類方法，通過機器學(xué)習(xí)的方式進行訓(xùn)練，建立以多邊形為輸入、以填充類型為輸出的數(shù)學(xué)模型。通過對輪廓多邊形進行填充和SVM建模，驗證該方法的有效性。

圖2 基于SVM的填充輪廓分類算法流程

1 相關(guān)研究工作

隨著統(tǒng)計機器學(xué)習(xí)方法的快速發(fā)展，線性及非線性分類技術(shù)越來越豐富。在這些技術(shù)中，SVM由于結(jié)構(gòu)風(fēng)險小、泛化能力較強，可以避免過學(xué)習(xí)和陷入局部最優(yōu)解等問題，且僅需要少量的訓(xùn)練樣本就可以獲得相對好的訓(xùn)練成果，得到了廣泛應(yīng)用。SVM是由模式識別中廣義肖像算法發(fā)展而來的分類器[3]，其早期研究成果源自于前蘇聯(lián)學(xué)者VAPNIK和LERNER在1963年發(fā)表的研究[4]。

針對一個分類問題，若數(shù)據(jù)是線性可分的，也就是用一條直線就可以將2種特征分開的時候，只要將直線的位置放在讓2種特征的直線距離最大化的位置即可，尋找這個最大間隔的過程就叫做最優(yōu)化。但是，本文作者所討論的多邊形分類問題中多邊形特征多樣、種類繁多，是線性不可分問題，即找不到一條直線將幾種特征很好地分類。因此，需要采用非線性問題的研究方法(核函數(shù)kernel)進行多特征分類問題的研究，即求解超平面(hyperplane)[5]。其改進算法[6]，如Soft Margin SVM，具有一定的容錯能力。

針對n維空間點x，在樣本空間中，超平面可通過線性方程描述為

wTx+b=0

其中：w=(w1，w2，…，wd)為超平面的法向量，決定超平面的方向；b為位移項，決定超平面與n維空間中原點之間的距離。將超平面記為(w,b)，因此n維樣本空間中任一點x到超平面(w,b)的距離[7]為

給定樣本數(shù)據(jù)集D={(x1,y1),(x2,y2),…,(xm,ym)},yi∈{+1,-1}，以進行分類，假設(shè)超平面能將樣本空間的點正確分類，即對于任意(xm,ym)∈D，合并起來為

利用優(yōu)化方法將問題轉(zhuǎn)化為等價問題，代入核函數(shù)求解。常用的核函數(shù)有多項式核函數(shù)、徑向基(高斯)核函數(shù)(Radial Basis Function，RBF)、多層感知器核函數(shù)等。文中采用RBF核函數(shù)，它對非線性特性、高維數(shù)據(jù)有較好的適應(yīng)性。其數(shù)學(xué)表達式[8]如下：

2 基于SVM進行特征分類過程建模

2.1 樣本特征選取

采用SVM方法建模，首先要解決樣本特征選取問題。針對多邊形幾何特征的分類并沒有一個統(tǒng)一的方法，而文中所提出的問題同時屬于應(yīng)用于增材制造的填充問題，只能靠經(jīng)驗來選取樣本特征。在填充過程中，影響填充質(zhì)量的因素有很多，從填充精度和效率來看，填充材料、溫度、搭接率、填充路徑等因素都會造成影響。相對而言，增材制造的填充精度要求比較低，沒有減材制造如數(shù)控加工要求那么苛刻，只關(guān)注影響填充質(zhì)量的主要因素而合理忽略次要因素也可以保證加工質(zhì)量。

實驗發(fā)現(xiàn)，針對根據(jù)填充路徑確定多邊形輪廓分類的問題，圓形度、面積/周長比、銳角比例對分類的影響十分明顯。其中，圓形度可以確定多邊形是否足夠圓潤，數(shù)值越大，則多邊形越接近圓形；銳角比例用于輔助判斷圖形的圓潤程度，若銳角比例大，則圖形必然存在較多的尖銳轉(zhuǎn)角，影響生產(chǎn)的螺旋軌跡質(zhì)量，銳角比例越小圓潤程度越好；面積與周長之比用于確定多邊形是否適宜采用直骨架方式填充，若圖形各處的粗細越均勻、一致，則越適宜采用直骨架方法進行填充。因此，本文作者選取圓形度、面積/周長比、銳角比例作為樣本特征，綜合考慮3個因素對圖形特征分類的影響。

2.2 模型訓(xùn)練過程中的參數(shù)選擇

基于SVM的建模過程成功與否，很大程度上依賴于所選擇的參數(shù)是否合適。相關(guān)的參數(shù)主要有：懲罰系數(shù)C、RBF核函數(shù)中的δ、不敏感損失函數(shù)中的ε[9]。懲罰系數(shù)C表示對經(jīng)驗誤差的懲罰，它的作用是在置信范圍與經(jīng)驗誤差之間取一個折中，C值過大會導(dǎo)致過學(xué)習(xí)，C值過小會導(dǎo)致欠學(xué)習(xí)。核參數(shù)δ表示核的寬度，主要影響樣本數(shù)據(jù)在高維特征空間中的分布。不敏感損失函數(shù)中的參數(shù)ε決定了支持向量的數(shù)目，ε越小，則支持向量的數(shù)目越多，函數(shù)估計的精度越高，但訓(xùn)練的時間也越長。

通常使用網(wǎng)格搜索和交叉驗證的方法尋找最優(yōu)參數(shù)。首先，根據(jù)經(jīng)驗確定參數(shù)的初始取值；然后，用2倍的指數(shù)方式漸次增大或減小參數(shù)值，如將樣本數(shù)據(jù)分為5份(即5折法)，依次選取其中的4份用于訓(xùn)練，剩余的1份用于測試。比較不同參數(shù)下模型的預(yù)測誤差，選取誤差最小的一組作為模型參數(shù)。

3 輪廓分類實驗與建模結(jié)果分析

3.1 實驗數(shù)據(jù)采集過程

對若干個模型進行切片求解，再對其中的多邊形進行人工分類，獲得模型訓(xùn)練與測試所需的樣本數(shù)據(jù)。具體方法：因采用相對簡單的模型容易造成樣本數(shù)據(jù)重復(fù)或過于近似，實驗中選擇的模型均為復(fù)雜模型；在切片計算后，對切片多邊形進行采樣，人工選取特征明顯的、典型的多邊形進行歸類，如：對可能由CPO進行填充也適用于雙螺旋軌跡填充的多邊形，不建議選取；對適用于CPO、雙螺旋及直骨架填充的路徑進行多邊形歸類，每個種類的多邊形應(yīng)盡量多、形狀應(yīng)盡量豐富。然后，重復(fù)上述過程，對數(shù)個模型進行切片再對多邊形進行人工分類。

采樣實驗中，圓形度、面積/周長比、銳角比例的取值應(yīng)滿足一定分布，以保證在所限定的范圍內(nèi)都有實驗數(shù)據(jù)分布?；趯嶋H可能的取值，此處設(shè)定的圓形度為0～1、面積/周長比為0～0.5、銳角比例為0～1。根據(jù)三者的不同組合，進行多組實驗，部分數(shù)據(jù)如表1所示。

表1 部分實驗數(shù)據(jù)

3.2 建模結(jié)果與數(shù)據(jù)分析

分別對圓形度、面積/周長比、銳角比例繪制Receiver Operating Characteristic(ROC)曲線[10]，根據(jù)學(xué)習(xí)的結(jié)果對樣例進行排序，按此順序逐個把樣本作為正例進行預(yù)測，每次計算出2個重要值，分別作為橫縱坐標。圖3所示為ROC曲線，可見利用本文作者所選定的3個樣本特征可以有效將樣本分類，驗證了所選樣本特征的合理性。

圖3 ROC曲線

使用LibSVM庫[11]對第3.1節(jié)中所獲得的數(shù)據(jù)進行建模。以多邊形的圓形度、面積/周長比、銳角比例為模型輸入量，以分類為模型輸出。訓(xùn)練所采用的參數(shù)分別為C=76、δ=0.777 8、ε=0.004 2。為驗證SVM建模方法的通用性與穩(wěn)定性，共進行20次實驗。每次實驗從樣本數(shù)據(jù)中隨機抽取16次用作訓(xùn)練、4次用作測試。使用最小均方誤差(Minimum Square Error，MSE)和平均絕對百分比誤差(Mean Absolute Percentage Error，MAPE)2個指標對預(yù)測結(jié)果進行評價。實驗結(jié)果如表2所示。

表2 模型訓(xùn)練與預(yù)測結(jié)果

由表2可以看到:該方法的迭代次數(shù)較少、耗時較少、穩(wěn)定性較強，對不同的訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)均能獲得很好的效果。從10次實驗的平均結(jié)果來看，磨削量預(yù)測的MSE僅為2.95×10-4、MAPE僅為8.52%。若以MAPE作為評價指標，模型的預(yù)測精度在90%以上。

4 填充路徑仿真分析

4.1 輪廓分類

在此節(jié)中，提供幾種適用于3種路徑的輪廓多邊形，均由文中前述算法分析獲得。適合不同路徑的多邊形輪廓如圖4所示。

圖4 適合不同路徑的多邊形輪廓

可見，各分類的多邊形均可以按照對應(yīng)的適應(yīng)軌跡進行規(guī)劃。利用本文作者提出的方案可將復(fù)雜多邊形進行分類。

4.2 輪廓填充示例

應(yīng)用前文所提的填充算法CPO、雙螺旋路徑[1]及直骨架路徑[2]，結(jié)合文中所提的分類方法，對下列已分類的多邊形進行填充，圖5所示為填充示例。

圖5 多邊形分類及對應(yīng)填充路徑

可見，各類型的多邊形均可以按照對應(yīng)的適應(yīng)軌跡進行規(guī)劃。所提方案成功地將分類后的多邊形按照設(shè)定的路徑進行了填充。

5 結(jié)論

本文作者提出了一種基于SVM的填充輪廓分類方案，研究了對輪廓特征提取影響較大的幾個因素(圓形度、面積/周長比、銳角比例)，并以它們作為模型輸入，以分類結(jié)果作為輸出，利用人工實際分類切片的樣本數(shù)據(jù)，建立分類模型。結(jié)果驗證了該方法的有效性，分類的預(yù)測精度基本滿足工業(yè)加工要求。