Bag of features

Bag of features ( BOF)一种适用于图像和视频检索的算法。BOF借鉴了文本分类的思路（也就是BOW），从图像抽象出很多具有代表性的「关键词」，形成一个字典，再统计每张图片中出现的「关键词」数量，得到图片的特征向量。
此算法的神奇之处，就在于对于不同角度，光照的图像，基本都能在图像库中正确检索。所以，在这里，我们要先了解一下BOW（Bag of features）算法。

Bag of Words

（Bag of Words） 是文本分类中一种通俗易懂的策略。一般来讲，如果我们要了解一段文本的主要内容，最行之有效的策略是抓取文本中的关键词，根据关键词出现的频率确定这段文本的中心思想。比如：如果一则新闻中经常出现「iraq」、「terrorists」，那么，我们可以认为这则新闻应该跟伊拉克的*有关。而如果一则新闻中出现较多的关键词是「soviet」、「cuba」，我们又可以猜测这则新闻是关于冷战的，如下图。

这里所说的关键词，就是BOW中的 W-words ，它们是区分度较高的单词。根据这些 words ，我们可以很快地识别出文章的内容，并快速地对文章进行分类。

BOF借鉴了这种思路，只不过在图像中，我们抽出的不再是一个个word，而是图像的关键特征“Feature”，所以研究人员将它更名为Bag of Feature。

BOF算法

通过对BOW的了解，我们可以大致明白BOF的本质是提出一种图像的特征表示方法。
首先我们要找到图像中的关键词，而且这些关键词必须具备较高的区分度。实际过程中，通常会采用SIFT特征算法（之前的博客中有粗略的介绍）。
然后，我们会将这些特征通过聚类算法得出很多聚类中心。这些聚类中心通常具有较高的代表性，比如，对于人脸来说，虽然不同人的眼睛、鼻子等特征都不尽相同，但它们往往具有共性，而这些聚类中心就代表了这类共性。我们将这些聚类中心组合在一起，形成一部“字典”。（听起来有没有感觉很厉害）
对于图像中的每个SIFT特征，我们能够在字典中找到最相似的聚类中心。统计这些聚类中心出现的次数，可以得到一个向量表示（或者称为直方图），如下图。
这些向量就是所谓的「Bag」。

算法过程

BOF算法大概分为四步：

提取图像特征；

就不用多说了，为使特征具有较高的区分度，而且满足旋转不变性以及尺寸不变性等，通常都会采用「SIFT」特征

对特征进行聚类，得到一部字典（ visual vocabulary ）；

我们会采用一些聚类算法对这些特征向量进行聚类。最常用的聚类算法是 k-means。另外，由于特征的数量可能非常庞大，这个聚类的过程也会非常漫长。

根据字典将图片表示成向量（直方图）；

上一步训练得到的字典，是为了这一步对图像特征进行量化。因为，对于一幅图像而言，我们可以提取大量的SIFT特征点，但这些特征点仍然属于一种不够具体的表达，缺乏代表性。所以，就要根据字典重新提取图像的高层特征。具体做法是，对于图像中的每一个SIFT特征，都可以在字典中找到一个最相似的 visual word，这样，我们可以统计一个 k 维的直方图，代表该图像的SIFT特征在字典中的相似度频率。

训练分类器或者用 KNN 进行检索。

当我们得到每幅图片的直方图向量后，剩下无非是根据数据库图片的向量以及图片的标签，训练分类器模型。对需要预测的图片，我们仍然按照上述方法，提取SIFT特征，用分类器模型对直方图向量进行分类。不过，也可以直接根据 KNN 算法对直方图向量做相似性判断。

个人实验结果