張佳琦,王建民

(太原理工大學(xué)礦業(yè)工程學(xué)院,太原 030024)

通過(guò)三維掃描技術(shù)可以獲取幾何體的點(diǎn)云模型數(shù)據(jù),其作為一種重要的三維空間數(shù)據(jù)源,在對(duì)被測(cè)物體的細(xì)節(jié)表現(xiàn)方面發(fā)揮著無(wú)可比擬的重要作用[1],已經(jīng)在逆向工程[2]、三維建模[3]等領(lǐng)域得到廣泛應(yīng)用。而點(diǎn)云數(shù)據(jù)的三維重建是其應(yīng)用的基礎(chǔ),在數(shù)據(jù)處理過(guò)程中若直接進(jìn)行三維重建會(huì)增加計(jì)算機(jī)處理的時(shí)間、空間的復(fù)雜度[4],因此可以利用逆向重建技術(shù)[5]對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行一系列處理,主要包括點(diǎn)云數(shù)據(jù)的分割、特征提取、匹配和曲面重建等,而在該過(guò)程中點(diǎn)云數(shù)據(jù)的區(qū)域分割是后續(xù)曲面重構(gòu)的基礎(chǔ)與關(guān)鍵。目前,常用的點(diǎn)云自動(dòng)分割方法可歸納為4類(lèi)[6]:基于邊、基于面、基于聚類(lèi)和混合分割方法。基于邊的方法對(duì)噪聲敏感,計(jì)算精度低,會(huì)造成區(qū)域之間連通;基于面的方法對(duì)種子點(diǎn)和閾值的選取要求較高,直接影響到分割結(jié)果的好壞;混合方法在唯一性和魯棒性等方面有一定優(yōu)勢(shì),但其涉及算法較多,實(shí)現(xiàn)較為復(fù)雜。近年來(lái),基于聚類(lèi)的分割方法由于實(shí)現(xiàn)簡(jiǎn)單、尋優(yōu)速度快且性能良好等優(yōu)點(diǎn),逐漸被應(yīng)用于點(diǎn)云數(shù)據(jù)分割?；诰垲?lèi)的方法是將數(shù)據(jù)點(diǎn)空間近鄰、屬性相同或相似的點(diǎn)歸為一類(lèi)(該方法對(duì)于曲面特征變化較明顯的點(diǎn)云數(shù)據(jù)尤為適用),其中模糊C均值(fuzzyC-means,FCM)算法[7]目前已經(jīng)成功應(yīng)用于點(diǎn)云、圖像分割等領(lǐng)域[8-10]。但是在實(shí)際應(yīng)用中,FCM算法對(duì)初始值敏感且易于陷入局部最優(yōu),致使點(diǎn)云分割效果不佳,因此,許多學(xué)者引入群智能優(yōu)化算法來(lái)改善初始聚類(lèi)中心的選擇,主要有基于遺傳算法、改進(jìn)的粒子群算法、人工蜂群算法與FCM算法相結(jié)合的分割算法[11-13],取得了良好的聚類(lèi)效果,但這些算法中均存在尋優(yōu)速度慢、對(duì)參數(shù)敏感、易“早熟”等問(wèn)題[14]。

狼群算法作為一種新興的群體智能優(yōu)化算法,具有敏感參數(shù)少、收斂速度快、精度高等優(yōu)點(diǎn)[15],已在圖像處理[16]、路徑規(guī)劃[17]、生產(chǎn)調(diào)度[18]等領(lǐng)域廣泛應(yīng)用。但是,在實(shí)際情況中狼群算法仍存在“早熟”、運(yùn)算復(fù)雜、參數(shù)較多等缺點(diǎn),為此基于狼群算法提出了改進(jìn)的優(yōu)化算法[19-21],主要有3個(gè)方面:①為了使得初始解更好的分布在解空間,對(duì)種群初始化進(jìn)行改進(jìn);②引入自適應(yīng)步長(zhǎng)因子,以減少算法對(duì)參數(shù)敏感的同時(shí)提高算法的收斂速度;③引入擾動(dòng)策略、交互策略使得算法更好地進(jìn)行全局尋優(yōu),并跳出局部最優(yōu)解。改進(jìn)后的狼群算法能夠減小參數(shù)的敏感性并獲得全局最優(yōu)的近似解,但是單純一種改進(jìn)策略效果有限。

為此,現(xiàn)采用佳點(diǎn)集、自適應(yīng)步長(zhǎng)、交互策略和高斯擾動(dòng)機(jī)制等方法對(duì)狼群算法進(jìn)行綜合改進(jìn)。并將改進(jìn)后算法融入FCM算法中,提出一種基于曲率約束的改進(jìn)狼群算法與FCM相結(jié)合的混合算法(IWPAFCM),提升FCM算法對(duì)點(diǎn)云分割的準(zhǔn)確性,并利用仿真實(shí)驗(yàn)測(cè)試算法性能。

1 模糊C-均值聚類(lèi)算法原理

模糊C-均值聚類(lèi)算法[7]是一種散亂數(shù)據(jù)分類(lèi)算法,通過(guò)最小化目標(biāo)函數(shù)將數(shù)據(jù)集劃分為多個(gè)聚類(lèi),數(shù)據(jù)集中的元素對(duì)于每個(gè)聚類(lèi)都有一個(gè)隸屬度值,代表其歸屬于某個(gè)聚類(lèi)的程度,定義隸屬度在[0,1]內(nèi)取值。

己知l維歐氏空間中的數(shù)據(jù)集S={s1,s2,…,sj,…,sn}?Rl,樣本sj的特征向量sj=(sj1,sj2,…,sjl)T∈Rl。將數(shù)據(jù)集S劃分為c(2≤c≤n)個(gè)子集,即聚類(lèi)數(shù)為c,c個(gè)子集聚類(lèi)中心為C={C1,C2…,Cc}。通過(guò)極小化目標(biāo)函數(shù)實(shí)現(xiàn)最佳聚類(lèi),目標(biāo)函數(shù)一般定義為

(1)

(2)

(3)

利用FCM算法實(shí)現(xiàn)對(duì)點(diǎn)云數(shù)據(jù)的區(qū)域分割,有兩個(gè)關(guān)鍵問(wèn)題需要考慮。首先,FCM算法對(duì)于初始聚類(lèi)中心選擇過(guò)于敏感,容易陷入局部最優(yōu),因此利用具有全局尋優(yōu)能力的改進(jìn)狼群算法來(lái)解決這一問(wèn)題。其次,單純利用傳統(tǒng)FCM算法的歐式距離(以點(diǎn)云坐標(biāo)為粒子點(diǎn)的距離)對(duì)三維點(diǎn)云進(jìn)行區(qū)域劃分時(shí),點(diǎn)云的微分幾何信息,如曲面、法向量等不能被充分利用,為此引入曲率約束的點(diǎn)距離[22]對(duì)歐式距離進(jìn)行替換,從而獲得理想的點(diǎn)云分割結(jié)果。

2 改進(jìn)狼群算法

狼群算法受到自然界中狼群捕食行為的啟發(fā),將狼群按不同的分工劃分為頭狼、探狼和猛狼,抽象出游走、召喚、圍攻3種智能行為,根據(jù)“勝者為王”和“強(qiáng)者生存”規(guī)則更新頭狼、保持狼群多樣性[23]。

在基本狼群算法中,探狼通過(guò)式(4)進(jìn)行位置更新,也即執(zhí)行游走行為來(lái)尋找當(dāng)前最優(yōu)解作為頭狼;猛狼通過(guò)式(5)向頭狼奔襲(召喚行為),在該過(guò)程中若其適應(yīng)度值優(yōu)于頭狼則更新頭狼狀態(tài)并發(fā)起召喚行為,否則,繼續(xù)朝頭狼奔襲。

當(dāng)兩種人工狼之間的距離小于判定距離時(shí),狼群按照式(6)執(zhí)行圍攻行為,并根據(jù)適應(yīng)度值判斷是否更新頭狼。然后淘汰部分適應(yīng)度值較小的狼,并隨機(jī)生成新的人工狼。當(dāng)滿(mǎn)足精度要求或達(dá)到最大迭代次數(shù)時(shí)輸出最優(yōu)解,否則回到游走行為。人工狼位置更新公式為

(4)

(5)

(6)

狼群算法具有全局尋優(yōu)能力強(qiáng)、精度高等優(yōu)點(diǎn),但在實(shí)際應(yīng)用中,還是會(huì)有一些缺點(diǎn),如種群多樣性隨迭代更新而下降、后期收斂速度慢、易陷入局部最優(yōu)等[15],因此利用佳點(diǎn)集、自適應(yīng)步長(zhǎng)、交互策略和高斯擾動(dòng)機(jī)制等方法對(duì)算法進(jìn)行相應(yīng)的改進(jìn)。

2.1 佳點(diǎn)集初始化和自適應(yīng)步長(zhǎng)

(1)基本狼群算法以隨機(jī)方式初始化種群,可能導(dǎo)致狼群在解空間分布不均勻,尋優(yōu)結(jié)果不理想。佳點(diǎn)集方法的精度不受其維數(shù)影響,產(chǎn)生的初始種群均勻性和多樣性更好[24]。一定程度上可以避免陷入局部最優(yōu),加快算法收斂速度。在狼群算法“強(qiáng)者生存”更新機(jī)制中,同樣以佳點(diǎn)集方式初始化原本隨機(jī)生成的人工狼。步驟總結(jié)如下。

步驟1根據(jù)歐式空間的維數(shù)s,找到滿(mǎn)足(p-3)/2≥s的最小素?cái)?shù)p。

步驟2設(shè)Gs是S維歐式空間的單位立方體,對(duì)Gs中的點(diǎn)r=(r1,r2,…,rs),取rk=2cos(2πk/p),1≤k≤s,則將p代入可求得佳點(diǎn)r。

(2)基本狼群算法在3種智能行為中,采用固定步長(zhǎng)對(duì)解空間進(jìn)行探索,當(dāng)步長(zhǎng)設(shè)定過(guò)大時(shí)不利于尋找全局最優(yōu)解,步長(zhǎng)過(guò)小時(shí)又會(huì)增加算法的收斂時(shí)間,本文研究引入文獻(xiàn)[20]提出的自適應(yīng)步長(zhǎng)來(lái)對(duì)尋優(yōu)與收斂時(shí)間進(jìn)行平衡。自適應(yīng)步長(zhǎng)定義為

(7)

式(7)中:rand為[0,1]間的隨機(jī)數(shù);xi為當(dāng)前人工狼i位置;XLead為當(dāng)前頭狼位置。

(3)基本狼群算法中判定距離的設(shè)定同樣影響算法的收斂速度和尋優(yōu)精度,即設(shè)定過(guò)小時(shí)猛狼多次被頭狼召喚卻難以進(jìn)入圍攻行為,設(shè)定過(guò)大時(shí)人工狼難以找到獵物位置;故本文研究取消初始判定距離,以頭狼更新或最大召喚次數(shù)作為進(jìn)入圍攻行為的條件[21],很好地提高了WPA算法運(yùn)行效率。

2.2 交互策略

在WPA算法的游走、召喚行為中,探狼、猛狼群體內(nèi)部缺少必要的交流,會(huì)出現(xiàn)對(duì)解空間重復(fù)搜索或探索不到的情況,導(dǎo)致尋優(yōu)時(shí)間長(zhǎng),甚至不收斂,因此為了增加人工狼群體內(nèi)部的交互性以及提高尋優(yōu)能力,引入交互策略[25],即

vi,d=xi,d+φi,d(xbest,d-xi,d)+φi,d(xj,d-xk,d)

(8)

式(8)中:φi,d為[0,1]的隨機(jī)數(shù);φi,d為[-1,1]的隨機(jī)數(shù);xbest,d為頭狼位置;xk,d,xj,d為隨機(jī)的人工狼k、j在d維空間位置,且k≠i≠j。式(8)的前半段確保了頭狼的領(lǐng)導(dǎo)能力,后半段增加了人工狼之間的交互,很好地提高了算法全局與局部尋優(yōu)的能力。

2.3 高斯擾動(dòng)機(jī)制

基本狼群算法在陷入局部最優(yōu)時(shí)難以跳出局部最優(yōu)點(diǎn)[15],因此引入高斯擾動(dòng)來(lái)解決這一問(wèn)題。位置更新公式為

(9)

(10)

以求解適應(yīng)度最小值為例,IWPA算法步驟如下。

步驟1初始化人工狼數(shù)目N,最大迭代次數(shù)kmax,最大游走次數(shù)ymax,召喚次數(shù)t,更新比例因子β。以佳點(diǎn)集方法對(duì)種群進(jìn)行初始化,確定每個(gè)人工狼的適應(yīng)度值,排序取最小值位置作為頭狼位置。

步驟2選取排序后適應(yīng)度較小的Snum匹人工狼作為探狼,按照更新后的游走步長(zhǎng)執(zhí)行游走,之后按式(8)尋找新獵物,從h+1個(gè)獵物中尋找最優(yōu)獵物,直到頭狼位置更新或者達(dá)到最大游走次數(shù)時(shí)執(zhí)行步驟3。

步驟3頭狼發(fā)起召喚,召集猛狼向其位置靠近,選取當(dāng)前猛狼、召喚后位置、進(jìn)行一次式(8)后位置三者中的最小適應(yīng)度位置作為新的猛狼位置,過(guò)程中若適應(yīng)度小于頭狼則更新頭狼位置,并以當(dāng)前頭狼位置發(fā)起召喚行為,直到猛狼達(dá)到最大召喚次數(shù)或頭狼被更新時(shí)執(zhí)行步驟4。

步驟4按自適應(yīng)圍攻步長(zhǎng)計(jì)算參與圍攻行為人工狼的新位置,若適應(yīng)度值小于頭狼則更新頭狼位置。

步驟5對(duì)當(dāng)前所有人工狼排序,淘汰適應(yīng)度值較差的部分人工狼,并以佳點(diǎn)集生成新的人工狼,若其適應(yīng)度值小于當(dāng)前頭狼則更新頭狼狀態(tài)。

步驟6以高斯擾動(dòng)機(jī)制對(duì)頭狼位置進(jìn)行更新。

步驟7判斷算法是否達(dá)到規(guī)定精度或最大迭代次數(shù),滿(mǎn)足其中一點(diǎn)則算法結(jié)束,輸出結(jié)果,否則,執(zhí)行步驟2。

2.4 算法性能測(cè)試

為了充分驗(yàn)證本文算法的尋優(yōu)性能,通過(guò)3個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)在固定維數(shù)30維情況下對(duì)所提算法(IWPA)的尋優(yōu)性能進(jìn)行測(cè)試,函數(shù)描述如表1所示。

表1 3個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)

表1中f1和f2為單模態(tài)函數(shù),可以用來(lái)測(cè)試算法的尋優(yōu)精度,f3為多模態(tài)函數(shù),一般尋優(yōu)算法很難找到全局的最優(yōu)解,用來(lái)測(cè)試算法在有多個(gè)局部最優(yōu)解情況下跳出局部最優(yōu)解和尋找全局最優(yōu)解的能力。函數(shù)分別運(yùn)行20次,迭代次數(shù)設(shè)為1 000次,計(jì)算出平均值、標(biāo)準(zhǔn)差、最優(yōu)和最差值,并和算法MWPA[19]、MACWPA[20]、WPA[23]和FA[26]進(jìn)行對(duì)比,計(jì)算結(jié)果如表2所示,迭代曲線如圖1所示。

圖1 各算法迭代曲線

表2 5種算法在3個(gè)測(cè)試函數(shù)下計(jì)算結(jié)果對(duì)比

通過(guò)表2中數(shù)據(jù)可以看出,對(duì)于所有的標(biāo)準(zhǔn)測(cè)試函數(shù),在規(guī)定的迭代次數(shù)情況下本文算法在尋優(yōu)精度和穩(wěn)定性方面都明顯優(yōu)于對(duì)比算法,尤其是在多模態(tài)函數(shù)中,本文算法的尋優(yōu)精度達(dá)到了1×10-10,表現(xiàn)出了極佳的尋優(yōu)能力。通過(guò)迭代圖可以看出,對(duì)于兩個(gè)單模態(tài)函數(shù),本文算法隨著迭代的進(jìn)行并沒(méi)有出現(xiàn)明顯的停滯現(xiàn)象,表明如果繼續(xù)迭代本文算法甚至可能找到函數(shù)的最優(yōu)解,而對(duì)于多模態(tài)函數(shù),本文算法在迭代后期有著明顯跳出局部最優(yōu)值的能力,表現(xiàn)出了本文算法在多模態(tài)函數(shù)中的優(yōu)勢(shì)。這主要是由于IWPA引入自適應(yīng)步長(zhǎng),使參與尋優(yōu)的人工狼能根據(jù)算法迭代自動(dòng)調(diào)整靠近頭狼的步長(zhǎng),同時(shí)以頭狼更新和最大召喚次數(shù)作為進(jìn)入圍攻行為的條件,加快了算法的尋優(yōu)速度,而通過(guò)佳點(diǎn)集、交互策略和高斯擾動(dòng)機(jī)制,使得算法擁有加深全局搜索能力,跳出局部最優(yōu),改善了全局尋優(yōu)的精度。通過(guò)以上測(cè)試充分證明了所提算法在單模態(tài)和多模態(tài)函數(shù)尋優(yōu)中的優(yōu)勢(shì),也為進(jìn)一步與FCM算法結(jié)合,解決其對(duì)初值敏感和易于陷入局部最優(yōu)的問(wèn)題提供了充分的依據(jù)。

3 基于曲率約束的IWPAFCM聚類(lèi)算法

應(yīng)用改進(jìn)狼群算法優(yōu)化FCM聚類(lèi)算法對(duì)點(diǎn)云進(jìn)行區(qū)域分割,可有效改善FCM算法陷入局部極小值的情況。而為了實(shí)現(xiàn)理想的點(diǎn)云分割效果,充分利用點(diǎn)云的特征信息,本文研究利用曲率約束的點(diǎn)距離替換傳統(tǒng)FCM算法的歐式距離。下面對(duì)點(diǎn)云特征向量的估算,點(diǎn)距離的計(jì)算,適應(yīng)度函數(shù)的選擇等關(guān)鍵問(wèn)題進(jìn)行說(shuō)明。

3.1 點(diǎn)云特征矢量的估算

利用法矢量、曲率構(gòu)成的7維特征向量表示點(diǎn)云粒子,以此來(lái)實(shí)現(xiàn)對(duì)特征變化明顯的物體表面的細(xì)分割。

(11)

應(yīng)用自適應(yīng)鄰域主成分分析法[27]對(duì)法向量求解,該方法易于實(shí)現(xiàn)、穩(wěn)定性強(qiáng);對(duì)于曲率估算可通過(guò)對(duì)某點(diǎn)鄰域內(nèi)的25～30個(gè)點(diǎn)進(jìn)行局部擬合,構(gòu)造局部鄰域內(nèi)的二次曲面[28],將擬合出的二次曲面的曲率近似作為該點(diǎn)的主曲率,進(jìn)而可求得高斯曲率、平均曲率。

3.2 點(diǎn)距離

傳統(tǒng)歐氏距離對(duì)點(diǎn)云數(shù)據(jù)分割不能很好地反映曲面的特征變化,即使特征變化明顯,在給定距離閾值范圍,還是會(huì)被分割到同一區(qū)域,在某些特定需求條件下不能得到理想的分割效果[22]。為此利用點(diǎn)云法矢和曲率來(lái)計(jì)算兩點(diǎn)之間的距離,實(shí)現(xiàn)對(duì)點(diǎn)云模型的細(xì)分割。

定義2點(diǎn)距離。設(shè)點(diǎn)云數(shù)據(jù)P中的任意兩個(gè)點(diǎn)pi和pj,分別表示為:pi=(ai,bi,ci,Ki,Hi,ki1,ki2),pj=(aj,bj,cj,Kj,Hj,kj1,kj2),則pi和pj的距離可表示為

D(pi,pj)=DN(pi,pj)+φDQ(pi,pj)

(12)

式(12)中:DN(pi,pj)為法向距離;DQ(pi,pj)為曲率約束;φ為約束調(diào)整參數(shù);DN(pi,pj) 和DQ(pi,pj)分別由式(13)和式(14)計(jì)算。

(13)

(14)

整理式(12)、式(13)和式(14),調(diào)整參數(shù)得

(15)

式中:λ為φ、ω合并后的調(diào)整參數(shù),當(dāng)點(diǎn)云曲面信息豐富,需要細(xì)分出更細(xì)節(jié)區(qū)域時(shí),應(yīng)適當(dāng)增大λ取值。以式(15)計(jì)算求得的距離D(pi,pj)來(lái)替換傳統(tǒng)FCM算法的歐式距離dij。

3.3 適應(yīng)度函數(shù)

模糊聚類(lèi)取得較優(yōu)的聚類(lèi)結(jié)果時(shí),目標(biāo)函數(shù)取極小值;而狼群算法為尋優(yōu)算法,可根據(jù)情況求得目標(biāo)函數(shù)的極大值或極小值,以模糊聚類(lèi)的目標(biāo)函數(shù)作為改進(jìn)狼群算法的適應(yīng)度函數(shù),適應(yīng)度函數(shù)為

f(Xi)=Jm

(16)

在IWPA-FCM算法中,種群中任意一個(gè)人工狼Xi的位置狀態(tài),都可以用一個(gè)c×l列的一維行向量表示,即:Xi=(c11,c12,…,c1d,…,ci1,ci2,…,cid,…,cc1,cc2,…,ccl),其中l(wèi)為樣本維數(shù),c為聚類(lèi)數(shù)。則種群中第i個(gè)聚類(lèi)中心可表示為 (ci1,ci2,…,cil)。IWPAFCM 聚類(lèi)算法的基本步驟如下。

步驟1根據(jù)輸入點(diǎn)云數(shù)據(jù)計(jì)算出每個(gè)點(diǎn)的特征向量并進(jìn)行歸一化處理[29]。

步驟2初始化狼群算法的基本參數(shù)[23],取模糊加權(quán)指數(shù)m=2。

步驟3利用改進(jìn)狼群算法來(lái)初始化種群、更新求解最優(yōu)適應(yīng)度值,并輸出最優(yōu)聚類(lèi)中心。

步驟4以改進(jìn)狼群算法求得的最優(yōu)聚類(lèi)中心作為FCM的初始值進(jìn)行迭代,最終求得全局最優(yōu)解。

IWPAFCM聚類(lèi)算法的點(diǎn)云分割流程圖如圖2所示。

圖2 改進(jìn)狼群算法優(yōu)化聚類(lèi)中心的點(diǎn)云分割流程

為了對(duì)以上過(guò)程有更詳細(xì)的描述,以取最小值為例給出IWPAFCM聚類(lèi)算法的主循環(huán)偽代碼,在主循環(huán)之前是一些基礎(chǔ)計(jì)算與賦值,包括利用點(diǎn)云X計(jì)算法矢量V和高斯曲率K、平均曲率H和主曲率K1和K2,然后歸一化V、K、H、K1、K2組成新的解空間,并在解空間中利用佳點(diǎn)集初始化狼群位置,之后由式(1)～式(3)和式(12)計(jì)算每只狼對(duì)應(yīng)適應(yīng)度值并排序確定頭狼、探狼和猛狼的位置和適應(yīng)度,然后代入主循環(huán)進(jìn)行計(jì)算,主循環(huán)偽代碼如下。

算法:IWPAFCM聚類(lèi)算法

----------------------------------------------------------

輸入:點(diǎn)云X、迭代次數(shù)imax、游走次數(shù)Tmax、游走方向數(shù)h、探狼數(shù)量Snum、猛狼數(shù)量Mnum、召喚最大次數(shù)Wmax

輸出:聚類(lèi)中心(頭狼位置)

%主循環(huán)

for iter=1:imax

%探狼游走

fori=1:Tmax

forj= 1:Snum

forn=1:h

根據(jù)式(4)和式(7)得到h個(gè)新獵物

end for

根據(jù)式(8)獲得交互獵物V

form=1:h+1

計(jì)算獲得的h+1個(gè)獵物的適應(yīng)度

end for

更新探狼位置

end for

選出當(dāng)前最優(yōu)探狼,位置為X,適應(yīng)度Y

IfY

Ylead=Y;

Xlead=X;

break; %跳出進(jìn)入召喚行為

end if

end for%結(jié)束游走

%召喚行為

fori=1:Mnum

flag_exit = 0;%判斷頭狼是否替換

wgt=0;%召喚次數(shù)

while flag_exit==0

由式(5)和式(7)計(jì)算奔襲后位置

由式(8)計(jì)算交互位置

分別計(jì)算新位置適應(yīng)度

選取三者最優(yōu)位置X和最優(yōu)Y

wgt= wgt+1;

ifY

Ylead=Y;

Xlead=X;

wgt=Wmax;

end if

%圍攻行為

if wgt==Wmax

由(6)和式(7)計(jì)算圍攻后位置

選取當(dāng)前最優(yōu)位置X和最優(yōu)Y

ifY

Ylead=Y;

Xlead=X;

flag_exit = 1;

break

end if

end if%結(jié)束圍攻

end while

end for%結(jié)束召喚

佳點(diǎn)集更新狼群

%高斯擾動(dòng)機(jī)制

由式(9)和式(10)計(jì)算和更新頭狼

end for%結(jié)束迭代

在基本W(wǎng)PA算法上主要進(jìn)行了步長(zhǎng)調(diào)整、改變圍攻條件、增加交互行為和高斯擾動(dòng)機(jī)制等,此處對(duì)改進(jìn)后的算法復(fù)雜度進(jìn)行分析。算法的計(jì)算量通常根據(jù)迭代次數(shù)乘以每次迭代的計(jì)算量進(jìn)行評(píng)估,所以對(duì)照偽代碼,取一次迭代過(guò)程的計(jì)算量為例來(lái)簡(jiǎn)要說(shuō)明算法的計(jì)算量,假設(shè)一次迭代過(guò)程中游走和召喚行為只執(zhí)行一次,取探狼和猛狼數(shù)量同為Snum。

WPA算法計(jì)算量為:游走行為中加法hSnum次,乘法2hSnum次;召喚行為中加法3Snum,乘法2Snum;圍攻行為中加法2Snum,乘法2Snum。IWPA算法的計(jì)算量為:游走行為中加法Snum(h+5)次,乘法2Snum(h+1.5),召喚行為中加法2Snum,乘法3Snum。

通過(guò)一次迭代計(jì)算量可以看出,IWPA 算法的計(jì)算量大于WPA。在實(shí)際應(yīng)用過(guò)程中,本文研究中IWPA采用頭狼更新或達(dá)到最大召喚次數(shù)進(jìn)入圍攻行為,WPA則以頭狼更新或進(jìn)入圍攻距離作為進(jìn)入圍攻行為的條件,而圍攻距離參數(shù)的設(shè)定會(huì)影響WPA算法的運(yùn)行時(shí)間,設(shè)定過(guò)小猛狼很難進(jìn)入圍攻行為,算法計(jì)算量會(huì)增大;過(guò)大計(jì)算量小但不利于尋優(yōu)。IWPA則利用自適應(yīng)步長(zhǎng)、交互行為和最大圍攻次數(shù)配合,雖然增加了一定的算法運(yùn)行時(shí)間,但保證了算法優(yōu)秀的尋優(yōu)性能和避免早熟的能力。

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

4.1 定性分析

為了驗(yàn)證算法的有效性,應(yīng)用MATLAB2018a對(duì)上述算法加以實(shí)現(xiàn),以ModelNet40公開(kāi)數(shù)據(jù)集[30]中Chair、Stool點(diǎn)云模型和實(shí)測(cè)點(diǎn)云機(jī)械零件、汽車(chē)覆蓋件點(diǎn)云模型為例進(jìn)行點(diǎn)云數(shù)據(jù)的區(qū)域分割,并與基本FCM算法、基于算法MACWPA[20]、WPA[23]、FA[26]優(yōu)化的模糊聚類(lèi)算法分割效果進(jìn)行對(duì)比,取30次實(shí)驗(yàn)中出現(xiàn)次數(shù)最多的分割效果作為該算法分割效果,當(dāng)分割效果相同時(shí),以得到該分割效果的次數(shù)(成功率)進(jìn)行比較。

對(duì)于點(diǎn)云數(shù)目較少的Chair和Stool點(diǎn)云模型,點(diǎn)數(shù)都為10 000,如圖3和圖4所示,圖3(a)為Chair原始點(diǎn)云;圖3(b)為Chair分割前曲率顯示;對(duì)于Chair點(diǎn)云模型,5種算法都取得了較好的點(diǎn)云模型分割效果,如圖3(c)所示,都很好地將椅子腿和椅子座面進(jìn)行了分割,但是對(duì)于成功率,基本FCM、FAFCM成功率分別為56.6%、93.3%,WPAFCM、MACWPAFCM和本文算法的成功率都為100%;圖4(a)為Stool原始點(diǎn)云;圖4(b)為Stool分割前曲率顯示;對(duì)于Stool點(diǎn)云模型,5種算法同樣都取得了較好的點(diǎn)云模型分割效果,都很好地將凳子腿和凳子座面進(jìn)行了分割,基本FCM、FAFCM、WPAFCM、MACWPAFCM和本文算法成功率分別為36.7%、83.3%、96.7%、93.3%和100%。綜上可以看出對(duì)于兩種公開(kāi)數(shù)據(jù)集點(diǎn)云模型,本文算法點(diǎn)云聚類(lèi)分割效果好且結(jié)果穩(wěn)定,成功率都達(dá)到了100%。

圖3 Chair點(diǎn)云數(shù)據(jù)區(qū)域分割

對(duì)于實(shí)測(cè)點(diǎn)云,如圖5和圖6所示,圖5(a)為機(jī)械零件原始點(diǎn)云,點(diǎn)數(shù)為140 282;圖5(b)為機(jī)械零件分割前數(shù)據(jù)點(diǎn)的曲率顯示,同一曲面會(huì)包含少量曲率屬性不同的點(diǎn);圖5(c)為基本FCM算法和WPAFCM算法分割結(jié)果,可明顯看到在模型前側(cè)對(duì)于邊界分割的效果不理想,成功率分別為46.7%和53.3%;圖5(d)為本文算法、MACWPAFCM和FAFCM算法分割結(jié)果,用8種不同顏色來(lái)表示類(lèi)型不同的面,可以看到邊界清晰,準(zhǔn)確表達(dá)了點(diǎn)云分割結(jié)果,成功率分別為93.3%、73.3%和63.3%。圖6(a)為汽車(chē)覆蓋件原始點(diǎn)云,點(diǎn)數(shù)為147 197;圖6(b)為汽車(chē)覆蓋件分割前數(shù)據(jù)點(diǎn)的曲率顯示,同一曲面會(huì)包含少量曲率屬性不同的點(diǎn);圖6(c)為基本FCM、WPAFCM算法和FAFCM算法分割結(jié)果,可明顯看到在粉紫色類(lèi)中包含有藍(lán)色類(lèi)的點(diǎn),分割效果不理想,其成功率分別為36.7%、56.7%和63.3%;圖6(d)為本文算法和MACWPAFCM分割結(jié)果,用8種不同顏色來(lái)表示分割結(jié)果,可以看到邊界清晰,準(zhǔn)確表達(dá)了點(diǎn)云分割結(jié)果,其成功率分別為100%和53.3%。綜上可以看出對(duì)于兩種實(shí)測(cè)點(diǎn)云模型本文算法點(diǎn)云聚類(lèi)分割效果好且結(jié)果穩(wěn)定。

圖5 機(jī)械零件點(diǎn)云數(shù)據(jù)區(qū)域分割

4.2 定量分析

為了客觀、科學(xué)地評(píng)價(jià)點(diǎn)云分割的結(jié)果,利用聚類(lèi)性能評(píng)價(jià)指標(biāo)劃分系數(shù)VPC、劃分熵VPE和緊湊度與分離度的比值VXB來(lái)評(píng)價(jià)算法性能與聚類(lèi)效果。各指標(biāo)表達(dá)式為

(17)

(18)

(19)

式中:VPC、VPE僅與隸屬度矩陣uij有關(guān),VPC越大表示聚類(lèi)結(jié)果最有效,VPE則相反[31];VXB與數(shù)據(jù)的幾何結(jié)構(gòu)有關(guān),是類(lèi)內(nèi)緊湊度與類(lèi)間分離度的比值,因此VXB越小表示聚類(lèi)結(jié)果越有效[32]。

分別用FCM、FAFCM、WPAFCM、MACWPAFCM和IWPAFCM算法在4種數(shù)據(jù)集上進(jìn)行聚類(lèi)分析,求得其各自的適應(yīng)度函數(shù)值以及聚類(lèi)性能指標(biāo)VPC、VPE和VXB,并統(tǒng)計(jì)其達(dá)到收斂精度(1×10-6)時(shí)的迭代次數(shù)T。種群規(guī)模取15,各算法分別運(yùn)行30次,MACWPAFCM、WPAFCM、FAFCM算法參數(shù)設(shè)定參考文獻(xiàn)[20,23,29],求得各項(xiàng)指標(biāo)的平均值,對(duì)比結(jié)果如表3所示,迭代過(guò)程圖如圖7～圖10所示(對(duì)于ModelNet40數(shù)據(jù)集取20次迭代,實(shí)測(cè)數(shù)據(jù)集取50次迭代結(jié)果進(jìn)行對(duì)比,因?yàn)樵?0、50次迭代之后兩類(lèi)數(shù)據(jù)集收斂所需迭代次數(shù)較多的FCM算法也接近收斂,數(shù)值不再有太大變化)。

圖8 Stool模型的聚類(lèi)迭代過(guò)程

圖9 機(jī)械零件的聚類(lèi)迭代過(guò)程

圖10 汽車(chē)覆蓋件的聚類(lèi)迭代過(guò)程

表3 各項(xiàng)指標(biāo)的實(shí)驗(yàn)結(jié)果比較

根據(jù)評(píng)價(jià)準(zhǔn)則,VPC越大越好,Jm、VPE、VXB越小越好,由表3可以看出對(duì)于各類(lèi)數(shù)據(jù)集,本文算法較其他4種算法在適應(yīng)度函數(shù)值Jm和VPC、VPE、VXB聚類(lèi)指標(biāo)值上均為最優(yōu),在迭代次數(shù)上本文算法明顯減少。其中FCM算法在各項(xiàng)指標(biāo)中均為最差值。

對(duì)于Chair數(shù)據(jù)集,本文算法較FAFCM和FCM算法,在VPC指標(biāo)上平均提高0.4%～4.1%,在適應(yīng)度函數(shù)值Jm上平均減少0.2%～1.68%,在VPE指標(biāo)上平均減少0.6%～7.2%,在VXB指標(biāo)上平均減少0.2%～2.1%,WPAFCM和MACWPAFCM算法與本文算法取得了相同的指標(biāo)值,但本文算法在迭代次數(shù)上較其他4種算法平均迭代減少了10～19次;對(duì)于Stool數(shù)據(jù)集,本文算法在VPC指標(biāo)上平均提高0.4%～4.5%,在在適應(yīng)度函數(shù)值Jm上平均減少0.2%～1.99%,在VPE指標(biāo)上平均減少0.7%～7.5%,在VXB指標(biāo)上平均減少0.4%～4.2%,在迭代次數(shù)上平均減少7～23次;綜上可知對(duì)于點(diǎn)云數(shù)較少的兩種ModelNet40數(shù)據(jù)集,本文算法在VPC指標(biāo)上平均提高0.4%～4.3%,適應(yīng)度函數(shù)值Jm平均減少0.2%～1.84%,在VPE指標(biāo)上平均減少0.65%～7.35%,在VXB指標(biāo)上平均減少0.3%～3.15%,平均迭代次數(shù)減少8～21次。因?yàn)辄c(diǎn)云數(shù)較少,對(duì)比算法同樣可以取得較好的各項(xiàng)指標(biāo),所以單純從數(shù)據(jù)上感覺(jué)提升不是很高,但在此基礎(chǔ)上本文算法仍在指標(biāo)上略有提高的同時(shí),迭代次數(shù)明顯減少。

對(duì)于機(jī)械零件,本文算法在VPC指標(biāo)上平均提高0.7%～2.1%,在適應(yīng)度函數(shù)值Jm上平均減少4.06%～10.75%,在VPE指標(biāo)上平均減少1.7%～5.7%,在VXB指標(biāo)上平均減少5.6%～28.3%,在迭代次數(shù)上平均減少33～56次;對(duì)于汽車(chē)覆蓋件,本文算法在VPC指標(biāo)上平均提高11.3%～21.8%,在適應(yīng)度函數(shù)值Jm上平均減少3.85%～13.19%,在VPE指標(biāo)上平均減少1.96%～4.13%,在VXB指標(biāo)上平均減少2.53%～10.64%,在迭代次數(shù)上平均減少45～58次;綜上可知對(duì)于點(diǎn)云數(shù)較多的兩種實(shí)測(cè)點(diǎn)云數(shù)據(jù),本文算法在VPC指標(biāo)上平均提高6%～11.95%,適應(yīng)度函數(shù)值Jm平均減少3.95%～11.97%,在VPE指標(biāo)上平均減少1.83%～4.92%,在VXB指標(biāo)上平均減少4.06%～19.47%,平均迭代次數(shù)減少39～57次。

從圖7～圖10同樣可以看出,本文算法較其他4種算法,不僅收斂速度快,收斂所需迭代次數(shù)少,而且獲得了較優(yōu)的適應(yīng)度函數(shù)值。因?yàn)镮WPAFCM算法在初始種群分布、搜索能力方面做出了改進(jìn),可以快速高效地獲得聚類(lèi)過(guò)程中較優(yōu)的聚類(lèi)中心,因此提高了聚類(lèi)性能,減少了迭代次數(shù),也獲得了更好的綜合評(píng)價(jià)指標(biāo)。

5 結(jié)論

為提高聚類(lèi)性能、解決標(biāo)準(zhǔn)FCM算法對(duì)初始值敏感的問(wèn)題,本文提出一種基于曲率約束的改進(jìn)狼群算法優(yōu)化模糊聚類(lèi)的混合算法IWPAFCM。在該算法中,首先利用佳點(diǎn)集將人工狼種群均勻分布到解空間中,生成分布均勻、范圍廣、全局尋優(yōu)能力強(qiáng)的初始種群;然后引入自適應(yīng)步長(zhǎng)因子,對(duì)尋優(yōu)與收斂速度進(jìn)行平衡;進(jìn)一步采用交互策略,增強(qiáng)了狼群的全局探索能力;最后采用高斯擾動(dòng)對(duì)頭狼進(jìn)行變異處理,使得算法能夠跳出局部最優(yōu)。曲率約束點(diǎn)距離的引入,使得IWPAFCM不僅保證了良好的全局與局部尋優(yōu)能力,而且能夠穩(wěn)定地得到良好的點(diǎn)云分割效果。

為驗(yàn)證算法有效性,利用兩種ModelNet40公開(kāi)數(shù)據(jù)集和兩種實(shí)測(cè)點(diǎn)云模型進(jìn)行仿真實(shí)驗(yàn)。結(jié)果表明,在兩種ModelNet40公開(kāi)數(shù)據(jù)集上,IWPAFCM算法相比4種對(duì)比算法中效果最差的FCM算法,在VPC指標(biāo)上平均提高4.3%,適應(yīng)度函數(shù)值Jm平均減少1.84%,在VPE指標(biāo)上平均減少7.35%,在VXB指標(biāo)上平均減少3.15%,平均迭代次數(shù)減少21次;相比4種算法中效果最好的MACWPAFCM算法在VPC指標(biāo)上平均提高0.4%,適應(yīng)度函數(shù)值Jm平均減少0.2%,在VPE指標(biāo)上平均減少0.65%,在VXB指標(biāo)上平均減少0.3%,平均迭代次數(shù)減少8次。在兩種實(shí)測(cè)點(diǎn)云數(shù)據(jù)集上,相比4種對(duì)比算法中效果最差的FCM算法,本文算法在VPC指標(biāo)上平均提高11.95%,適應(yīng)度函數(shù)值Jm平均減少11.97%,在VPE指標(biāo)上平均減少4.92%,在VXB指標(biāo)上平均減少19.7%,平均迭代次數(shù)減少57次。相比4種算法中效果最好的MACWPAFCM算法在VPC指標(biāo)上平均提高6%,適應(yīng)度函數(shù)值Jm平均減少3.95%,在VPE指標(biāo)上平均減少1.83%,在VXB指標(biāo)上平均減少4.06%,平均迭代次數(shù)減少39次。表明本文算法能夠準(zhǔn)確找到初始聚類(lèi)中心,獲得了良好的點(diǎn)云分割效果,減少了迭代次數(shù),提升了聚類(lèi)性能。