基于哈希編碼學習的圖像檢索方法

左 欣，沈繼鋒，于化龍，高 尚，徐 丹，胡春龍

(1.江蘇科技大學計算機科學與工程學院，江蘇鎮江212003)

(2.江蘇大學電氣信息工程學院，江蘇鎮江212013)

基于哈希編碼學習的圖像檢索方法

左 欣1，沈繼鋒2，于化龍1，高 尚1，徐 丹1，胡春龍1

(1.江蘇科技大學計算機科學與工程學院，江蘇鎮江212003)

(2.江蘇大學電氣信息工程學院，江蘇鎮江212013)

針對傳統的位置敏感哈希編碼低效的問題，提出一種監督學習框架下基于正交子空間的判別投影哈希函數學習的海明編碼方法.該方法首先根據特征值的能量分布進行子空間分解，其次基于Fisher判別分析準則，利用樣本的分布信息學習一組最佳投影的哈希函數，實現原始特征空間向海明空間的緊致嵌入，最終生成一組緊湊且具有判別性的二進制編碼，并用于圖像檢索.在公開數據集上的實驗結果表明:該算法與其他經典算法相比，具有較好的穩定性，降低了內存消耗并提高了檢索的平均準確率.

位置敏感哈希;正交子空間;判別投影學習;視覺字典;空間金字塔

圖像數據資源的集中和規模增大給圖像檢索帶來機遇的同時也帶來了挑戰，相較于傳統的基于文本的圖像檢索管理和查詢，其難度很大，很難滿足實際要求，因此，基于內容的圖像檢索(contentbased image retrieval，CBIR)受到很多學者的廣泛研究［1］.如何有效地描述圖像的特征信息，以及采用何種數據結構進行高效索引和快速相似性檢索等一系列問題成為了這個方向的研究熱點.此外索引的數據結構與查詢性能是緊密相關的，可以大致分為精確近鄰和近似近鄰這兩大類方法.前者主要研究如何準確地確定樣本點在樣本空間中的近鄰關系，檢索速度相對較慢;而后者主要研究如何設計高效數據結果確定樣本點的近似近鄰關系，將原始特征空間映射至海明空間，檢索速度較快.

當前基于內容的圖像檢索主要利用圖像的低層視覺特征，如顏色、紋理、形狀等，來表示圖像信息［2］，其面臨的主要問題是圖像低層特征和圖像高層語義間存在著語義鴻溝［3］，即圖像低層特征難以反映圖像所蘊含的對象、事件和場景等豐富語義［4］.為了解決這個問題，學者們進行了諸多方面的研究，并致力于建立一種有效介于圖像低層視覺特征到圖像高層語義之間的中間表示，稱為中層特征［5］.近年來隨著計算機視覺的發展，尤其是圖像特征、視覺字典法(bag of visual words，BoVW)［6］的提出及其應用，使得CBIR日趨實用化.BoVW是一種新穎的中層特征表示，該模型的主要思想是通過圖像訓練，用大量的局部特征向量聚類生成視覺字典，每幅圖像相對于視覺字典都能生成一個碼元頻率向量，并作為特征用于表示圖像.在物體識別領域，BoVW因其突出性能，已成為了目標識別領域的主流方法，受到越來越多的關注，一般在構造視覺字典時采用K-Means算法對特征點聚類，而該算法的每次迭代都要將數據點分配與之最近的聚類中心，因此在數據規模很大的情況下，大規模鄰近查找的時間急劇增加，因此，文獻［7］中提出一種層次化K-Means(jierarchical K-means，HKM)算法對大規模目標檢索實現了進一步優化，提高了字典學習的速度和目標檢索的效率.

基于視覺字典的圖像檢索還涉及高維數據的近鄰查找問題，在數據規模較大的情況下，用于高維近鄰查找的時間將急劇增加，使得算法效率很低.如果采用傳統的索引結構，如R樹、K-D樹等進行檢索，在特征維度較低時性能還比較高效，但當維數不斷增加時，它們的搜索性能卻隨之急劇惡化，有時甚至不如線性搜索［8］.文獻［9］中首次將倒排序結構引入圖像檢索領域，該方法在文本檢索中被廣泛應用.然而該方法隨著字典規模的擴大，檢索速度會明顯降低.文獻［10］中提出了詞匯樹結構來表示視覺詞典與索引，在圖像維度較低和數據量較小的時候可以達到較好的效果.

文獻［11］中提出的LSH算法成功克服了上述“維度災難”問題，解決了高維特征的近似近鄰(approximate nearest neighbor，ANN)搜索問題.然而由于LSH利用隨機選取投影面進行哈希，因此算法具有一定的隨機性，并且會導致以下兩個問題:①存在LSH映射函數的隨機性問題，進而隨機產生多個哈希表，得出不同檢索結果的現象，影響算法的性能;②LSH的隨機性會導致內存消耗大，尤其對大規模的數據集.

鑒于上述問題，文中提出一種基于正交特征子空間的判別投影哈希函數學習模型，并將其應用于大規模數據集的圖像檢索.該方法首先利用特征值分配算法［12］對原始特征空間進行正交分解;其次利用標注圖像之間的類別信息對每位哈希編碼的投影方向進行學習，并組合各個子空間的二進制編碼生成最終的編碼;最后進行空間驗證，進一步保證了算法的檢索效率.經典圖像庫中的實驗結果表明:文中算法與幾種經典的算法相比，具有較好的穩定性，在不影響檢索速度條件下，有效地提高了檢索準確率.

1 位置敏感哈希

位置敏感哈希［13］(locality sensitive hashing，LSH)近似查詢的索引技術，是目前解決高維向量近似最近鄰問題的經典算法，在圖像檢索等領域有著廣泛的應用［14］.LSH原理是利用一組基于穩定分布的哈希函數對高維數據進行降維映射建立多個哈希表，在某種相似度量條件下，使得原本空間中距離近的點經過映射操作后能夠以較大的概率哈希到同一個桶中，而相距較遠的點哈希到同一個桶中的概率很?。?5］，其數學表示如式(1):

式中:h(x)=sign(wTx+b);sim(x，y)= w為隨機超平面;b為隨機截距;sign()為符號函數.由于每個哈希函數計算只得到一位編碼，因而通常需要利用K比特編碼圖像特征信息，如式(2):

式中，H(x)∈{0，1}K，表示K維海明空間.

2 基于判別投影方向學習的哈希函數

2.1 判別投影哈希

文中基于監督學習框架，利用樣本之間的相似度信息來學習一組最優的投影方向，將原始的特征空間Rd映射至海明空間H，F:Rd→H，其中投影函數為

式中:W為優化求解后得到的投影方向的K×d維矩陣;b為K維偏置向量;x為d維圖像特征.利用產生的海明距離度量可以刻畫兩個海明向量間的距離，如下式所示:

因此，文中利用已有的相似樣本標注信息學習最優的投影矩陣W，使得相似樣本間的海明距離小，不相似的樣本間的海明距離大.

2.2 特征相似度表示

假設每個樣本提取的原始特征向量為x∈Rd，P={(x，x')|x，x'∈C}表示相似樣本集合，Ν= {(x，x')|x，x'?C}為不相似樣本集合.假設相似樣本間的特征用Sx，y∈RD表示，定義特征采樣函數fA(x)，A為采樣的維度序號，如A={1，2，3，10}表示只提取特性向量x的第1，2，3，10維作為特(y)＞表示特征第i維的值，刻畫了向量間的相似度.

2.3 判別投影矩陣學習

假設給定相似樣本對集合P與不相似性樣本對集合N，希望通過樣本對的信息學習一組最具判別能力的線性超平面，使得相似樣本與不相似樣本被正確的分類.這組線性超平面W可以通過線性判別準則進行學習，如下式所示:

類間散布矩陣Sb、類內散布矩陣Sw的推導為:

式中:C為類別數;μ為所有樣本的均值;μi為第i類樣本的均值;ni為第i類樣本的數目.Sw與Sb分別對應于類內和類間散度矩陣.因此，通過最優投影方向可以得出其封閉解，如下式所示:

2.4 偏置閾值求解

式中:FN(b)=|{(x，x')|min(y，y')+b＜0，(x，x')∈P}|;FP(b)=|{(x，x')|max(y，y')+b＞0，(x，x')∈N}|.P與N分別表示相似圖片對集合與不相似圖像對集合.上述目標函數可以利用簡單的線性搜索方式求解.

3 基于正交特征子空間聚合哈希

3.1 特征子空間分解

由于特征向量不同維度分布具有不同的方差，因此如何有效地平衡不同維度間的方差是降低量化誤差和提高檢索性能的關鍵.文中的方法是通過對特征子空間的方差平衡與最優判別投影方向的學習，來提高檢索的精度.假設原始特征空間為C，利用子空間分解成笛卡爾積的形式C=C1×C2×…× Cm，其中Ci表示原始特征空間的第i個子空間.假設原始的特征空間維數為RD，則子空間分解方法為等距劃分各個子空間，即Ci=Rd，D=md.為了更好地平衡各個維度的方差，文中利用特征值分配的子空間分解方法［16］對每個維度進行排列，再進行等距劃分來實現子空間的正交分解.

3.2 基于正交子空間的哈希編碼

文中提出的基于特征子空間的判別哈希學習目標函數如式(9):

式中:R為隨機旋轉正交矩陣，用于平衡不同子空間的能量分布［17］;ui(x)為子空間量化函數，用于提取原始特征空間的第i個子空間;Wi為第i子空間的最優判別投影方向，可以由式(7)計算獲得.最后的二進制編碼用每個子空間的編碼組合而成，如式(10):如:假設特征空間被劃分為兩個正交子空間，F(x) =［F1(x) F2(x)］=［010 100］，則最后x的二進制編碼為010100.

4 算法流程

基于BoWDA的目標檢索算法可以按如下步驟執行:

訓練階段如圖1a)所示:① 對圖片庫中所有圖像進行興趣點檢測，并利用SIFT方法提取所有點的特征;②利用層次K-means方法進行聚類，構建視覺字典;③基于視覺詞典，對圖像庫圖像進行量化編碼，生成特征向量;④基于空間金字塔技術構建每個圖像的量化特征，得到圖像的D維原始特征;⑤ 基于特征值分配的子空間正交分解;⑥基于監督學習框架，利用樣本之間的相似度信息，學習最優的投影方向W;⑦利用學習得到的投影矩陣，將所有樣本映射到哈希表，建立特征索引.

查詢階段如圖1b)所示:①計算查詢圖像的特征(參見訓練階段的①與③);②基于維度序號采樣的特征空間正交分解;③根據式(10)計算查詢圖像的二進制編碼;④采用海明距離對圖像進行相似性度量;⑤ 基于RANSAC的空間驗證［18］;⑥圖像檢索結果顯示.

圖1 圖像檢索系統Fig.1 Image retrieval system

5 實驗與分析

5.1 實驗設置

實驗環境為:小型服務器，4個四核酷睿2.8GHz CPU，12GB內存，所有實驗在MATLAB環境下運行.

分別在Oxford building 5k圖像庫［19］和INRIA Holiday圖像庫［20］上比較文中所提方法與幾種傳統方法的性能.Oxford building 5k數據庫包含5 062幅，含蓋11處標志性建筑的1024×768高分辨率圖片.INRIA Holiday圖像庫主要包含存在大量變化場景類型(如自然、人造，以及水和火影響等)的個人假期照片，共500個圖像組，每組代表一個明顯不同的場景或目標.其中每組的第1幅圖像為查詢圖像，組里其余的圖像為正確的檢索結果圖像.這些假期的圖像存在不同程度的旋轉、視角、光照亮度差異以及模糊變化等.另外為了驗證文中算法在大規模數據下的實驗性能，引入Flickr60K數據庫作為干擾項.

5.2 實驗結果及性能評價

5.2.1 查全率與查準率

實驗采用信息檢索的標準評價方法.查全率(recall)與查準率(precision)分別反映文中算法檢索的全面性和準確性，顯然兩個指標都越大越好.

式中:nr為檢索得到的正確的相關圖像數目;N為檢索得到的所有圖像;Nr為圖像庫中與查詢圖像相關的圖像數目.

INRIA Holiday圖像庫與Oxford building圖像庫的查全-查準曲線圖分別如圖2，3.從實驗曲線圖可以看出:詞匯樹的結果最差，倒排序方法其次;無論是查全率還是查準率，文中方法與傳統方法相比都得到了明顯的提高.

圖2 INRIA Holiday圖像庫查全-查準曲線圖Fig.2 Recall and precision picture INRIA Holiday image database

圖3 Oxford building圖像庫查全-查準曲線圖Fig.3 Recall and precision picture Oxford building image database

5.2.2 平均精度

文中還采用平均精度來評價圖像的檢索精度，如下式所示:

式中:M為圖像庫中總的圖像數目;Nt為圖像庫中屬于同一類圖像的數目;nt為被正確檢索出的屬于同一類圖像的數目.

由圖4可以看出字典尺寸對平均精度的影響.從圖中各組實驗的檢索結果中發現，隨著字典尺寸的增加，平均準確率的結果均越來越好.可以看出，字典經PCA［22］降維后，基于方向學習的LDA平均精度最高.

圖4 字典生成尺寸對平均準確率的影響Fig.4 Effect of dictionary size on the average precision

由圖5可知，編碼的長度是影響算法性能非常關鍵的參數.編碼長度的取值越大，算法的隨機性越小，算法的平均精度越高，隨之檢索復雜度也增加.

圖5 編碼長度對平均精度的影響Fig.5 Effect of encodings's length on the average precision

實驗以兩幅包含相同目標或場景的圖像為例，實驗結果如圖6，7.圖中左上帶藍色框的是查詢圖像，圖6a)是從INRIA Holiday圖像庫檢索出來的5幅未經空間驗證的相似圖像，不難看出，這些候選匹配對中存在錯誤匹配對，因此影響了檢索的質量;圖6b)中經過空間幾何驗證的結果大大減少了誤配.圖7a)是Oxford庫初步查詢的結果;圖7b)是空間幾何驗證后的結果.可以看出空間驗證可以很好地對查詢結果進行重新排序，提高檢索的準確率.

圖6 INRIA Holiday圖像庫空間驗證Fig.6 Space verification of INRIA Holiday image database

圖7 Oxford building圖像庫空間驗證Fig.7 Space verification of Oxford building image database

5.3 討論

從實驗結果可以看出文中方法具有良好的檢索性能，驗證了算法思路的有效性:首先歸功于樣本分布信息的判別投影方向學習，該方法利用圖像間的相似性，學習最優的判別投影方向，降低了算法的隨機性;其次歸功于采用了基于正交子空間的分解，提高了編碼緊致性;最后采用RANSAC算法對初次檢索返回的結果圖像加以驗證，進一步提高了算法的檢索準確率.

6 結論

針對傳統的LSH編碼低效，以及目前的CBIR算法很少考慮圖像像素點的空間信息的問題，文中提出了在一種監督學習框架下基于正交子空間的判別投影哈希函數學習的海明編碼方法.該方法首先根據特征值的能量分布進行子空間的分解，其次基于Fisher判別分析準則，利用樣本的分布信息學習一組最佳投影的哈希函數，實現原始特征空間向海明空間的緊致嵌入，最終生成一組緊湊且具有判別性的二進制編碼用于圖像檢索.公開數據集上的實驗結果表明:與其他經典算法相比，該方法具有較好的穩定性及有效性，大大提高了圖像檢索的平均準確率.

References)

［1］ 何佳蓉，蘇賦.基于內容的圖像檢索發展方向的探索［J］.信息通信，2015，1:85.

［2］Yilldizer E，Balci A M，Hassan M，et al.Efficient content-based image retrieval using multiple support vector machines ensemble［J］.Expert Systems with Applications，2012，39(3):2385-2396.

［3］Kovashka A，Parikh D，Grauman K.Whittlesearch:interactive image search with relative attribute feedback［J］.International Journal on Computer Vision，2015，115(2):185-210.

［4］Zhang H，Zha Z J，Yang Y，et al.Attribute-augmented semantic hierarchy:towards bridging semantic gap and intention gap in image retrieval［C］∥ACM International Conference on Multimedia.Barcelona，Spair: ACM，2013:33-42.

［5］Oquab M，Bottou L，Laptev I，et al.Learning and transferring mid-level image representations using convolutional neural networks［C］∥IEEE Conference on Computer Vision and Pattern Recognition.Columbus，OH，United States:IEEE，2014:1717-1724.

［6］Mansoori N S，Nejati M，Razzaghi P，et al.Bag of visual words approach for image retrieval using color information［C］∥Conference on Electrical Engineering.Mashhad:IEEE，2013，1-6.

［7］Yoo D，Park C，Choi Y，et al.Intra-class key feature weighting method for vocabulary tree based image retrieval［C］∥Proceedings of IEEE Conference on UbiquitousRobotsand AmbientIntelligence.Daejeon: IEEE，2012:517-520.

［8］Xu H，Wang J D，Zeng G，et al.Complementary hashing for approximate nearest neighbor search［C］∥Proceedings of IEEE International Conference on Computer Vision.Barcelona:IEEE，2011:1631-1638.

［9］Zobel J，Moffat A.Inverted files for text search engines［J］.ACM Computing Surveys，2006，38(2):6-10.

［10］Wang X Y，Yang M，Zhu S H，et al.Contextual weighting for vocabulary tree based image retrieval［C］∥IEEE International Conference on Computer Vision.Barcelona:IEEE，2011:209-216.

［11］Ji J Q，Yan S C，Li J M，et al.Batch-orthogonal locality-sensitive hashing for angular similarity［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2014，36(10):1963-1974.

［12］Philbin J，Chum O，Isard M，et al.Object retrieval with large vocabularies and fast spatial matching［C］∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Minneapolis，MN，USA:IEEE，2007，1-8.

［13］Cao Y D，Zhang H G，Guo J.Weakly supervised locality sensitive hashing for duplicate image retrieval［C］∥Proceedings of the 18th IEEE International Conference on Image Processing.Brussels:IEEE，2011: 2461-2464.

［14］Chafik S，Daoudi I，Ouardi H EI，et al.Locality sensitive hashing for content based image retrieval:a comparative experimental study［C］∥Proceedings of the Fifth International Conference on Next Generation Networks and Services.Casablanca:IEEE，2014:38-43.

［15］Kafai M，Eshghi K，Bhanu B.Discrete cosine transform locality-sensitive hashes for face retrieval［J］.IEEE Transactions on Multimedia，2014，16(4): 1090-1103.

［16］Ge T Z，He K M，Ke Q F，et al.Optimized product quantization for approximate nearest neighbor search［C］∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Portland，OR，USA: IEEE，2013:2946-2953.

［17］Gong Y C，Lazebnik S，Gordo A，et al.Iterative quantization:a procrustean approach to learning binary codes for large-scale image retrieval［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2013，35(12):2619-2929.

［18］ 邱亞輝，李長青，崔有幀.RANSAC算法在剔除圖像配準中誤匹配點的應用［J］.影像技術，2014(4): 46-47.

［19］Philbin J，Chum O，Isard M，et al.Object retrieval with large vocabularies and fast spatial matching［C］∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.Minneapolis，MN，USA: IEEE，2007，1-8.

［20］Jegou H，Douze M，Schmid C.Hamming embedding and weak geometry consistency for large scale image search［C］∥Proceedings of the 10th European conference on Computer vision.Marseille，France:Springer，2008:304-317.

［21］Agrawal S，Khatri P.Facial expression detection techniques:based on Viola and Jones algorithm and principal component analysis［C］∥Proceedings of the Fifth International Conference on Advanced Computing＆Communication Technologies.Haryana:IEEE，2015.108-112.

(責任編輯:童天添)

Image retrieval method based on hash code learning

Zuo Xin1，Shen Jifeng2，Yu Hualong1，Gao Shang1，Xu Dan1，Hu ChunLong1
(1.School of Computer Science and Engineering，Jiangsu University of Science and Technology，Zhenjiang Jiangsu 212003，China)
(2.School of Electrical and Information Engineering，Jiangsu University，Zhenjiang Jiangsu 212013，China)

We propose a supervised discriminative hash function learning for hamming coding to deal with the inefficiency of classical locality sensitive hashing(LSH)method.Firstly，the method decomposes the subspace according to the energy distribution based on the eigenvalues.Secondly，it makes use of the distribution of samples based on fisher criterion to embed the original feature space into hamming space in a more compact manner，and finally it generated a compact and discriminative binary code for the image retrieval system.Experimental results based on the public dataset demonstrated that our method is superior to other classical methods，which is more stable with less memory cost and also increases the average precision.

LSH;orthogonal subspace;discriminative projection learning;visual bags of words; spatial pyramid

TP391

A

1673-4807(2015)06-0567-07

10.3969/j.issn.1673-4807.2015.06.011

2015-07-01

國家自然科學基金資助項目(61305058);江蘇省青年科學基金資助項目(BK20150470，BK20130471，BK20140566，BK20150471);江蘇省高校自然科學基金資助項目(15KJB520008);江蘇科技大學博士科研啟動資金資助項目;校管課題(633301302)

左欣(1980—)，女，博士，講師，研究方向為圖像檢索、視覺屬性學習.E-mail:13952861739@163.com

左欣，沈繼鋒，于化龍，等.基于哈希編碼學習的圖像檢索方法［J］.江蘇科技大學學報(自然科學版)，2015，29(6):567-573.