视觉SLAM之词袋(bag of words) 模型与K-means聚类算法浅析(1)

在目前实际的视觉SLAM中,闭环检测多采用DBOW2模型https://github.com/dorian3d/DBoW2,而bag of words 又运用了数据挖掘的K-means聚类算法,笔者只通过bag of words 模型用在图像处理中进行形象讲解,并没有涉及太多对SLAM的闭环检测的应用。

1.Bag-of-words模型简介

Bag-of-words模型是信息检索领域常用的文档表示方法。在信息检索中,BOW模型假定对于一个文档,忽略它的单词顺序和语法、句法等要素,将其仅仅看作是若干个词汇的集合,文档中每个单词的出现都是独立的,不依赖于其它单词是否出现。 也就是说,文档中任意一个位置出现的任何单词,都不受该文档语意影响而独立选择的。举个例子就好理解:

例如有如下两个文档:

1:Bob likes to play basketball, Jim likes too.

2:Bob also likes to play football games.

基于这两个文本文档,构造一个词典:

Dictionary = {1:”Bob”, 2. “likes”, 3. “to”, 4. “play”, 5. “basketball”, 6. “also”, 7. “football”, 8. “games”, 9. “Jim”, 10. “too”}。

这个词典一共包含10个不同的单词,利用词典的索引号,上面两个文档每一个都可以用一个10维向量表示(用整数数字0~n(n为正整数)表示某个单词在文档中出现的次数):

1:[1, 2, 1, 1, 1, 0, 0, 0, 1, 1]

2:[1, 1, 1, 1 ,0, 1, 1, 1, 0, 0]

向量中每个元素表示词典中相关元素在文档中出现的次数。不过,在构造文档向量的过程中可以看到,我们并没有表达单词在原来句子中出现的次序。

Bag-of-words模型应用于图像表示:

为了表示一幅图像,我们可以将图像看作文档,即若干个“视觉词汇”的集合,同样的,视觉词汇相互之间没有顺序。

视觉词典的生成流程:

由于图像中的词汇不像文本文档中的那样是现成的,我们需要首先从图像中提取出相互独立的视觉词汇,这通常需要经过三个步骤:(1)特征检测,(2)特征表示,(3)单词本的生成。  下图是从图像中提取出相互独立的视觉词汇:

通过观察会发现,同一类目标的不同实例之间虽然存在差异,但我们仍然可以找到它们之间的一些共同的地方,比如说人脸,虽然说不同人的脸差别比较大,但眼睛, 嘴,鼻子等一些比较细小的部位,却观察不到太大差别,我们可以把这些不同实例之间共同的部位提取出来,作为识别这一类目标的视觉词汇。

构建BOW码本步骤:

利用K-Means算法构造单词表。用K-means对第二步中提取的N个SIFT特征进行聚类,K-Means算法是一种基于样本间相似性度量的间接聚类方法,此算法以K为参数,把N个对象分为K个簇,以使簇内具有较高的相似度,而簇间相似度较低。聚类中心有k个(在BOW模型中聚类中心我们称它们为视觉词),码本的长度也就为k,计算每一幅图像的每一个SIFT特征到这k个视觉词的距离,并将其映射到距离最近的视觉词中(即将该视觉词的对应词频+1)。完成这一步后,每一幅图像就变成了一个与视觉词序列相对应的词频矢量。

假定我们将K设为4,那么单词表的构造过程如下图所示:

第三步:

利用单词表的中词汇表示图像。利用SIFT算法,可以从每幅图像中提取很多个特征点,这些特征点都可以用单词表中的单词近似代替,通过统计单词表中每个单词在图像中出现的次数,可以将图像表示成为一个K=4维数值向量。将这些特征映射到为码本矢量,码本矢量归一化,最后计算其与训练码本的距离,对应最近距离的训练图像认为与测试图像匹配。请看下图:

我们从人脸、自行车和吉他三个目标类图像中提取出的不同视觉词汇,而构造的词汇表中,会把词义相近的视觉词汇合并为同一类,经过合并,词汇表中只包含了四个视觉单词,分别按索引值标记为1,2,3,4。通过观察可以看到,它们分别属于自行车、人脸、吉他、人脸类。统计这些词汇在不同目标类中出现的次数可以得到每幅图像的直方图表示:

人脸:  [3,30,3,20]
自行车:[20,3,3,2]
吉他:  [8,12,32,7]

其实这个过程非常简单,就是针对人脸、自行车和吉他这三个文档,抽取出相似的部分(或者词义相近的视觉词汇合并为同一类),构造一个词典,词典中包含4个视觉单词,即Dictionary = {1:”自行车”, 2. “人脸”, 3. “吉他”, 4. “人脸类”},最终人脸、自行车和吉他这三个文档皆可以用一个4维向量表示,最后根据三个文档相应部分出现的次数画成了上面对应的直方图。一般情况下,K的取值在几百到上千,在这里取K=4仅仅是为了方便说明。

总结一下步骤:

第一步:利用SIFT算法从不同类别的图像中提取视觉词汇向量,这些向量代表的是图像中局部不变的特征点;

第二步:将所有特征点向量集合到一块,利用K-Means算法合并词义相近的视觉词汇,构造一个包含K个词汇的单词表;

第三步:统计单词表中每个单词在图像中出现的次数,从而将图像表示成为一个K维数值向量。

时间: 05-31

视觉SLAM之词袋(bag of words) 模型与K-means聚类算法浅析(1)的相关文章

视觉SLAM之词袋(bag of words) 模型与K-means聚类算法浅析(2)

聚类概念: 聚类:简单地说就是把相似的东西分到一组.同 Classification (分类)不同,分类应属于监督学习.而在聚类的时候,我们并不关心某一类是什么,我们需要实现的目标只是把相似的东西聚到一起,因此,一个聚类算法通常只需要知道如何计算相似 度就可以开始工作了.聚类不需要使用训练数据进行学习,应属于无监督学习. 我们经常接触到的聚类分析,一般都是数值聚类,一种常见的做法是同时提取 N 种特征,将它们放在一起组成一个 N 维向量,从而得到一个从原始数据集合到 N 维向量空间的映射,然后基

视觉slam闭环检测之-DBoW2 -视觉词袋构建

需要准备的知识点:http://www.cnblogs.com/zjiaxing/p/5616653.html      http://www.cnblogs.com/zjiaxing/p/5616664.html http://www.cnblogs.com/zjiaxing/p/5616670.html http://www.cnblogs.com/zjiaxing/p/5616679.html 利用 BoVW 表示图像,将图像进行结构化描述.BoVW思想是将图像特征整合成视觉单词,将图像特

BoW(词袋)模型详细介绍

最近学习BoW模型,将自己网上看到的资料及对论文的理解,将BoW模型总结如下! BoW模型 Bag-of-words model (BoW model) 最早出现在自然语言处理(Natural Language Processing)和信息检索(Information Retrieval)领域..该模型忽略掉文本的语法和语序等要素,将其仅仅看作是若干个词汇的集合,文档中每个单词的出现都是独立的.BoW使用一组无序的单词(words)来表达一段文字或一个文档..近年来,BoW模型被广泛应用于计算机

视觉SLAM漫淡(二):图优化理论与g2o的使用

视觉SLAM漫谈(二):图优化理论与g2o的使用 1    前言以及回顾 各位朋友,自从上一篇<视觉SLAM漫谈>写成以来已经有一段时间了.我收到几位热心读者的邮件.有的希望我介绍一下当前视觉SLAM程序的实用程度,更多的人希望了解一下前文提到的g2o优化库.因此我另写一篇小文章来专门介绍这个新玩意. 在开始本篇文章正文以前,我们先来回顾一下图优化SLAM问题的提法.至于SLAM更基础的内容,例如SLAM是什么东西等等,请参见上一篇文章.我们直接进入较深层次的讨论.首先,关于我们要做的事情,你

视觉SLAM之RANSAC算法用于消除图像误匹配的原理

在基于特征点的视觉SLAM中,通常情况下,在特征匹配过程中往往会存在误匹配信息,使得计算获取的位姿精度低,易产生位姿估计失败的问题,因此,剔除这些错配点有很大的必要性.常会用到RANSAC算法进行消除两两匹配图像的误匹配点,如果只停留在应用的层面上很简单,直接调用opencv函数就行,看到效果时,感觉好神奇,到底怎么实现的啊,以前一直也没弄太明白,与图像结合的博客也比较少,在查阅了一些资料后,笔者似乎明白了一点,希望笔者的总结会对您的理解有帮助. 首先先介绍一下RANSAC算法(RANdom S

视觉SLAM中的数学基础 第三篇 李群与李代数

视觉SLAM中的数学基础 第三篇 李群与李代数 前言 在SLAM中,除了表达3D旋转与位移之外,我们还要对它们进行估计,因为SLAM整个过程就是在不断地估计机器人的位姿与地图.为了做这件事,需要对变换矩阵进行插值.求导.迭代等操作.例如,在经典ICP问题中,给定了两组3D点,我们要计算它们之间的变换矩阵.假设第一组的3D点为$\mathbf{P}=\{ \mathbf{p}_i | i = [1,2, \ldots, N] \}$,第二组3D点为$\mathbf{Q}=\{ \mathbf{q}

视觉SLAM中的数学基础 第二篇 四元数

视觉SLAM中的数学基础 第二篇 四元数 什么是四元数 相比欧拉角,四元数(Quaternion)则是一种紧凑.易于迭代.又不会出现奇异值的表示方法.它在程序中广为使用,例如ROS和几个著名的SLAM公开数据集.g2o等程序都使用四元数记录机器人的姿态.因此,理解四元数的含义与用法,对学习SLAM来说是必须的.本节我们就来讲讲四元数. 首先,请读者不要对四元数有什么神秘的感觉.四元数仅是3D姿态的一种表达方式,我们用一个单位四元数表达原本用旋转矩阵表示的三维旋转.这样做一个直接的好处是省空间.一

重磅︱R+NLP:text2vec包简介(GloVe词向量、LDA主题模型、各类距离计算等)

词向量的表示主流的有两种方式,一种当然是耳熟能详的google的word2vec,还有一类就是GloVe.那么前面一类有三个开源的包,后面这一类我倒是看到得不多,恰好是在我关注了许久的一个包里面有,它就是text2vec啦.该包提供了一个强大API接口,能够很好地处理文本信息. 本包是由C++写的,流处理器可以让内存得到更好的利用,一些地方是用RcppParallel包进行并行化加乘,同时兼容各个系统的服务器.如果没有并行的地方,大家也可以自己用foreach包来自己加速. ----------

NLP系列(4)_朴素贝叶斯实战与进阶(转)

http://blog.csdn.net/han_xiaoyang/article/details/50629608 作者: 寒小阳 && 龙心尘 时间:2016年2月. 出处:http://blog.csdn.net/han_xiaoyang/article/details/50629608 http://blog.csdn.net/longxinchen_ml/article/details/50629613 声明:版权所有,转载请联系作者并注明出处 1.引言 前两篇博文介绍了朴素贝叶