基于agent形態(tài)特征的聚類分析研究與應(yīng)用

李哲, 慕德俊, 張?zhí)旆? 黃一杰

(西北工業(yè)大學(xué) 自動化學(xué)院, 陜西 西安　710072)

?

基于agent形態(tài)特征的聚類分析研究與應(yīng)用

李哲, 慕德俊, 張?zhí)旆? 黃一杰

(西北工業(yè)大學(xué) 自動化學(xué)院, 陜西 西安710072)

摘要：目前在多智能體(agent)系統(tǒng)控制中，少量agent在行為上表現(xiàn)出較強的獨立性，但在宏觀上依然具有一定的相似性，當其規(guī)模較大時這種相似性會更加明顯，但隨著數(shù)量增加的同時控制系統(tǒng)的負擔也會快速增長并導(dǎo)致決策延遲或無效化。提出一種基于形態(tài)特征的聚類算法，嘗試將具有相似行為的agent進行聚類研究，以較少的聚類中心替代數(shù)量龐大的agent以簡化分析控制流程以提高效率。通過與K-means聚類算法的對比測試與分析，該算法能夠有效簡化系統(tǒng)復(fù)雜性，提升系統(tǒng)性能，并具有較強的穩(wěn)定性。

關(guān)鍵詞：圖像形態(tài)學(xué)；聚類分析；機器視覺；機器學(xué)習(xí)；K-means算法

多智能體協(xié)同控制十分復(fù)雜[1]，在復(fù)雜背景環(huán)境下的大數(shù)量智能體分析與控制則更加困難，如復(fù)雜戰(zhàn)場背景環(huán)境下的兵團戰(zhàn)斗——在未來很有可能演變?yōu)橐詿o人/有人控制的智能體系統(tǒng)的對抗[2]。目前在多agent[3]系統(tǒng)控制中，少量agent在行為上表現(xiàn)出較強的獨立性，一般分析與控制過程也是建立在這種單個個體的分析上[4]，但多agent在宏觀上依然具有一定的相似性，當其規(guī)模較大時這種相似性會更加明顯[5]，但agent數(shù)量的增加會導(dǎo)致控制系統(tǒng)負擔快速增長并導(dǎo)致決策延遲或無效化，因而可以通過聚類的方法將這些智能體按照一定的規(guī)則進行分類，從而簡化分析過程，能夠從宏觀層面對多智能體協(xié)同控制提供決策支持(而且當智能體數(shù)量增加時不會導(dǎo)致計算代價的明顯提升)。在已有的智能體控制、聚類分析中[6]，機器視覺[7-8]是常用的手段，圖像包含豐富信息的同時也容易產(chǎn)生噪聲以及過冗信息(特別是當來自多個不同傳感器的圖像需要進行融合時則會產(chǎn)生更多冗余[9])，會降低系統(tǒng)正確率以及處理效率，已有的文獻大多集中在圖像相似度或?qū)ο笞R別本身，本文提出一種基于形態(tài)特征的聚類算法，利用agent形態(tài)特征和圖像形態(tài)融合消除噪聲，同時將具有相似行為的agent進行聚類研究，以較少的聚類中心替代數(shù)量龐大的agent以簡化分析控制流程以提高效率。

1系統(tǒng)分析模型

聚類分析是無監(jiān)督的機器學(xué)習(xí)中常用的方法，也被廣泛應(yīng)用于多agent行為分析與控制上。相似的對象會因為某些屬性形成聚集趨勢，這種趨勢也會在視覺上呈現(xiàn)，因此可以利用這種“聚集趨勢”構(gòu)成圖像形態(tài)處理并在該基礎(chǔ)上再進行聚類分析，屬于同一類的對象會傾向于聚集到一起，它們之間的距離相比于該類以外的對象要近得多，因此其在圖像形態(tài)上的距離也會較近，經(jīng)過形態(tài)處理(主要為開運算)后其圖像特征會具有融合趨勢，如圖1所示。

圖1a)原始數(shù)據(jù)之間并沒有明顯的關(guān)聯(lián)，使用系數(shù)r1對原始圖像進行膨脹后部分特征產(chǎn)生了融合，如圖1b)左下角方框圈中區(qū)域所示，在使用系數(shù)r2對圖像處理后這種融合趨勢更加明顯了，圖1c)和圖1d)從結(jié)果上來看是圖形的“連通”。

圖1　對圖像進行形態(tài)處理后其呈現(xiàn)較強的特征

在對agent運動進行分析時(選擇其位置作為聚類數(shù)據(jù))一方面可利用多種傳感器獲取其位置參數(shù)，也可選擇包含更多信息機器視覺作為數(shù)據(jù)采集系統(tǒng)，在宏觀層面看來類似于集中式協(xié)作模型[10]，例如衛(wèi)星拍攝戰(zhàn)場后通過圖像處理獲得各單位(包括智能體)的相對位置數(shù)據(jù)，然后對該數(shù)據(jù)進行聚類分析，分析流程框圖如圖2所示：

圖2　算法框架示意圖

選用機器學(xué)習(xí)中廣泛應(yīng)用的K-means算法作為對比驗證算法，它屬于分割式聚類算法，目的是使各簇中的數(shù)據(jù)點與所在簇質(zhì)心的誤差平方和最?。?/p>

(1)

K-means需要數(shù)值型數(shù)據(jù)來進行相似性度量,由用戶提供聚類數(shù)K,然后再按照如距離、歐式距離、絕對誤差和等方式進行聚類計算。其優(yōu)點是容易實現(xiàn),缺點是可能收斂到局部最小值,在大規(guī)模數(shù)據(jù)集上收斂較慢。此外因其在算法開始前隨機確定K個初始點作為質(zhì)心,然后再以SSE迭代多次運算使得所有數(shù)據(jù)點向合適的簇質(zhì)心匯聚,這也是導(dǎo)致算法不穩(wěn)定的根本原因之一,每次開始算法是其啟始“參考”質(zhì)心是隨機選取的[11],每次數(shù)據(jù)收斂的方向和趨勢就可能發(fā)生變化,而且當所選相似性度量方法不同時這種變化會更加明顯。

本文提出的形態(tài)聚類分析則傾向于統(tǒng)計學(xué)[12]方向的質(zhì)心聚類,聚類中心是按照agent特征圖形的融合趨勢所產(chǎn)生的,無需設(shè)定隨機初始點,相比K-means更加穩(wěn)定。

2基于agent圖形特征的形態(tài)學(xué)的聚類分析

聚類分析中K值的確定以及效果最終需要用戶來評價,分為簇的重要原因是這些點在某種意義上具有一定的相似性或趨勢,從而在二維或多維空間形成收斂。這種收斂在視覺上使得相似的數(shù)據(jù)聚集成“一團”——可以通過圖像形態(tài)學(xué)將距離教近的(數(shù)據(jù)點)對象聚合到一起,然后判定其中心。開運算(膨脹)和閉運(腐蝕)算是基礎(chǔ)的形態(tài)運算,其中開運算可表示為

(2)

使用模板B對A進行運算,會將其邊界進行“擴充”,這會產(chǎn)生2個意義:①特征的輪廓按模板被放大——當放大到一定程度時相鄰特征的輪廓會連通到一起,在視覺層面上產(chǎn)生“融合”[13]的效果如圖1所示。②開運算在突出特征輪廓的同時也模糊部分噪聲,這將進一步改善。具體分析流程如下:

·圖像預(yù)處理,包括空間濾波、特征分割、二值化處理等力求得到理想圖像;

·對圖像按膨脹系數(shù)r進行膨脹,相鄰特征會向“連通”趨勢發(fā)展,當這種趨勢增大到一定程度時,位于簇內(nèi)的對象特征會連通從而融合形成一個尺寸較大的新特征;

·計算圖中所有特征的中心位置,可以采用:a)連通分量特征處理獲取連通中心;b)邊緣檢測提取輪廓極值點,然后利用質(zhì)心算法[14]獲取其中心;c)利用形態(tài)學(xué)“bons”做進一步處理后得到中心點。方法b可能因形態(tài)的不同存在較大的誤差,雖可用文獻[15]進行優(yōu)化,但增加了處理的復(fù)雜度;方法c過于復(fù)雜,因此這里選擇方法a進行處理,簡化算法可以在bwlabel直接使用后regionprops得到特征圖像區(qū)域,然后再得到特征區(qū)域的中心k(質(zhì)心),該中心就是形態(tài)學(xué)意義上的聚類中心;連通分量按照(3)計算

(3)

式中，B為結(jié)構(gòu)元,當Xk=Xk-1或|Xk-Xk-1|

·改變r多次迭代(也可采用文獻[16]基于目標跟蹤的思想對連續(xù)運動的動態(tài)圖像進行聚類分析,在較短的時間內(nèi)智能體聚積的趨勢不會發(fā)生較大的變化,下一時刻可沿用當前r值,或者根據(jù)變化的趨勢對r進行小范圍調(diào)整,從而減少計算次數(shù)以節(jié)省大量迭代計算時間)計算使中心向K收斂,直到滿足k=K或達到迭代上限為止。算法流程簡圖如圖3所示。

圖3　算法流程圖

3算法測試

3.1測試數(shù)據(jù)準備

數(shù)據(jù)樣本來源于文獻[17-18]對樣本數(shù)據(jù)進行了描述。為對比算法的穩(wěn)定性和性能,將測試分為2部分:基于數(shù)值的K-means測試部分,由于數(shù)值可以認為是精確的,因此將此部分測試數(shù)據(jù)作為理想的對比基準;將數(shù)值轉(zhuǎn)換為圖形的形態(tài)學(xué)聚類算法測試部分,用以模擬機器視覺獲取的agent數(shù)據(jù)。

由于測試數(shù)據(jù)樣本本身為數(shù)值,因此可直接使用K-means得到測試結(jié)果,而圖像形態(tài)學(xué)測試部分則需要將數(shù)據(jù)樣本以圖形方式展現(xiàn),其生成函數(shù)為:

(plot(Datas(:,1),Datas(:,2),'b.',

'MarkerSize',20);)

(4)

得到基本不受噪聲污染的理想圖像便于簡化測試流程,如圖4所示:

圖4　測試樣本圖片

在樣本圖像中進行數(shù)值對圖像的轉(zhuǎn)換參數(shù)MarkerSize可以參考碰撞測試中常用的ABB包圍盒(泡)[19-20],這里選擇MarkerSize=20在真實系統(tǒng)中可以認為被測對象(如智能體)的尺寸為20(單位),具體使用時不宜過大,因為真實的agent對象是不會在物理空間內(nèi)出現(xiàn)重疊的,而在圖像分析中過大的尺寸可能導(dǎo)致目標數(shù)據(jù)重疊而隱藏數(shù)據(jù)細節(jié),導(dǎo)致誤差增大。圖4中附加了K-means的聚類中心,其生成函數(shù)為:

[Idx,C,sumD,D]=Kmeans(Datas,3,'dist',

'sqEuclidean','rep',20)

(5)

選擇標準歐氏距離,并進行20次迭代計算,得到3個聚類中心,如表1所示:

表1　K-means聚類中心坐標

3.2算法測試與結(jié)果分析

準備好測試樣本后,使用不同的K值對圖像對象進行聚類處理,如圖5所示:

圖5　不同K值的圖像形態(tài)聚類效果圖

當K值較大時,其聚類中心傾向于與對象的圖像特征中心重合,而隨著K值的不斷減小,這種融合更加明顯,如圖5f)達到一個理想態(tài),該聚合良好反映了群體特征的變化。圖像尺寸對圖像處理和形態(tài)分析的影響是較大的,特別在執(zhí)行時間上有很大的影響,在K=3下進行了不同分辨率(DPI[1～250])下聚類誤差和執(zhí)行時間的統(tǒng)計,使用最小二乘插值擬合得到誤差擬合曲線,如圖6所示:

圖6　不同分辨率下的誤差分析對比圖

通過分析可知:

1) 分辨率對算法融合精度影響較小,平均誤差約為3.5%,已能滿足一般agent圖像處理與識別的要求;僅在分辨率較低(<10 DPI)時才出現(xiàn)較大幅度的波動,此時成像素化的圖像對于干擾十分敏感,如圖7所示:

圖7　低分辨率下形態(tài)聚類與數(shù)值聚類效果對比圖

分辨率過低時得到的結(jié)果難以反映真實對象特征(圖7右下小圖),因而形態(tài)聚類和數(shù)值聚類中心出現(xiàn)明顯偏差。

2) 分辨率提高有助于降低誤差,但算法的執(zhí)行時間也會大幅度增加:分辨率30時僅需0.484 4 s,而分辨率80時則需要15.39 s,嚴重降低系統(tǒng)實時性。

3) 圖像特征不會發(fā)生變化,因此當K值一定時,同一副圖像進行形態(tài)聚類得到的中心是一致的,不會出現(xiàn)K-means因隨機選擇起始中心導(dǎo)致的穩(wěn)定性問題;

4) 膨脹系數(shù)存在一定冗余,即一定范圍內(nèi)的膨脹系數(shù)可得相同的K,且分辨率越高,冗余度也越高,如圖8所示:

圖8　膨脹系數(shù)r的甯余度

圖中淺色區(qū)域的DPI為60、r=33形成的特征區(qū)域,而白色邊界為r=41形成的特征區(qū)域,它們的聚類中心點基本上沒有發(fā)生變化(clusterA和clusterA′幾乎重疊,誤差率<0.8%);

5) 膨脹系數(shù)與分辨率成線性關(guān)系,圖像分辨率會直接影響圖片大小,也會影響膨脹系數(shù)r,改變分辨率就會直接改變圖片大小,這符合幾何空間變換的規(guī)律(仿射變換)

(6)

而且采用的是恒等變換

(7)

即在X、Y 2個方向上進行擴展。由于圖像長寬比固定,因此在這里可以得到分辨率和膨脹系數(shù)的關(guān)系(8)所示

r=f(DPI)=?(0.54×DPI)」

(8)

(8)式表達的是一種線性關(guān)系,這為算法優(yōu)化提供了依據(jù):2次拍攝的圖像與分辨率其一般不會有較大的變化,因此可以依據(jù)上一幀圖像的膨脹系數(shù)確定當前幀的r值,從而減少迭代計算的次數(shù)提高計算效率;可通過(8)所示的這種線性關(guān)系快速確定r的大致范圍,將原有的迭代過程簡化為數(shù)次計算,從而大幅度提高運算效率,改進的算法流程圖如圖9所示:

改進算法一般只需1次運算即可得到合適的r值,在受干擾時也只需對r進行1～2次修改即可,改進后的算法執(zhí)行時間對比如圖10所示:

圖10　算法改進前后執(zhí)行時間對比圖

圖10顯示了改進前后的執(zhí)行時間，改進算法即便在250DPI時也不到17s的時間，而改進前則需上千秒，在實際應(yīng)用中是不現(xiàn)實的。

4結(jié)論

形態(tài)特征的聚類分析在多agent協(xié)同控制分析中，使用聚類方法從宏觀上突出群體特征，減少因大量agent識別與定位的計算開銷，從而提升最終決策性能，選擇一定的分辨率有助于在保留足夠信息細節(jié)的同時加快系統(tǒng)的處理速度，使得實時決策成為可能。這種形態(tài)聚類分析不僅可以用于多agent控制，還可以在其他領(lǐng)域如醫(yī)學(xué)影像、冶金、機械等領(lǐng)域得到應(yīng)用。

目前分析過程主要建立在二維數(shù)據(jù)上，對于衛(wèi)星遙感這類數(shù)據(jù)是有效的，但目前較難以應(yīng)用于三維及更高維數(shù)據(jù)的處理中，這是后續(xù)研究空間聚類需要重點解決的問題。

參考文獻：

[1]茹常劍,魏瑞軒,沈東. 多無人機協(xié)同的穩(wěn)定控制機理研究[J]. 物理學(xué)報,2014,63(22):13-19

RuChangjian,WeiRuixuan,ShenDong.StudyonStabilityControlMechanismofMultipleUnmannedAerialVehicleCooperativeSystem[J].ActaPhysicaSinica, 2014, 63(22): 13-19 (inChinese)

[2]LiuZhixin,GuoLei.SynchronizationofMulti-AgentSystemswithoutConnectivityAssumptions[J].Automatica, 2009,45(12): 2744-2753

[3]DydekZacharyT,AnnaswamyAnuradhaM,LavretskyEugene.AdaptiveConfigurationControlofMultipleUAVs[J].ControlEngineeringPractice, 2013, 21(8): 1043-1052

[4]蔡誠,王敏. 結(jié)合分層閾值和形態(tài)學(xué)濾波的小目標檢測方法[J]. 華中科技大學(xué)學(xué)報, 2013,41(1):157-159

CaiCheng,WangMin.SmallTargetDetectionMethodBasedonLayeredThresholdandMorphologyFiltering[J].JournalofHuazhongUniversityofScienceandTechnology, 2013,41(1): 157-159 (inChinese)

[5]胡健,孫金花. 基于系統(tǒng)能量理論的多目標優(yōu)化聚類集成研究[J]. 計算機工程與應(yīng)用,2011,47(36):9-11

HuJian,SunJinhua.Multi-ObjectiveClusterEnsemblewithSystemEnergyTheory[J].ComputerEngineeringandApplications, 2011, 47(36): 9-11 (inChinese)

[6]JanssonJonas,GustafssonFredrik.AFrameworkandAutomotiveApplicationofCollisionAvoidanceDecisionMaking[J].Automatica, 2008, 44(9): 2347-2351

[7]張偉,王軍鋒,王濤,等. 一種基于改進算子的形態(tài)學(xué)邊緣檢測算法[J]. 計算機技術(shù)與發(fā)展,2013,23(6):23-26

ZhangWei,WangJunfeng,WangTao,etal.AnImprovedEdgeDetectionAlgorithmBasedonMorphologicOperators[J].ComputerTechnologyandDevelopment, 2013, 23(6): 23-26 (inChinese)

[8]JesminF,RezaR,SharifMA.ACustomizedGaborFilterforUnsupervisedColorImageSegmentation[J].ImageandVisionComputing, 2009, 27(4): 489-501

[9]DengZhenghong,WangMeijing,BaiXiaoping.ANewMulti-FocusImageFusionAlgorithmBasedonContrastRatioandDiscreteWaveletFrameTransform[C]∥2ndInternationalConferenceonAdvancedEngineeringMaterialsandTechnology, 2012: 1011-1018

[10] 蔡自興,陳白帆,劉麗玨,等. 多移動機器人協(xié)同原理與技術(shù)[M]. 北京:國防工業(yè)出版社,2011: 5-8

CaiZixing,ChengBaifan,Liuliyu,etal.PrinciplesandTechniquesofCooperativeMultipleMobileRobots[M].Beijing,NationalDefenseIndustryPress, 2011: 5-8 (inChinese)

[11] 翟東海,魚江,高飛,等. 最大距離法選取初始簇中心的K-Means文本聚類算法的研究[J]. 計算機應(yīng)用研究, 2014, 31(3): 713-719

ZhaiDonghai,YuJiang,GaoFei,etal.K-MeanstextClusteringAlgorithmBasedonInitialClusterCentersSelectionAccordingtoMaximumDistance[J].ApplicationResearchofComputers, 2014, 31(3): 713-719 (inChinese)

[12] 吳明暉,張紅喜,金蒼宏,等. 一種基于邊緣度密度距的聚類算法[J]. 計算機科學(xué),2014, 41(8): 245-249

WuMinghui,ZhangHongxi,JingCanghong,etal.ClusterAlgorithmBasedonEdgeDensityDistance[J].ComputerScience, 2014, 41(8): 245-249 (inChinese)

[13] 楊鵬. 改進的數(shù)學(xué)形態(tài)學(xué)小波圖像融合算法[J]. 計算機仿真,2011,28(2): 288-291

YangPeng.ImprovedMorphologyWaveletsImageFusionAlgorithm[J].ComputerSimulation, 2011, 28(2): 288-291 (inChinese)

[14] 楊鵬,謝立,劉濟林. 基于Zernike矩的高精度太陽圖像質(zhì)心提取算法[J]. 宇航學(xué)報,2011,32(9):1963-1969

YangPeng,XieLi,LiuJilin.ZernikeMomentBasedHigh-AccuracySunImageCentroidAlgorithm[J].JournalofAstronautics, 2011, 32(9): 1963-1969 (inChinese)

[15] 李虎俊,郭藍天,盧軍,等. 基于二次質(zhì)心的無線傳感器網(wǎng)絡(luò)定位算法[J]. 現(xiàn)代電子技術(shù),2014,(23):37

LiHuJun,GuoLantian,LuJun,etal.TwiceCentroidBasedLocalizationAlgorithmforWirelessSensorNetwork[J].ModernElectronicsTechnique, 2014,(23):37 (inChinese)

[16]DengZhenghong,LiTingting,ZhangTingting.AnAdaptiveTrackingAlgorithmBasedonMeanShift[C]∥2ndInternationalConferenceonAdvancedEngineeringMaterialsandTechnology, 2012: 2607-2613

[17]PeterHarrington.MachineLearninginActionSourceCode[EB/OL].http:∥www.manning-source.com/books/pharrington/MLiA-SourceCode.zip

[18]PeterHarrington. 機器學(xué)習(xí)實戰(zhàn)[M]. 李銳,譯. 北京: 人民郵電出版社,2013: 185-193

PeterHarrington.MachineLearninginAction[M].LiRui,Translator.Beijing,Posts&TelecomPress, 2013: 185-193 (inChinese)

[19] 王偉,馬峻,劉偉. 基于OBB包圍盒的碰撞檢測研究與應(yīng)用[J]. 計算機仿真,2009,26(9): 180-183

WangWei,MaJun,LiuWei.ResearchandApplicationofCollisionDetectionBasedonOrientedBoundingBox[J].ComputerSimulation, 2009, 26(9): 180-183 (inChinese)

[20] 宋城虎,閔林,朱琳,等. 基于包圍盒和空間分解的碰撞檢測算法[J]. 計算機技術(shù)與發(fā)展,2014,24(1): 57-60

SongChenghu,MinLin,ZhuLin,etal.ACollisionDetectionAlgorithmBasedonBoundingBoxandSpatialSubdivision[J].ComputerTechnologyandDevelopment, 2014, 24(1): 57-60 (inChinese)

Clustering Algorithm and its Application Base on Agent Morphology

Li Zhe, Mu Dejun, Zhang Tianfan, Huang Yijie

(School of Automation, Northwestern PolytechnicalUniversity, Xi′an 710072, China)

Abstract:In multi-agent control system, a small amount of Agent showed a greater independence in behavior, but still has some similarity in macro, especially in a situation with more number of Agent is most evident in when the agent number will make the burden of control system of fast-growing and eventually led to the decision to postpone or invalidation. Clustering algorithm based on morphological characteristics of agent is proposed, try clustering research agent with similar behavior, cluster Centre substitute with less amount of agent in order to simplify the analysis of control processes to improve efficiency. Through comparison with K-means clustering algorithm testing and analysis, the algorithm can simplify the complexity; improve system performance, and better stability.

Keywords:cluster analysis; mage morphology; cluster algorithm; matlab; real time control; machine vision; machine learning; K-means algorithm

收稿日期：2015-10-12基金項目：湖北省自然科學(xué)基金(2014CFB576)、湖北工程學(xué)院自然科研項目(z2013016、z201515)及湖北工程學(xué)院新技術(shù)學(xué)院自然科研項目(Hgxky14)資助

作者簡介：李哲(1986—)，西北工業(yè)大學(xué)博士研究生，主要從事網(wǎng)絡(luò)信息安全、智能體協(xié)同控制的研究。

中圖分類號：TP391.4

文獻標志碼：A

文章編號:1000-2758(2016)04-0691-07