Pattern Recognition
Term Project Report Using Visual Words for Image Classification
u9562171, 雷禹恆
1.Abstract
Visual words 近年來在image retrieval領域被大量使用。它是基於文字上的textual words，套用在影像上的類比，因此可將過去在text retrieval領域的技巧直接利用於image retrieval，也有助於large-scale影像搜尋系統的效率。Visual words的擷取大致上是將影像的SIFT features，在keypoint feature space上做K-means clustering的結果，以histogram來表示，是一種bag-of-features。除了可用於retrieval外，visual words也被用於image classification。本專題的目的就是將visual words作為影像特徵，並套用於multi-class image classification。does的过去式
2.Introduction
Visual words (簡稱VWs) 近年來在image retrieval領域被大量使用，其motivation其實是從text retrieval領域而來，是基於文字上的textual words，套用在影像上的類比。
债权国
如同於一篇文章是由許多文字 (textual words) 組合而成，若我們也能將一張影像表示成由許多 “visual words” 組合而成，就能將過去在text retrieval領域的技巧直接利用於image retrieval；而以文字搜尋系統現今的效率，將影像的表示法「文字化」也有助於large-scale影像搜尋系統的效率。
在文獻 [1] 有提到motivation of visual words的細節。首先我們先回顧text retrieval 的過程：1. 一篇文章被par成許多文字，2. 每個文字是由它的「主幹(stem)」來表示的。例如以 ‘walk’ 這個字來說，‘walk’、‘walking’、‘walks’ 等variants同屬於 ‘walk’ 這個主幹，在text retrieval system裡被視為同一個字。3. 排除掉每篇文章都有的極端常見字，例如 ‘the’ 和 ‘an’。4. 一篇文章文章的表示法，即以每個字出現頻率的histogram vector來表示。5. 在此histogram中，對於每個字其實都有給一個某種形式weight，例如Google利用PageRank [2] 的方式來做weighting。6. 在執行文字搜尋時，回傳和此query vector最接近(以角度衡量)的文章。
下一節將解釋影像中VW的特徵擷取流程，及其與此段之1.、2.、4.的類比。
3.Construction of Visual words
Visual words的建構流程可以用圖(1)來說明：
圖(1)：Construction of visual words
步驟1：偵測影像中的SIFT keypoints，並計算keypoint descriptors。例如在原始SIFT文獻 [3] 使用Difference of Gaussians (DoG) 來偵測keypoints，而以一個128-D的向量作為descriptor。偵測keypoints的動作相當於上一節所說的1. 將文章par成一個一個的文字。contractor
步驟2：將所有訓練影像的所有keypoint descriptors，散佈於一個128-D的keypoint feature space中，再執行一個clustering algorithm，例如K-means或是這學期教過的EM。在image retrieval領域中，cluster數K 常訂為104~ 106。同一個cluster裡的keypoints，相當於是同一個 “visual word stem” 的variants，在retrieval / classification系統中被視為同一個VW，因此K也被稱為系統裡的 “vocabulary size”。clustering後的結果相當於上一節所說的2. 同一個word stem下有許多的variants。
步驟3：最後，一張影像可看成由許多VW（原先是keypoints）組成。因為在retrieval領域，我們並不在意文字的排列順序，只在意文章中文字的出現頻率，同樣
的道理，一張影像中我們只在乎每個VW stem的出現頻率。以這種概念構成的特徵被稱為 “Bag-of-features”，只在乎袋子裡有什麼物品，而不是物品的排列順序。因此影像特徵的表示法為根據VW出現頻率的 “visual word histogram”。這種概念與上一節4.
的文字出現頻率histogram相同。
cau i am your lady
結論：Visual words可看作是將影像中local的keypoint descriptors，套上clustering algorithm後，變成整張影像的global feature。
Visual words 除了大量用於image retrieval外，也可以直接作為features用於image classification。本專題的目的就是將visual words作為影像特徵，並套用於multi-class image classification。
4.Datat
dutycycle
網路上屬於multi-class，每個class大量，但一張影像只有單一物件的datat沒有想像中得好找。後來選擇了Caltech 101 [4] 的subt作為本次實驗的datat。Caltech 101雖然有101種object class，但class裡夠多張影像的只有5種，資料夾名稱(重新命名名稱)分別是：airplanes(Airplane)、BACKGROUND_Google(None)、Faces_easy(Face)、Faces(未使用)、Motorbikes(Motorbike)。Faces和Faces_easy我只選擇切割比較好的Faces_easy來使用。另外我也挑掉不少label有瑕疵的影像，尤其是None類別雖然號稱為背景，裡面卻有很多時候出現人臉。還有極少數張取VW失敗的影像也被剔除。
stevie wonder最後剩下的datat，我對於4個class分別以training : testing = 9 : 1的方式分配比例。各類的張數統計如表(1)，可看出Airplane和Motorbike的量約為Face和None的兩倍。影像範例如圖(2)，可看出None類別比較困難，因為各式各樣的內容都有，但其他三個類別就簡單許多，物體也少有被干擾的情況。
表(1)：datat中各類影像的張數統計
(b) Face
(a) Airplane
initial(c) Motorbike(d) None
圖(2)：datat中4類影像的範例
5.Experiment Results and Obrvations
本次實驗使用MATLAB R2009b (64-bit)，系統環境是Mac OS X 10.6.3，Intel Cuo
2 Duo 2.16GHz processor，3G RAM。分類器必須配合libSVM [5] 的主package與
MATLAB interface。詳細使用說明見。
而使用的features: visual word histograms，是把原始圖片給實驗室學長姊後，請她們用實驗室的tools幫我轉成VW文字檔的，其中偵測keypoints的方式是Hessian Affine (HA)，而非SIFT文獻上的Difference of Gaussians (DoG)。也就是說，feature extraction 的部分是training和testing皆事先完成。V ocabulary size分別有K = 10,000 (104)，1,000 (103)，及125 (53)。
Attempt 1：一開始我只使用作業學過的MATLAB內建SVM來分類。由於只支援binary classification，我用one-against-one的方式訓練了 C * (C-1) / 2 = 6個分類器，再用majority vote決定output值。使用人造data跑起來還算合理，但套進真實資料：K = 10,000的VW以後，外加手動測試了一些SVM參數，結果卻非常離譜地差。training與testing的confusion matrices如表(2)：
training [720000 039100 007170 000331]
片假名翻译
fromytoytesting [80000440008000037000]
表(2)：Attempt 1實驗的confusion matrices
可以看出training意外地完全被分對，testing卻完全被分到class 1(Airplane)。檢查之下發現在SVM train的過程中，所有的點都被歸類為support vectors，也就是本次實驗的結果極端地fit我的training data，對testing data幾乎沒有classification的能力。
Attempt 2：接著我改用libSVM的multi-class classifier來分類，配上其提供的parameter lection tools (grid.py)。實驗的結果好很多，整體accuracy可達90%以上。嘗試了K = 10,000和K = 1,000，其confusion matrix，每個class的recall與precision如表(3)：
confusion=[76013043010079141032],recall=[0.950.980.990.86],precision=[0.950.980.990.87]
完美的英文(a) K = 10,000：Accuracy = 95.4357% (230/241) confusion=[76013044000079142130],recall=[0.951.000.990.81],precision=[0.950.960.980.88]
(b) K = 1,000：Accuracy = 95.0207% (229/241)
表(3)：Attempt 2的實驗數據
Attempt 2的結果遠優於Attempt 1，我認為可能是MATLAB內建的SVM能力無法應付本次的高維度datat，或是只用人工測試少數SVM參數遠比用tools的效果差。另外從表(3)可看出，class 4 (None) 的recall和precision皆最差，符合預期，因為此類別的影像內容什麼都有，本身就比較困難，其他3個類別相對簡單很多，所以數據都蠻不錯的。本報告之後實驗結果，各個class的表現也符合這樣的現象。
Attempt 3：雖然Attempt 2的結果已經很好，datat仍然存在著一個問題：我的datat實際的dimensionality (K)是否真的有1,000、10,000那麼高？因此我接著多使用PCA (Principal Component Analysis) 來做轉換和降維，因為K = 10,000的PCA超出我自己電腦的運算能力，Attempt 3只測試K = 1,000。目標維度我利用保留多少百分比的total variance來決定，分別測試100%、99%、98%、97%、96%、95%。實驗數據如表(4)：
