[發(fā)明專利]一種多索引磁盤哈希結(jié)構(gòu)的圖像檢索方法

有效

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

本發(fā)明涉及一種多索引磁盤哈希結(jié)構(gòu)的圖像檢索方法，包括以下步驟：離線索引階段，對多媒體數(shù)據(jù)提取高維特征；使用哈希映射方法將高維特征映射為哈希編碼；將哈希編碼平均分割為編碼子串；將編碼子串分別插入對應的基于磁盤的B+樹索引結(jié)構(gòu)中；重復上述步驟m次，形成多索引磁盤結(jié)構(gòu)。在線查詢階段，對于查詢的多媒體數(shù)據(jù)，經(jīng)過提取特征、哈希編碼、編碼分割后得到編碼子串，搜索該編碼在磁盤索引的r近鄰結(jié)果，合并r近鄰結(jié)果直至找到k近鄰結(jié)果后返回。本發(fā)明結(jié)合多索引哈希方法與B+樹存儲結(jié)構(gòu)的優(yōu)勢，在提高索引結(jié)構(gòu)檢索準確率和檢索速度的同時，增大了支持的數(shù)據(jù)量。

技術(shù)領(lǐng)域

本發(fā)明涉及圖像索引與檢索技術(shù)領(lǐng)域，具體涉及一種多索引磁盤哈希結(jié)構(gòu)的圖像檢索方法。

背景技術(shù)

近年來隨著“互聯(lián)網(wǎng)+”政策的推進，我國的互聯(lián)網(wǎng)技術(shù)、數(shù)字媒體技術(shù)、網(wǎng)絡傳輸技術(shù)蓬勃發(fā)展。智能手機平板等終端設備的普及以及社交應用、電子商務應用的不斷發(fā)展，使得圖像數(shù)據(jù)呈快速增長趨勢。為了更好地利用這些圖像數(shù)據(jù)，快速準確的大規(guī)模圖像數(shù)據(jù)檢索成為一個亟待解決的重要問題。傳統(tǒng)基于文本的圖像檢索依賴于圖像名稱或者注釋等帶有較強主觀性的文本信息，往往不能達到預期的檢索效果。基于內(nèi)容的圖像檢索采用圖像的顏色、紋理或形狀等特征進行檢索，能夠克服上述局限性，受到學術(shù)界和工業(yè)界的重視。

基于內(nèi)容的圖像檢索可以分為特征提取和特征匹配兩個過程：特征提取將圖像像素壓縮表示為高維特征向量，特征匹配則從大規(guī)模高維特征中找到查詢特征的近鄰數(shù)據(jù)(nearest neighbors)。目前高維特征近鄰檢索方法主要分為基于樹形結(jié)構(gòu)的方法和基于哈希映射的方法。近年來基于哈希映射的索引及檢索方法由于在實際應用中的優(yōu)秀表現(xiàn)，獲得了廣泛關(guān)注。

基于哈希映射的方法原理是將近鄰數(shù)據(jù)映射到同一個哈希桶，利用哈希沖突過濾多數(shù)非近鄰數(shù)據(jù)從而提高檢索效率。通過設計合理的哈希映射函數(shù)，基于哈希映射的索引結(jié)構(gòu)能實現(xiàn)次線性時間復雜度的檢索效率。這類方法將圖像的高維特征壓縮表示為幾十或幾百個比特的哈希編碼，壓縮高維特征表示的同時保持數(shù)據(jù)的局部敏感特性，即任意距離測度(L1距離、歐式距離等)小的數(shù)據(jù)，經(jīng)過哈希映射之后漢明距離小。

基于哈希映射的方法將圖像數(shù)據(jù)壓縮表示為哈希編碼，提高了存儲和計算效率，但是對于大規(guī)模哈希編碼并沒有一種有效的方法進行檢索。目前大部分研究將圖像表示為哈希編碼后采用線性掃描方法找最近鄰，檢索效率較低。M.Norouzi等人在文獻“Fastsearch in hamming space with multi-index hashing”中提出了一種基于編碼分割的多索引哈希結(jié)構(gòu)，與近似檢索不同，該結(jié)構(gòu)能實現(xiàn)“準確”的哈希編碼檢索且檢索時間復雜度為次線性。但上述方法需要使用大量內(nèi)存，不僅代價高，而且在數(shù)據(jù)量大、內(nèi)存無法載入索引結(jié)構(gòu)時無法使用。相對內(nèi)存而言磁盤容量大、價格低廉，非常適合用于大數(shù)據(jù)量的基于內(nèi)容的圖像檢索。由于磁盤的IO效率比內(nèi)存要低，因此如何設計一種合理的索引結(jié)構(gòu)來優(yōu)化磁盤的IO策略，同時保持多索引哈希結(jié)構(gòu)的檢索性能成為解決哈希編碼高效檢索的關(guān)鍵問題。

發(fā)明內(nèi)容

針對現(xiàn)有技術(shù)的不足，本發(fā)明提出了一種多索引磁盤哈希結(jié)構(gòu)的圖像檢索方法，用于解決高維數(shù)據(jù)的索引和快速檢索問題。該發(fā)明結(jié)合了多索引哈希算法檢索效率高，以及B+樹結(jié)構(gòu)磁盤IO效率高的特性，將哈希編碼存儲在基于磁盤的B+樹索引結(jié)構(gòu)中，能夠很好地支持大規(guī)模圖像高維數(shù)據(jù)的索引與檢索。

為了達到以上目的，本發(fā)明采用的技術(shù)方案如下：

本發(fā)明提出了一種多索引磁盤哈希結(jié)構(gòu)，用于對圖像高維特征數(shù)據(jù)進行磁盤索引，該索引結(jié)構(gòu)的建立方法包括以下步驟：

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

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

(3)基于步驟(2)生成的哈希編碼，將該編碼分割為m份，形成m個哈希編碼子串；