董海霞，曾连荪

　　（上海海事大学 信息工程学院，上海 201306）

　　摘要：在基于人工视觉的移动机器人导航中，闭环检测是机器人准确构建地图及定位的一个重要问题。本文研究的闭环检测算法结合了计算机视觉中的词袋技术和视觉词典技术，在对图像进行处理时利用了BRIEF+FAST关键点的方法，利用离线阶段生成的词典树将二进制描述子空间离散化。训练图像生成的图像数据库结构主要由等级词袋、倒置索引和直接索引组成。倒置索引和直接索引提高了算法的效率。为了保证闭环检测结果的可靠性，对于匹配的图像还要进行验证。重点详述了一种高效的闭环检测算法，相对一般的基于概率的闭环检测，在硬件设备相同的情况下，本算法效率更高。

　　关键词：词袋；视觉词典；闭环检测；图像数据库；匹配

0引言

　　即时定位与构图（Simultaneous Localization and Mapping，SLAM）指的是机器人在未知的环境中，增量式地创建周围环境的连续地图，同时利用创建的地图为自身导航［1］。SLAM问题可以实现机器人真正的自主导航。数据关联是指移动机器人用确定传感器观测量与目标源之间的对应关系［2］。机器人进行一段时间的运行后，当长时间没有被观测到的区域被机器人自身携带的传感器观测到时，标准的匹配算法就会失败。当能稳定地检测到这些区域时，闭环检测算法就能够提供正确的数据关联。

　　早期数据关联算法的研究主要停留在几何方面，Singer等人提出的最近邻（Nearest Neighbor, NN）算法是最早也是最简单的数据关联方法［3］。在环境特征密度较大的情况下，使用NN算法容易发生关联失败现象，由于NN算法忽略了数据之间的相关性，可能导致一些错误的关联。Jose Neira等人提出了联合相容性检验（Joint Compatibility Test, JC Test）算法。联合相容分支定界（Joint Compatibility Branch and Bound, JCBB）［3］算法能排除一些NN算法无法排除的错误的关联假设［4］，基于几何的数据关联方法没有充分利用到机器人周围的环境信息。随着相机价格的下降，相机取代传统的传感器，在数据关联方面的应用越来越广泛。机器人通过所携带相机拍摄的周围环境图片含有丰富的信息，因此可以通过对图片的处理，判断图片间的相似性，看是否形成了一个闭环，从而对机器人构建的地图进行修正或增广。

　　本文中的闭环检测算法主要基于视觉词典［5］及对匹配的图像进行的几何检测，其高效性使得这种算法更适合实时应用。

1问题定义

　　闭环检测是指当移动机器人到达一个先前已经构建过地图的位置时，能够判断出这个位置已经构建过地图，然后对原来构建的地图进行更新、修正［6］。

　　1.1二进制特征

　　在进行两幅图像比较时，需要从图像中提取关键点和局部特征，这一步是非常费时的，这也是闭环检测算法实时应用的瓶颈。为了克服提取特征和关键点费时的问题，本文采用了FAST关键点和最优的BRIEF描述子。FAST关键点是一些像角一样的点，这些点是通过在一个半径为3的Bresenham圆中，对一些像素点的灰度强度进行比较得到的［7］。因为检测到的像素点的个数有限，所以在实时的应用中，FAST关键点也能很快被检索到。

　　对于每一个FAST关键点，以这个点为中心点画一个方形的图像块，然后计算一个BRIEF描述子。BRIEF描述子是二进制的比特向量，通过图像块（为了降低噪声已经事先经过高斯平滑处理）中两个像素点的强度比较得到比特分量的值［8］。给定图像块的尺度Sb，设置好用于比较的像素点的对数Lb（也就是描述子向量的长度），像素点是在离线阶段随机选择的。对于图像中的关键点P，它的BRIEF描述子向量B(P) 可以描述为：

　　Bi(P)是描述子向量中的第i个比特，I(·)表示平滑图像中像素点的强度，ai、bi表示第i个检测点相对于图像块中心点的2D偏置量，它们的取值范围是:

　　这种描述子向量不需要训练，只是在离线时随机选择的点，占用的时间可以忽略。BRIEF描述子最大的优点是计算速度快，由于这种描述子只是一个比特向量，可以通过异或比较两个向量之间不同比特的个数（汉明距离），在实时的应用中计算欧氏距离要比计算汉明距离慢得多。在使用SIFT和SURF描述子时，计算两个向量之间的距离就是计算欧氏距离。

　　1.2图像数据库

　　为了让机器人识别出目前所在的位置是否已经构建过地图，本文使用了图像数据库。图像数据库主要由等级词袋、倒置索引和直接索引三部分组成，如图1所示。词典中的字就是树中的叶子节点。倒置索引中存放的是字的权重。直接索引中的内容主要是图像的特征以及与特征相关的词典树中的节点。

　　在机器人自主导航过程中，机器人携带的相机拍摄了大量的图片。为了能够有序地存储这些图片，用词袋技术通过视觉词典把图片转换成稀疏的数值向量［9］。视觉词典是在离线阶段生成的，它把描述子空间离散成W个视觉字。本文所用的特征BRIEF使得二进制描述子空间离散化，生成一个更简洁的词典，把词袋按等级排列，整个词典就是一个树形的结构。为了生成词典树，从训练图像（这些图像与在线处理的图像是相互独立的）中提取大量的特征，它们所对应的描述子按照Kmeans算法离散成Kw个二进制的簇，这些簇就是词典树的一级节点，对于每一个节点再进行Kmeans算法，生成第二级节点，依次按照这种步骤进行Lw次，最终就会生成W个字的词典树［10］。根据字在训练集中的相关性，给每个字分配一个权重，那些出现次数比较频繁、对于区分不同图像没有太大作用的字，分配较小的权重，对于区分图像作用显著的字，分配权重大一些。假设在t时刻，获得一幅图像It，根据图像中特征的二进制描述子，从根到叶子遍历整个词典树，按照汉明距离最小原则在每一级选择一个节点，到达叶子节点时就可以得到该图像对应的二进制数值向量Vt∈Rw。两幅图像I1、I2之间的相似性可通过计算它们的数值向量之间的相似值来衡量：

　　在图像数据库中除了词袋外还有倒置索引和直接索引。对于词典中的一个字Wi，倒置索引中内容是包含这个字的图像的列表。有了这种结构，在从数据库中搜索与查询图像相似的数据库图像时，就可以只在与查询图像有共同字的数据库图像中进行搜索。如果在倒置索引中存放图像的数值向量中对应Wi这个字的分量，还可以得到字在图像中的权重。直接索引存储的是图像It中字的父节点和与节点相关的局部特征ftj。直接索引的结构可以使得在几何验证时，只寻找同一个字的特征间或者是有相同父节点的特征间的对应性，这样就节省了时间。但是，当有新的图像要加入数据库时，倒置索引和直接索引都要进行更新。

2闭环检测算法

　　本文研究的闭环检测算法主要分为四步个步骤。

　　2.1查询数据库

　　从图像数据库中检索与给定图像相似的图像。当机器人获得最新的图像It时，首先根据在离线阶段生成的词典树把它转换成词袋向量Vt，然后在数据库中进行搜索得到一些候选的匹配〈Vt,Vt1〉，〈Vt,Vt2〉，…，根据公式（3）计算出这些匹配对应的相似值s(Vt,Vtj)，相似值的变化范围是由查询图像和图像中字的分布决定的。对相似值进行归一化，得到归一化相似值η:

　　Vt-Δt是前一幅图像的词袋向量。当机器人在某一瞬间状态急剧变化时，s(Vt,Vt-Δt)的值就会很小，导致归一化相似值很高。为了避免这种错误的出现，对s(Vt,Vt-Δt)设置一个小的门限值，忽略短时间内与Vt相似度很低的图像。同时，为了避免有效的图像被错误的忽略掉，门限值应该设置得小一点。对于归一化相似值η，设置一个门限α，抛弃那些没有达到最小相似值α的匹配。

　　2.2匹配组

　　当相机的拍摄频率较高时，时间间隔很短的图像往往具有很高的相似性。为了避免在数据库中搜索时时间间隔很短的图像之间互相竞争，这里把拍摄时间间隔很短的图像看做是一个岛，在匹配的时候把这些匹配看做是一个匹配。将时间戳tni，…，tmi，用一个时间戳Ti表示，VTi 表示整个图像岛的词袋数值向量。根据相似值H，对岛的相似性进行排序：

　　具有最大相似值的岛作为候选的匹配组，再进行一致性检验。用图像岛的方法消除连续图像匹配时的竞争，如果It和It′是一个真正的闭环，It往往与It′±Δt，It’±2Δt，… ，也有很高的相似性。

　　2.3时间上的一致性

　　在得到最佳的匹配岛VT′后，要检测当前匹配与前面匹配的一致性。即匹配〈Vt，VT′〉与前面k个匹配〈Vt-Δt,VT1〉，…，〈Vt-kΔt,VTk〉必须一致，类似于JCBB算法中匹配时联合兼容性检验。如果一个岛符合一致性检验，则认为最大η值对应的匹配〈Vt，Vt′〉是最佳匹配（t′∈T′），把它作为一个候选的闭环，最后还要经过几何验证来判断其是否是一个真正的闭环。

　　2.4几何验证

　　对于候选为闭环的图像还要进行几何验证。几何验证是指利用RANSAC(Random Sample Consensus)算法在匹配的图像It和It′之间找到局部特征的对应性。局部特征的比较有两种方法，递归搜索是最简单也是最慢的方法，它是通过计算 It中的每一个特征和It′中的每一个特征在描述子空间中的距离， 根据最近邻比例策略，选择特征之间的对应特性。但是当图像中特征点数量很多时，递归搜索法的计算量是不可接受的。

　　另外一种方法是近似最近邻法，当有一幅新的图像加入图像数据库中，要把成对的节点和特征存储在直接索引中，在对It和It′进行几何验证时，查询It′的直接索引，只比较同一个节点关联的特征，节点在词典树中的级数l是事先给定的。由于进行特征比较的次数明显少于递归搜索，节省了大量时间。l的设置会影响几何验证的结果，当l=0时，只对属于同一个字的特征进行比较，这时几何验证效率最高，但是图像间对应的特征对数也是最少的，这就可能导致正确的闭环由于缺乏点之间的对应性而被拒绝。相反，当l=LW时，全部候选的匹配都能通过几何验证，但是此时，几何验证的效率也没有得到改善。

　　在几何验证阶段，只是对于匹配的图像之间进行验证，以确定两者的相似度足够高，在验证之后还要进行正确的数据关联。

3实验

　　整个实验模拟的是室外静态环境下闭环检测算法的过程，具体步骤：首先在离线阶段生成视觉词典树，然后在机器人运行时利用生成的词典树进行闭环检测。整个过程共检测到7个闭环，提取特征用的是BRIEF算法，特征提取时间为8.946 99 ms/图，实验中的词袋字典是在离线阶段生成的，规模是106，词典树中共有754 997个字，词典树的级数是L=6，Kmeans算法中K的值设置为10。

　　实验中的原始算法是由美国计算机视觉研究者Dorian Gálvez López 提出的DLoopDetector算法，本文实验中不同于原始算法的地方是：在Dorian Gálvez López的实验中，DBow2与DLoopDetector是分立的；在本文进行的实验中，把DBow2与DLoopDetector结合在一起，即利用DBow2生成的词典树进行闭环检测实验。本文实验效果图如图2所示。

4结束语

　　在视觉SLAM中，闭环检测是数据关联的扩展，是一个从点对点到面对面的过程。本文研究的闭环检测算法使用的图像数据库结构除了等级词袋、倒置索引外，还有直接索引，这种结构使得几何验证的效率更佳。二进制描述子BRIEF的使用使提取图像特征、计算描述子之间距离的速度更快。但是在尺度、光照、相机发生旋转时，BRIEF描述子是不稳定的。因为本文中实验是在室外静态环境下进行的，而且相机也只是在平面内进行微小运动，所以多数实验具有很高的准确性。

参考文献

　　［1］ 曲丽萍. 移动机器人同步定位与地图构建关键技术的研究［D］. 哈尔滨： 哈尔滨工程大学, 2013.

　　［2］ 柴红霞. 移动机器人在SLAM中数据关联方法的研究［D］. 大连： 大连理工大学, 2010.

　　［3］ 张雪晶,孙作雷,曾连荪，等.基于联合相容分支定界的关联算法研究［J］.微型机与应用,2015,34(15):8284,88.

　　［4］ NEIRA J， TARDS J D. Data association in stochastic mapping using the joint compatibility test［J］. Robotics and Automation, IEEE Transactions on, 2001，17（6）：890897.

　　［5］ 崔大成,曾连荪.基于视觉字典的移动机器人闭环检测方法研究［J］.微型机与应用,2015,34(9):8588.

　　［6］ WILLIAMS B, CUMMINS M, NEIRA J, et al. A comparison of loop closing techniques in monocular SLAM［J］. Robotics and Autonomous Systems, 2009，57（12）：11881197.

　　［7］ GLVEZLPEZ D， TARDS J. D. Bags of binary words for fast place recognition in image sequences［J］. Robotics, IEEE Transactions on, 2012，28（5）：11881197.

　　［8］ CALONDER M, LEPETIT V, STRECHA C, et al. Brief: binary robust independent elementary features［C］. Computer VisionECCV 2010, 2010:778792.

　　［9］ SIVIC J, ZISSERMAN A. Video google: a text retrieval approach to object matching in videos［C］. In Computer Vision, 2003. Proceedings. Ninth IEEE International Conference on, 2003：14701477.

　　［10］ NISTER D， STEWENIUS H. Scalable recognition with a vocabulary tree［C］. In Computer Vision and Pattern Recognition, 2006 IEEE Computer Society Conference on, 2006：21612168