1. BOW算法簡介

Bag-of-Words模型源于文本分類技術(shù)。在信息檢索中捣辆，它假定對于一個(gè)文本蔬螟，忽略其詞序、語法和句法汽畴，將其僅僅看作是一個(gè)詞集合旧巾，或者說是詞的一個(gè)組合。文本中每個(gè)詞的出現(xiàn)都是獨(dú)立的忍些，不依賴于其他詞是否出現(xiàn)鲁猩，或者說這篇文章的作者在任意一個(gè)位置選擇詞匯都不受前面句子的影響而獨(dú)立選擇的。

Bag-of-words在CV中的應(yīng)用首先出現(xiàn)在Andrew Zisserman中為解決對視頻場景的搜索罢坝，其提出了使用Bag-of-words關(guān)鍵點(diǎn)投影的方法來表示圖像信息廓握。后續(xù)更多的研究者歸結(jié)此方法為Bag-of-Features，并用于圖像分類嘁酿、目標(biāo)識別和圖像檢索隙券。Bag-of-Features模型仿照文本檢索領(lǐng)域的Bag-of-Words方法，把每幅圖像描述為一個(gè)局部區(qū)域或關(guān)鍵點(diǎn)(Patches/Key Points)特征的無序集合闹司，這些特征點(diǎn)可以看成一個(gè)詞娱仔。這樣，就能夠把文本檢索及分類的方法用到圖像分類及檢索中去游桩。

使用某種聚類算法(如K-means)將特征進(jìn)行聚類牲迫，每個(gè)聚類中心被看作是詞典中的一個(gè)視覺詞匯(Visual Word)，相當(dāng)于文本檢索中的詞众弓，視覺詞匯由聚類中心對應(yīng)特征形成的碼字(code word)來表示（可看當(dāng)為一種特征量化過程）恩溅。所有視覺詞匯形成一個(gè)視覺詞典(Visual Vocabulary)，對應(yīng)一個(gè)碼書(code book)谓娃，即碼字的集合脚乡，詞典中所含詞的個(gè)數(shù)反映了詞典的大小。圖像中的每個(gè)特征都將被映射到視覺詞典的某個(gè)詞上滨达，這種映射可以通過計(jì)算特征間的距離去實(shí)現(xiàn)奶稠。然后，統(tǒng)計(jì)每個(gè)視覺詞的出現(xiàn)與否或次數(shù)捡遍，圖像可描述為一個(gè)維數(shù)相同的直方圖向量锌订，即Bag-of-Features。在Bag-of-Features方法的基礎(chǔ)上画株，Andrew Zisserman進(jìn)一步借鑒文本檢索中TF-IDF模型(Term Frequency一Inverse Document Frequency)來計(jì)算Bag-of-Features特征向量辆飘。接下來便可以使用文本搜索引擎中的反向索引技術(shù)對圖像建立索引啦辐，高效的進(jìn)行圖像檢索。

Bag-of-Features更多地是用于圖像分類或?qū)ο笞R別蜈项。在上述思路下對訓(xùn)練集提取Bag-of-Features特征芹关，在某種監(jiān)督學(xué)習(xí)（如:SVM）的策略下，對訓(xùn)練集的Bag-of-Features特征向量進(jìn)行訓(xùn)練紧卒，獲得對象或場景的分類模型侥衬；對于待測圖像，提取局部特征跑芳，計(jì)算局部特征與詞典中每個(gè)碼字的特征距離轴总，選取最近距離的碼字代表該特征，建立一個(gè)統(tǒng)計(jì)直方圖博个，統(tǒng)計(jì)屬于每個(gè)碼字的特征個(gè)數(shù)怀樟，即為待測圖像的Bag-of-Features特征；在分類模型下坡倔，對該特征進(jìn)行預(yù)測漂佩，從而實(shí)現(xiàn)對待測圖像的分類。

2. BOW算法實(shí)現(xiàn)步驟

使用詞袋模型進(jìn)行圖像檢索罪塔。

2.0 圖像預(yù)處理

圖像預(yù)處理包括很多，在此就不介紹了养葵，因?yàn)槲覜]進(jìn)行征堪。
局部特征提取：通過分割关拒、密集或隨機(jī)采集佃蚜、關(guān)鍵點(diǎn)或穩(wěn)定區(qū)域、顯著區(qū)域等方式使圖像形成不同的patches着绊，并獲得各patches處的特征谐算。

2.1 提取圖像特征

鑒于SIFT的優(yōu)異性能，本文提取的是SIFT特征归露。關(guān)于SIFT的具體介紹可以百度查詢相關(guān)資料洲脂，后續(xù)我也會(huì)寫文章具體介紹。在本文中只需要會(huì)調(diào)用相應(yīng)的庫函數(shù)即可剧包，OpenCV庫實(shí)現(xiàn)了SIFT特征的提取恐锦。

2.2 構(gòu)建視覺詞典

將所有圖像的所有SIFT特征點(diǎn)放在一起，進(jìn)行聚類疆液，得出的聚類中心便是視覺詞匯一铅。所有視覺詞匯的集合便是視覺詞典。聚類中心的大小可以設(shè)置堕油，本文采用的是K-Means聚類算法潘飘。

2.3 統(tǒng)計(jì)數(shù)據(jù)肮之，生成碼書

生成碼書，即構(gòu)造Bag-of-Features特征卜录。計(jì)算每幅圖像有哪些視覺詞戈擒，統(tǒng)計(jì)出詞頻矩陣

2.4 引入TF-IDF權(quán)值

計(jì)算TF值和IDF值，進(jìn)而得到TF-IDF矩陣暴凑，并對其進(jìn)行L2歸一化（向量中每個(gè)元素除以向量的L2范數(shù)->x/平方和開根號）峦甩。

2.5 對查詢圖像生成同樣的帶權(quán)BOF特征

重復(fù)上述步驟，對查詢圖像生成同樣的帶權(quán)BOF特征现喳。

2.6 比較帶權(quán)BOF特征

本文使用漢明距離凯傲，比較查詢圖像與數(shù)據(jù)庫里的圖像。

3.實(shí)現(xiàn)代碼

#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("開始計(jì)算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("開始計(jì)算words:\n", words, words.size)
        for w in words:
            # print("開始輸出w:\n", w)
            im_features[i][w] += 1
        '''

        '''
    # Perform Tf-Idf vectorization
    print("-----正在計(jì)算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("開始計(jì)算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   #聚類中心的數(shù)目
    getInverseTable1(trainImagePath,wordsNum)                
    rank = searchImage(searchImagePath ,wordsNum,2)
     

4. 結(jié)果分析

運(yùn)行程序冰单，分析結(jié)果。當(dāng)測試集為60張圖片時(shí)灸促，top5的正確率只有40%左右诫欠。
分析如下：
1、使用k-means聚類浴栽，除了其K和初始聚類中心選擇的問題外荒叼，對于海量數(shù)據(jù)，輸入矩陣的巨大將使得內(nèi)存溢出及效率低下典鸡。有方法是在海量圖片中抽取部分訓(xùn)練集分類被廓，使用樸素貝葉斯分類的方法對圖庫中其余圖片進(jìn)行自動(dòng)分類。另外萝玷，由于圖片爬蟲在不斷更新后臺圖像集嫁乘，重新聚類的代價(jià)顯而易見。
2球碉、字典大小的選擇也是問題蜓斧，字典過大，單詞缺乏一般性睁冬，對噪聲敏感挎春，計(jì)算量大，關(guān)鍵是圖象投影后的維數(shù)高痴突；字典太小搂蜓，單詞區(qū)分性能差，對相似的目標(biāo)特征無法表示辽装。
3帮碰、相似性測度函數(shù)用來將圖象特征分類到單詞本的對應(yīng)單詞上，其涉及線型核拾积，塌方距離測度核殉挽，直方圖交叉核等的選擇丰涉。
4、將圖像表示成一個(gè)無序局部特征集的特征包方法斯碌，丟掉了所有的關(guān)于空間特征布局的信息一死，在描述性上具有一定的有限性。為此傻唾， Schmid提出了基于空間金字塔的Bag-of-Features投慈。
5、Jégou提出VLAD(vector of locally aggregated descriptors)冠骄，其方法是如同BOF先建立出含有k個(gè)visual word的codebook伪煤，而不同于BOF將一個(gè)local descriptor用NN分類到最近的visual word中，VLAD所采用的是計(jì)算出local descriptor和每個(gè)visual word在每個(gè)分量上的差距凛辣，將每個(gè)分量的差距形成一個(gè)新的向量來代表圖片抱既。

參考資料

[1] BOW 原理及代碼解析
[2] BoW（詞袋）模型詳細(xì)介紹
[3] BoW算法及DBoW2庫簡介
[4] Bag of Features (BOF)圖像檢索算法
[5] BOW模型理解
[6] 圖像檢索中BOW和LSH的一點(diǎn)理解
[7] 使用詞袋模型對圖像進(jìn)行分類
[8] Bag of Features (BOF)圖像檢索算法
[9] SIFT+BOW 實(shí)現(xiàn)圖像檢索
[10] 基于詞袋模型的圖像檢索與分類系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)
[11] BoW(詞袋模型)+python代碼實(shí)現(xiàn)