资源目录
压缩包内文档预览：(预览前20页/共54页)
编号：155458963
类型：共享资源
大小：7.91MB
格式：RAR
上传时间：2021-10-17
上传人：好资料QQ****51605
认证信息
个人认证
孙**（实名认证）
江苏
IP属地：江苏
20
积分
- 关 键 词：
-
基于
尺度
不变
特征
图像
匹配
研究
- 资源描述：
-
基于尺度不变特征的图像匹配研究,基于,尺度,不变,特征,图像,匹配,研究
- 内容简介：
-
本科毕业设计论文 题 目基于尺度不变特征的图像匹配研究专业名称 自动化 学生姓名 张钰群 指导教师 赵博毅 王卫军 毕业时间 2014.6 II西北工业大学明德学院本科毕业设计论文设计论文毕业 任务书一、题目 基于尺度不变特征的图像匹配研究二、指导思想和目的要求 1.利用已有的专业知识，培养学生的解决实际工程问题的能力 2.锻炼学生的科研工作能力和培养学生团队合作及攻关能力3、 主要技术指标 1.对SIFT特征提取算法进行研究 2.针对其维度过高，实时性不佳，对SIFT算子进行了简化 3.对简化算法进行实验分析四、进度和要求第01周-第02周：撰写开题报告；第03周-第05周：图像特征提取和匹配相关基础知识学习；第06周-第07周：熟悉Matlab等相关软件；第08周-第13周：研究SIFT特征提取算法；第14周-第16周：对改进的SIFT特征提取算法进行实验；第17周-第18周：撰写毕业设计论文，论文答辩。五、主要参考书及参考资料1 贾云得.机器视觉M.北京:科学出版社,2000:1-50.2 李博.图像的不变特征检测与研究C.重庆大学硕士学位论文,2007:6-8.3 李俊山,李旭辉.数字图像处理(第一版)M.北京:清华大学出版社,2007.4 戚世贵.基于图像特征点的提取匹配及应用C.吉林大学硕士学位论文,2006.5 李文锋.图形图像处理与应用(第一版)M.北京:中国标准出版社,2006.6 Lindeberg,Tony.Scale-space theory:A basic tool for analyzing structures at differentscalesJ.Journal of Applied Statistics.1994,21(2):224-270.学生 张钰群 指导教师 赵博毅 系主任 史仪凯摘 要视觉不变量理论是十九世纪八十年代末将不变量理论引入到计算机视觉研究领域中形成的一个研究方向。视觉不变量是指那些对于尺度变化、物体移动、旋转、放射、透视变化仍保持不变的特征。本文研究的SIFT算法正是一种基于局部不变量的特征提取算法。SIFT（Scale Invariant Feature Transform）算法由 D.G.Lowe于1999年提出，并于2004年做了完善和总结。SIFT特征点对于图像的尺度和旋转保持不变性，对于光照和3D视角的变化也能保持一定的稳定性，而且由于在立体和频域空间被很好的局部化，故而降低了噪声干扰的可能性。本文讨论了一种SIFT算子的简化方法，简化后的算子与原算子相比大大降低了特征点描述子的维度。同时，简化的SIFT算子具有很好的不变性，在3D视角变化、光照变化也有很好的稳定性，并且与SIFT算法相比时间复杂度大大降低，更适用于海量的数据搜索和匹配。本文主要内容如下：（1）为计算机视觉及视觉特征不变量理论做了概述的变换矩阵和图像特征的分类方法，给出了特征提取标准，并在最后简要概括了本文的主要研究内容和组织（2）介绍了SIFT算子，介绍多尺度空间及高斯差分的方法，描述了SIFT算子极值提取、去除不稳定点、生成特征点描述子的过程，这种算子对尺度变换、旋转、仿射变化保持不变，对光照也具有一定的不变性。（3）对SIFT算子进行改进，采用同心圆窗口替代之前的矩形SIFT特征向量进行降维简化。关键词：SIFT特征向量，图像匹配，视觉不变量ABSTRACTVisual invariant theory is eighteen eighties at the end of the invariant theory is introduced to a research direction in the field of computer vision research. Visual invariants are those changes in scale, moving, rotating, radiation, the perspective changes remain invariant feature. The SIFT algorithm is proposed in this study is a feature extraction algorithm based on local invariant.SIFT (Scale Invariant Feature Transform) algorithm proposed by D.G.Lowe in 1999, and in 2004 made a perfect and summary. SIFT feature points for image rotation and scale invariance to illumination changes, and from the perspective of 3D can also maintain a certain stability, but due to being localized well in three-dimensional space and frequency domain, so it reduces the possibility of noise.This paper discusses a simple method of SIFT operator, operator is simplified greatly reduces the dimensions of feature point descriptor is compared with the original operator. At the same time, SIFT operators simplified invariance of good, in the 3D perspective changes, illumination changes also had good stability, and the time complexity is greatly reduced compared with the SIFT algorithm, more suitable for mass data searching and matching.The main contents of this paper are as follows:(1) the classification method of transformation matrix and the image features of the computer vision and visual feature invariant theory, the feature extraction, and finally summarizes the main research content and organization(2) introduced the SIFT operator, the multi-scale space and Gauss differential method, described the process of SIFT operator extremum extraction, removal of unstable point, feature point descriptor generation, this operator remains committed to scaling, rotation, affine transformation, the light also has a certain invariance.(3) to improve the SIFT operator, the dimensionality reduction using a simplified rectangular SIFT feature vector before concentric circle window replacement.Keywords: SIFT feature vector, image matching, visual invariants目 录摘 要I目 录I第一章 绪 论11.1计算机视觉11.2视觉不变量理论21.3图像变化类型51.3.1刚体变换71.3.2仿射变换81.3.3射影变换81.3.4非线性变换91.4特征提取算法的衡量标准91.5本文的主要研究内容和结构10第二章 SIFT原理与应用112.1 SIFT基本思想112.2 SIFT特点112.3 SIFT特征计算步骤112.4 SIFT原理122.4.1尺度空间理论及其构造122.4.2 空间极值点检测152.4.3 特征点方向172.4.4 SIFT局部图像描述子182.5 对图像进行SIFT特征提取20第三章 SIFT算法的改进方案233.1 SIFT简化算法233.2 RANSAC算法253.2.1 RANSAC算法介绍253.2.2 RANSAC算法计算单应性矩阵27第四章 实验及结果分析294.1特征的匹配294.2性能指标和评价标准294.3维度的选择304.4简化算法不变性测试334.4.1改进算法在旋转和尺度变化下的匹配效果334.4.2改进算法在视角变化下的匹配效果344.4.3改进算法在光照变化下的匹配效果354.4.4改进算法的时间复杂度36参考文献39致 谢43毕业设计小结44 第一章 绪论1.1计算机视觉视觉是人类观察世界、认知世界的重要功能和手段。通过视觉，人类感知外界环境的位置、大小、颜色、纹理等，获得对机体生存具有重要意义的各种信息。在各种各样的外来信息中，至少有80%的信息来自于视觉，剩下的来自于触觉、嗅觉、听觉等感觉器官。同时，视觉也是思维的一个最基本的工具。人类视觉包括了视觉信息的获取、将信息传送至大脑、人脑根据过往的知识经验对信息的加工和推理等工作、将获取到的信息记忆到大脑、认知和理解获取的信息（包括观察到的物体种类、物体间的相对位置、大小、颜色、外形、纹理等）。因此，人类的视觉过程是很复杂的，包含了对信息采集、存储、处理和认知的全过程。人类进入信息时代以后，通过摄像机可以获取视觉信息，同时也希望计算机可以模拟人类的视觉过程，对信息加以处理，这就形成了计算机视觉这门学科。二十世纪五十年代，计算机视觉理论已出现，主要研究二维图像的分析和识别，是统计模式识别的重要内容。1965年，Robert通过计算机程序成功的对于三维积木世界的解释开创了以理解三维场景为目的的三维计算机视觉的研究，他对积木世界的创造性研究可以推广到理解更复杂的三维场景。1977年，麻省理工学院(MIT，Massachusetts Institute of Technology)的人工智能实验室(Artificial Intelligence Laboratory)的Marr教授提出了计算视觉理论(Computational Vision)，这个理论不同于Robert的“积木世界”分析方法，Marr理论立足于计算机科学，概述了心理物理学、神生理学、临床神经病理学等方面的成果，虽然它还不能认为是一个完整的理论，但是它是至今为止最系统的视觉系统框架，并在计算机视觉领域有很深远的影响。计算机视觉就是用各种成象系统代替视觉器官作为输入敏感手段，由计算机来代替大脑完成处理和解释。计算机视觉的研究目的是使计算机可以模拟人类视觉的过程，即可以通过由摄像机采集到的二维图像来认知现实世界中三维环境的能力，并且可以同人类视觉一样认知三维环境中的几何信息，包括物体间的相对位置、形状、颜色、运动等，而且能对采集到的信息进行描述、存储、处理和认知，进而做出决断。计算机视觉的应用十分广泛，并且和多个学科彼此紧密关联，如图像处理与图像分析、模式识别、机器视觉、人工智能、计算机图形学等。由于它的重要性，一些先进国家，如美国已把对计算机视觉的研究列为科学和工程领域中对经济和科学有广泛影响的重大基本问题，即所谓的重大挑战（grand challenge）。这也是因为计算机视觉具有以下一些难点：（1）信息的多义性：在三维物体投影到二维图像的过程中，可能发生不同形状物体投影相同，或者不同视角下同一物体投影不同的情况，也就是信息的多义性，这是由于投影过程存在信息丢失；（2）环境因素：获取的图像与环境中的很多因素（如光照强弱、场景中物体的几何形状和物理性质、摄像机的特性、光源与物体和摄像机之间的空间关系等）都息息相关，某一因素的改变都可直接导致信息的变化；（3）成像过程中的畸变和噪声：计算机视觉是计算机图形学的逆过程，计算机视觉是将获取的二维图像恢复并重建原始三维图像的过程，而获取的二维图像在成像过程中的畸变和噪声，更增加了此过程的难度；（4）海量数据：图像信息（如灰度图像、彩色图像、深度图像等）需要占据大量的存储空间，并且在海量数据库中实现快速处理较为困难。计算机视觉系统主要的功能包括图像获取、预处理、特征提取、监测和分割、高级处理。本文主要讨论计算机视觉中的不变量提取部分。1.2视觉不变量理论从几何上看，空间中物体的位置是相对不变的。但是对于同一三维空间现场，由于视角的变化，所获取的二维图像可能破坏了对象的不变特征，这就要求所提取的特征与尺度、位置和方向等因素无关，这样的特性或特征量称为不变性或不变量。十九世纪初，Cayley、Salmon、Clebsh等人提出了代数不变量理论，这是最早的不变量概念。十九世纪八十年代末，视觉不变量理论和应用的框架因不变量理论与人类视觉相近性被成功地引入机器视觉研究中而形成7。在1991年冰岛的正式研讨会中，欧美学者首次提出了视觉不变量理论，也就是几何结构不变量理论。理论中说明了不变量是指物体的特征在经过了如下的一个或几个变换：(1)尺度的缩放；(2)物体的移动；(3)物体的旋转变化；(4)仿射变换；(5)透视变换后，仍然保持不变的特征量。对某个物体由于观察视角的变化而获得的不同图像，可以等效为上述的一个或几个变换。其中变换(1)、(2)、(3)是变换(4)的特例，变换(5)是非线性的，但是在满足一定条件下，可以用(4)很好的近似(5)，实际成像系统是一个透视变换。视觉不变量理论认为，不变量是图像几何结构的一种本质描述。这是由于视觉不变量是物体几何结构在某个或某些变换群下仍然保持不变的函数形式。视觉不变量理论中的几个重要变换群有：欧几里德变换群、仿射变换群、射影变换群和拓扑变换群，这几个变换群是逐个包含的，即其他的变换群都是拓扑变换群的特例，并且具有封闭性、恒等性、可逆性和结合性。一般用齐次矩阵表示变换群，齐次矩阵中未知参数的个数称为变换群的自由度。自由度的大小可以反映变换群的复杂度和通用度，自由度越大通用程度越强，自由度越小复杂度越低。上述几种变换群依次增大，变换群越大，自由度越大，不变性越少。相对的，若变换群越小，自由度越小，不变性越多,可提取的不变量也越丰富。视觉不变量理论的优点可以归结为以下几点：首先，计算机视觉的难点之一就是当视角变化时，投影图像也会不同，这导致了物体识别的困难，而且物体越复杂识别越困难，这是因为一般的处理手段通常只能处理平移变换、刚性变换、旋转变换和尺度缩放，一旦因为视角变化而导致图像形状的改变，原始的方法便没法识别物体。而视觉不变量理论是几何结构的本质描述，可以找到在某个或几个变换群下仍不变的特性。其次，若使用计算机视觉理论中Marr理论识别时，须已知摄像机方向、位置和内外参数等先验知识才能采用算法，这是因为投影图像的位置和形状与摄像机的位置和角度有直接的关系。这增加了算法的复杂性，降低了算法的应用范围。而视觉不变量与摄像机参数无关，不需要先验知识便可求出不受摄像机参数变化影响的目标几何结构和不变量函数，降低了物体识别的难度。而且，视觉不变量可以应用于状态复杂的曲面，提取曲面的微分不变量。另外，计算机视觉中另一个难点是对海量数据库的实时性处理。当数据库大小呈指数级增长时，若采用传统的处理方法，识别时间会令人难以接受，无法保证实时性。而采用视觉不变量构成的模型库监测函数，则可以以近于常数的访问时间和检索时间处理模型库，从而保证了海量数据库处理的实时性问题。在实际应用中另一个经常遇到的难点是因物体遮挡而导致的信息丢失问题，若采用传统处理方法，则识别较为困难。而视觉不变量方法可以提取图像的全局几何特征，故局部信息遮挡并不影响全局物体识别效果，可以很好的解决因物体遮挡而导致的部分信息丢失问题。综上所述，视觉不变量理论可以很好的解决物体平移、旋转、缩放所造成的形状相似变化，也可以处理由于视角不同而造成的射影变化。同时由于视觉不变量提取的是目标的全局特征，当发生部分遮挡导致信息丢失的情况下，也可以从剩余部分提取不变量信息。这是因为不变性和不变量提取的是物体的本质特征，与物体所处的环境、3D视角的变化、位置等条件无关，因此根据不变量可以更准确的识别物体。可以总结为，视觉物体的几何结构可以由一些视觉不变量来代表，同样的也可以说，每一个不变量都在物体几何结构分析中起关键作用。视觉不变量理论主要用来处理相同维度空间间的映射，即以平面到平面的映射为基础，视觉不变量理论可以很好的提取平面物体、平面组合而成的物体、和部分由丰富特征平面构成的物体的表面中的不变量，并有较好的效果。视觉不变量理论的提出，最根本也是最重要的原因是它在功能上更加接近人的视觉本质。因为人的生理视觉感知是以不变特征为基础，故即使物体存在形状等剧烈变化（包括遮挡），人的视觉也可以从不同角度、不同距离、不同光照下轻松的感知和识别某个的目标。同样的，机器视觉因为以视觉不变量理论为基础，在功能上与人的生理视觉较为相似，故更加易于降低因3D视角变化而给目标识别带来的问题。在识别应用中，不变量不受物体平移、旋转和尺度缩放等物体形状变化影响，也不受因目标滚动产生的射影形态变化影响；而且不需要如摄像机位置、角度和内外参数等先验知识和校准；它能提取出目标的本质特征，用以构成海量模型库并可以实时性检索；它可以由两个不同观测视角获取的图像描绘出物体的三维形状，且三维形状的构建不需要已知视角之间的运动轨迹，还可以生成不同视角下的物体投影形状；它可以从两个不同观测视角上获取的图像中计算出未知目标的三维几何结构和刚性，并应用于运动分割方法中；当目标存在部分遮挡或信息缺失时，仍然可以由剩余部分来描述物体不变信息，从而准确描述物体的全局结构特征。不变量描述子一般分布于图像的各个不同的结构中，其中一种研究图像对称结构的有效方法便是Lie群理论。Hoffman是Lie群理论在视觉不变性理论的研究领域中最著名的科学家，Hoffman的研究为神经心理学的Lie变换群方法，研究结果主要为抽取视觉感知过程的模型，其中采用了多种的数学工具。目前，众多的国内外学者致力于不变量理论的研究，并取得了一定的研究成果。I.Weiss和E.Rivlin都在这方面做出了贡献，I.Weiss最早使用投影不变量描述应用于视觉领域中的曲线及表面的描述，之后E.Rivlin和I.Weiss又扩展了这种不变量描述方法。不变量可以主要分为代数不变量和微分不变量。代数不变量主要反映整个代数对象的整体特性，具有较好的全局特征，具有抗噪性能强、计算量小的优点，因此称代数不变量为全局不变量。微分不变量是指平面内曲线或曲面的局部特性，因此称微分不变量为局部不变量。每个特征提取算法都有各自的应用范围和不足之处，单单依靠一种的不变量提取算法，不容易准确的描述和检测出需要识别的物体。现阶段，常使用信息融合方法，即分析和综合多种不变量特征提取方法，这种信息融合方法一般能得到更加理想的识别效果。1.3图像变化类型在3D图像向2D图像映射过程中，由于摄像机角度不同，获取的图像也会有所差异。一般来说，可以将摄像机的运动归为以下几种情况：（1）平移运动：在固定焦距的情况下，摄像机的运动范围平行于成像平面；（2）镜头缩放：摄像机的焦距的变化，也就是场景平面和成像平面之间的距离的变化；（3）水平移动：摄像机绕垂直轴旋转；（4）垂直移动：摄像机绕水平轴旋转；（5）旋转移动：摄像机绕光轴旋转。而一般的摄像机运动可以使以上的某一种运动或者几种运动的合成，所以实际情况会比较复杂。研究摄像头变化的目的是为了求出图像变换的模型，用二维数组表示两幅具有变换关系的图像，他们之间的变换关系满足式（1-1）。 (1-1) 其中，h表示二维空间中的坐标变换，g表示图像的灰度或辐射变换，它是因传感器类型不同或成像时光照等变化导致的图像灰度的变化。目前常用的变换模型有平移变换、刚体变换、仿射变换以及投影变换。图1-1是一个正方形在不同关系模型下的变换图，图中分别画出了正方形在平移变换、刚体变换、相似变换、仿射变换和射影变换下的变换图。图1-1 不同关系模型下的关系图上述图像变换关系可以用齐次坐标表示式（1-2）。 （1-2）或A =M A。其中M为变换矩阵，共有8个自由度。M中各个自由度的作用如表1-1所示。 表1-1变换矩阵中自由度的作用参数参数的作用m2m5m1,m,3m4,m0m6,m7水平方向位移垂直方向位移尺度和旋转量水平与垂直方向的变形量1.3.1刚体变换如果一幅图像经变换后，原图中的两点间的距离与变换后的图像中两点的距离相等，则这种变换为刚体变换（Rigid Transformation）。对于直线，其平行性和垂直性在刚体变换后保持不变。刚体变换的变换矩阵M可表示为式（1-3）。 (1-3)二维空间中，点(x ,y)经过刚体变换到点(x ,y)的变换矩阵可以简化为式（1-4）。 (1-4)其中为物体的旋转角度,，m2和m5为水平方向和垂直方向的平移量，若为0，则上式为平移变换。由上式可以看出刚体变换具有3个自由度，理论上知道至少两对点对就可以计算出刚体变换矩阵，见图1-2。图1-2刚体变换需要两个点对1.3.2仿射变换如果一幅图像上的直线经过变换后在另一幅图像上仍然为直线，并且保持平行关系，则这种变换为仿射变换（Affine Transformation）。仿射变换包括各个方向尺度变换系数一致的均匀尺度变换、变换系数不一致的非均匀尺度变换、剪切变换等。放射变换的变换矩阵M可表示为式（1-5）。 (1-5)放射变换可以理解为线性变换和平移变换的组合。故点(x, y)经过放射变换到点(x ,y)的变换矩阵可以简化为式（1-6）。 (1-6)其中是实矩阵。由上式可知，仿射变换具有6个自由度（m0,m1,m2,m3,m4,m5），理论上选取至少三对不共线的点对就可以求解出变换矩阵，见图1-3。图1-3仿射变换变换需要三个点对1.3.3射影变换如果一幅图像中的直线经变换后在另一幅图像中仍未直线，但却并不保持原有的平行关系，这样的变换为射影变换（Projective Transformation）。可以看出平移变换、刚性变换、仿射变换和投影变换是依次被包含的。其中投影变换具有更一般的形式，但是具有更高的自由度并且更难以确定其变换矩阵。射影变换的变换矩阵M见式（1-7）。 (1-7)射影变换具有8个自由度，理论上至少选择四对点对且任意三对点对均不共线才能计算出变换矩阵，见图1-4。图1-4射影变换变换需要四个点对1.3.4非线性变换 如果一幅图像中的直线经过变换后在另一幅图像中不一定是直线，可能是曲线，这样的变换称为非线性变换（Nonliner Transformation），也称弯曲变换（Curved Transformation）。二维空间中，非线性变换可以表示为式（1-8）。 ()=F (x, y) （1-8） 其中F表示一幅图像到另一幅图像映射的任意一种函数形式。本文中不考虑非线性变换，只考虑到最一般的射影变换。1.4特征提取算法的衡量标准特征提取算法有其衡量标准，一般来说特征点的数量要适中，对于特征提取算法来说，不一定提取密集精细的特征提取方法就是优秀的。因为过多的特征点会导致后续匹配时间增多和存储容量的负担。提取的特征点要尽量均匀分布在图像上，而不是只集中在某一小部分，且特征点应对图像平移、旋转、尺度缩放等变换保持不变性，这样才能在后续的匹配中有较好的匹配效果。而且对于各种类型的图像都能有效的提取特征点，适应能力佳。一个较好的特征提取算法一般应满足以下约束条件：（1）样本的可分离性：同类样本间的距离要尽量小，不同类样本间的距离要尽量大，这样可以有效的区分不同类的样本；（2）特征的有效性：算法提取的特征需满足特征的一般要求和特殊要求，且分类错误率低于某给定数值；（3）抗模式畸变能力：特征点需对一般的模式畸变如平移、旋转、尺度缩放和仿射等变化保持不变性；（4）时间复杂度：提取特征点所花费的计算时间，即算法的时间复杂度；（5）适应性：特征提取算法应适用于对多种类型图像，通过验证其匹配的相关性和残差的大小，可以验证特征提取方法的适应性。图像特征提取的方法有多种多样，且涉及面广，通常需要根据用户的需要和实际的问题选择最适合的特征提取方法。1.5本文的主要研究内容和结构本文以图像局部特征描述子SIFT（Scale Invariant Feature Transform）为基础，提出了一种简化的SIFT特征描述子，并讨论了新算子在不同的情况下本文的研究工作主要分为以下几点：（1） 系统的分析和总结SIFT特点，将其应用于图像匹配中；（2） 提出了改进的SIFT算子，降低了算时间复杂度，并分析了新算子最优的维度数。在上述工作中，提出一种针对SIFT算子维度过高的降维办法，并分析算法的最优维度。本文的组织结构如下：第一章，绪论，为计算机视觉及视觉特征不变量理论做了概述的变换矩阵和图像特征的分类方法，给出了特征提取准，并在最后简要概括了本文的主要研究内容和组织第二章，SIFT算子，介绍多尺度空间及高斯差分的方法，描述了SIFT算子极值提取、去除不稳定点、生成特征点描述子的过程，这种算子对尺度变换、旋转、仿射变化保持不变，对光照也具有一定的不变性。最后简要介绍了基于 SIFT 的两种改进方法：PCA-SIFT和GLOH。第三章，SIFT算子改进方案，采用同心圆窗口替代之前的矩形SIFT特征向量进行降维简化。第四章，实验及结果分析，首先定义了图像检索算法的性能指改进算法的维度最优值，并与原算法进行对比。46第二章 SIFT原理与应用SIFT（Scale Invariant Feature Transform）即尺度不变特征变换，SIFT特征是一种电脑视觉的算法用来侦测与描述影像中的局部性特征，它在空间尺度中寻找极值点，并提取出其位置、尺度、旋转不变量，此算法由 David Lowe 在1999年所发表，2004年完善总结。其应用范围包含物体辨识、机器人地图感知与导航、影像缝合、3D模型建立、手势辨识、影像追踪和动作比对。2.1 SIFT基本思想将图像分解成许多不同大小的重叠的碎片，并将每一个碎片用一个不变特征来描述。这样每一个部分可以相互独立的进行匹配，以及检测匹配碎片的一致性。正是因为这一特征的提取，是将图片的每一个局部区域，变换为与图像的尺度和方向无关的特征向量，因此，它被命名为尺度不变特征转换（Scale-invariant feature transform）。2.2 SIFT特点（1）SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性；（2）独特性（Distinctiveness）好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配； （3）多量性，即使少数的几个物体也可以产生大量的SIFT特征向量； （4）高速性，经优化的SIFT匹配算法甚至可以达到实时的要求；（5）可扩展性，可以很方便的与其他形式的特征向量进行联合。2.3 SIFT特征计算步骤（1）检测尺度空间极值点；（2）精确定位极值点，得到关键点，并确定关键点的位置和所处的尺度；（3）为每个关键点指定方向参数（使用极值点邻域梯度的主方向作为该关键点的方向特征，以实现算子对尺度和方向的无关性）；（4）关键点描述子的生成。2.4 SIFT原理2.4.1尺度空间理论及其构造我们要精确表示的物体都是通过一定的尺度来反映的。现实世界的物体也总是通过不同尺度的观察而得到不同的变化。尺度空间理论最早在1962年提出，其主要思想是通过对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，对这些序列进行尺度空间主轮廓的提取，并以该主轮廓作为一种特征向量，实现边缘、角点检测和不同分辨率上的特征提取等。尺度空间中各尺度图像的模糊程度逐渐变大，能够模拟人在距离目标由近到远时目标在视网膜上的形成过程。尺度越大图像越模糊。根据文献Scale-space theory: A basic tool for analysing structures at different scales（Tony Lindeberg , 1994）以及The structure of images（J.J.Koenderink,1984）可知，在一系列合理的假设前提下，高斯核是唯一可以产生多尺度空间的核，一个图像的尺度空间L（x,y,) ，定义为原始图像I(x,y)与一个可变尺度的2维高斯函数G(x,y,) 卷积运算，即 （2-1）其中，高斯二维函数为 (2-2)被称为尺度空间因子，值越小表示图像被平滑的越少，相应的尺度也就越小。大尺度对应于图像的概貌特征，小尺度对应于图像的细节特征。为了在尺度空间中检测到稳定的关键点位置，Lowe提出使用Difference-of-Gaussian函数与图像卷积的极值，其中Difference-of-Gaussian可以由两个相差一个参数因子k的相邻尺度的高斯函数得到 (2-3)选择D这个函数是有很多好处的。首先，这个函数的计算非常高效。由于任何使用尺度空间特征描述的方法都得计算平滑的图像L，因此计算D仅需要一步图像减法。其次，DoG函数是尺度归一化的LoG的一个逼近，其中LOG为。Lindeberg等已经证实对于真正的尺度无关，归一因子扩是必须的。在更细的实验比较中，Mikolajezyk发现，与其他的一些函数，如宫gradient，Hessian和Harris Corner，的极大值与极小值产生最稳定的图像特征。D与的关系可以由从如下公式推导得到： (2-4)利用差分近似代替微分，则有： (2-5)因此有 (2-6)在SIFT尺度空间中，对图像进行S次光滑之后进行一次亚采样。每S次光滑所得的图像称为一组(octave)，一共O组。尺度空降具体构造方法如下：图2-1 SIFT尺度空间示意图（1）首先采用不同尺度因子的高斯核对图像进行卷积以得到图像的不同尺度空间，将这一组图像作为金子塔图像的第一层。（2）接着对第一层图像中的2倍尺度图像（相对于该层第一幅图像的2倍尺度）以2倍像素距离进行下采样来得到金子塔图像的第二层中的第一幅图像，对该图像采用不同尺度因子的高斯核进行卷积，以获得金字塔图像中第二层的一组图像。（3）再以金字塔图像中第二层中的2倍尺度图像（相对于该层第一幅图像的2倍尺度）以2倍像素距离进行下采样来得到金字塔图像的第三层中的第一幅图像，对该图像采用不同尺度因子的高斯核进行卷积，以获得金字塔图像中第三层的一组图像。这样依次类推，从而获得了金字塔图像的每一层中的一组图像。（4）对得到的每一层相邻的高斯图像相减，就得到了高斯差分图像。图2-1中的右列显示了将每组中相邻图像相减所生成的高斯差分图像的结果。因为高斯差分函数是归一化的高斯拉普拉斯函数的近似，所以可以从高斯差分金字塔分层结构提取出图像中的极值点作为候选的特征点。对DOG 尺度空间每个点与相邻尺度和相邻位置的点逐个进行比较，得到的局部极值位置即为特征点所处的位置和对应的尺度。2.4.2 空间极值点检测特征点就是DoG空间的局部极值点。为了寻找DOG空间的局部极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图2-2所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9x2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。图2-2 DoG尺度空间局部极值检测一旦通过与邻域比较确定为候选特征点之后，下一步便是如何根据特征点的位置、尺度、和主曲率来进一步筛选特征点。通过拟和三维二次函数以精确确定关键点的位置和尺度(达到亚像素精度)，同时去除低对比度的关键点和不稳定的边缘响应点(因为DOG算子会产生较强的边缘响应)，以增强匹配稳定性、提高抗噪声能力。(1）低对比度去除Brown等提出一种方法来确定特征点的精确位置。该方法通过拟合一个三维二次函数到局部图像采样点来决定极值点的插值后的位置。首先对于DoG函数进行泰勒展开 (2-7)其中为特征点附近的采样点，为原先得到的特征点。修正后的极值点的位置是通过对上式求导，并且令导数为零得到的： (2-8)由以上两式可得 (2-9)根据Lowe的实验，极值点的取舍准则为：对于所有极值点的值，如果小于0.03则剔除出候选特征点。(2）边缘响应去除由于DoG函数在横跨边的方向有很强的响应，因此对于噪声会不稳定。高斯差分算子的极值如果定义的不好，会在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率通过一个2x2的Hessian矩阵H求出： (2-10)导数由采样点相邻差估计得到。D的主曲率和H的特征值成正比，令为模最大特征值，为模最小的特征值，则 (2-11)表示矩阵H对角线元素之和，表示矩阵H的行列式。假设是较大的特征值，而是较小的特征值，令，则 (2-12)的值在两个特征值相等的时候最小，随着r的增大而增大，因此，为了检测主曲率是否在某域值r下，只需检测 (2-13)在Lowe的文章中，取r10。2.4.3 特征点方向有了特征点后，那么怎样才能实现特征点描述子旋转无关呢？通过赋予每个特征点一个方向，并且这个方向的计算仅依赖于局部图像信息，如果让特征点描述子通过这个方向来表示，那么这个特征点描述子便是旋转无关的。首先由特征点的尺度选择相应的Gaussian平滑图像L，这就使得所有的计算都是尺度无关的。对平滑图像L，利用像素差计算梯度大小和梯度方向 (2-14)在实际计算时，我们在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0360度，其中每10度一个柱，总共36个柱。在统计直方图的时候，对于区域内的每个点，由该点的梯度大小以及以关键点为心关键点尺度的1.5倍为标准偏差的Gauss加权窗在该点的值进行加权。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。主方向图2-3 由梯度方向直方图确定主梯度方在梯度方向直方图中，对于任意另一个大于主峰值80%能量的峰值时，则将这个方向认为是该关键点的辅方向。一个关键点可能会被指定具有多个方向(一个主方向，一个以上辅方向)，也就是有好几个关键点它们的位置和尺度相同，但是方向不一样。这么做的目的是为了增强匹配的鲁棒性。2.4.4 SIFT局部图像描述子通过以上步骤，对于每一个关键点，拥有三个信息：位置、尺度以及方向。接下来就是为每个关键点建立一个描述符，使其不随各种变化而改变，比如光照变化、视角变化等等。并且描述符应该有较高的独特性，以便于提高特征点正确匹配的概率。 图2-4 由特征点邻域梯度信息生成特征向量上图显示了局部描述子的计算过程。为了提高效率，首先计算所有Ganssian光滑图像的梯度大小和方向。对于每个特征点，选择与该特征点尺度相对应的光滑图像。为了实现旋转不变性，将图像的坐标轴旋转为特征点的方向，然后在特征点附近取以特征点为中心的8x8的一个区域。对于取定的区域的采样点，由Gauss加权窗赋予每个采样点一个权值，其中标准偏差取为描述子区域宽度的1.5倍。显然Gauss加权函数值从内到外逐渐递减，这么做的目的是让越靠近特征点的像素梯度方向信息贡献越大，并且这么做会避免因为描述子区域的微小变化而使描述子产生突变。接下来很重要一点就是如何避免边界效应，比如，一个采样点从一个直方图变到另一个直方图，或者从一个方向变到另一个方向。因此可以用三线性插值将一个像素的梯度信息分配到直方图的相邻柱子。特征点描述子如图2-4所示，左部分的中央黑点为当前特征点的位置，每个小格代表特征点邻域所在尺度空间的一个像素，箭头方向代表该像素的梯度方向，箭头长度代表梯度模值，图中蓝色的圈代表高斯加权的范围(越靠近关键点的像素梯度方向信息贡献越大)。然后在每44的小块上计算8个方向的梯度方向直方图，绘制每个梯度方向的累加值，如图右部分所示。这样每个描述子由4个直方图组成，每个直方图有8个方向向量信息。这种邻域方向性信息联合的思想增强了算法抗噪声的能力，同时对于含有定位误差的特征匹配也提供了较好的容错性。通过将描述子区域划分为若干子区域，并在这些子区域上分别统计方向直方图，这种方法能够允许梯度位置的平移。实际计算过程中，为了增强匹配的稳健性，Lowe建议对每个关键点使用 44共16个直方图来描述，这样对于一个关键点就可以产生448=128个数据，即最终形成128维的SIFT特征向量。此时SIFT特征向量己经去除了尺度变化、旋转等几何变形因素的影响，再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响。首先，对于图像对比度的变化，也就是将每个像素值乘以一个常数，这样得到的梯度值也放大(缩小)了常数倍，归一化刚好去除了这样的变化。对于图像亮度的变化，也就是将每个像素值加上一个常数，得到的梯度不会变化。因为梯度值是基于像素值之差。这样得到的SIFT特征描述子是仿射光照不变的，但是非线性的光照变化如照相机变化，还是能够导致梯度大小的变化，然而对梯度方向的影响很小。为了减小梯度大小变化带来的影响，可以通过设置一个阀值，将单位SIFT特征向量的分量中值大于0.2的设为0.2然后再次进行单位化。对于一幅图像，经过以上所有步骤以后，便可以得到这幅图像的所有SIFT特征点的信息：空间位置，尺度，方向。2.5 对图像进行SIFT特征提取图2-5是对一幅图像进行SIFT特征点选择的过程，包括极值点的检测、低对比度点和边缘点的剔除。图（a）是一幅233189像素的图像，图（b）是经高斯差分尺度变换后提取的832个局部极值点，图（c）是图（b）经剔除低对比度点后将特征点降为729个，图（d）是图（c）经去除边缘点后将特征点个数确定为536个。 图2-5关键点选择的过程图2-6是两幅同一场景不同光照条件下提取的特征点，可以看出对于光照变换，SIFT算法能保持一定的不变性。图2-6不同光照条件下的两幅图像的关键点图2-7是两幅图像在视角变化下提取的特征点，可以看出对于视角变化，SIFT算法能保持不变性。 图2-7不同视角下的两幅图像的关键点图2-8是两幅图像经旋转变化后的特征点，可以看出对于旋转变换，SIFT算法具有不变性。 图2-8经旋转变化的两幅图像的关键点第三章 SIFT算法的改进方案SIFT算法是一种基于局部特征描述的算法，对于每个特征点，根据其邻域内的像素值决定其描述子向量，较全局特征算法在大型数据库匹配中有了更强的应用，但是由于SIFT算子的特征描述子向量为128维，在存储中需要耗费较多的存储空间和匹配时间。GLOH算法虽然比SIFT算法有着更好的性能，但其特征向量也为128维，没有在复杂度上进行提高。针对于SIFT算法维度较高的缺点，本人对SIFT算法进行了改进，以下为具体的改进算法。3.1 SIFT简化算法SIFT算法两个改进方法都是从特征点描述子入手，因为特征点描述子生成占去整个算法处理时间的大部分，影响了算法的实时性，本文的改进算法也是针对于特征点描述子进行改进。本文的改进算法是将原有的均匀分布的矩形区域改为以关键点为中心向外扩散的同心圆区域，生成关键点的邻域没有变小。这样改进主要有以下一些因素：(1）SIFT算法中应用了高斯模糊的方法，也就是将图像与高斯函数即正态函数做卷积运算。对于图像来说，高斯模糊生成的曲面等高线是从关键点开始呈高斯分布的同心圆。这样处理之后，与关键点较近区域中的像素对关键点描述子的生成影响比重较大，而与关键点较远区域中的像素对关键点描述子的生成影响较小。若将原区域划分改为以关键点为中心的同心圆区域，可以省去高斯的模糊的步骤；(2）SIFT算法需要计算每个关键点的方向，并在描述子生成前旋转邻域，使关键点的方向为0，从而保证旋转不变性。这是因为矩形并不具有旋转不变性，相对而言，圆形区域具有很好的旋转不变性，可以免去邻域角度归零的步骤。新的描述子构造方法如下：(1）提取以关键点为中心，16为直径的圆形窗口区域作为邻域，以保证生成特征点描述子所需要计算的邻域范围和原算法基本一致；(2）将半径为8的圆形邻域以2为单位分为4个的同心圆，图3-1即为划分之后的同心圆，每个格子代表一个像素值；图3.1改进算子邻域的划分 (3）对于4个同心圆区域，分别求出其10个方向（0、36、72、108、144、180、216、252、288、324）的梯度累加值。由中心向外，取第一个圆环的10维向量作为特征向量的第1至第10个元素，取第二个圆环的10维向量作为特征向量的第11至第20个元素，以此类推。这样，特征点描述子即为4 10 40维向量；(4）为了保证旋转不变性，对特征向量实施排序操作。设D是关键点的特征向量，D1、D2、D3、D4分别为从中心向外第一、第二、第三、第四个圆环的特征向量，则D =(D1，D2，D3，D4)，其中D =(d i1,di2 ,d i3,.di10),i1,4。首先标记出最内圈最大值出现的位置，即d 11,d 12,.,d19 ,d110中的最大值，若d11为最大值，则不需要做任何处理，若最大值不是d11，则进行如下操作：将D1、D2、D3、D4同时循环左移，直至D1中的最大值为特征向量D1中的第一位，设d17为向量D1中的最大值，则移动之后四个圆环的特征向量为D i=(d i7,di8,.d i10,.di1,di2,.di6)如果将每一个10维向量分别取向量的最大值并执行此步操作，则匹配的效果会大大降低。这样操作保证了四个圆环旋转相同的角度，等同于原算法中邻域归零的操作，从而保证了改进描述子具有选择不变性；(5）为了减少光照的影响，同样需要对特征点描述子进行尺度归一化处理。设D是特征点描述子，且，则归一化公式为式（3-1）。 (3-1)同样，为了减少大梯度值的影响，设定一个阈值为0.2，若向量中某一元素的值大于0.2，则将其置于0.2，并重新进行归一化处理。3.2 RANSAC算法3.2.1 RANSAC算法介绍RANSAC（Random Sample Consensus）即随即抽样一致性方法是由Fischler和Bolles提出的，是计算机视觉领域中最有效的鲁棒参数估计算法之一，它对错误率超过50%的一组数据仍然有很好的一致性分析结果。传统方法如最小二乘法，是通过最小化误差的平方和来寻找数据的最佳匹配，也就是考虑所有点的整体误差，但是当数据中存在噪声点或者重大错误点时，并不能剔除错误点，往往得不到想要的结果。根据应用不同，RANSAC算法的输入可以分为数据点的集合和对应点对的集合，后者将在3.2.2详细说明。当输入为数据点集合U时，我们认为其中的一部分数据点与某一参数模型一致，这个模型的参数来自参数空间?，符合要求的这些点称为内点（inliers），而不满足参数模型的点，称为外点（outlier）。RANSAC算法是要从参数空间中寻找参数模型，并且参数模型可以使内点数目达到最大值，即代价方程为最大。其中为阈值输入，为参数模型，为数据点集合U中满足参数模型的一致集。当某一数据点与参数模型之间的距离小于阈值时，认为数据点符合参数模型，或者说支持模型。当一致集中数据最多时，方程为最大。方程表示数据点x与参数模型之间的距离。尽管RANSAC算法有很多修改，但是为使具有最大值，需以重复迭代方式出现的两个重要步骤是假定和测试。假定：首先，从输入数据集U中随机选取最小采样集（MSSs）Sk，根据最小采样集中的元素计算模型参数k，其中最小采样集的元素个数是能计算出模型参数的最少必要个数。之所以选取最小的采样集，是因为采样集中数据的个数m与一个样本中至少包含一个外点的概率是呈指数增加的。例如当参数模型为直线时，则根据两个不第3章SIFT算法的改进方案30同的点就可确定模型中参数的值。测试：下一步，RANSAC方法检查数据集中所有符合上一步计算的模型实例的数据点，这些符合要求的数据点成的集合称为一致集（CS）。方程的最大值的初值为置信度（预先定义好的概率）1-，其中是返回非优解的概率。最初随机选择的样本可以分为两类：一是不包含外点的样本集，二是至少包含一个外点的样本集。理想的情况是选择到不包含外点的样本集，因为在这种情况下计算出的模型参数是准确的。当一个不包含外点的随机抽样样本大小为m时，这个样本从含N个数据点的集合U中被选择的概率P为式（3-2）。 (3-2）其中，I为内点数目，初始时I是未知的；是内点比率（数据点正确率），则.是第k次抽样得到的参数模型的最大支持，=,错过内点数目为的集合概率为式（3-3）。 (3-3）当这个概率小于某一预先设定的阈值时，算法终止。故而，需要重复的次数为式（3-4）。 (3-4）RANSAC算法具体计算步骤如下：(1）随机从原始数据中抽取最小的点集，数据量对于计算模型参数是充分的，计算模型参数；(2）将所有原始数据代入1）的模型中，若距离小于，为阈值，则这些点称为内点，内点组成的集合称为一致集；(3）重复次步骤1、2，重复次数已在上文中介绍过：次随机抽样中，具有最大一致集的模型为最鲁棒的参数模型；根据最优模型参数，计算出原始数据集中所有的内点，并用内点重新计算参数模型，即是最终的参数模型。3.2.2 RANSAC算法计算单应性矩阵单应性矩阵是一个几何中的概念，是一种可逆的投影变换。设为一平面区域，和分别为在两个不同视角下透视投影变换后的图像，X为上的一点，x和x分别为和平面上X点变换后的坐标，则存在一个3 3维奇异矩阵H，满足式（3-5）。 （3-5）其中，,有8个不确定因子，H为对于的单应性矩阵，如图3-2所示图3-2由平面确定的单映性矩阵由于x和x采用齐次坐标，并且H中有8个不确定因子，若要确定单应性矩阵的值，则需要至少具有4对对应坐标点，且对于这4对对应点，每幅图像中的3个点都不能处于同一直线上。然后采用奇异值分解（Singular Value Decomposition,SVD）方法即可求出H的值。用表示两幅图像和中的所有对应点对构成的集合，其中分别为图像和中的坐标点，且一一对应于中的同一坐标点。H为有8个自由度待确定的单应性矩阵，为符合单应性矩阵的点对构成的一致集（CS），即满足式（3-6）的所有坐标对所构成的集合，式（3-6）中dist (m ,n)表示平面上两点m和n的欧氏距离，即若m和n的坐标为(a, b)和(c, d)，dist (m, n )=，t为预先给定的距离阈值。 (3-6)RANSAC算法引用于单应性矩阵的步骤如下：(1）随机从对应点对集D中抽取s个数据点，通过数据点计算样本的初始模型，即待确定的单应性矩阵中的参数；(2）将数据代入计算出的模型中，若距离小于预先定义距离阈值t，则这个数据点为内点，所有内点组成样本模型一致集DI；(3）若DI的势大于给定的阈值T，则通过奇异值分解方法用DI中的所有数据点重新计算单应性矩阵H，算法结束；(4）若DI的势小于给定的阈值T，则跳转到步骤1，重新构造初始单应性矩阵；(5）经过N次实验，选取势最大的DI。DI对应的单应性矩阵即为要求的解。第四章 实验及结果分析本章为SIFT算子的实验及结果分析部分。主要分析算法维度的选择和在几种变换下改进算法和原算法的对比。在实验前，本章介绍了特征的匹配和算法的性能指标和评价标准。4.1特征的匹配设待匹配的两个图像为M和N，两个图片经SIFT算法提取特征点后，特征点集特征点集合分别为：图像M的特征点集合为,图像N的特征点集合 L分别为图像M和N的特征点数目。通常，使用欧几里得公式计算两个特征点间的距离，当SIFT特征向量的维度为k时，距离为式（4-1）。 （4-1）并按距离比率（distance-ratio）准则进行特征匹配，即对于某一特征点，设另一图像中与其最近的欧几里得距离为d1，次近欧几里得距离为d2，且d1与d2的比率为ratio =d 1/d2。评判是否与特征点匹配的定义为： (4-2)其中，为预先设定的阈值，实验中采用值为0.44。也就是说当距离比率大于某一阈值时，认为特征点成功匹配，相反，则认为与特征点不匹配。4.2性能指标和评价标准为了便于衡量算法的性能以及与其他算法进行对比，需要确定出衡量算法性能的标准。鉴于此前介绍的算法优劣的一些方面，本文主要从以下几个方面衡量算法。(1)计算复杂度：也就是算法所要耗费的计算时间，一般仅计算完成一个典型的查询中需要采用的最重要的操作；(2）平均迭代次数：与计算复杂度相似但又并不完全一致（主要考虑操作复杂度）一般仅计算为获得一定的满意结果所需要的迭代次数；(3）平均查询范例数量：即为获得所需的满意程度而需要的查询范例数量的平均值。本文中衡量SIFT局部特征描述子在关键点匹配问题上的匹配效果采用K.Mikolajczyk的衡量方法，即计算算法的查全率（recall）和错误率（1-precision）。查全率和接收工作特性（Receiver Operating Characteristics）一般可以互相替代，通过根据他们之间微妙的不同来确定具体选择哪种方法。接收工作特性适用于评估分类子；而查全率在评估检测子上有很好的应用。故文中采用查全率和错误率的曲线图。在检索中，如果某一特征点对的特征向量的欧几里得距离小于给定的阈值，则这个匹配点对称为匹配的。正确的匹配对是指匹配的两个关键点对应于同一个物理位置，相对的，错误的匹配对是指匹配的两个关键点对应不同的物理位置。则查全率和错误可以定义为：其中，所有的关键点数假定是已知的，正确率=1-错误率。通过改变阈值，可以画出查全率和错误率的曲线图。最理想的查全率和错误率的曲线图应该是对于任何1-precision值，recall值始终为1。实际情况中，由于存在图像变换和特征提取引入而噪声等原因，recall值会随着距离阈值的增加而增大。一般来讲，1-precision值相同的情况下，recall值越大越说明匹配效果越好；而在recall值相同的情况下，1-precision越小越说明匹配效果越好。对于曲线图来说，则是曲线位置越高代表匹配效果越好。4.3维度的选择本文在改进算法中需要确定的一个重要参数是四个同心圆环窗口的向量维度，即每个同心圆环窗口所要统计的梯度直方图数目。例如，若每个同心圆环选择的向量维度为8，则生成的特征向量的维度为8 ?4 ?32维。向量维度不是越大越好，选择一个合适的向量维度可以提高查全率、正确率和降低时间复杂度。本文通过计算查全率和错误率来判定合适的维度数。在一定的阈值下，对两幅图片在不同维度下的一组直观匹配效果图见图4-1_4-5所示。其中，图4-1是在每个同心圆维度为6时的匹配效果，其中所有的匹配点数为197，正确匹配点数为163；图4-2是在每个同心圆维度为8时的匹配效果，其中所有的匹配点数为200，正确匹配点数为174；图4-3是在每个同心圆维度为10时的匹配效果，其中所有的匹配点数为170，正确匹配点数为146；图4-4是在每个同心圆维度为12时的匹配效果，其中所有的匹配点数为157，正确匹配点数为138；图4-5是在每个同心圆维度为14时的匹配效果，其中所有的匹配点数为137，正确匹配点数为122。图4-1同心圆环维度为6时的匹配效果图4-2同心圆环维度为8时的匹配效果图4-3同心圆环维度为10时的匹配效果图4-4同心圆环维度为12时的匹配效果图4-5同心圆环维度为14时的匹配效果由上述的匹配效果可以直观的看出，当维度增大时，匹配点总数在降低，而错误点数目也同时在降低，尤其是显著错误点的数目，当同心圆环的维度为8时，可以明显看到很多明显的匹配错误，而当维度为10时，明显错误降低了很多。这是因为随着维度的增大，特征点描述子中包含的信息增多。从数据库中，选取50对图像在不同的维度下作查询，统计在维度选择为6、8、10、12、14时图像的查全率、准确率，并绘制曲线图如图4-6所示。 图4-6不同维度下的查全率和正确率可以看出当维度增大时，图像的查全率降低而匹配正确率增高，本文中选取中间值，即维度为10。实际情况中，可以根据实际需要，如提高匹配精度或降低匹配时间来提高或降低维度的选择。4.4简化算法不变性测试为了验证改进的SIFT算法的可行性和有效性，实验验证其在旋转、尺度、灰度和视角变化时的图像匹配效果，并与原算法在匹配时间及匹配效果上做对比。实验平台为Windows Vista操作系统，CPU 1.83GHz，2G内存的个人电脑，编程环境为Matlab2007。4.4.1改进算法在旋转和尺度变化下的匹配效果本实验是为了测试改进算法在图像旋转和尺度变化下的匹配效果，并与原算法做对比。图4-7是6幅包含了旋转和尺度变化的图像，每个图像对于其他图像均有不同程度的旋转和尺度变化。图4-7一组包含旋转和尺度变化的图像每张图片检测到的关键点数目见表4-1，将第26张图片分别和第一张图像进行匹配实验，得到5组数据，见表4-2。表4-1旋转和尺度变化下图像的关键点数图片编号第一张第二张第三张第四张第五张第六张关键点数119910771005935709770表4-2旋转和尺度变化下图像的匹配比较数据匹配点数第一组第二组第三组第四组第五组简化SIFT1151727493101原SIFT510458339219170可以看出，在旋转和尺度变化下，改进算法虽然比原算法的匹配效果稍差，但也具有很好的匹配效果，在旋转和尺度变化下改进算法依然有效。4.4.2改进算法在视角变化下的匹配效果本实验是为了测试改进算法在图像视角变化下的匹配效果，并与原算法做对比。图4-9是6幅不同视角下的图像，每个图像对于原始的第一张图片具有不同程度的视角变化。图4-9一组包含3D视角变化的图像在SIFT算子中，每个图片检测的关键点数目见表4-3。将每张图片分别和原始图像进行匹配实验，得到5组数据，见表4-4。表4-3 3D视角变化下图像的关键点数图片编号第一张第二张第三张第四组第五张第六张关键点数113712781297139613311373表4-4视角变化下图像的匹配比较数据匹配点数第一组第二组第三组第四组第五组简化SIFT1261041018791原SIFT5893241217657可以看出，图像在视角变化时也具有很好的不变性。4.4.3改进算法在光照变化下的匹配效果本实验是为了测试改进算法在图像光照变化下的匹配效果，并与原算法做对比。图4-11一组包含光照变化的图像 图4-11是6幅不同光照条件下的图像，每个图像对于原始的第一张图片具有不同程度的光照变化，每个图片检测的关键点数目见表4-5。将每张图片分别于原始图像进行匹配实验，得到5组数据，见表4-6。 表4-5光照变化下图像的匹配点数图片编号第一张第二张第三张第四张第五张第六张关键点数585764606820481337803193表4-6光照变化下图像的匹配比较数据匹配点数第一组第二组第三组第四组第五组简化SIFT 31201338279619681421原SIFT 474738974273303022964.4.4改进算法的时间复杂度由于改进算子简化了特征点描述子，在匹配效果上有一定的降低，但是由于大大降低了SIFT算子的维度，时间复杂度也降低了很多，对比像素分别为800 640、400320、200160三种情况，在SIFT算法和改进算法中的时间，得到表4-7。可以看出，改进的SIFT算子在时间复杂度上较SIFT算子大大降低，更适用于海量的数据搜索。表4-7不同尺寸的图像速度的对比图像尺寸SIFT简化SIFT80064028.01s11.37s4003205.27s2.43s2001601.23s0.65s参考文献1贾云得.机器视觉M.北京:科学出版社,2000:1-50.2李博.图像的不变特征检测与研究C.重庆大学硕士学位论文,2007:6-8.3李俊山,李旭辉.数字图像处理(第一版)M.北京:清华大学出版社,2007.4戚世贵.基于图像特征点的提取匹配及应用C.吉林大学硕士学位论文,2006.5 杨占龙，郭宝龙.基于兴趣点不变矩的图像拼接J.光电子激光.2007，18(6):738一740.6Lindeberg,Tony.Scale-space theory:A basic tool for analyzing structures at different scalesJ.Journal of Applied Statistics.1994,21(2):224-270.7王付新，黄毓瑜，王田苗.三维重建中特征点提取算法的研究与实现J.工程图学学报，2007，(3):91一96.8Marr D著,姚国正译.视觉计算理论M.北京:科学出版社,1988.9马颂德,张正友.计算机视觉计算理论与算法基础M.北京:科学出版社,2003:1-5.10章毓晋.图象理解与计算机视觉（图象工程下册）M.北京:清华大学出版社,2000.11吴立德.计算机视觉M.上海:复旦大学出版社,1993:16-86.12I.Weiss.Projective Invariants of ShapesJ.Proceedings of DARPA Image Under-standing Workshop,2001(2):1125-1134.13颜孙震,孙即祥.矩不变量在目标形状识别中的应用研究J.国防科技大学学报,1998,20(5):75-80.14于长江.高等画法几何学M.北京:航空专业教材编审租,1983.15宋辉，李弼程.一种使用Harris特征点的区域图像检索算法J.计算机工程.2006，32(7):202一203.16孙晶.图像局部不变特征提取技术研究及其应用C.大连理工大学博士学位论文,2009:1-14.17龚声蓉，刘纯平，王强等.数字图像处理与分析.北京:清华大学出版社，2006.18彭勃，周文晖，刘济林.基于Harris角点检测的立体视觉里程计J.兵工学报，2007，28(l2):1498一1502.19孙即祥.模式识别中的特征提取与计算机视觉不变量M.北京:国防工业出版社,2001.20赵辉.基于点特征的图像配准算法研究C.山东大学硕士学位论文,2006.21李文锋.图形图像处理与应用(第一版)M.北京:中国标准出版社,2006.22王向阳.乌卜俊.侯丽敏.一种基于图像特征点的数字水印潜入方法.电子学报.2007，35(7):1318一1322.23刘琼,倪国强,周生兵.图像配准中几种特征点提取方法的分析与实验J.光学技术,2007,33(l):62-64,67.24龚声蓉,刘纯平,王强等.数字图像处理与分析M.北京:清华大学出版社,2006.25赵录刚,吴成柯.基于随机抽样一致性的多平面区域检测算法J,计算机应用,2008,28(12):154-157.26章毓晋.基于内容的视觉信息检索M.北京:科学出版社,2003.27贾涛，陈涛，杨润奎.基于仿射不变量的长基线立体匹配J.仪器仪表学报，2005，26(8):623一624.28刘曙，罗予频，杨士元.基于临界特征点的图像匹配算法J.计算机工程，2007，33(19):173一174.29孙向军，曹立鑫，刘凤山.基于角仿射不变的特征匹配J.中国图像图形学报，2004，9(5):30刘瑞祯，谭铁牛.数字图像水印研究综述J.通信学报，2000，21(8):39一48.31胡慧博，刘据，孙建德.基于ICA的抗拷贝攻击的数字水印方案J.电子与信息学报，2005，27(7):1035一1038.32欧阳建权.压缩域体育视频摘要技术研究.北京:中国科学院计算技术研究所，2005.33黄祥林，沈兰荪.基于内容的图像检索技术研究J.电子学报，2002，30(7):1065一1071
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号