[發明專利]二進制特征的檢索方法和系統

有效

• 申請號: 201410143079.3
• 申請日: 2014-04-10
• 公開（公告）號: CN104978350B
• 公開（公告）日: 2019-04-12
• 發明（設計）人: 李巖
• 申請（專利權）人: 騰訊科技（深圳）有限公司
• 主分類號: G06F16/903
• 分類號: G06F16/903
• 代理公司: 廣州華進聯合專利商標代理有限公司 44224
• 代理人: 王茹;黃曉慶

本發明提供一種二進制特征的檢索方法，包括如下步驟：獲取待查詢二進制特征，計算所述待查詢特征的跳變次數；其中，所述跳變次數為所述二進制特征中連續的比特值變化次數；根據所述待查詢二進制特征的跳變次數及預設的二進制特征集中各個二進制特征的跳變次數，獲得比較集合；將所述待查詢二進制特征與所述比較集合中的二進制特征進行窮舉比較，獲得檢索結果。本發明還提供對應的二進制特征的檢索系統，本發明能有效地減少檢索時間，提高檢索精度。

技術領域

本發明涉及數據檢索技術領域，特別是涉及一種二進制特征的檢索方法，以及一種二進制特征的檢索系統。

背景技術

二進制特征是圖像、音頻、文本等多媒體內容分析和其他數據分析常用的特征。比如圖像領域中的BRIEF特征、ORB特征、BRISK特征、FREAK特征等，文本分類中的simhash特征等。

如何實現近鄰搜索，即如何在一個二進制特征集合中快速查找某特征的近似最近鄰和R近鄰成為一個非常關鍵的問題。

目前常用的算法有：窮舉式搜索、基于hash函數的搜索、基于層狀樹結構的搜索。

雖然二進制特征的數據結構較為簡單，但是對于海量數據產生的二進制特征采用窮舉式搜索的速度還是很慢，無法滿足大數據下實時搜索的需求。

基于hash函數的搜索通過對二進制特征中的比特位進行抽樣，進行首次比較過濾，然后再用剩余的比特位進行校驗。該方法雖然比較簡單，但是hash函數的選擇及函數的個數都難以確定。

基于層狀樹的結構的搜索需要對二進制特征數據集上進行聚類，形成K個類別，每個類別中的特征相互之間的距離較小，不同類別的特征之間距離較大；之后再從K個類別中隨機選擇1個特征作為該類別的代表，將每個類別的特征再進行聚類，以此類推，構建一個樹結構。該方法需獲得訓練集，檢索精度與訓練集有關，因此檢索精度難以保證。

發明內容

基于此，本發明提供一種二進制特征的檢索方法及系統，能有效地減少檢索時間，提高檢索精度。

一種二進制特征的檢索方法，包括如下步驟：

獲取待查詢二進制特征，計算所述待查詢特征的跳變次數；其中，所述跳變次數為所述二進制特征中連續的比特值變化次數；

根據所述待查詢二進制特征的跳變次數及預設的二進制特征集中各個二進制特征的跳變次數，獲得比較集合；

將所述待查詢二進制特征與所述比較集合中的二進制特征進行窮舉比較，獲得檢索結果。

一種二進制特征的檢索系統，包括：

計算模塊，用于獲取待查詢二進制特征，計算所述待查詢特征的跳變次數；其中，所述跳變次數為所述二進制特征中連續的比特值變化次數；

第一獲取模塊，用于根據所述待查詢二進制特征的跳變次數及預設的二進制特征集中各個二進制特征的跳變次數，獲得比較集合；

比較模塊，用于將所述待查詢二進制特征與所述比較集合中的二進制特征進行窮舉比較，獲得檢索結果。

上述二進制特征的檢索方法及系統，針對二進制特征的特點，記錄二進制特征中連續的比特值變化次數作為跳變次數，根據二進制特征集中各個特征的跳變次數，當獲取到待查詢二進制特征時，根據兩者的跳變次數，獲得比較集合；由于比較集合中得到了與待查詢二進制特征跳變次數較為接近的特征，窮舉比較的數量較少，能更加快速地獲得檢索結果。

附圖說明

圖1為本發明二進制特征的檢索方法在一實施例中的流程示意圖。

圖2為圖1中索引樹的結構示意圖。

圖3為本發明二進制特征的檢索系統在一實施例中的結構示意圖。