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所示是利用欧氏距离作为度量依据，利用naïve查询处理算法来遍历图像库中的每幅图像求得的结果。
表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%。
由于设定的阈值不同，查全率和查准率会有所变化。