改進禿鷹搜索和K均值混合迭代的點云簡化算法

牛宏俠,李富麗

(1. 蘭州交通大學自動化與電氣工程學院,730070,蘭州;2. 蘭州交通大學甘肅省高原交通信息工程及控制重點實驗室,730070,蘭州;3. 蘭州交通大學光電技術與智能控制教育部重點實驗室,730070,蘭州)

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

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

1 CFBES算法

1.1 BES算法

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

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

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

(1)

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

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

θ(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ù),影響禿鷹搜索周期的長短,其中a∈(5,10),R∈(0.5,2);η為(0,1)內(nèi)的隨機數(shù);x(i)和y(i)分別為極坐標中禿鷹個體的位置,取值均為(-1,1);Pi+1為第i只禿鷹下一次準備更新的位置。

(3)俯沖階段:禿鷹以上一階段搜索到的最佳位置為中心,向獵物方向的最佳點移動并對其進行捕獲。仍用極坐標方式來描述禿鷹的運動狀態(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)為俯沖階段禿鷹個體在極坐標系中的位置。

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

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

(10)

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

1.2 改進BES算法

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

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

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

(11)

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

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

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

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

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

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

(12)

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

1.2.2 競爭淘汰機制

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

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

(13)

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

(14)

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

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

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

(15)

(16)

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

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

2 CFBES與KMC算法的混合迭代

KMC算法[12]是一種無監(jiān)督的機器學習算法,其將數(shù)據(jù)點劃分為K個簇,廣泛應用于數(shù)據(jù)分析和深度學習領域。KMC算法的具體流程如下。

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

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

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

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

(17)

式中:μj為第j個聚類中心;x為樣本點;m為該類簇中所有樣本點的個數(shù);K為聚類個數(shù)。通過適應度函數(shù)可知,當前聚類效果的好壞受該類樣本數(shù)及每個類別中所有樣本點到該簇聚類中心距離的影響。

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

(18)

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

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

(a)散點圖

(b)誤差平方和與簇數(shù)量關系曲線

(c)聚類結(jié)果

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

步驟1輸入標準點云數(shù)據(jù)集,計算誤差平方和SSSE,確定初始聚類數(shù)目K。

步驟2利用混沌映射對禿鷹搜索算法進行初始化。

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

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

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

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

3 點云信息量化

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

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

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

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

Z1(x)<…

(19)

式中:Zk為樣本對象x到第k近鄰點的距離。

d維k-NN估計定義如下

(20)

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

(21)

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

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

(22)

進一步推導可得

(23)

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

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

3.2 信息熵定義

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

(24)

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

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

3.3 簡化誤差評估

為了評價本文所提簡化方法的準確性,采用平均歐式距離(mean euclidean distance,MED)[18]指 標來評估全局誤差,采用Hausdorff距離[19]測量簡化后兩個點集之間的局部誤差。

平均歐式距離能夠直觀地反映簡化后點云和原始點云之間的差異,其原理是計算簡化后點云與原始點云之間的歐式距離,并取其平均值來評估簡化誤差的大小。設兩個點集分別為X=x1,x2,…,xm和Y=y1,y2, …,yn,則平均歐氏距離可寫為

(25)

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

(26)

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

3.4 基于CFBES-KMC算法和信息熵的三維點云簡化

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

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

4 實驗與結(jié)果分析

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

4.1 CFBES算法性能測試

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

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

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

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

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

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

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

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

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

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

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

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

4.2 CFBES-KMC算法總體效果評價

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

表2 標準數(shù)據(jù)集特征

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

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

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

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

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

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

(a)原始點云圖

(b)聚類結(jié)果

(c)簡化后點云圖

(a)原始點云圖

(b)聚類結(jié)果

(c)簡化后點云圖

(a)原始點云圖

(b)聚類結(jié)果

(c)簡化后點云圖

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

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

5 結(jié) 論

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