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

魯 明 宋馥莉

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

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

魯 明 宋馥莉

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

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

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

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

1 誤差加權哈希算法

LSH（Locality Sensitive Hashing）局部敏感哈希算法在最近鄰搜索中是非常杰出的算法，現存的許多方法都是基于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很大時，桶的數量將會很多。這種情況下，需要一個比較符合實際的M值和一個映射函數，將m比特子向量映射為1到M之間的整數。這個整數即為二進制向量的ID需要存放的桶號。

1.2 誤差加權哈希算法

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

表1 誤差加權哈希（EWH）

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

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

2 實驗部分

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

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

2.1 EWH和MIH的精度比較

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

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

圖1 不同數據集下EWH和MIH精度比較

2.2 EWH和MIH的速度比較

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

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

圖2 不同數據集下EWH和MIH查詢時間比較

2.3 結果分析

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

3 結論

本文介紹的是基于誤差加權哈希索引技術的圖像檢索系統的相關算法，可以應用于生物認證、內容檢索和數字版權管理相關領域。同時，影響大規模圖像檢索技術的關鍵是高效索引結構的選取，索引結構的優劣直接影響在線圖像檢索的實時性。

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

［1］梁俊杰.大規模圖像庫的高維索引技術研究［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-），男，碩士，講師，研究方向：計算機應用技術和教育信息化研究。