多智能体协同控制十分复杂[1]，在复杂背景环境下的大数量智能体分析与控制则更加困难，如复杂战场背景环境下的兵团战斗——在未来很有可能演变为以无人/有人控制的智能体系统的对抗[2]。目前在多agent[3]系统控制中，少量agent在行为上表现出较强的独立性，一般分析与控制过程也是建立在这种单个个体的分析上[4]，但多agent在宏观上依然具有一定的相似性，当其规模较大时这种相似性会更加明显[5]，但agent数量的增加会导致控制系统负担快速增长并导致决策延迟或无效化，因而可以通过聚类的方法将这些智能体按照一定的规则进行分类，从而简化分析过程，能够从宏观层面对多智能体协同控制提供决策支持(而且当智能体数量增加时不会导致计算代价的明显提升)。在已有的智能体控制、聚类分析中[6]，机器视觉[7, 8]是常用的手段，图像包含丰富信息的同时也容易产生噪声以及过冗信息(特别是当来自多个不同传感器的图像需要进行融合时则会产生更多冗余[9])，会降低系统正确率以及处理效率，已有的文献大多集中在图像相似度或对象识别本身，本文提出一种基于形态特征的聚类算法，利用agent形态特征和图像形态融合消除噪声，同时将具有相似行为的agent进行聚类研究，以较少的聚类中心替代数量庞大的agent以简化分析控制流程以提高效率。
1 系统分析模型聚类分析是无监督的机器学习中常用的方法，也被广泛应用于多agent行为分析与控制上。相似的对象会因为某些属性形成聚集趋势，这种趋势也会在视觉上呈现，因此可以利用这种“聚集趋势”构成图像形态处理并在该基础上再进行聚类分析，属于同一类的对象会倾向于聚集到一起，它们之间的距离相比于该类以外的对象要近得多，因此其在图像形态上的距离也会较近，经过形态处理(主要为开运算)后其图像特征会具有融合趋势，如图 1所示。
|
| 图 1 对图像进行形态处理后其呈现较强的特征 |
图 1a)原始数据之间并没有明显的关联，使用系数r1对原始图像进行膨胀后部分特征产生了融合，如图 1b)左下角方框圈中区域所示，在使用系数r2对图像处理后这种融合趋势更加明显了，图 1c)和图 1d)从结果上来看是图形的“连通”。
在对agent运动进行分析时(选择其位置作为聚类数据)一方面可利用多种传感器获取其位置参数，也可选择包含更多信息机器视觉作为数据采集系统，在宏观层面看来类似于集中式协作模型[10]，例如卫星拍摄战场后通过图像处理获得各单位(包括智能体)的相对位置数据，然后对该数据进行聚类分析，分析流程框图如图 2所示：
|
| 图 2 算法框架示意图 |
选用机器学习中广泛应用的K-means算法作为对比验证算法，它属于分割式聚类算法，目的是使各簇中的数据点与所在簇质心的误差平方和最小：
K-means需要数值型数据来进行相似性度量,由用户提供聚类数K,然后再按照如距离、欧式距离、绝对误差和等方式进行聚类计算。其优点是容易实现,缺点是可能收敛到局部最小值,在大规模数据集上收敛较慢。此外因其在算法开始前随机确定K个初始点作为质心,然后再以SSE迭代多次运算使得所有数据点向合适的簇质心汇聚,这也是导致算法不稳定的根本原因之一,每次开始算法是其启始“参考”质心是随机选取的[11],每次数据收敛的方向和趋势就可能发生变化,而且当所选相似性度量方法不同时这种变化会更加明显。
本文提出的形态聚类分析则倾向于统计学[12]方向的质心聚类,聚类中心是按照agent特征图形的融合趋势所产生的,无需设定随机初始点,相比K-means更加稳定。
2 基于agent图形特征的形态学的聚类分析聚类分析中K值的确定以及效果最终需要用户来评价,分为簇的重要原因是这些点在某种意义上具有一定的相似性或趋势,从而在二维或多维空间形成收敛。这种收敛在视觉上使得相似的数据聚集成“一团”——可以通过图像形态学将距离教近的(数据点)对象聚合到一起,然后判定其中心。开运算(膨胀)和闭运(腐蚀)算是基础的形态运算,其中开运算可表示为
使用模板B对A进行运算,会将其边界进行“扩充”,这会产生2个意义:①特征的轮廓按模板被放大——当放大到一定程度时相邻特征的轮廓会连通到一起,在视觉层面上产生“融合”[13]的效果如图 1所示。②开运算在突出特征轮廓的同时也模糊部分噪声,这将进一步改善。具体分析流程如下:
·图像预处理,包括空间滤波、特征分割、二值化处理等力求得到理想图像;
·对图像按膨胀系数r进行膨胀,相邻特征会向“连通”趋势发展,当这种趋势增大到一定程度时,位于簇内的对象特征会连通从而融合形成一个尺寸较大的新特征;
·计算图中所有特征的中心位置,可以采用:a)连通分量特征处理获取连通中心;b)边缘检测提取轮廓极值点,然后利用质心算法[14]获取其中心;c)利用形态学“bons”做进一步处理后得到中心点。方法b可能因形态的不同存在较大的误差,虽可用文献[15]进行优化,但增加了处理的复杂度;方法c过于复杂,因此这里选择方法a进行处理,简化算法可以在bwlabel直接使用后regionprops得到特征图像区域,然后再得到特征区域的中心k(质心),该中心就是形态学意义上的聚类中心;连通分量按照(3)计算
·改变r多次迭代(也可采用文献[16]基于目标跟踪的思想对连续运动的动态图像进行聚类分析,在较短的时间内智能体聚积的趋势不会发生较大的变化,下一时刻可沿用当前r值,或者根据变化的趋势对r进行小范围调整,从而减少计算次数以节省大量迭代计算时间)计算使中心向K收敛,直到满足k=K或达到迭代上限为止。算法流程简图如图 3所示。
|
| 图 3 算法流程图 |
数据样本来源于文献[17, 18]对样本数据进行了描述。为对比算法的稳定性和性能,将测试分为2部分:基于数值的K-means测试部分,由于数值可以认为是精确的,因此将此部分测试数据作为理想的对比基准;将数值转换为图形的形态学聚类算法测试部分,用以模拟机器视觉获取的agent数据。
由于测试数据样本本身为数值,因此可直接使用K-means得到测试结果,而图像形态学测试部分则需要将数据样本以图形方式展现,其生成函数为:
得到基本不受噪声污染的理想图像便于简化测试流程,如图 4所示:
|
| 图 4 测试样本图片 |
在样本图像中进行数值对图像的转换参数MarkerSize可以参考碰撞测试中常用的ABB包围盒(泡)[19, 20],这里选择MarkerSize=20在真实系统中可以认为被测对象(如智能体)的尺寸为20(单位),具体使用时不宜过大,因为真实的agent对象是不会在物理空间内出现重叠的,而在图像分析中过大的尺寸可能导致目标数据重叠而隐藏数据细节,导致误差增大。图 4中附加了K-means的聚类中心,其生成函数为:
选择标准欧氏距离,并进行20次迭代计算,得到3个聚类中心,如表 1所示:
准备好测试样本后,使用不同的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形成的特征区域,它们的聚类中心点基本上没有发生变化(cluster A和cluster A′几乎重叠,误差率＜0.8％);
5) 膨胀系数与分辨率成线性关系,图像分辨率会直接影响图片大小,也会影响膨胀系数r,改变分辨率就会直接改变图片大小,这符合几何空间变换的规律(仿射变换)
而且采用的是恒等变换
即在X、Y 2个方向上进行扩展。由于图像长宽比固定,因此在这里可以得到分辨率和膨胀系数的关系(8)所示
(8)式表达的是一种线性关系,这为算法优化提供了依据:2次拍摄的图像与分辨率其一般不会有较大的变化,因此可以依据上一帧图像的膨胀系数确定当前帧的r值,从而减少迭代计算的次数提高计算效率;可通过(8)所示的这种线性关系快速确定r的大致范围,将原有的迭代过程简化为数次计算,从而大幅度提高运算效率,改进的算法流程图如图 9所示:
|
| 图 9 改进的算法流程图 |
改进算法一般只需1次运算即可得到合适的r值,在受干扰时也只需对r进行1～2次修改即可,改进后的算法执行时间对比如图 10所示:
|
| 图 10 算法改进前后执行时间对比图 |
图 10显示了改进前后的执行时间，改进算法即便在250DPI时也不到17 s的时间，而改进前则需上千秒，在实际应用中是不现实的。
4 结 论形态特征的聚类分析在多agent协同控制分析中，使用聚类方法从宏观上突出群体特征，减少因大量agent识别与定位的计算开销，从而提升最终决策性能，选择一定的分辨率有助于在保留足够信息细节的同时加快系统的处理速度，使得实时决策成为可能。这种形态聚类分析不仅可以用于多agent控制，还可以在其他领域如医学影像、冶金、机械等领域得到应用。
目前分析过程主要建立在二维数据上，对于卫星遥感这类数据是有效的，但目前较难以应用于三维及更高维数据的处理中，这是后续研究空间聚类需要重点解决的问题。
| [1] |
茹常剑,魏瑞轩,沈东. 多无人机协同的稳定控制机理研究[J]. 物理学报,2014,63(22):13-19 Ru Changjian, Wei Ruixuan, Shen Dong. Study on Stability Control Mechanism of Multiple Unmanned Aerial Vehicle Cooperative System[J]. Acta Physica Sinica, 2014, 63(22): 13-19 (in Chinese) |
| Click to display the text | |
| [2] | Liu Zhixin, Guo Lei. Synchronization of Multi-Agent Systems without Connectivity Assumptions[J]. Automatica, 2009,45(12): 2744-2753 |
| Click to display the text | |
| [3] | Dydek Zachary T, Annaswamy Anuradha M, Lavretsky Eugene. Adaptive Configuration Control of Multiple UAVs[J]. Control Engineering Practice, 2013, 21(8): 1043-1052 |
| Click to display the text | |
| [4] |
蔡诚,王敏. 结合分层阈值和形态学滤波的小目标检测方法[J]. 华中科技大学学报, 2013,41(1):157-159 Cai Cheng, Wang Min. Small Target Detection Method Based on Layered Threshold and Morphology Filtering[J]. Journal of Huazhong University of Science and Technology, 2013,41(1): 157-159 (in Chinese) |
| Cited By in Cnki (1) | |
| [5] |
胡健,孙金花. 基于系统能量理论的多目标优化聚类集成研究[J]. 计算机工程与应用,2011,47(36):9-11 Hu Jian, Sun Jinhua. Multi-Objective Cluster Ensemble with System Energy Theory[J]. Computer Engineering and Applications, 2011, 47(36): 9-11 (in Chinese) |
| Cited By in Cnki (1) | |
| [6] | Jansson Jonas, Gustafsson Fredrik. A Framework and Automotive Application of Collision Avoidance Decision Making[J]. Automatica, 2008, 44(9): 2347-2351 |
| Click to display the text | |
| [7] |
张伟,王军锋,王涛,等. 一种基于改进算子的形态学边缘检测算法[J]. 计算机技术与发展,2013,23(6):23-26 Zhang Wei, Wang Junfeng, Wang Tao, et al. An Improved Edge Detection Algorithm Based on Morphologic Operators[J]. Computer Technology and Development, 2013, 23(6): 23-26 (in Chinese) |
| Cited By in Cnki (15) | |
| [8] | Jesmin F, Reza R, Sharif M A. A Customized Gabor Filter for Unsupervised Color Image Segmentation[J]. Image and Vision Computing, 2009, 27(4): 489-501 |
| Click to display the text | |
| [9] | Deng Zhenghong, Wang Meijing, Bai Xiaoping. A New Multi-Focus Image Fusion Algorithm Based on Contrast Ratio and Discrete Wavelet Frame Transform[C]//2nd International Conference on Advanced Engineering Materials and Technology, 2012: 1011-1018 |
| Click to display the text | |
| [10] |
蔡自兴,陈白帆,刘丽珏,等. 多移动机器人协同原理与技术[M]. 北京:国防工业出版社,2011: 5-8 Cai Zixing, Cheng Baifan, Liu liyu, et al. Principles and Techniques of Cooperative Multiple Mobile Robots[M]. Beijing, National Defense Industry Press, 2011: 5-8 (in Chinese) |
| [11] |
翟东海,鱼江,高飞,等. 最大距离法选取初始簇中心的K-Means文本聚类算法的研究[J]. 计算机应用研究, 2014, 31(3): 713-719 Zhai Donghai, Yu Jiang, Gao Fei, et al. K-Means text Clustering Algorithm Based on Initial Cluster Centers Selection According to Maximum Distance[J]. Application Research of Computers, 2014, 31(3): 713-719 (in Chinese) |
| Cited By in Cnki (27) | |
| [12] |
吴明晖,张红喜,金苍宏,等. 一种基于边缘度密度距的聚类算法[J]. 计算机科学,2014, 41(8): 245-249 Wu Minghui, Zhang Hongxi, Jing Canghong, et al. Cluster Algorithm Based on Edge Density Distance[J]. Computer Science, 2014, 41(8): 245-249 (in Chinese) |
| Cited By in Cnki (5) | |
| [13] |
杨鹏. 改进的数学形态学小波图像融合算法[J]. 计算机仿真,2011,28(2): 288-291 Yang Peng. Improved Morphology Wavelets Image Fusion Algorithm[J]. Computer Simulation, 2011, 28(2): 288-291 (in Chinese) |
| Cited By in Cnki (10) | |
| [14] |
杨鹏,谢立,刘济林. 基于Zernike矩的高精度太阳图像质心提取算法[J]. 宇航学报,2011,32(9):1963-1969 Yang Peng, Xie Li, Liu Jilin. Zernike Moment Based High-Accuracy Sun Image Centroid Algorithm[J]. Journal of Astronautics, 2011, 32(9): 1963-1969 (in Chinese) |
| Cited By in Cnki (8) | |
| [15] |
李虎俊,郭蓝天,卢军,等. 基于二次质心的无线传感器网络定位算法[J]. 现代电子技术,2014,(23):37 Li HuJun, Guo Lantian, Lu Jun, et al. Twice Centroid Based Localization Algorithm for Wireless Sensor Network[J]. Modern Electronics Technique, 2014,(23):37 (in Chinese) |
| Click to display the text | |
| [16] | Deng Zhenghong, Li Tingting, Zhang Tingting. An Adaptive Tracking Algorithm Based on Mean Shift[C]//2nd International Conference on Advanced Engineering Materials and Technology, 2012: 2607-2613 |
| [17] | Peter Harrington. Machine Learning in Action Source Code [EB/OL]. http://www.manning-source.com/books/pharrington/MLiA_SourceCode.zip |
| [18] |
Peter Harrington. 机器学习实战[M]. 李锐,译. 北京: 人民邮电出版社,2013: 185-193 Peter Harrington. Machine Learning in Action[M]. Li Rui, Translator. Beijing, Posts & Telecom Press, 2013: 185-193 (in Chinese) |
| [19] |
王伟,马峻,刘伟. 基于OBB包围盒的碰撞检测研究与应用[J]. 计算机仿真,2009,26(9): 180-183 Wang Wei, Ma Jun, Liu Wei. Research and Application of Collision Detection Based on Oriented Bounding Box[J]. Computer Simulation, 2009, 26(9): 180-183 (in Chinese) |
| Cited By in Cnki (52) | |
| [20] |
宋城虎,闵林,朱琳,等. 基于包围盒和空间分解的碰撞检测算法[J]. 计算机技术与发展,2014,24(1): 57-60 Song Chenghu, Min Lin, Zhu Lin, et al. A Collision Detection Algorithm Based on Bounding Box and Spatial Subdivision[J]. Computer Technology and Development, 2014, 24(1): 57-60 (in Chinese) |
| Cited By in Cnki (11) |
