基于Bag of words模型的图像检索系统的设计与实现

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于Bag of words模型的图像检索系统的设计与实现范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：该系统将Bag of words模型用于大批量图像检索，基于OpenCV C语言库提取图像的SIFT特征，然后使用Kmeans算法进行聚类，再将其表示成bag of words矢量并进行归一化，实现大批量图像检索，并用caltech256数据集进行实验。实验表明，该系统该系统采用的方法是有效的。

关键词：SIFT; Kmeans; Bag of words;大批量;图像检索

中图分类号：TP311文献标识码：A文章编号：1009-3044(2012)05-1139-03

Based on the Bag of Words of the Model of Image Retrieval System Design and Implementation

SUN Meng-ke, ZHANG Hong-mei

(Henan University of Technology College of Information Science and Engineering, Zhengzhou 450000, China)

Abstract: The system will be Bag of words model used in large quantities of image retrieval, based on OpenCV C library image SIFT fea? ture extraction, and then use Kmeans clustering algorithm, and then it says a Bag of words and vector normalization, realizing mass image retrieval, and caltech256 data set for experiments. Experiments show that the system adopts the method is effective.

Key words: SIFT; kmeans; bag of words; mass data; image retrieval

近年来，随着计算机科学的飞速发展，模式识别技术在社会生活中的应用已经非常普遍，特别是计算机图像识别技术，因为其直观，方便，快速，准确的特点，更是受到了人们的青睐。

目前常用的利用计算机自动检索图像的方法是使用颜色、纹理、形状等全局视觉特征来获得图像内容信息，衡量图像之间的相似程度以实现图像检索。然而，这种方法反映的只是图像的客观统计特性，不能被人的视觉所理解。

本文考虑到图像检索系统的用户是根据图像中的目标来判别图像之间的相似性，因而将目标识别中的典型模型-Bag of words模型引入图像的检索识别领域，提取图像的局部特征来实现图像的匹配检索，一定程度上对图像有了语义方面的理解，也屏蔽了复杂背景对检索结果的影响。

Gabriella Csurka等人[1]首先于2004年在图像处理领域引入了Bag of words模型，提取图像的SIFT特征并用支持向量机对5类图像进行分类，结果表明该模型对复杂背景具有一定的健壮性，并且在不利用几何信息的情况下，也能得到很好的分类效果。

Herbert Bay等人[2]在2006年提出了一种特征提取的快速算法SURF(Speeded Up Robust Features)，通过简化主流的兴趣点检测算子（a Hessian matrix-based measure）和描述算子（a distribution-based descriptor）来实现，并以recall、1-precision为标准同SIFT做了比较，结果显示，SURF在各个方面的性能均接近或超越了SIFT，但是计算速度却是SIFT的3倍左右。

何友松等人[3]在2009年将Bag of Words模型引入汽车图像识别领域，并提出将SIFT特征提取算法和PLSA分类算法结合在一起实现车辆和背景图像分类的思想，实验对比了该算法与Tamura纹理特征算法和Gabor纹理特征算法在车辆图像识别中的效果，结果表明该算法分类正确率优于另外两种方法。

综上所述，目下对于Bag of words模型在图像处理领域中的应用，大都集中在对小批量图像的处理，相应的对于在大批量图像处理中的应用却鲜见于报端。本文将Bag of words模型中的聚类算法改进之后，用于对大批量数据进行聚类，取得了非常好的效果。

1 Bag of words模型概述

Bag of words模型最初被用在文本分类中将文档表示成特征矢量。它的基本思想是假定对于一个文本，忽略其词序和语法、句法，仅仅将其看做是一些词汇的集合，而文本中的每个词汇都是独立的。

简单说就是将每篇文档都看成一个袋子（因为里边装的都是词汇，所以称为词袋，Bag of words即由此来)，然后看这个袋子里装的都是些什么词汇，将其分类。如果文档中猪、马、牛、羊、山谷、土地、拖拉机这样的词汇多些，而银行、大厦、汽车、公园这样的词汇少些，我们就倾向于判断它是一篇描述乡村的文档，而不是描述城镇的。

与之类似，我们也可以将图像当成一些图像片段（image patch―本文中用SIFT特征来描述）的集合。譬如构成一幅人脸图像的图像片段必定倾向于描述人的眼睛、鼻子、耳朵、嘴巴这些事物（我们称这些事物为视觉词汇）。

现在假设要使用Bag of words模型从一批训练图像中检索出与测试图像最相似的图像，我们要做的工作主要都有哪些呢？

首先要对训练图像集进行预处理。包括图像增强、分割、图像同一格式、同一规格的处理等等。

其次提取图像的SIFT特征。即将每一幅图像划分成很多个图像片段，每一个图像片段都用一个128维的SIFT描述子矢量来表示。

再次聚类生成视觉词，构建码本。一幅图像的码本是由两部分组成的，视觉词以及与其对应的SIFT描述子矢量的数目，即词频。假设码本包含k个视觉词序列，将上步中所有的SIFT描述子矢量用Kmeans聚类生成k个簇，最终这k个簇中心即为码本的k个视觉词。然后计算每幅图像中每个SIFT描述子到这些视觉词的距离，若其距离某个视觉词最近，就将其映射到该视觉词，并将该视觉词对应的词频数增1。直至将所有的SIFT描述子都映射到码本中，将每幅图像都用一个与视觉词序列相对应的词频矢量来描述，这个词频矢量即为相似度检索时所要使用的图像的Bag of words特征矢量,另外，由于每幅图像所包含的SIFT矢量的数目是不确定的，还需要对Bag of words特征矢量进行归一化。

最后计算图像距离相似度进行检索。测试图像也要经过预处理，提取SIFT特征，生成码本矢量并进行归一化的过程，然后计算其与训练码本的距离，并将此距离相似度按升序排列。

2图像特征提取

2.1 SIFT特征提取

SIFT算法由D.G.Lowe在1999年[4]提出，并于2004年[5]完善总结。SIFT算法是一种提取局部特征的算法，在尺度空间寻找极值点，提取位置，尺度，旋转不变量,从而使其对旋转、尺度缩放保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。

高斯卷积核是实现尺度变换的唯一线性核，于是一副二维图像I()

x,y的尺度空间定义：L(x,y,σ)=G(x,y,σ)?I(x,y),其中G(x,y,σ)=

x,y是空间坐标，反映像素的位置；σ是尺度坐标，决定图像的平滑程度。

为了在尺度空间检测到稳定的关键点，需要计算高斯差分尺度空间（DOG scale-space）：

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

DOG算子计算简单，是尺度归一化的LOG算子的近似。

在检测极值时，需要跟其周围邻域同一尺度的8个像素和相邻尺度对应位置的9×2个像素进行比较，以确保在尺度空间和二维图像空间都检测到局部极值。

关键点的方向参数是利用关键点邻域像素的梯度方向分布特性为其指定的。以关键点为中心在其邻域窗口内采样，并用直方图统计邻域像素的梯度方向，直方图的峰值就作为该关键点的主方向。如图1，图2所示。

图1关键点主方向示意图

图2一幅测试图像

特征描述子生成时，选取以特征点为中心的16*16邻域作为采样窗口，将采样点与特征点的相对方向通过高斯加权后归入包含8个bin的方向直方图，最后获得4*4*8（128维）的特征描述子。

2.2 Bag of words特征表示

SIFT特征虽然也能描述一幅图像，但是每个SIFT矢量都是128维的，而且一幅图像通常都包含成百上千个SIFT矢量，在进行相似度计算时，这个计算量是非常大的，通行的做法是用聚类算法对这些矢量数据进行聚类，然后用聚类中的一个簇代表Bag of words中的一个视觉词，将同一幅图像的SIFT矢量映射到视觉词序列生成码本，这样每一幅图像就只用一个码本矢量来描述，这样计算相似度时效率就大大提高了。

Kmeans算法是数据挖掘技术中基于分裂法的一个经典的聚类算法，因其理论可靠、算法简单、收敛速度快而被广泛应用[6]。

该算法采用迭代更新的思想，常规的思路是先将要参与聚类的特征数据载入内存，然后随机选择K个对象对聚类中心初始化

123, , ,...,K c c cc --初始化过程，再对剩下的每个对象ix（i =1，2，3，…，n)根据其与各个簇中心的距离（本文取欧氏距离）将它赋给最近的簇（m是特征数据的维数）--映射过程：

然后重新计算每个簇的均值作为下一次迭代的聚类中心―更新类中心：

cj=

xi∈sjxi，其中Nj为第j个簇sj中的对象数目即Kmeans算法需要进行初始化，映射和更新类中心3个过程，其中后两个过程要不断重复，直到所有类中心都不再变化为止， 最后得到的类中心就是Bag of words模型所需要的视觉词（visual words）。然后将每幅图像中的每个SIFT描述子都映射到某个视觉词，得到的词频序列就是该幅图像的码本矢量。

但是当数据量比较大时，该思路实现的聚类算法在运行过程中很可能会因内存分配不足而崩溃。为了保证程序平稳运行，笔者采用分批载入，整体聚类的思想实现该算法。每次载入SIFT特征数据时限定数量，将所有SIFT特征数据分成有数的几批分别载入内存，然后处理一批，释放一批。

即在映射过程中，计算每个批次中每一个SIFT矢量到各个簇中心的距离，记录下与其距离最近的那个簇的标号，就将那一批SIFT数据从内存中释放掉。在更新类中心的过程中同样如此，载入一个批次的SIFT后，读取该批次对应的SIFT类标号，将相同类标号的SIFT相加求和，然后释放，求和完毕之后，再求平均，得到新的类中心，这样分批载入的思想就解决了程序运行过程中可能出现的内存分配不足的问题。

3系统实现

本软件主要采用C++语言在vc++6.0平台下开发，基于OpenCV C语言库提取图像的SIFT特征，使用Bag of words模型将它表示成特征矢量，最后计算测试图像的码本矢量与训练图像的码本矢量之间的距离实现图像检索。

SIFT特征提取模块主要基于OpenCV开源库提供的API，使用C语言编写。涉及到的主要数据结构为feature，其属性主要包括：位置（x,y）、方向（orientation）、尺度（scale）、描述子矢量（double数组），所在文件为：sift.c和sift.h。

Bag of words表示模块主要利用Kmeans聚类算法生成视觉词，然后统计每幅图像上某个视觉词汇出现次数，最后通过归一化将它们转换为特征矢量；该模块对应的类文件为：BagWords.h和BagWords.cpp。

Kmeans算法实现的功能主要是：

数据存储模块在本软件的设计中占有重要地位，它直接为特征提取模块和Bag of words表示模块提供支持，下面将要介绍它的主要成员变量：

1）特征矢量Mat类_X：它是stl的vector容器，装有double型的指针，因此它的特征是：支持动态地增加double型的数组。由于每幅图像产生的SITF特征的数目不固定，因此我们在处理每幅图像时，需要逐步地将每个SIFT特征加入vector。

2）标号矢量Mat类_y：同上，每副图像关联到一个double数组而不是一个标量，可以存储多个标号，如对于每个SIFT特征而言，我们需要同时存储它所在的图像索引号和类别索引号。

3）图像路径映射表map类_image_map：string到string的映射表，主要将图像索引号与其路径建立一一对应关系，便于程序进行处理。

4）其他：mat文件数据是模块自定义的一种简单的数据格式，第一行为数据矩阵的行数和列数，其他行为数据，每一行为一个样本，数据均以float型数据读入；程序通过map来存储命令行的参数和参数值，并且作为全局变量供所有的程序访问，因此，我们可以在所有的类中使用我们所需的任意参数值（对于整数和浮点数需要通过系统函数进行转换_atoi等）。

4实验及分析

目前常用的的图像数据集主要有：Caltech-101，加州理工学院101类图像数据库，每类有40-800幅图像，每幅图像大小约为300*200像素；Caltech-256，加州理工学院256类图像数据库,包含256类共30607幅图像；Pascal数据集是为每年一次的voc竞赛精心准备的数据集，voc2011数据集，包含20类共1万多幅图像；此外还有TU Darmstadt数据集，MIT-CSAIL数据集等。

本文使用caltech-256数据集，在CPU型号为酷睿i5 750，内存容量为2G，操作系统为windows XP的机器上进行训练。将30607幅图像分批载入内存，提取超过1680万个SIFT特征，记录下每幅图像的索引序号和索引路径以及每个特征矢量对应的图像标号，并按批分文件保存到硬盘中，共用时13982.74秒。

然后分别读取每一批的数据进行kmeans聚类。测试时随机选取5幅图像做实验，提取SIFT,并映射到视觉词序列生成码本，分别计算这些码本到训练图像码本的距离，按升序进行排列，并查询图像标号与路径索引表，最终得到5幅图像的查全率与查准率如表1所示。

表1实验结果

该实验结果表明：

1)特征提取速度和检索速度非常快，一副图片的检索的总时间大概为1秒，调整系统的参数和采用其他聚类及检索算法，可以进一步改善系统的性能。

2)系统的可靠性较好，可以处理caltech256数据集的3万多幅图像文件，得到1600多万的特征，但是仍然不会出错。

3)图像旋转、尺度缩放、亮度变化、视角变化、仿射变换和噪声等可变因素影响下，系统的检索性能并没有太大的化。

5结论

经过以上分析，我们可以看到，将Bag of words模型应用于大批量图像检索的思路是正确的，不仅计算量大大减小，而且得到了比较满意的检索效果。但是如果要进一步优化系统性能，还需要做更深入的研究，比如聚类要聚成几类才是最合适的，这个决定最终码本矢量维数的数据对系统性能的影响是可以想见的；另外聚类过程中的时间开销非常大，虽然是在线下运行的，但是有没有可能让时间花费更少一点，让其聚类效果更精确一点呢。

参考文献：

[1] Csurka G,Dance C,Fan L,et al.Visual categorization with bags of keypoints[C].ECCV’04 workshop on Statistical Learning in Computer Vi? sion,2004:59-74.

[2] Bay H,Ess A,Tuytelaars T,et al.SURF: Speeded Up Robust Features[J].Computer Vision and Image Understanding(CVIU),2008,110(3): 346-359.

[3]何友松,吴炜,陈默,等.基于Bag of Features算法的车辆图像识别研究[J].电视技术,2009,33(12):104-107.

[4] Lowe D G.Object recognition from local scale invariant features[C].Corfu,Greece:International Conference on Computer Vision,1999: 1150-1157.

[5] Lowe D G.Distinctive image features from scale-invariant keypoints[J].International Conference on Computer Vision,2004,60(2):99-110.

[6]边肇祺,张学工.模式识别[M].北京:清华大学出版社,2000.