【泡泡一分钟】 HBST：用于基于特征的视觉位置识别的汉明距离嵌入二叉搜索树

会员服务 ·

【泡泡一分钟】 HBST：用于基于特征的视觉位置识别的汉明距离嵌入二叉搜索树

2019 年 3 月 15 日 泡泡机器人SLAM

每天一分钟，带你读遍机器人顶级会议文章

标题：HBST: A Hamming Distance embedding Binary Search Tree for Feature-based Visual Place Recognition

作者：Dominik Schlegel and Giorgio Grisetti

来源：2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

编译：孙钦

审核：颜青松，陈世浪

欢迎个人转发朋友圈；其他机构或自媒体如需转载，后台留言申请授权

摘要

可靠高效的视觉位置识别是现代SLAM系统的主要组成部分。在本文中，我们结合以前的工作，提出了用于二进制描述子匹配和图像检索的汉明距离嵌入二进制搜索树（HBST）方法。HBST通过利用二进制描述子的特有属性，可以在对数时间内进行描述子搜索和插入。通过对被利用的描述子属性及其对搜索和插入的完整性和复杂性的影响进行全面分析，我们支持搜索结构背后的思想。HBST可作为紧凑的开源C ++头文件库。

图1 本文提出的HBST方法在KITTI 00序列数据集上的匹配性能。上图显示了图像数量和处理时间的关系，下图显示了单帧图像HBST方法的描述子匹配结果。

本文的方法主要分为：树的构造，描述子搜索和匹配，完整性分析，平衡树构造和增量树构造五个部分。

树的构造：

图2 在场景中使用8个4维的描述子构造HBST树。

描述子搜索和匹配：

图3 深度为1的小树场景搜索。

完整性分析

图3 在深度为1，匹配阈值为10,25,50,75的不同描述子类型的按位平均完整度。

图4 预测的平均完整性和测量的平均完整性比较。

平衡树构造：

我们使用位索引来实现描述子{dj}的均匀分布。

增量树构建：

图5 单输入描述子dj的插入过程示意图。

图6 不同插入图片数量条件下，树深度h的均值和标准差。

为了验证我们提出的方法，我们在广泛的公开数据集上进行了HBST和几种最先进方法的比较实验，实验结果表明，在保持足够精度的同时，本文的方法在计算速度方面明显优于最先进的方法。

图4 从KITTI数据集中选取的用于后面算法比较的序列，其中蓝色是相机轨迹真值，高亮的绿色是匹配图像片段。

图5 在Lucia Stereo Vehicular 数据集上比较不同方法的处理时间和精度-召回率曲线。

图6 在KITTI数据集上，比较不同方法平均处理时间和最大F1得分。

Abstract

Reliable and efficient Visual Place Recognition is a major building block of modern SLAM systems. Leveraging on our prior work, in this paper we present a Hamming Distance embedding Binary Search Tree (HBST) approach for binary Descriptor Matching and Image Retrieval. HBST allows for descriptor Search and Insertion in logarithmic time by exploiting particular properties of binary descriptors. We support the idea behind our search structure with a thorough analysis on the exploited descriptor properties and their effects on completeness and complexity of search and insertion. To validate our claims we conducted comparative experiments for HBST and several state-of-the-art methods on a broad range of publicly available datasets. HBST is available as a compact open-source C++ header-only library.

如果你对本文感兴趣，想要下载完整文章进行阅读，可以关注【泡泡机器人SLAM】公众号（paopaorobot_slam）。

欢迎来到泡泡论坛，这里有大牛为你解答关于SLAM的任何疑惑。

有想问的问题，或者想刷帖回答问题，泡泡论坛欢迎你！

泡泡网站：www.paopaorobot.org

泡泡论坛：http://paopaorobot.org/bbs/