Bag-of-Words Model (BoW)

Posted on 2022-11-13 Edited on 2022-11-30 In Summary Waline:

BoW 是 NLP 中的使用较多的模型，其用于检测单词相似度。在 CV 领域，BoW 用于 SLAM 的回环检测，通过提取图像特征作为图像单词，生成词汇树和词汇数据库，从而加速回环检测过程中对历史帧的提取匹配。

BoW in CV

1 介绍

Bag-of-Words model (BoW model) 最早出现在自然语言处理和信息检索领域：

该模型忽略掉文本的语法和语序等要素，将其仅仅看作是若干个词汇的集合，文档中每个单词的出现都是独立的。
BoW 使用一组无序的单词来表达一段文字或一个文档。
近年来，BoW 模型被广泛应用于计算机视觉中。

2 基于文本的 BoW 模型 —— 举例

给定两个简单的文本：

John likes to watch movies. Mary likes too.
John also likes to watch football games.

基于两个文本中的单词，可以构建如下的词典：

{
    "John": 1,
    "likes": 2,
    "to": 3,
    "watch": 4,
    "movies": 5,
    "also": 6,
    "football": 7,
    "games": 8,
    "Mary": 9,
    "too": 10
}

词典中包含 10 个单词，每个单词有唯一索引，那么每个文本可以使用一个 10 维向量来表示：

$[1, 2, 1, 1, 1, 0, 0, 0, 1, 1] \\ [1, 1, 1, 1, 0, 1, 1, 1, 0, 0] \tag{1}$

该向量与原来文本中单词出现的顺序没有关系，而是词典中每个单词在文本中出现的频率。上述向量也可以用频率分布直方图来表示。

3 BoW 模型应用于图像检索

为了表示一副图像，可以将图像看作文档，即由若干个“视觉单词”构成的集合，同理，视觉单词之间没有顺序。

3.1 特称提取

由于视觉词汇不是文本中的单词，因此需要从图像中提取出相互独立的视觉单词，即提取出特征描述子：

SIFT 是提取图像中局部不变特征应用较广的算法，因此采用 SIFT 进行特征提取。
将每幅图像提取出的描述子保存在一个文件中，构建视觉词典。

3.2 学习“视觉词典（Visual Vocabulary）”

使用聚类算法实现视觉词典，常用的聚类算法有 K-means：

随机初始化 $k$ 个聚类中心；
对于每个特征，根据与聚类中心的距离，赋值给某个聚类中心/类别，距离的计算可以采用欧式距离：

$D(X, M) = \sum_{\text{cluster } k} \sum_{\text{point } i \text{ in cluster } k} (x_i - m_k)^2 \tag{2}$
对于每个类别，根据得到的特征集重新计算聚类中心；
重复 2，3 步，直到收敛。

3.3 用视觉词典量化输入特征集

对于输入特征，量化的过程是将该特征映射到距离其最接近的视觉单词（前面的 $k$ 个聚类结果），并实现计数。

选择合适的视觉词典规模是需要考虑的问题：

若规模太少，会出现视觉单词无法覆盖所有可能出现的情况。
若规模太多，又会计算量大，容易过拟合。
只能通过不断的测试，才能找到最合适的词典规模。

3.4 输入图像转换为频率分布直方图

利用 SIFT 算法，可以从每幅图像中提取多个特征点，通过统计每个视觉单词在词典中出现的次数，可以获得直方图。

3.5 通过倒排表快速索引图像

用 K 近邻算法进行图像检索。给定输入图像的 BoW 直方图，在数据库中查找 $k$ 个最近林的图像。对于图像分类问题，可以根据这 $k$ 个近邻图像的分类标签，获得分类结果。

3.6 根据索引结果进行直方图匹配

利用建立起来的索引找到包含特定单词的所有图像。为了获得包含多个单词的候选图像，有两种解决方法：

可以在每个单词上进行遍历，得到包含该单词的所有图像列表，然后合并这些列表。在合并后的列表中，对每一个图像 ID 出现的次数进行跟踪排序，排在列表最前面的是最好的匹配图像。
如果不遍历所有的单词，可以根据其倒排序文档频率权重进行排序，并使用那些权重最高的单词，在这些单词上进行遍历，减少计算量。

4 图像检索 —— 代码

4.1 设置

每张图片生成相应的 .sift 文件、视觉单词，以建立 BoW 模型。
设着图像集大小为 100，词典包含 1000 个单词，K-means 类别数为 10。

4.2 建立词典

# -*- coding: utf-8 -*-
import pickle
from PCV.imagesearch import vocabulary
from PCV.tools.imtools import get_imlist
from PCV.localdescriptors import sift

# 获取图像列表
imlist = get_imlist('./dataset/')
nbr_images = len(imlist)

# 获取特征列表
featlist = [imlist[i][:-3] + 'sift' for i in range(nbr_images)]

# 提取文件夹下图像的sift特征
for i in range(nbr_images):
    sift.process_image(imlist[i], featlist[i])

# 生成词汇
voc = vocabulary.Vocabulary('ukbenchtest')
voc.train(featlist, 100, 10)

# 保存词汇
with open('./dataset/vocabulary.pkl', 'wb') as f:
    pickle.dump(voc, f)

print('vocabulary is:', voc.name, voc.nbr_words)

4.3 建立图像索引

创建表，索引和索引器 indexer 类，以便将图像数据写入数据库，将上面得到的数据模型存放数据库 testImaAdd.db 中。

# -*- coding: utf-8 -*-
import pickle
from PCV.imagesearch import imagesearch
from PCV.localdescriptors import sift
import sqlite3
from PCV.tools.imtools import get_imlist

# 获取图像列表
imlist = get_imlist('./dataset/')
nbr_images = len(imlist)

# 获取特征列表
featlist = [imlist[i][:-3] + 'sift' for i in range(nbr_images)]

# 载入词汇
with open('./dataset/vocabulary.pkl', 'rb') as f:
    voc = pickle.load(f)

# 创建索引
indx = imagesearch.Indexer('testImaAdd.db', voc)
indx.create_tables()

# 遍历所有的图像，并将它们的特征投影到词汇上
for i in range(nbr_images)[:100]:
    locs, descr = sift.read_features_from_file(featlist[i])
    indx.add_to_index(imlist[i], descr)

# 提交到数据库
indx.db_commit()
con = sqlite3.connect('testImaAdd.db')
print(con.execute('select count (filename) from imlist').fetchone())
print(con.execute('select * from imlist').fetchone())

4.4 图像索引测试

# -*- coding: utf-8 -*-
import pickle
from PCV.localdescriptors import sift
from PCV.imagesearch import imagesearch
from PCV.geometry import homography
from PCV.tools.imtools import get_imlist

# 载入图像列表
imlist = get_imlist('./dataset/first1000/')
nbr_images = len(imlist)
# 载入特征列表
featlist = [imlist[i][:-3 ] +'sift' for i in range(nbr_images)]

# 载入词汇
with open('./dataset/vocabulary.pkl', 'rb') as f:
    voc = pickle.load(f)
src = imagesearch.Searcher('testImaAdd.db' ,voc)

# 查询图像索引和查询返回的图像数
q_ind = 0
nbr_results = 20

# 常规查询(按欧式距离对结果排序)
res_reg = [w[1] for w in src.query(imlist[q_ind])[:nbr_results]]
print('top matches (regular):', res_reg)

# 载入查询图像特征
q_locs ,q_descr = sift.read_features_from_file(featlist[q_ind])
fp = homography.make_homog(q_locs[:, :2].T)

# 用单应性进行拟合建立RANSAC模型
model = homography.RansacModel()

rank = {}

# 载入候选图像的特征
for ndx in res_reg[1:]:
    locs ,descr = sift.read_features_from_file(featlist[ndx])
    matches = sift.match(q_descr ,descr)
    ind = matches.nonzero()[0]
    ind2 = matches[ind]
    tp = homography.make_homog(locs[: ,:2].T)
    
    # compute homography, count inliers. if not enough matches return empty list
    try:
        H ,inliers = homography.H_from_ransac(fp[: ,ind] ,tp[: ,ind2] ,model ,match_theshold=4)
    except:
        inliers = []

    # store inlier count
    rank[ndx] = len(inliers)

# sort dictionary to get the most inliers first
sorted_rank = sorted(rank.items(), key=lambda t: t[1], reverse=True)
res_geom = [res_reg[0] ] +[s[0] for s in sorted_rank]
print ('top matches (homography):', res_geom)

# 显示查询结果
imagesearch.plot_results(src ,res_reg[:11])  # 常规查询
imagesearch.plot_results(src ,res_geom[:11])  # 重排后的结果

5 DBoW3

5.1 简介

DBoW3 是一个开源的 C++ 词袋模型库，可以将图像转化成视觉词袋表示。它采用层级树状结构将相近的图像特征在物理存储上聚集在一起，创建一个视觉词典。
DBoW3 还生成一个图像数据库，带有顺序索引和逆序索引，可以使图像特征的检索和对比非常快。
DBoW3 是 DBoW2 的增强版，仅依赖 OpenCV，能够很方便的使用。
DBoW3 两个比较重要的类是 Vocabulary 和 Database：
- Vocabulary 表示图像库的视觉词汇表，并可以将任一的图像转换为 BoW 表示；
- Database是一个图像数据库，能够方便的对图像进行检索。

5.2 安装 DBoW3

git clone https://github.com/rmsalinas/DBow3.git # 下载源文件
cd DBoW3 					# 进入源文件夹
mkdir build 				# 新建一个编译目标文件夹
cd build 					# 将build作为make工作路径
cmake -DUSE_CONTRIB=ON .. 	# 编译上一级目录，如果提前安装好了contrib_modules，则使用cmake选项-DUSE_CONTRIB=ON使能SURF，否则直接运行cmake ..
make -j4 					# 取决于您的电脑的线程数量
sudo make install 			# 安装DBoW3

5.3 Vocabulary 构建

void vocabulary(const vector<cv::Mat> &features, const string &file_path, int k = 9, int l = 3){
    // Branching factor and depth levels
    const DBoW3::WeightingType weight = DBoW3::TF_IDF;
    const DBoW3::ScoringType score = DBoW3::L2_NORM;

    DBoW3::Vocabulary voc(k, l, weight, score);
    cout << "Creating a small " << k << "^" << l << " vocabulary..." << endl;
    voc.create(features);
    cout << "...done!" << endl;
    
    //cout << "Vocabulary infomation: " << endl << voc << endl << endl;

    // save the vocabulary to disk
    cout << endl << "Saving vocabulary..." << endl;
    stringstream ss;
    ss << file_path << "/small_voc.yml.gz";
    voc.save(ss.str());
    cout << "Done" << endl;
}

5.4 构建 Database

void database(const vector<cv::Mat> &features,const string &file_path){
    // load the vocabulary from disk
    stringstream ss ;
    ss << file_path << "/small_voc.yml.gz";
    DBoW3::Vocabulary voc(ss.str());

    DBoW3::Database db(voc, false, 0); // false = do not use direct index
    // add images to the database
    for(size_t i = 0; i < features.size(); i++)
        db.add(features[i]);

    cout << "... done!" << endl;

    cout << "Database information: " << endl << db << endl;

    // we can save the database. The created file includes the vocabulary
    // and the entries added
    cout << "Saving database..." << endl;
    db.save("small_db.yml.gz");
    cout << "... done!" << endl;
}

5.5 调用 query 查找图片

   // auto fdetector=cv::xfeatures2d::SURF::create(400, 4, 2);
   auto fdetector = cv::xfeatures2d::SIFT::create(0, 3, 0.2, 10);
   vector<cv::KeyPoint> kpts;
   cv::Mat des;
   fdetector->detectAndCompute(img, noArray(), kpts, des);

DBoW3::QueryResults ret;
int max_results = 5;  // 输出前 5 张图像
   db.query(des, ret, max_results);

6 回环检测中的 BoW

6.1 视觉词袋

对描述子聚类后，可以用一个 $k$ 维向量表示该图。构建视觉词袋的步骤是：

对图像集合检测特征，形成特征描述子；
对描述子进行聚类来形成词典，用层次 K-means 来形成词汇树（Vocabulary Tree），每个节点下的描述子相近，可以认为同一个节点下的这些描述子是一个视觉单词。如一个三层、每层 4 个聚类的词汇树，可以形成 4 维的词向量，也可以是 16 维。
对图像集中的每张图像，提取其对应特征描述子进行分类，然后得到分别属于 4 个类别的描述子个数，即得到一个 4 维向量，归一化该向量，即将该图像表示成一个 4 维向量。
将每张图像都表示为上述 4 维向量，根据向量相似度就可以知道两张图像之间的相似度。

举例：

看书的时候不认识那么多字，买一本词典，一遍翻词典，一遍看书；在后面的步骤中，需要产生一个数据库，用来记录查词典时所用到的单词，方便回看时能快速找到。

在实际使用的过程中，第一步需要训练产生一本词典，如上例，单词就是一些特征聚类的结果。可能有几十万甚至几百万张训练的图片，需要依次提取特征，然后在特征空间中就会有多个特征信息，接下来要用这些特征聚类产生单词，聚类的数量取决于选择的树形结构。

6.2 词典产生流程图

所有特征描述子分布在特征空间；
根据设定好的树形结构参数，进行 Kmean++ 聚类，产生叶子结点；
对产生的节点依次进行 Kmean++ 聚类，直至产生根节点。

6.3 视觉词向量数据库

一般提前训练好词典，设计成单词树，每个树节点包含一个逆序索引信息包，每帧图像包含一个顺序索引信息包。

对新进来的图像帧，将其中每个特征点都从词汇树根节点往下遍历，取汉明距离最小的节点接着往下遍历直到叶节点。最终，计算各个叶节点上的数目并形成图像表达向量 $\bold{v}$ ，同时得到图像的顺序索引，以便用于之后的回环检测。

逆序索引：

逆序索引覆盖了所有出现的单词；
对每个单词节点，其存储了逆序索引。逆序索引存储的是图像的索引号，以及该单词在对应图像中的权重（即逆文本频率）。
每进来一张图像，数据库以及逆序索引就需要更新。
如上图，词汇树有 $L_W$ 层，0 层代表叶节点即单词 word 所在的节点，该节点包含多个特征点。节点 1 的逆序索引的表示，在图 68 的逆文本频率为 0.79，在图 82 为 0.73。
如下图为逆序索引加快搜索的示意。

顺序索引：

在回环检测的最后阶段——几何结构验证阶段，可以加速匹配候选图像与当前图像之间的特征点对。
对于每张图像，顺序索引存储出现在图像中的每个特征（word）对应的父节点；找到父节点后再把父节点下边所有特征也加入顺序索引。在最后的几何验证阶段就可以迅速找到两帧之间的特征匹配点对。需要为每张图建立 $0 - L_W$ 所有层的顺序索引。
如上图，第 $l$ 层中，图 1 的顺序索引有节点 1，节点 1 下边的所有特征点在本图像中出现的只有本图像中的第 65 个特征点。

6.4 回环检测流程

BoW 模型主要是利用训练词典产生高度差异型的模型，每张图片通过词典检索，都会得到一个独一无二的直方图向量，向量的维度就是词典个数（一般是 100 万）。在具体写程序时不会产生这么大维度的链表，可以有一个等效的模型。

图像 $\bold{\rightarrow}$ 向量：

输入图像 $I$ ，进行特征检测与特征描述，特征点数不超过阈值；
将每个特征通过树形结构字典，得到 BoW 向量 $\bold{v}$ ，向量的维度为特征数量或叶节点数量。

向量 $\bold{v}$ 的数据单元结构为 map<index, value> 或 map<word index, weight>。

word index：

将每个特征从根节点 $\rightarrow$ 叶节点，依次与当前子节点进行比较，选择汉明距离最小的节点作为中继节点，以此类推，直到叶节点。

weight：

$w_t^i = \operatorname{tf}(i, I_t) \times \operatorname{idf}(i),\ w_t^i = \frac{w_t^i}{\sum w_t^i} \\ \operatorname{tf}(i, I_t) = \frac{n_{i I_t}}{n_{I_t}},\ \operatorname{idf}(i) = \log \frac{N}{n_i} \tag{3}$

每个单词的权重有归一化过程，权重由 tf 和 idf 两部分构成：对于前者，分子为当前图片中出现单词 $i$ 的个数，分母为图像总共包含的单词个数，这是在线得到的；后者是词典的属性，已经离线生成，不会发生改变，分子为生成词典时所包含的训练图片数量，分母为出现单词 $i$ 的图片个数。

在得到了两张图片的 BoW 向量之后，需要比较两者的相似性：

$s(\bold{v}_1, \bold{v}_2) = 1 - \frac{1}{2} \cdot \left| \frac{\bold{v_1}}{|\bold{v}_1|} - \frac{\bold{v_2}}{|\bold{v}_2|} \right| \tag{4}$

实际计算过程中，逐个找到 index 相同的 word，计算相似度然后累加得到相似度：

$s(\bold{v}_1, \bold{v}_2) = - \frac{1}{2} \sum (|\bold{v}_1 - \bold{v}_2| - |\bold{v}_1| - |\bold{v}_2|) \tag{5}$

6.5 回环检测的数据库查询

查询的数据库就是上述在线更新和维护的逆序索引。利用逆序索引数据库简化检索过程；不采用暴力匹配，只匹配包含相同单词的个别图像信息，加快检索过程。

当新的一帧到来，先计算其表达向量 $\bold{v}_t$ ，随后凭借逆序索引得到一连串的相似图像,分别与每一张相似图像 $\bold{v}_{t_j}$ 的归一化相似度（ $t - \Delta t$ 表示上一帧）：

$\eta(\bold{v}_t, \bold{v}_{t_j}) = \frac{s(\bold{v}_t, \bold{v}_{t_j})}{s(\bold{v}_t, \bold{v}_{t - \Delta t})} \tag{6}$

防止因分母过小，而引起的得分过大，需要对分母增加条件（有特征点数要求或者得分要求）；
需要对最后得分设立阈值，过滤得分较少的候选图像，保留符合要求的候选图像进入组匹配进行校验

6.6 组匹配

当图像 $I_t, I_{t'}$ 表示了一个真正的回环，则 $I_t$ 同样和 $I_{t \pm \Delta t}, I_{t \pm 2 \Delta t}$ 也有较高的相似性，定义相似得分和函数如下：

$H (\bold{v}_t, \bold{V}_{T_i}) = \sum_{j = n_i}^{m_i} \eta (\bold{v}_t, \bold{v_{t_j}}) \tag{7}$

其中 $\bold{V}_{T_i}$ 表示候选图像所在集合，范围从 $\bold{v}_{t_{ni}}$ 到 $\bold{v}_{t_{mj}}$ 。