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

劉 靖

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

0 引 言

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

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

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

1 本文方法

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

圖1 本文方法的基本流程

1.1 特征檢測

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

1.2 特征描述

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

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

1.3 詞袋模型

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

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

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

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

(1)

1.5 降維處理

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

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

b=vTP≥0

(2)

其中，二進(jìn)制簽名b的大小為k×p，b的總比特數(shù)是B。

1.6 圖像比較

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

(3)

(4)

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

(5)

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

2 實驗結(jié)果與分析

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

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

2.1 實驗數(shù)據(jù)集

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

圖2 實驗數(shù)據(jù)集的樣本圖像

2.2 實驗的訓(xùn)練階段

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

2.3 參數(shù)設(shè)置

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

表1 實驗參數(shù)

2.4 圖像簽名

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

圖3 不同方法的正確匹配結(jié)果

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

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

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

2.5 計算時間

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

2.5.1 圖像處理

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

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

表2 圖像處理時間

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

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

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

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

2.5.2 圖像比較

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

表3 圖像比較時間

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

2.6 詞匯量的選擇

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

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

2.7 召回與精度的比較

另一個常用的評價系統(tǒng)性能的指標(biāo)是精確和召回。召回和精確定義為

(6)

(7)

其中，TP為真正匹配的數(shù)目；FP是假匹配的數(shù)目；FN是假負(fù)匹配的數(shù)目。

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

圖6 本文VLAD在D-1數(shù)據(jù)集不同長度的表現(xiàn)

3 結(jié)束語

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