改進(jìn)禿鷹搜索和K均值混合迭代的點(diǎn)云簡(jiǎn)化算法

牛宏俠,李富麗

(1. 蘭州交通大學(xué)自動(dòng)化與電氣工程學(xué)院,730070,蘭州;2. 蘭州交通大學(xué)甘肅省高原交通信息工程及控制重點(diǎn)實(shí)驗(yàn)室,730070,蘭州;3. 蘭州交通大學(xué)光電技術(shù)與智能控制教育部重點(diǎn)實(shí)驗(yàn)室,730070,蘭州)

隨著3D目標(biāo)檢測(cè)技術(shù)的發(fā)展,點(diǎn)云的深度學(xué)習(xí)受到眾多學(xué)者關(guān)注[1]。然而,點(diǎn)云數(shù)據(jù)無(wú)序和離散的特點(diǎn)對(duì)3D檢測(cè)任務(wù)造成了極大的困擾,因此,三維點(diǎn)云簡(jiǎn)化算法的研究對(duì)點(diǎn)云的深度學(xué)習(xí)顯得尤為重要。經(jīng)典的點(diǎn)云簡(jiǎn)化算法主要包括包圍盒法[2]、隨機(jī)采樣法[3]、基于特征的點(diǎn)云簡(jiǎn)化算法[4]等。Pauly等[5]通過(guò)計(jì)算空間二值化,提出了一種基于點(diǎn)樣本分層分解的簡(jiǎn)化方法,但由于空間性質(zhì)的原因,很難控制采樣表面分布點(diǎn)的質(zhì)量。Xuan等[6]引入信息熵和向量角,提出了一種漸進(jìn)點(diǎn)云簡(jiǎn)化方法,該方法的基礎(chǔ)是利用法向角的信息熵來(lái)尋找重要的點(diǎn),并通過(guò)刪除不相關(guān)的點(diǎn)來(lái)進(jìn)行簡(jiǎn)化操作;然而,不相關(guān)點(diǎn)的選擇具有極大的不確定性。Mahdaoui等[7]提出了一種基于香農(nóng)熵和K均值聚類(lèi) (K-means clustering,KMC)的方法來(lái)簡(jiǎn)化三維點(diǎn)云,由于聚類(lèi)時(shí)受點(diǎn)云空間形狀的限制,因此聚類(lèi)差異較大;同時(shí),由于聚類(lèi)中心點(diǎn)選取的隨機(jī)性以及聚類(lèi)優(yōu)化路徑的單一性,導(dǎo)致聚類(lèi)結(jié)果不穩(wěn)定。群智能算法在對(duì)聚類(lèi)中心進(jìn)行優(yōu)化方面具有顯著優(yōu)勢(shì)[8-9],結(jié)合聚類(lèi)算法和信息估計(jì)為點(diǎn)云簡(jiǎn)化提供了一種新的思路。

禿鷹搜索算法(bald eagle search,BES)是2020年提出的一種新型優(yōu)化算法[10],由于可擴(kuò)展性強(qiáng),在大規(guī)模全局優(yōu)化問(wèn)題中能夠有效地跳出局部最優(yōu),與其它群智能算法相比具有更強(qiáng)的全局搜索能力。BES算法通過(guò)生物行為構(gòu)建數(shù)學(xué)模型,主要分為選擇、搜索和俯沖3個(gè)階段,與KMC算法結(jié)合后能夠?qū)崿F(xiàn)點(diǎn)云的高精度聚類(lèi)。由此,本文提出了一種基于改進(jìn)禿鷹搜索和KMC混合迭代的點(diǎn)云簡(jiǎn)化算法(improved bald eagle search and KMC hybrid iteration simplification algorithm,IBESSA)。首先,對(duì)BES算法的優(yōu)化和更新迭代方式進(jìn)行改進(jìn),通過(guò)BES算法迭代階段的競(jìng)爭(zhēng)融合(competitive fusion bald eagle search,CFBES)加速收斂;然后,通過(guò)CFBES和KMC算法的混合迭代,實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的聚類(lèi);最后,引入點(diǎn)云信息熵概念,結(jié)合點(diǎn)云聚類(lèi)結(jié)果實(shí)現(xiàn)了點(diǎn)云的簡(jiǎn)化。

1 CFBES算法

1.1 BES算法

BES算法通過(guò)模擬禿鷹捕食鮭魚(yú)的過(guò)程,在搜索空間內(nèi)對(duì)解進(jìn)行優(yōu)化。BES算法主要分為選擇、搜索和俯沖3個(gè)階段。

(1)選擇階段:禿鷹通過(guò)觀(guān)察區(qū)域內(nèi)獵物的多少來(lái)確定合適的搜索區(qū)域,為下一階段搜索獵物做好準(zhǔn)備。該階段禿鷹位置Pi,new可用數(shù)學(xué)模型描述為

Pi,new=Pbest+αη(Pmean-Pi)

(1)

式中:Pbest為當(dāng)前禿鷹確定的最佳搜索位置;α為控制位置變化的參數(shù),α∈(1.5,2);η為隨機(jī)數(shù),η∈(0,1);Pmean為禿鷹根據(jù)所有搜索結(jié)果計(jì)算出的平均分布位置;Pi為第i只禿鷹的位置。

(2)搜索階段:禿鷹在先前選定的搜索區(qū)域內(nèi)進(jìn)行螺旋運(yùn)動(dòng),不斷改變搜索的角度和速度以尋找最佳俯沖捕獲位置,并同時(shí)向最佳位置移動(dòng)。其運(yùn)動(dòng)行為可描述如下

θ(i)=aπη

(2)

r(i)=θ(i)+Rη

(3)

x(i)=r(i)sin(θ(i))/max(|r(i)sin(θ(i))|)

(4)

y(i)=r(i)cos(θ(i))/max(|r(i)cos(θ(i))|)

(5)

Pi,new=Pi+x(i)(Pi-Pmean)+y(i)(Pi-Pi+1)

(6)

式中:θ(i)和r(i)分別為螺旋方程的極角和極徑;a和R為控制禿鷹飛行軌跡的常數(shù),影響禿鷹搜索周期的長(zhǎng)短,其中a∈(5,10),R∈(0.5,2);η為(0,1)內(nèi)的隨機(jī)數(shù);x(i)和y(i)分別為極坐標(biāo)中禿鷹個(gè)體的位置,取值均為(-1,1);Pi+1為第i只禿鷹下一次準(zhǔn)備更新的位置。

(3)俯沖階段:禿鷹以上一階段搜索到的最佳位置為中心,向獵物方向的最佳點(diǎn)移動(dòng)并對(duì)其進(jìn)行捕獲。仍用極坐標(biāo)方式來(lái)描述禿鷹的運(yùn)動(dòng)狀態(tài),如下所示

θ(i)=aπη;r(i)=θ(i)

(7)

x1(i)=r(i)sinh(θ(i))/max(|r(i)sinh(θ(i))|)

(8)

y1(i)=r(i)cosh(θ(i))/max(|r(i)cosh(θ(i))|)

(9)

式中:x1(i)、y1(i)為俯沖階段禿鷹個(gè)體在極坐標(biāo)系中的位置。

禿鷹在俯沖過(guò)程中的位置更新公式可表示為

Pi,new=ηPbest+x1(i)(Pi-c1Pmean)+y1(i)(Pi-c2Pbest)

(10)

式中:c1、c2分別為禿鷹向最佳位置和中心位置運(yùn)動(dòng)強(qiáng)度的大小,取值范圍為(1,2)。

1.2 改進(jìn)BES算法

1.2.1 基于混沌映射的禿鷹初始化

由于禿鷹種群初始分布是隨機(jī)的,生成的種群不夠均勻,因此嚴(yán)重影響到種群的收斂速度和最終解的精度。蔣宇飛等[11]在蜉蝣算法中引入Sine混沌映射用于蜉蝣種群的初始化,使種群能夠均勻分布在解空間中,從而提高了初始種群的質(zhì)量,優(yōu)化了隨機(jī)初始化產(chǎn)生的缺陷,證明了混沌映射方法對(duì)元啟發(fā)式算法的有效性。

本文利用混沌映射遍歷性和隨機(jī)性的特性,在傳統(tǒng)Tent混沌映射中加入調(diào)節(jié)機(jī)制v/N,得到新的映射機(jī)制,如下所示

(11)

式中:Xi,j+1為映射得到的混沌值,i為種群大小,i=1, 2, …,N,j為混沌序號(hào),j=1, 2,…,d;Xi,j為種群大小為i、混沌序號(hào)為j的混沌值;v為隨機(jī)數(shù),v∈[0,1];β為混沌參數(shù),β∈[0,2]。圖1給出了混沌映射序列分布的直方圖對(duì)比,其中橫坐標(biāo)表示映射區(qū)間,縱坐標(biāo)表示序列中落在相應(yīng)取值區(qū)間內(nèi)的數(shù)據(jù)個(gè)數(shù)。圖1(a)為改進(jìn)型Tent映射在區(qū)間[0,1]的分布圖,此時(shí)β=1.2;圖1(b)為經(jīng)典的Logistic序列直方圖。

(a)改進(jìn)型Tent序列直方圖

(b)經(jīng)典Logistic序列直方圖

通過(guò)對(duì)比兩種序列直方圖,發(fā)現(xiàn)改進(jìn)后的Tent混沌序列能夠使生成的初始種群較為均勻,而均勻分布的初始位置使得種群更容易從局部最優(yōu)解中逃脫,從而尋找全局最優(yōu)解。因此,使用改進(jìn)型Tent映射生成隨機(jī)序列,有利于前期的全局搜索以及種群的隨機(jī)初始化。

通過(guò)不斷迭代,得到一系列混沌值Xi,j,再將其映射到種群搜索空間,映射規(guī)則如下

Pi,j=Lj,min+Xi,j(Uj,max-Lj,min)

(12)

式中:Lj,min、Uj,max分別為禿鷹位置Pi,j的下邊界和上邊界。

1.2.2 競(jìng)爭(zhēng)淘汰機(jī)制

禿鷹搜索算法中,位置更新主要靠個(gè)體間信息的相互交流,由于個(gè)體差異較大,導(dǎo)致同一區(qū)域內(nèi)的禿鷹通過(guò)螺旋運(yùn)動(dòng)進(jìn)行食物搜索時(shí),需要多次迭代才能捕獲獵物,同時(shí),性能較弱的個(gè)體不能較快地達(dá)到最優(yōu)區(qū)域,致使禿鷹在進(jìn)行捕獲獵物時(shí)尋優(yōu)效率過(guò)慢,且在精度要求越高的場(chǎng)合,算法效率就越低。為進(jìn)一步提高BES算法的開(kāi)發(fā)能力,本文借鑒捕獵的習(xí)性,在禿鷹搜索階段設(shè)計(jì)了競(jìng)爭(zhēng)淘汰機(jī)制對(duì)禿鷹種群進(jìn)行篩選,其基本過(guò)程主要分為個(gè)體篩選和盤(pán)旋尋優(yōu)兩個(gè)階段。第一階段以禿鷹個(gè)體的適應(yīng)度函數(shù)作為篩選標(biāo)準(zhǔn),根據(jù)種群中子代個(gè)體的適應(yīng)度判斷個(gè)體的優(yōu)化性能,淘汰適應(yīng)度較差的個(gè)體,從而獲得新的禿鷹種群。第二階段對(duì)第一階段得到的新禿鷹種群進(jìn)行增殖,以中心輻射法模擬禿鷹低空盤(pán)旋搜尋路線(xiàn),獲得新的禿鷹增殖種群,然后再次對(duì)新的種群進(jìn)行適應(yīng)度排序,按照初始種群數(shù)保留新的優(yōu)秀個(gè)體,淘汰質(zhì)量較差的個(gè)體,以保證種群數(shù)量不變。競(jìng)爭(zhēng)淘汰機(jī)制具體過(guò)程如下。

首先,根據(jù)適應(yīng)度設(shè)定閾值,通過(guò)優(yōu)化性能差異進(jìn)行個(gè)體篩選操作,保留適應(yīng)度高于設(shè)定閾值的個(gè)體,淘汰適應(yīng)度差的個(gè)體,同時(shí)更新禿鷹種群的數(shù)量,具體淘汰機(jī)制如下

(13)

式中:pi+1為根據(jù)篩選原則保留下來(lái)的適應(yīng)度較優(yōu)的個(gè)體;r為(0,1)間服從均勻分布的隨機(jī)數(shù);FSortIndex(i)為當(dāng)前種群中第i個(gè)禿鷹個(gè)體對(duì)應(yīng)的優(yōu)化性能,表達(dá)式可寫(xiě)為

(14)

式中:SortIndex(i)為個(gè)體pi排序后的索引值;σ介于0和1之間,旨在任意方向形成搜索向量,提高找到最優(yōu)個(gè)體的可能性;fmax、fmin分別為當(dāng)前種群中最優(yōu)適應(yīng)度和最差適應(yīng)度;f(i)為第i個(gè)禿鷹個(gè)體的適應(yīng)度。

通過(guò)個(gè)體篩選策略,適應(yīng)度低于閾值的個(gè)體會(huì)被淘汰,性能較優(yōu)的個(gè)體會(huì)被保留,算法的尋優(yōu)能力和搜索精度得到了提高。

以中心輻射法模擬上一階段得到的禿鷹種群低空盤(pán)旋搜尋路線(xiàn),進(jìn)而獲得新的禿鷹增殖種群,再次對(duì)新的種群進(jìn)行適應(yīng)度排序,按照初始種群數(shù)保留新的種群個(gè)體,以保證種群數(shù)量不變。禿鷹個(gè)體在搜索空間仍然服從均勻分布,用Ei表示通過(guò)中心輻射法得到的禿鷹數(shù)量,Oi表示以最優(yōu)位置進(jìn)行輻射增值的禿鷹種群半徑,表達(dá)式可寫(xiě)為

(15)

(16)

式中:λ為輻射系數(shù),用以決定種群中產(chǎn)生有效個(gè)體的能力,λ越大種群產(chǎn)生有效個(gè)體的數(shù)量越多;b為增值步長(zhǎng);N為種群數(shù)量;ζ為調(diào)節(jié)常數(shù)。

競(jìng)爭(zhēng)淘汰機(jī)制可以通過(guò)淘汰適應(yīng)度低的個(gè)體,使優(yōu)質(zhì)個(gè)體更容易地在搜索空間中找到更好的解,并避免過(guò)早收斂于局部極值。同時(shí),在競(jìng)爭(zhēng)淘汰過(guò)程中,采用中心輻射增值法會(huì)不斷產(chǎn)生新的種群,并與原有個(gè)體進(jìn)行競(jìng)爭(zhēng),從而保持種群多樣性,避免種群陷入全局最優(yōu)。通過(guò)設(shè)置適當(dāng)?shù)脑鲋挡介L(zhǎng)、輻射系數(shù)等參數(shù),能夠進(jìn)一步增強(qiáng)算法的全局搜索能力。

2 CFBES與KMC算法的混合迭代

KMC算法[12]是一種無(wú)監(jiān)督的機(jī)器學(xué)習(xí)算法,其將數(shù)據(jù)點(diǎn)劃分為K個(gè)簇,廣泛應(yīng)用于數(shù)據(jù)分析和深度學(xué)習(xí)領(lǐng)域。KMC算法的具體流程如下。

(1)隨機(jī)選取K個(gè)對(duì)象作為初始聚類(lèi)中心,按照距離最近原則將數(shù)據(jù)分為K組。

(2)計(jì)算每個(gè)聚類(lèi)簇各個(gè)維度的平均值,并將其作為新聚類(lèi)中心用以更新聚類(lèi)簇。

(3)重復(fù)過(guò)程(2),直到新的聚類(lèi)中心不再變化或達(dá)到最大迭代次數(shù),輸出聚類(lèi)中心。

KMC算法采用迭代方式求取各個(gè)維度的均值,但通過(guò)此方法確定聚類(lèi)中心的局限性在于易陷入局部最優(yōu),導(dǎo)致優(yōu)化精度過(guò)低。本文通過(guò)采用CFBES代替KMC的優(yōu)化路徑,實(shí)現(xiàn)CFBES與KMC的混合迭代,擴(kuò)大了尋優(yōu)范圍,從而提升了聚類(lèi)的效果。采用同一簇內(nèi)聚類(lèi)中心和樣本點(diǎn)之間距離平方和,定義CFBES算法的適應(yīng)度函數(shù)為

(17)

式中:μj為第j個(gè)聚類(lèi)中心;x為樣本點(diǎn);m為該類(lèi)簇中所有樣本點(diǎn)的個(gè)數(shù);K為聚類(lèi)個(gè)數(shù)。通過(guò)適應(yīng)度函數(shù)可知,當(dāng)前聚類(lèi)效果的好壞受該類(lèi)樣本數(shù)及每個(gè)類(lèi)別中所有樣本點(diǎn)到該簇聚類(lèi)中心距離的影響。

聚類(lèi)數(shù)目的設(shè)定會(huì)影響到最終的聚類(lèi)結(jié)果,不同點(diǎn)云數(shù)據(jù)由于空間分布差異大,無(wú)法預(yù)先統(tǒng)一聚類(lèi)數(shù)目。為適應(yīng)不同數(shù)據(jù)空間特征,引入肘部法則(elbow method,EM)來(lái)確定點(diǎn)云數(shù)據(jù)的最佳聚類(lèi)數(shù)目。EM法則的適用條件為:需要確定的聚類(lèi)數(shù)目位于一個(gè)合理的范圍內(nèi),且數(shù)據(jù)的聚類(lèi)結(jié)構(gòu)比較清晰,聚類(lèi)簇之間的聚類(lèi)有明顯差異。EM法則對(duì)于點(diǎn)云數(shù)據(jù)同樣適用,其基本思想為:隨著聚類(lèi)數(shù)目的增加,聚類(lèi)效果會(huì)不斷提高,但當(dāng)聚類(lèi)數(shù)目達(dá)到某一閾值時(shí),聚類(lèi)效果的提升會(huì)逐漸減緩,這個(gè)閾值即為最優(yōu)聚類(lèi)數(shù)目。EM法則的實(shí)現(xiàn)原理為:利用誤差平方和SSSE畫(huà)出K-SSSE曲線(xiàn),通過(guò)觀(guān)察圖像,找到圖像中出現(xiàn)“拐點(diǎn)”的位置,這個(gè)拐點(diǎn)對(duì)應(yīng)的聚類(lèi)數(shù)目即為最優(yōu)聚類(lèi)數(shù)目。SSSE的表達(dá)式可寫(xiě)為

(18)

式中:Ci為第i個(gè)簇;x為樣本點(diǎn);μi為Ci的質(zhì)心。

圖2給出了EM法則的取值示意圖。其中,圖2(a)表示輸入點(diǎn)云數(shù)據(jù)散點(diǎn)圖;圖2(b)表示根據(jù)輸入的數(shù)據(jù)進(jìn)行聚類(lèi)得到不同的簇;同時(shí)計(jì)算誤差平方和確定最佳簇?cái)?shù),最后得到的聚類(lèi)結(jié)果如圖2(c)。由圖可知,當(dāng)聚類(lèi)數(shù)目為4時(shí),SSSE的斜率變化最大,由此可知,EM法則取值合理。

(a)散點(diǎn)圖

(b)誤差平方和與簇?cái)?shù)量關(guān)系曲線(xiàn)

(c)聚類(lèi)結(jié)果

CFBES-KMC算法流程如圖3所示。算法的基本步驟描述如下。

步驟1輸入標(biāo)準(zhǔn)點(diǎn)云數(shù)據(jù)集,計(jì)算誤差平方和SSSE,確定初始聚類(lèi)數(shù)目K。

步驟2利用混沌映射對(duì)禿鷹搜索算法進(jìn)行初始化。

步驟3根據(jù)禿鷹搜索策略對(duì)種群進(jìn)行更新。

步驟4利用改進(jìn)的禿鷹搜索算法對(duì)種群進(jìn)行尋優(yōu)操作,得到新的聚類(lèi)中心。若新得到的聚類(lèi)中心適應(yīng)度優(yōu)于上次迭代的聚類(lèi)中心,用新的聚類(lèi)中心代替歷史聚類(lèi)中心。

步驟5判斷當(dāng)前迭代是否達(dá)到結(jié)束條件,若達(dá)到終止條件,輸出尋優(yōu)結(jié)果,結(jié)束程序。若未到達(dá),則跳到步驟3,繼續(xù)執(zhí)行。

圖3 CFBES-KMC算法流程Fig.3 CFBES-KMC algorithm flow char

3 點(diǎn)云信息量化

在三維點(diǎn)云簡(jiǎn)化任務(wù)中,需要通過(guò)信息熵對(duì)局部點(diǎn)云包含信息進(jìn)行量化,通過(guò)計(jì)算信息熵評(píng)估點(diǎn)云中點(diǎn)的分布情況,涉及到密度評(píng)估函數(shù)[13-15],密度評(píng)估函數(shù)一般包括參數(shù)法和非參數(shù)法兩種。由于點(diǎn)云數(shù)據(jù)的無(wú)序性,采用參數(shù)法進(jìn)行密度估計(jì)存在一定的難度,因此,本文采用k近鄰(k-nearest neighbors,k-NN)估計(jì)去完成點(diǎn)云信息熵的計(jì)算。

3.1 基于高斯核函數(shù)的k近鄰密度估計(jì)

高斯核函數(shù)[16]是一種徑向基核函數(shù),常用于處理非線(xiàn)性數(shù)據(jù),其基本原理是將數(shù)據(jù)映射到一個(gè)無(wú)限維的特征空間中,使數(shù)據(jù)變得線(xiàn)性可分,且具有很好的非線(xiàn)性分類(lèi)能力。因此,本文結(jié)合高斯核函數(shù)提出了一種點(diǎn)云k-NN密度估計(jì)方法。

點(diǎn)云k-NN密度估計(jì)通過(guò)計(jì)算樣本空間中每個(gè)點(diǎn)云的k近鄰距離來(lái)估計(jì)該點(diǎn)處的概率密度,估計(jì)量的水平由k定義,它是最近鄰的整數(shù),與樣本N成比例。樣本對(duì)象x與其余點(diǎn)之間的距離關(guān)系可表示如下

Z1(x)<…

(19)

式中:Zk為樣本對(duì)象x到第k近鄰點(diǎn)的距離。

d維k-NN估計(jì)定義如下

(20)

式中:G(u)為高斯核函數(shù),可寫(xiě)為

(21)

將式(21)代入式(20),可得

Qk-NN(x)=N-1Zk(x)-d(2π)-(d/2)·

(22)

進(jìn)一步推導(dǎo)可得

(23)

式中:Cd為d維空間中單位球體的體積。

由上可見(jiàn),k-NN密度估計(jì)方法的優(yōu)點(diǎn)是不需要對(duì)概率密度函數(shù)進(jìn)行假設(shè),且對(duì)密度函數(shù)的局部變化具有較好的適應(yīng)性。

3.2 信息熵定義

香農(nóng)熵[17]是由美國(guó)科學(xué)家克勞德香農(nóng)于1948年提出的一個(gè)數(shù)學(xué)函數(shù),其直觀(guān)地對(duì)應(yīng)于信息源所包含或傳遞的信息量。在點(diǎn)云簇的k-NN密度估計(jì)完成后,需要根據(jù)得到的局部密度值來(lái)計(jì)算點(diǎn)云的信息熵。點(diǎn)云的信息熵表示點(diǎn)云中點(diǎn)分布的不確定度,可以采用香農(nóng)熵來(lái)計(jì)算,公式如下

(24)

式中:n為點(diǎn)云中的點(diǎn)數(shù);Q(X=xi)為xi的密度估計(jì)值。

通過(guò)式(24),可以計(jì)算每個(gè)點(diǎn)云簇中各個(gè)點(diǎn)的貢獻(xiàn)信息熵,并將其累加得到整個(gè)點(diǎn)云簇的信息熵。對(duì)于孤立的噪聲點(diǎn)云而言,其信息熵通常為0。因此,香農(nóng)熵用來(lái)表示每個(gè)點(diǎn)云中的信息量大小,數(shù)值越大包含的信息量越多。如果一個(gè)點(diǎn)云的信息熵為0,則意味著該點(diǎn)云的取值是確定的,不包含任何信息。基于對(duì)信息量的估計(jì),可以準(zhǔn)確地評(píng)估該點(diǎn)云簇是否包含主要特征,從而確定是否需要保留該簇。

3.3 簡(jiǎn)化誤差評(píng)估

為了評(píng)價(jià)本文所提簡(jiǎn)化方法的準(zhǔn)確性,采用平均歐式距離(mean euclidean distance,MED)[18]指 標(biāo)來(lái)評(píng)估全局誤差,采用Hausdorff距離[19]測(cè)量簡(jiǎn)化后兩個(gè)點(diǎn)集之間的局部誤差。

平均歐式距離能夠直觀(guān)地反映簡(jiǎn)化后點(diǎn)云和原始點(diǎn)云之間的差異,其原理是計(jì)算簡(jiǎn)化后點(diǎn)云與原始點(diǎn)云之間的歐式距離,并取其平均值來(lái)評(píng)估簡(jiǎn)化誤差的大小。設(shè)兩個(gè)點(diǎn)集分別為X=x1,x2,…,xm和Y=y1,y2, …,yn,則平均歐氏距離可寫(xiě)為

(25)

Hausdorff距離常用于評(píng)估簡(jiǎn)化后點(diǎn)云與原始點(diǎn)云之間的局部誤差,其基本思想是找到一個(gè)點(diǎn)在兩個(gè)集合之間的最短距離,然后取最大值。給定點(diǎn)集A和點(diǎn)集B,它們之間的Hausdorff距離可定義為

(26)

式中:d(a,b)為點(diǎn)a和點(diǎn)b之間的距離;inf為下確界操作;sup為上確界操作。式(26)可解釋為:對(duì)于A中每個(gè)點(diǎn)a,計(jì)算與B中最近點(diǎn)b的距離d(a,b),取所有距離中的最大值;對(duì)于B中的每個(gè)點(diǎn)b,計(jì)算與A中最近點(diǎn)a的距離d(a,b),取所有距離中的最大值;將兩個(gè)最大值中較大的一個(gè)作為Hausdorff距離,此值越小,說(shuō)明簡(jiǎn)化后的點(diǎn)云越接近原始點(diǎn)云。

3.4 基于CFBES-KMC算法和信息熵的三維點(diǎn)云簡(jiǎn)化

三維點(diǎn)云簡(jiǎn)化的目的是選擇相關(guān)且具有代表性的三維點(diǎn),去除冗余的數(shù)據(jù)點(diǎn)。本文將改進(jìn)的CFBES-KMC算法用于簡(jiǎn)化密集點(diǎn)云,如圖4所示。首先使用CFBES-KMC算法將點(diǎn)云細(xì)分為若干個(gè)簇,然后計(jì)算每個(gè)簇的信息熵,根據(jù)所得熵對(duì)簇進(jìn)行降序排列,從而去除信息熵低的簇。這種簡(jiǎn)化方法既保留了鮮明的輪廓特征,又在簡(jiǎn)化點(diǎn)集中保留了細(xì)節(jié)特征,適用于簡(jiǎn)化非均勻分布的點(diǎn)集。

圖4 主程序流程圖Fig.4 Flow chart of the main program

4 實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)硬件平臺(tái)為Intel Core i7-12700KF處理器,NVIDIA GeForce RTX 3060 Ti顯卡×2,32 GB內(nèi)存的計(jì)算機(jī),操作系統(tǒng)為Windows11,軟件實(shí)現(xiàn)語(yǔ)言為python。

4.1 CFBES算法性能測(cè)試

為驗(yàn)證CFBES算法的優(yōu)化性能,將CFBES與BES[9]、改進(jìn)禿鷹搜索(IBES)[20]、非均勻變異麻雀搜索(MSSA)[21]、改進(jìn)飛蛾撲火(IMFO)[22]4種優(yōu)化算法進(jìn)行對(duì)比,采用單峰測(cè)試函數(shù)F1～F4測(cè)試其收斂效果,多峰測(cè)試函數(shù)F8～F10及F14測(cè)試其局部尋優(yōu)及全局搜索能力。圖5所示為各測(cè)試函數(shù)及收斂曲線(xiàn)的可視化結(jié)果,圖中的x、y、z軸僅表示函數(shù)數(shù)值,量綱為1。設(shè)各種群大小均為30,迭代次數(shù)為100,維度為30,實(shí)驗(yàn)次數(shù)為20。CFBES算法中的輻射系數(shù)λ取30,調(diào)節(jié)常數(shù)ζ取20,增值步長(zhǎng)b取1.5。采用平均適應(yīng)度、標(biāo)準(zhǔn)差來(lái)定量評(píng)價(jià)算法的優(yōu)化性能。

由圖5(a)～(d)的收斂曲線(xiàn)可見(jiàn),對(duì)于單峰測(cè)試函數(shù),CFBES算法的收斂速度最快,即同一時(shí)刻CFBES算法獲得的適應(yīng)度最小,相比改進(jìn)前的BES算法在搜索性能方面有較大的提升。由圖5(e)～(h)的多峰測(cè)試函數(shù)迭代曲線(xiàn)可以看出,CFBES算法能夠較早脫離局部最優(yōu),在全局尋優(yōu)能力方面有著不錯(cuò)的表現(xiàn)。

(a)F1函數(shù)及收斂曲線(xiàn)

(b)F2函數(shù)及收斂曲線(xiàn)

(c)F3函數(shù)及收斂曲線(xiàn)

(d)F4函數(shù)及收斂曲線(xiàn)

(e)F8函數(shù)及收斂曲線(xiàn)

(f)F9函數(shù)及收斂曲線(xiàn)

(g)F10函數(shù)及收斂曲線(xiàn)

(h)F14函數(shù)及收斂曲線(xiàn)

表1給出了CFBES算法與其他優(yōu)化算法的測(cè)試結(jié)果對(duì)比。由分析結(jié)果可知,在平均適應(yīng)度方面,CFBES算法在8個(gè)測(cè)試函數(shù)中尋優(yōu)得到的平均適應(yīng)度更接近理論最優(yōu)值,表明其收斂效果更佳,能夠快速找到全局最優(yōu)解。適應(yīng)度標(biāo)準(zhǔn)差方面,CFBES算法在選取的8個(gè)測(cè)試函數(shù)中尋優(yōu)效果較其他算法而言更加穩(wěn)定。

表1 CFBES算法與其他優(yōu)化算法測(cè)試結(jié)果的對(duì)比

4.2 CFBES-KMC算法總體效果評(píng)價(jià)

為了評(píng)價(jià)本文提出的CFBES-KMC算法的改進(jìn)效果,將其與改進(jìn)飛蛾撲火K均值交叉迭代(IMFO-KMC)算法[22]、K-means++算法[23]、模糊C均值(FCM)聚類(lèi)算法[24]應(yīng)用到UCI數(shù)據(jù)集中,用以比較各算法的優(yōu)劣性能。算法的參數(shù)設(shè)置如下:各類(lèi)種群大小均為30,最大迭代次數(shù)為100,FCM聚類(lèi)算法中的權(quán)重指數(shù)取2.1。標(biāo)準(zhǔn)數(shù)據(jù)集如表2所示。圖6分別給出了CFBES-KMC、IMFO-KMC、K-means++、FCM 4種算法在Iris、Wine、CMC和Seeds數(shù)據(jù)集上的適應(yīng)度收斂曲線(xiàn)。

表2 標(biāo)準(zhǔn)數(shù)據(jù)集特征

由圖6可見(jiàn),在Iris和Wine數(shù)據(jù)集測(cè)試中,CFBES-KMC算法均具有比IMFO-KMC算法更快的收斂速度;在CMC和Seeds數(shù)據(jù)集上,CFBES-KMC算法收斂效果明顯優(yōu)于參與對(duì)比的其他3種算法。由此可得,本文所改進(jìn)的CFBES-KMC算法在收斂速度方面優(yōu)于傳統(tǒng)的K-means++和FCM算法。

同時(shí),為更客觀(guān)地評(píng)價(jià)CFBES-KMC算法的改進(jìn)效果,分別采用YAcc、TARI、BNMI3個(gè)指標(biāo)來(lái)衡量不同聚類(lèi)算法的性能[25]。其中,YAcc表示聚類(lèi)的準(zhǔn)確率,即比較聚類(lèi)結(jié)果和真實(shí)結(jié)果之間的一致性;TARI衡量的是兩個(gè)數(shù)據(jù)分布的吻合程度,值越大意味著計(jì)算結(jié)果與真實(shí)值越相似;BNMI為歸一化互信息,用來(lái)表示兩組數(shù)據(jù)之間的關(guān)聯(lián)程度。表3列出了4種算法在3個(gè)數(shù)據(jù)集上測(cè)試得到的評(píng)價(jià)指標(biāo)以及單次迭代所需時(shí)間。由表3可知,CFBES-KMC算法在Iris數(shù)據(jù)集上測(cè)得的YAcc指標(biāo)高于其他3種算法,表明CFBES-KMC算法在復(fù)雜尋優(yōu)過(guò)程中具有更好的魯棒性,其主要是由于在禿鷹搜索過(guò)程中加入了競(jìng)爭(zhēng)淘汰機(jī)制;在Wine數(shù)據(jù)集上,CFBES-KMC算法的YAcc相較于IMFO-KMC、FCM、K-means++算法,分別提高了0.21%、2.48%和8.83%;在CMC數(shù)據(jù)集中,CFBES-KMC算法的TARI指標(biāo)相較于其他算法提升了0.26%～1.94%;與此同時(shí),CFBES-KMC算法在Seeds數(shù)據(jù)集上測(cè)得的YAcc、TARI和BNMI也均優(yōu)于其他3種算法。

(a)在Iris數(shù)據(jù)集上

(b)在CMC數(shù)據(jù)集上

(c)在Wine數(shù)據(jù)集上

(d)在Seeds數(shù)據(jù)集上

表3 不同算法在4種數(shù)據(jù)集上的性能指標(biāo)對(duì)比

在4種測(cè)試數(shù)據(jù)集上,K-means++和FCM算法單次迭代所需的時(shí)間均少于CFBES-KMC算法,而CFBES-KMC算法所消耗的時(shí)間相較于IMFO-KMC算法有不同程度的提升。其中,在Wine和CMC數(shù)據(jù)集上,CFBES-KMC算法的單次迭代時(shí)間相較于IMFO-KMC算法,分別節(jié)省了9.79%、6.83%。

由上述實(shí)驗(yàn)結(jié)果可知,KMC算法思路簡(jiǎn)單,聚類(lèi)精度低,隨機(jī)選取聚類(lèi)中心致使算法穩(wěn)定性差; FCM算法由于涉及到模糊控制,迭代曲線(xiàn)趨于平滑,但聚類(lèi)精度不高;IMFO-KMC算法相較于CFBES-KMC算法,需要花費(fèi)更多的時(shí)間才能收斂到足夠精度;而CFBES-KMC算法由于采取了競(jìng)爭(zhēng)淘汰機(jī)制,使得聚類(lèi)算法不易陷入局部最優(yōu),穩(wěn)定性較強(qiáng),相比于其他算法聚類(lèi)準(zhǔn)確率更高。

4.3 基于信息熵的CFBES-KMC聚類(lèi)三維點(diǎn)云簡(jiǎn)化結(jié)果分析

實(shí)驗(yàn)采用常見(jiàn)的三維點(diǎn)云數(shù)據(jù)格式,選取兔、椅子和馬作為點(diǎn)云數(shù)據(jù)模型進(jìn)行三維點(diǎn)云的簡(jiǎn)化,得到原始點(diǎn)云、聚類(lèi)結(jié)果、簡(jiǎn)化后點(diǎn)云的可視化圖像,如圖7～圖9所示。由圖可見(jiàn),聚類(lèi)結(jié)果保留了原始點(diǎn)云的結(jié)構(gòu)特征,將模型主體結(jié)構(gòu)劃分為同一聚類(lèi)簇,信息熵占比較大,避免了信息熵過(guò)低導(dǎo)致的結(jié)構(gòu)性特征刪除;而冗余的細(xì)節(jié)特征表現(xiàn)為離散的小型聚類(lèi)簇,此類(lèi)冗余點(diǎn)云數(shù)據(jù)由于信息熵過(guò)低,可在后期被過(guò)濾以達(dá)到刪除非結(jié)構(gòu)性特征的目的,從而實(shí)現(xiàn)三維點(diǎn)云的簡(jiǎn)化。表4給出了不同三維點(diǎn)云模型簡(jiǎn)化后的量化結(jié)果,統(tǒng)計(jì)數(shù)據(jù)為20次獨(dú)立實(shí)驗(yàn)得到的平均值。

(a)原始點(diǎn)云圖

(b)聚類(lèi)結(jié)果

(c)簡(jiǎn)化后點(diǎn)云圖

(a)原始點(diǎn)云圖

(b)聚類(lèi)結(jié)果

(c)簡(jiǎn)化后點(diǎn)云圖

(a)原始點(diǎn)云圖

(b)聚類(lèi)結(jié)果

(c)簡(jiǎn)化后點(diǎn)云圖

表4 不同三維點(diǎn)云模型簡(jiǎn)化結(jié)果

由表4可知,改進(jìn)后的簡(jiǎn)化算法在刪除點(diǎn)數(shù)和簡(jiǎn)化表面之間的誤差方面有著較好的表現(xiàn),原始表面和使用改進(jìn)后方法得到的簡(jiǎn)化表面之間的全局、局部誤差均較小;在運(yùn)行時(shí)間方面,改進(jìn)后的點(diǎn)云簡(jiǎn)化算法的運(yùn)行速度能夠滿(mǎn)足實(shí)時(shí)性要求,且在有效濾除冗余點(diǎn)云的基礎(chǔ)上保留了原始模型的紋理特性和幾何特征,實(shí)現(xiàn)了點(diǎn)云數(shù)據(jù)模型的有效簡(jiǎn)化。

5 結(jié) 論

本文通過(guò)混沌映射對(duì)禿鷹種群的初始化進(jìn)行優(yōu)化,并在搜索階段加入競(jìng)爭(zhēng)淘汰機(jī)制對(duì)禿鷹種群進(jìn)行篩選,提高了BES算法的搜索精度和全局尋優(yōu)能力,然后通過(guò)CFBES-KMC算法實(shí)現(xiàn)點(diǎn)云數(shù)據(jù)的聚類(lèi),在k-NN實(shí)現(xiàn)點(diǎn)云簇密度估計(jì)的基礎(chǔ)上,結(jié)合香農(nóng)熵實(shí)現(xiàn)點(diǎn)云信息量化,刪除量化值小于閾值的聚類(lèi)簇,從而完成了點(diǎn)云數(shù)據(jù)的簡(jiǎn)化。仿真結(jié)果表明:在標(biāo)準(zhǔn)測(cè)試函數(shù)上進(jìn)行優(yōu)化性能分析時(shí),CFBES算法的尋優(yōu)性能優(yōu)于參與比較的其它算法;與同類(lèi)型的IMFO-KMC、K-means++、FCM算法的聚類(lèi)效果相比,CFBES-KMC算法的聚類(lèi)準(zhǔn)確率分別提高了1.02%、12.31%、14.72%;提出的IBESSA點(diǎn)云簡(jiǎn)化算法在有效濾除冗余點(diǎn)云的基礎(chǔ)上保留了原本點(diǎn)云的細(xì)節(jié)和形狀特征,不失為一種高效的點(diǎn)云簡(jiǎn)化算法。