基于场景复杂度的移动机器人目标搜索方法的研究

马志伟， 金小峰

（延边大学工学院计算机科学与技术系 智能信息处理研究室，吉林 延吉133002）

基于场景复杂度的移动机器人目标搜索方法的研究

马志伟， 金小峰＊

（延边大学工学院计算机科学与技术系 智能信息处理研究室，吉林 延吉133002）

借鉴人类搜索经验，将场景复杂度概念应用到移动机器人目标搜索过程，提出了一种基于场景复杂度的移动机器人目标搜索方法．首先，通过分析影响场景复杂度的主要因素，给出了融合图像和激光深度信息的场景复杂度形式化定义；其次，结合视觉目标检测过程，描述了基于场景复杂度的目标搜索方法，该方法通过对各个场景按复杂度进行筛选来确定待搜索场景，并根据场景深度信息确定该场景的待搜索点．实验结果表明：本文提出的场景复杂度计算方法符合人的复杂度主观感受，较好地反映了场景的内在特征；基于场景复杂度的目标搜索方法可以有效地搜索目标，具有较好的鲁棒性．

移动机器人；目标搜索；环境探索；场景复杂度

0 引言

移动机器人是机器人研究领域的重要分支，它集中体现了人工智能与信息科学的最新成果，在事故救援、军事侦察、爆炸物搜索与处理、防止核污染等方面有着广泛的应用［1］．在多数应用中，移动机器人必须首先具备物品识别和目标搜索的能力，然后才能对目标进行进一步处理．移动机器人目标搜索属于最优搜索理论与机器人自动化相结合的前沿课题，研究内容除了搜索理论，还涉及到环境感知、环境探索、运动控制和模式识别等多个研究内容，是移动机器人领域最具挑战的研究课题之一［2］．

针对未知环境移动机器人视觉目标搜索问题，国内外学者进行了广泛研究．Ye和Tsotsos［3］证明了3－D空间的视觉目标搜索是1个N－P完备性问题．Connolly［4］认为，搜索过程中的视角选择问题类似于未知场景中获得新的观察数据的场景重建问题．为了降低搜索代价，Alper［5］提出了1种间接搜索方法，即首先搜索与目标有关的“中间对象”，然后根据空间关联关系指导目标搜索过程．Shubina和Tsotsos［6］将视觉注意引入了视觉搜索过程，利用视觉注意的内在优化机制改善目标搜索进程，提高了搜索效率．此外，很多学者对多机器人目标搜索问题也进行了广泛的研究［7－8］．上述搜索方法多数需要在特定假设条件下才能完成，不具有通用性，因此，本文借鉴人类的搜索经验，将复杂度概念应用到移动机器人目标搜索任务中，提出一种基于场景复杂度的移动机器人目标搜索方法．该方法有效地整合了未知环境探索和目标检测，通过分析各场景的复杂度指导目标搜索过程，算法结构简单、通用性良好，在真实环境搜索实验中取得了很好的实验结果．

1 场景复杂度

在目标搜索过程中，人们往往对那些隐蔽、杂乱、不规则的场景给予更多的关注，认为目标在这些场景中出现的可能性更大，因而，场景的复杂程度直接决定了搜索的方向．根据生理学和神经学研究发现，人类从视觉场景中可以获得由二维图像信息和一维深度信息构成的三维场景信息，所以对于场景的复杂度分析也需要在图像和深度2个方面进行．本文借助单目视觉传感器和激光深度测距传感器获得相应的三维场景信息．机器人目标搜索过程中的场景复杂度计算方法如公式（1）所示：

其中fc（I）为视觉图像数据I提供的图像复杂度，fc（D）为激光深度数据D提供的深度复杂度，wi和wd分别为图像和深度在总体场景复杂度中的归一化影响因子．

1．1 场景图像复杂度

图像复杂度是对图像内在复杂程度的描述，文献［9］提出了1种综合整体、区域、目标角度的图像复杂度描述方法，该方法通过计算图像的信息熵、纹理特征和边缘比率获得图像的复杂度．对于目标搜索任务，为使复杂度计算有利于目标搜索过程，本文在此基础上引入了图像显著性和目标似然度2部分，具体计算方法如下描述．

如果1幅图像中显著性区域较多，则表明图像比较复杂．一般认为，显著性就是稀有性，但它同时还会受到尺度的影响，选择不同尺度的特征会产生不同的显著性区域．当前，显著性区域提取的方法有很多种［10］，但要获得越好的效果其相应的计算代价就越大．鉴于此，本文采用文献［11］提出的基于DCT系数稀疏编码的方法进行显著性区域提取，并将其转化为图像复杂度的评价指标，如式（2）和（3）所示：

其中sign（·）为符号函数，dct2（·）和idct2（·）为图像的正、逆DCT变换函数，I′为变换后的图像，M和N分别为图像的行数和列数，PI′为I′阈值化后显著性区域像素的总个数．

目标似然度是指目标在场景中被检测出的概率，不同于目标识别的精确检测，它给出的是场景中与目标相似的区域比例．目标似然度可以利用目标图像与场景图像的颜色直方图反向投影图像计算得出，其计算方法如式（4）所示：

其中Pproject为场景图像对应的目标颜色直方图反向投影图像中非零像素数．

整合纹理TI、显著性SI、边缘比率RI和目标似然度LI，图像复杂度计算方法如公式（5）所示，其中wi1、wi2、wi3和wi4分别为4个部分的归一化影响因子．

其中σ为方差，μ为均值，wd1和wd2分别为方差σ和均值μ的归一化影响因子．

1．2 场景深度复杂度

场景深度反映了场景中物品的距离变化，距离变化越剧烈，说明分布越混乱，对应场景整体越复杂；同时，若场景深度的平均距离越大，表明场景空间越大，相应场景也就越复杂．本文采用变异系数与平均距离的加权来计算场景深度复杂度fc（D），如式（6）所示：

2 视觉目标搜索方法

针对室内未知环境静止视觉目标搜索问题，本文提出了基于场景复杂度的目标搜索方法，该方法采用文献［12］中提出的Harris－SIFT局部不变特征作为目标模型进行视觉目标检测，并利用上文中的场景复杂度计算方法对各个场景进行筛选，并保留复杂的场景做进一步的搜索．假定待搜索目标只为1种，数量为n，借助激光测距和单目视觉传感器，其相应算法描述如下：

算法1 基于场景复杂度的目标搜索．

输入：待搜索目标O和相应的目标分类器C，机器人起始定位P，搜索点链表L，最大搜索时间Tmax．

输出：目标定位列表Pos＿List，机器人搜索轨迹Path，环境地图m．

步骤1 根据起始定位P初始化环境地图m，清空待搜索点链表L；

步骤2 获得机器人当前位置对应的各个场景信息，更新环境地图m，并将当前定位信息存入Path；

步骤3 利用目标检测算法对各个场景进行精确目标检测，若目标被检测到且并未在Pos＿List中出现过，则将此定位信息放入Pos＿List中；否则，按式（1）计算此场景的复杂度；

步骤4 保留复杂度大于给定阈值φ的场景；

步骤5 依据激光深度数据depth计算各个场景的中心位置，并增加最大搜索距离约束，判断其是否满足待搜索条件，若满足，则将其存入待搜索点链表L中；

步骤6 从待搜索点链表L中选择当前待搜索点，利用A＊算法进行路径规划，确定可行路径，执行搜索过程，并将其从待搜索点链表中删除；

步骤7 重复执行步骤2—步骤6，直到待搜索点链表为空或搜索时间超过Tmax．

从该算法的描述中可知，复杂度阈值在目标搜索过程中起到了重要的作用，不同复杂度阈值将产生不同类型的搜索结果：阈值越小，搜索越精细；阈值越大，搜索越粗糙．

3 实验结果及分析

为了验证本文方法的有效性，在室内环境进行多组实验．实验平台为AS－R移动机器人（携带车载计算机，Pentium（R）4 3．00 GHz，1 G RAM），见图1．实验环境如图2和图3所示．

在实验中，设机器人的行驶速度为0．3 m/s，单目视觉采样率为15帧/s，激光传感器的响应时间为26 ms，角度分辨率为0．5°，距离分辨率为10 mm，扫描范围为180°，环境栅格地图的比例尺为1∶50 mm．

图1 AS－R移动机器人

图2 实验环境1

图3 实验环境2

由于单目视觉的水平视域为60°，故需要在同1个位置转动5次才能获取与当前位置对应的360°范围内的6个不重叠场景信息（图像和激光测距数据）．同时，在场景复杂度计算过程中，需要利用与视觉重合的中间60°范围内的激光测距数据．

1）场景复杂度实验 实验在图3所示的环境中进行．图4从左到右、从上到下分别为6个不同视角的场景图像和场景深度信息，表1为其对应的复杂度信息．

图4 环境1中不同朝向的场景信息

表1 环境1的场景复杂度

从图4和表1可以看出：场景复杂度的计算结果与人的复杂度主观感受一致，较好地反映了场景的内在特征．尽管场景a的深度复杂度比场景d大，但场景d的图像复杂度远大于场景a，因而总体上场景d的场景复杂度大于场景a．场景c和场景e的图像复杂度比较接近，但由于场景c中的黑色物体吸收了部分激光信号，产生了较大的偏差，使得场景c的深度复杂度大于场景e，故场景c的场景复杂度大于场景e．对于复杂度计算公式中的权值确定问题，通常与特定任务性质和环境类型相关，可通过实验加以确定．

2）视觉目标搜索实验 为验证复杂度阈值与目标搜索之间的关系，对不同复杂度阈值下的搜索实验进行了对比．实验过程中，假定未知环境中仅存在1个静止的待搜索目标，各算法按最近邻原则选择下1个待搜索点，算法终止条件为找到既定目标或无待搜索点．

搜索实验在图2和图3所示的环境中进行，每组实验在同一环境中的3个不同起点运行2次，目标放置在与起点不同的位置，各评价指标取6次实验的平均值，场景复杂度阈值分别设为0．00、0．15、0．25、0．35、0．45、0．55．搜索算法性能评价指标由搜索成功率、搜索时间、轨迹长度和单次平均搜索步长组成，实验结果如表2和表3所示．

表2 目标搜索实验1

表3 目标搜索实验2

从表2和表3可以看出，本文提出的目标搜索方法可以有效地搜索目标，其中算法中的复杂度阈值对搜索结果有着重要的影响．复杂度阈值越低，搜索过程越精细，搜索步长越小，进而搜索成功率越高，但相应的搜索时间和轨迹长度也越大；复杂度阈值越高，搜索过程越粗糙，搜索步长越大，进而搜索成功率越低，同时搜索时间和轨迹长度也就越小．综合考虑搜索成功率和搜索效率，搜索实验1中的最佳复杂度阈值为0．0，搜索实验2中的最佳复杂度阈值为0．25，这说明最佳复杂度阈值与特定搜索环境有关．

4 结束语

本文提出的场景复杂度计算方法符合人的复杂度主观感受，较好地反映了场景的内在特征．实验结果表明：文中提出的场景复杂度可以应用于移动机器人目标搜索任务，但是复杂度阈值会影响搜索算法的性能，阈值越低搜索越精细，阈值越高搜索越粗糙．如何根据不同的搜索环境自适应地确定复杂度阈值是下一步的研究内容．

［1］ Murphy R R．人工智能机器人学导论［M］．杜军平，吴立成，胡金春，等译．北京：电子工业出版社，2004：10－11．

［2］ 张林．家庭服务机器人物品搜寻与定位技术研究［D］．山东大学控制科学与控制工程学院，2009：1－5．

［3］ Tsotsos J K．The complexity of perceptual search tasks［C］//Proceedings of the 11th International Joint Conference on Artificial Intelligence：Vol．2．Menlo Park，California，USA：AAAI，1989：1571－1577．

［4］ Connolly C I．Determination of next best views［C］//IEEE International Conference on Robotics and Automation．Piscataway，N J，USA：IEEE，1985：432－435．

［5］ Alper A，Kristoffer S，Patric J．Object search on a mobile robot using relational spatial information［C］//Proceedings of the 11th International Conference on Intelligent Autonomous Systems．Amsterdam，Netherlands：IOS，2010：111－120．

［6］ Shubina K，Tsotsos J K．Visual search for an object in a 3D environment using a mobile robot［J］．Computer Vision and Image Understanding，2010，114（5）：535－547．

［7］ Pham H N．A comprehensive cooperative exploration framework for ground and air vehicles in unknown environments［D］．Master thesis of School of Aerospace，Mechanical and Mechatronic Engineering，The University of Sydney，2007：116－149．

［8］ Hollinger G A．Search in the physical world［D］．Doctor thesis of Robotics Institute Carnegie Mellon University，2010：1－7．

［9］ 高振宇，杨晓梅，龚剑明，等．图像复杂度描述方法研究［J］．中国图像图形学报，2010，15（1）：129－135．

［10］ 胡正平，孟鹏权．全局孤立性和局部同质性图表示的随机游走显著目标检测算法［J］．自动化学报，2011，37（10）：1279－1284．

［11］ Hou X D，Hare J，Koch C．Image signature：highlighting sparse salient regions［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34（1）：194－201．

［12］ Azad P，Asfour T，Dillmann R．Combining harris interest points and the SIFT descriptor for fast scale－invariant object recognition［C］//IEEE Conference on Intelligent Robots and Systems．Piscataway，N J，USA：IEEE，2009：4275－4280．

Research on target search method for mobile robot based on scene complexity

MA Zhi－wei， JIN Xiao－feng＊
（Intelligent Information Processing Lab．，Department of Computer Science ＆Technology，College of Engineering，Yanbian University，Yanji 133002，China）

Base on the concept of scene complexity which was from the human search experience，we present a novel target search method for mobile robot．In the method，formalization definition of scene complexity was firstly given by analyzing the main factors relative to scene complexity which combined image complexity with laser ranges complexity．Then，combined the processes of visual target detection，the complexity of several scenes were calculated according to the definition．Thirdly，the next search scene was selected by comparing the obtained scenes complexity and the next search point was determined by the laser ranges of the scene．Experimental results show that the method of scene complexity is in accord with the human evaluation and reflects the scene’s intrinsic characteristics，and the proposed target search method is effective and robust．

mobile robot；target search；environment exploration；scene complexity

TP242．6

A

1004－4353（2012）02－0158－05

2012－05－06

＊通信作者：金小峰（1970—），男，副教授，研究方向为语音识别、机器视觉及机器人技术．