词袋模型:DBoW原理介绍以及使用方法

2024-06-05 17:32

本文主要是介绍词袋模型:DBoW原理介绍以及使用方法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 词袋模型介绍

词袋模型在很多方面都有应用,其的原理也很容易理解:

有以下一些句子:

1. my name is jack!
2. I like to eat apples!
3. I am a student!
4. I like to take pictures!

我现在交给你一个任务,从上面四句话中找到一句和下面这句话最相似的一句(这里认为同样的单词越多越相似):

I am a boy!

请原谅我,我并没有侮辱你智商的意思! 你几乎想都没想就说出了和第3句最像。

因为上面这个例子比较简单。但是当我们的句子变成文章那么长时,我相信再让你去找就没有那么容易了。

于是我们就必须探索出一种方法,让计算机去找!

上面出现的五句话中,包含了以下这些单词,一共15个,我们就用这15个单词构造一个字典:

Iamastudentliketoeatapplestakepicturesmynameisjackboy

有了以上这个单词表之后,我们可以使用这个单词表来表示上面的四个句子。

对于第1句:my name is jack!
1.[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0]

提示: 用一个15维的向量来表示一个句子,这个向量和上表的单词顺序一致,如果当前句子出现了上表中的某一个单词,那么单词对应的向量位就为1,否则为0!

同理,可以得到另外几个单词的向量表示:
第2句: I like to eat apples!
2.[1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0]

第3句:I am a student!
3.[1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

现在再来看刚才的查找任务,需要查找的句子为:I am a boy!

其对应的向量为[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

现在用向量表示这些句子之后,再找最相似的句子就容易多了,只需要按找元素位来比较,比方说:
待查找句子的向量与第3句的向量,在第1,2,3位上都是1,所以它们的相似结果是3
同理,待查找的句子与第1句,第2句,相似结果分别是0和1

以上就是一个词袋模型的思路,但是有一点儿你需要注意,上面这个例子只是用来给你理解词袋模型的思想,其中处理问题的细节,并不具有参考性,在实际情况中可以会有多种多样的处理方法,多种多样的变体,甚至有时你都很难找到词袋模型的影子。

2.DBoW的原理

DBoW就是一种从词袋思想中走出来的算法。在视觉SLAM中它已经成为了回环检测必不可少的工具。它在SLAM中不但可以用来做回环检测,还能用来加快特征点的匹配。

它和我们上面的例子步骤是一样的,也是先创建字典,然后进行查找。

2.1 创建词汇树

DBoW创建的字典方式是通过树型结构来完成的。如下图:
在这里插入图片描述

实际上真实使用的词汇树比这个大很多,为了方便只是用一棵小树进行示意!

下面来看一下这棵树是怎么得到的:
在这里插入图片描述

画的好丑啊!

我们现在有1000个描述子,我们先将它放在根节点里(最上面那个圆圈)

然后对这1000个点进行聚类(你竟然不知道聚类是啥!?),将其聚类为3类,然后分别将它们分配给根节点下一级的三个节点,根据聚类结果,它们分别获得了200、300和500个描述子。

然后继续对这些点分别进行聚类,对于中间层最左边的200个描述子,再进行聚类,其又被分配到了下一级节点,分别被分配了50、100、50个描述子。以此类推,就得到了整个词汇树。

这个过程就是词汇树的训练过程,当然真实的词汇树分支多,层数更深。

有一点儿还需要注意,其中每一个节点都有一个值用来表示聚类中心。例如根节点有1000个描述子,就会根据这些描述子计算一个聚类中心。类似的最下面那一层,也会根据其中被分配到的描述子计算聚类中心,而这个聚类中心就是单词(words)。因此对于这种分支为3,深度为2的词汇树,一共可以获得9个单词。

当我们保存整个训练好的词汇树时,只要把树的结构和聚类中心都保存下来就行了,其中那些用来训练的描述子都可以扔掉了。

以上过程用更加规范的句子描述:

  • step1.在根节点将样本聚为k类
  • step2.对第一层的每个节点,把属于该节点的样本再聚为k类
  • step3.重复step2,最后得到叶子层,每个叶子对应一个word,最终得到的树就是vocabulary tree

聚类方法是kmeans++

2.2 使用词汇树

训练好了词汇树,下面就是如果使用它了。

例如,我们现在有一个分支为10,层数为5的词汇树,那么其共有单词(word)数量为100000个

例如现在有一张图像,我们对其提取了2000个特征点(关键点+描述子),然后将其每一个描述子通过词汇树找到对应的单词。

在这里插入图片描述
步骤为:

  • step1:先将描述子放在根节点处;
  • step2:然后将描述子与第一层聚类进行比较,找到与自己最相似的那个子节点,然后将其放入当前子节点;
  • step3:重复step2,直到该描述子被分配了叶子节点中。

那么叶子节点在训练时得到聚类中心(其实也相当于是描述子),就是当前描述子对应的单词,然后将对每一个描述子都执行这样的操作,那么就会得到每一个描述子对应的单词。

注意:如果从图像中提取的2000个描述子,全部都落入某一个叶子节点中,那么当前图像经过词袋模型转换之后,就只有一个单词。如果2000个描述子经过词袋树之后,落入了不相同的叶子节点中,那么这张图片就有2000个单词。

这就是转换描述子为单词的过程!

你是否明白这个过程了?

在很多视觉SLAM系统中,它对每一个KeyFrame都进行了如上述的描述子转word的过程,所以每一个KeyFrame都有一个词汇向量(BowVector),当我们需要回环检测时,只需要从这些KeyFrame中找到与当前单词数最多的那个KayFrame。

理论上来说,上面的回环检测是行得通的,但是实际上单词数相似的很多,也并不一定就是真正的回环帧,所以在实际的应用中会加入非常严格的判断。这一点可以参考ORB-SLAM2的做法进行学习。

当然词汇树还有别的应用,例如加快特征点匹配过程中的搜索。再拿出那张很丑的图:

在这里插入图片描述
我们现在有一个描述子想要与1000个描述子进行匹配搜索,找到最近的一个,最朴素的做法是暴力匹配,做1000次比较,求出汉明距离最近的那个。但是如果稍微利用一下词汇树,情况就会容易很多,1000个描述子,进行一次聚类,可以得到第一层。我只需要去第一层中比较哪个节点的聚类中心离当前描述子最近,然后就去那个节点中进行搜索。比方说,第一层中的最左边那个节点的聚类中心离当前描述子最近,那么就只需要在这200个里面进行搜索匹配。当然还可以进一步缩小搜索空间,在这200个里面还可以根据聚类结果(第二层聚类得到的节点),进行第二层的聚类中心比较,又可以进一步缩小搜索。

简单来说,上面的步骤可以概括为,一个描述子在根节点处,与子节点的聚类中心进行比较,得到了最近的那个,然后在最近的那个节点里,在进行聚类中的比较,又获得了它的子节点,然后一层一层的缩小搜索范围。

当然不能缩到太小,太小之后,可能就会导致结果中没有这个要查找的描述子。这个道理就相当于是你想找一个叫张伟的人,然后限定了在A市找,实际上他在B市,那你在A市永远找不到它,所以此时就需要扩到查找范围。

2.3 每个单词(words)都一样重要吗?

在上面的介绍过程中,实际上忽略了一个问题,那就是每一个单词都一样重要吗?试想一下上面那个查找句子的例子,如果给你一个单词’I’你能确定是哪个句子吗?我想你不行!但是给你一个’apple’你就确定了是第二个句子。所以’I’和’apple’虽然都是单词,但是其重要程度是不一样的。

对于DBoW,它采用了一些方法量化单词的重要性。当我们拿到一棵已经建好的树,当我们进行描述子的单词匹配时,发现大量的描述子都被分配到了某一个叶子节点中,那么当前叶子节点的word权重就比较低。

DBoW算法一共提供了三种权重计算方法,其计算方法如下:

  • 1.词频Term Frequency(TF):某个词在文章中出现的次数。为了归一化,词频也可以定义成,某个词在文章中出现的次数 / 文章的总词数。如果一个词比较少见,那么区分度就大。
  • 2.逆向文件频率Inverse document frequency(IDF):需要一个语料库,来模拟语言的使用环境。IDF定义为,log(语料库的文档总数 / 包含该词的文档数 +1 )。如果一个词越常见,那么分母就越大,逆文档频率就越小,越接近0。
  • 3.TF-IDF:词频(TF)* 逆向文件频率(IDF)。如果某个词比较少见,但是它在这篇文章中多次出现,那么它很可能就反映了这篇文章的特性,正是我们所需要的关键词。某个词对文章的重要性越高,它的TF-IDF值就越大。

所以当我们我们SLAM系统在运行时,不停低有KeyFrame描述子转换为单词,所以单词对应的权重也就在不停地进行更新!

3.总结

上面通过一些例子简单的介绍了DBoW的算法思想,这其中主要是介绍思路,所以并没有针对算法细节做很多介绍。如果你对算法细节有兴趣,可以参考作者的论文和源码!

如果有机会,我会写一下DBoW在ORB-SLAM2中的用法的具体细节!

这篇关于词袋模型:DBoW原理介绍以及使用方法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1033710

相关文章

vue使用docxtemplater导出word

《vue使用docxtemplater导出word》docxtemplater是一种邮件合并工具,以编程方式使用并处理条件、循环,并且可以扩展以插入任何内容,下面我们来看看如何使用docxtempl... 目录docxtemplatervue使用docxtemplater导出word安装常用语法 封装导出方

Linux换行符的使用方法详解

《Linux换行符的使用方法详解》本文介绍了Linux中常用的换行符LF及其在文件中的表示,展示了如何使用sed命令替换换行符,并列举了与换行符处理相关的Linux命令,通过代码讲解的非常详细,需要的... 目录简介检测文件中的换行符使用 cat -A 查看换行符使用 od -c 检查字符换行符格式转换将

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON(序列化)2.2 JSON 转对象(反序列化)3.

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

Elasticsearch 在 Java 中的使用教程

《Elasticsearch在Java中的使用教程》Elasticsearch是一个分布式搜索和分析引擎,基于ApacheLucene构建,能够实现实时数据的存储、搜索、和分析,它广泛应用于全文... 目录1. Elasticsearch 简介2. 环境准备2.1 安装 Elasticsearch2.2 J

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain