Bag-of-words模型是信息检索领域常用的文档表示方法。在信息检索中，BOW模型假定对于一个文档，忽略它的单词顺序和语法、句法等要素，将其仅仅看作是若干个词汇的集合，文档中每个单词的出现都是独立的，不依赖于其它单词是否出现。例如有如下两个文档： 

1：Bob likes to play basketball, Jim likes too.      2：Bob also likes to play football games. 

基于这两个文本文档，提取单个单词，并构造一个词典： 

Dictionary = {1:”Bob”, 2. “like”, 3. “to”, 4. “play”, 5. “basketball”, 6. “also”, 7. “football”, 8. “games”, 9. “Jim”, 10. “too”}。

这个词典一共包含10个不同的单词，根据词典，对上面两个文档中的单词出现次数进行统计，每个文档可表示为10维向量。如下：

1：[1, 2, 1, 1, 1, 0, 0, 0, 1, 1]      2：[1, 1, 1, 1 ,0, 1, 1, 1, 0, 0]

若每种类型的文档中单词的直方图统计呈现特定的规律，则可以利用这种规律进行海量文档归类。

Bag Of Feature

1.1 [CVPR06] Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories

摘要：将BOW的思想引入到图像中来，word在图像中用一种特定的特征描述子来代替，但这样完全忽略了图像的空间布局关系，incapable of capturing shape or of segmenting an object from its background，因此结合空间金字塔匹配来实现。 Our method involves repeatedly subdividing the image and computing histograms of local features at increasingly fine resolutions.

比较：以下三方面和传统方法比较： 

1 locally orderless images：SPM as an alternative formulation of a locally orderless image, instead of a Gaussian scale space of apertures,define a fixed hierarchy of rectangular windows. 2 multiresolution histograms：fixing the resolution at which the features are computed, but varying the spatial resolution at which they are aggregated.3 subdivide and disorder：the best subdivision scheme may be achieved when multiple resolutions are combined in a principled way; the reason for the empirical success of “subdivide and disorder” techniques is the fact that they actually perform approximate geometric matching.

Pyramid Match Kernels:

xy表示两个矢量 PyramidMatch用来计算xy之间的appriosimate correspondence.通过placing a sequence of increasingly coarser grids over the feature space and taking a weighted sum of the number of matches that occur at each level of resolution.

Match means they fall into the same cell. Resolution counts from 0 to L.

At level l,image can be divide into 2exp(d*l) cells(这里的cell应该就是后面的聚类中心？);The number of matchs at level l is given by (1);

The weight number of level l is set to 1/(2exp(L-l)),Note lower(coarser) level include the num of finer level, so the num of level l is given by .The Pyramid match kernel can be given by(2);

(1)(2)

(1)为什么表示了xy之间的appriosimate correspondence？怎样计算H，如何算是fall into the same cell？

Spatial Matching Scheme 

perform pyramid matching in the two-dimensional image space, and use traditional clustering techniques in feature space.(对于图像中feature空间，图像的坐标已经包含了几何空间信息，只需要按照坐标顺序排列vector即可)(特征空间用聚类将特征聚到M个类别channel，大概就是上面讲的fall into the same cell，H就是用直方图统计，I越小表示二者相关度越小)

 The final dimension is:(上式中k(x,y) 中并不是相加 而是每level的I矢量连接成一个很长的矢量) ;  M=400 L=3 d=34000 is long and sparse.

Normalize all histograms by the total weight of all features in the image. 

Q：

局部和全局特征表示：本文中说到SPM是一种approximate global geometric correspondence，又如何理解an alternative formulation of a locally orderless image,传统的局部和全局特征是怎样定义的，有哪些？？

ps：

部分来源于：http://blog.csdn.net/v_JULY_v

经典论文学习bag of feature（二）