1. 簡介

Bag of Visual Words (BoVW) 模型源自於 Bag of Words (BoW, 詞袋模型),是一種圖片分類方法。

在文件檢索中,BoW 模型將文件所包含的字彙 (Words) 分裝在不同的袋子中,每個文件所含的字彙種類不同則會對應到不同的袋子。舉例來說,假設有三個袋子分別包含「汽車、機車、馬路」、「醫生、感冒、生病」、「貓咪、金魚、狗狗」,那今天如果有一個文件裡面提到「汽車」,那我們就比較相信這文件屬於第一個袋子。BoW 簡單來說就是這樣做分類。

同理,在 BoVW 中,因為我們做的是圖片分類,所以這邊的 Word 就會是圖片的特徵,例如一個袋子包含一個人的「眼睛、鼻子、嘴巴」,那麼當我們在辨識一張圖片的時候,看到類似的圖片特徵,例如裡面包含「鼻子、嘴巴」,就可以將他歸類在是這個袋子,反之如果圖片特徵是「桌腳、扶手」那麼就不會是這個袋子,以此方法我們就可以做圖片分類。

2. BoVW 原理與實作

2.1 找出 Kmeans Clusters

我們想要辨識一群照片,這些照片可能有好幾種種類,例如種類分為建築物、森林、動物等。

首先將所有照片的所有特徵都蒐集起來,裡面可能包含家具、屋頂、樹葉、貓尾巴、樹枝等等特徵。

然後用 Kmeans 去歸納這些特徵,找出不同的群集 (Clusters),這個群集就是 BoVW 中的袋子。如果特徵相近,他們就有可能都被歸類在同一個袋子,像是貓尾巴、狗耳朵因為都是動物的器官,他們可能就都屬於同一個袋子。

Kmeans 示意圖

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 示意圖

上方示意圖可以看到,每張照片對應的 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_clustersimage_histogram 找特徵的方法要統一,例如統一用 dsift

2.3 KNN 分類

要能辨識照片,我們會有一組訓練集和一組測試集,訓練集用來學習某個類別的照片的 Histogram 應該長怎樣,測試集則是判斷我們分類的正確性。

我們先替訓練集找出 Histogram 後,再去算要測試的照片的 Histogram,看這張照片的 Histogram 最接近哪一個種類的 Histogram,我們就可以知道這張照片屬於哪一種類。

你可以考慮用 K Nearest Neighbors (KNN) 分類器,演算法如下:

  1. 找出這張測試照片的 Histogram
  2. 比較這個 Histogram 與訓練集所有種類圖片的 Histogram 的差異 (向量距離差)
  3. 選出與此照片 Histogram 差異最小的 K 個訓練集圖片
  4. 統計這 K 個訓練圖片分別屬於哪個種類的分布
  5. 選出票數最高的種類,此為測試照片的種類

2.4 SVM 分類

KNN 正確率大概介於 40~50%,我們可以考慮用 SVM 來做分類,準確率可以達 60~70%。當你不知道要用甚麼分類器的時候通常可以試試看 SVM,處理速度算滿快的。

SVM 分類的簡單原理是將不同群以一條線切開,同時這條線應該和兩邊的群都保有一定距離,如下圖所示:

SVM image
(Source: Dhairya Kumar)

SVM 的原理和實作可以參考這篇「Support Vector Machine — Introduction to Machine Learning Algorithms」。

實作上可以考慮用 Scikit-Learn SVM 或是 LibSVM 函式庫,我們將訓練集找出的 Histogram 丟進 SVM 學習,再讓 SVM 去猜測試的照片是屬於哪個種類。

完整的程式碼範例可以在這邊找到:連結

3. 問題討論

已知一批照片,並且用 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,亦即將原本的群集再切割成更多小的群集。

3.3 不同分類器

根據實驗可以觀察到 SVM 表現是比 KNN 優秀的。

4. 結論

本篇介紹如何用 Bag of Visual Words (BoVW) 模型來做圖片辨識,先將取得圖片集的特徵篩選出有哪些群集,然後對每張照片根據其特徵得到他們的 Histogram,最後用分類器來辨識測試圖片屬於哪一種類的圖片。