基于局部聚合描述符的視點不變視覺位置識別

劉 靖

(吉林大學 吉林吉大通信設計院股份有限公司，吉林 長春 130012)

0 引 言

視覺地點識別系統可用于識別機器人是否曾經訪問過它當前的位置[1]。即使場所的外觀發生變化，或從不同的角度觀察場景，視覺識別(檢測)系統[2]都應該能識別場景。隨著智能機器人的快速發展，該方面的研究逐漸成為熱門研究課題。

很多位置識別的研究著重關注視點不變性、條件不變性及效率。如Mactavish等[3]提出了在同一視角下利用記憶功能進行長時間的視覺定位方法。Liu等[4]設計了一種基于形狀匹配的視覺定位算法，算法在速度和精度兩個方面均達到與國外商業軟件相當的水平，可部分替代商業軟件使用。Yan等[5]提出的“視覺-詞語”將特征空間量化成一組集群，由二進制串描述圖像，將圖像簡化為二進制串匹配，匹配效率高。在保持高效性能的同時，還可以通過局部聚合描述符(vector of locally aggregated descriptor，VLAD)等技術來增強BOW模型的性能[6]。文獻[7]中提出了農業機器人視覺定位方法，即：基于目標的顏色、形狀和位置特征。Gao等[8]提出的FAB-MAP、文獻[9]提出的 SeqSLAM 均采用圖像過濾方法進行視點及條件不變的位置識別，但這類方法計算代價非常大。

與以上方法不同，本文提出了一個位置識別系統，將條件不變的特征和輕量級的圖像描述機制結合起來，采用VLAD[10]向量。即使在外觀和視點發生變化的情況下，也可以進行位置識別。但當每個位置分配的內存數量減少時，基于VLAD系統的性能就會下降。VLAD的計算效率類似于一個BOW模型，但所提VLAD系統在相同內存占用情況下，具有更高的性能。

1 本文方法

在變換的環境下，本文的目標是將用于視覺位置識別的魯棒描述符與低內存要求和有特征量化的技術(如BOW和VLAD模型)相結合，以提供更快的圖像匹配。由于VLAD模型已被證明性能優于BOW模型，所以本文選用VLAD。本文方法的基本流程如圖1所示。

圖1 本文方法的基本流程

1.1 特征檢測

相比于其它特征檢測算法，SURF算法的魯棒性及檢測出的特征的視點不變性較好，其穩鍵性高，效率也表現優秀[11]，所以本文選用SURF算法檢測特征。為了計算描述符，本文將每個關鍵點的感興趣區域定義為大小為20s×20s 的區塊，其中s是檢測到的SURF關鍵點尺度。

1.2 特征描述

所選描述符采用梯度直方圖[12](histogram of gradient，HoG)，可以在變換的環境中有效識別特征，具有良好的魯棒性和效率。

將由SURF算法選擇的每個圖像塊分為N×N個單元，并使用水平 (1,0,1) 和垂直濾波器 ((1,0,1)T) 卷積計算每個點的梯度矢量，得到矢量的大小和方向。根據矢量的大小和方向，將每個梯度矢量添加到直方圖區域，該直方圖區域分為0°和180°之間的b個區段，則特征的維度為d=N2b。然后，本文使用主成分分析(principal component analysis，PCA)[13]和預先訓練好的PCA基礎降低所提特征的維度。

1.3 詞袋模型

詞袋模型使用余弦距離通過k均值聚類將HOG描述符的特征空間劃分為k個視覺詞。將每個描述符劃分到特征空間內與其最接近的質心。這樣，圖像可以由長度為k的二進制串表示，當且僅當第j個視覺單詞出現在圖像中時，第j位是1。

1.4 局部聚合的描述符(VLAD)

類似于詞袋模型，VLAD將每個特征劃分到特定單詞，詞袋模型只包含該單詞是否在圖像中出現的二進制信息，但VLAD同時存儲與位置有關單元的特征信息。如果可以在同一個單元格中找到多個特征，則VLAD將相對位置相加(或“聚合”)在一起。

具體來說，VLAD矢量v是子矢量v1，v2，…，vk的連接，每個子矢量代表一個特定的視覺單詞。對于任何i≤k，與質心ci相關的子矢量vi定義為

(1)

1.5 降維處理

由于VLAD描述符的大小是d×k，其中d是特征維數，k是詞袋模型中詞的數量，所以VLAD描述符會變得非常大。因此，需對VLAD描述符進行降維處理。本文使用基于局部敏感散列[14](local sensitive hash，LSH)的數據降低維數，將特征隨機投影到低維的二進制簽名，該過程通過二進制簽名之間的漢明距離近似保留原始向量之間的余弦相似度。

本文對每個單詞使用相同的隨機投影。這種簡化操作減少了存儲需求，但要求詞匯表中的單詞數量k必須小于一個因子B。投影平面的數量是p=B/k，每個描述符的維數為d。p平面P的值是從單位正態分布中隨機抽取的。對于VLAD描述符v，二進制簽名計算為

b=vTP≥0

(2)

其中，二進制簽名b的大小為k×p，b的總比特數是B。

1.6 圖像比較

本文通過計算二進制圖像簽名上的漢明距離實現圖像比較。如果使用包含k個單詞的BOW模型，則兩個簽名b1和b2的漢明距離為

(3)

(4)

漢明距離H在b1到b2之間的距離為每個子向量的漢明距離之和

(5)

視覺位置相對于當前位置的最佳匹配位置，可定義為具有最小二進制簽名的漢明距離所處的方位。

2 實驗結果與分析

所提系統在Matlab2014b上實現，使用matlab平臺內置的函數計算SURF關鍵點、PCA分解和HOG描述符。使用Yael庫實現BOW和VLAD模型。在商用筆記本電腦上使用英特爾i7-4810MQ CPU的單核進行時序比較。

實驗評估視覺位置識別系統對每個圖像存儲的信息量以及圖像處理計算時間進行比較。將所提VLAD系統也與其它特征識別方法進行比較，即BOW、SeqSLAM、FAB-MAP和全特征匹配。

2.1 實驗數據集

在5個公開的數據集上評估了可視位置識別系統，每個數據集包含兩個或更多不同條件下的場景。圖2給出了每個數據集的樣本圖像。Nordland數據集為不同季節從列車上得到的分辨率為640×360的圖像組成，如圖2(a)所示，實驗中使用了Nordland數據集的250幅圖像。Gardens Point數據集包含一條某大學校園的道路，路徑之間有側向視角變化，分為白天和黑夜獲取的圖片，如圖2(b)所示。白天獲得的圖像使用雙三次插值進行調整，生成分辨率為640×360的圖像。SFU Mountain數據集為一條森林小徑的圖像，如圖2(c)所示。該數據集包含239個在不同天氣條件下和不同時段得到的圖像。來自Mapillary圖像共享服務[15]的分辨率為640×480的圖像，包括汽車、自行車和巴士的頂部獲得的圖像，如圖2(d)和圖2(e)所示。數據集內的照明和天氣條件也有所不同。

圖2 實驗數據集的樣本圖像

2.2 實驗的訓練階段

所提系統對Nordland數據集的500張照片進行了訓練，從中提取了441 538個特征。這些訓練特征用于計算HOG描述符上初始降維的PCA基礎，并通過k-means聚類為詞袋生成詞匯模型。所有測試數據集都使用相同的PCA基礎和詞匯模型，以確保系統是廣泛通用的，且不需要對每個場景做特殊調整。

2.3 參數設置

實驗參數見表1。特征檢測算法和HOG描述符的參數保持不變，同時使用了特征尺寸、詞匯量和VLAD簽名長度的多個參數值，并給出了測試值的范圍。在大多實驗中，從每幅圖像中提取300個特征，除了評估檢測效率的實驗，其余實驗使用100和2000個特征。

表1 實驗參數

2.4 圖像簽名

特征識別系統的一個關鍵要求是存儲的描述符應該盡可能小，本文實驗主要研究位置識別的性能如何與每個圖像存儲的信息量有關。BOW、FAB-MAP和所提VLAD的性能如圖3所示，每個圖像使用相同數量的比特。

圖3 不同方法的正確匹配結果

對于大多數位長和數據集組合來說，本文VLAD的性能優于BOW和FAB-MAP。除了圖3(e)中使用16 384比特，FAB-MAP的正確匹配為43%，VLAD的正確匹配為39%。然而，在其它數據集中，VLAD的正確匹配比FAB-MAP高出10%。當每個圖像的位數很小時，BOW優于VLAD和FAB-MAP。但是，圖像存儲的位數增加時，BOW一直優于VAD和FAB-MAP的性能。

當圖像存儲比特增加時，BOW的性能并不總是提高，并且在4個數據集中，16 384比特的詞匯比256比特差(如圖3(a)、圖3(c)、圖3(d))。相關研究表明[16]，BOW模型中的單詞聚類必須足夠大才能夠捕獲由于外觀和視點變化引起的描述符變化，但不能太大，因為太大會導致太多不同的特征聚集在一起。因此，中等大小的單詞聚類較為合適。相比之下，VLAD的性能一直與圖像的位數有關。

最后比較了使用16 384位的VLAD與以未編碼形式存儲相同特征的版本性能。每個特征是1764個維度，每個圖像存儲300個特征，因此存儲的總字節數為1764×300×4字節或每個圖像大約2 MB的數據。結果顯示：未編碼特征的性能比Nordland(D-1數據集)數據集上的2048字節VLAD描述符大2.7倍。然而，對于每個全局特征圖像，大約有1000個位置可以存儲VLAD的16 384字節。根據系統要求，如果必須存儲大量圖像，可以使用更小的VLAD描述符。

2.5 計算時間

在理想的情況下，一個特征識別系統應該在計算效率和匹配方面均表現優秀。該過程可以分為兩個獨立的階段：圖像處理階段和圖像比較階段。

2.5.1 圖像處理

對于BOW以及完整的特性匹配，執行以下步驟：①在圖像中檢測關鍵點；②基于關鍵點提取描述符；③使用PCA減少描述符。對于VLAD模型，還需執行以下步驟：①每個描述符通過查找最近的相鄰集群質心匹配一個可視化的單詞；②計算每個描述符和集群質心之間的差異；③歸一化向量；④計算二進制簽名。

使用Nordland數據集(D-1)的29 000張圖像進行基準測試實驗。表2給出了16 384位BOW和本文VLAD的每幅圖像的平均處理時間。

表2 圖像處理時間

雖然需要額外的處理步驟，但VLAD的性能實際上比BOW更高。BOW模型使用更大的詞匯表，當特征分配給視覺詞時，最近的鄰近計算取決于聚類的數量。在這種情況下，與VLAD的128詞匯相比，BOW的大小為16 384的詞匯導致計算速度較慢，這比后續的VLAD處理花費的時間還長。

然而，計算時間是由特征提取過程決定的，并且這個過程主要取決于每個圖像提取的特征數量，如圖4所示，一個需要較少特征的系統，其效率一般會更高。

圖4 描述符的特征提取時間

總的來說，數量較多的特征并不一定能夠為BOW或VLAD提供更好的性能。此外，BOW對參數的選擇更加敏感。如果特征和詞群之間的關系發生了變化，那么對于詞匯的選擇，BOW的敏感度會非常大，對VLAD的影響較小。

2.5.2 圖像比較

BOW和VLAD的圖像比較非常相似，兩個系統都使用海明距離比較圖像。表3給出了使用Nordland數據集(D-1數據集)圖像進行10 000次圖像比較的平均時間。這兩種方法之間幾乎沒有時差。相比之下，直接特征匹配則要慢兩個數量級。

表3 圖像比較時間

雖然BOW和VLAD具有相似的計算時間，但BOW具有優勢，因為它比VLAD更稀疏，BOW簽名通常包含比VLAD簽名更多的零。在Nordland數據集中，每個BOW簽名的中位數為237，而VLAD的中位數為1216。這種稀疏性為其它更有效的比較方法應用于BOW提供了可能。但是，由于VLAD比BOW具有更好的特征識別性能，因此這種額外的效率是以犧牲整體性能為代價。

2.6 詞匯量的選擇

VLAD的一個重要參數是詞匯量的選擇。圖5給出了不同比特長度的圖像簽名在性能和詞匯大小之間的關系。在所有數據集上，表現最好的詞匯大小取決于簽名長度。當簽名長度很小時，較小的詞匯表現良好；對于每個數據集，只有8或16個字的詞匯表在64位簽名上表現最佳。如果使用大簽名，則較大的詞匯表現更好。但是，即使對于16 384位的簽名，最大的詞匯(4096個單詞)也會被較小的64或256個詞匯表超出。這些結果表明：小詞匯比較大詞匯更好，特別是非常緊湊的圖像簽名。

圖5 不同比特長度的圖像簽名在性能和詞匯大小間的關系

2.7 召回與精度的比較

另一個常用的評價系統性能的指標是精確和召回。召回和精確定義為

(6)

(7)

其中，TP為真正匹配的數目；FP是假匹配的數目；FN是假負匹配的數目。

圖6(a)是對D-1數據集進行了完全精確的召回率，圖6(b)給出了正確匹配的性能。精確的召回受到了比特數減少的嚴重影響，在2048位或更短的時間內，該數字快速下降甚至接近零。相比之下，較小圖像簽名正確匹配的百分比會較少，在2048位上保持在20%左右。當添加一個序列濾波器時，VLAD的表現如圖6(c)所示，由圖可知，對于1024位或更小的簽名來說，很難達到召回百分之百的精度。這個結果表明，在執行濾波操作時，對圖像簽名長度的完全恢復比找到正確的匹配更敏感。

圖6 本文VLAD在D-1數據集不同長度的表現

3 結束語

在位置識別中，即使外觀環境發生變化，識別系統也可以從不同的角度進行視覺識別。與其它視點不變和條件不變的位置識別系統不同，本文系統在存儲和計算方面都表現優秀。當存儲每個圖像256位時，性能降低緩慢，在所有數據集中正確匹配至少10%的位置，并且在每個圖像存儲64位時仍然在所有數據集中匹配5%正確的位置。VLAD的性能優于全特征匹配方法，且所需時間更短，相差約兩個數量級。由于VLAD保留的本地位置信息允許系統區分同一詞組中的不同特征，從而提高了性能并降低了對詞匯選擇的敏感度。