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

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

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

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

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

為了解決這個(gè)問題，我采用一下策略，不使用整一個(gè)數(shù)據(jù)矩陣X作為輸入的k-means，而是自己寫循環(huán)，每次處理一幅圖像的所有patches，對于效率的問題，因?yàn)閙atlab強(qiáng)大的矩陣處理能力，可以有效避免耗時(shí)費(fèi)力的自己編寫的循環(huán)迭代。

我自己的代碼下載：

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

[轉(zhuǎn)帖]李菲菲 bag of words