Scale Invariant Feature Transform（以下簡稱SIFT）算法由D.G.Lowe 1999年提出，2004年完善總結[7]。SIFT算法是一種提取圖像局部特徵的算法，其對旋轉、尺度、亮度變化保持不變性，對視角變化、仿射變換、噪聲保持一定的穩定性。
Bag-of-Feature（以下簡稱BoF）Descriptor是用於數據分類流行的視覺描述符之一。BoF的靈感源於一個用來進行文檔分類的Bag of Word（以下簡稱BoW）。在計算機視覺中，一個BoW代表詞彙的出現次數的稀疏向量。也就是說，一個特徵視覺上的BoW就相當於局部圖像特徵的出現次數的稀疏向量。
在使用BoF之前，需要做圖像的分解。圖像的分解被描述為：利用低級特徵來描述圖像，如顏色、形狀和紋理特徵。顏色直方圖、形狀輪廓、邊緣直方圖描述符都是很流行的基於圖像內容檢索的技術。為了獲得一個BoF描述符，本節中我們使用SIFT算法對圖像提取特徵。SIFT算法是特徵提取和描述中很受歡迎的算法之一。SIFT特徵點很可能是圖像中的一個角點、邊緣點、暗區的亮點及亮區的暗點等。
下面是我們基於SIFT提取特徵的BoF思想的算法[8]。
7.8.1 BoF-SIFT算法的使用
在Windows 7環境下，使用Visual Studio 2010開發環境，配置OpenCV2.4.9。解決方案配置選擇「release」，該算法對應的項目文件名稱是「BoFSIFT.sln」，位於「..BoF-SIFTBoFSIFT」路徑下。
使用Visual Studio 2010打開「..BoFSIFTBoFSIFT」路徑下的BoFSIFT.sln文件，運行源文件中的BoFSIFT.cpp文件即可。
7.8.2 BoF-SIFT算法原理
首先我們瞭解一下SIFT算法的原理。SIFT是一種檢測圖像局部特徵的算法，該算法通過在尺度空間尋找極值點，提取位置、尺度、旋轉不變量，並求特徵點的描述子，從而為相似性檢索提供依據。
BoF主要分為兩大步。第一步是得到BoF集合，可以得到特定特徵包的集合，然後使用它們生成BoF描述符；第二步是對已給的特徵聚集，然後將這些包視為一個直方圖中的柱子（Bar），最後使用該直方圖對圖像進行分類。
7.8.3 BoF-SIFT算法實現
SIFT算法的步驟如下。
（1）構建尺度空間。
（2）檢測DoG尺度空間極值點：為了尋找尺度空間的極值點，每一個採樣點要與其所有的相鄰點比較，看它是否比其圖像域和尺度域的相鄰點大或者小。中間的檢測點和它同尺度的8個相鄰點和上下相鄰尺度對應的9×2個點（共26個點）比較，以確保在尺度空間和二維圖像空間都檢測到極值點。一個點如果在DoG尺度空間本層以及上下兩層的26個領域中是最大或最小值，就認為該點是圖像在該尺度下的一個特徵點。
（3）除去不好的特徵點：去掉DoG局部曲率不對稱的像素。
（4）給每一個特徵點賦值一個128維方向參數：上一步中確定了每張圖像中的特徵點，為每個特徵點計算一個方向，依照此方向做下一步的計算，利用關鍵點鄰域像素的梯度方向分佈特性為每個特徵點制定方向參數，使算子具備旋轉不變性。其中每一個關鍵點有三個信息：位置、所處尺度、方向。梯度直方圖的範圍是0°～360°，其中每10°一個柱，共36個柱。距中心點越遠的領域，其對直方圖的貢獻也相應越小。
在實際計算時，我們在以關鍵點為中心的鄰域窗口內採樣，並用直方圖統計鄰域像素的梯度方向。梯度直方圖的範圍是0°～360°，其中每45°一個柱，共8個柱；或者每10°一個柱，共36個柱。直方圖的峰值則代表了該關鍵點處鄰域梯度的主方向，即作為該關鍵點的方向。
（5）關鍵點描述子的生成：首先將坐標軸旋轉為關鍵點的方向，以確保旋轉不變形。以關鍵點為中心取16×16像素的窗口，然後將該窗口分為4×4=16個子窗口。對於每個子窗口（其實就是4×4個像素點的區域），我們用8個方向來描述它，最終就得到了16×8=128維的描述子，每一維都可以表示4×4個格子中的scale/orientation，將這個向量歸一化後就進一步去除了光照的影響。需要注意的是，128維表示的是一個描述子，也就是一個特徵點，而非表示整個圖像。也就是說，一個圖像是由若干個128維的描述子組成。如若判斷兩個圖像是否相似，現假設圖像A是由m個128維的描述子組成，圖像B是由n個128維的描述子組成，使用圖像A的第一個特徵描述子與圖像B的所有描述子進行匹配，以此類推，直至遍歷完圖像A的所有描述子，匹配成功的個數達到預設定的閾值，我們就認為這兩個圖像是相似圖像。但是本節算法中我們並沒有採用該方法，而是採用和BoF思想相結合的相似性圖像檢索。下面我們來看一下BoF-SIFT結合後的算法實現。
文獻[8]實現了BoF-SIFT算法，相關的算法步驟如下。
（1）計算圖像庫中的特徵包集合。
１挑選出一個大的圖像庫。
２提取圖像庫中所有圖像的SIFT特徵點，得到每個特徵點的SIFT描述符。
３使用K-means對所有的特徵描述符集合進行聚集。
４得到一個視覺的詞彙表。
（2）得到查詢圖像的BoF描述符。
１提取查詢圖像的SIFT特徵點。
２得到每個特徵點的SIFT描述符。
３與第一步生成的詞彙表和特徵描述符匹配。
４建立直方圖。
（3）計算歐氏距離，輸出查詢圖像與圖像庫中所有圖像的相似度。其中，文獻[8]中給出了BoF-SIFT算法的核心代碼。
obtain_dictionary函數如下：
obtain_BoF(char * )函數如下[8]：
計算查詢圖像與圖像庫中的每個圖像的歐氏距離（此算法中SIFT提取出來特徵為128維度）。calculateEuDis函數參考本書7.2節。
7.8.4 BoF-SIFT算法的實驗數據、實驗結果及分析
1.實驗數據
輸入圖像為「..BoFSIFTimage」路徑下的所有（495幅）圖像。
輸入測試圖像為「..BoFSIFTimageS001-008.jpg」圖像。
image圖像集的說明：以其中一幅圖像的名稱為例，「s001-001.jpg」就代表第一個人的第一幅圖像，「s001-002.jpg」就表示第一個人的第二幅圖像，「s002-001.jpg」代表第二個人的第一幅圖像。
2.實驗結果
實驗結果存儲在「..BoFSIFTBoFSIFTsimility.txt」。以下是歐氏距離度量方法的部分查詢結果。
查詢圖像如圖7-7所示。
圖7-7 查詢圖像（4）
檢索出的部分相似圖像如圖7-8所示。
圖7-8 檢索出的部分相似圖像（4）
表7-4所示是利用歐氏距離作為度量依據，利用naive查詢處理算法來遍歷圖像庫中的每幅圖像求得的結果。
表7-4 實驗結果
續表
3.實驗分析
使用餘弦相似度度量方法：設置餘弦相似度閾值為0.82。實驗結果查准率為29/42×100%=69.05%，查全率為29/42×100%=69.05%。
使用歐氏距離度量方法：設置歐氏距離相似度閾值為0.5。查准率為30/60×100%=50%，查全率為30/42×100%=71.43%。
由於設定的閾值不同，查全率和查准率會有所變化。