基于误差加权哈希的图像检索方法

鲁 明 宋馥莉

（河南广播电视大学，河南 郑州 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-），男，硕士，讲师，研究方向：计算机应用技术和教育信息化研究。