最初的Bag of words，也叫做“詞袋”，在信息檢索中，Bag of words model假定對于一個文本，忽略其詞序和語法，句法，將其僅僅看做是一個詞集合，或者說是詞的一個組合，文本中每個詞的出現都是獨立的，不依賴于其他詞 是否出現，或者說當這篇文章的作者在任意一個位置選擇一個詞匯都不受前面句子的影響而獨立選擇的。

現在Computer Vision中的Bag of words來表示圖像的特征描述也是很流行的。大體思想是這樣的，假設有5類圖像，每一類中有10幅圖像，這樣首先對每一幅圖像劃分成patch（可以是剛性分割也可以是像SIFT基于關鍵點檢測的），這樣，每一個圖像就由很多個patch表示，每一個patch用一個特征向量來表示，咱就假設用Sift表示的，一幅圖像可能會有成百上千個patch，每一個patch特征向量的維數128。

接下來就要進行構建Bag of words模型了，假設Dictionary詞典的Size為100，即有100個詞。那么咱們可以用K-means算法對所有的patch進行聚類，k=100，我們知道，等k-means收斂時，我們也得到了每一個cluster最后的質心，那么這100個質心（維數128）就是詞典里的100個詞了，詞典構建完畢。

詞典構建完了怎么用呢？是這樣的，先初始化一個100個bin的初始值為0的直方圖h。每一幅圖像不是有很多patch么？我們就再次計算這些patch和和每一個質心的距離，看看每一個patch離哪一個質心最近，那么直方圖h中相對應的bin就加1，然后計算完這幅圖像所有的patches之后，就得到了一個bin=100的直方圖，然后進行歸一化，用這個100維的向量來表示這幅圖像。對所有圖像計算完成之后，就可以進行分類聚類訓練預測之類的了。

那么，這里影響效率的一個方面是構建詞典時的K-means聚類，我在用的時候遇到了兩個問題：1、內存溢出。這是由于一般的K-means函數的輸入是待聚類的完整的矩陣，在這里就是所有patches的特征向量f合成的一個大矩陣，由于這個矩陣太大，內存不頂了。我內存為4G。2、效率低。因為需要計算每一個patch和每一個質心的歐拉距離，還有比較大小，那么要是循環下來這個效率是很低的。

為了解決這個問題，我采用一下策略，不使用整一個數據矩陣X作為輸入的k-means，而是自己寫循環，每次處理一幅圖像的所有patches，對于效率的問題，因為matlab強大的矩陣處理能力，可以有效避免耗時費力的自己編寫的循環迭代。

我自己的代碼下載：

PG_SPBOW.zip : Matlab code for computing the bag of visual words at different levels of spatial pyramid of images.

[轉帖]李菲菲 bag of words