张磊磊　陈丽芳

摘 要：由于SIFT特征点能对图像局部特征进行合理、精确描述，有效使用SIFT特征点实现基于内容的图像检索成为当前计算机视觉领域中的热点问题。针对该问题，提出一种基于SIFT特征点的改进聚类的图像检索新方法。该方法包括图像颜色转换、特征点改进聚类算法，以及基于该算法的更有效的灰度直方图构建方法。与现有基于流光法的检索方法相比，该方法能有效解决聚类后特征点分组不确定和依赖特征点颜色信息和空间信息权重的问题。从公共图像库上的实验结果可以看出，该方法与现有方法相比具有较高的检索精度。

关键词：图像检索；SIFT特征点；聚类算法

DOI：10.11907/rjdk.171512

中图分类号：TP317.4 文献标识码：A 文章编号：1672-7800（2017）009-0188-04

Abstract：Because SIFT feature points can represent the local feature of images effectively and accurately， how to realize content-based image retrieval by SIFT feature points is a hot issue in the computer vision. So， a novel image retrieval method based on the improvement combinatorial clustering of SIFT feature points is proposed. The proposed method consists of image color space transformation， improvement combinatorial clustering algorithm of SIFT feature points and effective local color histogram building approach. Compared with existing methods based on FLOW feature points and local color histogram， the proposed method can solve the problem that uncertain sets of feature points after clustering and existing methods are sensitive to the weight of position and the color of feature points. According to experimental results on public image database， it can be seen that the proposed method is more effective than existing methods.

Key Words：content-based image retrieval； SIFT feature points； improvement combinatorial clustering

0 引言

基于內容的图像检索一直是计算机视觉领域的研究热点[1-2]，其实现主要是通过抽取图像特征来表示图像内容，通过计算特征间的相似性来表示两幅图像是否相似，从而找出与检索条件最为相似的图像。近年来，基于特征点的局部特征能有效描述图像内容[4]，因此被广泛应用于图像检索中。

在已有特征点的基础上，再通过局部颜色直方图，既可实现对像素点颜色进行取值统计，又不会忽略像素点的空间分布特征。基于特征点组合聚类图像检索方法的主要思想是根据视频流光算法或者SIFT算法得到图像的特征点；然后根据聚类的思想[3]对特征点的颜色和空间位置进行聚类分组，得到一系列特征点集合；每个集合构建一个局部颜色直方图，通过计算局部颜色直方图之间的距离来表示图像间的相似性[4]。虽然这种方法具有一定的有效性，但仍存在以下问题：①图像特征点聚类分组依赖像素点的颜色信息和空间信息，颜色信息和空间信息权重对结果的影响很大；②图像特征点聚类后特征点分组结果不确定，计算图像的相似度时影响比较大；③计算图像相似性时，局部直方图的距离算法没有充分考虑特征点分组后的空间信息；④在聚类和匹配过程中没有对算法进行优化，匹配速度较慢。

针对上述存在的一些问题，本文基于SIFT特征点的空间信息聚类方法，在聚类时不用考虑颜色信息和空间信息的权重问题，而且匹配结果是确定的。计算图像相似性时，充分考虑分组后直方图的空间信息，同时对聚类和局部灰度直方图匹配算法进行了一定的优化。实验结果表明，本文方法具有一定的有效性和速度优势。

1 基于SIFT特征点改进聚类的检索方法

SIFT算法由DAVID G L于1999年提出[5]，并于2004年进行了发展和完善[6]，MIKOLAJCZYK[7]对多种描述子进行实验分析，结果证实了当图像进行旋转、平移、尺度缩放、仿射变换时，SIFT特征具有很好的稳定性和鲁棒性。

基于SIFT特征点改进聚类的检索方法包含5个步骤：①图像颜色转换；②使用SIFT算法提取图像的特征点；③使用改进聚类算法将特征点进行分组；④统计每个分组特征点的灰度值，构建一个灰度直方图，该直方图为图像的局部灰度直方图；⑤根据直方图计算图像之间的距离，返回匹配结果。

1.1 颜色转换

颜色是检索系统中最常用的图像特征。颜色表示模型有很多种，数字图像一般使用RGB表示模型存储其二进制数据，其可分辨色差是非线性的。HSV颜色表示模型是基于人眼对色彩的识别，是一种从视觉角度定义的颜色表示模型。本文在特征点提取之前，首先将图像从RGB模型转为HSV模型。endprint

HSV颜色模型中，H表示色调，S表示饱和度，V表示亮度。RGB颜色表示模型与HSV颜色表示模型之间的转换公式如下：T=arccos（R-G）+（R-B）2（R-G）2+4（R-B）（R-G）

H=T，B≤G

2π-T，B>G

S=max（R，G，B）-min（R，G，B）max（R，G，B）

V=max（R，G，B）255 其中，R，G，B∈[0～255]，由公式得到H、S、V的值，H∈[0～360]，S∈[0～1]，V∈[0～1]。按照上式转换图片颜色模型。

1.2 图像特征點提取

图片颜色转换之后，使用SIFT算法提取图像的特征点。传统SIFT算法主要分为4个步骤：①检测尺度空间极值点；②精确定位极值点；③为每个关键点指定方向参数；④关键点描述子的生成。

SIFT特征点提取时使用OpenCV库中的SIFT算法对图片进行处理，得到特征点后使用聚类算法进行分组。

1.3 改进的聚类算法

传统聚类算法步骤如下：

输入：聚类对象集合A={a1，a2，…，an}，其中每个对象ai由m个特征向量表示，ai=（v1i，v2i，…，vmi）；簇中心数目k（k

输出：k个簇中心。

流程如下：

（1）给出k个初始的簇中心与算法迭代次数的变量t：c1=d1，c2=d2，…，ck=dk

t=0 （2）计算A中每个对象到各簇中心的距离。若ai=（1≤i≤n）与cj（1≤j≤k）的距离值最小，则ai属于第j个簇。

（3）一轮分簇结束后，再计算簇中心，记录k个新的簇中心。

（4）t=t+1，若t

（5）新旧簇中心二者比较，若不相同返回步骤（2）；若相同则算法收敛，算法结束。

传统聚类算法中，初始簇中心是随机选取的，同一个图片特征点在两次聚类后，特征点分组情况是不同的，如图1所示，结果导致最后的检索查全率和查准率不稳定。

针对以上问题，本文方法中，提出了确定聚类初始簇中心的新方法。

计算集合A的中心点，即平均值cm；集合对象A中距离cm最远的对象d1为第一个初始簇中心c1；集合对象中距离c1最远的对象d2为第二个初始簇中心c2；集合对象中距离c1和c2的中心点最远的对象d3为第三个初始簇中心c3；重复上一步直至找到第k个初始簇中心ck。

对特征点进行聚类时，使用像素点的位置信息，若pi表示第i个特征点，有：pi=（xi，yi） 其中，xi，yi表示pi的位置信息。

若聚类对象ai和第j类中心cj分别为ai=（v1i，v2i）和cj=（v1j，v2j），则二者的欧氏距离为：d（ai，cj）=（v1i-v1j）2+（v1j-v2j）2 分组时，本文方法的好处是每次初始化簇的中心是确定的，分类之后的结果是唯一的，图像检索的结果是确定的，而且避免了聚类后结果匹配的不确定性。同时，本文方法计算特征点距离时只考虑空间信息，避免检索结果对权重的依赖。本文算法对同一个图片聚类后结果如图2所示，这说明基于改进聚类算法的检索方法可以克服现有方法中存在的问题。

1.4 相似度计算方法

当一幅图像表示为多个局部颜色直方图时，图像间相似性的计算过程为：计算对应的两个直方图之间的距离，再将多个距离值进行相加，距离值的总和即可用来表示两幅图像间的相似性，该值越小，图像间的相似性越小。

在文献[4]流光子算法特征点组合聚类算法中，通过计算局部灰度直方图之间的欧氏距离，若两个直方图之间的距离最小，则二者存在对应关系。将所有具有两两对应关系的直方图间的距离进行累加，最终得到两个图像间的距离，以此表示两幅图像的相似性，值越小，相似度越大。然而计算过程中会出现一幅图像里多个局部灰度直方图匹配另一个图像里一个局部灰度直方图的情况。如图3所示，在两幅图为不同类别的情况下，由于没有充分考虑局部灰度直方图的空间信息，在计算图像相似性时，局部灰度直方图会发生局部匹配，一部分局部直方图没有参加匹配，导致错误的匹配结果。

为解决这一问题，在本文方法中，使用改进的图像距离计算算法。假设待检索图像与库中的一幅图像可以分别表示为两个直方图的集合：Hi=（h1i，h2i，…，hni）和Hj=（h1j，h2j，…，hnj） 则二者间距离：

d1为Hi和Hj里直方图间欧氏距离最小值，去掉集合中两个匹配最小值的直方图，得到两个新的直方图集合H1i和H1j；d2为H1i和H1j里直方图间欧氏距离最小值，去掉两个匹配最小值的直方图，得到两个新的直方图集合H2i和H2j；重复上述步骤最终得到dn；累加直方图距离得到图像距离D：D=d1+d2+…+dn 图4为从图片库中选择一幅图使用文献[4]中的图像距离计算方法匹配后的结果。由于没有充分考虑图像局部灰度直方图之间的空间信息，匹配结果中出现了错误的匹配。

图5为本文方法检索后返回的前十幅图的结果，由于充分考虑了图像的局部灰度直方图之间的空间信息，较文献[4]中方法，本文方法更具有效性。

1.5 算法优化

图像匹配过程主要分为前期图像预处理和后期图像距离计算并返回结果两部分。前期图像预处理主要包括SIFT特征点提取和特征点聚类分组，后期匹配结果使用K近邻算法返回前K个距离最小的有效值。

针对以上情况，主要从以下两方面进行算法优化：①SIFT特征点提取时，只计算特征点的坐标值，忽略特征点描述信息的计算；②聚类算法和K近邻算法中排序算法占了很大一部分，基于此，提出改进的二分法插入排序算法。

传统二分法插入排序在插入第i个元素时，对前面的0～i-1元素进行折半，先与它们中间的那个元素相比，如果小，则对前半再进行折半，否则对后半进行折半，直到left>right，然后将第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

本文提出的二分插入排序算法是：①在第j个元素成功插入后记录其在有序数组中的位置lj，其中left≤lj≤right；②插入第j+1个元素时，先与第j个元素比较大小；如果小，使right=lj；如果大，使left=lj；③如果right≥left，在left和right之间继续二分查找，否则找到元素待插入位置lj+1；④将lj+1以及后面的元素向后依次移位，将第j+1个元素插入该位置。

通过以上两部分算法优化，可以减少不必要的计算步骤，能够有效提高匹配速度。

2 实验结果对比

为了验证本文方法的有效性，在公共图像库上分别用流光法算法和本文算法来实现图像检索，通过检索结果的比较来验证本文方法的优越性。实验中，所选公共图像库为Simplicity系统评测时所采用的图像库[8]，该图像库包含了取自Corel图像库的1 000幅图像，这些图像来自不同的10个类别，本文为了客观地对两种检索方法进行对比，将图像库中的每一幅图像都作为检索条件，执行一次检索过程，最后统计1 000次检索后的平均检索精度。

整个实验包括两个部分，其中第一部分是比较两种检索方法的平均性能，第二部分比较每一类的检索性能。

实验1 两种检索方法的性能比较

在该部分实验中，每幅图先用SIFT算法提取图像的特征点，然后特征点通过改进聚类算法分配到3个集合中。图像检索结果中，排序靠前的图像往往被视为有效结果。实验中，分别将返回图像的前十到前五十位作为有效检索结果，并计算检索精度来进行性能评价。假设有效结果数目为N，其中正确结果数目为Ne，则检索精度P为：P=（NeN）×100% 如图6所示，基于SIFT特征点改进聚类的平均性能最优，原因在于该算法对特征点的分组更加合理有效。而且本文匹配正確率随着检索结果数量的增加而比较稳定，表明本文对图像间的距离计算方法更合理有效。

实验2 每一类图像的检索性能

利用改进聚类方法对特征点分簇时，只考虑了特征点的空间信息。针对TOP10结果计算检索精度，每类图像所对应的检索精度平均值由表1给出。其中，F-MAX为文献[4]中每类匹配的最大值，F-MEAN为文献[4]中每类匹配的平均值。不难看出，针对大多数类别而言，在使用SIFT算法提取特征点时，仅考虑空间信息时，其平均搜索精度优于使用流光子算法。避免了文献中既要考虑空间信息又要考虑颜色信息，并且检索结果依赖于空间信息和颜色信息之间的权重。

实验二的结果验证了基于SIFT特征点改进聚类的方法中，聚类分组时使用SIFT特征点的空间信息在图像检索中仍然具较好的有效性。为了进一步提高检索性能，适当使用特征点的其它描述信息值得进一步研究。

实验3 检索速度比较

算法优化之前，由于前期SIFT特征点提取与聚类分组和后期匹配的影响，从检索开始到返回结果，耗费时间太长，用户体验较差。

在原来算法基础上通过改良SIFT特征点提取算法和改进的二分插入排序算法。图7结果表明，在不影响匹配正确率的情况下，能有效提高检索速度。

3 结语

基于SIFT特征点改进聚类的图像检索方法，是一种以局部颜色直方图作为图像特征的检索方法。与文献[4]相比，该方法包含3个创新点：①使用SIFT特征点代替流光子特征点；②使用改进的聚类算法；③使用改进的图像局部直方图距离算法；④对匹配过程中算法进行了一定的优化。

本文在公共图像库上进行了实验验证分析，从最终结果的对比分析可以看出，仅仅以局部颜色直方图作为图像特征时，本文方法在检索正确率和检索速度方面要优于现有方法。

在后续研究工作中，为了进一步提高检索性能，可以考虑使用特征点的其它描述信息，并且，在不影响检索性能的情况下，重点考虑进一步提高检索速度。

参考文献：

[1] SMEULDERS A， WORRING M， SANTINI S， et al. Content-based image retrieval at the end of the early years [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（12）：1349-1380.

[2] LEW M S， SEBE N， DJERABA C， et al. Content-based multimedia information retrieval： state of the art and challenges[J]. ACM Transactions on Multimedia Computing， Communications and Applications，2006，2（1）：1-19.

[3] 孙吉贵，刘杰，赵连宇.聚类算法的研究[J].软件学报，2008，19（1）：48-61.

[4] 齐恒，李克秋，申彦明，等.基于特征点组合聚类的图像检索新方法[J].大连理工大学学报，2014（4）：477-481.

[5] DAVID G L. Object recognition from local scale-invarint features[C]. International Conference on Computer Vision，1999：1150-1157.

[6] DAVID G L. Distinctive image features from scale-invariant key-points[J]. International Journal of Computer Vision，2004，60（2）：91-110.

[7] MIKOLAJCZYK K， SCHMID C. A performance evaluation of local descriptors [J].IEEE Transactions on Pattern Analysis，2008.

[8] WANG J Z， LI JIA， WIEDERHOLD G. SIMPLIcity： semantics-sensitive integrated matching for picture libraries[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2001，23（9）：947-963.

（责任编辑：孙 娟）endprint