????????（1）输入图片
????????（2）特征提取：即将图片数据进行降维，提取数据的判别性信息，一般将一张图片降维成一个向量；
????????（3）度量学习：利用度量函数，计算图片特征之间的距离，作为loss, 训练特征提取网络，使得相似图片提取的特征相似，不同类的图片提取的特征差异性较大。
????????（4）重排序：利用数据间的流形关系，对度量结果进行重新排序，从而得到更好的检索结果。

二、Bag Of Words模型(BOW)

2.1 简介

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

2.2 原理

????????将Bag-of-words模型应用于图像，为了表示一幅图像，我们可以将图像看作文档，即若干个“视觉词汇”的集合，同样的，视觉词汇相互之间没有顺序。

????????由于图像中的词汇不像文本文档中那样是现成的，我们需要首先从图像中提取出相互独立的视觉词汇，这通常需要经过以下几个步骤：

????????（1）特征提取

????????（2）学习 “视觉词典（visual vocabulary）”

????????（3）针对输入图片对应的特征集，根据视觉词典进行量化

????????（4）把输入图像，根据TF-IDF转化成视觉单词（visual words）的频率直方图

????????（5）构造特征到图像的倒排表，通过倒排表快速索引相关图像

????????（6）根据索引结果进行直方图匹配

2.2.1 特征提取

我们可以用SIFT、Harris角点检测算法来提取特征。
由于特征必须具有较高的区分度，而且要满足旋转不变性以及尺寸不变性等。因此，我们通常都会采用SIFT特征（SIFT算法在之前的博客中已有详细介绍，这里就不再赘述）

2.2.2 学习“视觉词典”

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

????????而SIFT算法是提取图像中局部不变特征的应用最广泛的算法，因此我们可以用SIFT算法从图像中提取不变特征点，作为视觉词汇，并构造单词表，用单词表中的单词表示一幅图像。

????????接下来，我们通过上述图像展示如何通过Bag-of-words模型，将图像表示成数值向量。现在有三个目标类，分别是人脸、自行车和吉他。

利用SIFT算法，从每类图像中提取视觉词汇，将所有的视觉词汇集合在一起，如下图所示：

利用K-Means算法构造单词表。K-Means算法是一种基于样本间相似性度量的间接聚类方法，此算法以K为参数，把N个对象分为K个簇，以使簇内具有较高的相似度，而簇间相似度较低。SIFT提取的视觉词汇向量之间根据距离的远近，可以利用K-Means算法将词义相近的词汇合并，作为单词表中的基础词汇，假定我们将K设为4，那么单词表的构造过程如下图所示：

Kmeans算法：

? ? ? ? 最小化每个特征X~i~与其相对应的聚类中心m~k~之间的欧式距离

算法流程:

（1）随机初始化 K 个聚类中心

（2）重复下述步骤直至算法收敛:
????????????????对应每个特征，根据距离关系赋值给某个中心/类别
????????????????对每个类别，根据其对应的特征集重新计算聚类中心

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

2.2.3 量化输入特征集

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

2.2.4 TF-IDF

TF-IDF的主要思想是：如果某个单词在一篇文章中出现的频率高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。
TF(Term Frequency)指的是词频，即一个词在文中出现的次数, 这个数字通常会被归一化(一般是词频除以文章总词数), 以防止它偏向长的文件。
IDF(Inverse Document Frequency)指的是逆向文件频率。某一特定词语的IDF，可以由总文件数目除以包含该词语的文件的数目，再将得到的商取对数得到。?

????????如果包含词条t的文档越少, 则IDF越大，则说明词条具有很好的类别区分能力

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

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

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

????????上图中，我们从人脸、自行车和吉他三个目标类图像中提取出的不同视觉词汇，而构造的词汇表中，会把词义相近的视觉词汇合并为同一类，经过合并，词汇表中只包含了四个视觉单词，分别按索引值标记为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值也越大，一般情况下，K的取值在几百到上千，在这里取K＝4仅仅是为了方便说明。

?2.2.6 倒排表

????????倒排表是一种逆向的查找方式，在BOW中大体的思路是通过已经提取出来的词汇，反向查找出现过这个词汇的文章。

????????假设我们爬取了4个文档，里面的内容如下
????????基于4个文档，写出我们的词库 [我们，今天，运动，昨天，上，课，什么]
????????统计词库中的每个单词出现在哪些文档中，显然我们出现在[doc1,doc2] 中

?这样我们就可以把文档以到排表的方式存储了，这样做有什么优点呢？？？
假如用户输入：我们上课
如果没有倒排表，则只能一篇一篇的去搜索文档中是否既包含我们又包含上课，这样复杂度太高了有了倒排表：我们知道我们[Doc1, Doc2], 上 [ Doc3,Doc4], 课[Doc3,Doc4], 如果有交集，我们可以直接返回交集，如果没有交集，那么直接返回
并集[ Doc1,Doc2, Doc3,Doc4]
?

三、代码实现

3.1 数据集

?

3.2 具体代码

3.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])

运行截图?

?3.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)

运行截图

3.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())

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

3.2.4 建立图像索引进行图像检索?

# -*- 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])  # 重排后的结果

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

3.3 运行截图

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

????????左边第一张为检索的图像！！！！！

? ? ? ? 剩余为检索结果

?维度=10：

?重排结果：

??维度=50：

重排结果：

???维度=100：

重排结果：

????维度=1000：

重排结果：

?????维度=5000：

重排结果：

?3.4 结果分析

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

参考资料：计算机视觉—基于BOW的图像检索_机智的小陈今天学习了吗的博客-CSDN博客_bow图像检索?

BOW 原理及代码解析_曼陀罗彼岸花的博客-CSDN博客_bow特征