BOW 演算法，被CNN 打爆之前的王者

在你親歷的短短時間內，世界有哪些驚人的改變？ - 知乎 在這個問題里我提到過2012 年 deep convolutional neural networks 對機器視覺界的衝擊。 簡而言之就是2012 年Alex 使用CNN 突然將圖片識別的正確率降低了一倍！之後CNN 就席捲了Computer Vision 界，對此的研究如同雨後春筍般冒了出來（computer vision 水論文很容易 改個參數就行）。

那麼問題來了... 在CNN 之前 ， 我們用什麼方法來識別圖像？

這裡介紹一個過氣網紅 ----- Bag of visual words 演算法。 這個演算法在10年前， 大約2005-2006 年是非常火的。

故事要從過濾辣雞郵件（Spam）開始，收悉這一演算法的人都知道 在識別辣雞郵件的時候會有一個字典， 上面有很多單詞（vocabulary / words ）， 這些單詞是根據前人對辣雞郵件的總結得出來的。然後系統會對一篇新郵件掃描，數出這篇郵件中這些單詞出現的次數， 然後根據出現的頻率進行預測。

舉個例子， 下圖是 Trump 大妹子和希拉里小胸弟的Vocabulary，遮住前面的名字，你們都能準確得說出左右兩邊分別是誰。 為什麼能這樣做？ 因為在我們的腦中就有了川希兩人的圖像， 一個食指朝天說著 make America great again, 另一個面帶微笑喊 love trumps hate。 看著字典數圖像中vocabulary 出現的個數， 就能清楚地分辨誰是誰。

將這個思路擴展到圖像上。 我們需要用一個方法獲取圖像中的特徵點。這些特徵點就好比川主席推特里的所有推文。 之後我們需要處理這些特徵點，把最具有代表性的單詞（visual words / vocabulary ）羅列出來，構造一個字典（codebook） 。 之後，我們可以把單張圖像上的所有特徵點和這些vocabulary做對比， 如果這個特徵點和某個vocabulary 相似， 就把這個vocabulary的計數+1 ，遍歷所有特徵點就能得到這個圖像的所有頻率分布，遍歷特徵點獲得頻率分布，我們叫做quantization. 先這樣處理training set， 得到已知類別（class）的頻率分布，然後扔到任何一個multicalss classifier 里。再處理test set， 得到頻率分布以後，把頻率分布扔到上一個模型里做預測。

主要思路和垃圾郵件識別是一模一樣的， 只不過一個是圖像，一個是文字。 老外也缺乏創造精神，後者叫bag of words， 前者叫 bag of visual words。

有些人要問了， 我要怎麼從圖像里得到特徵點？ 這裡推薦一個演算法叫做 SIFT 它在圖像中尋找極值點， 並附帶了其他特徵。在我心中這個演算法如同魔術一般是工程學的集大成者， 但不幸在很多方面被CNN打爆了。

有些人又問了， 我要怎麼選取最具有代表性的單詞（vocabulary） ？ 用unsupervised learning， 這裡推薦Kmeans 聚類，或者Random Forest。假設原來有10個class， 每個class 15個圖像，每張圖像都做SIFT，一共得到40k 個特徵點， 然後apply k means ，選取一個合適的k ， 例如 k = 128。 那麼這個k means 的cluster centroid 就是我們要的vocabulary， 這128 個 vocabularies 統稱一個codebook。每張圖的特徵都拿去比照看看哪個vocabulary 更相近，得到概率分布，長度為1*128 。假設我們有150個圖像， 那麼能得到一個 150*128 的matrix，和這150個圖像的label長度為 150*1 ， 之後就扔到multiclass classifier 咯。

下圖就是Bag of visual words 的流程圖。

在實際的過程中，我們要盡量避免過擬合， 盡量避免雜訊。 這裡有很多小聰明可以耍，我的做法是把每張圖的SIFT特徵隨機選 25% ， 扔掉剩下的75% 。 這樣做既可以讓訓練更塊， 又可以避免過擬合。

電腦算力有限，我在 caltech 101 里選了10 個class ，每個class 15 張圖做訓練，15 張圖做測試。 調了一下參數 能做到75% 的正確率。

代碼放在bag of words -public 里。

在構建codebook的時候還能用 Random forest ， 我也試了一下， 除了速度快一點，準確度上並沒有明顯的提升。 具體細節可以參考 Fast Discriminative Visual Codebooks using Randomized Clustering Forests。