基于内容的图像检索系统及sift算法的应用.doc

基于SIFT算法的图像检索系统的研究摘 要人类进入现代社会以来，科技、经济、文明不断发展，信息量的增长速度也随之加快。从海量数据中迅速检索出有用信息成为人们的迫切需求。因此，图像检索作为一种能从海量图像中迅速查找到需要图像的技术很快成为人们研究的热点。在一个图像检索系统中最重要的环节便是图像特征提取与匹配，而SIFT算法正是一种由David Lowe提出的图像局部特征描述子，因为其良好的独特性和鲁棒性而受到人们的普遍关注。本文给出了一种基于SIFT算法的图像检索技术，并依此开发了一套图像检索实验系统，主要研究工作总结为：首先分析了CBIR系统的组成和关键技术的基本原理，重点分析了特征提取环节的技术细节，对比分析了几种经典的特征描述算子，尤其是SIFT算法的基本原理和各自的优缺点。然后根据对比结果选择SIFT算法作为最终的特征提取方案，最后实现了一个实验性的CBIR系统。实验结果表明SIFT 算法对图像的平移、旋转、视角等变化具有良好的鲁棒性，提出的基于SIFT算法的CBIR系统方案具有良好的效果。关键词 图像检索；CBIR；SIFT算法；特征提取 Research about Image Retrieval System Based on SIFT AlgorithmAbstractSince the humans enter the modern age,the growth of science,technology, economy and civilization has accelerated the growth of information.Retrieving useful information from the huge amounts of data quickly becomes people's urgent needs.Therefore, image retrieval as a technology which able to find the required image from massive image quickly has became a research focus soon. Image feature extraction and matching is the most important principle in image retrieval system,and SIFT algorithm is a local characteristic of image description made by David Lowe,because of its unique and robustness,SIFT algorithm has admired widespread concern.This article will present an image retrieval technology based on SIFT algorithm and so on develops a testing system for image retrieval.Research summary:Firstly,analysis the basic principle and key technology of CBIR system,focusing on aspects of feature extraction from technical details.Secondly,comparison and analysis several classic describes of the characteristics,particularly foundations and their respective advantages and disadvantages,then select SIFT algorithm based on comparison results as the final programme of feature extraction.Finally achieved an experimental CBIR system. Experimental results show that the SIFT algorithm has good robustness to image translation, rotation and perspective changes,and the CBIR system based on SIFT algorithm also shows good property and action.Keywords image retrieval; feature extraction; SIFT algorithm目 录摘要IAbstractII第1章 绪 论11.1 研究背景11.2 CBIR系统概述11.3 研究现状31.4 应用领域41.5 主要工作内容5第2章 CBIR系统关键技术环节62.1 特征提取技术62.1.1 图像特征基础62.1.2 点特征提取算子72.1.3 各算法性能比较112.2 匹配与相似性度量132.3 CBIR 系统性能评价142.4 本章小结14第3章 SIFT算法原理及性能验证153.1 SIFT算法原理153.1.1 DoG尺度空间的构造153.1.2 关键点搜索与定位193.1.3 特征点方向赋值213.1.4 关键点描述223.2 SIFT算法性能实验243.3 SIFT算法在CBIR系统中的应用283.4 本章小结30第4章 基于SIFT算法的CBIR系统314.1 系统概述314.2 系统GUI324.3 性能实验334.4 本章小结34结论35参考文献36致谢38附录39第1章 绪 论1.1 研究背景人类进入现代社会以来，多媒体技术、计算机网络技术和通信技术迅速发展，使得信息总量不断飙升。而图像信息由于能够对场景或对象进行直观生动的描述，因而成为最重要、也是最常见的多媒体信息。随着数码相机、扫描仪等数字设备的普及，大量的图像信息被创造出来，随着图像的数量越来越多，人们亟需一种能够有效管理图像信息的技术。于是，自20世纪70年代以来，图像检索技术逐渐成为一个非常活跃的研究领域。图像检索技术共经历了基于文本的图像检索技术（TBIR, Text Based Image Retrieval）、基于内容的图像检索技术（CBIR，Content Based Image Retrieval，为叙述方便，以下皆简称CBIR）两个发展阶段。前者主要通过人工对图像进行文本标注，然后将图像的文本描述写入数据库中进行管理。用户检索时，则根据数据库中存储的文本描述查找需要的图片。后者则直接利用图像内容进行检索，即通过对图像的视觉特征进行研究和提取，形成图像库中所有图像的特征集，检索时对用户所提交的样本图像进行一致或相似的特征提取操作，通过对图像低层视觉特征的比较来实现检索。随着图像库规模的增加，TBIR技术的弊端日益显露。首先，由于人类意识的主观性，对同一副图像不同的人会产生不同的理解，因此不可能形成一个统一的检索标准。这使得图像的文本描述很难准确响应用户的查询信息，查询效果差，效率低。其次，图像携带大量的信息，其丰富的细节和深远意义很难用文字表达出来，更别说区区几个关键词了。另外，对图像的文本标注是通过人工操作完成的，当需要处理大量的图像信息时，这无疑是一项浩大的工程，处理速度也会很慢。由于这些原因，上个世纪90年代开始，CBIR技术逐渐取代TBIR而成为新的研究热点。1.2 CBIR系统概述如上所述，CBIR系统是指直接采用图像内容进行图像信息查询的检索，即在图像数据库中检索与用户所提交样本图像在内容上一致或相似的图像集合的过程，通过对图像底层特征的比较来实现检索。主要研究技术包括特征抽取、相似度量、图像匹配、用户反馈。它不同于TBIR技术，不需要人工参与图像特征的描述，而是按照一定的方法有计算机自动完成，然后建立索引，因此相对于TBIR技术，它拥有许多优点：1.由计算机进行特征的分析与提取取，无需人工参与，避免了由于主观意识不同而引起的误差，又节省了大量的人力物力财力，同时大大提高了建立索引的时间，图像库的管理也更加方便高效。2.采用近似匹配作为匹配方式。CBIR系统找出的图片是与查询图像最相似的图像，并对查询结果按相似程度进行派序，具有很高的灵活性，能应用到多个领域。3.采用交互式的查询方式，具有根据用户反馈进行再查询的能力，用户可以根据查询结果提供反馈信息，系统再根据用户的反馈对查询结果进行修正，提高查准率。综上，CBIR突破TBIR系统的许多局限，使图像检索的效率和查准率都有了质的飞跃，因此很快在各个领域推广开来。对该领域的研究，也因此具有十分重要的学术和经济价值。但是CBIR技术所利用的仅是图像的低层视觉特征，还无法实现对图像内容、场景和所表达的情感等含义的理解与认识，也就是说现有的CBIR技术还无法利用图像的高层语义特征。这种高层语义特征是无法直接从视觉特征中提取出来的，它依赖于人的经验、推理和认识。因此，要想利用高层语义特征进行图像检索，势必需要人工智能、机器学习等相关理论的发展，这还有待更加深入的研究和探索。CBIR是一项新兴技术，集成性很高，技术环节主要包括以下几个：1.特征提取 视觉特征主要分为通用视觉特征和与领域相关的视觉特征，通用特征是指所有图像共有的特征，包括颜色、纹理、形状、空间位置关系等；与领域相关的视觉特征则建立某些经验、专业知识的基础上，如人脸特征、指纹特征等。特征提取是CBIR技术的基础环节，是区别不同类型图像检索系统的标准。2. 征匹配和相似性度量 图像特征提取出来之后，通常会用向量的形式对其进行描述，这样图像的相似性就转化成了特征空间的相似性问题。良好的匹配与相似性度量标准映与人眼的相似性判断保持良好的一致性。 3. 特征索引 图像蕴含了大量的有用信息，在处理大图像库时，提取出的特征类型多、结构复杂、数据量大。采用合理有效的数据结构对这些特征信息进行存储对节省存储空间、提高检索效率非常重要。常用的索引方式Kd-tree，B-tree等。 4. 查询模式 查询模式是指用户用何种方式向系统提交何种类型的查询信息，主要有以下几种模式：由用户提供一个查询图像(query image)进行检索的按例查询(QBE, Query By Example)、以用户绘制简单的图形为标准进行查询的按草图查询(query by sketch)、由用户指定对检索条件的描述，然后据此查询的按描述查询例。5. 相关反馈(Relevance Feedback) 在系统按照用户要求进行初次检索之后，用户可以根据初步查询的结果向系统提交修正信息一获得更佳的检索结果，这个过程就是相关反馈。采用这种方式可以提高检索的准确性，并从一定程度上弥补了用户与计算机之间的语义鸿沟。6. 系统性能评价(performance evaluation) CBIR是一项集成度很高的技术，有着丰富的理论和复杂的分类，因此对不同算法的评判和比较方法是确定CBIR系统优劣的重要工具，有利于研究者之间的交流和算法的推广，共同推动CBIR技术的发展。图2-1给出了一个典型的CBIR系统整体框图：图1-1 CBIR系统整体框图1.3 研究现状如上所述，CBIR技术是利用图像特征进行图像库索引的生成与检索的，对图像特征的研究是开发CBIR系统的基础。图像特征是一幅图像区别于其他图像所特有的属性或特点，是人们区别图像的依据，描述了图像的各个含义，是图像抽象的表达。图像特征从提取范围角度可分为局部特征（点特征、线特征等）和全局特征；从获取方式角度可分为自然特征（大小、方向、位置等）和人工特征（直方图、距、边缘等）；从特征属性角度可分为高层语义特征（知识语义、人工交互语义、外部信息源语言等）和低层视觉特征（颜色、纹理、形状等）。图像特征的研究最早始于20世纪70年代末。早在1977年Moravec就提出了点特征这个概念，他将图像特征点称为“兴趣点”，通过灰度自相关函数来衡量某像元与其邻域像元的关系。C.Harris和M.J.Stephens在1988年提出的Harris算子是一种特征点提取算子，它是Moravec 角点检测算法的改进，用一阶偏导来描述亮度变化，这种算子受信号处理中自相关函数的启发，给出与自相关函数相联系的矩阵M。M矩阵的特征值是自相关函数的一阶曲率，如果两个曲率值都高，那么就认为该点是特征点。直观的看，Harris算子的原理为：如果某一点向任一方向的微小偏移都会引起灰度的很大变化，这就说明该点是角点。1999 年Lowe提出的高效SIFT局部特征检测算法可以说是图像特征研究领域里程碑式的成果。该算法的思想来源是林德伯格的尺度空间理论，在林德伯格的论文中，规范化的拉普拉斯高斯算子被证明具有真正的尺度不变性。然而高斯拉普拉斯变换计算相当繁琐，Lowe便采用高斯差分算子近似高斯拉普拉斯变换，首先图像转化为灰度图，然后对图像进行不同尺度的高斯平滑滤波处理，进而获得图像在高斯差分尺度空间中的表达，最后将尺度空间中的极值点最为图像的特征点，特征提取速度提高的同时，又具备对各类缩放、光照强度、旋转等变化的不变性和稳定性。正由于SIFT算法具备的这些优点，因而被选为本课题的特征提取方案。其基本原理及具体实现方法将在第三章详细介绍。就图像检索技术总体而言，相关研究可分为三个层次：1.利用图像的低层视觉特征，包括颜色、纹理、形状以及空间结构等进行查询；2.利用检出特征或图像中各对象之间的逻辑关系进行检索，其中加入了对于图像中目标的识别和描述；3.抽象语义特征如场景描述，包含理解图像的深层寓意。现阶段大部分CBIR系统都在应用低层视觉特征进行图像检索，少数系统能够应用局部特征进行图像中部分对象的识别与检索，而高层语义特征的研究还在进行中，目前没有成熟的应用。1.4 应用领域基于内容的图像检索作为一项新兴的技术自问世以来已取得了不少的突破，这些成果也已经开始转化为应用技术，创造了不少的价值和财富，甚至颠覆了不少传统的运作方式，刺激了整个行业的技术革新。随着研究的不断深入，CBIR技术也逐渐渗透到越来越多的领域，它所带来的效益也刺激人们不断将其理论研究推向更高的层次。以下便是几个成功应用CBIR技术的领域。1.设计领域 利用CBIR系统，可以迅速找到所需要的素材，提高设计效率。2.医学领域 对收录的各种病例的医学CT图像进行检索，可快速搜索相似病例，及时快速的找到病因，获得参考治疗方案。另外也可以迅速查找典型病例进行教学，对医学研究也会产生深远影响。3.地理信息管理领域 可以快速检索利用遥感技术获得的大量图像信息，准确辨识图像中的各个地标，方便地理信息的后期处理。4.军事领域 不断对实时获取的图像进行检索，及时发现关键目标，可应用于武器制导和目标侦查。5.刑事侦查领域 通过人脸识别技术提取面部特征后建立头像资料库，可利用图像检索技术迅速确定犯罪嫌疑人身份，相同的技术还可建立指纹资料库或DNA资料库。6.版权保护领域 可将已注册的所有商标提取特征后建立索引，注册新商标时，都要对原有商标进行检索，防止重复或雷同，避免纠纷事件的发生。7.安全领域 对监控视频进行关键帧检索，迅速定位关键信息，另外指纹识别、视网膜识别等也都要利用到图像检索技术。正是由于CBIR系统有着越来越广泛的应用领域，创造着越来越多的社会财富，引起越来越多的生产及运作方式的革新，进行CBIR技术的深入研究，也拥有了重要的经济及学术价值。另外，由于CBIR技术跨学科、宽领域的技术特点，CBIR技术自身的发展，势必会带动其他诸如人工智能、认知心理学、计算机学习等学科的发展与进步。1.5 主要工作内容1.分析了CBIR系统的组成和各个模块的原理和细节，涉及的关键技术，对比分析了现有的几个著名的CBIR系统的基本原理和特点。2.对比分析了Harris算子、SUSAN算子和SIFT算子三种图像特征描述及提取方法，分析了他们各自的优缺点，并根据对比结果后选择了SIFT算法作为本系统的特征提取方案。3.分析了SIFT算法的原理及细节，并编写了matlab程序以验证它的各项性能，对将SIFT算法应用到图像检索领域的可能性进行了论证。4.利用matlab开发了一套CBIR试验系统，能够对较大的图像库（包涵1000张以上的图片）进行方便高效的管理，并根据提供的样图快速的检索出相关图片。第2章 CBIR系统关键技术环节2.1 特征提取技术在CBIR系统中，图像库中的每张图像的特征信息被预先提取出来并存入特征数据库，检索时通过匹配待查图像和库中图像的特征信息来判断二者的相似程度。因此，图像特征及其描述方法的好坏直接影响到检索的准确率和耗费的时间，可以说特征提取是 CBIR 系统的关键环节。下面我们将从图像特征基础开始逐步剖析特征提取技术的原理及实现算法。2.1.1 图像特征基础在上一章中，我们从多个角度对图像特征进行例如简单分类，下面我们将介绍几种在CBIR系统中广泛应用的几种图像特征。1.点特征 点特征是最重要的图像特征，目前大部分局部特征提取算法都是基于点特征提出的。点特征包括对象边缘点、线段交叉点、角点等，其中角点是最具代表性的。角点常用的提取方法如下：(1)基于曲率提取法：寻找图像的凸包边界上的最大曲率点或曲率的零交叉点；(2)基于灰度的提取方法：寻找图像灰度值变化剧烈部位的像素点，方法为求图像函数的一阶导数，寻找导数中的局部极值点，这些极值点即为在各个方向的邻域中灰度变化最剧烈的角点；(3)基于边缘提取法：寻找两条或两条以上线段边缘的交叉点，或者两个指向不同方向半边缘的交叉点，且两个半边缘间角度不等于180°，即角点为不连续的点。综上所述，角点出现在图像灰度梯度变化最为激烈处、两条或两条以上边缘线段以一定的角度交叉处和边界方向发生剧烈变化处，这些点也是引起视觉刺激最剧烈的点。由此看出，角点能够反映较为丰富的图像结构信息，因此它被称为特征点或兴趣点。2.颜色特征 颜色是图像的重要特征之一，也是最早被应用到CBIR技术中的一种特征。要提取颜色特征必须先选择合适的颜色空间，并将图像映射到选择的颜色空间中去，然后定义颜色特征并将其量化，最后进行相似性度量和匹配。颜色特征与图像中的物体或背景息息相关，因此对图像具有较强的描述性，另外颜色特征的提取方法相对简单，描述准确。所以颜色作为描述一幅图像最简单准确的方式，成为几乎所有CBIR系统着重提取的特征。3.纹理特征 纹理特征至今没有一个完整的定义。一般来说，纹理特征可以理解为图像中与某种颜色或亮度都无关的具有相同性质的视觉特征，通常是某些纹理元素有规律的排列组合。常用的纹理分析方法有 Tamura 纹理特征、小波变换和自回归纹理模型等。4.形状特征 物体的形状是图像的另一重要特征，它可以分为基于边界或轮廓的形状描述和基于区域的形状特征两种。前者的典型描述子有傅里叶描述子、小波形状描述子和Delaunay三角剖分法等。其中傅里叶描述子性能最佳，它以边界的傅里叶变换最为形状的特征描述。后者的描述子主要为各种矩不变量，如Hu不变矩、Legenda矩、Zernike矩等。另外也包括一些简单的如面积、圆度、主轴方向等形状因子。5.空间位置特征 上文所讲述的颜色、纹理和形状等描述的是图像的整体特征，但图像中各个区域或对象之间的相对位置关系却无法体现。弱项应用这些位置关系则必须对图像进行划分。划分图像并描述其空间位置关系的方法有两种：一是通过图像分割划分出图像的各个区域或对象，描述它们的空间关系存入索引；二是将图像划分为几个子图像，然后分别提取子图像的特征建立索引。上述每一种特征都各有优劣，所适合的图像类型也各不相同，很难找适合描述所有类型图像的特征描述子。所以在一些CBIR系统中为了提高系统的实用性，更加全面准确地描述图像，提高检索准确率，便将多种特征综合起来作为描述子，这便是综合特征检索技术。综合特征检索技术灵活性高，各种特征优势互补，性能较好。2.1.2 点特征提取算子点特征在相同条件下与其他图像特征相比，能够概括更多的图像信息，而且具有更少的计算量，现阶段局部特征算法的研究也主要以点特征的提取与匹配为研究方向。本课题实现的CBIR系统也使用图像的点特征进行检索与匹配。在一幅图像中，特征点要远远少于像元，但却携带大量的图像信息，在图像匹配、目标识别等方面也有广泛的应用，成为众多学者的研究重点，也提出了许多优秀的特征提取算法。下面我们将介绍几个非常重要的特征点检测技术，并对这几种算法在稳定性、有效性、处理速度及定位准确性这几个层面进行对比分析。1.SUSAN算子 SUSAN是最小吸收核同值区的缩写，是由由英国牛津大学学者S.M. Smith和J.M.Brady提出的。SUSAN算子是一种简单有效的基于灰度的特征点获取方法，主要应用于图像的边缘和角点检测，对噪声干扰具有一定的鲁棒性。SUSAN算子将使用窗口模板对图像进行处理，从而得出图像各向同性的响应。 SUSAN算子采用了不同于传统卷积运算方形模板的近似圆形的模板，如图2-1所示。首先，将模板放置在图像某一像元上，然后比较模板内部每个图像像元的灰度值都与模板中心像素的灰度值。如果模板内某点像素的灰度与模板中心像素(核)灰度的差值较小（通常要设定一个阈值），则认为该点与核的灰度值相同。将模板内所有像素点比较一次后，移动模板到下一像素点重复以上过程。所有与核灰度值相同的像素点组成的区域称做核值相似区(USAN)。图2-1 SUSAN模板离散图与核当圆形模板完全处在图像中某一对象内部时，模板内USAN区域面积最大(如图2-2中的a和b)；当在模板移到图像边缘的过程中，USAN区域逐渐变小；当模板中心移动到图像边缘时，USAN区域很小(如图2-2中的c)；当模板中心移动到角点时，USAN区域最小(如图2-2中的d)。可以看出，在边缘处象素的USAN值都小于或等于模板面积的的一半，因此，计算图像中每一个像素的USAN值，如果某一像素点的USAN值小于某一阈值，即可确定该点为边缘点，这就是SUSAN算法基本思想。由此可以得出SUSAN算子提取边缘和角点的基本方法：计算图像中每一像素点的USAN值，USAN较小的像素点可以确定为边缘、角点，并能根据USAN值的大小或矩形特征来确定边缘、角点等特征的位置和方向信息。图2-2 USAN区域大小确定总结 Susan 特征点检测算子，计算过程可以总结为如下四步：(1) 将近似圆形模板置于图像中移动，使模板核与每一个像元重合；(2) 统计在模板与核像元灰度值相似的像元数量，得到核像元的 USAN值；(3) 计算角点的相应值；(4) 利用非最大值抑制计算特征点集。SUSAN算子的突出有点是对局部的噪声不敏感，抗干扰性强。由于SUSAN算子并不需要对图像进行分割，因此也不需要计算图像的梯度数据，同时，USAN区域是通过模板内与模板中心像元具有相似灰度值的像元累加而得到的，而像元的累加过程实际上类似于积分的过程，从而可以有效的抑制高斯噪声。2.Harris算子 Harris算子是1988年由C.Harris和M.J.Stephens提出的一种点特征提取算子。这种算子受信号处理中自相关函数的启发，可以给出图像中某一像素点的自相关矩阵肘，其特征值是自相关函数的一阶曲率，如果算，Y两个方向上的曲率值都高，那么就认为该点是角点。Harris角点检测算法的原理可以描述为以下几个过程：首先将待处理图像中的矩形窗口W向任意的方向移动微小的位移( x , y )，那么灰度的改变量由式2-1计算得到。(2-1)其中，M是点(x,y)自相关函数矩阵，它是自相关函数在原点形状的描述，X,Y分别是图像函数在水平方向、竖直方向上的一阶导数，为高斯窗口的系数，A、B、C、M表示如下：(2-2)(2-3)(2-4)(2-5)假设矩阵M的两个特征值为，某一像素点的像素灰度自相关函数的极值曲率便由此表示，成正比。然后通过由像素点对应的矩阵M的特征值来确定角点的位置：如果都很小，那么它的局部自相关函数很平坦，说明被检测区域的灰度值变化不大，该区域为平坦区域；如果一个大，一个小时，那么该像素点的局部自相关函数呈现山脊状，说明该像素点处于图像边沿；如果都很大，那么图像的局部自相关函数呈现山峰状，说明该像素点是一个角点。在算法的实际的实现过程中，往往使用矩阵M的迹和行列式来代替特征值，这样可以大大简化计算的繁琐程度，提高检索效率。于是角点定义为下式的局部最大值。(2-6)为了降低高对比度的边界点的漏检率，于是添加了修正因子k，k 一般设定为 0.040.06。由于：(2-7)(2-8)所以Harris 角点响应函数CRF定义为：(2-9)Harris 算子是一种有效的角点提取算子，其优点总结起来有：(1)计算简单：Harris算子中只用到灰度的一阶差分以及滤波，操作简单，整个过程的自动化程度高；(2)提取的点特征均匀而且合理：Harris算子对图像中的每个点都计算其特征值，然后在邻域中选取最优点；(3)可以定量的提取特征点：Harris算子最后一步是对所有的局部极值进行排序，所以可以根据需要提取一定数量的最优点；(4)Harris算子在计算时用到了图像数据的一阶导数，具有各向同性。因此对图像旋转、亮度变化、视角变化和噪声的影响具有较好的鲁棒性。Harris 算子的局限性有：(1)它对尺度很敏感，不具有尺度不变性；(2)提取的角点是像素级的。3.SIFT算法 SIFT算法描述的是图像的局部特征，即图像特征点附近的像素灰度梯度分布情况，并对尺度变化、平移、旋转和亮度变化等具有良好的鲁棒性。本设计采用SIFT算子作为图像的特征描述子，分别为两幅图像提取SIFT特征后，便可使用获得的特征向量对其进行相似性匹配和聚类。其算法原理和匹配方法将在下一张做详细论述，本章暂不讨论。2.1.3 各算法性能比较为比较各上文提出的三种点特征检测算法的性能，本文设计了实验对上述算法进行验证。实验使用两张图片(图2-3)，图像(a)为一幅分辨率250×260的脑核磁共振图像，图像(b)为图像(a)经过平移与旋转后的图像。实验分别使用Harris算子、SUSAN算子和SIFT算子对这两幅图片进行特征提取，比较取得的特征点数量。以比较各个算法检测特正点的能力及对旋转及平移的稳定性。在实验中，Harris算子在图像(a)中提取出165个角点，同时在待配准图像(b)中提取出129个角点；SUSAN算子在图像(a)中提取出799个角点，同时在待图像(b)中提取出640个角点；SIFT算法在图像(a)中检测出722个特征点，在图像(b)中检测出736个特征点。实验图像和结果如下图所示。 (a) (b)图2-3 测试图像(a) (b)图2-4 Harris算子特征检测效果(a) (b)图2-5 SUSAN算子特征检测效果 (a) (b)图2-6 SIFT算法特征检测效果在实验中，Harris算子在图像(a)中提取出165个角点，同时在待配准图像(b)中提取出129个角点；SUSAN算子在图像(a)中提取出799个角点，同时在待图像(b)中提取出640个角点；SIFT算法在图像(a)中检测出722个特征点，在图像(b)中检测出736个特征点。从实验结果来看，Harris算子和SUSAN算子检测出的特征点主要是图像的边缘和角点，特征信息略显单调；而SIFT算法除能检测出图像的部分边缘外，还能检测出图像中的线段交叉点和边界曲率较大的点，能更加全面的反映图像特征。Harris算子在图像灰度值变化较大的部分能较好得检测出图像的特征点，但在灰度值变化较为缓和的部位则出现漏检现象，因而检测出的特征点总数较少，但(a)(b)两幅图像检测出的特征点总数相差不大，因而对旋转和平移具有较好的稳定性；SUSAN算法对图像中每一个区域中的特征点都有良好的敏感度，但却出现了冗余的边缘与角点，而且两幅图像检测出的特征点数量相差较大，体现出它对旋转的不稳定性；而SIFT算法出了检测出合适数量的边缘与角点外，还检测出图像中线段交叉点和曲线曲率较大的点，能更全面的反映图像特征，而且对旋转具有出色的稳定性。另外，在图像发生尺度、视角及亮度变化时，SUSAN算子及Harris算子将检测出完全不同的特征点，而此时SIFT算法将保持良好的鲁棒性。考虑到SIFT算法的以上优点，选用SIFT算法作为本课题中实现的CBIR系统的特征提取方案。2.2 匹配与相似性度量相似性度量也是图像检索系统的重要组成部分，度量方法的好坏直接影响到检索的性能，而匹配方法的计算复杂程度则直接影响到图像检索的时间。一般认为，好的相似性度量方法应与人体的视觉系统保持良好的一致性，即视觉上认为相似的图像它们的度量相似性就应该大，反之则小。通常采用各种相似距离(similarity distance)来度量相似性，常见的如下：1.绝对值距离，其公式如下：(2-10)2.欧氏距离，公式为：(2-11)3.余弦距离：(2-12)将图像中的特征点提取出来后，一般用一个n维向量来对图像的特征点进行描述，通过计算两幅图片相应特征点描述向量的相似距离来确定是否为相似特征。基于相似距离的度量方法具有计算简单，比较有效等优点，但和人体视觉实际的相似度感知还存在差距。因为SIFT算法会对检测出的特征点生成一个128维的描述向量，因此在本课题中，采用欧氏距离作为相似性度量的方法。并按并按距离比率(distance-ratio)准则进行特征匹配，即对于某一特征点，设其描述向量另一图像中与该特征点最相似的特征点描述向量的欧几里得距离为，与次相似点描述向量欧几里得距离为，计算与的比率ratio = /。则评判是否与特征点匹配的定义为：(2-13)其中，为预先设定的阈值，Lowe 实验中采用值为 0.44。也就是说当距离比率大于某一阈值时，认为特征点成功匹配，相反，则认为与特征点不匹配。2.3 CBIR 系统性能评价一般情况下，大型数据库系统采用Recall-Precision准则来评自身的有效性。该准则具体的评价方法是：先选择一副基准图像作为CBIR系统的查询，然后根据查询结果与基准图像I将数据库里的全部图像分为四类：A、检索到的且与I相似的图像；B、检索到的但与I无关的图像；C、未检索到但与I相似的图像；D、未检索到且与I无关的图像。最后统计各类图像的数量并计算查全率R(又叫召回率，Recall)和差准率P(Precision)。计算公式为：(2-14)“召回率”与“准确率”虽然没有必然的关系（从上面公式中可以看到），然而在大规模数据集合中，这两个指标却是相互制约的。由于“检索策略”并不完美，希望更多相关的文档被检索到时，放宽“检索策略”时，往往也会伴随出现一些不相关的结果，从而使准确率受到影响。而希望去除检索结果中的不相关文档时，务必要将“检索策略”定的更加严格，这样也会使有一些相关的文档不再能被检索到，从而使召回率受到影响。凡是设计到大规模数据集合的检索和选取，都涉及到“召回率”和“准确率”这两个指标。而由于两个指标相互制约，我们通常也会根据需要为“检索策略”选择一个合适的度，不能太严格也不能太松，寻求在召回率和准确率中间的一个平衡点。这个平衡点由具体需求决定。2.4 本章小结本章主要研究了CBIR技术的部分关键环节，如最为基础的特征提取和匹配技术，这是CBIR系统最为重要的一个环节，直接决定了整个系统性能的好坏。在本章节中，我们主要研究了Harris算法、SUSAN算法的基本原理，并设计实验对其特征检索特点、能力及稳定性进行了验证，并与SIFT算法进行了对比分析。而SIFT算法原理及实现方法将在下一章做详细分析。另外本章节还介绍了常用的特征索引技术，这一环节直接关系到系统的检索效率及信息的管理能力。第3章 SIFT算法原理及性能验证3.1 SIFT算法原理SIFT算法（Scale Invariant Feature Transform）是一种基于尺度空间的、对图像缩放、旋转甚至仿射变换保持不变性的图像局部特征描述算子，最早是由British Columbia大学的大卫·劳伊（David G.Lowe）教授于1999年总结提出的，并于2004年进一步完善。SIFT特征对旋转、尺度缩放、亮度变化等保持不变性，是非常稳定的局部特征。并且它将特征点检测，特征矢量生成，特征点匹配等步骤结合在一起，独特性好，信息量丰富，现在的应用十分广泛。总的来说，SIFT算法包括两部分内容：一是在尺度空间中进行兴趣点检测；二是对检测出的兴趣点用一个128维德向量进行描述。具体实现可以分为四步：构造DoG尺度空间、关键点的搜索与定位、特征点方向赋值和关键点描述。3.1.1 DoG尺度空间的构造尺度可以理解为我们观察自然界物体时使用的单位，如观察高山时，我们使用的尺度是米或千米，而观察细胞或微生物时，我们使用的尺度是微米或纳米。更形象的例子是电影中的拉伸镜头、查看图片时的缩放等等。图像的尺度空间表达就是图像在所有尺度下的描述，即尺度空间是由同一副图片分别使用不同尺度表示所组成的图像组。尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。尺度越大图像越模糊。用机器视觉系统分析未知场景时，计算机并不预先知道图像中物体的尺度。我们需要同时考虑图像在多尺度下的描述，获知感兴趣物体的最佳尺度。另外如果不同的尺度下都有同样的关键点，那么在不同的尺度的输入图像下就都可以进行匹配，也就是尺度不变性。瑞典皇家理工学院的Tony Lindeberg在他的论文Scale-space theory: A basic tool for analysing structures at different scales指出尺度规范化的 LoG( Laplace of Gaussian)算子具有真正的尺度不变性，也就是说图像经过LoG变换后再检测出的特征点便具有尺度不变性，这就是SIFT算法检测特征点方法的理论依据。LoG算子可由高斯梯度算子GoG构建。式3-1为尺度规范化的GoG算子：(3-1)LoG算子与高斯核函数又有如下关系：(3-2)(3-3)(3-4)式中，通过推导可以看出，LoG算子与高斯核函数的差有近似关系，由此引入一种新的算子DoG（Difference of Gaussian），即高斯差分算子作为LoG算子的近似。根据以上理论，SIFT