楊永強, 李淑紅

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

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

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

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

1 最小二乘支持向量機

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

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

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

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

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

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

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

(9)

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

(10)

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

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

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

(11)

(12)

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

(13)

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

為了分析點云數(shù)據(jù)孔洞修補算法的效果, 采用測試平臺： Intel Core i7 6800K(3.4 GHz/L3 15M)的處理機, 技嘉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圖形編程接口實現(xiàn)點云數(shù)據(jù)孔洞修補算法, 實驗對象為花瓶和兔子, 本文算法首先提取散亂點云邊界, 然后對點云數(shù)據(jù)孔洞進行修補, 實驗結(jié)果如圖2所示.

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

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

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

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