基于LSSVM-NSGA-II的橋梁鋼構件三維激光掃描方案優化

吳賢國，鄧婷婷，黃金龍，王洪濤，王堃宇，陳虹宇，李鐵軍

(1. 華中科技大學 土木與水利工程學院， 湖北 武漢 430074； 2. 中建三局集團有限公司， 湖北 武漢 430000；3. 南洋理工大學 土木工程與環境學院， 新加坡 639798； 4. 中國交通建設集團有限公司， 北京 100088)

由于三維激光掃描系統的精度高，在工程項目中得到了越來越多的使用，其中在獲取構件空間點云數據的應用尤為廣泛。而在三維激光掃描過程中，三維激光掃描參數的設置會直接對掃描精度帶來很大的影響，因此，通過調節三維激光掃描參數降低掃描誤差的研究是十分有價值的。

近些年來，為了獲得較優的參數值，國內外學者進行了大量的研究，于志亮等[3]提出粗瞄與精瞄結合的螺旋-正弦復合方法，并基于線性優化對參數進行設置；楊書哲[4]等利用三維激光掃描技術通過對三維點云數據的獲取及處理，以快速且精準度超高的線性方式直接獲取物體表面的空間三維坐標；賈冰等[5]提出基于激光脈沖掃描測量體制下的高速點目標捕獲、跟蹤測量方法，基于時間序列法的捕獲方法，優化最佳捕獲次數。蔡軍等[6]設計了由高精度旋轉云臺和小型二維激光測距傳感器組成的三維激光掃描系統，并根據非線性最小二乘法對三維激光掃描系統的參數進行優化計算；宗文鵬等[7]提出了以優化點云數據中平面的平面度和平面面積為目標的內參數標定方法，并通過提出的單純形和人工蜂群混合優化算法(Nelder-Mead Simplex and Artificial Bee Colony，NMS-ABC)進行參數解算，實現內參數標定；韓光瞬等[8]介紹了三維激光掃描系統的測量原理、測樹過程和測樹因子的獲取方法，在甘肅省小隴山林業局黨川林場，利用樣木三維模型理論及方法；韓嘯等[9]提出了非線性攝像機成像模型，在對標定圖像進行預處理之后，給出了一種快速、準確的角點提取算法；Pathak等[10]采用偏好選擇指數和元啟發式方法來確定掃描過程參數的最佳值，并使用PSI(Purchase Sales Inventory)方法探索的多標準決策(Multi-Criteria Decision-Making，MCDM)技術；Li等[11]為了估計三維激光掃描儀的測量模型參數，提出了結合入侵雜草優化(Invasive Weed Optimization，IWO)和LM(Levenberg-Marquardt)算法的空間球面標定方法，建立了三維激光掃描儀標定的目標函數。

以往的研究均對三維激光掃描參數優化有一定程度的幫助，但是沒有更加精準地表示出相對誤差和三維激光掃描參數之間的復雜關系，所以在優化上可能存在較大誤差。針對此問題，本文將提出基于三維激光掃描參數的LSSVM-NSGA-II(Least Squares Support Vector Machines and Non-dominated Sorting Genetic Algorithm)優化模型，利用最小二乘支持向量機對相對誤差和掃描時間進行預測，以預測非線性函數作為適應度函數，利用遺傳算法進行優化，在實現相對誤差的基礎上獲得各個三維激光掃描參數的取值，從而實現精準、有效快速的鋼構件拼裝。

1 理論基礎

1.1 最小二乘支持向量機基本原理

支持向量機(Support Vector Machines，SVM)作為一種智能算法，可以很好地克服非線性問題，具有全局性且適用于小樣本[12]。利用最小二乘支持向量機預測耐久性，即利用核函數學習輸入指標與輸出指標之間的規律進而做出決策的過程。

(1)

式中：α，α*為Lagrange乘數；K(xi，x)為核函數；b為對xi賦予權重乘積后所發生的偏置數。為了降低支持向量機的計算量，提出最小二乘法的支持向量機模型，LSSVM最大的優勢就是采用平方和誤差代替原本的損失函數，損失函數φ(w)如下：

(2)

同時損失函數應該滿足的約束條件為：

yi=wTφ(xi)+b+ei

(3)

式中：γ為LSSVM的懲罰參數；ei為LSSVM的誤差變量；φ(xi)為從x到內積特征空間的映射；w為xi的權重系數向量。引入拉格朗日乘子，則表達形式轉化為：

(4)

通過對式(4)進行等式求導后可以得到以下方程組：

(5)

求解上述方程組可以得到LSSVM參數(αi，ei，w，b)。最后可得LSSVM的非線性回歸模型為：

(6)

式中：核函數K(x,xi)用來代替高維空間上的內積運算；xi為核函數的中心；x為訓練樣本的輸入值；yi為樣本的輸出;N為樣本數量。

1.2 遺傳算法基本原理

遺傳算法是一種基于達爾文進化理論的智能優化算法[13]，2002年，Deb等在原遺傳算法的基礎上提出帶精英策略的非支配排序遺傳算法(NSGA-II)。改進后的遺傳算法最大特點是快速非支配排序和擁擠距離。

傳統的遺傳算法的非支配排序是O(MN3)(M為目標數，N為種群大小)，經過改進之后，NSGA-II算法的的非支配排序是O(MN2)，提升了種群的排列速度，所以稱為快速非支配排序。

在進行擁擠距離計算時，對種群升序排序，將第一個、最后一個擁擠距離設置為無窮大，用擁擠距離法就可以計算每個解的距離，其中第i個解的擁擠距離計算如下：

(7)

1.3 基于LSSVM-NSGA-II的目標優化算法構建

本文為了全局地考慮所有方案且提高參數優化的準確度，可以先利用數據挖掘中最小二乘支持向量機算法探究不同參數與優化目標之間的關系，以達到擬合目標函數的目的，繼而利用遺傳算法進行參數優化，主要步驟分為：(1)利用最小二乘支持向量機回歸擬合標定參數之間的函數關系；(2)利用遺傳算法對各個標定參數進行優化。LSSVM-NSGA-II流程圖如下：

圖1 基于LSSVM-NSGA-II三維激光掃描多目標優化流程

1.3.1 基于LSSVM三維激光掃描相對誤差預測

Step 1：數據獲取及預處理

本研究可以選取項目上一個某掃描構件作為實驗對象，所涉及的三維激光掃描參數為：水平入射角度、傾斜角度、點云密度、測量距離、分辨率以及能見度，利用試驗數據進行三維激光掃描，并計算相對誤差和確定掃描時間，從而得到足夠數量的樣本數據。

數據預處理主要是對數據進行歸一化，避免樣本出現數據過大或過小的情況，導致數據被淹沒或不收斂[14]。本文將利用式(8)將輸入變量和輸出統一到[-1,1]區間，實現數據歸一化，使得每個特征在預測過程中起到效果。

(8)

式中：y為歸一化之后的標準值；ymax，ymin分別默認為1和-1；x為樣本值；xmax，xmin分別為樣本值的最大值和最小值。

Step 2：核函數參數優化

核函數對最小二乘支持向量機預測精度有很大的影響。在不同預測模型中，應根據研究特點選擇合適的核函數[15]。由于高斯核函數既有徑向基核函數的優勢，還有良好的抗干擾能力，本文將采用高斯核函數當作預測模型的核函數進行研究，其表達式為：

(9)

式中：xi為輸入變量；x為輸出變量。

在確定核函數后，為了確保LSSVM的泛化水平，本文將采用K折交叉驗證，進行網格搜索對核函數寬度參數g和懲罰系數c進行優化。其中，網格搜索法是一種全局搜索法，在避免局部最優的同時節約時間[16]；K折交叉驗證常用于LSSVM模型性能的驗證，可以保證LSSVM模型良好的學習狀態。

Step 3：預測結果分析

為了驗證LSSVM模型的預測精度，通過兩個模型性能的指標均方根誤差RMSE和擬合優度R2來進行檢驗。均方根誤差RMSE表示預測值與真實值之間的離散程度，擬合優度R2表示預測值與真實值之間的擬合效果，兩個指標分別由式(10)(11)得出：

(10)

(11)

1.3.2 NSGA-Ⅱ多目標優化

Step 1：建立目標函數

引入LSSVM三維激光掃描相對誤差和掃描時間回歸預測算法替代傳統數學函數作為多目標遺傳算法中的適應度函數，從而表示輸入變量與輸出目標之間存在復雜非線性關系，三維激光掃描相對誤差和掃描時間回歸函數ming1和ming2表示為：

ming1(lssvm(x1,x2,…,xn))

(12)

ming2(lssvm(x1,x2,…,xn))

(13)

Step 2：建立目標約束條件

為了使得生成的方案更加合理可行，需要對方案生成時的各個因素設定限制范圍，形成變量的約束條件，約束條件的一般形式如下：

ail

(14)

式中：xi為第i個設計參數；ail，aiu分別為第i個設計參數值的下限和上限。

Step 3：NSGA-Ⅱ多目標優化

當目標函數和約束條件都確定下來之后，便可基于NSGA-II算法實現多個目標優化，可以找到基于掃描參數的三維激光掃描相對誤差的Pareto最優解集。NSGA-II算法與傳統遺傳算法相比，關鍵不同步驟主要有兩個：

(1)在設置初始種群后，NSGA-II算法將通過快速非支配排序后，利用三個遺傳機制：選擇、交叉、變異后獲得首批子代種群。

(2)在第二代種群進化后進行父、子代合并，通過快速非支配排序之后計算個體之間擁擠度，根據非支配關系和個體間擁擠距離確定新種群，通過三個遺傳機制產生新的子代種群。

2 實例分析

2.1 項目背景

我國北方某段高速公路建設項目某一標段主線全長約206 km，在進行項目橋梁鋼構件加工和拼裝過程中，采用三維激光掃描技術獲取構件點云數據，所選擇的三維激光掃描儀器是Leica Scan Station P30/40掃描儀，這種型號的掃描儀測角精度8″，測距精度1.2 mm±10 ppm，掃描速度可達1000000點/s，標靶獲取精度2 mm@50 m。其中三維激光掃描現場如圖2所示，現場鋼構件測量標記如圖3所示。

圖2 三維激光掃描現場

圖3 現場鋼構件測量標記

2.2 最小二乘支持向量機預測2.2.1 數據獲取及歸一化

在三維激光掃描過程中，為了探究掃描參數與相對誤差以及掃描時間的關系，選取相對誤差和掃描時間作為LSSVM預測模型的輸出指標。水平入射角度、傾斜角度、點云密度、測量距離、分辨率以及能見度六個對測量誤差有較大影響的三維激光掃描參數作為輸入指標。通過現場實驗，收集一共100組樣本數據如表1所示，其中點云模型實驗圖如圖4所示，隨機抽取80組樣本構成訓練集，剩下的20組樣本作為測試集。通過式(8)對輸入和輸出特征指標進行歸一化處理。

圖4 點云實驗圖像

表1 輸入和輸出指標樣本數據

2.2.2 核函數參數優化

根據1.3節的分析，選擇5折交叉驗證法和網格搜索法對LSSVM模型的核函數寬度參數g和懲罰系數c進行選優，分別得到相對誤差和掃描時間核函數最優參數，圖5，6分別為相對誤差、掃描時間預測參數優化結果3D視圖。

圖5 相對誤差參數優化3D視圖

圖6 掃描時間參數優化3D視圖

2.2.3 預測結果分析

從圖5中可知，懲罰系數bestc=1，核函數參數bestg=3.0314，此時均方根誤差CVmse=0.0018012。表示c=1，g=3.0314，在5-CV驗證后的均方誤差值最小。

同樣，從圖6中可知，懲罰系數bestc=48.5029，核函數參數bestg=0.57435，此時均方根誤差CVmse=0.00029359。表示c=48.5029，g=0.57435，在5-CV驗證后的均方誤差值最小。

基于LSSVM核函數參數優化的結果，利用訓練集進行學習，分別建立LSSVM相對誤差預測模型和掃描時間預測模型，再利用測試集檢驗訓練集的預測模型。根據上述步驟，相對誤差訓練集預測結果如圖7a，測試集預測結果如圖7b；同理掃描時間訓練集預測結果如圖8a，測試集預測結果如圖8b。

圖7 相對誤差預測結果

圖8 掃描時間預測結果

從圖7能夠發現，LSSVM模型能夠很好地預測相對誤差的變化。圖7a為相對誤差訓練集預測模型，均方根誤差為0.00277，擬合優度為0.9777，可以看出該模型擬合結果很好，其預測值與實際值之間誤差非常小。圖7b為SVM模型對訓練集預測回歸函數的檢驗，其中均方根誤差為0.000234，擬合優度為0.996，相對誤差的支持向量機預測模型對測試集樣本的預測值與試驗值十分接近。以上數據說明該模型對相對誤差預測具有良好的精度且具有出色的泛化能力。

同樣從圖8中可以看出LSSVM預測模型對掃描時間預測也具有良好的精度。

為了進一步驗證利用LSSVM對三維激光掃描的高精度性，將LSSVM模型的預測效果與SVM、BP人工神經網絡以及小波神經網絡三個預測模型的預測精度及誤差進行對比分析，對比結果如表2，3所示。

根據預測精度及誤差分析對比表可得：

表2 相對誤差預測模型精度及誤差對比

表3 掃描時間預測模型精度及誤差對比

無論是對三維激光掃描的相對誤差還是對掃描時間進行預測，LSSVM預測模型與SVM模型、BP人工神經網絡以及小波神經網絡預測模型相比，模型的均方根誤差都是最低的，同時模型的擬合優度是最高的。因此，利用LSSVM預測模型對三維激光掃描的相對誤差以及掃描時間進行預測所得的結果是可靠精準的。

2.3 基于LSSVM-NSGA-II算法三維激光掃描多目標優化

2.3.1 建立目標函數

在實際三維激光掃描過程中，掃描精度是首要考慮的目標之一，除此之外，為了可以在保證精度的基礎上提高測量效率，需要減少掃描時間。因此，本研究將以掃描相對誤差以及掃描時間為考慮對象，同時進行多目標優化。

(1)基于LSSVM相對誤差目標函數

根據上述式(12)(13),可得相對誤差和掃描時間的目標函數：ming1(lssvm(x1,x2,…,x6))，ming2(lssvm(x1,x2,…,x6))。其中，x1,x2,x3,x4,x5,x6分別為水平入射角度、傾斜角度、點云密度、測量距離、分辨率以及能見度。

2.3.2 建立多目標約束范圍

根據規范以及工程實際等要求確定合理的三維激光掃描參數取值范圍，根據式(14)確定優化的約束條件：

2.3.3 基于NSGA-Ⅱ的多目標優化

在三維激光掃描相對誤差和掃描時間的目標函數以及掃描參數約束范圍后，基于NSGA-Ⅱ進行多目標優化。本文取NSGA-Ⅱ算法的交叉算子為0.8，變異算子為0.02，種群大小為40，最大進化代數和停止代數為60，利用NSGA-Ⅱ算法進行全局尋優，迭代60次后得到最優配比組合，如圖9所示。

圖9 最優Pareto前沿

由圖9可知，隨著相對誤差的減少，三維激光掃描的掃描時間增長。由于項目對構件的要求比較高，因此要求三維激光掃描的相對誤差不能大于3.5 mm。由最優Pareto前沿可得當三維激光掃描的相對誤差不大于3.5 mm時，最短的掃描時間為335.944 s，此時相對誤差為2.93 mm，水平入射角度、傾斜角度、點云密度、測量距離、分辨率以及能見度分別對應的參數解為89.79°，89.77°，3.29 mm，3 m，0.456，8.67 km。根據項目實際情況，將水平入射角度、傾斜角度和點云密度均取整數，則分別為90°，90°，3.2 mm。利用優化得出的三維激光掃描參數值對掃描儀進行調整，所得點云圖像如圖10所示，可以看出圖像清晰度處于良好水平。

圖10 優化后的點云圖像

3 結 論

本文建立了一種基于LSSVM-NSGA-II的優化模型，首先以相對誤差和掃描時間為研究對象，基于三維激光掃描參數進行試驗獲取100組樣本數據集，然后進行LSSVM實現高精度預測，并將預測函數作為適應度函數，結合規范及工程項目的要求，利用NSGA-II算法進行目標優化，在滿足相對誤差最低的條件下，得到最優三維激光掃描參數。

(1)選取水平入射角度、傾斜角度、點云密度、測量距離、分辨率以及能見度等6個因素作為最優輸入變量集構建基于LSSVM預測三維激光掃描精度模型，預測結果表明基于采用LSSVM算法對相對誤差和掃描時間進行預測的精度很高。其中，在對相對誤差進行預測時，均方根誤差為0.000234，擬合優度為0.996；在對掃描時間進行預測時，均方根誤差為0.0012，擬合優度為0.9971。說明了LSSVM模型在三維激光掃描誤差分析預測中的可行性以及有效性。

(2)由于基于最小二乘支持向量機預測的效果良好，可將LSSVM回歸預測函數作為目標適應度函數，對相對誤差和掃描時間進行NSGA-II算法優化后，在滿足相對誤差達到2.93 mm的基礎上，最短的掃描時間為335.944 s，此時相對誤差為2.93 mm，水平入射角度、傾斜角度、點云密度、測量距離、分辨率以及能見度分別對應的參數解為90°，90°，3.2 mm，3 m，0.456，8.67 km。結果表明，這是一種智能、精確、高效的參數優化方法，在三維激光掃描中具有非常好的應用價值，達到了保證鋼構件加工尺寸的準確性。