張運(yùn)超　陳靖　王涌天，

一種融合重力信息的快速海量圖像檢索方法

張運(yùn)超1陳靖2王涌天1，2

海量圖像檢索算法的核心問(wèn)題是如何對(duì)特征進(jìn)行有效的編碼以及快速的檢索.局部集聚向量描述（Vector of locally aggregated descriptors，VLAD）算法因其精確的編碼方式以及較低的特征維度，取得了良好的檢索性能.然而VLAD算法在編碼過(guò)程中并沒(méi)有考慮到局部特征的角度信息，VLAD編碼向量維度依然較高，無(wú)法支持實(shí)時(shí)的海量圖像檢索.本文提出一種在VLAD編碼框架中融合重力信息的角度編碼方法以及適用于海量圖像的角度乘積量化快速檢索方法.在特征編碼階段，利用前端移動(dòng)設(shè)備采集的重力信息實(shí)現(xiàn)融合特征角度的特征編碼方法.在最近鄰檢索階段將角度分區(qū)與乘積量化子分區(qū)相結(jié)合，采用改進(jìn)的角度乘積量化進(jìn)行快速近似最近鄰檢索.另外本文提出的基于角度編碼的圖像檢索算法可適用于主流的詞袋模型及其變種算法等框架.在GPS及重力信息標(biāo)注的北京地標(biāo)建筑（Beijing landmark）數(shù)據(jù)庫(kù)、Holidays數(shù)據(jù)庫(kù)以及SUN397數(shù)據(jù)庫(kù)中進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果表明本文算法能夠充分利用匹配特征在描述符以及幾何空間的相似性，相比傳統(tǒng)的VLAD以及協(xié)變局部集聚向量描述符（Covariant vector of locally aggregated descriptors，CVLAD）算法精度有明顯提升.

海量圖像檢索，重力信息，角度編碼，角度乘積量化

引用格式張運(yùn)超，陳靖，王涌天.一種融合重力信息的快速海量圖像檢索方法.自動(dòng)化學(xué)報(bào)，2016，42（10）:1501-1511

近年來(lái)，互聯(lián)網(wǎng)數(shù)據(jù)呈現(xiàn)爆炸式增長(zhǎng)，特別是每年新增的圖像數(shù)據(jù)以指數(shù)級(jí)發(fā)展，如何從海量圖像數(shù)據(jù)中快速檢索出目標(biāo)圖像成為重要的研究課題.經(jīng)典的海量圖像檢索技術(shù)主要包含兩部分：高效的圖像編碼技術(shù)以及快速的最近鄰搜索技術(shù).目前，國(guó)內(nèi)外眾多研究機(jī)構(gòu)已經(jīng)在海量圖像檢索相關(guān)領(lǐng)域取得了很多重要成果.

高效的編碼方式：面對(duì)海量的圖像數(shù)據(jù)，視覺(jué)編碼算法精度與效率的均衡是評(píng)價(jià)其性能的重要指標(biāo).詞袋模型［1］（Bag of words，BOW）、Fisher向量［2］（Fisher vector，F(xiàn)V）、稀疏編碼［3］（Sparse coding，SC）以及局部集聚向量描述［4］（Vector of locally aggregated descriptors，VLAD）等視覺(jué)編碼框架的提出旨在解決海量圖像檢索過(guò)程中精度與效率均衡的問(wèn)題.上述算法框架可用于百萬(wàn)量級(jí)規(guī)模的圖像檢索，其中VLAD編碼算法通過(guò)計(jì)算特征描述符與視覺(jué)單詞的殘差來(lái)表征圖像，具有良好的檢索精度及速度，特別適用于快速的海量圖像檢索應(yīng)用.本文主要結(jié)合VLAD編碼算法框架進(jìn)行大規(guī)模海量圖像檢索.

然而，傳統(tǒng)的VLAD編碼算法通過(guò)圖像特征描述符空間的相似性計(jì)算圖像相似度，忽略了圖像整體特征在幾何空間的相關(guān)特性.雖然文獻(xiàn)［5-6］提出了幾何全校驗(yàn)重排算法，利用了查詢樣本與候選樣本的空間位置約束信息進(jìn)行重排，但算法較為耗時(shí)，只能作用于少量檢索結(jié)果.然而，對(duì)于海量圖像數(shù)據(jù)，相關(guān)圖像可能并不在少量檢索結(jié)果中，該幾何重排算法精度難以滿足要求.弱幾何一致性校驗(yàn)［7］（Weak geometry consistency，WGC）的提出解決了幾何重排校驗(yàn)無(wú)法適用于海量圖像的問(wèn)題，該算法依據(jù)圖像整體尺度及角度變化一致的假定篩選特征點(diǎn)，通過(guò)直方圖統(tǒng)計(jì)加速計(jì)算，實(shí)現(xiàn)快速的幾何重排.除上述幾何重排序的研究工作外，研究人員也展開(kāi)對(duì)圖像編碼階段融合幾何信息的研究.文獻(xiàn)［8］中，作者沿用WGC幾何變化一致的假定，提出在特征集聚階段按照特征角度劃分分區(qū)，特征點(diǎn)分區(qū)集聚的方法協(xié)變局部集聚向量描述符（Covariant vector of locally aggregated descriptors，CVLAD）.然而由于圖像存在旋轉(zhuǎn)變化，該算法需要通過(guò)窮舉法估算查詢圖像與訓(xùn)練圖像的旋轉(zhuǎn)變化，進(jìn)而找到不同圖像角度分區(qū)的對(duì)應(yīng)關(guān)系，算法較為耗時(shí).文獻(xiàn)［9］采用單項(xiàng)嵌入方式在特征集聚階段將特征角度信息融入到圖像整體表征中，并以匹配核的形式重新解釋了角度信息對(duì)于圖像特征匹配的意義.文獻(xiàn)［10］利用圖像特征角度聚類的思想統(tǒng)一旋轉(zhuǎn)圖像的矢量表征，并采用極坐標(biāo)對(duì)特征角度進(jìn)行參數(shù)化表征，從而避免CVLAD中角度對(duì)應(yīng)關(guān)系的窮舉搜索計(jì)算.然而上述重排序、特征集聚階段結(jié)合幾何信息的工作，仍然采用傳統(tǒng)的K均值聚類算法訓(xùn)練視覺(jué)詞典，并未考慮幾何信息對(duì)視覺(jué)詞典的影響.因此，特征編碼階段孤立了特征描述符與特征幾何信息的關(guān)聯(lián)性，也即幾何信息沒(méi)有影響特征編碼方式.

除特征點(diǎn)的幾何信息外，移動(dòng)硬件傳感器數(shù)據(jù)的融合是近年來(lái)海量圖像檢索領(lǐng)域研究的另一熱點(diǎn).文獻(xiàn)［11］提出利用移動(dòng)設(shè)備內(nèi)置重力傳感器信息構(gòu)建重力對(duì)齊的特征描述符（Gravity aligned feature descriptors，GAFD）.GAFD算法利用重力方向作為特征點(diǎn)主方向，節(jié)約特征主方向計(jì)算時(shí)間，同時(shí)提升相似結(jié)構(gòu)特征的匹配性能.文獻(xiàn)［12］中作者將GAFD算法用于VLAD編碼框架，其檢索精度以及效率有明顯提升.然而GAFD是以忽略特征原始梯度主方向?yàn)榇鷥r(jià)換取檢索速度以及檢索精度的少量提升.特征點(diǎn)梯度主方向?qū)τ诤Ａ繄D像檢索也具有重要意義.

快速的最近鄰檢索：海量圖像檢索中，為提高檢索效率，通常采用主成分分析（Principle component analysis，PCA）降低圖像表達(dá)向量維度［13］.然而單純依靠PCA降維仍不能滿足百萬(wàn)量級(jí)圖像檢索對(duì)于速度的需求.近年來(lái)，國(guó)內(nèi)外研究人員相繼展開(kāi)對(duì)海量圖像最近鄰搜索問(wèn)題的研究.

當(dāng)前，主流的最近鄰搜索分為兩類.一類是線性搜索算法，算法需要逐次計(jì)算查詢向量到數(shù)據(jù)庫(kù)中每個(gè)向量的距離.代表算法是局部敏感哈希（Locality sensitive hashing，LSH）［14］，將向量進(jìn)行二值編碼，計(jì)算向量投影后的漢明距離.LSH主要依據(jù)是相似向量在哈希映射后仍以較高概率保持相似.隨后，一些改進(jìn)算法如譜哈希（Spectral hashing，SH）［15］等算法優(yōu)化了哈希函數(shù)，譜哈希通過(guò)設(shè)計(jì)高效的特征向量圖劃分方法實(shí)現(xiàn)特征點(diǎn)的最佳哈希編碼.另外文獻(xiàn)［16］則利用最新的深度學(xué)習(xí)方法學(xué)習(xí)緊湊的哈希函數(shù).相比LSH，該類算法主要利用了樣本的分布信息.另一類最近鄰搜索算法是非線性搜索方法，算法無(wú)需遍歷數(shù)據(jù)庫(kù)中的所有向量.該類算法的典型代表有K叉樹(shù)（K-dimensional tree，K-D tree）［17］以及快速近似最近鄰庫(kù)（Fast library for approximate nearest neighbors，F(xiàn)LANN）［18］.

乘積量化（Product quantization，PQ）［19］是近期提出的一種線性最近鄰搜索算法.與LSH等二值編碼方法不同，該算法計(jì)算的是向量原始空間的L2距離，通過(guò)對(duì)空間的分解優(yōu)化量化精度，成為當(dāng)前海量圖像檢索中一種有效的壓縮方式，它常用于對(duì)圖像表達(dá)向量PCA降維之后.乘積量化的目標(biāo)函數(shù)可表示為

1　算法設(shè)計(jì)及框架

融合重力信息的海量圖像檢索框架如圖1所示，離線階段，數(shù)據(jù)庫(kù)圖像根據(jù)重力信息以及特征角度信息進(jìn)行分區(qū)VLAD量化并在每個(gè)子分區(qū)構(gòu)建乘積量化子碼書(shū)；在線查詢階段，分區(qū)量化后的查詢子向量與數(shù)據(jù)庫(kù)子向量通過(guò)非對(duì)稱計(jì)算得到兩者的相似度度量，具體流程如下：

圖1　融合重力信息和特征角度信息的海量圖像檢索框架Fig.1　The framework of large-scale image retrieval based on a fusion of gravity aware orientation information

離線階段：

1）角度編碼：數(shù)據(jù)庫(kù)圖像根據(jù)重力信息以及特征角度進(jìn)行特征分區(qū)；

2）VLAD量化qc：對(duì)訓(xùn)練圖像角度子分區(qū)進(jìn)行碼書(shū)映射及殘差計(jì)算；

3）角度乘積量化qp：各角度分區(qū)VLAD子向量進(jìn)行PCA降維以及子碼書(shū)量化.

在線階段：

2）VLAD量化qc：對(duì)查詢圖像角度子分區(qū)進(jìn)行碼書(shū)映射及殘差計(jì)算；

3）PCA降維：各角度分區(qū)VLAD子向量降至同數(shù)據(jù)庫(kù)圖像相同維度；

4）非對(duì)稱計(jì)算：計(jì)算查詢子向量到訓(xùn)練圖像子向量對(duì)應(yīng)子碼書(shū)中心的距離：

5）選擇K 近鄰結(jié)果進(jìn)行真實(shí)歐氏距離重排序，排序后的結(jié)果即為檢索結(jié)果.

本文基于文獻(xiàn)［7-10］的工作基礎(chǔ)之上，將幾何信息用于視覺(jué)詞典的訓(xùn)練，在特征編碼階段，經(jīng)重力旋轉(zhuǎn)后具有相似角度的特征點(diǎn)被分區(qū)量化，獲得的圖像向量表達(dá)融合了特征點(diǎn)的描述符以及角度兩方面信息.角度乘積量化算法對(duì)每個(gè)角度子分區(qū)進(jìn)行單獨(dú)編碼量化，通過(guò)查詢子向量與角度分區(qū)子碼書(shū)的非對(duì)稱計(jì)算取代查詢向量與數(shù)據(jù)庫(kù)向量的直接距離計(jì)算，在保證查詢精度的前提下大大降低了計(jì)算量.

2　融合重力信息的角度編碼算法

假定圖像I提取n個(gè)尺度不變特征變換算法（Scale invariant feature transfarm，SIFT）［5］或者SURF（Speeded up robust features）［21］特征I=｛t1，t2，···，tn｝，每個(gè)特征包含描述符Des、特征角度β以及尺度信息s，即ti=（Des，β，s）. BOW、VLAD等傳統(tǒng)圖像編碼算法假定落在同一視覺(jué)單詞上描述符相似的特征即為匹配特征：

該假定忽略了每個(gè)特征點(diǎn)的上下文幾何信息，因此并不是一個(gè)充分條件.

文獻(xiàn)［7］指出，圖像整體的主方向旋轉(zhuǎn)以及特征尺度縮放是一致的，即相似圖像的匹配特征角度變化β1-β2=?β以及尺度縮放s1/s2=?s是定值，它們滿足數(shù)學(xué)上的線性相關(guān)性，角度以及尺度等幾何信息的利用有助于提高圖像匹配性能.將幾何信息用于BOW、FV、VLAD以及SC等傳統(tǒng)圖像編碼框架，匹配特征同時(shí)滿足描述符的相似性以及幾何信息的線性相關(guān)性，增加了特征編碼的準(zhǔn)確性.

重力傳感器已成為當(dāng)前移動(dòng)智能硬件的標(biāo)配，重力傳感器能夠記錄相機(jī)姿態(tài)的旋轉(zhuǎn).由于圖像旋轉(zhuǎn)變化的整體性，特征點(diǎn)主方向的旋轉(zhuǎn)變化?β也能夠通過(guò)重力傳感器測(cè)得［22］.因此，在詞典訓(xùn)練過(guò)程中可以充分利用匹配特征主方向的線性相關(guān)性.

在本節(jié)中，我們提出一種融合重力信息的角度編碼方法（Oriented coding）來(lái)訓(xùn)練具有幾何信息的視覺(jué)詞典，并將其應(yīng)用于VLAD檢索框架中.

2.1融合重力信息的角度編碼

本節(jié)主要介紹融合重力信息的角度編碼（Oriented coding）算法，該方法由重力自適應(yīng)的特征主方向計(jì)算以及角度量化兩部分構(gòu)成.

1）重力自適應(yīng)的特征主方向

圖2反映了在拍攝地標(biāo)建筑過(guò)程中可能發(fā)生的相機(jī)旋轉(zhuǎn).地標(biāo)建筑垂直方向始終與重力方向平行，因此可以通過(guò)圖像坐標(biāo)系中重力方向的變化估算地標(biāo)建筑的旋轉(zhuǎn).圖2（a）中重力方向垂直向下，設(shè)此為基準(zhǔn)位置，圖2（b）中重力方向相較于圖像坐標(biāo)軸的旋轉(zhuǎn)角度θ可由重力傳感器信息Gi測(cè)得，需要特別注意的是圖像坐標(biāo)系與重力坐標(biāo)系三軸相平行，但其X軸與Y軸坐標(biāo)剛相反，即重力Y軸為圖像坐標(biāo)X軸.

圖2　不同拍攝角度的地標(biāo)建筑及對(duì)應(yīng)重力信息Fig.2　The landmark building with different viewing angles and corresponding gravity information

若圖 2（b）中重力傳感器信息為 Gi=［gx（i），gy（i），gz（i）］，則此時(shí)地標(biāo)建筑旋轉(zhuǎn)角度：

將地標(biāo)建筑旋轉(zhuǎn)θ，即旋轉(zhuǎn)至與圖像坐標(biāo)軸平行位置，所得圖像同圖2（a）相似.由于圖像特征旋轉(zhuǎn)的整體性，則特征主方向β的旋轉(zhuǎn)為β+θ.經(jīng)重力信息旋轉(zhuǎn)后，兩張圖像對(duì)應(yīng)的匹配特征（t1，t2）角度之間的相互關(guān)系可以表示為

θ（t1）與θ（t2）分別是（t1，t2）所在圖像的重力方向旋轉(zhuǎn)角度.如果不考慮重力計(jì)算旋轉(zhuǎn)角的誤差，則重力旋轉(zhuǎn)后相似圖像匹配特征具有相同的主方向.

2）角度量化考慮到重力傳感器精度以及匹配特征的角度計(jì)算誤差，本文將旋轉(zhuǎn)后的主方向映射至B個(gè)分區(qū)，并建立特征描述符到角度分區(qū)的分區(qū)索引，O是映射后的分區(qū)索引：

通過(guò)角度分區(qū)映射，在特征編碼階段，角度相關(guān)的特征點(diǎn)落入相同分區(qū)中.如圖3所示，經(jīng)過(guò)重力信息旋轉(zhuǎn)后，相似圖像的主方向角度分布直方圖具有高度相似性.本文在編碼過(guò)程中綜合利用了匹配特征描述符的相似性以及特征主方向的相關(guān)性，訓(xùn)練的視覺(jué)詞典在幾何空間以及描述符空間具有雙重區(qū)分力.

圖3　相似圖像的主方向角度分布直方圖Fig.3　The histogram of angle distribution on similar images

相比較CVLAD等算法將角度信息用在特征集聚階段，文中提出的算法在保持相同維度情況下將角度信息融入到視覺(jué)單詞中，增加了視覺(jué)單詞的區(qū)分度，本文將在后續(xù)實(shí)驗(yàn)中驗(yàn)證該算法有效性.

2.2基于VLAD算法框架的角度編碼

下面將上節(jié)提出的Oriented coding方法應(yīng)用于VLAD檢索算法框架中.不失一般性，本文以文獻(xiàn)［4］提出的VLAD算法為例介紹編碼過(guò)程，這里沒(méi)有采用軟量化策略［23］，因此編碼主要包含兩部分：角度編碼OC（t）=j，j=1，···，B以及最近鄰視覺(jué)單詞查找其中t為輸入特征，B，K分別為角度分區(qū)數(shù)及視覺(jué)單詞數(shù)代表主方向映射為第j角度分區(qū)的視覺(jué)詞典，cj，k是中第k視覺(jué)單詞.是落在視覺(jué)單詞cj，k上的所有特征的集聚殘差向量和，也即為圖像向量表達(dá)x的第j角度分區(qū)中第k子向量：

通過(guò)在特征編碼過(guò)程中融合特征幾何信息，算法充分利用了匹配特征在描述符以及幾何空間的相關(guān)性，并且有助于消除Burstiness［24］現(xiàn)象帶來(lái)的負(fù)面影響.

3　基于角度乘積量化的最近鄰檢索

圖像向量表達(dá)維度與海量圖像檢索速度直接相關(guān).海量圖像在線檢索時(shí)間主要消耗在特征編碼以及最近鄰檢索階段.假定數(shù)據(jù)庫(kù)包含N張圖像，特征描述維度為d，VLAD編碼視覺(jué)單詞個(gè)數(shù)為K，角度分區(qū)數(shù)為B，則VLAD、CVLAD以及本文提出的Oriented coding算法特征編碼時(shí)間幾乎相同，而最近鄰檢索時(shí)間分別為O（N×K×d）、O（N×B× B×K×d）以及O（N×B×K×d）.

海量圖像檢索中，圖像數(shù)目N可達(dá)百萬(wàn)量級(jí)以上，即使通過(guò)PCA將圖像整體表征矢量降至D維，最近鄰檢索時(shí)間復(fù)雜度由O（N×B×K×d）降至O（N×D），速度也通常難以滿足快速查詢的需求.因此，本文在傳統(tǒng)PCA降維基礎(chǔ)上提出基于角度分區(qū)的乘積量化方法對(duì)檢索向量進(jìn)一步壓縮.首先，通過(guò)角度編碼算法將圖像向量表達(dá)分解成若干個(gè)子分區(qū)，將每個(gè)子分區(qū)進(jìn)行PCA降維；然后，在每個(gè)分解子分區(qū)上進(jìn)行K均值聚類生成子碼書(shū)量化器，構(gòu)建角度乘積量化方法.該方法采用角度子分區(qū)作為乘積量化子分區(qū)，在不額外引入投影矩陣的情況下解決了特征值分布不均的問(wèn)題.

離線數(shù)據(jù)庫(kù)構(gòu)建階段，首先對(duì)角度子分區(qū)進(jìn)行PCA降維：

然后對(duì)降維后的子分區(qū)分別進(jìn)行K均值聚類，構(gòu)建B個(gè)子分區(qū)碼書(shū)Cpj，j=1，···，B.每個(gè)子分區(qū)碼書(shū)包含k?個(gè)視覺(jué)單詞總共B×k?個(gè)子碼書(shū)，分區(qū)子碼書(shū)之間采用笛卡爾積形式組合，構(gòu)成（k?）B個(gè)大碼書(shū).最后對(duì)數(shù)據(jù)庫(kù)向量進(jìn)行分區(qū)編碼，qpj為第j分區(qū)量化器，量化結(jié)果為子碼書(shū)中心索引標(biāo)號(hào)：

在線查詢階段，首先將查詢子向量進(jìn)行PCA降維，并計(jì)算與所在子分區(qū)每個(gè)碼書(shū)中心的歐氏距離，生成B×k?查找表：

然后針對(duì)每一數(shù)據(jù)庫(kù)向量，根據(jù)離線存儲(chǔ)的子碼書(shū)中心映射索引標(biāo)號(hào)qpj（yi，j）在B×k?查找表中尋找非對(duì)稱距離：

根據(jù)非對(duì)稱計(jì)算返回Top K的最近鄰距離并進(jìn)行歐氏距離重排，最后輸出結(jié)果即為檢索結(jié)果.

算法流程如下：

算法1.角度乘積量化

輸入.數(shù)據(jù)庫(kù)向量以及查詢向量.

輸出.查詢向量的K最近鄰.

步驟1.PCA降維后的數(shù)據(jù)庫(kù)向量子分區(qū)分別進(jìn)行K均值聚類構(gòu)建子分區(qū)碼書(shū)，并進(jìn)行分區(qū)編碼；

步驟2.查詢子向量PCA降維，并依次計(jì)算與子分區(qū)碼書(shū)中心的距離，形成B×k?查找表；

步驟3.通過(guò)查找表以及數(shù)據(jù)庫(kù)子向量的碼書(shū)映射情況計(jì)算非對(duì)稱距離；

步驟4.返回Top K的最近鄰距離進(jìn)行歐氏距離重排.

若PCA降維后圖像整體表征矢量為D維，則其線性搜索時(shí)間復(fù)雜度為O（N×D），而文中提出的角度乘積量化算法的時(shí)間復(fù)雜度為O（N×B+k?×D），其中k?為子分區(qū)量化器大小，一般k??N，因此角度乘積量化算法大大降低了圖像在線查詢時(shí)間.

4　實(shí)驗(yàn)結(jié)果及分析

4.1測(cè)試數(shù)據(jù)庫(kù)

為驗(yàn)證文中提出的Oriented coding方法以及Oriented PQ方法，本文在自己構(gòu)建的北京地標(biāo)建筑（Beijing landmark）圖像數(shù)據(jù)庫(kù)、Holidays數(shù)據(jù)庫(kù)［4］以及SUN397數(shù)據(jù)庫(kù)［25］中進(jìn)行測(cè)試.Beijing landmark由課題組使用智能手機(jī)在北京周邊搜集構(gòu)建.圖像采用自己編寫(xiě)的Android平臺(tái)拍照應(yīng)用程序搜集，在拍照的同時(shí)記錄GPS以及重力傳感器信息.該圖像數(shù)據(jù)庫(kù)總共包含4000張地標(biāo)圖像，每5張圖像為一個(gè)地標(biāo)建筑，分別包含尺度、視角以及旋轉(zhuǎn)等不同變化.數(shù)據(jù)庫(kù)中的部分圖片如圖4所示. Beijing landmark提供公開(kāi)下載，可供后續(xù)測(cè)試研究（http：//pan.baidu.com/s/1c04gdlI）.由于每個(gè)場(chǎng)景圖像數(shù)目相同，本文選擇與Zurich以及UKB等標(biāo)準(zhǔn)圖像庫(kù)相類似的評(píng)價(jià)標(biāo)準(zhǔn)，取檢索到前5張圖像中相關(guān)圖像數(shù)目的平均值作為圖像檢索精度的評(píng)價(jià)標(biāo)準(zhǔn)，即為Recall＠Top5.Holidays數(shù)據(jù)庫(kù)［4］包含1491張數(shù)據(jù)庫(kù)圖像以及500張查詢圖片.本文將圖像降采樣至最大786432像素，采用mAP作為衡量檢索精度的標(biāo)準(zhǔn).考慮到無(wú)法獲取Holidays數(shù)據(jù)庫(kù)的重力信息，與文獻(xiàn)［10］相類似，本文實(shí)驗(yàn)將Holidays數(shù)據(jù)庫(kù)圖像做人工旋轉(zhuǎn)校正.SUN397包含130519張各類建筑圖像，本文隨機(jī)選擇其中96000張圖像賦以隨機(jī)重力信息作為干擾圖像，同Beijing landmark相混合成100KB大小數(shù)據(jù)庫(kù)，作為海量檢索圖像數(shù)據(jù)庫(kù).

圖4　重力信息標(biāo)注的北京地標(biāo)建筑數(shù)據(jù)庫(kù)Fig.4　Beijing landmarks of gravity information tagging database

4.2參數(shù)設(shè)定

本文實(shí)驗(yàn)主要測(cè)試文中提出的融合重力信息的Oriented coding方法以及Oriented PQ方法對(duì)于海量圖像檢索性能的影響.考慮到移動(dòng)端的計(jì)算性能以及快速查詢要求，文中采用d=64維SURF特征作為主要特征提取算法，K均值聚類方法作為描述符聚類的主要方法.其中K均值聚類的聚類中心個(gè)數(shù)設(shè)定為K，特征點(diǎn)進(jìn)行角度映射的分區(qū)數(shù)目設(shè)置為B.文中將在第4.3節(jié)重點(diǎn)討論這些參數(shù)對(duì)于檢索性能的影響.

4.3檢索性能

本節(jié)主要測(cè)試融合重力信息的Oriented coding方法對(duì)于海量圖像檢索精度的影響，并與VLAD算法［4］，改進(jìn)的VLAD+算法［26］以及CVLAD［8］進(jìn)行性能對(duì)比.測(cè)試數(shù)據(jù)庫(kù)為Beijing landmark數(shù)據(jù)庫(kù)以及Holidays數(shù)據(jù)庫(kù).

圖 5所示為 Beijing landmark數(shù)據(jù)庫(kù)下VLAD、VLAD+、CVLAD以及Oriented coding方法檢索精度對(duì)比.可以看出，在角度分區(qū)B=4，6，8的情況下，文中提出的Oriented coding方法均比VLAD、VLAD+以及CVLAD有較大的精度提升.其中CVLAD檢索精度隨分區(qū)數(shù)目增長(zhǎng)而提高，這是由于隨著角度分區(qū)數(shù)目的增加，CVLAD的窮舉搜索算法能夠更準(zhǔn)確地預(yù)估圖像旋轉(zhuǎn)變化，因此其檢索精度隨之提高.但是，這同樣帶來(lái)了內(nèi)存以及速度的犧牲.

與CVLAD不同，圖5中Oriented coding方法檢索精度B=6＞8＞4，圖6具體給出K=16情況下Oriented coding方法隨角度分區(qū)數(shù)目B變化的檢索精度變化曲線，其中B=1代表不分區(qū)，即傳統(tǒng)VLAD方法.可以看出，Oriented coding方法在分區(qū)數(shù)目達(dá)到B=6后，檢索精度開(kāi)始有所下降，這是由于本文采用重力傳感器XY軸計(jì)算圖像旋轉(zhuǎn)角度，對(duì)圖像拍攝時(shí)俯仰變化比較敏感.過(guò)細(xì)角度分區(qū)劃分會(huì)影響到俯仰角較大拍攝圖像的特征角度分區(qū)，容易出現(xiàn)錯(cuò)分現(xiàn)象，導(dǎo)致檢索精度下降.因此后續(xù)實(shí)驗(yàn)中，無(wú)特別說(shuō)明，角度分區(qū)數(shù)目主要設(shè)置為B=6進(jìn)行實(shí)驗(yàn).

圖5　不同編碼方法檢索精度對(duì)比Fig.5　Comparison of retrieval accuracy with different coding method

圖6　Oriented coding檢索精度與分區(qū)數(shù)目關(guān)系Fig.6　The relationship of oriented coding retrieval accuracy and partition number

考慮到本文 Orientedcoding方法相比VLAD、VLAD+以及CVLAD多利用了圖像的重力信息，為公平對(duì)比，本文將重力信息賦予CVLAD算法，即假定CVLAD也通過(guò)重力獲取旋轉(zhuǎn)角，將特征角度用于特征集聚階段，無(wú)需窮舉搜索計(jì)算圖像旋轉(zhuǎn)角度.本文將CVLAD的重力版本定義為gCVLAD.Oriented coding與gCVLAD方法對(duì)比結(jié)果如圖7.可以看出本文的方法在相同角度分區(qū)數(shù)目情況下均優(yōu)于gCVLAD方法，gCVLAD與Oriented coding相同的是，B=6檢索精度最高.

圖7　Oriented coding與重力版本CVLAD方法檢索精度對(duì)比Fig.7　Comparison of retrieval accuracy with oriented coding and gCVLAD

由于重力信息存在計(jì)算誤差，下面分別在Rotated Holidays數(shù)據(jù)庫(kù)以及原始Holidays數(shù)據(jù)庫(kù)中進(jìn)行對(duì)比測(cè)試，這里僅考慮角度編碼影響，剔除重力信息影響.實(shí)驗(yàn)中碼書(shū)大小設(shè)置為變化的K，CVLAD以及Oriented coding中角度分區(qū)數(shù)目B=6.在Rotated Holidays數(shù)據(jù)庫(kù)測(cè)試中，由于校正數(shù)據(jù)庫(kù)中相似圖像匹配特征主方向相同，CVLAD方法無(wú)需窮舉搜索圖像主方向變化.

表1所示為Holidays數(shù)據(jù)庫(kù)下各方法檢索精度對(duì)比.可以看出，CVLAD以及Oriented coding方法在校正圖像數(shù)據(jù)庫(kù)下均具有良好的檢索結(jié)果，其中本文提出的Oriented coding方法優(yōu)于CVLAD，而VLAD以及VLAD+提升不大，這驗(yàn)證了正確的角度編碼對(duì)于檢索精度提升的效果.同時(shí)，CVLAD和Oriented coding相比無(wú)幾何信息的VLAD和VLAD+，隨著碼書(shū)大小K的增加，檢索精度的提升相對(duì)較小.

在時(shí)間消耗方面，CVLAD采用窮舉遍歷法計(jì)算圖像的旋轉(zhuǎn)，時(shí)間代價(jià)為O（N×B×B×K×d）.而本文的融合重力信息的Oriented coding方法僅需O（N×B×K×d）時(shí)間復(fù)雜度，在B=6的情況下時(shí)間節(jié)約接近80%.

表1　Holidays數(shù)據(jù)庫(kù)檢索精度（mAP）Table 1　The retrieval accuracy of Holidays dataset（mAP）

4.4特征降維

為保證算法性能對(duì)比的公平性，本實(shí)驗(yàn)在VLAD、VLAD+、CVLAD以及本文提出的Oriented coding等方法編碼后采用PCA降低到相同維度，然后進(jìn)行檢索精度對(duì)比.假定上述編碼算法采用的特征描述維度為d，編碼視覺(jué)單詞個(gè)數(shù)為K，角度分區(qū)數(shù)為B，則VLAD以及VLAD+圖像表達(dá)向量維度為K×d，CVLAD以及文中提出的Oriented coding向量維度為B×K×d.本實(shí)驗(yàn)對(duì)上述編碼方法通過(guò)PCA將維度降低至同一維度，比較其檢索精度.圖8為分區(qū)數(shù)目B=6，詞典數(shù)目K=16情況下各算法的檢索精度比較.實(shí)驗(yàn)結(jié)果表明，文中提出的結(jié)合重力以及幾何信息的Oriented coding編碼算法在相同維度下有較大精度優(yōu)勢(shì).而CVLAD在相同維度下相比VLAD+并沒(méi)有明顯的精度優(yōu)勢(shì).另外上述檢索算法隨著維度增加到一定程度，檢索精度并未繼續(xù)增長(zhǎng)，甚至部分情況下會(huì)發(fā)生精度下降的情況.

圖8　PCA降維后Oriented coding檢索算法精度Fig.8　The retrieval accuracy of oriented coding after PCA

4.5基于角度乘積量化的海量圖像檢索方法

本節(jié)主要測(cè)試文中提出的Oriented coding最近鄰搜索算法的性能，并將Oriented PQ與Oriented coding相結(jié)合，應(yīng)用于海量圖像檢索中.測(cè)試數(shù)據(jù)庫(kù)由SUN397與Beijing landmark混合構(gòu)成，數(shù)據(jù)庫(kù)大小為100KB.PCA降維后圖像向量表達(dá)維度D=128，乘積量化子分區(qū)數(shù)B=8，子分區(qū)聚類詞典數(shù)目k?=256.

如圖9所示，文中提出的Oriented PQ方法相比傳統(tǒng)的PQ能夠提升一定的檢索精度，在100KB數(shù)據(jù)庫(kù)中，檢索精度提升3%以上，并且檢索精度更加接近直接線性查找算法，誤差在1%以內(nèi).

圖9　海量圖像最近鄰檢索方法精度對(duì)比Fig.9　Comparison of retrieval accuracy with different ANN methods

表2所示為海量檢索過(guò)程中的時(shí)間開(kāi)銷.從表2可見(jiàn)，PQ方法相比PCA降維有較大的檢索速度提升.但在較小的10KB數(shù)據(jù)庫(kù)中，由于子分區(qū)中心距離的計(jì)算將消耗一定時(shí)間O（k?×D），PQ速度提升并不明顯.而子分區(qū)距離中心計(jì)算時(shí)間不隨圖像數(shù)目發(fā)生變化，在100KB數(shù)據(jù)庫(kù)中，影響檢索速度的主要因素是特征維度以及圖片數(shù)目，此時(shí)O（N×B+k?×D）＜O（N×D），隨著圖片數(shù)目的遞增，文中提出的檢索算法時(shí)間消耗接近于PCA降維的B/D.由于影響PQ速度的關(guān)鍵因素子分區(qū)數(shù)目相同，文中提出的Oriented PQ方法與PQ有較為接近的檢索速度.

4.6與其他檢索算法框架相結(jié)合

稀疏編碼是另外一種比較主流的圖像檢索算法［27-29］，其檢索精度與VLAD算法相當(dāng)，因此，本實(shí)驗(yàn)測(cè)試Oriented coding算法與稀疏編碼框架結(jié)合的檢索精度，實(shí)驗(yàn)結(jié)果如圖10所示，其中“B bins SC with max pooling”代表角度分區(qū)數(shù)目為B的稀疏編碼方法，每個(gè)分區(qū)取稀疏系數(shù)的最大值，B=1時(shí)即為傳統(tǒng)的稀疏編碼方法.實(shí)驗(yàn)結(jié)果表明，Oriented coding方法應(yīng)用于稀疏編碼同樣能夠提升檢索精度.然而稀疏編碼特征編碼階段較為耗時(shí)，當(dāng)前還無(wú)法應(yīng)用于實(shí)時(shí)性要求較高的移動(dòng)視覺(jué)檢索系統(tǒng).

表2　海量檢索時(shí)間消耗（ms）Table 2　Time consuming of image retrieval（ms）

圖10　基于稀疏編碼框架的Oriented coding方法檢索精度Fig.10　The retrieval accuracy of oriented coding based on sparse coding framework

5　總結(jié)和展望

本文研究了海量圖像檢索過(guò)程中利用重力傳感器以及特征點(diǎn)角度信息的問(wèn)題，提出了一種融合重力信息的Oriented coding以及Oriented PQ快速檢索算法.本文搜集了GPS以及重力信息標(biāo)注的Beijing landmark圖像數(shù)據(jù)庫(kù)，可用于后續(xù)算法研究.文中提出的融合重力信息的Oriented coding算法綜合利用了匹配特征在描述符空間以及幾何空間的相關(guān)性，Oriented PQ算法在100KB圖像檢索中保持較高的檢索速度及精度.同時(shí)本文提出的Oriented coding算法還存在一些問(wèn)題，例如不同角度之間視覺(jué)單詞的相關(guān)性如何消除，特征尺度信息如何利用，這些問(wèn)題的研究有助于進(jìn)一步降低圖像表達(dá)向量維度，本文會(huì)在后續(xù)研究中繼續(xù)深入探索這些問(wèn)題.

References

1 Sivic J，Zisserman A.Video Google:a text retrieval approach to object matching in videos.In:Proceedings of the 9th IEEE International Conference on Computer Vision. Nice，F(xiàn)rance:IEEE，2003.1470-1477

3 Ge T Z，Ke Q F，Sun J.Sparse-coded features for image retrieval.In:Proceedings of the 24th British Machine Vision Conference.British:British Machine Vision，2013.1-8

5 Lowe D G.Distinctive image features from scale-invariant keypoints.International Journal of Computer Vision，2004，60（2）:91-110

6 Chum O，Philbin J，Sivic J，Isard M，Zisserman A.Total recall:automatic query expansion with a generative feature model for object retrieval.In:Proceedings of the 11th IEEE International Conference on Computer Vision.Rio de Janeiro，Brazil:IEEE，2007.1-8

7 Jegou H，Douze M，Schmid C.Hamming embedding and weak geometric consistency for large scale image search.In: Proceedings of the 10th European Conference on Computer Vision.Berlin，Heidelberg:Springer，2008.304-317

10 Wang Z X，Di W，Bhardwaj A，Jagadeesh V，Piramuthu R.Geometric VLAD for large scale image search.In:Proceedings of the 31th International Conference on Machine Learning.Beijing，China，2014.134-141

11 Kurz D，Ben H S.Inertial sensor-aligned visual feature descriptors.In:Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition.Providence，RI，USA:IEEE，2011.161-166

12 Guan T，He Y F，Gao J，Yang J Z，Yu J Q.On-device mobile visual location recognition by integrating vision and inertial sensors.IEEE Transactions on Multimedia，2013，15（7）:1688-1699

15 Weiss Y，Torralba A，F(xiàn)ergus R.Spectral hashing.In:Proceedings of Advances in Neural Information Processing Systems.USA:MIT Press，2009.1753-1760

16 Zhang R M，Lin L，Zhang R，Zuo W M，Zhang L.Bitscalable deep hashing with regularized similarity learning for image retrieval and person re-identification.IEEE Transactions on Image Processing，2015，24（12）:4766-4779

17 Bentley J L.Multidimensional binary search trees used for associative searching.Communications of the ACM，1975，18（9）:509-517

18 Muja M，Lowe D G.Fast approximate nearest neighbors with automatic algorithm configuration.In:Proceedings of the 2009 International Joint Conference on Computer Vision，Imaging and Computer Graphics Theory and Applications.Lisboa，Portugal:Thomson Reuters，2009.331-340

19 Jegou H，Douze M，Schmid C.Product quantization for nearest neighbor search.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（1）:117-128

20 Ge T，He K，Ke Q，Sun J.Optimized product quantization for approximate nearest neighbor search.In:Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition.Portland，OR，USA:IEEE，2013.2946-2953

21 Bay H，Tuytelaars T，Van Gool L.Surf:speeded up robust features.In:Proceedings of the 9th European Conference on Computer Vision.Graz，Austria:Springer，2006.404-417

22 Gui Zhen-Wen，Wu Ting，Peng Xin.A novel recognition approach for mobile image fusing inertial sensors.Acta Automatica Sinica，2015，41（8）:1394-1404（桂振文，吳亻廷，彭欣.一種融合多傳感器信息的移動(dòng)圖像識(shí)別方法.自動(dòng)化學(xué)報(bào)，2015，41（8）:1394-1404）

23 He Yu-Feng，Zhou Ling，Yu Jun-Qing，Xu Tao，Guan Tao. Image retrieval based on locally features aggregating.Chinese Journal of Computers，2011，34（11）:2224-2233（何云峰，周玲，于俊清，徐濤，管濤.基于局部特征聚合的圖像檢索方法.計(jì)算機(jī)學(xué)報(bào)，2011，34（11）:2224-2233）

24 Jegou H，Douze M，Schmid C.On the burstiness of visual elements.In:Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition.Miami，F(xiàn)L，USA:IEEE，2009.1169-1176

25 Xiao J，Hays J，Ehinger K A，Oliva A，Torralba A.Sun database:large-scale scene recognition from abbey to zoo. In:Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition.San Francisco，CA，USA: IEEE，2010.3485-3492

26 Arandjelovic R，Zisserman A.All about VLAD.In:Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition.Portland，OR，USA:IEEE，2013. 1578-1585

27 Tang Hong-Zhong，Zhang Xiao-Gang，Chen Hua，Cheng Wei，Tang Mei-Ling.Incoherent dictionary learning method with border condition constrained for sparse representation. Acta Automatica Sinica，2015，41（2）:312-319（湯紅忠，張小剛，陳華，程煒，唐美玲.帶邊界條件約束的非相干字典學(xué)習(xí)方法及其稀疏表示.自動(dòng)化學(xué)報(bào)，2015，41（2）:312-319）

28 Liu Pei-Na，Liu Guo-Jun，Guo Mao-Zu，Liu Yang，Li Pan.Image classification based on non-negative localityconstrained linear coding.Acta Automatica Sinica，2015，41（7）:1235-1243（劉培娜，劉國(guó)軍，郭茂祖，劉揚(yáng)，李盼.非負(fù)局部約束線性編碼圖像分類算法.自動(dòng)化學(xué)報(bào)，2015，41（7）:1235-1243）

29 Ren Yue-Mei，Zhang Yan-Ning，Li Ying.Advances and perspective on compressed sensing and application on image processing.Acta Automatica Sinica，2014，40（8）: 1563-1575（任越美，張艷寧，李映.壓縮感知及其圖像處理應(yīng)用研究進(jìn)展與展望.自動(dòng)化學(xué)報(bào)，2014，40（8）:1563-1575）

張運(yùn)超北京理工大學(xué)計(jì)算機(jī)學(xué)院博士研究生.主要研究方向?yàn)樵鰪?qiáng)現(xiàn)實(shí)與虛擬現(xiàn)實(shí).

E-mail:zhangyunchao163@163.com

（ZHANG Yun-ChaoPh.D.candidate at the School of Computer Science and Technology，Beijing Institute of Technology.His research interest covers augmented reality and virtual reality.）

陳 靖北京理工大學(xué)副研究員.主要研究方向?yàn)樵鰪?qiáng)現(xiàn)實(shí)與虛擬現(xiàn)實(shí)，計(jì)算機(jī)視覺(jué).本文通信作者.

E-mail:chen74jing29@bit.edu.cn

（CHEN JingPh.D.，associate professor at Beijing Institude of Technology.Her research interest covers augmented reality and virtual reality，and computer vision.Corresponding author of this paper.）

王涌天北京理工大學(xué)教授.主要研究方向?yàn)樾滦?D顯示，虛擬現(xiàn)實(shí)，增強(qiáng)現(xiàn)實(shí)技術(shù).

E-mail:wyt@bit.edu.cn

（WANGYong-TianProfessorat Beijing Institude of Technology.His research interest covers new 3D display，virtual reality，and augmented reality.）

Large-scale Image Retrieval Based on a Fusion of Gravity Aware Orientation Information

ZHANG Yun-Chao1CHEN Jing2WANG Yong-Tian1，2

Large scale image retrieval has focused on effective feature coding and efficient searching.Vector of locally aggregated descriptors（VLAD）has achieved great retrieval performance as with its exact coding method and relatively low dimension.However，orientation information of features is ignored in coding step and feature dimension is not suitable for large scale image retrieval.In this paper，a gravity-aware oriented coding and oriented product quantization method based on traditional VLAD framework is proposed，which is efficient and effective.In feature coding step，gravity sensors built-in the mobile devices can be used for feature coding as with orientation information.In vector indexing step，oriented product quantization which combines orientation bins and product quantization bins is used for approximate nearest neighborhood search.Our method can be adapted to any popular retrieval frameworks，including bag-of-words and its variants.Experimental results on collected GPS and gravity-tagged Beijing landmark dataset，Holidays dataset and SUN397 dataset demonstrate that the approach can make full use of the similarity of matching pairs in descriptor space as well as in geometric space and improve the mobile visual search accuracy a lot when compared with VLAD and CVLAD.

Large scale image retrieval，gravity information，oriented coding，oriented product quantization

Manuscript September 2，2015；accepted February 27，2016

10.16383/j.aas.2016.c150556

Zhang Yun-Chao，Chen Jing，Wang Yong-Tian.Large-scale image retrieval based on a fusion of gravity aware orientation information.Acta Automatica Sinica，2016，42（10）:1501-1511

2015-09-02錄用日期2016-02-27

國(guó)家高技術(shù)研究發(fā)展計(jì)劃（863計(jì)劃）（2013AA013802），國(guó)家自然科學(xué)基金（61271375）資助

Supported by National High Technology Research and Development Program of China（863 Program）（2013AA013802）and National Natural Science Foundation of China（61271375）

本文責(zé)任編委賴劍煌

Recommended by Associate Editor LAI Jian-Huang

1.北京理工大學(xué)計(jì)算機(jī)學(xué)院 北京1000812.北京理工大學(xué)光電學(xué)院北京100081

1.School of Computer Science and Technology，Beijing Institute of Technology，Beijing 1000812.School of Optics and Electronics，Beijing Institute of Technology，Beijing 100081