基于agent形態特征的聚類分析研究與應用

李哲, 慕德俊, 張天凡, 黃一杰

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

?

基于agent形態特征的聚類分析研究與應用

李哲, 慕德俊, 張天凡, 黃一杰

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

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

關鍵詞：圖像形態學；聚類分析；機器視覺；機器學習；K-means算法

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

1系統分析模型

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

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

圖1　對圖像進行形態處理后其呈現較強的特征

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

圖2　算法框架示意圖

選用機器學習中廣泛應用的K-means算法作為對比驗證算法，它屬于分割式聚類算法，目的是使各簇中的數據點與所在簇質心的誤差平方和最小：

(1)

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

本文提出的形態聚類分析則傾向于統計學[12]方向的質心聚類,聚類中心是按照agent特征圖形的融合趨勢所產生的,無需設定隨機初始點,相比K-means更加穩定。

2基于agent圖形特征的形態學的聚類分析

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

(2)

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

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

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

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

(3)

式中，B為結構元,當Xk=Xk-1或|Xk-Xk-1|

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

圖3　算法流程圖

3算法測試

3.1測試數據準備

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

由于測試數據樣本本身為數值,因此可直接使用K-means得到測試結果,而圖像形態學測試部分則需要將數據樣本以圖形方式展現,其生成函數為:

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

'MarkerSize',20);)

(4)

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

圖4　測試樣本圖片

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

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

'sqEuclidean','rep',20)

(5)

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

表1　K-means聚類中心坐標

3.2算法測試與結果分析

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

圖5　不同K值的圖像形態聚類效果圖

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

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

通過分析可知:

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

圖7　低分辨率下形態聚類與數值聚類效果對比圖

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

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

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

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

圖8　膨脹系數r的甯余度

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

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

(6)

而且采用的是恒等變換

(7)

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

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

(8)

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

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

圖10　算法改進前后執行時間對比圖

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

4結論

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

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

參考文獻：

[1]茹常劍,魏瑞軒,沈東. 多無人機協同的穩定控制機理研究[J]. 物理學報,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]蔡誠,王敏. 結合分層閾值和形態學濾波的小目標檢測方法[J]. 華中科技大學學報, 2013,41(1):157-159

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

[5]胡健,孫金花. 基于系統能量理論的多目標優化聚類集成研究[J]. 計算機工程與應用,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]張偉,王軍鋒,王濤,等. 一種基于改進算子的形態學邊緣檢測算法[J]. 計算機技術與發展,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] 蔡自興,陳白帆,劉麗玨,等. 多移動機器人協同原理與技術[M]. 北京:國防工業出版社,2011: 5-8

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

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

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

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

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

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

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

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

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

[15] 李虎俊,郭藍天,盧軍,等. 基于二次質心的無線傳感器網絡定位算法[J]. 現代電子技術,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. 機器學習實戰[M]. 李銳,譯. 北京: 人民郵電出版社,2013: 185-193

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

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

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

[20] 宋城虎,閔林,朱琳,等. 基于包圍盒和空間分解的碰撞檢測算法[J]. 計算機技術與發展,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基金項目：湖北省自然科學基金(2014CFB576)、湖北工程學院自然科研項目(z2013016、z201515)及湖北工程學院新技術學院自然科研項目(Hgxky14)資助

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

中圖分類號：TP391.4

文獻標志碼：A

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