多媒体数据处理实验3：图像特征提取与检索

第3次实验： 图像特征提取与检索

1. 算法描述

功能：

  使用BOF(Bag of Features)算法提取图像特征，在corel数据集(10*100)张图片上实现以图搜图，即输入数据集中某一张图，在剩下的999张图里搜索最邻近的10张图。

2.算法流程：

1. 用SIFT算法提取图像的特征。每幅图像提取出几百至几千个特征点，将所有图像的特征点对应的描述子放在一个矩阵descriptors中，该矩阵的尺寸为695655x128。

2. 对全体特征进行K-Means聚类，然后构造聚类中心（视觉词汇）矩阵voc，该矩阵的尺寸为kx128，其中k为我们指定的聚类数目。在聚类过程中，由于原始特征点数多达仅七十万，因此我采取了每隔10个点进行一次采样的方法加速聚类过程。

3. 遍历所有图像，将各图像中的所有特征点映射到与其欧式距离最近的视觉词汇上，然后根据该图像中各视觉词汇出现的频率构造出图像的直方图向量imhist，将所有图像的直方图向量排列为矩阵，称为imhist。

4. 根据TF-IDF的原理，计算出各视觉词汇的词频TF和逆文本频率指数IDF值以优化直方图向量。设$N$为图像总数，$f_i$表示视觉词汇$i$在全体图像中的出现次数，当前图像的直方图向量为$(h_1,h_2,...,h_k)$，则当前图像的直方图向量中各视觉词汇的TF和IDF的计算公式如下：
   $$\begin{gathered} T{F}_i=\frac{h_i}{{\sum }_j{h}_j},j=1,2,...,k \\ ID{F}_i=log(\frac{N}{f_i}) \end{gathered}$$
   当前图像经过TF-IDF加权优化后的直方图向量为：
   $$hh=h_i(i=1,2,...,k)=\frac{h_i}{{\sum }_j{h}_j}log(\frac{N}{f_i})(i=1,2,...,k)$$

5. 给定一副输入图像，求该图像的直方图向量与所有图像直方图向量之间的余弦相似度，然后降序排列，选择相似度排在前10的图像作为检索输出。余弦相似度的计算公式如下：
   $$<aa,bb>=\frac{aa\cdot bb}{|aa|\cdot |bb|}$$

3. 核心代码

# 用SIFT算法提取特征的128维描述子向量
def SIFT(img):
    I = cv2.imread(img)
    descriptor = cv2.xfeatures2d.SIFT_create()
    (kps, features) = descriptor.detectAndCompute(I, None)
    return features
    
# 自编kmeans算法
# 计算新的聚类中心
def calcNewCentroids(cls_pos):
    Centroids_new = np.zeros((1, 128))
    for Centroid in cls_pos.keys():
        # 初始化新聚类中心坐标为128维0向量
        pos_new = np.zeros((1, 128))
        for pos in cls_pos[Centroid]:
            pos_new += pos
        # 以各类中所有点的坐标的均值作为新的聚类中心点坐标
        pos_new /= len(cls_pos[Centroid])
        # 将新中心坐标添加到列表中
        Centroids_new = np.row_stack((Centroids_new, pos_new))
    return Centroids_new[1:,:]

def kmeans(X, k):
    n = X.shape[0]   # 数据点总数
    epoch = 0        # 迭代次数
    idxs = [random.randint(0,k) for _ in range(k)]
    Centroids = X[idxs] # 构造初始的中心点矩阵（1000x128）
    while(1):
        epoch += 1
        cls_pos = {
    }
        # 对于每个点，计算它到各中心的距离，得到它所属的类
        cls, _ = vq(X, Centroids)
        for i in range(n):
            cls_pos.setdefault(cls[i],[]).append(X[i])
        for j in range(k):
            if j not in cls_pos.keys():
                cls_pos.setdefault(j,[]).append(Centroids[j])
        # 所有点均已分到相应的类中。下求新的聚类中心坐标
        Centroids_new = calcNewCentroids(cls_pos)
        # 当聚类中心不再变化时，停止迭代
        if (Centroids_new == Centroids).all():
            break
        # 更新聚类中心为新的聚类中心
        Centroids = Centroids_new
    # 返回聚类中心坐标及迭代次数
    return epoch, Centroids

# 求单幅图像的直方图向量
def project(descriptors, words_num, voc):
    imhist = np.zeros(words_num)
    cls, _ = vq(descriptors, voc)
    for c in cls:
        imhist[c] += 1
    return imhist

# 用TF-IDF的思想加权优化直方图向量
occurence_num = sum((imhists > 0) * 1)
IDF = np.log((image_nums) / (occurence_num + 1))
for i in range(image_nums):
    imhists[i] = imhists[i] / sum(imhists[i]) * IDF

4. 实验结果

设置聚类数目k=1000，对若干图像进行图像检索，效果如下：

原始图像320.jpg：

检索结果：
原始图像500.jpg：
检索结果：
原始图像600.jpg：

检索结果：
原始图像720.jpg：
检索结果：

各类别的检索准确率统计表如下：

类别	0	1	2	3	4	5	6	7	8	9
检索准确率	56.5%	8.6%	43.9%	76.5%	87.7%	55.5%	29.4%	65.9%	14.5%	20.9%

5. 分析与总结

1. 本次实验的结果呈现出以下特点：

   0、2、3、4、5、7 这几类准确率较高；

   海滩(类1)图片容易和大象(类5) / 马(类7)混淆；

   花朵(类6)一旦背景有绿叶，容易和其他类别中背景有大片绿色的图像混淆；

   山峰 / 雪山(类8)容易和其他类别混淆；

   食物(类9)容易和非洲部落(类1) / 大象(类5) / 马(类7)混淆，因为它们的主色调有点相似。

2. 从实验结果可以发现，随着聚类类别数量的增加（从100到20000），图像检索的结果中错分的图像数量在逐渐变少，即越来越符合人们的视觉常理。但是当类别数量k增加到某一个值的时候，图像检索的效果又开始下降。但是在实际运用kmeans时，k的取值会显著影响聚类算法的运行速度，因此取k=1000是一个比较合适（折衷）的做法。此外，由于kmeans算法每次执行时一开始初始化的聚类中心是随机的，这会对结果造成不确定性的影响，可能某次聚类效果较好，下一次又变差了。

3. 在对所有的特征点进行聚类时，由于原始特征点多达近70万个，若直接对其聚类，则会带来难以接受的时间开销，因此我选择了每隔10个样本采一次样，减小了样本规模，极大地缩短了kmeans的执行时间，且不会对预测准确率造成较大的损失。但当采样率超过20后，预测准确率将会明显下降。

4. 在本次实验中，我尝试自己编写了朴素的kmeans算法，但是后来发现速度特别特别慢，因为进行一轮迭代需要执行上亿次的距离计算。后来我将计算距离+分配聚类中心的过程用scipy.cluster.vq中的vq()函数代替，显著地提高了kmeans算法的执行速度，将所耗时间控制在可以接受的范围内。这说明作者封装好的kmeans包实际上蕴含了一些tricks，能够极大地提升算法的执行效率。

5. 我尝试了使用TF-IDF的思想去优化图像直方图向量的表示，但发现预测准确率不升反降，后来还是采用了原始的求解方法。

6. 在本次实验中，我采用的相似度度量方法是余弦相似度。一开始的时候我也尝试了欧氏距离，但是发现效果相比使用余弦相似度而言下降了很多。

7. BOF算法在处理局部特征向视觉词汇的映射时，只是将一个局部特征映射到与其相似度最高的那个词汇上，但有时图像的局部特征可能同时与多个视觉词汇的相似度都非常高，这么做会丢失一些信息。