位圖局部敏感哈希的匹配二進制特征搜索算法

楊東升，張 展,2，廉夢佳,2，王麗娜,2

(1.中國科學院 沈陽計算技術研究所,沈陽 110168；2.中國科學院大學,北京 100049)

0 引 言

二進制特征是圖像特征匹配和識別的先進技術，相對于SIFT[1,2]和SURF[3,4]特征，其具有有效計算、快速比較和緊密存儲的優點。目前，主要二進制特征的提取算法有BRIEF[5]、ORB[6]、BRISK[7]、FREAK[8]和CBD[9]等。二進制特征即01字符串，一般使用漢明距離和最近鄰比率算法[10](NNDR)判斷兩個二進制特征是否匹配。

搜索匹配特征向量的算法有多種，但并不適用于搜索匹配二進制特征，因此有人提出了適用于搜索匹配二進制特征的哈希技術。例如：Indyk等[11]提出基于哈希表的近似近鄰搜索算法——局部敏感哈希(LSH)算法，其只適用于歐氏空間特征向量的搜索。Lv等[12]提出多探頭局部敏感哈希(MPLSH)，有效地解決了高維特征的相似度搜索問題，且可用于匹配二進制特征搜索。Kong等[13]提出將曼哈頓哈希表用于大規模圖像檢索，把二進制特征轉化為十進制數，根據曼哈頓距離計算不相似度進行查詢。Shrivastave等[14]通過旋轉致密化位排列哈希，實現了高維二進制特征的快速近鄰搜索。Lin等[15]提出在高維數據中使用決策樹快速監督哈希算法。Liong等[16]提出了基于緊湊二進制代碼學習的深度哈希算法。Lin等[17]提出了二進制哈希編碼的深度學習算法，實現了圖像的快速檢索。Norouzi等[18]在緊湊二進制代碼中，給出最小虧損哈希算法；之后，采用多索引實現了在漢明空間的二進制代碼子字符串的快速搜索，使在漢明空間的k近鄰(KNN)搜索成為可能[19]。Muja等[20]在使用自動算法配置的快速近鄰搜索中，給出多個隨機KD樹算法搜索高維匹配特征，在二進制特征快速匹配算法中提出了多層次聚類樹(HCT)算法，在高維數據可擴展近鄰算法[21]中，對近似最近鄰算法做出總結，并給出相應的近似近鄰快速搜索的函數庫(FLANN)。文獻[22]提出了位圖索引的近鄰搜索算法，具有占用空間少和搜索速度快的優點。

本文提出了快速計算位圖(FCBM)算法和位圖局部敏感哈希(BMLSH)算法，搜索兩個數據集中的匹配二進制特征或相似的二進制代碼，以提高匹配特征搜索效率和增加入圍點數。本文實驗使用文獻[23]給出的圖像數據集提取的ORB二進制特征，使用入圍點數、入圍率、平均查詢時間、平均投影誤差和空間復雜度等評價標準，將本文算法與FLANN函數庫中的二進制特征匹配算法(包括LINEAR、MPLSH和HCT等)進行對比。實驗結果表明：在相同條件下，本文算法的消耗時間少、搜索到的入圍點數多、匹配入圍率與平均投影誤差與其他算法接近、消耗的內存空間與多探頭局部敏感哈希算法相當。

1 理論基礎

1.1 二進制特征

二進制特征的提取[5，24，25]是根據特征點鄰域中，對應的“點對”之間灰度值大小確定特征0、1狀態的取值，如式(1)所示：

(1)

設L為二進制特征的長度，F代表二進制特征，是依次將多個T(Pa)按順序移位算出的整型數，如式(2)所示：

(2)

二進制特征(如BRIEF、ORB、BRISK和FREAK特征)在存儲時，依次將每8個T(Pa)作為一個無符號字符類型(uchar，8 bit)存入內存，每個二進制特征長度為L，則每個二進制特征可以用L/8個無符號字符型表示。

1.2 局部敏感哈希

(3)

點積的投影使近鄰特征映射到哈希表中相同的位置，需要的條件如下：

(1)在Rd空間(d維歐氏空間)中，任意特征向量p和q之間的距離小于等于R1，則特征向量p和q被分到同一個哈希桶的概率PH大于等于p1，如下所示：

PH=[h(p)=h(q)]≥p1

for‖p-q‖≤R1

(4)

式中：‖?‖為L2范數。

(2)在Rd空間，任意特征向量p和q之間的距離大于等于R2，則特征向量p和q被分到同一個哈希桶的概率PH很小，小于等于p2，且p2

PH=[h(p)=h(q)]≤p2

for ‖p-q‖≥cR1=R2

(5)

注意，由于線性點積，兩特征向量p和q所在哈希桶的距離‖h(p)-h(q)‖擁有的量級分布與‖p-q‖成比例，因此p1>p2。

1.3 位圖索引

位圖索引V是一個長度為N的聚集位向量[22]，每位的狀態只能是0或1。在位向量V中第i位的狀態，取決于對應的記錄，如果該位置的記錄是t，則該位為1；否則為0。舉例說明：當前的文件中，有6個記錄，每條記錄是(int,binary)的點對，編號為1到6，并依次為：(30,101)，(30,010)，(40,011)，(50,101)，(40,010)，(30,011)。

例子中，有6條點對記錄，所以位向量長度為6，第1條、第2條和第6條的整型記錄為30，所以整型記錄30對應的位向量為110001；同理，整型記錄40和50對應的位向量分別為001010和000100。例子中，第1條和第4條的二進制記錄為101，所以二進制記錄101對應的位向量為100100；同理，二進制記錄010和011對應的位向量分別為010010和001001。

2 位圖局部敏感哈希

2.1 計算二進制特征的位圖

二進制特征是高維的位向量，比如BRIEF、ORB特征是256位，BRISK、FREAK特征為512位。本文以ORB二進制特征為例，描述本文FCBM算法。ORB特征以無符號字符型(uchar)的形式存儲在內存，所以256位的ORB特征在內存中存儲了32個無符號字符型數。FCBM算法的主要目的是讓近鄰的二進制特征獲得相同的或近鄰的位圖，并使計算位圖的速度更快。

FCBM算法如下：首先從一個無符號字符型數(8 bit)中選取5 bit，組成一個5 bit的無符號字符類型數Si，Si∈[0,31]，則長度為32個無符號類型的ORB特征，經過以上處理可以得到32個Si，將Si按照ORB特征中對應無符號類型數的排序，依次編號為1～32，則每個ORB特征對應的記錄為S=S1S2…S32；Si∈[0,31]，即S的每個位置上的記錄Si∈[0,31]。然后，按照1.3節的方法計算位圖，記錄0～31都有一個對應的位向量設為Bj，j∈[0,31]，將位向量Bj轉化為32 bit無符號整型數，存儲于內存中。最后，將近鄰記錄的位向量按位或得到最終位向量作為ORB二進制特征的位圖。ORB特征由32個無符號字符型組成，只取前4個對FCBM算法進行舉例說明。

表1 無符號字符型的取位Table 1 Getting bits of unsigned characters

表2 記錄Si和對應的位向量Table 2 Bit vector of Si and

2.2 哈希表構建和位集優化查詢

將每個二進制特征的位圖或其位圖的一部分作為關鍵字，將關鍵字與二進制特征的ID作為映射存入每個哈希表相應的桶中。每個哈希表都有一個與關鍵字長度一致的掩碼，目的是再計算二進制特征的位圖時，避開近鄰特征中不一樣的位和降維。一般構建多個哈希表，哈希表中的一個哈希桶對應一個關鍵字，一個關鍵字對應一個或者多個二進制特征ID。因為ORB二進制特征是由256位組成，即32個uchar類型，所以ORB二進制特征位圖是32維的位向量，轉化成32 bit的無符號整型數，保存在內存中。

位集(bitset)是快速查詢關鍵字是否存在的一種算法。本文使用位集對匹配二進制特征的查詢進行優化，以快速判斷當前查詢特征是否存在于哈希表中。初始化位集為0，首先根據式(6)將哈希表中所有的關鍵字key存儲到位集bitset[]中，如下所示：

bitset[key/32]|=(1<<(key%32))

(6)

查詢時，根據式(7)判斷當前查詢關鍵字是否存在于哈希表中：

bitset[key/32]&(1<<(key%32))!=0

(7)

若當前計算結果為0，則關鍵字不存在；若計算結果不為0，說明關鍵字存在，則查詢與當前哈希表對應的桶。

2.3 保存查詢信息與特征匹配判斷

在位集中，若當前關鍵字存在于哈希表中，則查詢關鍵字對應的哈希桶中所有ID相應的二進制特征，計算當前關鍵字相應的二進制特征與ID相應二進制特征的漢明距離，當遇到與當前查詢二進制特征的最近鄰特征和次近鄰特征時，保存相應的ID以及最近鄰和次近鄰距離。設最近鄰距離為d1，次近鄰距離為d2，根據NNDR算法，判斷當前查詢特征與ID相應的二進制特征是否匹配，如式(8)所示：

R=d1/d2

(8)

若滿足閾值條件R<0.6，則匹配；否則不匹配。

3 實驗驗證

3.1 實驗設計

實驗包括5個部分：①計算位圖：提取左、右兩圖像的二進制特征，使用FCBM算法，分段依次計算每個二進制特征對應的位圖。②構建哈希表：使用左圖二進制特征對應位圖作為關鍵字，將關鍵字與二進制特征的ID作為映射，存入每個哈希表里相應的桶中，一個關鍵字可以對應多個二進制特征的ID。③位集優化搜索：將哈希表中的關鍵字存到位集中，原因是位集可以快速判斷當前查詢關鍵字是否存在于當前哈希表中。④保存查詢信息：若右圖特征對應關鍵字存在于哈希表中，則計算左圖關鍵字對應二進制特征與當前右圖特征的漢明距離，保存當前特征的最近鄰和次近鄰距離以及關鍵字對應特征的ID。⑤匹配入圍點判斷：使用NNDR算法，判斷左、右兩圖二進制特征是否匹配，根據左、右圖像匹配點集合，計算左圖轉到右圖點的旋轉矩陣，旋轉矩陣乘以左圖點得到的坐標與對應右圖點坐標的距離叫投影誤差，根據投影誤差判斷當前點是否是入圍點，入圍點數除以匹配點數即為匹配入圍率。

實驗使用Windows7操作系統，OPENCV圖像處理函數庫；使用文獻[23]給出圖像數據集所提取的ORB二進制特征作為算法評價數據集。文獻[23]給出的圖像數據集中，每個圖庫有6幅圖像，且每個圖庫里的圖像都是同一場景在不同情況下拍攝的。實驗時使用其中的5個圖庫，包括bike、boat、luven、trees和ubc圖庫，同一圖庫將第1幅圖像提取的ORB特征作為訓練特征，其他圖像提取的ORB特征作為匹配查詢二進制特征，圖庫中每張圖提取的ORB特征數如表3所示。使用搜索算法，查詢左圖與右圖的匹配二進制特征，計算兩圖的匹配點數、入圍點數、入圍率和平均投影誤差等。將本文算法與FLANN函數庫中的搜索匹配二進制特征的算法進行對比，包括LINEAR、MPLSH和HCT算法等。

表3 提取不同數據集中各圖像的ORB特征個數Table 3 Number of ORB features for extracting each image in different dataset

3.2 實驗數據及對比分析

3.2.1 哈希表數目不同

本文BMLSH算法有兩個變量，分別是哈希表數和關鍵字長度。如圖1所示，本文算法的定量分析圖，設置關鍵字長度為20，提取bike圖庫中bike1圖的ORB特征為5972個，bike2圖的ORB特征為5067個。由圖1(a)可以看出：本文算法搜索到的入圍點數在哈希表數不少于3個時，入圍點數大于2300，并且隨著表數的增加，入圍點數先是快速增加隨后趨于穩定；由圖1(b)可以看出：本文算法的入圍率高，入圍率隨著哈希表數的增加先是增加隨后趨于穩定；由圖1(c)可以看出：本文算法的平均查詢時間隨著哈希表數的增加呈線性增長；由圖1(d)可以看出，本文算法搜索到入圍點的平均投影誤差小于1.5 pixel。

3.2.2 關鍵字長度不同

圖2為不同關鍵字長度時本文算法的性能，定量設置哈希表數為5和12，提取bike圖庫中bike1圖的ORB特征為5972個，bike2圖的ORB特征為5067個。由于3.2.1節入圍點數入圍率在哈希表數為5時接近最大，在哈希表數為12時趨于穩定，所以設置兩個定量分析：當哈希表數為5時，設置關鍵字長度為14～25；當哈希表數為12時，設置關鍵字長度為15～27。

圖1 不同哈希表數量時本文算法的性能Fig.1 Performance of proposed method under different number of hash tables

由圖2(a)(b)(c)可知：隨著關鍵字長度的增加，入圍點數先增加后減小，入圍率逐漸減少，平均查找時間逐漸減少，在關鍵字長度為20左右時，入圍點數最多，入圍率最高，平均查詢時間適中；由圖2(d)(e)(f)可知：隨著關鍵字長度的增加，入圍點數先增加后減小，入圍率逐漸減少，平均查詢時間逐漸減少，在關鍵字長度為20左右時，入圍點數最多，入圍率最高，平均查詢時間適中。

3.2.3 不同算法性能的對比

圖3 使用bike圖庫時不同算法的性能Fig.3 Performance of different algorithms test bike dataset

圖3為LINEAR、MPLSH和HCT算法，與本文BMLSH算法的性能對比。其中，提取bike圖庫中6張圖像的ORB特征數，如表3所示。本文以bike1作為源圖像提取ORB特征作為訓練特征，其他圖像(bike2、bike3、bike4、bike5和bike6)提取的ORB特征作為查詢特征，bike圖庫中的圖像隨著編號的增加其模糊程度也增加。在相同的情況下，圖3(a)表明本文算法的入圍點數比其他算法多40個以上；圖3(b)表明，隨著查詢特征的增加，本文算法所需查詢時間的增加程度小，所需的查詢時間少；圖3(c)表明本文算法的查詢入圍率大于95.8%，與其他算法相當；圖3(d)表明本文算法平均投影誤差與其他算法接近。

圖4為使用boat圖庫，不同算法的性能對比。提取boat圖庫中6張圖像的ORB特征數，如表3所示。boat1～boat6圖像是不同視角不同旋轉角度下拍攝的圖像。在相同的情況下，圖4(a)表明本文算法的入圍點數多比其他算法至少多11個；圖4(b)表明，在查詢特征數目一定時，本文算法所需查詢時間少且穩定，為622.899～664.01 μs；圖4(c)表明本文算法的查詢入圍率大于85%，與其他算法相當；圖4(d)表明本文算法平均投影誤差與其他算法接近。

3.2.4 特征匹配效果對比

圖5 不同算法的入圍點連線圖Fig.5 Inliers connection diagram of different algorithms

圖5為本文BMLSH算法與其他算法的入圍點連線效果圖。實驗使用boat圖庫，提取boat1和boat2圖像的ORB特征分別為1500和1497個。本文BMLSH算法搜索到的入圍點數為330個，MPLSH算法搜到295個，LINEAR算法搜到239個，HCT算法搜索到267個。比較入圍點連線圖5(a)與圖5(b)(c)(d)可知，本文BMLSH算法的入圍點連線比較稠密，匹配入圍點數較多。

表4為不同算法使用luven圖庫查詢匹配特征的入圍點數，1|2是指luven1和luven2組成的圖像對。表5為不同算法使用luven圖庫查詢匹配特征的平均查詢時間。由表5可知：本文BMLSH算法查詢的入圍點數多，比其他算法多9個以上，平均查詢時間短，在666.046 μs以下。表6為不同算法使用trees圖庫查詢匹配特征的入圍點數。表7是不同算法使用trees圖庫查詢匹配特征的平均查詢時間。由表7可知：本文BMLSH算法的查詢入圍點數多，平均查詢時間最短，在636.796 μs以下。

表4 luven 圖庫不同算法的入圍點數Table 4 Number of inliers for different algorithms under luven dataset

表5 luven圖庫不同算法的平均查詢時間Table 5 Average query time by different algorithms under luven dataset μs

表6 trees圖庫不同算法的入圍點數Table 6 Number of inliers for different algorithms under trees dataset

表7 trees圖庫不同算法的平均查詢時間Table 7 Average query time by different algorithms under trees dataset μs

4 結束語

針對線性搜索、層次聚類樹等查詢匹配二進制特征時，效率低和入圍點數少的問題，本文提出了快速計算位圖(FCBM)算法以及位圖局部敏感哈希(BMLSH)算法。本文算法可用于匹配二進制特征的搜索、二進制特征識別、圖像定位和拼接等領域。實驗證明：在相同條件下，本文算法的消耗時間少，搜索到的入圍點數多，入圍率和平均重投影誤差與其他算法接近，消耗的內存空間與多探頭局部敏感哈希算法相當。

參考文獻：

[1] Lowe D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision,2004,60(2):91-110.

[2] 聶海濤,龍科慧,馬軍,等. 基于快速SIFT算法和模糊控制的人臉識別[J]. 吉林大學學報:工學版，2016,46(2):549-555.

Nie Hai-tao,Long Ke-hui,Ma Jun,et al. Face recognition based on fast scale invariant feature algorithm and fuzzy control[J]. Journal of Jilin University (Engineering and Technology Edition),2016,46(2):549-555.

[3] Bay H,Ess A,Tuytelaars T,et al. Speeded-up robust features (surf)[J]. Computer Vision and Image Understanding,2008,110(3):346-359.

[4] 郭清達,全燕鳴,姜長城,等. 應用攝像機位姿估計的點云初始配準[J]. 光學精密工程,2017,25(6):1635-1651.

Guo Qing-da,Quan Yan-ming,Jiang Chang-cheng,et al. Initial registration of point clouds using camera pos estimation[J]. Optics and Precision Engineering,2017,25(6):1635-1651.

[5] Calonder M, Lepetit V, Strecha C,et al. BRIEF:binary robust independent elementary features[J/OL].[2017-03-22]. http:∥icwww.epfl.ch/～lepetit/papers/calonder_eccv10.pdf.

[6] Rublee E, Rabaud V, Konolige K, et al. ORB:an efficient alternative to SIFT or SURF[J/OL].[2017-03-25].http:∥www.cs.zju.edu.cn/～gpan/course/materials/ORB.pdf.

[7] Leutenegger S, Chli M, Siegwart R Y. BRISK: binary robust invariant scalable keypoints[J/OL].[2017-03-23]. http:∥www.robots.ox.ac.uk/～vgg/rg/papers/brisk.pdf.

[8] Alahi A, Ortiz R, Vandergheynst P. FREAK:fast retina keypoint[J/OL].[2017-03-24]. https:∥infoscience.epfl.ch/record/175537/files/2069.pdf.

[9] 張展，楊東升. 圓周二進制描述符的圖像點特征提取方法[J]. 計算機輔助設計與圖形學學報,2017,29(8):1465-1476.

Zhang Zhan,Yang Dong-sheng. Image point feature extraction algorithm of circumferential binary descriptor[J]. Journal of Computer-Aided Design & Computer Grphics,2017,29(8):1465-1476.

[10] Richard Szeliski. 計算機視覺-算法與應用[M]. 艾海舟，興軍亮譯. 北京：清華大學出版社，2012:175-176.

[11] Indyk P, Motwani R. Approximate nearest neighbor: towards removing the curse of dimensionality[J/OL].[2017-03-23]. http:∥www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/IndykM-curse.pdf.

[12] Lv Qin, Josephson William, Wang Zhe, et al. Multi-probe LSH: efficient indexing for high-dimensional similarity search[J/OL].[2017-03-24]. http://www.cs.princeton.edu/cass/papers/mplsh_vldb07.pdf.

[13] Kong Wei-hao,Li Wu-jun,Guo Min-yi. Manhattan hashing for large-scale image retrieval[C]∥Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval, New York, NY, USA,2012:45-54.

[14] Shrivastave Anshumali, Li Ping. Densifying one permutation hashing via rotation for fast near neighbor search[J/OL].[2017-03-23]. http:∥proceedings.mlr.press/v32/shrivastava14.pdf.

[15] Lin Guo-sheng,Shen Chun-hua,Shi Qin-fen,et al. Fast supervised hashing with decision trees for high-dimensional data[C]∥IEEE Conference on Computer Vision& Pattern Recognition, Columbus, OH, USA, 2014:1971-1978.

[16] Liong Venice Erin, Lu Ji-wen, Wang Gang, et al. Deep hashing for compact binary codes learning[J/OL]. [2017-03-23].https://www.cv-foundation.org/openaccess/content_cvpr_2015/papers/Liong_Deep_Hashing_for_2015_CVPR_paper.pdf.

[17] Lin Kevin, Yang Huei-fang, Hsiao Jen-hao, et al. Deep learning of binary hash codes for fast image retrieval[J/OL].[2017-03-22]. http:∥www.iis.sinica.edu.tw/～kevinlin311.tw/cvprw15.pdf.

[18] Norouzi M, Fleet D J. Minimal loss hashing for compact binary codes[C]∥Proceedings of the 28th International Conference on Machine Learning, Bellevue, Washington, USA,2011:353-360.

[19] Norouzi M, Punjani A, Fleet D J. Fast search in hamming space with multi-index hashing[J/OL].[2017-03-25]. https:∥www.cs.toronto.edu/～norouzi/research/papers/multi_index_hashing.pdf.

[20] Muja M, Lowe D G. Fast matching of binary features[C]∥2012 Ninth Conference on Computer and Robot Vision, Toronto, ON, Canada,2012:404-410.

[21] Muja M, Lowe D G. Scalable nearest neighbor algorithms for high dimensional data[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence,2014,36(11):2227-2240.

[22] Garcia-Molina H, Ullman J D, Widom J. 數據庫系統實現[M]. 楊冬青,吳愈青,包小源譯. 2版. 北京：機械工業出版社，2010:688-693.

[23] Mikolajczyk K, Schmid C. A performance evaluation of local descriptors[J]. IEEE Transactions on Pattern Analysis &Machine Intelligence,2005,27(10):1615-1630.

[24] 鄒瑜,梁斌,王學謙,等. 基于旋轉投影二進制描述符的空間目標位姿估計[J]. 光學精密工程,2017,25(11)：2958-2967.

Zou Yu,Liang Bin,Wang Xue-qian,et al. Spacetarget pose estimation based on binary rotational projection histogram[J]. Optics and Precision Engineering,2017,25(11)：2958-2967.

[25] 崔少輝,謝征,王剛,等. 二進制魯棒不變尺度特征匹配電子穩像[J]. 光學精密工程,2015,23(9)：2715-2723.

Cui Shao-hui,Xie Zheng,Wang Gang,et al. Feature matching electronic image stabilization based on binary robust in variant scalable keypionts[J]. Optics and Precision Engineering,2015,23(9)：2715-2723.

[26] 羅家祥，林暢赫，王加朋，等．結合深度卷積網絡與加速魯棒特征配準的圖像精準定位[J]．光學精密工程，2017,25(2):469-476.

Luo Jia-xiang,Lin Chang-he,Wang Jia-peng,et al. Accurate image positioning combining deep convolution network with SURF registering[J]. Optics and Precision Engineering,2017,25(2):469-476.

[27] 熊昌鎮，單艷梅，郭芬紅．結合主體檢測的圖像檢索方法[J]．光學精密工程，2017,25(3)：792-798.

Xiong Chang-zhen, Shan Yan-mei, Guo Fen-hong. Image retrieval method based on image principal part detection[J]. Optics and Precision Engineering,2017,25(3):792-798.