[發明專利]云計算環境下基于倒排LSH的高維近似圖象檢索方法

有效

• 申請號: 201610083263.2
• 申請日: 2016-02-05
• 公開（公告）號: CN105760469B
• 公開（公告）日: 2019-05-31
• 發明（設計）人: 季長清;王寶鳳;汪祖民;宋佳齊
• 申請（專利權）人: 大連大學
• 主分類號: G06F16/53
• 分類號: G06F16/53
• 代理公司: 大連智高專利事務所(特殊普通合伙) 21235
• 代理人: 畢進

本發明公開了一種云計算環境下基于倒排LSH的高維近似圖象檢索方法，屬于基于大數據與移動應用領域。系統建立一種新的索引結構(LSRP?tree),降低了高維索引代價，提高了查詢效率；LSH與MapReduce結合形成的新算法(H?c2kNN)表現出了良好的擴展性和高效性。這兩種創新的應用解決了高維數據空間下的近似檢索問題。采用了基于哈希沖突碰撞計數與排序的優化方法，極大地減小中間數據量而加快數據處理速度。本發明是利用智能移動平臺來查找圖片的系統，包括一組云端服務器和一個移動客戶端，后者進行圖片采集與傳送，前者負責建立高維索引與執行kNN查詢處理等。本發明切實有利的提高了大量圖像的識別問題，滿足人們對移動信息檢索智能化的進一步渴求。

技術領域

本發明屬于基于大規模時空數據處理與移動技術應用領域，涉及一種云計算環境下基于倒排LSH的高維近似圖象檢索方法

背景技術

現在網絡基本覆蓋了人們的生活，手機上網成為主要上網模式。截至2014年6月，我國網民上網設備中，手機使用率達83.4％，首次超越傳統PC(使用臺式機和筆記本)整體使用率80.9％，手機作為第一大上網終端設備的地位更加鞏固。如今信息技術發展十分迅速，各種形式的信息數量也在迅速增長中，隨著用戶檢索要求多樣化復雜化，用戶不再滿足于簡單的文字檢索，而將圖像作為一種重要的信息載體，日常生活當中充斥著豐富多樣的圖像信息。例如用戶看到喜歡的漂亮頭像，想找類似的頭像、看到一款衣服或裙子，想找類似的款等等這種用文字表達不方便，而有圖片參考的檢索需求。

如今信息技術發展十分迅速，各種形式的信息數量也在迅速增長中，隨著用戶檢索要求多樣化復雜化，用戶已不再滿足于簡單的文字檢索，而更傾向圖像這一信息檢索。日常生活當中充斥著豐富多樣的圖像信息。例如用戶看到喜歡的頭像，想找類似的樣式，或是看到一款衣服或裙子，想找類似的款試等等。這種情況用文字表達不方便，但用圖片卻能極快滿足用戶的檢索需求。智能手機作為圖像的采集器當然必不可少。根據新數據了解，2015年全球智能手機用戶將達19.1億，2016年該指數將增長12.6％達到21.6億。智能手機將逐漸占領信息通訊市場。

那么，研究用戶應該如何做到依據圖像在這么多選擇中快速地找到自己需要的信息，怎樣提供一種快速有效的方法來進行圖像檢索已經成為當今圖像檢索領域的一個至關重要的研究熱點。現有的研究工作中，通常的做法是先對圖像的高維數據根據特定的方法(如圖像中常用的sift算子)來提取高維特征，然后根據特征建立索引來加快查詢速度。但不同的數據特征下，向量維數通常高達幾十甚至幾百維，而且每個維度的數據量都很大，這就要求高維索引結構具有較好的維度擴展性，即隨著維數的增加，索引仍然能夠保持較好的性能。遺憾的是，現在絕大多數傳統的空間索引技術都會遇到維災難等問題，比如Rtree與Voronoi等索引，總的來說，當前的高維特征索引技術存在以下不足：(1)大多數傳統的索引結構擴展性差與遇到維災難問題；(2)多數傳統索引機制在劃分數據空間時，對數據分布做了一定的假設(如均勻分布)，通常與數據的真實分布(如傾斜分布、Zipf分正態分布等)不同；(3)多數高維索引結構的空間和時間復雜度較高、精度較差。

發明內容

為了解決現有基于位置敏感哈希索引無法適應分布式索引，本發明提出了一種云計算環境下基于倒排LSH的高維近似圖象檢索方法，可以實現置敏感哈希索引適應分布式索引。

為了實現上述目的，本發明采用如下技術方案：一種云計算環境下基于倒排LSH的高維近似圖象檢索方法，包括步驟：客戶端采集并提取圖片特征，與云中心服務系統通信；云中心服務系統建立基于位置敏感哈希分布式倒排索引并查詢與采集圖片對應的近鄰圖像。

有益效果：由于云中心服務系統建立了基于倒排位置敏感哈希索引，使得位置敏感哈希索引可以適應分布式查詢，使得本發明解決了信息量過大、所需信息與顯示圖片不符等問題，盡可能幫助使用者節省了檢索與查詢的時間。

附圖說明

圖1云計算環境下基于倒排位置敏感哈希索引的大規模高維圖像檢索的原理圖；