劃重點

=================================================
BOF、FV、VLAD等算法都是基于特征描述算子的特征編碼算法，關(guān)于特征描述算子是以SIFT為基礎(chǔ)的一類算法，該類算法能得到圖片的一系列局部特征，該類特征對旋轉(zhuǎn)、縮放、亮度變化保持不變性，對視角變化、仿射變換、噪聲也保持一定程度的穩(wěn)定性，但是該類特征產(chǎn)生的特征矩陣一般都較為龐大，因此需要利用特征編碼算法對其進(jìn)行編碼，以便后續(xù)構(gòu)建索引，實現(xiàn)圖像檢索。

BOF、FV、VLAD都需要對SIFT得到的特征進(jìn)行聚類，得到一個碼本，利用碼本，將原始的N維特征向量映射到K維的空間中，不同之處在于映射方法不同。

BOF（Bag Of Features）：建立碼本時采用K-means，在映射時，利用視覺詞袋量化圖像特征，統(tǒng)計的詞頻直方圖，該詞頻直方圖即為編碼后的特征向量，損失的信息較多。BOF是把特征點做kmeans聚類，然后用離特征點最近的一個聚類中心去代替該特征點，損失較多信息；

FV（Fisher Vector）：FV是對特征點用GMM建模，GMM實際上也是一種聚類，只不過它是考慮了特征點到每個聚類中心的距離，也就是用所有聚類中心的線性組合去表示該特征點，在GMM建模的過程中也有損失信息。

VLAD（vector of locally aggregated descriptors）：VLAD像BOF那樣，只考慮離特征點最近的聚類中心，VLAD保存了每個特征點到離它最近的聚類中心的距離； 像Fisher vector那樣，VLAD考慮了特征點的每一維的值，對圖像局部信息有更細(xì)致的刻畫； 而且VLAD特征沒有損失信息。
=========================================================

VLAD（Vector of Aggragate Locally Descriptor）算法

VLAD算法可以分為如下幾步：

1、提取圖像的SIFT描述子

2、利用提取到的SIFT描述子（是所有訓(xùn)練圖像的SIFT）訓(xùn)練一本碼書，訓(xùn)練方法是K-means

3、把一副圖像所有的SIFT描述子按照最近鄰原則分配到碼書上（也即分配到K個聚類中心）

4、對每個聚類中心做殘差和（即屬于當(dāng)前聚類中心的所有SIFT減去聚類中心然后求和）

5、對這個殘差和做L2歸一化，然后拼接成一個K*128的長向量。128是單條SIFT的長度

如果不考慮海量數(shù)據(jù)的話，這個訓(xùn)練和建庫過程已經(jīng)可以了，直接保存第五步的結(jié)果（圖像庫），然后對查詢圖像做上述的操作，之后計算和圖像庫中每一條向量的歐式距離，輸出前5個最小距離，既是一次完整的檢索過程。

一、簡介

　　雖然現(xiàn)在深度學(xué)習(xí)已經(jīng)基本統(tǒng)一了圖像識別與分類這個江湖，但是我覺得在某些小型數(shù)據(jù)庫上或者小型的算法上常規(guī)的如BoW，F(xiàn)V，VLAD，T-Embedding等還是有一定用處的，如果專門做圖像檢索的不知道這些常規(guī)算法也免得有點貽笑大方了。

　　如上所說的這些算法都大同小異，一般都是基于局部特征（如SIFT，SURF）等進(jìn)行特征編碼獲得一個關(guān)于圖像的feature，最后計算feature之間的距離，即使是CNN也是這個過程。下面主要就是介紹一下關(guān)于VLAD算法，它主要是得優(yōu)點就是相比FV計算量較小，相比BoW碼書規(guī)模很小，并且檢索精度較高。

二、VLAD算法

第一步自然是提取局部特征，有了OpenCV這一步就僅僅是函數(shù)調(diào)用的問題了：

SurfFeatureDetector detector;
SurfDescriptorExtractor extractor;
detector.detect( image_0,  keypoints );
extractor.compute( image_0,  keypoints, descriptors );

　　如果對特征有什么要求也可以根據(jù)OpenCV的源碼或者網(wǎng)上的源碼進(jìn)行修改，最終的結(jié)果就是提取到了一幅圖像的局部特征（還有關(guān)于局部特征參數(shù)的控制）；

第二步本應(yīng)是量化的過程，但是在量化之前需要事先訓(xùn)練一本碼書，而碼書同BoW一樣是用K-means算法訓(xùn)練得到的，同樣OpenCV里面也集成了這個算法，所以這個過程也再簡單不過了：

kmeans(descriptors, numClusters, labels,
           TermCriteria( CV_TERMCRIT_EPS+CV_TERMCRIT_ITER, 10, 0.01 ),
           3, KMEANS_PP_CENTERS, centers);

　　需要做的就是定義一些參數(shù)，如果自己寫的話就不清楚了。另外碼書的大小從64-256甚至更大不等，理論上碼書越大檢索精度越高。

第三步就是量化每一幅圖像的特征了，其實如果數(shù)據(jù)庫較小，可以直接使用全部圖像的特征作訓(xùn)練，然后Kmeans函數(shù)中的labels中存儲的就是量化的結(jié)果：即每一個特征距離那一個聚類中心最近。但是通常訓(xùn)練和量化是分開的，在VLAD算法中使用的是KDTree算法，KDTree算法是一種快速檢索算法，OpenCV里同樣集成了KDTree算法：

const int k=1, Emax=INT_MAX;<br>KDTree T(centers,false);
T.findNearest(descriptors_row, k, Emax, idx_t, noArray(), noArray());

　　通過KDTree下的findNearest函數(shù)找到與之最近的聚類中心，需要注意的是輸入的STL的vector類型，返回的是centers的索引值；

量化結(jié)束之后就是計算特征和中心的殘差，并對每一幅圖像落在同一個聚類中心上的殘差進(jìn)行累加求和，并進(jìn)行歸一化處理，最后每一個聚類中心上都會得到一個殘差的累加和，進(jìn)行歸一化時需要注意正負(fù)號的問題（針對不同的特征）。假設(shè)有k個聚類中心，則每一個聚類中心上都有一個128維（SIFT）殘差累加和向量；
把這k個殘差累加和串聯(lián)起來，獲得一個超長向量，向量的長度為k*d（d=128），然后對這個超長矢量做一個power normolization處理可以稍微提升檢索精度，然后對這個超長矢量再做一次歸一化，現(xiàn)在這個超長矢量就可以保存起來了。

假設(shè)對N幅圖像都進(jìn)行了上面的編碼處理之后就會得到N個超長矢量，為了加快距離計算的速度通常需要進(jìn)行PCA降維處理，關(guān)于PCA降維的理論同KDTree一樣都很成熟，OpenCV也有集成，沒有時間自己寫就可以調(diào)用了：

PCA pca( vlad, noArray(), CV_PCA_DATA_AS_ROW, 256 );
pca.project(vlad,vlad_tt);

　　輸入訓(xùn)練矩陣，定義按照行或列進(jìn)行降維，和降維之后的維度，經(jīng)過訓(xùn)練之后就可以進(jìn)行投影處理了，也可以直接調(diào)用特征向量進(jìn)行矩陣乘法運算。這里有一點就是PCA的過程是比較費時的，進(jìn)行查詢的時候由于同樣需要進(jìn)行降維處理，所以可以直接保存投影矩陣（特征值矩陣），也可以把特征向量、特征值、均值都保存下來然后恢復(fù)出訓(xùn)練的pca，然后進(jìn)行pca.project進(jìn)行投影處理；

如果不考慮速度或者數(shù)據(jù)庫規(guī)模不是很大時，就可以直接使用降維后的圖像表達(dá)矢量進(jìn)行距離計算了，常用的距離就是歐式距離和余弦距離，這里使用余弦距離速度更快。當(dāng)然進(jìn)行距離計算的基礎(chǔ)就是已經(jīng)設(shè)計好了訓(xùn)練過程和查詢過程。

三、總結(jié)

　　可以看到，整個VLAD算法結(jié)合OpenCV實現(xiàn)起來還是非常簡單的，并且小型數(shù)據(jù)庫上的檢索效果還可以，但是當(dāng)數(shù)據(jù)庫規(guī)模很大時只使用這一種檢索算法檢索效果會出現(xiàn)不可避免的下降。另外在作者的原文中，針對百萬甚至千萬級的數(shù)據(jù)庫時單單使用PCA降維加速距離的計算仍然是不夠的，所以還會使用稱之為積量化或乘積量化（Product Quantization）的檢索算法進(jìn)行加速，這個也是一個很有意思的算法，以后有機(jī)會再介紹它。

來源：https://www.cnblogs.com/mafuqiang/p/6909556.html
https://blog.csdn.net/u010333076/article/details/87900431
https://blog.csdn.net/zshluckydogs/article/details/81003966

總結(jié)

以上是生活随笔為你收集整理的VLAD算法浅析, BOF、FV比较的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。