劉 靖

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

0 引 言

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

很多位置識(shí)別的研究著重關(guān)注視點(diǎn)不變性、條件不變性及效率。如Mactavish等[3]提出了在同一視角下利用記憶功能進(jìn)行長時(shí)間的視覺定位方法。Liu等[4]設(shè)計(jì)了一種基于形狀匹配的視覺定位算法，算法在速度和精度兩個(gè)方面均達(dá)到與國外商業(yè)軟件相當(dāng)?shù)乃?，可部分替代商業(yè)軟件使用。Yan等[5]提出的“視覺-詞語”將特征空間量化成一組集群，由二進(jìn)制串描述圖像，將圖像簡化為二進(jìn)制串匹配，匹配效率高。在保持高效性能的同時(shí)，還可以通過局部聚合描述符(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)行視點(diǎn)及條件不變的位置識(shí)別，但這類方法計(jì)算代價(jià)非常大。

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

1 本文方法

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

圖1 本文方法的基本流程

1.1 特征檢測

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

1.2 特征描述

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

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

1.3 詞袋模型

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

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

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

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

(1)

1.5 降維處理

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

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

b=vTP≥0

(2)

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

1.6 圖像比較

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

(3)

(4)

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

(5)

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

2 實(shí)驗(yàn)結(jié)果與分析

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

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

2.1 實(shí)驗(yàn)數(shù)據(jù)集

在5個(gè)公開的數(shù)據(jù)集上評(píng)估了可視位置識(shí)別系統(tǒng)，每個(gè)數(shù)據(jù)集包含兩個(gè)或更多不同條件下的場景。圖2給出了每個(gè)數(shù)據(jù)集的樣本圖像。Nordland數(shù)據(jù)集為不同季節(jié)從列車上得到的分辨率為640×360的圖像組成，如圖2(a)所示，實(shí)驗(yàn)中使用了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個(gè)在不同天氣條件下和不同時(shí)段得到的圖像。來自Mapillary圖像共享服務(wù)[15]的分辨率為640×480的圖像，包括汽車、自行車和巴士的頂部獲得的圖像，如圖2(d)和圖2(e)所示。數(shù)據(jù)集內(nèi)的照明和天氣條件也有所不同。

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

2.2 實(shí)驗(yàn)的訓(xùn)練階段

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

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

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

表1 實(shí)驗(yàn)參數(shù)

2.4 圖像簽名

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

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

對(duì)于大多數(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)每個(gè)圖像的位數(shù)很小時(shí)，BOW優(yōu)于VLAD和FAB-MAP。但是，圖像存儲(chǔ)的位數(shù)增加時(shí)，BOW一直優(yōu)于VAD和FAB-MAP的性能。

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

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

2.5 計(jì)算時(shí)間

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

2.5.1 圖像處理

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

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

表2 圖像處理時(shí)間

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

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

圖4 描述符的特征提取時(shí)間

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

2.5.2 圖像比較

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

表3 圖像比較時(shí)間

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

2.6 詞匯量的選擇

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

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

2.7 召回與精度的比較

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

(6)

(7)

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

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

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

3 結(jié)束語

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