使用 Bag of Visual Words 做圖片分類
Bag of Visual Words (BoVW) 模型源自於 Bag of Words (BoW, 詞袋模型),是一種圖片分類方法。
在文件檢索中,BoW 模型將文件所包含的字彙 (Words) 分裝在不同的袋子中,每個文件所含的字彙種類不同則會對應到不同的袋子。舉例來說,假設有三個袋子分別包含「汽車、機車、馬路」、「醫生、感冒、生病」、「貓咪、金魚、狗狗」,那今天如果有一個文件裡面提到「汽車」,那我們就比較相信這文件屬於第一個袋子。BoW 簡單來說就是這樣做分類。
同理,在 BoVW 中,因為我們做的是圖片分類,所以這邊的 Word 就會是圖片的特徵,例如一個袋子包含一個人的「眼睛、鼻子、嘴巴」,那麼當我們在辨識一張圖片的時候,看到類似的圖片特徵,例如裡麪包含「鼻子、嘴巴」,就可以將他歸類在是這個袋子,反之如果圖片特徵是「桌腳、扶手」那麼就不會是這個袋子,以此方法我們就可以做圖片分類。
2. BoVW 原理與實作
2.1 找出 Kmeans Clusters
我們想要辨識一羣照片,這些照片可能有好幾種種類,例如種類分為建築物、森林、動物等。
首先將所有照片的所有特徵都蒐集起來,裡面可能包含傢俱、屋頂、樹葉、貓尾巴、樹枝等等特徵。
然後用 Kmeans 去歸納這些特徵,找出不同的羣集 (Clusters),這個羣集就是 BoVW 中的袋子。如果特徵相近,他們就有可能都被歸類在同一個袋子,像是貓尾巴、狗耳朵因為都是動物的器官,他們可能就都屬於同一個袋子。
Kmeans 的羣集是我們可以決定的,一般來說會取辨識種類的 10 倍,亦即如果一羣照片要被分成 5 種的話,Kmeans 會區分成 50 個羣集,一個羣集可以視為是一個特徵的集合。如上圖,所有跟山嶽類似的特徵都會被分到「山」的特徵集合。
以下示範如何取得特徵與 Kmeans 集合:
import numpy as np import cv2 from cyvlfeat.kmeans import kmeans from cyvlfeat.sift.dsift import dsift def get_clusters(images, cluster_size, method="dsift"): bag_of_features = [] for img in images: # 遍歷所有圖片 if(method == "dsift"): _keypoints, descriptors = dsift(img, step=[5,5], fast=True) elif(method == "orb"): orb = cv2.ORB_create() _keypoints, descriptors = orb.detectAndCompute(img, None) elif(method == "sift"): sift = cv2.xfeatures2d.SIFT_create() _keypoints, descriptors = sift.detectAndCompute(img, None) if descriptors is not None: for des in descriptors: bag_of_features.append(des) clusters = kmeans(np.array(bag_of_features).astype('float32'), cluster_size, initialization="PLUSPLUS") return clusters feature_clusters = get_clusters(images, 150, method="dsift")
在上面實作中, descriptor
就是一張圖片的其中一個特徵描述量,也可以說是一個 word,通常是一個描述局部區域的矩陣。取得特徵的方法有很多,像是程式碼中就提供了 DSIFT (Dense SIFT)、SIFT、ORB 三種擷取方法。根據實測 DSIFT 在分類問題中表現最好,在文後會仔細討論。
Kmeans 有很多 Python 函式庫都有提供,不過經過實測 cyvlfeat 表現比 sklean 和 scipy 都快,但如果要更快的話,還有其他用不同演算法時實現的函式庫,根據數據多寡和要分羣的大小不同算法效能上也會有差。
2.2 圖片的 Histogram
一張照片會包含許多不同特徵,這些特徵分別屬於剛剛得到 Kmeans Clusters 中的不同羣集。
如果這張照片是山嶽的話,那麼它的特徵應該大部分都會跟山、山峯、山嶽等等屬於相同的羣集。於是我們可以去統計這張照片的特徵,分別屬於不同羣集的數量,就可以判斷他應該是哪一種類的照片。這個方法方法就是 BoVW。
實務上,我們可以用 Histogram (統計圖) 來表示 BoVW,記錄這張圖片對應羣集的分佈。
上方示意圖可以看到,每張照片對應的 Histogram 都不太一樣,以此我們可以推論他們分別屬於哪一種類的照片,如果是傢俱建築物可能紅色就多一點,如果是自然可能藍色特徵就多一點。
def image_histogram(image, feature_clusters, method="dsift"): # 這邊我只寫出 dsift 以節省空間 if(method == "dsift"): _keypoints, descriptors = dsift(image), step=[5,5], fast=True) # 比較這張照片的特徵和羣集的特徵 dist = distance.cdist(feature_clusters, descriptors, metric='euclidean') # 替這張照片每個特徵選最接近的羣集特徵 idx = np.argmin(dist, axis=0) # 建立 Histogram hist, bin_edges = np.histogram(idx, bins=len(feature_clusters)) hist_norm = [float(i)/sum(hist) for i in hist] return hist_norm
這邊要注意 get_clusters
和 image_histogram
找特徵的方法要統一,例如統一用 dsift
。
要能辨識照片,我們會有一組訓練集和一組測試集,訓練集用來學習某個類別的照片的 Histogram 應該長怎樣,測試集則是判斷我們分類的正確性。
我們先替訓練集找出 Histogram 後,再去算要測試的照片的 Histogram,看這張照片的 Histogram 最接近哪一個種類的 Histogram,我們就可以知道這張照片屬於哪一種類。
你可以考慮用 K Nearest Neighbors (KNN) 分類器,演算法如下:
- 找出這張測試照片的 Histogram
- 比較這個 Histogram 與訓練集所有種類圖片的 Histogram 的差異 (向量距離差)
- 選出與此照片 Histogram 差異最小的 K 個訓練集圖片
- 統計這 K 個訓練圖片分別屬於哪個種類的分佈
- 選出票數最高的種類,此為測試照片的種類
KNN 正確率大概介於 40~50%,我們可以考慮用 SVM 來做分類,準確率可以達 60~70%。當你不知道要用甚麼分類器的時候通常可以試試看 SVM,處理速度算滿快的。
SVM 分類的簡單原理是將不同羣以一條線切開,同時這條線應該和兩邊的羣都保有一定距離,如下圖所示:
(Source: Dhairya Kumar )
SVM 的原理和實作可以參考這篇「 Support Vector Machine — Introduction to Machine Learning Algorithms 」。
實作上可以考慮用 Scikit-Learn SVM 或是 LibSVM 函式庫,我們將訓練集找出的 Histogram 丟進 SVM 學習,再讓 SVM 去猜測試的照片是屬於哪個種類。
完整的程式碼範例可以在這邊找到: 連結
已知一批照片,並且用 BoVW 來做分類。照片分為 15 種類,每一個種類都有 100 張 256*256 像素的灰階照片,用來當作訓練集,此外每一類都有 10 張同規格照片作為測試集。
種類如下:
測試環境是 Macbook Pro 2017 with 2.3 GHz Intel Core i5 搭配 Python 3.6。
實驗結果如下:
Descriptor | Kmeans Cluster | KNN(%) | Linear SVM(%) | Time(min) |
---|---|---|---|---|
DSIFT | 60 | 49.3 | 58 | 12:10 |
DSIFT | 150 | 40.7 | 57.3 | 20:52 |
DSIFT | 300 | 39.3 | 60.7 | 51:19 |
SIFT | 60 | 30 | 42.7 | 4:33 |
SIFT | 150 | 24.7 | 38.7 | 6:33 |
SIFT | 300 | 22.7 | 34.7 | 9:57 |
ORB | 60 | 12.7 | 14 | 0:30 |
ORB | 150 | 12.7 | 17.3 | 1:15 |
ORB | 300 | 10.0 | 13.3 | 2:23 |
3.1 特徵演算法差異
可以看到 DSIFT 雖然花費時間最長,但表現也最好。令人意外的是 ORB 的雖然非常快但結果十分差。
這其實可以理解,DSIFT 是一種 Dense Feature Extraction,白話來說就是一次取用好幾個特徵來用,那麼對於物體形狀的辨識也會比較優秀。反之 ORB 這種主要拿來找 Key Points 的演算法,對於局部的理解的比較低,就比較難辨識出形狀。
3.2 Kmeans 羣集數量差異
Kmeans 需要在獨特性和穩健度上取得平衡,分羣數量較少,羣集差異越大,反之分羣數量較多,差異度可能不是很大,但結果可能會比較穩健,這也會影響演算法的效能。
實驗中分別設定 Kmeans 的羣集數量為 60、120、300,分別是圖片種類的 2 倍、4 倍、20 倍,發現 DSIFT 在 300 個羣集時表現最優,但也只好一點點,代價卻是幾乎兩倍以上的時間,因為 Kmeans 的複雜度是 $O(t \times k \times n \times d)$,其中 $t$ 是迭代次數,$k$ 是羣集數量,$n$ 是多少個點,$d$ 是每個點的維度。
此外可以觀察到 SIFT 卻是 60 時最高,而 ORB 則是 150 最高。
因此在此實驗情況下分羣不需要很大,也許是因為照片種類差異比較大,少量羣集就可以分辨出不同種類。
實務上如果分類效果不佳,可以試試看 Hierarchically clustering,亦即將原本的羣集再切割成更多小的羣集。
根據實驗可以觀察到 SVM 表現是比 KNN 優秀的。
本篇介紹如何用 Bag of Visual Words (BoVW) 模型來做圖片辨識,先將取得圖片集的特徵篩選出有哪些羣集,然後對每張照片根據其特徵得到他們的 Histogram,最後用分類器來辨識測試圖片屬於哪一種類的圖片。