魯 明 宋馥莉

（河南廣播電視大學，河南 鄭州 450008）

基于誤差加權哈希的圖像檢索方法

魯 明 宋馥莉

（河南廣播電視大學，河南 鄭州 450008）

圖像檢索技術旨在大規(guī)模圖像庫中準確、快速地檢索與查詢圖像相似的圖像?；诖?，對誤差加權哈希Error Weighted Hashing（EWH）快速近似最近鄰搜索算法進行分析，并將其與Locality Sensitive Hashing（LSH）局部敏感哈希、Multi-Index Hashing（MIH）多索引哈希進行分析比較，然后基于誤差加權哈希（EWH）算法構(gòu)建圖像檢索系統(tǒng)，設計分段哈希索引的結(jié)構(gòu)以及該系統(tǒng)所需要實現(xiàn)的功能模塊。

圖像檢索；算法設計；誤差加權哈希

隨著網(wǎng)絡的快速發(fā)展與多媒體技術的廣泛應用，互聯(lián)網(wǎng)上的圖像數(shù)量達到了上千億級并仍在不斷快速增長。圖像是人們廣泛使用的信息載體，因此，如何在大規(guī)模的圖像庫中對圖像建立有效檢索機制，實現(xiàn)精確、快速的相似圖像檢索，成為多媒體領域亟待解決的問題。本文設計實現(xiàn)了一種基于誤差加權的哈希圖像檢索方法。

1 誤差加權哈希算法

LSH（Locality Sensitive Hashing）局部敏感哈希算法在最近鄰搜索中是非常杰出的算法，現(xiàn)存的許多方法都是基于LSH算法而提出的［1］。但是，LSH算法存在的問題是，由于對查詢向量的子串在索引表中進行的是精確查找，所以一旦沒有找到與查詢向量子串完全相同的向量，那么該算法就無法將真正的最近鄰列入候選集中。

因為LSH的這一缺陷，Mani Malek Esmaeili等［2］在局部敏感哈希的基礎上提出了誤差加權哈希（Error Weight?ed Hashing，EWH）算法，通過考慮有誤差不完全相同的哈希向量，并且利用這些向量生成更為精確的候選集。與LSH和MIH相似，EWH同樣也需要一個預處理步驟，這一步驟要求先從二進制特征庫中生成索引表，而EWH算法的新穎之處在于其從索引表中檢索候選的方式。

1.1 預處理

為了提高檢索過程的時間效率，首先從二進制向量特征庫中生成一張索引表。該索引表有M行和n列，通過給每一列分配一個隨機秘鑰（共n個）而初始化索引表。每一個隨機秘鑰決定了一個二進制向量中的m個比特位的位置，從而形成了n個子向量中的一個。每一個子向量確定一個完整二進制向量在索引表中的存儲位置，如果二進制向量對應的子向量相同，將存儲在索引表的同一項中。每一列有M個哈希桶，理想情況下，M=2m，但是當m很大時，桶的數(shù)量將會很多。這種情況下，需要一個比較符合實際的M值和一個映射函數(shù)，將m比特子向量映射為1到M之間的整數(shù)。這個整數(shù)即為二進制向量的ID需要存放的桶號。

1.2 誤差加權哈希算法

EWH的核心算法的基本思想是：通過把離查詢向量的子串更近的向量賦以更高的分數(shù)，最后選取達到一定閾值的向量作為候選集向量。下面具體介紹了該核心算法的過程，如表1所示。

表1 誤差加權哈希（EWH）

對于一個查詢q，該算法初始化給特征庫中所有特征分配相似性分數(shù)0。從第一個秘鑰k1開始，從查詢向量q中產(chǎn)生子向量qk1，然后計算整數(shù)哈希值h0［=H(qk1)］并分配給第1列，第h0行桶中所有特征相似性分數(shù)a0。然后該算法產(chǎn)生m個與qk1相差1比特位的向量，并計算整數(shù)哈希值{h1}，分配給第1列，第{h1}行m個桶中的所有特征相似性分數(shù)a1。該算法繼續(xù)產(chǎn)生與qk1相差2比特位的向量，提取哈希值{h2}，分配給第1列，第{h2}行的桶中所有特征相似性分數(shù)a2。這個過程重復e次，最終每一個特征被賦予一個權重，該權重基于其子向量與查詢特征子向量之間的海明距離的大小。

上述過程對所有查詢向量的子向量分別在索引表中的每一列里重復一遍。每一次產(chǎn)生的哈希值{hr}（0≤r≤e）所指向的索引表中的桶里的所有特征的分數(shù)都增加了ar。因此，該算法產(chǎn)生了一個分數(shù)列表，每個分數(shù)代表了查詢向量與特征庫中向量之間的相似性水平。EWH然后選擇具有較高分數(shù)（大于s0）的特征作為候選。然后計算這些候選對應的完整向量與查詢向量之間的海明距離，最后返回查詢的最近鄰。

2 實驗部分

本研究所述方法的實驗使用大小不同的圖像數(shù)據(jù)集，對誤差加權哈希（EWH）和多索引哈希（MIH）進行對比，來比較2種索引技術的查詢性能實驗。本實驗采用256維的二進制向量，將所有圖像分成不同大小的數(shù)據(jù)集，分別為10、100、1000、10 000幅和100 000幅圖像，然后對每一個數(shù)據(jù)集分別進行特征提取，在本實驗中提取的是圖像的ORB特征，每幅圖像提取的特征數(shù)最多為100，相當于最終形成一個二進制向量的集合。查詢集是執(zhí)行查詢時使用的向量，本實驗在每一個數(shù)據(jù)集中分別選擇圖像組成每個數(shù)據(jù)集對應的查詢集，然后對每幅查詢圖像提取其圖像的ORB特征，也就是對二進制向量在二進制向量的數(shù)據(jù)集合中進行檢索。每次實驗的結(jié)果相似，從這些實驗數(shù)據(jù)來驗證分析所提出的方法的有效性，這里由于篇幅有限，下面只給出其中一次的實驗結(jié)果。

實驗采用的是64位Windows，實驗的運行環(huán)境是In?tel i3-3240（3.40GHZ）、2GB內(nèi)存。在此對本文采用的誤差加權哈希算法（EWH）而構(gòu)建的圖像檢索系統(tǒng)和基于多索引哈希（MIH）的圖像檢索系統(tǒng)的性能進行比較，為每一組數(shù)據(jù)建立索引結(jié)構(gòu)，設置查詢的最近鄰數(shù)量為100，然后計算查詢精度和速度，比較二者的精度和查詢速度。

2.1 EWH和MIH的精度比較

精度是判斷索引優(yōu)劣的一個重要準則。本實驗以精確的線性查詢作為基準來衡量算法的精度，結(jié)果如圖1所示，對從10、102、103、104和105的不同規(guī)模的數(shù)據(jù)集分別進行實驗分析，比較誤差加權哈希（EWH）和多索引哈希（MIH）的精度。

結(jié)果表明，在e取值為5的前提下，誤差加權哈希（EWH）的檢索精度在10、102、103、104、105的不同規(guī)模的圖像數(shù)據(jù)集下比多索引哈希（MIH）的檢索精度都略高。

圖1 不同數(shù)據(jù)集下EWH和MIH精度比較

2.2 EWH和MIH的速度比較

運行時間是判斷索引優(yōu)劣的關鍵。下面將進行誤差加權哈希算法（EWH）和多索引哈希算法（MIH）的查詢時間的實驗比較，在圖像數(shù)據(jù)集為10、102、103、104、105幅圖像時分別進行實驗。

實驗結(jié)果如圖2所示，由此可以看出隨著數(shù)據(jù)集的增大，查詢時間都在增加，但是誤差加權哈希算法（EWH）的查詢時間增加更快；在數(shù)據(jù)集為10、102、103時，誤差加權哈希算法（EWH）和多索引哈希算法（MIH）對一幅圖像進行查詢的運行時間非常接近；但是，在數(shù)據(jù)集為104、105幅圖像時，誤差加權哈希算法（EWH）對一幅圖像進行查詢的時間要明顯長于多索引哈希算法（MIH）的查詢時間。

圖2 不同數(shù)據(jù)集下EWH和MIH查詢時間比較

2.3 結(jié)果分析

由上述實驗結(jié)果可以看出，當e取值為5時，誤差加權哈希（EWH）能夠?qū)崿F(xiàn)精度更高的最近鄰查詢。但是，在數(shù)據(jù)集很大時，誤差加權哈希（EWH）對一幅圖像的查詢時間更長。誤差加權哈希（EWH）和多索引哈希（MIH）在本質(zhì)上都是通過不斷增加海明距離來進行最近鄰查詢的，但是誤差加權哈希（EWH）增加了根據(jù)海明距離大小賦值分數(shù)的過程，對所有特征的分數(shù)遍歷來篩選分數(shù)大于某一閾值的候選集的過程。

3 結(jié)論

本文介紹的是基于誤差加權哈希索引技術的圖像檢索系統(tǒng)的相關算法，可以應用于生物認證、內(nèi)容檢索和數(shù)字版權管理相關領域。同時，影響大規(guī)模圖像檢索技術的關鍵是高效索引結(jié)構(gòu)的選取，索引結(jié)構(gòu)的優(yōu)劣直接影響在線圖像檢索的實時性。

對圖像檢索的研究已在不斷發(fā)展，但當前的索引技術仍面臨著兩大問題，即高維數(shù)據(jù)引起的查詢性能下降和大規(guī)模數(shù)據(jù)導致的內(nèi)存空間資源不足［3，4］。目前，已有的研究還無法有效地解決這兩大問題。因此，如何組織大規(guī)模數(shù)據(jù)并進行準確快速的相似性查詢，是當前信息內(nèi)容安全領域研究的熱點與難點。

［1］梁俊杰.大規(guī)模圖像庫的高維索引技術研究［D］.武漢：華中科技大學，2007.

［2］盧佳音.基于圖像哈希檢索的圖像重排方法研究［D］.大連：大連理工大學，2013.

［3］Zhou W，Lu Y，Li H，et al.Spatial coding for large scale partial-duplicate web image search［A］//International Conference on Multimedea，2010：511-520.

［4］Xie H，Gao K，Zhang Y，et al.Efficient Feature Detection and Effective Post-Verification for Large Scale Near-Duplicate Im?age Search［J］.IEEE Transactions on Multimedia，2011（6）：1319-1332.

Image Retrieval Method Based on Error Weighted Hash

Lu Ming Song Fuli
（Henan Radio and Television University，Zhengzhou Henan 450008）

The goal of image retrieval technology is to find accurately and quickly the similar images in massive im?age database.Based on this,fast approximate nearest neighbor search algorithm for Weighted Hashing Error(EWH) was analyzed,and compared it with Locality Sensitive Hashing(LSH)and Multi-Index Hashing(MIH)algorithm, then the image retrieval system was constructed based on Error Weighted Hashing(EWH),the structure of the block hash index and the function modules that the system needs to implement were designed.

image retrieval；algorithm design；EWH

TP311

A

1003-5168(2016)09-0056-03

2016-08-11

河南省教育廳科學技術研究重點項目（14A520084）；河南省科技廳科技攻關課題（152102310325）；河南省教育廳人文社科研究重點項目（2017-ZZJH-112）。

魯明（1977-），男，碩士，講師，研究方向：計算機應用技術和教育信息化研究。