基于SIFT特征和颜色融合的图像检索方法
2013-04-03董傲霜宋宏亮
董傲霜,宋宏亮
(东北大学软件学院,沈阳110004)
基于内容的图像检索CBIR(Content-based Image retrieval)[1],属于图像分析的一个研究领域,目的是在给定查询图像的前提下,依据内容信息或指定查询标准,在图像数据库中搜索并查找出符合查询条件的图片。传统的图像检索是基于文本标注的。其基本原理是通过对图像进行人工文字注解,利用文本关键字进行检索以实现对图像的查找。而基于内容的图像检索是图像特征相似性匹配检索,系统内的图像标识是图像特征描述,检索线索是一目了然的图像示例,输入为图像示例,输出为所有与示例特征相同或相近的图像,按相似程度排序,供用户选择。实际上,把一般用户难以完成的图像特征描述、提取与识别等难题交由系统解决。CBIR是一门有关图像特征相似性匹配的新技术。它利用图像的内容,如颜色、形状、纹理以及空间关系等特征,建立图像的特征矢量检索图像[2]。当用户进行图像检索时,系统把查询图像作为检索条件提交给系统,通过提取查询图像的特征向量,在图像库中检索与特征向量相匹配的图像,将结果集返回给用户。图像的颜色具有稳定性强,旋转不变形,复杂背景健壮性好及计算简单等特点。颜色特征成为描述一幅图像最简便而有效的特征。但单纯依靠描述图像颜色特征进行匹配不能达到理想的准确程度,而SIFT特征提取能较好地处理局部点特征,应用SIFT特征可得到很好的匹配效果。基于这种思想,本文提出一种基于图像颜色特征和局部点特征相结合的检索算法。通过实验和结果分析,验证了算法的有效性。
1 图像检索系统的设计
本文实现一个基于Web的小型CBIR系统。系统采用C语言实现图像特征提取和特征向量匹配,采用php抓取网络图像、客户端上传查询图像以及展现检索结果等。系统可分为三个主要模块:爬虫模块、特征提取及入库模块和用户查询模块,模块划分如图1所示。
图1 系统模块划分Fig.1 Partition of system model
从图1中可以看出,这三个模块是系统的核心。各个模块的功能如下。
①爬虫模块:将网络上的图像批量下载到本地,这些图像作为服务器端图像库。
②图像特征提取及入库模块:对图像库中的图像进行特征抽取及把这些图像特征放入数据库,并通过k-means算法对颜色特征进行聚类。
③用户查询模块:将查询图像转化为查询向量,并根据查询向量与数据库中特征向量的相似度大小按序输出结果。
2 颜色和SIFT特征融合的检索算法
算法采用基于RGB颜色空间的灰度直方图和SIFT描述符综合描述图像内容,一方面充分利用颜色直方图特征提取计算量小和相似度计算简便的优势,把颜色直方图作为辅助特征,实现快速粗检索,缩小检索范围;另一方面利用SIFT描述子能充分描述图像空间信息,并且对图像的旋转、尺度等变化具有很高的鲁棒性的优势,把SIFT特征作为主特征,在粗检索得出的中间集上进行细检索,查询图像匹配SIFT特征,得出相似度,最后根据相似度进行从大到小排序,得到最后结果集。
2.1 特征提取
2.1.1 基于灰度直方图的颜色特征提取
在颜色检索中,颜色直方图是最通用的颜色特征表示形式,它运用了统计学的方法,体现了三个颜色通道分布密度的联合分布概率。本文将彩色图像转化为灰度图像,将RGB三个分量变成一个灰度分量,再用颜色空间量将原来庞大的直方图下降到可接受的程度。
给定一幅图像(fxy)M×N,fxy表示像素点(x,y)处的颜色值,M×N表示图像的尺寸,图像所包含的颜色集记为C,则图像的颜色直方图可表示为
得到图像的颜色特征为32维特征向量,可表示如下:
2.1.2 SIFT特征提取
SIFT特征提取可分解为两个子模块,即检测特征点模块和生成特征描述符模块[3]。SIFT算法的主要步骤为:
①构建高斯尺度空间和高斯差分尺度空间;
②检测特征点;
③确定稳定特征点;
④确定特征点主方向;
⑤生成特征点描述符;
⑥匹配特征点。
由于SIFT特征描述符是基于特征点邻域像素梯度变化的,所以对于特征点而言,邻域窗口内像素的梯度变化越大,特征描述符的独特性就越好,进行描述符匹配时正确匹配的概率就越高。因为Harris角点的邻域窗口内像素具有显著的梯度变化,因此本文使用Harris角点对SIFT特征提取算法进行改进。算法首先按照传统SIFT算法在像素点邻域内检测极值点,接着在极值点邻域内检测该极值点是否是Harris角点,如果是角点,则保留该极值点为特征点,否则直接丢弃该极值点。
不同的尺度空间上角点检测公式为
式中:σ1是积分的尺度;σs是特征点所在的尺度。
分别使用传统SIFT和改进的SIFT对同一幅图像检测特征点,结果如图2所示。
图2 两种算法检测特征点结果Fig.2 Search result of two algorithem
2.2 相似性度量
2.2.1 颜色直方图匹配
对上面得到的图像,使用欧氏距离计算两个颜色特征向量的距离。令Hp(k)和Hq(k)分别为数据库图像p和查询图像q的特征向量,则两图像颜色特征的欧式距离可定义为
特征向量间欧式距离越小,说明相似度越大。
2.2.2 SIFT特征匹配
以两个特征点描述符之间的欧式距离作为特征点匹配的相似度准则。假设特征点对p和q的特征描述符分别为Desp和Desq,则其欧式距离定义为
使用基于 k-d树的近似最近邻搜索算法(Best-bin-first,BBF)在欧式空间中寻找各特征向量的最近邻和次近邻[4],比如寻找特征点p欧式距离最近和次近的两个邻居特征点q'和q″,然后计算p与q'及p与q″两组描述符之间欧氏距离的比值。如果小于规定的某个阈值,则认为匹配成功,接受点对(p,q')为一对匹配点;否则匹配失败。本文取阈值为0.45。
设Nq和Np分别表示查询图像q和数据库图像p提取的特征点个数,应用BBF算法得到图像q和p匹配特征点个数为N_of_Mateched,则定义查询图像q和数据库图像p的相似度为
3 计算结果与比较
实验图片集大致分为三类:人脸图片、自然景物和同一物体仿射变换处理后的图像。选取其中32幅具有代表性的图片作为查询图像。
图3是本文算法对某一自然景物图像的检索返回结果,图4是本文算法对一幅建筑物图像检索的返回结果。其中左边的图像是查询图像。图中只列出了结果的第一页,也就是最相似的图像。其中包括图像及与目标图像的相似度。
图3 基于本文算法自然景物检索结果Fig.3 Search result using color characteristics
图4中采用本文算法返回的前10张图像都是相似图像,唯一的瑕疵是第7位和第4位位置应该互换。
图4 基于本文算法建筑物检索结果Fig.4 Search result using method of this article
①查全率和查准率。
本文采用查准率/查全率作为系统性能评价准则。结果为1表示最优检索,0表示最差检索,其定义如下所示:
式中:Pn,Rn分别表示查准率和查全率,tp表示返回的相关图像个数,n表示相关图像个数,k表示返回图像个数。
32次检索结果的平均查准率Pn和查全率Rn如表1所示,在表1中,A1表示基于颜色直方图算法,A2表示本文算法,A3表示基于SIFT特征算法。
表1 三种算法的查全率和查准率Table 1 Recall rate and precision of three algorithms
所有检索结果的查全率和查准率如图5和图6所示。
图5 算法对三类图像的查全率Fig.5 Recall rate of algorithm on three types of image
图6 算法对三类图像的查准率Fig.6 Precision of algorithm on three types of image
基于颜色直方图算法的检索能力很差,基于SIFT特征算法的检索能力则非常强,拥有超过0.9的查全率和查准率。而本文算法的检索能力比基于SIFT特征算法略弱,但查全率和查准率也在超过了0.8。
②检索响应时间。
搜索引擎的检索响应时间是指系统平均完成一次检索的耗时,可用如下表达式描述:
式中:T表示平均检索时间;n表示检索次数;tn表示n次检索响应时间总和。3种算法对于32次检索所需时间如图7所示。
图7 三种算法的查询响应时间Fig.7 Query response time of three algorithms
对于图像库中存在500幅图像规模,基于颜色直方图算法每次检索所需时间最短,平均检索时间3.5 s左右;基于SIFT特征算法最长,平均大于60 s,大大超过了用户的忍耐度;本文算法居中,平均检索时间为12 s左右,这是因为算法先使用颜色特征过滤了大部分数据。
4 结论
本文提出了一种融合颜色特征和SIFT特征的图像检索算法。算法使用颜色特征匹配缩小检索范围,得到一个中间集合;对中间集合应用SIFT算法,得到最终结果集和匹配的相似度。结果表明,算法综合检索能力良好,查全率和查准率远高于单独使用颜色特征算法,而平均检索响应时间远低于单独使用SIFT特征检索算法,对同一物体经过旋转、尺度缩放、平移等处理后的图像表现出很好的检索能力,该多特征融合算法是切实可行的。
[1]Niblack W.The QBIC project:Querying image by content using color,texture and shape[C]∥SPIE,1993: 173-187.
[2]周明全,耿国华,韦娜.基于内容图像检索技术[M].北京:清华大学出版社,2007.
[3]Riepe W,Steller M.Characterization of coal and coal blends by automatic image analysis[J].Fuel,1984,63 (3):313.
[4]Zhan Hong-liang,Zhong Di.A scheme for visual feature based image retrieval[C]∥Proc SPIE Storage and Retrieval for Image and Video Database,1995.