卢艳君，徐望明

(武汉科技大学信息科学与工程学院，湖北 武汉，430081)

一种运用随机算法改进的图像检索方法

卢艳君，徐望明

(武汉科技大学信息科学与工程学院，湖北 武汉，430081)

传统基于局部特征表示的图像检索方法在图像特征提取和特征相似性匹配时计算量较大，为此提出一种运用随机算法进行改进的图像检索方法。在图像特征提取方面，通过随机采样获得数量适当的像素点作为特征点，用SIFT(scale invariant feature transform)算子对随机特征点进行描述以形成图像的有效表示；在特征相似性匹配方面，采用基于随机映射的LSH(locality sensitive hashing)算法为图像特征库建立索引，并用于对所查询图像的局部特征进行高效的近似近邻搜索。实验结果表明，该方法有效降低了图像检索的计算复杂度，提高了检索效率。

图像检索；局部特征；随机采样；特征索引；SIFT特征；LSH算法

为了从海量数字图像信息中获取有价值的信息，基于内容的图像检索(content-based image retrieval, CBIR)技术[1]近年来得到广泛关注和应用。CBIR是从所查询图像的视觉特征出发，在图像库中找出与其最为相似的图像。CBIR系统中最关键的两项技术是图像特征提取和特征相似性匹配。

图像特征提取技术是CBIR的基础，用于解决图像的有效特征表示问题。图像特征有全局特征和局部特征之分，后者是近年来计算机视觉领域的研究热点，人们相继提出很多局部特征描述方法，其中SIFT(scale invariant feature transform)特征[2]的性能得到普遍认可。标准SIFT特征是采用精心设计的算法检测图像特征点(也称作“兴趣点”或“关键点”)并进行特征描述而得到，而通常从一幅图像上提取的特征数量有限，且随图像灰度的变化其差异性较大，甚至在有些对比度过低的图像中还可能检测不到特征，另外一个不利因素是其特征点检测算法的运算复杂度一般较高；密集采样(dense sampling)[3]的局部特征(如dense SIFT)按给定窗口尺寸和步长遍历图像子区域并进行特征描述，虽然其对图像内容的描述覆盖面较大，但也带来特征数据量过多的问题。

特征相似性匹配技术是CBIR的核心，用于解决库图像特征的有效索引和所查询图像特征的高效近邻搜索问题。一个有效的特征索引机制对于查询特征的高效近邻搜索而言是至关重要的。常规的基于特征空间搜索的索引算法如KD -Tree、R-Tree等仅能处理较低维度的特征数据，当维度提高时这些算法的复杂度呈指数级上升，性能急剧下降，而线性扫描(即穷举搜索)虽然不受特征维度的限制，但耗时较长。在图像检索的实际应用中，为了提高检索速度，一种可行的做法是以降低部分检索准确度为代价，由此，从“近邻搜索”的概念出发，研究者提出了“近似近邻搜索”的概念。LSH(locality sensitive hashing)算法就是建立在哈希索引基础上的近似近邻搜索算法[4-6]，它具有较低的复杂度，对高维数据空间中搜索查询的支持性较好。

在综合分析标准SIFT和密集采样这两种特征提取方式优缺点的基础上，本文提出一种运用随机算法改进的图像检索方法，即通过合理设置采样点数和相关参数对图像进行随机采样(random sampling)[7]，将采样点作为特征点，进而利用SIFT特征描述算法对随机特征点进行描述，从而形成图像的特征集表示形式；同时，在建立特征索引和进行近邻搜索时均采用LSH算法，以提高检索效率。

1 改进的图像检索系统工作原理

本文运用随机算法改进的图像检索系统如图1所示，系统可分为离线过程和在线过程两部分。①离线过程，即对于图像库中的每幅图像，系统事先离线运用特征提取算法，经特征检测、特征描述两步得到图像特征向量，形成相应的图像特征库，然后在此基础上建立特征索引以方便对查询特征的快速搜索；②在线过程，即对于用户提交的查询图像，系统运用相同的特征提取算法实时获取图像特征向量，然后通过适当的相似性搜索算法从特征库中查找所有查询图像特征的近邻特征，并通过对库图像投票的方式计算查询图像与库图像之间的相似度，按相似度从大到小的顺序返回最相似的一组库图像作为图像检索结果。

为了评估图像检索性能，可根据返回的检索结果和库中真实结果做统计分析，计算出查准率、查全率及检索效率等评价指标。其中，查全率是检索出的相关图像与图像库中相关图像的比值，查准率是检索出的相关图像与检索出的图像总量的比值。

Fig.1 Improved image retrieval system using random algorithms

2 关键算法描述

2.1 随机采样SIFT

图像特征提取包括特征检测和特征描述两个部分。标准SIFT算法获取图像特征向量大致有4个步骤[1]：检测尺度空间极值点作为候选特征点；筛选并精确定位特征点的位置和尺度；为特征点分配主方向；生成特征描述向量。其中，前两步属于特征检测部分，后两步属于特征描述部分。

本文缩减了标准SIFT算法在特征检测阶段的大量计算，通过随机采样图像像素点作为特征点并进行SIFT特征描述从而得到图像特征向量，不涉及尺度空间理论和极值点检测及筛选过程，因此该方法能有效降低计算复杂度，提高计算效率。

随机特征点采样完成后，对其进行描述。特征描述的目的在于准确表达局部图像信息并使这种信息具有可靠的表征性。本文直接对随机采样的特征点进行SIFT特征描述，因此最终得到的特征向量相对于标准SIFT算法而言只包含位置和方向信息。SIFT特征向量计算步骤如下：

(1)取特征点周围4×4的邻域，利用此邻域内像素点的梯度来统计方向直方图，即以每10°方向为一个柱，柱所代表的方向为像素点梯度方向，柱的长度代表梯度幅值。对方向直方图进行两次平滑后的主峰值即为特征点的主方向。利用特征点邻域像素的梯度方向分布特性，可以为每个特征点指定方向，从而使描述子对图像旋转具有不变性。设特征点(x,y)处的灰度值为g(x,y)，图像梯度方向为θ(x,y)、幅值为M(x,y)，计算公式如下：

(1)

M(x,y)=[(g(x+1,y)-g(x-1,y))2+

(2)

(2)为保证特征向量的旋转不变性，将特征点周围16×16邻域旋转为特征点的主方向。设旋转前采样点坐标为(x,y)，则可计算旋转后的采样点坐标(x′,y′)：

(3)

式中：θ为步骤(1)中计算得到的特征点梯度方向θ(x,y)。

(3)在特征点周围16×16邻域窗口中，对各像素点根据坐标按加权平均归入4×4的位置网格，每个网格构成一个种子点。

(4)利用式(1)、式(2)统计各个网格的方向直方图，此时每个网格区域直方图将00～360°划分为8个方向区间，每个区间范围为45°，即每个种子点有8个方向区间的梯度强度信息，最终获得128维的SIFT特征描述向量。进一步对其进行归一化处理，以去除光照变化的影响。

由于本文中采样点的位置是随机的，一些采样点经特征描述后得到的128维向量表征图像特征的能力较弱，甚至可能影响检索的准确率，因此，需对特征描述后得到的向量进行筛选，具体方法为：

假设特征点D经特征描述后所得向量(a0,a1,…,a127)中元素值为0的元素个数为n(n∈[0,128])，若n>K(K∈N+)，则舍去该点D。K值可根据所查询的图像，通过多次实验比较获得。

2.2 LSH算法

LSH算法的基本思想是：对于数据点集，利用一组具有一定约束条件的哈希函数建立多个哈希表，使得在某种相似度量条件下相似点发生冲突的概率相对较大，而不相似点发生冲突的概率相对较小[4-5]。引入LSH函数族定义：

LSH函数实际上是一种随机映射，本文将LSH算法应用于CBIR系统中，将图像局部特征映射为Hamming空间的点，对这些点进行哈希处理，使Hamming距离越近的点发生冲突的概率越大。在CBIR系统中，LSH算法用于进行图像特征相似性匹配，具体包括建立库图像的特征索引以及搜索查询图像特征的近似近邻。

应用LSH算法为图像特征库建立索引的步骤为：

(1)将图像高维特征向量p=(x1,x2,…,xd)映射到Hamming空间中，转化为二进制串p'=Uc(x1)Uc(x2)…Uc(xd)。其中，Uc(xi)(i∈[1,d])表示xi个1后跟c-xi个0组成的二进制串，c为特征向量p中任意元素xi的最大值。

(2)从字符串p'中随机选k位(k∈(0,c×d))组成哈希函数族gj(p)(j∈(0,l],l∈N+))，这样l个函数：g1(p)、g2(p)、…、gl(p)，每个函数对应一个哈希表。此过程计算复杂度低，体现了LSH算法的随机性。

(3)利用步骤(2)中的哈希函数，将特征向量映射到相应的哈希表中。

应用LSH算法对查询图像特征进行近似近邻搜索的步骤为：

(1)对于查询图像中特征q1、q2、…、qk，同样将特征向量按索引建立过程中的步骤(1)映射到Hamming空间中，转换为二进制字符串，并通过与索引建立过程中相同的l个哈希函数g1(p)、g2(p)、…、gl(p)分别映射到相应的哈希表中。

(2)提取gi(qj)(i∈(0,l],j∈(0,k])相似域中的所有哈希表项，保留与查询图像特征向量距离在阈值范围内的表项，由特征库索引查找对应特征作为候选的近邻特征。

(3)对于得到的候选近邻特征集，按其与查询特征之间的Hamming距离由小到大排序，返回前K个特征作为查询图像特征的近邻特征，它们是后续对库图像进行投票和排序从而得出图像检索结果的依据。

这里，LSH算法将原始特征空间中距离问题转换成了Hamming空间中的距离度量问题，提高了空间使用率，大规模数据的索引、查询操作转化为一组哈希函数的操作，在一个相对很小的数据集上的数据检索大大缩短了相似搜索时间。因此，LSH算法具有较好的时间效率，而且在高维数据空间仍能保持良好的性能[8]。

3 图像检索实验及结果分析

实验环境为Intel(R)Core(TM)i5CPU3.20 GHz，操作系统为Windows XP，系统开发平台为配置了开源计算机视觉库OpenCV2.4.9的Microsoft Visual Studio 2012。所用图像库是著名的ZuBuD图像库[9]，它包含201栋建筑物图像，每个建筑物各有5幅不同季节和天气条件下不同角度的图像，共1005幅，格式为png，分辨率为640×480。本实验的目标在于从图像库中查找与给定查询图像属于同一建筑物的图像。经多次实验观察，对于本文所用图像，在对特征描述后得到的向量进行筛选时，取K=64时检索效果较好。

为了进行对比分析，离线过程中，对图像库所有图像采用标准SIFT或随机采样SIFT进行特征提取，将所有特征数据存入特定文件夹作为图像特征库，不建立索引或采用LSH算法对特征库建立索引；在线过程中，从图像库中选取100幅图像作为查询图像，同样采用标准SIFT或随机采样SIFT实时提取特征后，将查询特征与特征库特征通过线性扫描法或LSH算法实现近邻搜索，从而根据搜索到的近邻特征对库图像进行投票、排序并得出最终检索结果。

在进行图像特征提取实验时，统计了对单幅图像特征提取的平均数量和平均时间，以比较标准SIFT算法和本文采用的随机采样SIFT算法。实验结果如表1所示。

表1 单幅图像特征提取的平均数量和时间

Table 1 Average number and time of feature extraction from one image

由表1不难看出，随机采样SIFT算法提取的特征数量虽然是标准SIFT算法的近4倍，但所需的提取时间却不到标准SIFT算法的1/3，因此，随机采样SIFT算法明显比标准SIFT算法的特征提取效率高。

采用不同的特征提取方法(标准SIFT、随机采样SIFT)和特征相似性匹配方法(线性扫描法、LSH算法)进行图像检索的实验结果对比如表2所示。

由表2可见，在特征提取方法相同时，线性扫描法相比LSH算法在检索准确率上只提高4.5个百分点左右，然而LSH算法比线性扫描法的检索时间却减少了53.3%以上。在进行图像检索时，本文采用的“随机采样SIFT+LSH算法”组合相比传统的“标准SIFT+线性扫描法”组合在平均查准率上只降低了7.1个百分点，但平均检索时间明显减少，前者的查询效率接近后者的3.8倍。在对计算效率要求苛刻的图像检索实际应用中，这种以牺牲较少准确率为代价换取更高效率的做法是可取的。

4 结语

本文针对传统基于局部特征表示的图像检索方法存在的不足，提出了一种运用随机算法改进的图像检索新方法，即采用随机采样SIFT算法提取图像局部特征，采用LSH算法实现图像特征的相似性匹配，包括建立库图像特征索引和完成查询图像特征的近似近邻搜索。随机算法的合理运用明显降低了图像检索中特征提取和特征相似性匹配的计算复杂度。实验结果表明，相比于传统的基于局部特征表示的图像检索方法，本文方法有效减少了计算量，缩短了检索时间，特征提取和图像检索的效率大为提高。

[1] 韦立梅, 苏兵. 基于内容的图像检索技术综述[J]. 电脑与电信, 2012 (10): 69-70.

[2]LoweDG.Distinctiveimagefeaturesfromscale-invariant keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[3] Li Fei-Fei, Pietro Perona. A Bayesian hierarchical model for learning natural scene categories[C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. IEEE, Los Alamitos, CA, 2005, Vol 2: 524-531.

[4] Datar M, Indyk P, Immorlica N, et al. Locality-sensitive hashing scheme based on p-stable distributions[C]//Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG’04). New York, Jun 9-11, 2004: 253-262.

[5] Slaney M, Casey M. Locality-sensitive hashing for finding nearest neighbors[J]. IEEE Signal Processing Magazine, 2008,25(2):128-131.

[6] 於慧, 谢萍, 李世进, 等. 基于多特征LSH索引的快速遥感图像检索[J]. 山西大学学报:自然科学版, 2013, 36(3):350-360.

[7] Nowak E, Jurie F, Triggs B. Sampling strategies for bag-of-features image classification[C]//Proceedings of 9th European Conference on Computer Vision. Graz, Austria, May 7-13, 2006: 490-503.

[8] 赵启潍, 张乐, 祝贝利, 等.面向高维数据的LSH算法及应用[J]. 福建电脑, 2012, 28(4): 13-14.

[9] Shao H, Svoboda T，Van Gool L. ZuBuD-Zurich buildings database for image based recognition[R]. Technical Report No.260, Zurich: Swiss Federal Institute of Technology, 2003.

[责任编辑 尚 晶]

An improved image retrieval method using random algorithms

LuYanjun,XuWangming

(College of Information Science and Engineering, Wuhan University of Science and Technology, Wuhan 430081, China)

An image retrieval method using random algorithms is proposed to improve the traditional local feature representation method which often needs a large amount of calculation during image feature extraction and similarity matching. For image feature extracting,the method adopts random sampling to obtain an appropriate number of image pixels as the feature points, then represents these random feature points with SIFT descriptors in order to form an effective image representation. For feature similarity matching, it applies a random mapping LSH algorithm to indexing the feature database and conducting the efficient approximate nearest neighbor query of image local features. Experimental results show that the proposed method can efficiently reduce the computation complexity and improve the image retrieval efficiency.

image retrieval; local feature; random sampling; feature indexing; scale invariant feature transform; locality sensitive hashing

2014-09-01

国家自然科学基金资助项目(61105058);武汉科技大学大学生科技创新基金研究项目(12ZRA109).

卢艳君(1988-),女,武汉科技大学硕士生. E-mail:1060146221@qq.com

徐望明(1979-),男,武汉科技大学高级工程师,博士. E-mail: xuwangming@wust.edu.cn

TP391.4

A

1674-3644(2015)01-0072-05