[發明專利]一種多索引磁盤哈希結構的圖像檢索方法

有效

• 申請號: 201610101397.2
• 申請日: 2016-02-24
• 公開（公告）號: CN105574212B
• 公開（公告）日: 2019-04-26
• 發明（設計）人: 趙仕榮;張健;彭宇新
• 申請（專利權）人: 北京大學
• 主分類號: G06F16/51
• 分類號: G06F16/51
• 代理公司: 北京君尚知識產權代理事務所(普通合伙) 11200
• 代理人: 邱曉鋒

1.一種用于圖像檢索的多索引磁盤哈希結構的建立方法，其步驟包括：

(1)對需要建立索引的圖像集提取一種或多種高維特征；

(2)使用哈希映射方法將步驟(1)提取的高維特征映射為若干比特的哈希編碼；

(3)將所述哈希編碼均勻分割為若干組哈希編碼子串；

(4)將步驟(3)所得的哈希編碼子串插入到對應的基于磁盤的B+樹索引結構中；

(5)重復步驟(3)、(4)，使用步驟(4)中基于磁盤的B+樹索引結構，對步驟(3)中均勻分割的哈希編碼構建索引結構，形成高維數據的多索引磁盤結構。

2.如權利要求1所述的方法，其特征在于，所述步驟(1)中的提取高維特征，是對圖像提取顏色、紋理或形狀特征。

3.如權利要求1所述的方法，其特征在于，所述步驟(2)中的哈希映射方法，包括各類將高維數據壓縮編碼成二進制的映射方法，在壓縮數據的同時保持局部敏感特性，即任意兩個距離測度小的數據，經過編碼之后形成的哈希編碼的漢明距離小。

4.如權利要求1所述的方法，其特征在于，所述步驟(3)中的編碼分割方法為將哈希編碼平均分成m等份，形成m個哈希編碼子串，其中m由最佳編碼長度決定。

5.如權利要求1所述的方法，其特征在于，所述步驟(5)重復步驟(3)、(4)m次，即每一個高維特征生成m個哈希編碼，保存到m個基于磁盤的B+樹索引。

6.根據權利要求1-5中任一權利要求建立的用于圖像檢索的多索引磁盤哈希結構。

7.一種多索引磁盤哈希結構的圖像檢索方法，其步驟包括：

(a)采用權利要求1所述的方法對圖像數據建立多索引磁盤哈希結構；

(b)對于查詢圖像，經過與權利要求1中步驟(1)、(2)、(3)相同的特征提取、哈希映射和編碼切割方法，得到m個查詢編碼子串；

(c)初始化檢索距離r為0，k近鄰結果為

(d)基于上述步驟(a)建立的磁盤索引，進行查詢編碼的r近鄰檢索，得到查詢編碼的r近鄰結果；

(e)將上述步驟(d)得到的r近鄰結果合并到k近鄰結果中；

(f)將r遞增1，重復上述步驟(d)、(e)，直至k近鄰結果數量超過k后，返回該結果。

8.如權利要求7所述的方法，其特征在于，所述步驟(c)中的檢索距離r表示當前循環查詢編碼與檢索結果的漢明距離，所述的k近鄰結果用于存放最終查詢編碼的k近鄰。

9.如權利要求7所述的方法，其特征在于，所述步驟(d)中進行查詢編碼的r近鄰檢索的方法是：

a)對查詢編碼第a+1個子串，其中a＝r％m，在對應的第a+1個B+樹索引結構中檢索r’近鄰，其中檢索r’近鄰時，首先枚舉與查詢編碼子串漢明距離為r’的所有編碼，然后從對應的B+樹索引結構中找到枚舉編碼對應的哈希桶并返回其中數據，得到候選結果；

b)計算步驟a)得到的候選數據哈希編碼與查詢編碼的漢明距離，篩選出漢明距離小于r的數據，得到查詢編碼的r近鄰結果。

10.如權利要求7所述的方法，其特征在于，所述步驟(f)中重復步驟(d)、(e)的次數不固定，由查詢編碼的近鄰數據分布決定，循環在找到k個近鄰結果后停止。