[發明專利]基于分層結構的局部敏感哈希圖像索引方法

有效

• 申請號: 201910033703.7
• 申請日: 2019-01-14
• 公開（公告）號: CN109829066B
• 公開（公告）日: 2023-03-21
• 發明（設計）人: 吳家皋;黃超;侯澤磊;成新宇
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F16/51
• 分類號: G06F16/51;G06F16/583
• 代理公司: 南京蘇科專利代理有限責任公司 32102
• 代理人: 姚姣陽

本發明揭示了一種基于分層結構的局部敏感哈希圖像索引方法，包括如下步驟：S1、定義局部敏感哈希函數族H；S2、從H中取出k個函數，定義k維局部敏感哈希函數族G；S3、利用G將圖像特征數據集映射為k維向量集；S4、采用求和取余哈希法建立L張哈希表；S5、判斷是否已進行過第二次局部敏感哈希處理，若否則重新設置k和L，并返回S2，若是則結束流程。本發明通過引入了分層結構思想的方式對LSH算法進行了優化，即對經過一次LSH處理后得到的特征向量數據再處理一次，從而使得數據可以均勻的分布到各哈希桶中，從而縮小了查詢的候選向量集，顯著地提升了檢索速度。

技術領域

本發明涉及一種圖像索引方法，具體而言，涉及一種基于分層結構的局部敏感哈希圖像索引方法，屬于圖像處理技術領域。

背景技術

隨著云計算、大數據技術的發展，互聯網上的圖像、視頻等多媒體數據的處理量急劇增長。與傳統數據相比，圖像、視頻等多媒體數據具有高維度、非結構化的特性，這也就對相似性數據檢索和語義分析等算法的研究提出了新的挑戰?；趫D像特征的局部敏感哈希(Local ity Sensitive Hash，LSH)算法在處理高維數據時表現出了良好的性能，也正基于此，使其成為了近年來的研究熱點。

LSH算法由Indyk和Motwani于1998年提出，其基本思想是對數據點集利用一組哈希函數，使得經過哈希映射后相似的點沖突的概率增大，而不相似的點沖突的概率減小。目前，領域內已提出多個與局部敏感哈希相關的哈希索引方法，例如：p穩定局部敏感哈希將空間距離計算由漢明空間轉移到歐式空間；基于熵的局部敏感哈希在查詢項的周圍隨機產生擾動對象作為查詢項集合；多探針局部敏感哈希根據候選查詢結果與查詢對象的相鄰關系提出了有效的索引方案。

由于局部敏感哈希函數的隨機性，單個局部敏感哈希函數往往不能滿足相似性檢索的要求。為了提高算法的精確率，使用k個局部敏感哈希函數組成k維局部敏感哈希函數族；為了提高算法的召回率，使用L個k維局部敏感哈希函數來創建L張哈希表；這樣的操作方式也逐漸成為了業內在使用局部敏感哈希處理時的常見步驟。但在實際應用過程中操作人員發現，盡管在局部敏感哈希處理中引入了參數L、k，但還是存在部分特征向量數據在哈希劃分時出現錯誤的情況。

綜上所述，如何在現有技術的基礎上，提出一種新的局部敏感哈希算法，從而克服現有技術中存在的問題、提高算法使用過程中的檢索效率，也就成為了目前業內研究人員亟待解決的問題。

發明內容

鑒于現有技術存在上述缺陷，本發明的目的是提出一種基于分層結構的局部敏感哈希圖像索引方法，包括如下步驟：

S1、定義局部敏感哈希函數族H；

S2、從H中取出k個函數，定義k維局部敏感哈希函數族G；

S3、利用G將圖像特征數據集映射為k維向量集；

S4、采用求和取余哈希法建立L張哈希表；

S5、判斷是否已進行過第二次局部敏感哈希處理，若否則重新設置k和L，并返回S2，若是則結束流程。

優選地，S1具體包括如下步驟：

設任一圖像都能表示為d維特征向量空間R^d中的一個點，則所有圖像構成d維特征向量數據集D，定義局部敏感哈希函數族H＝{h|D→U}為從數據集D到整數域U的映射，