BoVW 图像检索

BoVW (Bag of Visual Word) 是在传统图像检索领域里比较常用的一种方法. 大体可以分为三个步骤: 特征提取, 聚类(类似于寻找一组基), 计算图片在基上的坐标. 算法的创新点是对图片的特征寻找基. 这样, 在基固定的情况下, 所有的图片都可以使用这组基来唯一的表示. 而且, 由于基的维数是固定的, 也为相似度计算提供了极大的方便. 根据检索图片的不同, 可以选用不同的特征提取方法.

特征提取

根据检索图片的特点, 可以选用不同的特征提取方法, 最终, 图像中的特征要映射到一组基上面.

聚类

聚类的目的是为了给图片的特征寻找一组合适的基(大部分时候论文中叫做簇, 为了方便理解, 这里仍然使用基这个名词). 聚类的中心点的个数需要自定义. 一般情况, 聚类中心的数量要大于一张图片中的特征的数量. 假设一张图片中特征的数量是 \(n\), 我比较喜欢选择的聚类中心的数量是 \(kn^2\). 这样做的目的是为了图片特征表达的稀疏性. 为了理解这一点, 假设选择的聚类中心个数为\(2\), 那么, 每张图片中提取的特征的数量是\(100\), 那么, 这种情况下, 所有不同的坐标个数是 \(101\), 也就是说, 最理想的情况下, 这种方法能够检索的图像的数量是\(101\)张. 如果聚类中心数量为\(1000\), 好吧, 我暂时没有计算出来具体数字.o(╯□╰)o 反正是一个好大好大的数字.
由于从 train set 中提取的特征的数量特别多(比如, 每张图片1000个特征, 10000张图片的话就是1kw的特征), 如果直接聚类的话(聚类中心为 \(10^3\) 量级), 由于 sample 的数量特别多, 聚类时长无法接受, 常用的做法是先进行抽样, 然后用抽样得到的样本进行聚类. 抽样又有两种方法, 一种是对原始图片进行抽样, 然后对样本图片提取特征, 聚类. 另外一种做法是对全部图片的特征进行抽样, 然后对抽样特征进行聚类.

计算坐标

通过聚类, 我们得到了一个模型, 假设该,模型的聚类中心的数量是 \(\cal N\), 并且赋予聚类中心顺序, 那么, 使用该聚类模型对 train set 中的每一张图片的特征进行预测, 得到这张图片每一个特征所在的聚类中心\(P\), 计算\(P\) 的 histogram, 就的到了相应的 \(\cal N\) 维的特征. 如果每一张图片提取的特征的数量不同(例如 SIFT 特征)(即使相同, 也推荐做一下归一化), 那么, 还需要对 histogram 做一个归一化操作. 这样, 就可以得到每一张图片一个 \(\cal N\) 维的 code.

检索

对一张图片, 计算其code, 然后和train set 中的图片的 code 比较距离. 距离越近越相似, 说明图片越相似.

训练代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import cv2
import numpy as np
def extract_sift(mats):
sifts = []
for mat in mats:
_, sift = cv2.xfeatures2d.SIFT_create(nfeatures=500).detectAndCompute(
mat, None)
sifts.append(sift)
return sifts
def train_kmeans(sifts):
# put all sit description to on numpy.array
code_dim = 0
for sift in sifts:
if sift is not None:
code_dim += 1
codes = np.empty((code_dim, 128))
cur_row = 0
for sift in sifts:
if sift is None:
continue
codes[cur_row:cur_row + sift.shape[0], :] = sift
cur_row += sift.shape[0]
kmean_model = MiniBatchKMeans(
n_clusters=500,
max_iter=10000,
batch_size=100, )
kmean_model.fit(codes)
return kmean_model
def compute_codebook(sifts, kmeans_model):
n_clusters = kmeans_model.get_params()['n_clusters']
codebook = np.empty((len(sifts), n_clusters))
bins = range(1 + kmeans_model.get_params()['n_clusters'])
for idx, sift in enumerate(sifts):
if sift is not None:
hist, _ = np.histogram(
kmeans_model.predict(sift), bins=bins, density=True)
codebook[idx] = hist
else:
codebook[idx] = np.zeros(n_clusters) + np.NaN
return codebook

思考

由于对特征进行聚类之后计算 histogram, 把 histogram 的结果用来计算相似度, 所以, 这就损失了原始特征在图片中的位置信息. 一种比较直观的方法是对图片先进行分块, 对每一块计算其code, 然后把所有快的code组合到一起进行比较相似度, 但是, 这种方法又损失和旋转不变性和平移不变性.