改進(jìn)蟻群算法的三維激光點(diǎn)云聚類方法

江　珊，呂京國，李現(xiàn)虎

(北京建筑大學(xué)測繪與城市空間信息學(xué)院，北京 102616)

近年來，點(diǎn)云分割方面取得了很多成果。Herman Gross[1]采用從點(diǎn)云中提取線特征的方法，通過計算最大特征值和特征向量，利用提取的特征線實(shí)現(xiàn)點(diǎn)云的分割，結(jié)果表明線曲率特征適用于流形結(jié)構(gòu)的點(diǎn)云。Bisheng Yang[2]采用移動LiDAR點(diǎn)云利用路面反射率探測路面信息，首先采用內(nèi)插生成具有幾何參照的點(diǎn)云圖像，然后通過反射率強(qiáng)度值分離非地面點(diǎn)，試驗(yàn)表明該算法適用于路面特征的提取。Rostislav Hulik[3]提出了基于三維霍夫變換的連續(xù)平面的點(diǎn)云分割算法，通過對比PCL點(diǎn)云庫的隨機(jī)一致性采樣算法，證明了算法的穩(wěn)健性。

隨著人工智能的發(fā)展，研究者開始關(guān)注群智能算法的點(diǎn)云分割研究。林望[4]提出了基于多維粒子群算法(MD-PSO)的散亂點(diǎn)云非監(jiān)督分類方法，依據(jù)PSO聚類和RANSAC建立了穩(wěn)健的非監(jiān)督平面分割目標(biāo)函數(shù)，為了防止陷入局部最優(yōu)，每一維度改進(jìn)策略的粒子全局最優(yōu)加入到MD-PSO算法中，試驗(yàn)表明對平面分割具有較高的精度。許多研究者利用蟻群算法來解決分割，分類和類似的問題[6-10]。Ni Shihong提出了基于改進(jìn)蟻群算法的連續(xù)空間優(yōu)化方法[11]。蟻群算法在其他領(lǐng)域[12-17]也有許多其他方面的應(yīng)用。

本文的內(nèi)容為：首先，采用改進(jìn)信息素殘留系數(shù)的模型，通過網(wǎng)格劃分連續(xù)區(qū)間變量優(yōu)化投影方向，實(shí)現(xiàn)蟻群優(yōu)化的投影尋蹤點(diǎn)云聚類；然后，評估樹木和建筑數(shù)量及位置的準(zhǔn)確性；最后，基于DUNN指數(shù)對蟻群聚類結(jié)果的有效性進(jìn)行評價。

1　改進(jìn)的蟻群優(yōu)化投影尋蹤聚類算法

從投影時是否需要計算投影密度函數(shù)角度，投影指標(biāo)分為非密度型投影指標(biāo)和密度型投影指標(biāo)。前者最常用的是方差指標(biāo)，后者最常用的是Friedman-Tukey指標(biāo)。本文所選擇的投影指標(biāo)為后者。假定多指標(biāo)樣本集合為

{y(i,j)|i=1,2，…,n；j=1,2，…,m}

式中，n為樣本的個數(shù)；m為指標(biāo)的個數(shù)；y(i,j)為第i個樣本的第j個指標(biāo)值。

首先，進(jìn)行多指標(biāo)樣本集合的預(yù)處理，完成樣本指標(biāo)集合的歸一化工作，達(dá)到消除各指標(biāo)值的量綱和統(tǒng)一各指標(biāo)值的變化范圍的目的。針對樣本集合的歸一化問題，存在兩種可選策略。第一種情況是越大越優(yōu)的指標(biāo)，采用如下歸一化策略：y(i,j)=(y(i,j)-ymin(j))/(ymax(j)-ymin(j))；第二種情況是越小越優(yōu)的指標(biāo)，采用如下歸一化策略：y(i,j)=(ymax(j)-y(i,j))/(ymax(j)-ymin(j))；以上兩式中，ymin(j)、ymax(j)分別為多元指標(biāo)樣本集合中第j個指標(biāo)值的最小值和最大值。

其次，構(gòu)造投影指標(biāo)函數(shù)。假設(shè)a(j)為投影方向向量(單位長度向量)，樣本i以a(j)為投影方向的一維投影值為

(1)

那么優(yōu)化投影方向的依據(jù)就是構(gòu)造投影指標(biāo)函數(shù)Q(a),最佳投影方向就是指標(biāo)達(dá)到極大值時的投影方向。分類策略根據(jù)一維投影序列{z(i)|i=1,2,…,n}的一維散布圖，則優(yōu)化投影要求z(i)的散布應(yīng)滿足：從局部角度上，投影點(diǎn)應(yīng)該盡可能呈密集狀態(tài)，表現(xiàn)為凝聚成若干點(diǎn)團(tuán)；從整體角度上，各個投影點(diǎn)團(tuán)之間盡可能呈散布狀態(tài)。因此投影指標(biāo)函數(shù)可以構(gòu)造為

Q(a)=SzDz

(2)

式中，Sz為一維投影值z(i)的標(biāo)準(zhǔn)差，表示類別之間的散開度；Dz為一維投影值z(i)的局部密度，代表類內(nèi)密集度。公式如下

(3)

式中，E(z)為一維投影序列{z(i)|i=1,2,…,n}的均值；R為數(shù)據(jù)特征的局部密度的窗口半徑，R的取值應(yīng)該滿足兩個條件，一是包含在窗口內(nèi)投影點(diǎn)個數(shù)不能太少，二是抑制Dz隨n增大的幅度，那么R的取值影響投影方向，計算時一般取值為0.1Sz或rmax+m/2≤R≤2m，其中rmax=max[r(i,j)]；rij=|z(i)-z(j)|為點(diǎn)間距值，如果rij≤R，則歸為同一類，否則為不同的類；I(R-rij)為單位階躍函數(shù)，如

(4)

然后，估計最佳投影方向，因?yàn)樗鶚?gòu)造的投影指標(biāo)函數(shù)Q(a)隨投影方向a變化而變化，所以求解投影指標(biāo)函數(shù)的最大值就可以得到最優(yōu)投影方向。求解模型為

(5)

以上數(shù)學(xué)模型是一個以{a(j)|j=1,2,…,m}為優(yōu)化變化的非線性優(yōu)化問題，采用蟻群算法來求解連續(xù)空間的最優(yōu)化問題，與遺傳算法相比效率與性能較高。

最后，進(jìn)行聚類分析；將求解后的最優(yōu)投影方向a*(j)代入一維投影值z(i)的公式為

(6)

計算出各樣本點(diǎn)的投影值z*(i)，并比較z*(i)和z*(i+1)的接近程度，如果二者越接近，那么樣本i和i+1就歸為同一類。

投影尋蹤算法中投影方向的優(yōu)化是一種連續(xù)空間的優(yōu)化問題，其目標(biāo)函數(shù)為非線性問題，那么采用蟻群算法相比傳統(tǒng)的解析法、網(wǎng)格法與遺傳算法，它具有較高的效率和精度，并且對目標(biāo)函數(shù)與約束函數(shù)并無連續(xù)性和偏導(dǎo)數(shù)存在性的要求。依據(jù)現(xiàn)有的關(guān)于蟻群連續(xù)空間優(yōu)化的研究文獻(xiàn)，蟻群算法在連續(xù)空間優(yōu)化的方法一般分為兩種：第一種是信息量函數(shù)分布的蟻群優(yōu)化算法；第二種是簡單連續(xù)優(yōu)化問題的蟻群算法。本文提出改進(jìn)信息素殘留系數(shù)的蟻群算法，優(yōu)化投影尋蹤投影方向，實(shí)現(xiàn)三維點(diǎn)云的最佳聚類。

本文蟻群優(yōu)化投影尋蹤算法過程為：

(1) 針對投影方向中各變量的取值范圍，ajk≤aj≤aij(j=1,2,…,m)，m為樣本的指標(biāo)數(shù)目，采取在變量區(qū)間內(nèi)劃分網(wǎng)格的方法，將變量的取值狀態(tài)映射到空間網(wǎng)格點(diǎn)上，那么螞蟻在各個空間網(wǎng)格點(diǎn)上的移動將依據(jù)各網(wǎng)格點(diǎn)上的目標(biāo)函數(shù)值，并且釋放出不同的信息量，就可以影響下一群螞蟻的移動方向；經(jīng)過一定時間的循環(huán)之后，目標(biāo)函數(shù)值小(或大)的網(wǎng)格點(diǎn)上信息量殘留就比較大，以信息量的大小作為判斷準(zhǔn)則，選擇信息量大的空間網(wǎng)格點(diǎn)，以此來縮小變量的變化區(qū)間，那么蟻群就在此點(diǎn)附近移動；重復(fù)以上過程，直到網(wǎng)格間距小于一定的閾值后(或滿足其他條件)，則投影方向的優(yōu)化過程終止。

(2) 將投影方向aj分為n等份，那么投影方向中m個變量取值的選擇問題就變?yōu)閙級決策問題，每一級存在n+1個節(jié)點(diǎn)，則總計有(n+1)m個節(jié)點(diǎn)。將第1級到第m級所選擇的各節(jié)點(diǎn)連接起來，構(gòu)成解空間中的一個解，見表1。

表1投影狀態(tài)空間的解

從表1可知，投影方向的狀態(tài)為(4,5,3,…,1)，那么其所對應(yīng)的解為

(7)

結(jié)合改進(jìn)的蟻群算法求解投影向量，首先，需要改進(jìn)蟻群連續(xù)空間尋優(yōu)的狀態(tài)轉(zhuǎn)移規(guī)則。假設(shè)每一級設(shè)定1只螞蟻(或更多)，螞蟻總數(shù)為m(或更多)，將每一只螞蟻的評價函數(shù)定義為相鄰點(diǎn)之間的目標(biāo)函數(shù)差值,Δfij=fi-fj,?i,j。那么對限定在本級節(jié)點(diǎn)之間移動的每一只螞蟻的轉(zhuǎn)移概率pij為

(8)

式中，τij為每一只螞蟻在鄰域內(nèi)的信息素強(qiáng)度，表達(dá)了第j節(jié)點(diǎn)對第i節(jié)點(diǎn)的吸引強(qiáng)度；Ak表示螞蟻k在下一步可以經(jīng)過的空間網(wǎng)格點(diǎn)集合。最初，螞蟻散布在網(wǎng)格點(diǎn)中，記錄評價函數(shù)值最佳的位置，依據(jù)以上轉(zhuǎn)移概率公式移動每一只螞蟻，按照最鄰近原則進(jìn)行搜索，如下所示：

其次，需要改進(jìn)螞蟻在連續(xù)空間尋優(yōu)的信息素更新策略。信息素更新公式為

(9)

式中，ρ為信息素的殘留系數(shù)，表達(dá)了信息強(qiáng)度的持久性，其值影響收斂的全局性與速度，一般取值為0.5～0.9之間。因?yàn)棣言酱?，收斂就越快，但搜索就越易于陷入局部最?yōu)解，而ρ越小，全局搜索的能力就會提高，但搜索速度就會降低，因此對ρ提出了基于對數(shù)反正切函數(shù)的自適應(yīng)更新策略，即ρ隨迭代次數(shù)的反正切函數(shù)而發(fā)生改變，這樣既保證了全局收斂性能，也提高了算法的收斂速度。Q為一正數(shù)，fk為目標(biāo)函數(shù)值。ρ的更新公式為

(10)

式中，nc為迭代次數(shù)；參數(shù)a為控制迭代次數(shù)變化的加速度。

2　點(diǎn)云聚類試驗(yàn)分析

2.1　改進(jìn)蟻群優(yōu)化投影尋蹤聚類試驗(yàn)

在試驗(yàn)中，用坐標(biāo)x，坐標(biāo)y，坐標(biāo)z，法矢量(x,y,z方向)，曲率共7個特征來分類點(diǎn)云。為了使投影指數(shù)函數(shù)Q(a)達(dá)到最大值，必須同時優(yōu)化7個參數(shù)。從本質(zhì)上講，它是一個多維的優(yōu)化問題。本文采用改進(jìn)的蟻群優(yōu)化投影尋蹤聚類算法。蟻群算法的參數(shù)見表3，改進(jìn)后算法中的螞蟻數(shù)目為變量的數(shù)量m=7，軌跡的相對重要性alpha=0.9，能見度的相對重要性beta=2.0，按照信息素進(jìn)行轉(zhuǎn)移的概率為q0=1，迭代次數(shù)的初始值為nc=1，各路徑的信息素tau=0，各路徑能見度為1。最大迭代次數(shù)是500。各個變量分為100等分,并將螞蟻隨機(jī)分布在每個變量的某一個區(qū)間內(nèi)，其中ε為0.001。點(diǎn)云分割及提取的植物和建筑物結(jié)果如圖1、圖2所示。

圖1　點(diǎn)云分割的植物和建筑物結(jié)果

圖2　提取植物和建筑物的結(jié)果

圖2左圖為樹，右圖為建筑物。

本文試驗(yàn)用的點(diǎn)云數(shù)據(jù)為徠卡ALS60 sn/6133在太子港獲取的機(jī)載激光雷達(dá)數(shù)據(jù)，其飛行高度約為760 m。本文使用交互式操作，從點(diǎn)云中提取樹木和建筑物。通過設(shè)置不同的參數(shù)來提取樹木和建筑物。并對樹木與建筑物的數(shù)量與準(zhǔn)確性進(jìn)行評估。見表2和表4。

表2　樹木與建筑物位置和數(shù)量的精度

表3　蟻群算法的參數(shù)

如表2所示，通過計算建筑物和樹木的數(shù)量和位置可以看出，本文提出的方法適用于精確測定樹木和建筑物的位置。

本文提出的改進(jìn)的蟻群優(yōu)化投影尋蹤聚類與傳統(tǒng)的蟻群優(yōu)化投影尋蹤聚類效果比較一致。與其他兩種算法相比，本文提出的算法在迭代次數(shù)上較少，時間復(fù)雜度相對較低，這源于信息素殘留系數(shù)的更新方式影響了迭代次數(shù)，對于連續(xù)空間尋優(yōu)速度起著很重要的作用。最佳投影方向各個分量的大小反映了各個特征對點(diǎn)云分類的影響程度，從最佳投影方向可知，對點(diǎn)云的分類影響程度大小依次為坐標(biāo)x、坐標(biāo)y、法矢量、曲率和坐標(biāo)z。

3　結(jié)　論

本文深入分析了蟻群算法在點(diǎn)云聚類中應(yīng)用的計算原理，并將該模型與其他聚類模型相結(jié)合應(yīng)用于三維點(diǎn)云的聚類中?？偨Y(jié)如下：

(1) 深入分析蟻群算法在連續(xù)空間優(yōu)化的原理，通過優(yōu)化信息素殘留系數(shù)的更新方式，對比了遺傳算法優(yōu)化投影尋蹤的效率，實(shí)現(xiàn)投影尋蹤聚類的最佳投影方向加速選擇，為蟻群優(yōu)化投影尋蹤三維激光點(diǎn)云高維度特征的聚類提供指導(dǎo)。研究表明，信息素殘留系數(shù)是影響連續(xù)空間搜索的關(guān)鍵因素，特別是對于大數(shù)據(jù)量的高維特征投影問題，特征的重要性對分類起到了決定作用，也意味著未來點(diǎn)云聚類研究應(yīng)該加強(qiáng)特征選擇的研究。

表4　對蟻群算法與其他算法的性能比較

(2) 改進(jìn)的蟻群優(yōu)化投影尋蹤聚類方法適用于樹和建筑物分割。經(jīng)過試驗(yàn)評估發(fā)現(xiàn)，樹木的高度和建筑物的結(jié)構(gòu)對結(jié)果均有重要影響。一般來說，樹或建筑物越高，百分比和定位精度就越好。本文認(rèn)為這種方法用在其他領(lǐng)域具有可行性。

參考文獻(xiàn)：

[1] GROSS H，THOENNESSEN U.Extraction of Lines from Laser Point Clouds[C]∥Symposium of ISPRS Commission Ⅲ：Photogrammetric Computer Vision PCV06.[S.l.]：International Archives of Photogrammetry，Remote Sensing and Spatial Information Sciences，2006：86-91.

[2] YANG B，F(xiàn)ANG L，LI Q，et al.Automated Extraction of Road Markings from Mobile LiDAR Point Clouds[J].Photogrammetric Engineering & Remote Sensing，2012，78(4)：331-338.

[3] HULIK R，SPANEL M，SMRZ P，et al.Continuous Plane Detection in Point-cloud Data Based on 3D Hough Transform[J].Journal of Visual Communication and Image Representation，2014，25(1)：86-97.

[4] WANG L，CAO J，HAN C.Multidimensional Particle Swarm Optimization-based Unsupervised Planar Segmen-tation Algorithm of Unorganized Point Clouds[J].Pattern Recognition，2012，45(11)：4034-4043.

[5] BIOSCA J M，LERMA J L.Unsupervised Robust Planar Segmentation of Terrestrial Laser Scanner Point Clouds Based on Fuzzy Clustering Methods[J].ISPRS Journal of Photogrammetry and Remote Sensing，2008，63(1)：84-98.

[6] GUPTA S，WEINACKER H，KOCH B.Comparative Analysis of Clustering-based Approaches for 3-D Single Tree Detection Using Airborne Fullwave LiDAR Data[J].Remote Sensing，2010，2(4)：968-989.

[7] REITBERGER J，SCHN?RR C，KRZYSTEK P，et al.3D Segmentation of Single Trees Exploiting Full Waveform LiDAR Data[J].ISPRS Journal of Photogrammetry and Remote Sensing，2009，64(6)：561-574.

[8] LEE H，SLATTON K C，ROTH B E，et al.Adaptive Clustering of Airborne LiDAR Data to Segment Individual Tree Crowns in Managed Pine Forests[J].International Journal of Remote Sensing，2010，31(1)：117-139.

[9] OTERO F E B，F(xiàn)REITAS A A，JOHNSON C G.A New Sequential Covering Strategy for Inducing Classification Rules with Ant Colony Algorithms[J].IEEE Transactions on Evolutionary Computation，2013，17(1)：64-76.

[10]XIAO J，ADLER B，ZHANG J，et al.Planar Segment Based Three-dimensional Point Cloud Registration in Outdoor Environments[J].Journal of Field Robotics，2013，30(4)：552-582.

[11]NI S，QIN J，SU C.Dynamic AntColony Algorithm Used in Continuous Space Optimization[J].Electronics Optics and Control，2009，16(12):12-14.

[12]KHANNA K，RAJPAL N.Reconstruction of Curves from Point Clouds Using Fuzzy Logic and Ant Colony Optimization[J].Neurocomputing，2015，161(8)：72-80.

[13]PARPINELLI R S，LOPES H S，F(xiàn)REITAS A A.An Ant Colony Algorithm for Classification Rule Discovery[J].Data Mining：A Heuristic Approach，2002：191-208.

[14]HEMMATEENEJAD B，SHAMSIPUR M，ZARE-SHAHABADI V，et al.Building Optimal Regression Tree by Ant Colony System-Genetic Algorithm：Application to Modeling of Melting Points[J].Analytica Chimica Acta，2011，704(1)：57-62.

[15]AFSHAR M H.Partially Constrained Ant Colony Optimization Algorithm for the Solution of Constrained Optimization Problems：Application to Storm Water Network Design[J].Advances in Water Resources，2007，30(4)：954-965.

[16]楊德賀，袁靜，王秀英，等.形變觀測數(shù)據(jù)的多異常形態(tài)統(tǒng)一識別[J].地球物理學(xué)報，2017,60(12)：4623-4632.

[17]楊德賀，王秀英，申旭輝，等.鉆孔應(yīng)變觀測數(shù)據(jù)的分形特征研究[J].科學(xué)技術(shù)與工程，2017,17(34)：73-79.