Bag-of-Visual Word视觉词袋

简介

继特征提取的第二个步骤,检索结构。

综合转载以下文章:

Bag of words模型最初被用在文本分类中,将文档表示成特征矢量。它的基本思想是假定对于一个文本,忽略其词序和语法、句法,仅仅将其看做是一些词汇的集合,而文本中的每个词汇都是独立的。简单说就是讲每篇文档都看成一个袋子(因为里面装的都是词汇,所以称为词袋,Bag of words即因此而来)。

同样地,BoVW模型的假设也是特征之间独立。

步骤

预处理

假设训练集有$M$幅图像,对训练图象集进行预处理。包括图像增强,分割,图像统一格式,统一规格等等。

提取SIFT特征

对每一幅图像提取SIFT特征(每一幅图像提取多少个SIFT特征不定)。每一个SIFT特征用一个128维的描述子矢量表示,假设M幅图像共提取出N个SIFT特征。

K-means聚类

用K-means对2中提取的$N$个SIFT特征进行聚类,K-Means算法是一种基于样本间相似性度量的间接聚类方法,此算法以$K$为参数,把$N$个对象分为$K$个簇,以使簇内具有较高的相似度,而簇间相似度较低。聚类中心有$K$个(在BOW模型中聚类中心我们称它们为视觉词),码本的长度也就为$K$,计算每一幅图像的每一个SIFT特征到这$K$个视觉词的距离,并将其映射到距离最近的视觉词中(即将该视觉词的对应词频+1)。完成这一步后,每一幅图像就变成了一个与视觉词序列相对应的词频矢量。

构造码本

码本矢量归一化因为每一幅图像的SIFT特征个数不定,所以需要归一化。如上述例子,归一化后为$[1,0,0]$,$\frac{1}{12} \times [5,3,4]$。测试图像也需经过预处理,提取SIFT特征,将这些特征映射到为码本矢量,码本矢量归一化,最后计算其与训练码本的距离,对应最近距离的训练图像认为与测试图像匹配。

预测

一张测试图像,经过预处理,之后经过码本,生成词频矢量,归一化,寻找与它最近的训练样本所代表的类别即为预测类别,一种相似性衡量方法就是余弦距离:

因为之前已经经过归一化,所以这里相当于两个向量进行内积。

也可以寻找最近的$k$个训练样本,投票得到预测类别。

以上是检索的方法。

如果是识别问题的话,可以把码本向量当成图像集更加高维的特征,维数更少,识别可以更加快速。

倒排

实际使用时,码本的词汇数量大约是数十万至数百万,所以造成最后每张图片得到的词频向量是稀疏的,这时使用倒排索引会加快很多。

缺点

由于量化,引入了两种类型的误差,

  1. 可能有两个特征$x$和$y$应该被匹配,但是已经被量化为不同的视觉单词。 这是匹配错误的来源;
  2. 不应该匹配两个特征$x$和$y$的情况下,它们已被量化为相同的视觉单词,从而发生错误匹配。

对于第一类错误,将一个特征量化为多个视觉单词可以缓解该问题。 对于第二类错误,已经提出了视觉验证和几何验证来解决。

代码

代码是在github上找到的一个demo,简介中已经引用。

原代码具有高度模块化的优点,很值得学习,我这里只是自己想对整个过程有个了解,自己简单地跟着做了一下。

1. 引入需要的包

1
2
3
4
5
6
7
import os
import cv2
import numpy as np
from sklearn.svm import SVC
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from matplotlib import pyplot as plt

2. 定义需要的参数

1
2
3
train_path = './images/train/'
test_path = './images/test/'
n_clusters = 5

3. 定义读取图片的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
def imageloader(path):
imlist = {}
count = 0
for each in os.listdir(path):
word = each.split("/")[-1]
print(" #### Reading image category ", word, " ##### ")
imlist[word] = []
for imagefile in os.listdir(path+word):
print("Reading file ", path+word+'/'+imagefile)
im = cv2.imread(path+word+'/'+imagefile, 0)
imlist[word].append(im)
count += 1
return imlist, count

4. 读取训练集图像

1
trainImages, trainImageCount = imageloader(train_path)

5. 提取SIFT特征

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
name_dict = {}
label_count = 0
descriptor_list = []
trainLabels = np.array([])
sift_object = cv2.xfeatures2d.SIFT_create()
for word, imlist in trainImages.items():
name_dict[str(label_count)] = word
print("computing Features for ", word)
for image in imlist:
trainLabels = np.append(trainLabels, label_count)
kp, des = sift_object.detectAndCompute(image, None)
descriptor_list.append(des)
label_count += 1

descriptor_vstack = np.array(descriptor_list[0])
for remaining in descriptor_list[1:]:
descriptor_vstack = np.vstack((descriptor_vstack, remaining))

6. 对特征进行聚类

1
2
kmeans_obj = KMeans(n_clusters = n_clusters)
kmeans_ret = kmeans_obj.fit_predict(descriptor_vstack)

7. 构建直方图

1
2
3
4
5
6
mega_histogram = np.array([np.zeros(n_clusters) for i in range(trainImageCount)])
for i in range(trainImageCount):
l = len(descriptor_list[i])
for j in range(l):
idx = kmeans_ret[i+j]
mega_histogram[i][idx] += 1
1
2
3
4
5
6
7
8
9
10
11
12
mega_histogram
x_scalar = np.arange(n_clusters)
y_scalar = np.array([abs(np.sum(mega_histogram[:,h], dtype=np.int32)) for h in range(n_clusters)])

print(y_scalar)

plt.bar(x_scalar, y_scalar)
plt.xlabel("Visual Word Index")
plt.ylabel("Frequency")
plt.title("Complete Vocabulary Generated")
plt.xticks(x_scalar + 0.4, x_scalar)
plt.show()

8. 标准化

1
2
scale = StandardScaler().fit(mega_histogram)
mega_histogram = scale.transform(mega_histogram)

9. 用SVM训练模型

1
2
3
4
5
clf = SVC()
print("Training SVM")
print("Train labels", trainLabels)
clf.fit(mega_histogram, trainLabels)
print("Training completed")

10. 读取测试图像,得到码本向量,标准化,进行预测

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
testImages, testImageCount = imageloader(test_path)
predictions = []
for word, imlist in testImages.items():
print("processing ", word)
for image in imlist:
kp, des = sift_object.detectAndCompute(image, None)
vocab = np.array([[0 for i in range(n_clusters)]])
test_ret = kmeans_obj.predict(des)
for each in test_ret:
vocab[0][each] += 1
vocab = scale.transform(vocab)
lb = clf.predict(vocab)
print(lb)
predictions.append({
'image':image,
'class':lb,
'object_name':name_dict[str(int(lb[0]))]
})
for each in predictions:
plt.imshow(cv2.cvtColor(each['image'], cv2.COLOR_GRAY2RGB))
plt.title(each['object_name'])
plt.show()

可以看到总共八张图像,正确率有75%,这个是我通过调整聚类个数得到的最佳结果,原本作者使用的是20个聚类个数。另外,SVM分类器的参数没有调整。

一分一毛,也是心意。