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

張運超　陳靖　王涌天，

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

張運超1陳靖2王涌天1，2

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

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

引用格式張運超，陳靖，王涌天.一種融合重力信息的快速海量圖像檢索方法.自動化學報，2016，42（10）:1501-1511

近年來，互聯網數據呈現爆炸式增長，特別是每年新增的圖像數據以指數級發展，如何從海量圖像數據中快速檢索出目標圖像成為重要的研究課題.經典的海量圖像檢索技術主要包含兩部分：高效的圖像編碼技術以及快速的最近鄰搜索技術.目前，國內外眾多研究機構已經在海量圖像檢索相關領域取得了很多重要成果.

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

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

除特征點的幾何信息外，移動硬件傳感器數據的融合是近年來海量圖像檢索領域研究的另一熱點.文獻［11］提出利用移動設備內置重力傳感器信息構建重力對齊的特征描述符（Gravity aligned feature descriptors，GAFD）.GAFD算法利用重力方向作為特征點主方向，節約特征主方向計算時間，同時提升相似結構特征的匹配性能.文獻［12］中作者將GAFD算法用于VLAD編碼框架，其檢索精度以及效率有明顯提升.然而GAFD是以忽略特征原始梯度主方向為代價換取檢索速度以及檢索精度的少量提升.特征點梯度主方向對于海量圖像檢索也具有重要意義.

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

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

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

1　算法設計及框架

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

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

離線階段：

1）角度編碼：數據庫圖像根據重力信息以及特征角度進行特征分區；

2）VLAD量化qc：對訓練圖像角度子分區進行碼書映射及殘差計算；

3）角度乘積量化qp：各角度分區VLAD子向量進行PCA降維以及子碼書量化.

在線階段：

2）VLAD量化qc：對查詢圖像角度子分區進行碼書映射及殘差計算；

3）PCA降維：各角度分區VLAD子向量降至同數據庫圖像相同維度；

4）非對稱計算：計算查詢子向量到訓練圖像子向量對應子碼書中心的距離：

5）選擇K 近鄰結果進行真實歐氏距離重排序，排序后的結果即為檢索結果.

本文基于文獻［7-10］的工作基礎之上，將幾何信息用于視覺詞典的訓練，在特征編碼階段，經重力旋轉后具有相似角度的特征點被分區量化，獲得的圖像向量表達融合了特征點的描述符以及角度兩方面信息.角度乘積量化算法對每個角度子分區進行單獨編碼量化，通過查詢子向量與角度分區子碼書的非對稱計算取代查詢向量與數據庫向量的直接距離計算，在保證查詢精度的前提下大大降低了計算量.

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

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

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

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

重力傳感器已成為當前移動智能硬件的標配，重力傳感器能夠記錄相機姿態的旋轉.由于圖像旋轉變化的整體性，特征點主方向的旋轉變化?β也能夠通過重力傳感器測得［22］.因此，在詞典訓練過程中可以充分利用匹配特征主方向的線性相關性.

在本節中，我們提出一種融合重力信息的角度編碼方法（Oriented coding）來訓練具有幾何信息的視覺詞典，并將其應用于VLAD檢索框架中.

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

本節主要介紹融合重力信息的角度編碼（Oriented coding）算法，該方法由重力自適應的特征主方向計算以及角度量化兩部分構成.

1）重力自適應的特征主方向

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

圖2　不同拍攝角度的地標建筑及對應重力信息Fig.2　The landmark building with different viewing angles and corresponding gravity information

若圖 2（b）中重力傳感器信息為 Gi=［gx（i），gy（i），gz（i）］，則此時地標建筑旋轉角度：

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

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

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

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

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

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

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

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

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

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

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

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

離線數據庫構建階段，首先對角度子分區進行PCA降維：

然后對降維后的子分區分別進行K均值聚類，構建B個子分區碼書Cpj，j=1，···，B.每個子分區碼書包含k?個視覺單詞總共B×k?個子碼書，分區子碼書之間采用笛卡爾積形式組合，構成（k?）B個大碼書.最后對數據庫向量進行分區編碼，qpj為第j分區量化器，量化結果為子碼書中心索引標號：

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

然后針對每一數據庫向量，根據離線存儲的子碼書中心映射索引標號qpj（yi，j）在B×k?查找表中尋找非對稱距離：

根據非對稱計算返回Top K的最近鄰距離并進行歐氏距離重排，最后輸出結果即為檢索結果.

算法流程如下：

算法1.角度乘積量化

輸入.數據庫向量以及查詢向量.

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

步驟1.PCA降維后的數據庫向量子分區分別進行K均值聚類構建子分區碼書，并進行分區編碼；

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

步驟3.通過查找表以及數據庫子向量的碼書映射情況計算非對稱距離；

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

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

4　實驗結果及分析

4.1測試數據庫

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

圖4　重力信息標注的北京地標建筑數據庫Fig.4　Beijing landmarks of gravity information tagging database

4.2參數設定

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

4.3檢索性能

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

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

與CVLAD不同，圖5中Oriented coding方法檢索精度B=6＞8＞4，圖6具體給出K=16情況下Oriented coding方法隨角度分區數目B變化的檢索精度變化曲線，其中B=1代表不分區，即傳統VLAD方法.可以看出，Oriented coding方法在分區數目達到B=6后，檢索精度開始有所下降，這是由于本文采用重力傳感器XY軸計算圖像旋轉角度，對圖像拍攝時俯仰變化比較敏感.過細角度分區劃分會影響到俯仰角較大拍攝圖像的特征角度分區，容易出現錯分現象，導致檢索精度下降.因此后續實驗中，無特別說明，角度分區數目主要設置為B=6進行實驗.

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

圖6　Oriented coding檢索精度與分區數目關系Fig.6　The relationship of oriented coding retrieval accuracy and partition number

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

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

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

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

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

表1　Holidays數據庫檢索精度（mAP）Table 1　The retrieval accuracy of Holidays dataset（mAP）

4.4特征降維

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

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

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

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

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

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

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

4.6與其他檢索算法框架相結合

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

表2　海量檢索時間消耗（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　總結和展望

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

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，France: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，Fergus 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（桂振文，吳亻廷，彭欣.一種融合多傳感器信息的移動圖像識別方法.自動化學報，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（何云峰，周玲，于俊清，徐濤，管濤.基于局部特征聚合的圖像檢索方法.計算機學報，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，FL，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（湯紅忠，張小剛，陳華，程煒，唐美玲.帶邊界條件約束的非相干字典學習方法及其稀疏表示.自動化學報，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（劉培娜，劉國軍，郭茂祖，劉揚，李盼.非負局部約束線性編碼圖像分類算法.自動化學報，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（任越美，張艷寧，李映.壓縮感知及其圖像處理應用研究進展與展望.自動化學報，2014，40（8）:1563-1575）

張運超北京理工大學計算機學院博士研究生.主要研究方向為增強現實與虛擬現實.

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.）

陳 靖北京理工大學副研究員.主要研究方向為增強現實與虛擬現實，計算機視覺.本文通信作者.

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.）

王涌天北京理工大學教授.主要研究方向為新型3D顯示，虛擬現實，增強現實技術.

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

國家高技術研究發展計劃（863計劃）（2013AA013802），國家自然科學基金（61271375）資助

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

本文責任編委賴劍煌

Recommended by Associate Editor LAI Jian-Huang

1.北京理工大學計算機學院 北京1000812.北京理工大學光電學院北京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