, 宋立滨1, 许君杰1, 石循磊1, 刘莉1,2 1. 清华大学 机械工程系, 北京 100084;
2. 东莞深圳清华大学研究院创新中心, 东莞 523808
收稿日期：2018-10-24
基金项目：广东省省级科技计划项目(2017A040405002);国家自然科学基金资助项目(61403225)
作者简介：张继文(1983-), 男, 助理研究员, E-mail:jwzhang@tsinghua.edu.cn
摘要：为适应人类赛场环境, 仿人足球机器人需能够识别未预先定义足球, 此时足球不再具有固定的与场地鲜明对比的颜色, 因而不能通过传统的单色块识别策略解决。该文将足球颜色划分为专有色和共有色两类, 采用两轮颜色标记方法生成颜色查找表; 在图像像素级联通分割获得色块的基础上, 提出基于图连接关系的宏像素聚类算法, 从而得到若干足球识别候选对象; 再利用模糊逻辑方法中的隶属度函数从候选对象中获得最佳足球识别结果。实验表明在不具备高性能计算硬件平台的情况下, 算法能够在存在大量干扰, 远近距离大幅度变化的条件下准确识别出非预先定义的足球, 避免与边线、机器人等对象的混淆, 且达到每秒15帧的计算速率。该算法能够在严格受限的计算能力下达到高效的足球识别能力, 从而为参赛机器人提供了一种崭新策略。
关键词：仿人机器人计算机视觉聚类颜色标记模糊逻辑
Unpredefined ball detection algorithm for humanoid soccer robots
ZHANG Jiwen1,2
, SONG Libin1, XU Junjie1, SHI Xunlei1, LIU Li1,21.Department of Mechanical Engineering, Tsinghua University, Beijing 100084, China;
2.Tsinghua Innovation Center in Dongguan, Dongguan, 523808, China
Abstract: Humanoid soccer robots need to adapt to the conditions in human soccer games such as detecting a soccer ball that does not have predefined characteristics such as a definite color and that may blend in with the playing field. For such conditions, the problem cannot be solved by classical detection strategies based on a single colorblock. In this study, the ball color is split into a specific color and a shared color. Two rounds of labelling are used to generate a color lookup table. Color-blocks obtained by pixel-level segmentation are used in a marco-pixel clustering method based on a connecting relationship graph to generate several ball candidates. The best ball object is estimated via the membership function by fuzzy logic. Tests show that the method is able to detect unpredefined balls even in a very disturbed environment and at large distances from the robot and is also able to avoid confusion with the border lines and other robots on the field without excessive computing requirements. The calculations can reach a high framerate of 15 frames per second. This strategy provides an efficient detection method using strictly limited computing resources for robot soccer players.
Key words: humanoid robotcomputer visionclusteringcolor labelingfuzzy logic
仿人机器人足球是一项典型的多机器人智能协作任务，能够有效推进机器人多项技术进步，具体包括计算机视觉、状态估计、机器学习、多机器人决策以及运动规划等。其中计算机视觉是重要课题之一[1]。为促进仿人足球机器人机器视觉能力的不断进步，Robocup等赛事的球场环境取消了可作为定位陆标的定位柱和具有鲜明颜色标记的球门，仅留有边线，逐步从赛前预先定义的橙色足球转变为赛前非预先定义的表面颜色复杂的足球。
近年来，深度学习技术大幅提升了视觉识别的准确性和通用性。视觉系统逐步摆脱了专有特征的归纳和提取的限制，从而为有效解决球场复杂对象的识别提供了有效解决方案[2-3]。然而，实时条件下的基于深度学习的视觉一般需要图像处理器(graphics processing unit, GPU)等一系列高性能硬件的支持。但小型仿人足球机器人一般载重能力有限，功耗要求苛刻。深度学习技术还依赖于大量的学习样本和漫长的学习时间。尽管迁移学习技术能够有效降低机器学习的代价，能够大幅降低适应现场的时间，但仍然无法摆脱针对确定环境的视觉系统预处理和标定。尽管已经有部分研究机构成功地引入了机器学习系统，并展示了其优异的对象识别功能。但对于其他为数众多的小型类人机器人，则无法完全抛弃原有的计算机硬件系统。因此，深度学习这一类成本高昂的策略不应该是解决这一类相对确定环境下对象识别的唯一途径。
传统的足球识别算法全部或部分地依赖于固定且鲜明的颜色特征[4-7]。然而图 1中的非预先定义足球则没有固定的颜色可供作为依据，与球场上的其他对象如边线、点球点及外界干扰易于产生混淆，增加了识别的难度。
 |
| 图 1 (网络版彩图)Robocup中曾使用过的非预先定义足球 |
| 图选项 |
此外，仿人机器人依赖于双足步行实现移动。步行期间，身体的摇摆以及头部的搜索运动将引起其视觉系统的波动和振动，进而造成所采集图像的清晰度下降以及所见物体的变形。其后果是对于具有典型球形特征的足球也不宜完全依赖于其圆形特征识别。同时，足球对象与机器人的距离变化范围很大，远距离的足球难以保证其在图像中的典型圆形状，因而其边界特征不易被提取，阻碍了这一类依赖形状的足球识别方法的应用[8]。例如，文[9]为实现比赛实况录像中基于形状提取球对象，要求采用高速相机以避免变形和模糊的问题。
为了解决这一系列复杂球识别所提出的新问题，本文提出一套基于图连接关系的宏像素聚类算法，并综合利用该算法和模糊逻辑算法获得最佳足球识别结果。
1 整体算法框架本文提出的算法整体框架如图 2所示，其中样本图片是预先采集的待学习图片，目标图片是机器人摄像机实时采集到的待处理图像。最终识别结果为球对象。
 |
| 图 2 基于颜色分类与区域分割的球检测策略 |
| 图选项 |
图 2中的颜色查找表标记算法中，采取一种特殊的球颜色划分方法，将球的颜色分为两类：专有色和共有色。而后通过4-连通域或8-连通域的聚类方法[4]获得系列大小不一的小色块，形成宏像素。通过一种宏像素聚类算法进一步连接宏像素，从而形成一系列候选对象。最终，借助模糊逻辑的方法，在多个候选对象中挑选一个最可能是真实球的对象视作最终识别结果。
2 球颜色分类策略基于颜色特征识别的基础是将待处理像素划分为不同的颜色标记，一般通过颜色查找表(colour lookup table，CLUT)建立颜色空间到颜色标记之间的映射关系[8, 10]。对于表面颜色复杂的球对象，无法采用单一的颜色标记，因此采用特殊的颜色标定方法和样本图片，通过两轮颜色标记生成CLUT：
1) 采集第一批待标记样本图片，该批样本图片的视野内仅具有待识别球以及绿色的场地背景。进而将球表面的全部颜色标记为mb，将场地颜色标记为mf，得到球全部颜色和场地颜色的颜色查找表L1。
2) 采集第二批待学习图片样本，其视野内仅具球场的其他对象，而不包含球对象本身。标记这些对象如机器人黑色mk、球门和边线的白色mw、以及除场地颜色之外的所有其他图像识别所关心的颜色，从而得到查找表L2；
基于上述两个查找表L1和L2，获得用于球识别的查找表Lb，其原理如图 3所示。mb和mk取交集，得到球表面和机器人共有色mb/k。同理，可获得共有色标记mb/w。球表面专有颜色被标记为mz。依赖Lb以及栈的4连通聚类算法[11]，实现了多个标记颜色的聚类，形成一系列大小不一的色块{Bi}，其中每一个色块Bi的参数包括：颜色类别ki、像素数量ni以及色块轴对齐包围盒(axis-aligned bounding box，AABB)等。本文定义这一系列色块{Bi}为宏像素，以区别于摄像机中的物理像素。
 |
| 图 3 两轮标定生成球颜色查找表策略 |
| 图选项 |
3 宏像素的聚类在所获得的宏像素中，不但包含属于球的色块，也包含有其他对象的干扰色块。因此需要依据宏像素的连通性以及实际对象观测合理性进一步分割聚类，从而获取一系列候选对象。为此本文提出了一种宏像素聚类算法。
3.1 构造宏像素的邻接矩阵由于宏像素不再具有物理像素的4-连通或者8-连通的固定邻接特性，因此连通聚类的第一步是构造宏像素之间的邻接关系。
为此，首先定义宏像素的两类基本关系：其一是宏像素相邻关系，即两个宏像素AABB包围盒存在相互重叠的部分；其二是宏像素的兼容关系，即两个宏像素的并集的AABB包围盒尺寸不超过物理对象的合理区间[8, 12]。基于该定义，宏像素之间关系共划分为三种：相邻、不确定以及互斥。
1) 相邻关系：两个宏像素满足邻接关系，且满足兼容关系；
2) 不确定关系：两个宏像素不满足邻接关系，但满足兼容关系；
3) 互斥关系：两个宏像素不满足兼容关系。
可为多个宏像素之间的关系绘制图连接矩阵，如图 4所示是几个宏像素示例以及这些宏像素之间的关系表。其中标为“邻”的表明为相邻关系，标为“斥”的为互斥关系，标为“？”的为不确定关系。
 |
| 图 4 宏像素及其邻接矩阵实例 |
| 图选项 |
3.2 宏像素的图分割算法宏像素分割的目标是将小的色块合并构造成为一个可能的球识别对象。依据如图 4宏像素之间的邻接矩阵，定义宏像素聚类的目标：
1) 处于同一个聚类结果内的任意两个宏像素均满足兼容关系；
2) 集合内的任意一个宏像素总能找到另一个宏像素并与之满足相邻关系。
上述两个目标表明，最终的分割结果中不存在两两不兼容的宏像素，且任意一个宏像素总能邻接于其他某个宏像素。为了达到上述目的，以宏像素图中的任选节点启动聚类过程，其中一个过程示例如图 5所示。
 |
| 图 5 以节点0为起点的宏像素聚类过程实例 |
| 图选项 |
节点0—7是8个宏像素单元，构成了一张无向图，假设第一轮聚类分割从节点0起始。
第1步首先将节点0加入闭集合，并将与之存在相邻关系的节点，即节点1、2、3、4放入开集合；
第2步将开集合内一个节点1加入闭集合中，在加入过程中，由于开集合中的节点2与1互斥，因此将开集合中的节点2删除。此外，再将与节点1存在相邻关系的节点5、6加入开集中；
第3步将开集合内的一个节点3加入闭集中，加入过程中，开集合中的节点6与3互斥，因此从开集中删除节点6；此外，由于不存在与节点3相邻的其他节点，因此本轮没有新节点加入开集中；
第4—5步，先后将开集内的一个节点4、5加入闭集中，由于此时开集中没有与节点4、5互斥的节点，也没有与节点4、5连接的新节点，因此没有节点从开集移除或删除；
最终，开集合为空，本轮聚类结束，{0、1、3、4、5}形成一个分割结果，其任意两个节点不存在互斥关系，且该集合构成一个连通子图，因而满足聚类分割的两项基本假设。
此后再挑选一个分割起点执行类似的聚类过程，为了提升效率，避免重复聚类，已经出现在前述分割结果的节点不再作为分割的起点。针对图 5中的实例以及第一轮分割的结果，能够作为下一轮聚类的起始节点为2、6、7。如图 6所示是以节点7为起始节点的聚类分割过程。
 |
| 图 6 以节点7为起点的宏像素聚类过程实例 |
| 图选项 |
该轮分割所获得的结果是{1, 3, 5, 7}，从而得到与第一轮聚类不完全相同的一个联通子图。所提出的分割算法如图 7所示。
 |
| 图 7 宏像素聚类过程算法 |
| 图选项 |
图 7中OPEN为开集合，CLOSED为闭集合，START聚类起点集合。RESULT为最终宏像素聚类结果。一个宏像素聚类循环起始于第6行，从START起点集合中选择一个元素s放入CLOSED集合作为本轮聚类的起点。自第9行开始，随着OPEN集合中的元素不断放置进入CLOSED中，完成以s为起点的集合搜索。其中：
| ${\rm{Rel}}(a, b, M) = \left\{ {\begin{array}{*{20}{l}}{n, }&{a与b邻接;}\\{r, }&{a与b互斥;}\\{u, }&{a与b不确定.}\end{array}} \right.$ | (1) |
另一方面，注意到算法第8、11行将REM集合中的元素不断放入OPEN集合，而每一轮聚类循环启动时，REM集合均初始化为S，即算法的输入集合，从而使得每一轮循环均能够从完整的像素集合中完成聚类。典型的实例如图 5和6所示，两个聚类循环的结果中除去节点7和节点0、4的差异外，还具有三个公共的节点1、3、5，表明最终几个聚类集合中必有差异，但允许存在共有的部分。即假设两个聚类结果集合为RESULT(i)和RESULT(j)，则：
| $\left\{ \begin{array}{l}{\rm{RESULT}}\left( i \right) \ne {\rm{RESULT}}\left( j \right), \\{\rm{RESULT}}\left( i \right) \cap {\rm{RESULT}}\left( j \right) \ne \emptyset .\end{array} \right.$ | (2) |
 |
| 图 8 (网络版彩图)原始图像中球与边线混淆条件下所生成的多个宏像素聚类结果 |
| 图选项 |
4 最佳识别对象的选择通过宏像素聚类算法获得了多个候选结果，每个候选结果则由一个宏像素集合构成。依据宏像素的颜色类别、像素数量、包围盒等参数可推算出候选结果的一系列综合属性，例如候选对象整体的AABB包围盒的尺寸、填充率、长宽比，面积以及专有色、共有色的比率等。为了确定最终识别结果，还需要从这些候选结果中挑选出球对象。本文借助模糊逻辑的隶属度函数评估观测结果与理想结果的特征差异，从而得到一个最可能的球观测结果。更进一步的，考虑到后续球运动建模和滤波的过程，则可将多个观测对象与隶属度函数数值一同作为目标观测输出，从而借助Kalman滤波器或Bayes滤波器[13]获得健壮性更为优良、更为准确的球定位策略。
设候选结果的观测参数为xi，i∈N，代表最终的观测特征，隶属度函数定义为
| $G\left( {\mathit{\boldsymbol{x}};\mathit{\boldsymbol{c}}, \mathit{\boldsymbol{\sigma }}} \right) = \exp \left[ { - \frac{1}{2}\sum\limits_{i = 1}^N {{{\left( {\frac{{{x_i} - {c_i}}}{{{\sigma _i}}}} \right)}^2}} } \right].$ | (3) |
| ${g_i}({x_i};{c_i}, {\sigma _i}) = \exp \left[ { - \frac{1}{2}{{\left( {\frac{{{x_i} - {c_i}}}{{{\sigma _i}}}} \right)}^2}} \right].$ | (4) |
5 实验及讨论实验所采用仿人机器人及其参数如图 9所示[14]。图像处理算法运行于图 9中的机载计算机上。处理器的运行频率仅为1 GHz、内存仅有512 MB，难以支持深度学习和神经网络的实时在线计算。
 |
| 图 9 用于非预定义球检测的仿人机器人外形及其机载计算机系统[14] |
| 图选项 |
图 10a是机器人视觉系统所采集的一帧原始图像，实验选用了图 1中的实验用球，该球表面具有黑色、白色及其他多种颜色，色块之间相互交织耦合，具有较大的识别难度。图 10b是依据颜色查找表Lb转换为颜色标记的图片。其中，球本身以及所在的边线和周边干扰均成为目标颜色。经过4-连通分割聚类所获得的宏像素的AABB包围盒如图 10c所示，共有宏像素113个。图 10d是执行宏像素聚类算法后所获得的连接色块集合，从而进一步滤除了独立微小的干扰。依据这些连接色块的高宽比、填充率、直径合理性等参数滤除不合理的色块后，获得3个色块成为候选对象，其参数如表 1所示。隶属度函数计算的结果表明序号为1的对象成为最终球识别结果。整体算法能够从大量的干扰像素的多值化图像中获得图 10e的准确识别结果。
 |
| 图 10 (网络版彩图)自原始图像到提取出最终识别结果的任意球检测过程实例 |
| 图选项 |
表 1 多个候选对象特征参数及隶属度函数
| 序号 | 专有色比例/% | 白色比例/% | 黑色比例/% | 尺寸准确比/% | 背景色比/% | 形状准确度/% | 隶属度函数值 |
| 1 | 26.9 | 27.5 | 45.6 | 91.3 | 54.9 | 96.4 | 0.942 1 |
| 2 | 28.6 | 71.4 | 0.0 | 76.0 | 36.7 | 71.4 | 0.851 1 |
| 3 | 41.2 | 0.0 | 58.8 | 102.9 | 42.2 | 66.7 | 0.885 1 |
表选项
图 11是典型视野场景下的识别结果。其中图 11a是在杂乱的背景下，在多个候选对象中挑选出最终的球识别结果。图 11b是近距离条件下，球放置在白线上，并存在黑色机器人干扰条件下，仍然能够准确识别出球，而未出现与这些对象间的混淆现象。图 11c表明在摄像机分辨率(640×480像素)和视角范围(55°)条件下，算法的最远可识别距离可达4.5 m。同时图中的球也位于白色边线上，且近处具有一个明显的圆形点球点的干扰，表明在远距离条件下该算法也能够精确滤除边线及其他对象的干扰。图 11d是球位于机器人足底附近的识别结果，可见在部分遮挡以及颜色干扰的条件下能够达到良好的识别效果。图 11e是图 1中多种球的识别结果，从而实现了对多种非预先定义球的适应性。
 |
| 图 11 (网络版彩图)多种典型条件下的任意球检测过程结果 |
| 图选项 |
特别注意在图 11f中的视野内，存在2个不同的球对象，因而算法得到了远近两个候选对象，各项提取参数以及隶属度函数值如表 2所示。
表 2 多个球对象特征参数及隶属度函数
| 序号 | 专有色比例/% | 白色比例/% | 黑色比例/% | 尺寸准确比/% | 背景色比/% | 形状准确度/% | 隶属度函数值 |
| 1 | 12.5 | 41.5 | 46.0 | 45.7 | 56.3 | 90.9 | 0.881 |
| 2 | 51.0 | 49.0 | 0.0 | 85.5 | 81.6 | 85.7 | 0.970 |
表选项
不同的球的识别依赖于节2所述的两轮标记过程以及节4所述的隶属度函数的参数。针对如图 11f所示的两个不同的球，序号为2的对象隶属度函数值显著地高于1号对象。这表明2号候选对象更为接近于目标球对象。相比之下，1号候选对象则与目标球对象差异较大，从而将1号候选对象作为干扰而忽略。因此，本文所述的方法能够较为精确地识别出经过预先标定的球对象，当球对象的外观以及场地环境发生大幅度变化时，须重新标定，避免球识别的混淆，从而得到精准的识别结果。
实验所用的Matlab/Octave离线仿真代码位于https://github.com/zjwtsh/arbitrary_ball_detection，球在线检测运行程序源代码位于https://github.com/zjwtsh/uikidcm/tree/tiny210/Lib/Modules/ImageProc。经在比赛中实际应用测试，本文算法在图 9所示的机器人运算平台上可达到每秒15帧的平均处理速度。
6 结论本文提出了一种基于颜色的非预定义足球识别算法，通过将足球颜色划分为专有色和共有色2类，采用两轮颜色标记方法生成颜色查找表。基于像素级联通分割色块，建立了宏像素及其图连接关系，并给出了宏像素的聚类算法，从而得到若干球识别候选对象。利用模糊逻辑方法中的隶属度函数从候选对象中获得最佳足球识别结果。该算法能够在不具备高性能计算硬件平台的情况下，在存在大量干扰，远近距离大幅度变化的条件下准确识别出任意选择的足球，避免与边线、机器人等对象的混淆，且达到较高的计算速率，有效解决了计算性能受限条件下的复杂球对象识别问题。
下一步在对球对象的识别建模时可以将隶属度函数作为候选对象的权重，结合粒子滤波等方法，实施更为复杂的球运动状态估计。此外，本文算法依赖于对观测球距离的推算，当球处于飞行状态时，距离观测较为困难，因而也是未来亟待解决的问题之一。
参考文献
| [1] | NADARAJAH S, SUNDARAJ K. Vision in robot soccer:A review[J]. Artificial Intelligence Review, 2015, 44(3): 289-310. DOI:10.1007/s10462-013-9401-3 |
| [2] | JOSEPH R, DIVVALA S, GIRSHICK R, et al. You only look once: Unified, real-time object detection[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas, NV, USA: IEEE, 2016: 779-788. https://www.researchgate.net/publication/278049038_You_Only_Look_Once_Unified_Real-Time_Object_Detection |
| [3] | JONATHAN L, EVAN S, TREVOR D. Fully convolutional networks for semantic segmentation[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. Boston, MA, USA: IEEE, 2015: 3431-3440. https://www.ncbi.nlm.nih.gov/pubmed/27244717/ |
| [4] | RAHMAN A, WIDODO N S. Colored ball position tracking method for goalkeeper humanoid robot soccer[J]. Telecommunication Computing Electronics and Control, 2013, 11(1): 11-16. |
| [5] | TRIFAN A, NEVES A J R, CUNHA B, et al. UAVision: A modular time-constrained vision library for soccer robots[C]//Robot Soccer World Cup. Switzerland: Springer, Cham, 2014: 490-501. https://link.springer.com/chapter/10.1007/978-3-319-18615-3_40 |
| [6] | 李晓瑜, 杨马英. 足球机器人视觉图像分割算法[J]. 吉林大学学报(工学版), 2013(s1): 260-264. LI X Y, YANG M Y. Objective segmentation method of video image in robot soccer[J]. Journal of Jilin University (Engineering and Technology Edition), 2013(s1): 260-264. (in Chinese) |
| [7] | 杜鑫峰, 熊蓉, 褚健. 仿人足球机器人视觉系统快速识别与精确定位[J]. 浙江大学学报(工学版), 2009, 43(11): 1975-1981. DU X F, XIONG R, CHU J, et al. Fast recognition and precise localization of humanoid soccer robot vision system[J]. Journal of Zhejiang University (Engineering Science), 2009, 43(11): 1975-1981. DOI:10.3785/j.issn.1008-973X.2009.11.006 (in Chinese) |
| [8] | BUDDEN D, FENN S, WALKER J, et al. A novel approach to ball detection for humanoid robot soccer[C]//Australasian Joint Conference on Artificial Intelligence. Berlin Heidelberg: Springer, 2012: 827-838. https://link.springer.com/chapter/10.1007/978-3-642-35101-3_70 |
| [9] | MAZZEO P L, SPAGNOLO P, LEO M, et al. Ball detection in soccer images using isophote's curvature and discriminative features[J]. Pattern Analysis and Applications, 2016, 19(3): 709-718. DOI:10.1007/s10044-014-0443-1 |
| [10] | BRUCE J, BALCH T, VELOSO M. Fast and inexpensive color image segmentation for interactive robots[C]//Proceedings of 2000 IEEE/RSJ International Conference on Intelligent Robots and Systems, Takamatsu, Japan: IEEE, 2000(3): 2061-2066. https://ieeexplore.ieee.org/document/895274 |
| [11] | ABUBAKER A, QAHWAJI R, IPSON S, et al. One scan connected component labeling technique[C]//IEEE International Conference on Signal Processing and Communications, Dubai, United Arab Emirates: IEEE, 2007: 1283-1286. https://www.researchgate.net/publication/224363479_One_Scan_Connected_Component_Labeling_Technique |
| [12] | HARTL A, VISSER U, ROFER T. Robust and efficient object recognition for a humanoid soccer robot[C]//RoboCup 2013: Robot World Cup XVⅡ. Berlin Heidelberg: Springer, 2013: 396-407. https://rd.springer.com/chapter/10.1007/978-3-662-44468-9_35 |
| [13] | THRUN S. Probabilistic robotics[M]. Cambridge: MIT Press, 2006. |
| [14] | 张继文, 刘莉, 陈恳. 小型仿人足球机器人MOS-7的系统设计及局部优化[J]. 清华大学学报(自然科学版), 2016, 56(8): 811-817. ZHANG J W, LIU L, CHEN K. System design and local optimization of a small humanoid soccer robot MOS-7[J]. Journal of Tsinghua University (Science and Technology), 2016, 56(8): 811-817. (in Chinese) |
