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

这篇具有很好参考价值的文章主要介绍了多媒体数据处理实验3：图像特征提取与检索。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

1. 算法描述

功能：

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

2.算法流程：

用SIFT算法提取图像的特征。每幅图像提取出几百至几千个特征点，将所有图像的特征点对应的描述子放在一个矩阵descriptors中，该矩阵的尺寸为695655x128。
对全体特征进行K-Means聚类，然后构造聚类中心（视觉词汇）矩阵voc，该矩阵的尺寸为kx128，其中k为我们指定的聚类数目。在聚类过程中，由于原始特征点数多达仅七十万，因此我采取了每隔10个点进行一次采样的方法加速聚类过程。
遍历所有图像，将各图像中的所有特征点映射到与其欧式距离最近的视觉词汇上，然后根据该图像中各视觉词汇出现的频率构造出图像的直方图向量imhist，将所有图像的直方图向量排列为矩阵，称为imhist。
根据TF-IDF的原理，计算出各视觉词汇的词频TF和逆文本频率指数IDF值以优化直方图向量。设 $N$ 为图像总数， $f_i$ 表示视觉词汇 $i$ 在全体图像中的出现次数，当前图像的直方图向量为 $h_1,h_2,...,h_k)$ ，则当前图像的直方图向量中各视觉词汇的TF和IDF的计算公式如下：
$TF_i=\frac{h_i}{\sum_j{h_j}}, j=1,2,...,k\\ IDF_i=log(\frac{N}{f_i})$
当前图像经过TF-IDF加权优化后的直方图向量为：
$\pmb{h} = h_i(i=1,2,...,k)=\frac{h_i}{\sum_j{h_j}}log(\frac{N}{f_i})(i=1,2,...,k)$
给定一副输入图像，求该图像的直方图向量与所有图像直方图向量之间的余弦相似度，然后降序排列，选择相似度排在前10的图像作为检索输出。余弦相似度的计算公式如下：
$<\pmb{a},\pmb{b}> = \frac{\pmb{a}·\pmb{b}}{|\pmb{a}|·|\pmb{b}|}$

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：
多媒体数据处理实验3：图像特征提取与检索
检索结果：
原始图像500.jpg：
检索结果：
原始图像600.jpg：

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

多媒体数据处理实验3：图像特征提取与检索
各类别的检索准确率统计表如下：

类别	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. 分析与总结

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

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

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

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

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

食物(类9)容易和非洲部落(类1) / 大象(类5) / 马(类7)混淆，因为它们的主色调有点相似。
从实验结果可以发现，随着聚类类别数量的增加（从100到20000），图像检索的结果中错分的图像数量在逐渐变少，即越来越符合人们的视觉常理。但是当类别数量k增加到某一个值的时候，图像检索的效果又开始下降。但是在实际运用kmeans时，k的取值会显著影响聚类算法的运行速度，因此取k=1000是一个比较合适（折衷）的做法。此外，由于kmeans算法每次执行时一开始初始化的聚类中心是随机的，这会对结果造成不确定性的影响，可能某次聚类效果较好，下一次又变差了。
在对所有的特征点进行聚类时，由于原始特征点多达近70万个，若直接对其聚类，则会带来难以接受的时间开销，因此我选择了每隔10个样本采一次样，减小了样本规模，极大地缩短了kmeans的执行时间，且不会对预测准确率造成较大的损失。但当采样率超过20后，预测准确率将会明显下降。
在本次实验中，我尝试自己编写了朴素的kmeans算法，但是后来发现速度特别特别慢，因为进行一轮迭代需要执行上亿次的距离计算。后来我将计算距离+分配聚类中心的过程用scipy.cluster.vq中的vq()函数代替，显著地提高了kmeans算法的执行速度，将所耗时间控制在可以接受的范围内。这说明作者封装好的kmeans包实际上蕴含了一些tricks，能够极大地提升算法的执行效率。
我尝试了使用TF-IDF的思想去优化图像直方图向量的表示，但发现预测准确率不升反降，后来还是采用了原始的求解方法。
在本次实验中，我采用的相似度度量方法是余弦相似度。一开始的时候我也尝试了欧氏距离，但是发现效果相比使用余弦相似度而言下降了很多。
BOF算法在处理局部特征向视觉词汇的映射时，只是将一个局部特征映射到与其相似度最高的那个词汇上，但有时图像的局部特征可能同时与多个视觉词汇的相似度都非常高，这么做会丢失一些信息。