[發明專利]移動環境下基于倒排位置敏感哈希索引的大規模圖象查詢系統

有效

• 申請號: 201610083052.9
• 申請日: 2016-02-05
• 公開（公告）號: CN105760468B
• 公開（公告）日: 2019-05-31
• 發明（設計）人: 季長清;陶帥;汪祖民;宮保樂
• 申請（專利權）人: 大連大學
• 主分類號: G06F16/53
• 分類號: G06F16/53;G06F16/951
• 代理公司: 大連智高專利事務所(特殊普通合伙) 21235
• 代理人: 畢進

1.一種移動環境下基于倒排位置敏感哈希索引的大規模圖象查詢系統，其特征在于，包括：

移動客戶端，通過攝像頭采集并提取圖片特征，與云中心服務系統通信；

云中心服務系統，建立基于倒排位置敏感哈希索引并查詢得到與采集圖片對應的近鄰圖像；

移動客戶端，通過攝像頭采集并提取圖片特征，與云中心服務系統通信；

云中心服務系統，建立基于倒排位置敏感哈希索引并查詢得到與采集圖片對應的近鄰圖像；

建立基于倒排位置敏感哈希索引的具體方法為，預先將數據集存儲到HDFS分布式文件系統中，啟動任務時，通過分布式緩存機制讀入一些配置文件LSH哈希函數族，每個Map任務讀入由JobTracker指定的數據分片作為輸入，然后根據給定的哈希函數對每一個數據對象進行哈希映射降維，將高維向量通過哈希映射之后得到一個哈希值，這一哈希值作為索引值，以鍵值對的形式進行輸出，Map過程的輸出作為Reduce的輸入，在Reduce里將相同哈希的所有數據對象收集到一起，將數據對象分隔，作為結果輸出到HDFS分布式文件系統中進行存儲；

所述查詢是建立基于位置敏感哈希分布式倒排索引的kNN查詢，步驟是：

設定網格單元大小為ɡ*ɡ，給定一個查詢點q，用Aq表示q點所在網格，以r為半徑，q為圓心作圓，對于特定的哈希函數，給定一點q，求其相鄰點時，首先利用函數分成若干個Hash桶，將Hash桶作為Key，Hash桶內的點集作為Value，Hash桶代指特定關系存在區域，用hv1、hv2、hv3······hvN表示，然后函數利用數據與哈希函數之間的關系對應哈希到特定的桶內，同時會使q與其有對應關系的桶內數據進行碰撞，篩選出與q碰撞次數較高的數據進行整合，則就得到某一特定點的相似數據；對于圖片的索引，需要更多的特征才能確定某一具體圖片，需要求出其他特征的相似數據，給定另一點P，同樣建立在同一數據表格中，以R為半徑，ｐ為圓心，找出其近鄰數據點，p與q點的最近鄰中可能出現同一點M，則M為索引的特征數據點的概率就特別大，以此類推，進行哈希，直至找出最終數據；

篩選出與q碰撞次數較高的數據的方法如下：

設高維數據集合為S，S是圖象檢索系統中已有大規模圖象庫，查詢對象集合為Q，Q是查詢圖象對象，先進行高維特征提取后，形成特征集,對于每個查詢對象q屬于Q,初始化關聯函數h,h屬于G，G是一個哈希族，LSH是一個多輪哈希的算法，不同的哈希函數，會得到不同的哈希結果，h對應q的相似點集合，半徑集合R=getCandidates(hashvalue)，hashvalue是哈希值，不同的哈希值，得到不同的哈希結果，R是桶寬；在某一半徑為r的區域內進行有關哈希函數的哈希沖突碰撞，哈希的每個對象為hashvalue=Computer(q,h)，每一個hasvalue是通過哈希計算函數得到的，多次碰撞直至將數據全部哈希，篩選出碰撞次數相對比較高的對象d=computer(q,c),對象d為對象q的臨近點的概率最高，對象d是碰撞可能性最高的對象，用碰撞計數統計代替實際的值，統計碰撞的次數作為最后的排序結果。