MicrocomputerApplicationsVol.27,No.5,2011
文章编号：1007-757X(2011)05-0004-04
设计与研究微型电脑应用2011年第27卷第5期
基于一种
SIFT优化算法的图像检索
吴建波，赵建民，朱信忠，徐慧英
摘
要：提出了一种基于优化后的SIFT图像检索算法,该算法采用高斯核尺寸自适应的方法来构建金字塔影像，降低其计算复杂度，然后按照传统步骤进行提取特征。它将一幅图像转换成特征向量的集合,通过计算两幅图像特征向量间的欧氏距离来度量图像间的相似性，并且采用BBF搜索算法来提高检索速度。实验结果表明，该改良后的算法具有尺度、平移、旋转不变性,一定的仿射、光照不变性，以及对特定形状特征目标的检索，无论在时间还是效率上都具有相当的优越性。关键词:基于内容的图像检索;SIFT特征;KEMEL-PCA变换;BBF算法；中图分类号：TP391
文献标志码：A
本文提出了一种基于SIFT优化算法提取图像特征的图像检索算法,并结合KEMEL-PCA变换对该特征向量进行降低向量空间维数,减少计算量。图像间的相似特征向量的搜索由BBF搜索算法实现。文中描述了SIFT特征向量的提取
以及SIFT算法的优化过程,并给出实验来检测该优化算法的
0引言
随着Internet和多媒体技术的迅猛发展，使得人们的信
息来源不再局限于原有的简单文本数据，而是不断扩展到图形图像等多媒体领域。单纯的采用文本形式的数据查询方式很难胜任当今大量出现的基于内容的图像等多种媒体数据的检索。从20世纪90年代初期以来,逐渐形成了基于内容的海量多媒体索引和检索技术。在图像领域中，最有代表性的是基于内容的图像检索(CBIR)，如QBIC，Photobook，VisualSeek和MARS等[1]。
基于内容的图像检索(CBIR)是利用图像本身的信息，通常以图像底层特征(颜色、纹理、形状与结构布局等)的相似性为检索依据,根据每幅图像都有的可比较特征进行检索[2]。检索算法的核心问题是图像的相似度度量和图像的特征描述。但这些基于底层特征的图像检索也有其不足之处。如颜色特征是一种全局特征,它对图像或图像区域的方向、大小等变化不敏感,所以颜色特征不能很好地捕捉图像中对象的局部特征,也不能表达颜色空间分布的信息。纹理特征也是一种全局特征，并不能真实的反映物体本身，并且抗光照，抗反射性较差。正是因为这些底层特征对空间分布已经目标旋转平移尺度十分敏感，并且不能准确地表达场景的信息。图像检索领域急需一种能够对目标进行检索,并且对图像目标亮度、旋转、平移、尺度甚至仿射不变的检索算法。
LoweD.G于2004年改进了他于1999年提出的SIFT(ScaleInvariantFeatureTransform)算法[3]，它是一种提取局部特征的算法:在尺度空间寻找极值点,提取位置、尺度、旋转不变量。YanKe引入主分量分析(PrincipalComponentAnalysis)的方法改进SIFT又提出了PCA-SIFT算法,取得了更好的效果[4]。KrystianMikola-jczyk比较多种匹配算法,总结出：基于SIFT的匹配算法是目前各种图像匹配算法中抗平移、尺度变化、旋转、噪声干扰等鲁棒性最强的匹配算法[5]
。本文就是在这样的基础上提出的。
检索性能。
1
1.1
SIFT算法
SIFT特征点检测
SIFT(ScaleInvariantFeatureTransform）的主要思路是：首先建立图像的尺度空间表示，然后检测该图像尺度空间特征点，定义特征点主方向，最后生成特征向量描述子。采用SIFT方法提取的图像特征具有放缩不变性、旋转不变性，还有一定的抗光照变化和抗视点变换性能。1.1.1检测尺度空间极值点
尺度空间理论最早出现于计算机视觉领域时其目的是模拟图像数据的多尺度特征。Koendetink[6]证明高斯卷积核是实现尺度变换的唯一变换核,而Lindeberg[7]等人则进一步证明高斯核是唯一的线性核。一幅二维图像在不同尺度下的尺度空间表示可由图像与高斯核卷积得到:L(x,y,σ)=G(x,y,σ)*I(x,y)(1)
其中：G(x,y,σ)是尺度可变高斯函数,
G(x,y,σ)=
1
e2
2πσ
(x+y)/2σ
2
2
2
，I(x,y)代表图像。
因此,要提取稳定的具有尺度无关性的特征点,就必须在
图像二维平面空间和DoG(DifferenceofGaussian)尺度空间中同时检测局部极值点。DoG算子定义如下:
D(x,y,σ)=[G(x,y,kσ)G(x,y,σ)]*I(x,y)L(x,y,kσ)L(x,y,σ)
=
(2)
———————————
基金项目：浙江省自然科学基金(Y1101269)，科技计划项目(2008C14063)，浙江省重中之重学科资助作者简介：吴建波（1987-），男，浙江师范大学数理与信息工程学院，硕士研究生，浙江金华，321004；
赵建民（1951-），男，浙江师范大学数理与信息工程学院，教授，博士生导师，浙江金华，321004；朱信忠（1975-），男，浙江师范大学数理与信息工程学院，副教授，硕士生导师，浙江金华，321004；徐慧英（1977-），女，浙江师范大学数理与信息工程学院，副教授，浙江金华，321004
4
MicrocomputerApplicationsVol.27,No.5,2011设计与研究微型电脑应用2011年第27卷第5期
其中：L(x,y,σ)=G(x,y,σ)*I(x,y)为高斯尺度空间。检测DoG空间极值时,需要把关键点与同一尺度的周围邻域8个像素和相邻尺度对应位置的周围邻域9×2个像素总共26个像素进行比较（如图1所示），以确保同时在尺度空间和二维图像空间检测局部极值。所有这样的局部极值点构成了一个SIFT候选关键点的集合。
公式(6)为(x,y)处梯度的模值m和方向θ的求解公式,其中所用的尺度为每个关键点所在的尺度。在实际计算时,以关键点为中心的邻域窗口内采样,并用直方图统计邻域像素的梯度方向。直方图的峰值即代表了该关键点处邻域梯度的主方向在梯度直方图中,当存在另一个相当于主峰值80%能量的峰值时,则将这个方向认为是该关键点的辅方向[8]。一个关键点可能会被指定具有多个方向,这可以增强匹配的鲁棒性。
1.1.4SIFT特征向量生成[4,9]为了以确保旋转不变性，先将坐标轴旋转为关键点的方向，接下来以关键点为中心取16×16窗口,分割成4×4个子区域,在每个子区域上计算8个方向的梯度直方图,绘制每个梯度方向的累加值,即可形成一个种子点,因此,一共可以生成16个种子点,这样对于每个关键点就可以产生一个长度为128的数据,即最终形成一个长度为128的SIFT特征向量。此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响,再继续将特征向量的长度归一化,则可进一步去除光照变化的影响。
图1寻找极值点
1.1.2精确定位极值点
DoG算子会产生较强的边缘响应,因此要通过拟合三维二次函数以精确确定关键点的位置和尺度,同时去除低对比度的关键点和不稳定的边缘响应点,以增强匹配稳定性,提高抗噪声能力。
)在局部极值点空间尺度函数G(x,y,σ
泰勒展开式如下：D(x,y,σ)=D(x0,y0,σ)+
D
T
(x0,y0,σ)
处的2SIFT算法优化
X0
X+
12
2
XT
D
2
0
X
X
(3)
对上式求导,并令其为0,得到精确的位置所示:
2
Xmax。如公式(5)
Xmax=(
D
X0
)12
DX0
(4)
在已经检测到的特征点中,要去掉低对比度的特征点和不稳定的边缘响应点。去除低对比度的点:把公式(4)代入公式(3),只取前两项可得：
D(Xmax)=D+
1D
Xmax
2X0
T
(5)
若D(Xmax)≥0.03,该特征点就保留下来,否则丢弃。去除不稳定的边缘点:一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的曲率,而在垂直边缘的方向有较小的主曲率。主曲率可以通过一个2×2的Hessian矩阵求出。
1.1.3关键点主方向分配
利用关键点邻域像素的梯度方向分布特性为每个关键点制定方向参数,使算子具备抗旋转性。mx(+y)=(Lx(+1,y)Lx(1,y))+(Lx(,y+1)Lx(,y1))
2
2
θ(x,y)=arctan(Lx(,y+1)L(x,y1))/(L(x+1,y)L(x1,y))
(6)
5
2.1尺度空间构造算法优化
图像检索所需的时间要充分考虑使用者的等待时间，正如百度等搜索引擎每次都显示搜索所用时间一样，而SIFT算法本身复杂度较高、参数较多,通常采用的是Lowe[4]的建议值,但这些参数对算法复杂度影响较小。SIFT要应用于数据量较大的图像库时,需要对其计算过程加以优化。
2.1.1尺度空间构造耗时
传统的SIFT算法本身复杂度较高、参数较多、计算费时，最佳参数往往不能统一确定，这给图像检索带来额外的工作成本。KONG等在其文献[10]中统计了SIFT算法各个阶段所需时间占总时间百分比,结果显示构造尺度空间比较耗时，占算法总时间的35%到60%左右。此部分耗时将很大程度影响整个算法所需时间,因此优化空间较大。2.1.2耗时原因
多尺度空间的构建是一个高斯金字塔图像和高斯差分金字塔图像的生成的过程，前者的卷积运算时间远大于后者的代数差运算时间，且卷积时间随着高斯卷积核尺寸和尺度因子增大而增大。同时，图像的平滑程度也直接受制于高斯卷积核尺寸和尺度因子，理论上，高斯卷积核尺寸和尺度因子的值越大，图像的平滑处理效果越好。但是，特征点数目并没有随着模板卷积核尺寸增大而增多[11]。传统算法是采用“固定且数值较大的高斯核尺寸”的方法来构建多尺度空间，若尺寸过小，虽然省时，但平滑程度低，提取的特征点少；若尺寸过大，虽然平滑程度高，但费时，提取的特征点也未必多。为了避免上述情况,争取在较少时间内提取出较多特征点,本文采用一种基于尺度因子变化的高斯核模板尺寸自适应调整办法对多尺度空间做自适应重构，以解决传统
MicrocomputerApplicationsVol.27,No.5,2011设计与研究微型电脑应用2011年第27卷第5期
算法中高斯滤波器核尺寸一成不变的缺陷，保证其随着尺度因子变化时做出自动且最佳的配置。2.1.3自适应算法
通过试验统计发现,随着核尺寸从7×7、9×9逐渐增加到21×21的过程中,检测出的关键点数目在15×15到17×17之间开始出现临界值。虽然所需时间仍不断增加,但关键点数目开始逐渐减少。本文对多组图像进行了试验,结论基本一致。由于篇幅有限,仅列举其中一组试验结果,如表1所示。
表1
不同高斯核尺寸试验结果
结果尺寸7×79×911×1113×1315×1517×1719×1921×21自适应
aGus/ms2331282835575087681069869148101276934
bGus/ms2435239237094494622574599260100466839
aKeys/个1098283432673628374238133730365637
bKeys/个1146325437144003412265411240784134
表1为两幅同一数据库中不同时相的图像(尺寸大小为512像素×512像素)在不同高斯核尺寸下构造高斯金字塔影像所需时间及初始提取特征点数。其中,aGUS、bGUS分别代表两幅影像构建高斯金字塔所需时间,aKeys、bKeys代表各自提取特征点数。试验运行环境:Core2Duo2.20GHzCPU，1.99GB。
在以上多组试验结果基础上,拟合了一次函数,设高斯核尺寸为[x×y],其大小依据每个octave中图像对应的值自适应过程为:
x=y=15，x<17
(7)
x=y=17，x≥17
上式表明，随着高斯卷积核尺寸不断递增且没超过
[17×17]，就以[15×15]作为卷积核模板，否则采用[17×17]。因此本文在传统SIFT算法的基础上,采用自适应高斯核尺寸选择方法，对尺度空间的构建进行了优化，为进一步提高检索速度奠定了基础。
对于这128维的向量来说,要找出数据库图像中与之距离最近次近的向量,其计算量是十分巨大的。为了解决高维空间搜索问题,本文采用的解决方法是:a)KEMELPCA变换降低向量的空间维数;b)利用BBF(BestBinFirst)算法实现图像中最近邻向量的快速搜索。3.1.1KEMELPCA变换
KEMELPCA变换又称为核主成分分析,采用非线性方法提取主成分，是主成分分析的改进算法。离散的KEMELPCA变换是针对向量的变换。设N维的矩阵Y,其均值向量为MY,设KEMELPCA的变换矩阵A是由Y的协方差矩阵的特征向量按特征值递减顺序排列组成的变换核矩阵，则典型的KEMELPCA变换写为：
X=A(Y-MY)(8)
又因为能量集中在特征值λ比较大的系数中,因此在不会影响图像的质量的前提下可以舍弃对应特征值λ较小的X系数。取λ最大的前m个特征向量组成的变换核矩阵,记做Am,则有：
X′=Am(Y-MY)(9)
这相当于原x的m维投影。在本文的实验中,取m=20,这样就使128维的向量降到了20维。3.1.2搜索算法
为了准确匹配特征向量,对于查询图中的每一个SIFT特征向量,需要比较它与查询图中所有特征向量的欧氏距离。为了避免低效的穷举搜索，本文采用BBF(BestBinFirst)来寻找最近邻和次近邻。
BBF的算法是对k-d树搜索算法的改进，主要通过k-d树中叶子节点数来缩短搜索时间。它的基本思想是：当沿一个方向的分支搜索一节点时,优先级队列会被加入一个成员,该成员记录了该节点相关的信息,包括当前节点在树中的位置和该节点与被查询节点之间的距离。当一个叶节点被搜索到后,从队首删除一项;然后,再搜索包括最近节点的其他分支。
3.2定义检索性能指标
若关键点匹配的数量越多，则图像越相似。在本文的实验中，采用匹配百分数来衡量相似程度。本文定义，匹配百分数F=图像匹配的关键点总数/查询图像中总的关键点数量。
若与检索特定图像匹配数量越多，时间越短，则我们可以认为性能越优。本文定义，检索性能指标E=前20幅图像中与特定图像匹配数量/运行时间。
4实验及其结果分析
为了验证算法的有效性，在PC机上进行实验仿真验证，其中运行环境为WindowsXP操作系统，系统配置为Core2Duo2.20GHzCPU，1.99GB内存，仿真平台为Matlab7.0。
实验1中，笔者在一个包含10141幅各类图像的综合图像数据库中进行检索，图像大小均为254×386。库中包含了各类常见的图像，人物、花草、建筑、动物等，每类100多幅相关图片，如图2给出部分实例图。
3图像检索
通过SIFT提取的128维向量很好地刻画了图像的局部内容特征,并且具有很强的局部特征匹配能力。当两幅图像的SIFT特征向量生成后,笔者采用关键点特征向量的欧氏距离作为两幅图像中关键点的相似性判断度量，并采用最近邻
/次近邻法进行图像匹配。
3.1特征向量的匹配
一幅图像中可能需要成千上万的SIFT特征向量来表示,
6
MicrocomputerApplicationsVol.27,No.5,2011设计与研究微型电脑应用2011年第27卷第5期
于文献[12]算法来说有一定的优势，很好的验证了本文SIFT优化算法在检索性能上的进步。
5结束语
图2部分实例图
在实验中返回前十二幅相似程度最高的图像，检索结果按照相似度从左到右，从上到下的顺序排列，如图3所示。
本文针对图像检索领域在图像目标发生一定变化情况下不能很好实现检索问题,提出一种新颖的多尺度图像检索算法,基于SIFT特征提取的图像检索算法。该算法在改进构建金字塔影像构建的前提下，将图像内容转换成128维特征向量的集合,通过计算向量之间的欧式距离实现匹配。
该检索算法有着很大的应用前景,如对电视台台标的检测,给出一个台标图像,就可以精确地查询到数据库中是否有相同的台标;或者应用在饰品行业，如果给定一张包含了某一型号耳环的查询图像,该算法可以以很高的概率在图像库中检索该饰品相关图像。
进一步的研究计划是将图像特征与反馈策略相结合,以寻求更好的检索效果和系统的实用性。
参考文献：
[1]
沈兰荪,张菁,李晓光.图像检索与压缩域处理技术的研究[M].北京:人民邮电出版社,2008.
[2]宋涛,.一种基于内容的文档图像检索方法[J].
郑州大学学报(工学版).2010.31(1).
[3]DavidG.Lowe,ObjectRecognitionfromLocal
Scale-InvariantFeatures[C]//SeventhInternationalConferenceonComputerVision(ICCV'99)-Volume2,Greece,1999.
[4]DavidG.Lowe.Distinctiveimagesfeaturesfrom
scale-invariantkey-points[J].InternationalJournalofComputerVision,200460(2):91-110.
[5]KrystianMikolajczyk,CordeliaSchmid,APerformance
EvaluationofLocalDescriptors[C]//ProceedingsoftheConferenceo-nComputerVisionandPatternRecongnito-n.Madison,Wisconsin,USA:[s.n.],2005:257-2.
[6]JanJ.Koenderink.Thestructureofimages[J].Biological
Cybernetics,1984,50:363-396.
[7]Lindeberg,T.Scale-spacefordiscretesignals[J].IEEE
TransactionsPami,1980,207:187-217.
[8]纪华,,吴元昊,孙宏海,王延杰.结合全局信息的SIFT特
征匹配算法[J].光学精密工程.2009.17(2).
[9]ZHAOH.SIFTfeaturesmatchingtechnology[J].Journal
ofYanchengInstituteofTechnology(NaturalScienceEdition),2007,20(2).
[10]孔军，汤心溢，蒋敏.多尺度特征提取的双目视觉匹
配[J].计算机工程与应用.2010.46(33).
[11]李芳芳,肖本林,贾永红,毛星亮.SIFT算法优化及其用于
遥感影像自动配准[J].武汉大学学报信息科学版.2009.34(10).
[12]吴锐航,李绍滋,邹丰美.基于SIFT特征的图像检索[J].
计算机应用研究.2008,25(2).
（收稿日期：2011-01-04）
7
图3实验1结果图
实验1的结果图3比较令人满意，其中第一幅图像（595.jpg）为原图，即与要搜索的图像完全匹配。除了第十幅图像不相关外，其余图像都是正确的关联图像。在本文的图像数据库中，大象的图像占到了100幅，实验结果图只给出了前12幅的检索结果，事实上在前20幅图像中只有3幅不相关。出现本文实验结果的原因主要有如下几条：a)该算法与图像中目标形状关系密切,如果目标形状发生了较大的改变,则该算法就不容易将其检出。b)该算法对于整幅画面中有多个相似区域的情况,该算法就会出现一定的的误匹配。c)在特征向量的降维过程中,对向量包含的信息量不可避免地造成损失,这也对图像匹配过程中的稳健性造成影响。
实验2，笔者用本文提出的基于SIFT优化算法与文献[12]的算法在检索性能上做了一组对照实验。在图像总数量变化的前提下，分别对同一张图片进行检索,并用上文定义的检索性能指标E来衡量算法的优劣。图4给出了实验结果。
图4实验2结果图
从图4的结果来看，本文算法在图像库数量较大时，对