Memo
0%

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
47
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 组合到一起进行比较相似度，但是，这种方法又损失和旋转不变性和平移不变性。