基于多Agent进化计算的图像目标识别

周亦鹏，胡 娟，杜军平

（1.北京工商大学计算机与信息工程学院，北京 100048；2.北京政法职业学院信息技术系，北京 100024；3.北京邮电大学计算机学院，北京 100876）

基于多Agent进化计算的图像目标识别

周亦鹏1，胡 娟2，杜军平3

（1.北京工商大学计算机与信息工程学院，北京 100048；2.北京政法职业学院信息技术系，北京 100024；3.北京邮电大学计算机学院，北京 100876）

对图像的多目标识别问题进行研究，提出一种基于Agent进化计算的目标识别方法。该方法通过Agent和Agent群体的协同进化完成对样本图像集的快速搜索和模板匹配。同时，针对目标遮挡的问题，利用遮挡圆来构造模板，实现对遮挡目标的识别。实验结果表明，提出的方法实现了平移不变、旋转不变、尺度不变、镜像不变的识别，而且能够准确地确定出遮挡区域的位置和遮挡区域的大小，同时也大大减小了模板匹配的计算量。

图像处理；目标识别；Agent；进化计算

0 引言

计算机视觉研究中的一个热点问题是图像的目标识别，它的主要任务是通过自动化的方法，在不需要或尽可能少的人工干预情况下，由计算机系统自动识别出图像中出现的特定目标。图像目标识别算法大致可以分为基于模板的方法、基于特征的方法和基于三维模型的方法3类［1-3］。其中，基于模板的方法具有较强的抗噪性，对目标的识别具有平移不变性、尺度不变性等特点，但是计算量相对较大。

因此，本文把模板匹配的思想和多Agent进化计算［4-5］结合起来，在实现目标识别的同时，减少模板匹配的计算量，提高计算效率。

同时，针对遮挡目标识别的问题，考虑到遮挡位置和遮挡区域大小的随机性，以及无法预知遮挡区域的轮廓、纹理等特征，本文提出一种采用遮挡模板的方法来解决遮挡目标识别题，利用Agent构造遮挡模板，在待测图像中同时搜索遮挡目标和遮挡区域。

1 基于模板匹配的图像目标识别

基于模板匹配的目标识别方法，其优点在于不需要掌握图像内容的知识，只要有实际的目标图像数据即可，而且能够保持目标的原始信息。

基于模板的方法根据模板在匹配过程中是否发生变形可以分为刚性模板和变形模板两类。刚性模板是指模板一旦构造完成就不再发生变化，模板匹配过程中，只能将模板进行旋转、缩放等形式的变换，这些变换过程中，模板内各像素间的相对位置要保持不变且不产生任何形变。而变形模板的形状则能够根据测度函数发生变化，目的是使其与目标的形状更为接近。

虽然变形模板能够适应不同形状的目标，但是构造变形模板需要大量的先验知识，因此很多目标识别问题并不适用。而且，多数变形模板的构造仅依赖于目标的轮廓信息，没有充分利用颜色、纹理等其它特征信息，也影响了识别准确性。刚性模板则几乎不需要先验知识，而且能充分地利用目标自身的各种特征，即使是在目标受到部分遮挡的情况下，仍然可以通过未遮挡区域的特征进行识别。

因此，本文采用刚性模板实现目标匹配，将同一类目标的多个样本的平均图像作为模板，从而使同一类型的各个目标均能够获得较高的匹配度。具体方法是：从多个样本图像中剪切出目标的所在区域，获得多个目标图像，并通过插值获得统一的尺度，然后将所有目标图像的灰度值进行标准化。设目标图像I的灰度矩阵为I［W］［H］（W 为图像的宽度，H为高度），计算其均值和方差：

将图像I的灰度值标准化到（μ0，σ0）：

最后求所有目标图像的灰度的平均值，重采样后就得到模板图像。

模板匹配过程是将模板在待测图像上逐点进行平移，依次计算模板与其所覆盖的区域之间的相似度，找出匹配度最高的位置，即要寻找的目标。

设模板T的尺寸为TW×TH，待测图像I的尺寸为W×H（通常TW ＜W，TH ＜H）。待测图像I被模板T所覆盖的区域称为子图S（i，j），其中（i，j）为子图的中心坐标。目标识别过程就是在整幅待测图像中寻找与模板T最为相似的子图S（i，j）。但是，如果采用遍历搜索，将模板与所有子图进行比较，则搜索过程的计算量将十分巨大，因此必须设计有效的方法来降低搜索空间，提高搜索效率。

2 多Agent进化计算

2.1 多Agent进化计算系统的结构

基于模板匹配的图像目标识别实质上是一个组合优化问题，从而能够以较少的计算量获得最优的解决方案。进化计算是解决此类问题的常用方法［6-8］，但随着图像识别难度和复杂度的提高，存在进化缓慢、易于早熟、搜索效率不高等缺点。因此，本文提出一种基于Agent的进化计算方法，利用Agent的智能性、自主性和协作能力［9-10］，将其与进化计算方法相结合，以提高目标识别的准确度和计算效率。

基于Agent的进化计算将进化过程中的每个个体作为一个Agent，所有Agent构成一个群体。同时，一个群体可以进一步划分为若干个子群体。所有子群体分为优胜子群体和临时子群体两类，优胜子群体由全局竞争过程中胜出的Agent构成，临时子群体则包括竞争过程中的其它Agent，如图1所示。

不同于传统的进化计算方法，本文在Agent进化过程中采用“趋同”和“异化”算子。趋同的作用是在子群体内快速搜索局部最优解，然后在各个子群体中选出当前的优胜子群体。异化操作是通过重构子群体，从而在整个解空间中探索全局最优的个体。

系统中的Agent通过公告板实现交互与通信，其中局部公告板用于子群体内Agent间的通信，全局公告板则用于各子群体间的通信。公告板包含Agent个体或子群体的序号（No.）、动作（Action）和得分（Score）等信息。其中，Agent的动作与具体的领域有关，在目标识别领域，动作可以是Agent在待测图像中所处的位置及其下一步的搜索方向；得分则是对Agent动作执行效果的评价。

此外，系统通过特征提取F-Agent对个体Agent的动作和得分进行分析，从中提取环境信息，从而指导异化操作的进行。

图1 多Agent进化计算系统结构Fig.1 Architecture of multi-agent evolution systen

2.2 趋同和异化

Agent进化计算过程中包含趋同和异化两个重要的操作，其中趋同是局部搜索，异化是全局搜索。

子群体中的各个Agent为成为子群体内的优胜者而竞争的过程叫做趋同。当一个子群体内不再产生新的优胜Agent时，则称该子群体已经成熟，此时趋同过程结束。

在整个搜索空间内，所有子群体也在为成为全局优胜者而进行竞争。子群体通过重构来不断地探索新的空间，从而成为新的优胜子群体，这个过程叫做异化。异化包含两种情况：1）若某个临时子群体的得分高于成熟的优胜子群体的得分，则该临时子群体成为新的优胜子群体，并且释放原优胜子群体中的Agent；若某个成熟的临时子群体的得分低于优胜子群体，则释放该临时子群体中的Agent。2）被释放的Agent在整个搜索空间内重新进行散布并形成新的临时群体。

初始情况下，所有的Agent进行全局搜索，然后以其中得分较高的若干个Agent为中心形成多个初始子群体。之后趋同和异化操作在进化过程中反复交替进行。

与传统进化计算相比，基于Agent的进化计算将群体划分为子群体，类似于小生境环境，更易于并行实现。

3 多Agent图像目标识别

3.1 基于多Agent的图像目标识别过程

本文采用多Agent进化计算与模板匹配相结合的方法识别目标，从而减少计算代价，并且通过并行计算来提高识别速度。

首先，每个Agent采用一定大小的窗口从待测图像上剪切一个子图像，然后将子图像与模板图像进行匹配。为了适应目标尺度大小和旋转角度的变化，Agent需要将窗口内的子图像进行缩放、旋转等处理，然后进行匹配。

因此，每个Agent的窗口W 包括4个参数：窗口的中心坐标（i，j）、窗口宽度lw和窗口的旋转角度θ。Agent将获得的窗口子图像再进行尺度缩放后得到与模板大小相同的待匹配图像，称为样本图像，记为Si，j，θ，lw（x，y）。

这样处理的优点是：多个Agent群体可以同时搜索多个区域，与模板图像进行匹配，既能避免陷入局部最优，又能加快处理的速度；通过调整Agent的窗口参数，可以对样本图像进行平移、旋转、缩放，保持目标识别过程的平移、旋转和缩放不变性。

为了评价样本图像和模板之间的匹配度，通过计算模板图像与样本图像色差的累计和来定义评价函数：

其中，Tuv（x，y）和Suv，i，j，θ，lw（x，y）分别为转换到CIE1976L＊u＊v＊均匀颜色空间上的模板图像和样本图像，TW、TH分别是模板图像的宽度和高度。u（x，y）、v（x，y）分别为样本图像的U＊、V＊值，u（x，y）、v（x，y）分别为模板图像的U＊、V＊值。

根据式（4）可以看出，F（i，j，θ，lw）值越小，样本图像和模板的匹配度越高。

3.2 遮挡目标的识别

如何识别被遮挡的目标一直是目标识别中最难解决的问题之一。由于遮挡区域的位置和大小难以预知，同时也无法预先获得遮挡区域的轮廓、纹理等辅助信息，因此传统的模板匹配和特征选择方法都不能很好地解决这一问题。

本文提出一种采用遮挡模板的遮挡目标识别方法。遮挡模板是将目标的遮挡位置定义为某个圆与模板图像的相交区域，然后利用这样的遮挡模板与样本图像进行匹配。通过寻找遮挡圆心、半径等最优的参数组合来解决目标遮挡问题。使用圆定义遮挡区域的优点为：

1）使用圆和模板的相交区域来定义遮挡位置，既可以用来描述边缘遮挡的情况，也可以用来描述孔形遮挡，如图2所示。此外，如果将遮挡位置定义为圆和模板的相交区域的补集，则还适用于镜框遮挡的情况。

2）不论遮挡区域与目标区域的相交线为直线还是曲线都可以用圆形遮挡进行描述，圆半径较大时，相交线可以近似为直线，圆半径较小时相交线是弧线。

由于遮挡圆的位置和大小不确定，因此在模板匹配过程中需要增加圆心的横、纵坐标（a，b）和圆半径（r）3个参数来确定遮挡模板。这样，在整个目标识别过程中共有7维参数来确定受到遮挡的窗口，包括遮挡圆的3维参数（圆心的横纵坐标

和圆半径）和样本图像窗口的4维参数（窗口中心横纵坐标、窗口的宽度和旋转角）。因此，目标识别过程需要使用多Agent系统在样本图像集中进行搜索，获得这7维参数的最优解，从而达到目标识别的目的。

图2 使用圆遮挡住模板Fig.2 Template covered by circularity

4 实验结果

4.1 一般目标的实验结果

采用图3所示的刚性模板来识别图4中的多个目标，每个目标分别用字母A-G进行标记。

根据多Agent进化系统优化的结果，将最优的个体（即找到的目标）用方框标示出来。

图4的7个目标中，识别出A-F共6个目标。可以看出，目标A、B与目标D之间的旋转角度具有很大的差别，这说明了算法具有很好旋转不变性。由于水流和光照的影响，每个目标上具有不同的水纹，而且目标B与其它几个目标还具有较大的颜色差异，这些目标均能被正确识别，说明算法具有彩色恒定性。但是，由于目标G的一部分被目标E所遮挡，因此没有识别出来。

图4中，若采用遍历法进行识别，则搜索计算量达33 751万次，而本文方法识别出6个目标共进化79代，评价个体1.59万次，可见使用多Agent进化计算方法极大减小了计算量。

图3 模板图像Fig.3 Template Image

4.2 遮挡目标的实验结果

针对前一实验中目标G因遮挡而未能识别的问题，采用3.2节提出的遮挡目标识别方法进行实验，待测图像的识别结果如图5所示，同时得到的遮挡位置如图6所示。

图4 待测图像和识别结果Fig.4 Test image and recognition result

图5 遮挡目标的实验结果Fig.5 Recognition result of covered object

图6 目标E和G的差图像及遮挡圆位置Fig.6 Diffevence images of object E and G and their covered circularity

从实验中看出，样本图像中的目标E在窗口剪切的过程中并没有完整保留，而目标G也有相当一部分被E所遮挡。从图5的识别结果可以看出，使用本文提出的遮挡目标识别方案，两个目标均能准确地找到，并识别出目标的遮挡位置。

5 结论

本文提出一种改进的图像目标识别算法，将基于模板匹配的目标识别方法和性能优异的Agent进化计算结合起来。同时，采用遮挡圆来构造遮挡模板，解决了遮挡目标的识别问题。实验结果表明，本文算法不但能够在目标识别过程中保持平移不变性、旋转不变性和尺度不变性，而且能够有效识别被遮挡的目标并定位遮挡区域。同时，模板匹配的计算量也大大地减少。

［1］田娟，郑郁正.模板匹配技术在图像识别中的应用［J］.传感器与微系统，2008，27（1）：112-114，117.

Tian Juan，ZhengYuzheng.Application of template matching technique in image recognition［J］.Transducer and Microsystem Technologies，2008，27（1）：112-114，117.

［2］Roy Kaushik，Bhattacharya Prabir.Iris recognition using genetic algorithms and asymmetricalSVMs［J］.Machine Graphics and Vision，2010，19（1）：33-62.

［3］Zhang Changjiang，Lu Juan.Satellite cloud image enhancement by genetic algorithm with fuzzy technique［C］//2009In-ternational Conference on New Trends in Information and Service Science，NISS2009.Beijing，2009：1090-1095.

［4］姜楠，张春森.遗传算法在图像模板匹配中的应用［J］.红外与激光工程，2008，37（4）：324-327.

Jiang Nan，Zhang Chunsen.Application of genetic algorithm in image matching［J］.Infrared and Laser Engineering，2008，37（4）：324-327.

［5］刘其成，郑纬民.多Agent并行遗传算法在地震勘探属性优化中的应用［J］.计算机科学，2010，37（4）：234-237.

Liu Qicheng，Zheng Weimin.Seismic exploration attribute optimization based on multi-agent parallel genetic algorithm［J］.Computer Science，2010，37（4）：234-237.

［6］梁军，程显毅.基于混合蚁群遗传算法的Agent联盟求解［J］.计算机科学，2009，36（4）：227-231.

Liang Jun，Cheng Xianyi.Solving method of agent coalition problem based on hybrid ant colony and genetic algorithm［J］.Computer Science，2009，36（4）：227-231.

［7］Ugur A，Korukoglu S，Caliskan A，et al.Genetic algorithm based solution for TSP on a sphere［J］.Mathematical and Computational Applications，2009，14（3）：219-228.

［8］马永杰，马义德，蒋兆远，等.一种快速遗传算法及其收敛性［J］.系统工程与电子技术，2009，31（3）：714-718.

Ma Yongjie，Ma Yide，Jiang Zhaoyuan，et al.Fast genetic algorithm and its convergence［J］.Systems Engineering and Electronics，2009，31（3）：714-718.

［9］彭军，刘亚，吴敏，等.基于状态预测的多智能体动态协作算法［J］.系统仿真学报，2008，20（20）：5511-5515.

Peng Jun，Liu Ya，Wu Min，et al.Dynamic cooperation algorithm in multi-agent system based on state prediction［J］.Journal of System Simulation，2008，20（20）：5511-5515.

［10］张秋花，薛惠锋，吴介军，等.多智能体系统MAS及其应用［J］.计算机仿真，2007，24（6）：133-137.

Zhang Qiuhua，Xue Huifeng，Wu Jiejun，et al.Theory and application of the multi-agent system［J］.Computer Simulation，2007，24（6）：133-137.

Image Object Recognition Based on Multi-Agent Evolutionary Computation

ZHOU Yi-peng1，HU Juan2，DU Jun-ping3
（1.School of Computer Science and Information Engineering，Beijing Technology and Business University，Beijing 100048，China；2.Department of Information Technology，Beijing College of Politics and Law，Beijing 100024，China 3.School of Computer Science，Beijing University of Posts and Telecommunications Beijing，100876，China）

Image objects recognition is studied.A new object recognition method based on Agent evolutionary computation is proposed.In this method，the processes of searching object on sample image set and template matching are all achieved by cooperation of Agent groups.Moreover，to solve the problem of occluded object recognition，a new method using occluding circle to construct template is proposed too.The experimental results show that the proposed method has the features of translation invariance，rotation invariance，scale invariance and mirror invariance，at the same time，the occluded area can be located.Furthermore，the computation amount of template matching is greatly reduced.

image processing；object recognition；Agent；evolutionary computation

TP391.9

A

1672-3813（2013）03-0055-06

2012-12-04

国家重点基础研究发展计划（973计划）（2012CB821206）；国家自然科学基金（91024001，61070142）；北京市自然科学基金（4111002）

周亦鹏（1976-），男，山西太原人，博士，讲师，主要研究方向为智能系统。

（责任编辑 耿金花）