基于词汇树方法的图像检索

曹健健，唐 悦，刘芮辰，王志青

(安徽大学 计算机科学与技术学院，安徽 合肥 230039)



基于词汇树方法的图像检索

曹健健，唐 悦，刘芮辰，王志青

(安徽大学 计算机科学与技术学院，安徽 合肥 230039)

目前SIFT特征提取算法具有较高的时间复杂度，不利于大规模图像检索，提出一种构建词汇树的方法，来缩短用户检索图像的时间。对图像库用SIFT特征提取算法提取特征点，用聚类方法对图像库中的特征点构建一棵三层词汇树，并为每个结点赋合适的权值。接着计算图像库中每张图片与词汇树的距离，这个距离称为索引值，用来唯一表示每张图片。在进行图像检索时，只需计算待检索图片的索引值，通过索引值的匹配来检索图像，可以极大地缩短用户检索图像的时间。

SIFT特征提取；K-Means聚类算法；词汇树；索引值

0 引言

图像检索是计算机视觉的核心问题，也是一个非常值得研究的问题，它的关键在于构建能够适用于不同规模图像库[1-2]的方法，并且可以在有限的时间内检索到最准确的图像。对于传统的SIFT特征提取算法[3]具有很好的鲁棒性和抗干扰性，有着广泛的应用，但是由于SIFT 算子具有很高的维数(128维)，增强了其计算复杂性和时间复杂度，并且在大规模特征图像库[4]的检索中存在存储压力。目前国内外研究学者针对其高维数的缺点，进行了改进和尝试，以求在保持SIFT算子良好特征的前提下，尽量降低其维数。

本文提出的构建三层词汇树的方法在很大程度上是受传统的词汇树构建方法[5-6]的启发，都是通过特征提取和聚类方法来构建词汇树，主要区别在于词汇树[7-8]结点权重的确定方法以及每张图片索引值的计算方法上有所不同。由于构建词汇树的过程是通过线下完成的，不需要占用用户的等待时间，从而提高检索效率。同时，计算图像库中图片的索引值，通过索引值来唯一表示图像，就可以极大地减少图像库的存储压力。本文最重要的贡献是建立了一个索引机制[9]，它可以实现非常高效的检索。

1 构建词汇树方法

1.1 SIFT特征提取

尺度不变特征变换[3](Scale Invariant Feature Transform，SIFT)是David Lowe提出的提取图像局部特征[10-11]的算法，SIFT已被证实在同类描述子中具有最强的健壮性,对平移、旋转、亮度变化和噪声等有良好的不变性。SIFT算法实现过程如下。

1.1.1 构建高斯差分(DoG)尺度空间

首先将高斯核函数G与输入图像卷积构成高斯金字塔：

(1)

L(x,y,σ)=G(x,y,σ)*I(x,y),

(2)

式中，I(x,y)为图像I上的点，L为尺度空间，σ 为尺度空间因子。

在高斯金字塔的基础上，利用同一阶的2个相邻的2层的尺度空间函数之差得到DoG金子塔：

D(x,y,σ)=(G(x,y,kσ)-G(x,y,σ))*I(x,y)=

L(x,y,kσ)-L(x,y,σ) 。

(3)

1.1.2 特征提取的4个步骤

(1)尺度空间极值点检测

待检测点在由图1中26个圆点构成的邻域中进行比较，如果该检测点为最大值或最小值，则该点为候选关键点。图中*表示待检测点。

图1 尺度空间极值点的确定

(2)对粗特征点的过滤和精确定位

首先，剔除低对比度点，特征点的像素必须是与周围的点有明显的差异；其次，去除边缘点，有助于提高抗噪声能力。

(3)为特征点分配方向值

利用关键点邻域像素的梯度方向分布为每个关键点指定主方向，公式如下：

(4)

(5)

式中，m为(x,y)处的模值，θ表示方向，L为所在的空间尺度函数。采用梯度方向直方图法，以梯度模m作为权重，选择主峰值作为特征点的主方向，局部峰值作为辅助方向。

(4)生成SIFT特征向量

首先将坐标轴旋转为关键点的方向，以关键点为中心取8*8的窗口，每个小格代表所在尺度空间的一个像素。图中心点为关键点。图中圆圈代表高斯加权的范围(越靠近关键点的像素梯度方向信息贡献越大)。在4*4的小块上计算8个方向的梯度方向，绘制其累加值，最后将特征向量长度归一化。

图2 图像梯度及特征向量生成

1.2 K-Means聚类算法

聚类[12]就是按照某个特定标准把一个数据集分割成不同的类或簇，使得聚类后同一类的数据尽可能聚集[13]到一起，不同数据尽量分离。K-Means聚类算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。

k-means算法的处理过程如下：首先，随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心；对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。通常，采用平方误差准则，其定义如下：

(6)

式中，E为数据库中所有对象的平方误差的总和，p是空间中的点，mi是簇Ci的平均值。

1.3 构建词汇树具体步骤

词汇树[7-8]用来唯一地表示一个图像库，它是基于对图像库中的所有特征点进行聚类构造出来，并根据特征点的密集程度[7]为每个聚类中心分配不同的权重。

词汇树的具体构造步骤如下：

① 利用SIFT特征提取方法将图像库中的图片进行特征提取,并保存每张图片的特征点；对图像库中的所有特征点[2-3]利用K-Means聚类算法构建最底层的叶子结点(64个)，根据每个结点上特征点的个数分配不同的权重；

② 对底层的叶子结点利用K-Means聚类算法构建中层叶子结点(16个)，结点权重的分配方法与上述相同；

③ 对中层叶子结点再次聚类，这样就构建出一个三层的词汇树并且每个结点都有相应的权重。权重的分配方法如下：

Wi,j=(maxi-nri,j)/maxii=1,2,3，

(7)

式中，Wi,j为词汇树第i层第j个结点的权重，maxi为结点中包含最多特征点的个数，nri,j为第i层第j个结点上特征点的个数。图3为建立的词汇树模型。

图3 词汇树模型

2 基于词汇树的图像检索算法

通过对大型图像库[4-6]的特征点进行训练，利用K-Means聚类算法构建出词汇树[7-8]，接下来就是利用构建出的三层词汇树对图像进行检索。具体做法如下：首先可以先计算出图像库中每张图片的特征点相对于词汇树各个结点(聚类中心)之间的距离，这个距离作为每张图片的索引值[8-9]，称之为图片索引。这样图像库中每张图片就具有唯一的一个索引值，计算索引值可以通过线下处理。用户在进行图像检索过程中只需将待检索图片的索引值计算出来，与图像库中每个图片的索引值进行比较[14]和排序[15]，将排序后的图片再进行筛选，选出最接近待检索图片索引值的图片，即为检索到的图片。

索引值的计算方法如下：首先，计算图片的每个特征点到词汇树的各个结点之间的距离；距离计算公式：

(8)

式中，di,k为图片的第i个特征点与词汇树的第k个结点之间的距离，xi为图片的第i个特征点，yk为词汇树的第k个结点。接着，找出距离最短的下标k，则该特征点属于词汇树的第k个结点；统计图片所有特征点属于词汇树各个结点的数目num1*m，可以得到一个矩阵；将该矩阵与词汇树的权重矩阵weightn*1相乘，就可以得到该图片相对于词汇树的索引值。

3 有效性分析

3.1 实验中的图像库

本次实验采用的图像库中含有170张图片，每张图片的大小约为500*500像素，图片可以分为50组，图片的主题为人行走时的状态。图片记录了不同人物在不同的背景下行走时的姿态，由于人物行走时的姿态具有很大的相似性，检索中的特征点相似程度[16]比较高，所以对于实验的算法要求就比较高，对实验方法的验证具有很好的有效性。

3.2 实验数据

在构建词汇树的过程中，会产生一些非常重要的数据，这些数据对于成功构建词汇树至关重要，对于图像检索的准确性具有很大的影响，本次实验数据如表1所示。对于大规模图像库，所提取特征点的个数更多，所建立的词汇树模型的层次也可以适当的增加。表中，centers1、centers2、centers3为3次聚类的聚类中心；centers 表示聚类中心；k1、k2、k3 为各级聚类的个数；tezheng向量用来存储每张照片特征点；cid表示每个数据属于哪一类，nr表示每一类的个数。

表1 构建词汇树的参数和图像库的索引值

3.3 数据分析

3.3.1 SIFT算法的时间复杂度分析

实验中统计了每张图片用SIFT特征提取算法提取的特征点的个数以及所用的时间，从中抽取若干数据进行分析，统计特征点个数与提取时间的关系，如图4所示。可以发现图片提取的特征点与提取时间基本成线性增加，从而验证了SIFT算法具有较高的时间复杂度O(N)。

图4 图像特征点个数与提取时间的关系

3.3.2 基于词汇树的检索过程

① 输入待检索图像，如图5所示。

图5 待检索的图像

② 检索图像过程，如图6所示。

图6 图像检索程序的过程

③ 检索结果如图7和图8所示。

图7 检索到第1张图片(最相似)

图8 检索到第2张图片

3.3.3 实验结果分析

在本次实验之前，同样进行了传统SIFT特征特征提取，利用特征点的高斯距离来进行检索图像，但是由于SIFT算法具有较高的时间复杂度，提取过程就非常耗时，同时距离匹配的计算也十分耗时，容易出现超出内存的现象，实验的结果不是很理想。对于本文提出的利用词汇树检索图像的方法，从实验的结果来看，检索一张图片的时间大约是1 min，并且检索的结果也十分准确。

4 结束语

利用传统的SIFT算法进行图像检索，需要计算图像库中每张图片的特征点与待检索图像特征点之间的距离，再进行排序检索，此算法耗时严重。而构建词汇树的方法，可以将图像库的建树以及每张图片索引值的计算通过线下处理完成，用户只需要计算待检索图像的索引值，根据索引值进行检索，算法的时间复杂度大大减少，可以很快速检索到用户所需的图片。

[1] Lowe D.Object Recognition from Local Scale-Invariant Features[C]∥International Conference On Computer Vision,Corfu,Greece,1999:1150-1157.

[2] Lowe D.Distinctive Image Features from Scale Invariant Keypoints[C]∥ Computer Science Department University of British Columbia ,Vancouver B C,Canada,2004:91-110.

[3] Vedaldi A. An Implementation of SIFT Detector and Descriptor[D]. Los Angeles :University of California,2010 .

[4] Zhou W,Lu Y,Li H,et al. Scalar Quantization for Large Scale Image Search[C]∥Conference Proceedings of the 20th ACM International Conference on Multimedia,Japan,2012:169-178.

[5] Cai Y,Tong W,Yang L,et al.Constrained Keypoint Quantization: Towards Better Bag-of-words Model for Large-scale Multimedia Retrieval[C]∥ACM International Conference on Multimedia Retrieval,Hong Kong,China,2012:1-8.

[6] Zheng L,Wang S,Liu Z,et al.Lp-norm IDF for Large Scale Image Search[C]∥IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Springer,2013:1626-1633.

[7] Jégou H,Douze M,Schmid C.On the Burstiness of Visual Elements[C]∥IEEE Conference on Computer Vision and Pattern Recognition,Miami,2009:1169-1176.

[8] Wang X,Yang M,Cour T,et al.Contextual Weighting for Vocabulary Tree Based Image Retrieval[C]∥IEEE Intetnational Conference on Computer Vision,Barcelona,2011:209-216.

[9] Zhang X,Li Z,Zhang L,et al. Efcient Indexing for Large Scale Visual Search[C]∥IEEE Intetnational Conference on Computer Vision,USA,2009:761-768.

[10]Zhou W,Lu Y,Li H,et al.Spatial Coding for Large Scale Partial-duplicate Web Image Retrieval[J].Journal of Computer Science & Technology,2014,29(5):837-848.

[11]Ke Y,Sukthankar R. PCA-SIFT: A More Distinctive Representation for Local Image Descriptors[C]∥Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition,Washington,2004:506-513.

[12]汪海波，张海臣，段雪丽．基于MATLAB的自组织竞争神经网络聚类研究[J]．邢台职业技术学院学报，2005，22(1)：45-47．

[13]Yuan X T,Yan S.Visual Classification with Multi-task Joint Sparse Representation[C]∥In Proc. IEEE Conf. Comput. Vis. Pattern Recognit,2010:3493-3500.

[14]Sivic J,Zisserman A.Video Google: A Text Retrieval Approach to Object Matching in Videos[C]∥In Proc. 9th Int. Conf. Com-put. Vis.,Nice,France,2003:1470-1477.

[15]Fagin R,Kumar R,Sivakumar D.Efficient Similarity Search and Classification Via Rank Aggregation[C]∥In Proc. ACM SIGMOD Int. Conf. Manage. Data,San Diego,CA,USA,2003:301-312.

[16]Jaccard P.The Distribution of the Flora in the Alpine Zone[J].New Phytologist,1912,11(2):37-50.

Image Retrieval Based on Vocabulary Tree Approach

CAO Jian-jian,TANG Yue,LIU Rui-chen,WANG Zhi-qing

(School of Computer Science and Technology,Anhui University,Hefei Anhui 230039,China)

The SIFT feature extraction algorithm has higher time complexity,which is disadvantageous to large-scale image retrieval. In view of this problem,this paper puts forward a new method of constructing vocabulary tree in order to shorten the user time of image retrieval. In this method,firstly the feature points are extracted from image library by using SIFT feature extraction algorithm,these points are clustered by clustering method,a three-layer vocabulary tree is constructed,and the appropriate weights are assigned to all nodes After constructing a complete vocabulary tree for the image library,the distance between the vocabulary tree and each image in image library is calculated,and this distance is called as index value and used to represent each image uniquely. In image retrieval,only the index values of images to be retrieved are necessary to calculate,and the image retrieval is performed by matching the index value of the image library. This method can greatly shorten the user time of image retrieval.

SIFT feature extraction; k-means clustering algorithm; vocabulary tree; index value

2017-05-18

安徽大学大学生创新项目(J10118515624)

曹健健(1996—)，男，本科生，主要研究方向：基于内容的图像检索。唐悦(1996—)，女，本科生，主要研究方向：模式识别。

10. 3969/j.issn. 1003-3114. 2017.05.17

曹健健，唐悦，刘芮辰，等.基于词汇树方法的图像检索[J].无线电通信技术,2017,43(5):77-81.

[CAO Jianjian,TANG Yue,LIU Ruichen,et al. Image Retrieval Based on Vocabulary Tree Approach[J].Radio Communications Technology,2017,43(5):77-81.]

TP391

A

1003-3114(2017)05-77-5