[發(fā)明專利]一種基于自適應(yīng)位分配哈希算法的大規(guī)模圖像庫檢索方法

有效

• 申請?zhí)枺?/td>: 201410305838.1
• 申請日: 2014-06-30
• 公開（公告）號: CN104021234B
• 公開（公告）日: 2017-04-19
• 發(fā)明（設(shè)計(jì)）人: 郭勤振;曾智;張樹武
• 申請（專利權(quán)）人: 中國科學(xué)院自動(dòng)化研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06K9/62
• 代理公司: 中科專利商標(biāo)代理有限責(zé)任公司11021
• 代理人: 宋焰琴

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

本發(fā)明屬于圖像檢索技術(shù)領(lǐng)域，涉及一種基于內(nèi)容的圖像檢索方法，尤其涉及一種基于自適應(yīng)位分配哈希算法的大規(guī)模圖像庫檢索方法。

背景技術(shù)

隨著互聯(lián)網(wǎng)上圖片數(shù)據(jù)的日益增多，如何快速、準(zhǔn)確地為用戶提供所需要的圖片資源顯得越來越重要。基于內(nèi)容的圖像檢索(content-based image retrieval，CBIR)可以比較好地解決這個(gè)問題，因此受到了許多研究者的關(guān)注。現(xiàn)有的檢索方法通過提取圖像的底層特征對圖像內(nèi)容進(jìn)行描述，然后利用特征比對判斷是否為相似圖像。因此，CBIR主要包括兩部分的核心研究內(nèi)容，一是有效的圖像特征表述，二是高效檢索算法。本發(fā)明主要解決高效檢索算法問題。

高效的檢索算法主要包括：基于樹的檢索算法和基于哈希的檢索算法。基于樹的檢索算法利用超平面遞歸劃分整個(gè)數(shù)據(jù)空間，在數(shù)據(jù)比較低維的情況下效果很好，但是當(dāng)數(shù)據(jù)維度比較高的時(shí)候，基于樹的檢索算法會(huì)退化成窮盡搜索。基于哈希的檢索算法的主要思想是將原始數(shù)據(jù)映射成漢明空間中的二值串(binary string)，數(shù)據(jù)之間的相似度可以利用它們在漢明空間的二值串之間的漢明距離來度量。基于哈希的高效檢索算法有兩個(gè)主要優(yōu)點(diǎn)：一是可以減少數(shù)據(jù)存儲(chǔ)空間；二是可以提高檢索效率。

局部敏感哈希(locality-sensitive hashing，LSH)[Mayur Datar，Nicole Immorlica，Piotr Indyk and Vahab S.Mirrokni.Locality-sensitive hashing scheme based on p-stable distributions.In Proceedings of the twentieth annual symposium on computational geometry，ACM，2004]利用c個(gè)投影函數(shù)來對原始數(shù)據(jù)分別進(jìn)行投影，再把投影后的數(shù)據(jù)閾值化為0和1，這樣就得到了原始數(shù)據(jù)的c位的編碼。但是由于LSH的投影函數(shù)是數(shù)據(jù)無關(guān)的(data-independent)，隨機(jī)產(chǎn)生的，并且產(chǎn)生的投影函數(shù)可能彼此是相關(guān)的，因此LSH編碼的效果不是很理想。

為了克服LSH的缺點(diǎn)，譜哈希(spectral hashing，SH)[Yair Weiss，Antonio Torralba，and Rob Fergus.Spectral Hashing.In NIPS，2008]根據(jù)原始數(shù)據(jù)，利用機(jī)器學(xué)習(xí)的方法尋找合適的投影函數(shù)，建立哈希構(gòu)造機(jī)制。主成分哈希(PCA hashing，PCAH)[Bin Wang，Zhiwei Li，Mingjing Li and Wei-Ying Ma.Efficient duplicate image detection algorithm for web images and large-scale database.In ICME，2006.]首先利用PCA對數(shù)據(jù)進(jìn)行投影，然后利用每一維度的均值將數(shù)據(jù)進(jìn)行閾值化為0，1來對數(shù)據(jù)進(jìn)行編碼。但是數(shù)據(jù)經(jīng)過PCA投影之后，每個(gè)維度的方差非常不均勻，差別很大，因此每一維度同等對待地利用1-bit來進(jìn)行編碼是不合理的，并且實(shí)驗(yàn)也驗(yàn)證了PCAH的這個(gè)缺點(diǎn)。各向同性哈希(Isotropic hashing，IsoH)[Weihao Kong and Wu-Jun Li.Isotropic hashing.In NIPS，2012.]的提出就是為了解決這個(gè)問題，在IsoH中，數(shù)據(jù)被PCA投影之后，會(huì)被一個(gè)學(xué)習(xí)到的正交各向同性矩陣重新投影，經(jīng)過兩次投影之后，數(shù)據(jù)在每一維度的方差都是相等的，之后再用1-bit來分別編碼每一維。但I(xiàn)soH存在不同維度具有不同信息，利用同樣的位數(shù)來編碼并不合理的問題。

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

針對上述問題，本發(fā)明提出了一種自適應(yīng)位分配哈希算法(Adaptive bit allocation hashing，ABAH)，根據(jù)不同維度的離散度，自適應(yīng)地分配不同的位數(shù)來編碼相應(yīng)的維度。本發(fā)明的特點(diǎn)在于，對于投影后的數(shù)據(jù)，離散度比較大的維度會(huì)被更多的位數(shù)來編碼，離散度比較小的維度會(huì)被比較少的位數(shù)來編碼。經(jīng)過ABAH編碼之后，數(shù)據(jù)之間的相似度可以利用它們在漢明空間的編碼之間的漢明距離來度量，而漢明空間的ABAH編碼可以很好地保持原始數(shù)據(jù)的近鄰結(jié)構(gòu)。

由此，本發(fā)明可以解決針對海量圖像檢索存在的圖像特征庫存儲(chǔ)空間大，檢索速度慢的問題，克服了LSH、SH、PCAH方法存在的不足。