最小二乘支持向量機(jī)的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法

楊永強(qiáng), 李淑紅

(河南財(cái)經(jīng)政法大學(xué) 計(jì)算機(jī)與信息工程學(xué)院, 鄭州 450002)

點(diǎn)云處理技術(shù)在逆向工程、 精密制造、 數(shù)字化文物、 機(jī)械設(shè)計(jì)等領(lǐng)域應(yīng)用廣泛[1-2]. 在點(diǎn)云數(shù)據(jù)采集過程中, 由于技術(shù)條件限制及外界因素的影響, 不可避免會出現(xiàn)點(diǎn)云數(shù)據(jù)缺失現(xiàn)象, 出現(xiàn)一些孔洞, 對后續(xù)點(diǎn)云數(shù)據(jù)建模過程產(chǎn)生不利影響. 因此, 為了保證模型的完整性, 在進(jìn)行點(diǎn)云數(shù)據(jù)建模前, 首先要實(shí)現(xiàn)孔洞修補(bǔ)[3].

目前, 已有許多點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法[4-5], 傳統(tǒng)點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法主要分為兩類： 基于體積元素的算法和基于三角網(wǎng)絡(luò)的算法. 其中基于體積元素的算法采用體積元素描述物體修補(bǔ)模型, 如: 文獻(xiàn)[6]提出了基于體積離散的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法, 可有效修補(bǔ)有島嶼面片的物體模型, 但易改變物體模型的結(jié)構(gòu)； 文獻(xiàn)[7]提出了基于空間雕刻與等值面相融合的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法； 文獻(xiàn)[8]提出了基于最小切割算法的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法, 通過估計(jì)物體模型內(nèi)部和外部邊界實(shí)現(xiàn)復(fù)雜物體模型的修補(bǔ). 基于三角網(wǎng)格的算法采用三角網(wǎng)格描述物體修補(bǔ)模型, 如: 文獻(xiàn)[9]提出了基于Poisson方程重構(gòu)的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法； 文獻(xiàn)[10]提出了基于差分進(jìn)化理論的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法; 文獻(xiàn)[11]提出了基于徑向基函數(shù)(RBF)的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法; 文獻(xiàn)[12]提出了基于移動最小二乘法的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法. 當(dāng)點(diǎn)云數(shù)據(jù)分布均勻, 且數(shù)據(jù)規(guī)模較小時, 該類算法可得到理想的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)效果, 但當(dāng)數(shù)據(jù)規(guī)模較大時, 修補(bǔ)過程費(fèi)時, 很難取得好的修補(bǔ)效果. 將神經(jīng)網(wǎng)絡(luò)、 支持向量機(jī)應(yīng)用于點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)中, 通過其自適應(yīng)、 自組織學(xué)習(xí)能力, 實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的輪廓構(gòu)建與曲面擬合, 其云數(shù)據(jù)孔洞修補(bǔ)效果優(yōu)于傳統(tǒng)算法[13]. 但在實(shí)際應(yīng)用中, 神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)復(fù)雜, 收斂速度慢, 易產(chǎn)生局部極小值, 支持向量機(jī)的訓(xùn)練時間較長, 不能滿足點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)實(shí)時性的要求. 最小二乘支持向量機(jī)(least square support vector machine, LSSVM)[14]對標(biāo)準(zhǔn)支持向量機(jī)進(jìn)行簡化, 克服了神經(jīng)網(wǎng)絡(luò)易產(chǎn)生局部極小值的缺陷, 且具有支持向量機(jī)良好的泛化能力, 為點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)提供了一種新技術(shù).

為了獲得理想的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)結(jié)果, 本文提出一種基于最小二乘支持向量機(jī)的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法. 首先根據(jù)散亂點(diǎn)云邊界估計(jì)孔洞修補(bǔ)范圍, 然后根據(jù)孔洞及周圍點(diǎn)的信息, 采用最小二乘支持向量機(jī)建立曲面, 實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的孔洞修補(bǔ), 最后通過仿真實(shí)驗(yàn)驗(yàn)證本文算法的有效性. 結(jié)果表明, 最小二乘支持向量機(jī)能有效修補(bǔ)各種復(fù)雜的孔洞, 具有一定的實(shí)際應(yīng)用價值.

1 最小二乘支持向量機(jī)

標(biāo)準(zhǔn)支持向量機(jī)采用不等式約束, 訓(xùn)練過程較復(fù)雜, 耗時較長, 且待確定參數(shù)較多, 因此無法應(yīng)用于大規(guī)模云數(shù)據(jù)孔洞修補(bǔ)中. 而最小二乘支持向量機(jī)把不等式約束變?yōu)榈仁郊s束, 加快了訓(xùn)練速度, 簡化了參數(shù)優(yōu)化, 可更好地滿足大規(guī)模云數(shù)據(jù)孔洞修補(bǔ)的要求. 設(shè)訓(xùn)練集為{(xi,yi)},i=1,2,…,k,xi∈n,yi∈,xi和yi分別為輸入向量和期望輸出, 采用函數(shù)φ(·)對原始訓(xùn)練集進(jìn)行映射, 得到LSSVM的回歸方程為

f(x)=wTφ(x)+b,

(1)

其中w和b分別表示權(quán)值和偏置. 基于結(jié)構(gòu)風(fēng)險最小化原理, 式(1)等價于

(2)

其中:γ為正則化參數(shù)；ei為回歸誤差.

為了簡化LSSVM學(xué)習(xí)的過程, 提高學(xué)習(xí)效率, 引入Lagrange乘子αi對式(2)進(jìn)行轉(zhuǎn)換, 得到其對偶空間優(yōu)化模型為

(3)

(4)

對于非線性問題, 通過引入核函數(shù)K(xi,xj)=φ(xi)Tφ(xj)得到LSSVM的回歸函數(shù)為

(5)

采用RBF構(gòu)建LSSVM, 其定義為

(6)

式中σ為寬度參數(shù). 基于RBF函數(shù)的LSSVM回歸函數(shù)為

(7)

在LSSVM建模過程中, 參數(shù)γ和σ直接影響回歸結(jié)果的優(yōu)劣, 因此通常要進(jìn)行最優(yōu)參數(shù)的確定, 參數(shù)σ的變化范圍定義為

k1dmin=σl<σ<σu=k2dmax,

(8)

其中dmin和dmax分別為訓(xùn)練集的最小和最大距離. 若σl太小則將導(dǎo)致過擬合, 若σu太大則覆蓋范圍較大, 學(xué)習(xí)復(fù)雜程度較高, 本文設(shè)σ參數(shù)取值范圍為[0.001,1 000], 采用粒子群算法[15]按圖1所示流程確定參數(shù)γ和σ.

圖1 LSSVM參數(shù)的確定流程Fig.1 Determination procedure of LSSVM parameters

2 改進(jìn)算法

2.1 檢測孔洞 在點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)過程中, 首先進(jìn)行孔洞檢測. 孔洞檢測結(jié)果的優(yōu)劣直接影響后續(xù)孔洞修補(bǔ)效果, 是孔洞修補(bǔ)的基礎(chǔ), 步驟如下：

1) 根據(jù)點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)問題, 在點(diǎn)云數(shù)據(jù)孔洞邊緣上選擇多個數(shù)據(jù)點(diǎn)；

2) 根據(jù)這些點(diǎn)云數(shù)據(jù)點(diǎn)擬合曲線邊界的控制頂點(diǎn), 得到邊界曲線；

3) 對產(chǎn)生的新曲線, 在其邊界重新采樣, 即可得到點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)的新增點(diǎn)；

4) 根據(jù)原邊界點(diǎn)與新增采樣點(diǎn), 得到孔洞邊界, 實(shí)現(xiàn)孔洞的檢測.

2.2 估計(jì)孔洞鄰近域 孔洞及其附近的幾何信息共同組成了點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)的孔洞鄰近域, 而附近幾何信息可根據(jù)鄰近域的半徑進(jìn)行選擇, 設(shè)孔洞所在面與鄰近域內(nèi)各點(diǎn)P1,P2,…,Pn的平方和最小, 則表示該面為特征面, 能用空間點(diǎn)O和單位法向量n描述, 從而有

(9)

若點(diǎn)云數(shù)據(jù)的某一孔洞鄰近域?yàn)镻1,P2,…,Pn, 設(shè)d(Pi,O)≥d(Pj,O), 則近域的最遠(yuǎn)數(shù)據(jù)點(diǎn)為Pd,d(x,y)為x和y兩點(diǎn)之間的距離,O為原點(diǎn), (Pd-O)×n,n×((Pd-O)×n),n分別為u軸、v軸、s軸, 其共同組成一個孔洞坐標(biāo)系, 其中uv位于同一個平面上,v軸表示孔洞較狹小的方向.

(10)

因此可通過LSSVM實(shí)現(xiàn)曲面擬合, 步驟如下：

1) 給定樣本集T, 確定LSSVM核函數(shù)及參數(shù), 參數(shù)采用粒子群優(yōu)化算法確定;

2) 構(gòu)造并求解最優(yōu)問題, 得到其解為

(11)

(12)

4) 構(gòu)造曲面擬合函數(shù)為

(13)

3 點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法的性能測試與分析

為了分析點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法的效果, 采用測試平臺： Intel Core i7 6800K(3.4 GHz/L3 15M)的處理機(jī), 技嘉X99-Phoenix SLI主板, 32 GB DDR4的內(nèi)存, NVIDIA GeForce GTX 1070的顯卡, 256 GB的SDD硬盤, 內(nèi)置10-100-1000M網(wǎng)卡, Windows10的操作系統(tǒng). 用標(biāo)準(zhǔn)C++語言和OpenGL圖形編程接口實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法, 實(shí)驗(yàn)對象為花瓶和兔子, 本文算法首先提取散亂點(diǎn)云邊界, 然后對點(diǎn)云數(shù)據(jù)孔洞進(jìn)行修補(bǔ), 實(shí)驗(yàn)結(jié)果如圖2所示.

圖2 點(diǎn)云數(shù)據(jù)修補(bǔ)結(jié)果Fig.2 Results of point cloud data repairing

為了進(jìn)一步測試本文算法的優(yōu)越性, 選擇文獻(xiàn)[7]、 文獻(xiàn)[8]和文獻(xiàn)[10]的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法進(jìn)行對比實(shí)驗(yàn), 對比結(jié)果列于表1. 由表1可見, 相對于對比算法, 本文算法的孔洞修補(bǔ)成功率大幅度提高, 且修補(bǔ)耗費(fèi)時間也有所下降, 加快了點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)的速度, 獲得了更理想的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)效果.

表1 不同點(diǎn)云數(shù)據(jù)修補(bǔ)算法的性能對比

綜上所述, 本文針對當(dāng)前點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法耗時長、 修補(bǔ)效果不理想的問題, 提出了一種基于最小二乘支持向量機(jī)的點(diǎn)云數(shù)據(jù)孔洞修補(bǔ)算法, 充分利用孔洞邊界點(diǎn)和鄰域信息, 采用最小二乘支持向量機(jī)建立曲面函數(shù), 實(shí)現(xiàn)孔洞修補(bǔ)點(diǎn)與原始點(diǎn)云的平滑過渡, 獲得了理想的修補(bǔ)效果.