1. BOW算法简介

Bag-of-Words模型源于文本分类技术。在信息检索中，它假定对于一个文本，忽略其词序、语法和句法，将其仅仅看作是一个词集合，或者说是词的一个组合。文本中每个词的出现都是独立的，不依赖于其他词是否出现，或者说这篇文章的作者在任意一个位置选择词汇都不受前面句子的影响而独立选择的。

Bag-of-words在CV中的应用首先出现在Andrew Zisserman中为解决对视频场景的搜索，其提出了使用Bag-of-words关键点投影的方法来表示图像信息。后续更多的研究者归结此方法为Bag-of-Features，并用于图像分类、目标识别和图像检索。Bag-of-Features模型仿照文本检索领域的Bag-of-Words方法，把每幅图像描述为一个局部区域或关键点(Patches/Key Points)特征的无序集合，这些特征点可以看成一个词。这样，就能够把文本检索及分类的方法用到图像分类及检索中去。

使用某种聚类算法(如K-means)将特征进行聚类，每个聚类中心被看作是词典中的一个视觉词汇(Visual Word)，相当于文本检索中的词，视觉词汇由聚类中心对应特征形成的码字(code word)来表示（可看当为一种特征量化过程）。所有视觉词汇形成一个视觉词典(Visual Vocabulary)，对应一个码书(code book)，即码字的集合，词典中所含词的个数反映了词典的大小。图像中的每个特征都将被映射到视觉词典的某个词上，这种映射可以通过计算特征间的距离去实现。然后，统计每个视觉词的出现与否或次数，图像可描述为一个维数相同的直方图向量，即Bag-of-Features。在Bag-of-Features方法的基础上，Andrew Zisserman进一步借鉴文本检索中TF-IDF模型(Term Frequency一Inverse Document Frequency)来计算Bag-of-Features特征向量。接下来便可以使用文本搜索引擎中的反向索引技术对图像建立索引，高效的进行图像检索。

Bag-of-Features更多地是用于图像分类或对象识别。在上述思路下对训练集提取Bag-of-Features特征，在某种监督学习（如:SVM）的策略下，对训练集的Bag-of-Features特征向量进行训练，获得对象或场景的分类模型；对于待测图像，提取局部特征，计算局部特征与词典中每个码字的特征距离，选取最近距离的码字代表该特征，建立一个统计直方图，统计属于每个码字的特征个数，即为待测图像的Bag-of-Features特征；在分类模型下，对该特征进行预测，从而实现对待测图像的分类。

2. BOW算法实现步骤

使用词袋模型进行图像检索。

2.0 图像预处理

图像预处理包括很多，在此就不介绍了，因为我没进行。
局部特征提取：通过分割、密集或随机采集、关键点或稳定区域、显著区域等方式使图像形成不同的patches，并获得各patches处的特征。

2.1 提取图像特征

鉴于SIFT的优异性能，本文提取的是SIFT特征。关于SIFT的具体介绍可以百度查询相关资料，后续我也会写文章具体介绍。在本文中只需要会调用相应的库函数即可，OpenCV库实现了SIFT特征的提取。

2.2 构建视觉词典

将所有图像的所有SIFT特征点放在一起，进行聚类，得出的聚类中心便是视觉词汇。所有视觉词汇的集合便是视觉词典。聚类中心的大小可以设置，本文采用的是K-Means聚类算法。

2.3 统计数据，生成码书

生成码书，即构造Bag-of-Features特征。计算每幅图像有哪些视觉词，统计出词频矩阵

2.4 引入TF-IDF权值

计算TF值和IDF值，进而得到TF-IDF矩阵，并对其进行L2归一化（向量中每个元素除以向量的L2范数->x/平方和开根号）。

2.5 对查询图像生成同样的带权BOF特征

重复上述步骤，对查询图像生成同样的带权BOF特征。

2.6 比较带权BOF特征

本文使用汉明距离，比较查询图像与数据库里的图像。

3.实现代码

#python findFeatures.py -t dataset/train/

import argparse as ap
import cv2
import numpy as np
import os
from sklearn.externals import joblib
from scipy.cluster.vq import *
import scipy
import scipy.cluster.hierarchy as sch
from scipy.cluster.vq import vq,kmeans,whiten
from sklearn import preprocessing
#from rootsift import RootSIFT
import math

def getInverseTable1(train_path, wordsNum):
    path = "E:\\"
    txtPath = "E:\\"
    count = 0
    f = open(txtPath, "w")
    for file in os.listdir(path):
        count = count + 1
        # ff='/'+filename+"/"+file+" "+filename+"\n"
        ff = file + " " + "\n"
        f.write(ff)
        print('{} class: {}'.format(file, count))
    f.close()

    # Get the training classes names and store them in a list
    # train_path = args["trainingSet"]
    # train_path = "dataset/train/"
    train_path = "E:\\"
    training_names = os.listdir(train_path)

    numWords = wordsNum
    # Get all the path to the images and save them in a list
    # image_paths and the corresponding label in image_paths
    image_paths = []
    for training_name in training_names:
        image_path = os.path.join(train_path, training_name)
        image_paths += [image_path]

    # Create feature extraction and keypoint detector objects
    # fea_det = cv2.FeatureDetector_create("SIFT")
    # des_ext = cv2.DescriptorExtractor_create("SIFT")
    surf = cv2.xfeatures2d.SURF_create()
    sift = cv2.xfeatures2d.SIFT_create()
    # sift = cv2.SIFT()
    # List where all the descriptors are stored
    des_list = []
    count = 0
    for i, image_path in enumerate(image_paths):
        # if count<3:
        count = count + 1
        img = cv2.imread(image_path)
        print("Extract SIFT of %s image, %d of %d images" % (training_names[i], i, len(image_paths)))
        # kpts = fea_det.detect(img)
        # kpts, des = des_ext.compute(img, kpts)
        kpts, des = sift.detectAndCompute(img, None)
        # rootsift
        # rs = RootSIFT()
        # des = rs.compute(kpts, des)
        des_list.append((image_path, des))

    # Stack all the descriptors vertically in a numpy array
    # downsampling = 1
    # descriptors = des_list[0][1][::downsampling,:]
    # for image_path, descriptor in des_list[1:]:
    #    descriptors = np.vstack((descriptors, descriptor[::downsampling,:]))

    # Stack all the descriptors vertically in a numpy array
    descriptors = des_list[0][1]
    for image_path, descriptor in des_list[1:]:
        descriptors = np.vstack((descriptors, descriptor))

    # Perform k-means clustering
    print("Start k-means: %d words, %d key points,%d points dimension" % (
    numWords, descriptors.shape[0], descriptors.shape[1]))
    data = whiten(descriptors)
    # print ("data  by whiten:\n",data)
    # centroid=kmeans(data,numWords)[0]
    # print ("centroid by k-means:\n",centroid)
    voc, variance = kmeans(descriptors, numWords, 1)
    print("损失大小：",variance)
    print("start k-means:\n")


    # Calculate the histogram of features
    print("开始计算TF-IDF:\n")
    im_features = np.zeros((len(image_paths), numWords), "float32")

    for i in range(len(image_paths)):
        words, distance = vq(des_list[i][1], voc)
        print("开始计算words:\n", words, words.size)
        for w in words:
            # print("开始输出w:\n", w)
            im_features[i][w] += 1
        '''

        '''
    # Perform Tf-Idf vectorization
    print("-----正在计算TF-IDF:\n")
    np.savetxt("im_features0.txt", im_features)
    tf = np.zeros((len(image_paths), numWords), "float32")

    nbr_occurences = np.sum((im_features > 0) * 1, axis=0)
    idf = np.array(np.log((1.0 * len(image_paths) + 1) / (1.0 * nbr_occurences + 1)), 'float32')
    # print ("-----TF-IDF:\n",nbr_occurences,idf)
    # Perform L2 normalization
    # im_features = im_features*idf*tf
    im_features = im_features * idf
    for i in range(len(image_paths)):
        tf[i] = im_features[i] / (np.sum(im_features, axis=1).reshape(60, 1)[i])
        #print("tf[i]:",tf[i])
        im_features[i] = im_features [i]* tf[i]
    inverse_table = im_features.T
    np.savetxt("inverse_table.txt", inverse_table)
    np.savetxt("im_features.txt", im_features)
    print("-----输出inverse_table.txt:\n")
    im_features = preprocessing.normalize(im_features, norm='l2')

    joblib.dump((im_features, image_paths, idf, numWords, voc), "bof.pkl", compress=3)
def searchImage(searchImagePath,wordsNum,flag):
    if flag==1:
        im_features, image_paths, idf, numWords, centers = joblib.load("bof.pkl")
    if flag==2:
        im_features, image_paths, idf, numWords, voc=joblib.load("bof.pkl")
        centers = voc
    img = cv2.imread(searchImagePath)
    #print("Extract SIFT of %s image" % (searchImagePath))
    surf =  cv2.xfeatures2d.SURF_create()
    sift = cv2.xfeatures2d.SIFT_create()
    # kpts = fea_det.detect(img)
    # kpts, des = des_ext.compute(img, kpts)
    kpts, des = sift.detectAndCompute(img, None)
    words, distance = vq(des, centers)
    #print("开始计算words:\n", words, words.size)
    im_features_search = np.zeros((wordsNum), "float32")
    for w in words:
        # print("开始输出w:\n", w)
        im_features_search[w] += 1
    inverseTable = np.loadtxt("inverse_table.txt")

    tf = im_features_search / (np.sum(im_features_search))
    #print("tf:", tf)
    im_features_search = im_features_search*tf
    im_features_search = im_features_search.reshape(1, wordsNum) * idf
    im_features_search = preprocessing.normalize(im_features_search, norm='l2')
    temp = np.dot(im_features_search,inverseTable)
    #print("开始求和:\n",temp)
    rank = np.argsort(-temp)
    #print("开始输出rank:\n", rank)
    return rank

if __name__ == '__main__':
    print("-----开始匹配:\n")
    trainImagePath ="E:\\"
    searchImagePath="E:\\"
    wordsNum = 1000   #聚类中心的数目
    getInverseTable1(trainImagePath,wordsNum)                
    rank = searchImage(searchImagePath ,wordsNum,2)
     

4. 结果分析

运行程序，分析结果。当测试集为60张图片时，top5的正确率只有40%左右。
分析如下：
1、使用k-means聚类，除了其K和初始聚类中心选择的问题外，对于海量数据，输入矩阵的巨大将使得内存溢出及效率低下。有方法是在海量图片中抽取部分训练集分类，使用朴素贝叶斯分类的方法对图库中其余图片进行自动分类。另外，由于图片爬虫在不断更新后台图像集，重新聚类的代价显而易见。
2、字典大小的选择也是问题，字典过大，单词缺乏一般性，对噪声敏感，计算量大，关键是图象投影后的维数高；字典太小，单词区分性能差，对相似的目标特征无法表示。
3、相似性测度函数用来将图象特征分类到单词本的对应单词上，其涉及线型核，塌方距离测度核，直方图交叉核等的选择。
4、将图像表示成一个无序局部特征集的特征包方法，丢掉了所有的关于空间特征布局的信息，在描述性上具有一定的有限性。为此， Schmid提出了基于空间金字塔的Bag-of-Features。
5、Jégou提出VLAD(vector of locally aggregated descriptors)，其方法是如同BOF先建立出含有k个visual word的codebook，而不同于BOF将一个local descriptor用NN分类到最近的visual word中，VLAD所采用的是计算出local descriptor和每个visual word在每个分量上的差距，将每个分量的差距形成一个新的向量来代表图片。

参考资料

[1] BOW 原理及代码解析
[2] BoW（词袋）模型详细介绍
[3] BoW算法及DBoW2库简介
[4] Bag of Features (BOF)图像检索算法
[5] BOW模型理解
[6] 图像检索中BOW和LSH的一点理解
[7] 使用词袋模型对图像进行分类
[8] Bag of Features (BOF)图像检索算法
[9] SIFT+BOW 实现图像检索
[10] 基于词袋模型的图像检索与分类系统的设计与实现
[11] BoW(词袋模型)+python代码实现