1. 基本原理

1.1 Bag-of-words原理简介

• Bag Of Words（词袋）模型，是现在一种用于图像检索的一种方法。它最早用于对于文章内容的检索，原理是将文本看作是单词的集合，不考虑文档内的词的顺序关系和语法等。通过建立词典，对每个单词出现次数进行统计，以便得到文本内容的分类。

1.2 Bag-of-features原理简介

计算机视觉的专家将Bag-of-words方法应用于图像的检索中就有了Bag-of-features。
和Bag-of-words原理相似，若将文档对应一幅图像的话，那么文档内的词就是一个图像块的特征向量。一篇文档有若干个词构成，同样的，一幅图像由若干个图像块构成，而特征向量是图像块的一种表达方式。我们求得N幅图像中的若干个图像块的特征向量，然后用k-means算法把它们聚成k类，相当于我们的词袋里就有k个词，然后来了一幅图像，看它包含哪些词，若包含单词A，就把单词A的频数加1。

1.3 Bag-of-features算法

1.3.1 图像检索流程

• 特征提取
• 学习 “视觉词典（visual vocabulary）”
• 针对输入图片对应的特征集，根据视觉词典进行量化
• 把输入图像，根据TF-IDF转化成视觉单词（visual words）的频率直方图
• 构造特征到图像的倒排表，通过倒排表快速索引相关图像
• 根据索引结果进行直方图匹配

1.3.1.1 特征提取

• 我们之前学过像SIFT、Harris角点检测算法来提取特征。
• 由于特征必须具有较高的区分度，而且要满足旋转不变性以及尺寸不变性等。因此，我们通常都会采用SIFT特征（有时为了降低计算量，也会采用其他特征，如：SURF ）
  
• SIFT特征提取可以参考之前的博文： SIFT算法-图像特征匹配、地理标记图像匹配.

1.3.1.2 学习"视觉词典"

• 提取完图像特征后，将进行"视觉词典"的学习。
• 我们会采用一些聚类算法对这些特征向量进行聚类，通常采用 k-means算法。

k-means算法：最小化每个特征 $x_i$ 与其相对应的聚类中心 $m_k$ 之间的欧式距离

算法流程:

• 随机初始化 K 个聚类中心
• 重复下述步骤直至算法收敛:
  对应每个特征，根据距离关系赋值给某个中心/类别
  对每个类别，根据其对应的特征集重新计算聚类中心

• k-means算法中的 k 值需要根据具体情况来确定。
• 聚类完成后，我们就得到了这 k 个向量组成的词典，这 k 个向量有一个通用的表达，称为visual words(视觉单词)。
  
  

1.3.1.3 对输入特征集进行量化

• 对于图像中的每一个SIFT特征，都可以在字典中找到一个最相似的 visual word，对于输入特征集，量化的过程时将该图像的每一个特征映射到距离其最接近的视觉的单词，并实现计数。

1.3.1.4 TF-IDF

• TF-IDF的主要思想是：如果某个单词在一篇文章中出现的频率高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。

• TF(Term Frequency)指的是词频，即一个词在文中出现的次数, 这个数字通常会被归一化(一般是词频除以文章总词数), 以防止它偏向长的文件。
  公式：单词w在文档d的词频为 $t{f}_w{,}_d=\frac{n_w}{\sum n_j}$

• IDF(Inverse Document Frequency)指的是逆向文件频率。某一特定词语的IDF，可以由总文件数目除以包含该词语的文件的数目，再将得到的商取对数得到。
  公式：$log\frac{总文件数目}{包含该词语的文件的数目}$
  如果包含词条t的文档越少, 则IDF越大，则说明词条具有很好的类别区分能力。

• TF-IDF实际上是：TF * IDF
  某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF。因此，TF-IDF倾向于过滤掉常见的词语，保留重要的词语。

1.3.1.5 根据TF-IDF转化成视觉单词（visual words）的频率直方图

在BOW中，一些常用词汇譬如the，it，do等等词汇，不能体现文本内容特征，但是出现频率却很高，利用TF-IDF可以降低这种不必要词汇的影响。同理，在BOF图像搜索中，图像之间也会有这样的无意义的特征出现，所以需要降低这类特征的权值。
所以我们在将输入图像转换为频率直方图时需要根据TF-IDF赋予权值。
权值为：词频与逆文档频率的乘积即TF*IDF

1.3.1.6 倒排表

倒排表是一种逆向的查找方式，在BOW中大体的思路是通过已经提取出来的词汇，反向查找出现过这个词汇的文章。如图，查找多个词汇，就形成了一个倒排表。就可以通过倒排表到相应文档快速查找词汇。

BOF中倒排表也是同理。通过对视觉词汇的反向查找，就会得到拥有同一视觉词汇的图像集合，反复多次就能得到一张倒排表。倒排表可以快速的得到新的图像与数据库里相似的图像。

2. 具体实现

2.1 数据集准备

准备了六组不同花卉的照片，每组20张

2.2 实验过程

2.2.1 SIFT特征提取

# -*- coding=utf-8 -*-
# name: nan chen
# date: 2021/6/1 11:06
# -*- coding: utf-8 -*-
from PCV.localdescriptors import sift
from PCV.tools.imtools import get_imlist

# 获取图像列表
imlist = get_imlist(r'D:\bof-picture')
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])

部分sift特征提取结果截图：

2.2.2 学习“视觉词典(visual vocabulary)”

# -*- coding=utf-8 -*-
# name: nan chen
# date: 2021/6/1 11:13
# -*- coding: utf-8 -*-
import pickle
from PCV.imagesearch import vocabulary
from PCV.tools.imtools import get_imlist
# 获取图像列表
imlist = get_imlist(r'D:\bof-picture')
nbr_images = len(imlist)
# 获取特征列表
featlist = [imlist[i][:-3] + 'sift' for i in range(nbr_images)]
# 生成词汇
voc = vocabulary.Vocabulary('bof_test')
voc.train(featlist, 50, 10)

# 保存词汇
with open(r'D:\bof-picture\vocabulary50.pkl', 'wb') as f:
    pickle.dump(voc, f)
print('vocabulary is:', voc.name, voc.nbr_words)

生成了数据模型vocabulary.pkl

2.2.3 对输入特征集进行量化

# -*- coding=utf-8 -*-
# name: nan chen
# date: 2021/6/1 11:16
# -*- 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(r'D:\bof-picture')
nbr_images = len(imlist)
# 获取特征列表
featlist = [imlist[i][:-3] + 'sift' for i in range(nbr_images)]

# 载入词汇
with open(r'D:\bof-picture\vocabulary50.pkl', 'rb') as f:
    voc = pickle.load(f)
# 创建索引
indx = imagesearch.Indexer('testImaAdd.db', voc)
indx.create_tables()
# 遍历所有的图像，并将它们的特征投影到词汇上
for i in range(nbr_images)[:120]:
    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())

对数据集中的所有图像进行量化，为所有图像创建索引，再遍历所有的图像，将它们的特征投影到词汇上，最终提交到数据库保存下来。

生成数据库：

2.2.3 建立图像索引进行图像检索

# -*- coding=utf-8 -*-
# name: nan chen
# date: 2021/6/1 11:23
import pickle
from PCV.imagesearch import imagesearch
from PCV.geometry import homography
from PCV.tools.imtools import get_imlist
from PCV.localdescriptors import sift
import warnings
warnings.filterwarnings("ignore")

# load image list and vocabulary
# 载入图像列表
imlist = get_imlist(r'D:\bof-picture')
nbr_images = len(imlist)
# 载入特征列表
featlist = [imlist[i][:-3] + 'sift' for i in range(nbr_images)]

# 载入词汇
with open(r'D:\bof-picture\vocabulary10.pkl', 'rb') as f:
    voc = pickle.load(f, encoding='iso-8859-1')

src = imagesearch.Searcher('testImaAdd.db', voc)  # Searcher类读入图像的单词直方图执行查询

# index of query image and number of results to return
# 查询图像索引和查询返回的图像数
q_ind = 3
nbr_results = 10

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

# load image features for query image
# 载入查询图像特征进行匹配
q_locs, q_descr = sift.read_features_from_file(featlist[q_ind])
fp = homography.make_homog(q_locs[:, :2].T)

# RANSAC model for homography fitting
# 用单应性进行拟合建立RANSAC模型
model = homography.RansacModel()
rank = {}
# load image features for result
# 载入候选图像的特征
for ndx in res_reg[1:]:
    locs, descr = sift.read_features_from_file(featlist[ndx])  # because 'ndx' is a rowid of the DB that starts at 1
    # get matches
    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[:6])  # 常规查询
imagesearch.plot_results(src, res_geom[:6])  # 重排后的结果

最后的重排序是先将检索出来的挑选出来，再把每一张图像进行一一比对，按照相似程度得到一个排列顺。

2.3 实验结果及分析

2.3.1 不同维度视觉词典的生成

维度越大，生成视觉词典所需要的时间越长
并且可以看到随着维度的增加，视觉词典的大小也随之增加

2.3.2 图像检索

维度 = 10

检索的图像：

检索结果：

重排序：

维度 = 50

检索的图像：

检索结果：

重排序：

维度 = 100

检索的图像：

检索结果：

重排序：

维度 = 1000

检索的图像：

检索结果：

重排序：

维度 = 5000

检索的图像：

检索结果：

重排序：

2.3.2 结果分析

由上面的实验结果可以看出：

• 当维度为10时，检索的图像和检索结果没有太大的关联，检索出来的结果大多是和原图像不同类别的花卉。
• 当维度为50、100、1000时，检索的结果较维度为10的效果好。因为当维度越来越大的时候，视觉词典的细分程度较高，整个视觉词典的大小基础词汇的个数越多，进行图像检索时可以对细小的元素进行比对，将会得到更准确的结果。但可以看出还是存在错误检索的图片。
• 当维度为5000时，检索效果又变得十分糟糕，只有一张图片是匹配的。可能是因为当维度过大时产生过拟合，检索的结果反而不好
• 所准备的数据集中所拍摄的背景存在较为相似的草地而且花卉在纹理及颜色上有相似的地方，对图像提取的SIFT特征可能相似，这导致在用所得到的"视觉词汇"进行对比时可能误配，导致结果不佳。

3. 实验中遇到的问题

ModuleFoundError: No module named pysqlite2.

解决方法：
python3中已将pysqlite2取消，进入报错的.py文件用import sqlite3 as sqlite 替换from pysqlite2 import dbapi2 as sqlite

2.

TypeError: a bytes-like object is required, not ‘str’

解决方法：
python3和Python2.7在套接字返回值解码上有区别，进入相应的.py文件，将str去掉即可

TypeError: ‘cmp’ is an invalid keyword argument for this function

解决方法：
python3中的sort函数sort(*, key=None, reverse=None)取消了cmp参数

1.手动添加cmp函数

def cmp_for_py3(a, b):
    return (a > b) - (a < b)

2.将相应.py文件中的语句修改

tmp.sort(key=cmp_to_key(lambda x,y:cmp_for_py3(x[1],y[1])))

参考：
TF-IDF算法介绍及实现