图像特征点提取与匹配算法研究论文

1、本科毕业设计(论文)题目名称：学 院：专业年级：学生： 班级学号：指导教师：二O一O年 月 日 45 / 51目 录摘 要IIIABSTRACTIV第一章 绪论11.1 研究背景11.2 研究现状综述21.2.1 特征点提取研究现状21.2.2 特征点匹配研究现状41.3 研究容51.4 论文组织结构6第二章 图像特征点提取算法研究82.1 Harris特征点提取算法82.1.1 Harris特征点检测原理82.1.2 Harris特征点检测步骤92.1.3 实验分析92.2 SIFT特征点提取算法122.2.1 SIFT特征点提取算法原理与步骤122.2.2 实验分析162.3 本章小结19

2、第三章 改进的H/S特征点提取算法203.1 H/S算法分析203.1.1 H/S算法提出的可行性分析203.1.2 H/S算法结合方案研究213.2 H/S算法实现223.2.1 多尺度特征点检测223.2.2 特征点描述233.3 实验分析253.3.1 算法评价标准253.3.2 分情况特征点提取结果分析253.4 本章小结27第四章 基于H/S的特征点匹配方法294.1 相似三角形方法局限性分析294.1.1 三角形匹配原理294.1.2 三角形相似方法局限性314.2 改进的相似三角形匹配方法实现314.2.1 三角形选取方案研究324.2.2 相似三角形检索方法改进334.2.3

3、多模板改进方法分析354.3 实验结果与分析364.4 本章小结39第五章 工作总结与展望405.1 工作总结405.2 工作展望41致 42参考文献43摘 要图像匹配是图像处理领域的基础课题，在图像拼接、全景视图、对象识别等计算机视觉方面有广泛应用。图像匹配分为基于灰度的方法和基于特征的方法，前者简单易行，但算法时间复杂度高，难以处理图像存在旋转和尺度变化等情况，后者在适应性和速度方面有很大优势，但图像特征的提取以与如何建立特征之间的对应关系一直是这类方法的研究难题。本文提出了一种新的特征点检测算法，并根据三角形相似原理，提出一种改进特征点匹配方法。本文首先对两种特征点提取算法(Harris

4、算法和SIFT算法)进行分析比较，Harris角点检测算法效率高，但对尺度变化和抗噪性的鲁棒性差，SIFT算法对尺度变化与抗噪性鲁棒性好，但算法时间复杂度高，且对图像纹理要求高，本文结合两种算法的优点，提出了一种新的H/S特征点提取算法，该算法特征点检测效率高，并且尺度不变性与抗噪性得到很大改善。在采用新的H/S特征点提取算法得到图像中特征点后，对特征点匹配方法进行研究。传统的三角形相似匹配方法虽然实现简单，鲁棒性好，但时间复杂度高，针对此局限性，本文提出了一种改进三角形匹配方法，将传统方法被动搜索相似三角形变为在复数空间下选择基线后主动构造相似三角形，并利用特征点组成基线向量对应三角形组得到

5、多个模板在实物图中匹配，提高了改进算法的实时性和稳定性。关键词 特征点，H/S算法，机器视觉，相似三角形检索ABSTRACTImage matching is a basic problem in the field of image processing, it has wide applications in computer vision, such as image stitching, panoramic view, object recognition and so on. It includes gray-based method and feature-based method

6、. The former method is simple, but the time complexity of this algorithm is high, especially its difficult to deal with the situations of image rotation and scaling. The latter method is much more easily overcoming the difficulties which encountered by the former method, but how to create the corres

7、ponding relationships between the images features is always a difficult problem. A new feature point extracting method is proposed in this thesis, and a new matching method which is based on similar triangles is proposed.The thesis firstly analyses and compares two kinds of extracting feature points

8、 algorithms( Harris algorithm and SIFT algorithm ), Harris algorithm has high efficiency and poor anti-scaling and anti-noise performance, SIFT algorithm has good robustness about anti-scaling and anti-noise, but the time complexity of this algorithm is high, and it has a great demand on image textu

9、re. The thesis combines the advantages of these two algorithms, a new H/S algorithm which is used to extract feature points is proposed, this algorithm has well efficiency, meanwhile, the anti-scaling and anti-noise performance is greatly improved.While the feature points of images are obtained by u

10、sing the new H/S algorithm, the matching methods are studied. Traditional similar triangles matching method is simple and has good robustness, but the time complexity of this algorithm is high, because of this limitations, the thesis proposes a improved matching method which is based on similar tria

11、ngles, making the traditional passively searching similar triangles to select the baseline to actively construct similar triangles. The algorithm uses multi-templates to match in the image, the real time ability and stability of the algorithm is improved.KEY WORDSfeature points,H/S algorithm, comput

12、er vision, similar triangles retrieval第一章 绪论1.1 研究背景图像特征点提取和匹配是图像处理研究领域中的基础课题，也是机器视觉的关键技术之一，广泛应用于虚拟现实、视频压缩、图像复原、图像数据库检索等技术中，具有广泛的应用前景与社会经济价值。因此，特征点的提取和匹配越来越得到研究人员的关注。图像匹配可以认为是在不同时间或一样时间、从不同视角或一样视角对同一场景拍摄的两幅或者多幅图像进行的空间域上的匹配过程。它通过建立两幅图像之间的对应关系，确定相应的几何变换参数，对两幅图像中的同一目标进行匹配。近几年在许多领域中，都对图像配准进行了大量的研究，比较有代表

13、的有：模式识别、自动导航、遥感领域、医学诊断、计算机视觉等。经过国外研究者多年的努力，人们提出了多种图像匹配方法。这些方法大致可分为基于灰度值的方法和基于特征的方法两大类1。基于灰度的匹配就是逐像素地把一个以一定大小的实时图像窗口的灰度矩阵与实际图像的所有可能的窗口灰度矩阵按某种相似性度量方法进行搜索比较的匹配方法。为了克服基于灰度匹配方法缺点，提出了基于特征的匹配方法。特征匹配方法首先对图像进行预处理来提取其高层次的特征，然后建立两幅图像之间特征的匹配对应关系，常用的特征基元有点特征、边缘特征和曲线轮廓与区域特征等。由于兴趣点(角点、拐点等)的信息含量高、数量相对较少且局部不变等特点，使其在

14、基于特征的匹配中有更加广泛的应用。如何建立图像兴趣点之间的对应关系一直是这类方法的研究热点。目前已有许多有关此类问题的如Sanjay Ranade等提出的松弛算法2、Zsolt Miklós等提出的三角形匹配算法3等。特征点匹配方法首先依赖于好的特征提取方法，特征点提取方法是从众多特征中求出那些对分类识别最有效的特征，从而实现特征空间维数或数据量的压缩。特征提取方法一般包含两个阶段：一是对图像进行分割，提取目标区域或其边界，抽取目标的基本特征，如灰度、纹理、形状描述。二是找出或构造目标作某种运动或无论目标作何种运动都不变化的目标图像特性的特征不变量。当提取特征点数目过多时就会存在大量

15、的干扰信息(如：伪匹配点)，这将影响匹配的正确率和速度，当提取特征点过少时，将不利于精确匹配。同时特征点匹配方法需要保证在两幅图像点集中存有大量有效点，而当图像特征点较多时，算法复杂度较大。本文基于以上热点问题展开研究，首先对两种特征点提取算法(Harris算法和SIFT算法)进行原理分析与实验比较，得出Harris角点检测算法效率高，但对尺度变化和噪声干扰鲁棒性差，以与SIFT算法对尺度变化与抗噪性鲁棒性好，但算法时间复杂度高，且对图像纹理要求高等结论，提出一种在多尺度下提取图像稳定特征点的H/S(Harris/SIFT)算法，并在此基础上采用复数空间中相似三角形多模版匹配算法进行特征点间匹

16、配，通过理论分析与实验证明该方法在时间复杂度方面的改进和在图像存在旋转、缩放情况时匹配的准确性和有效性。1.2 研究现状综述1.2.1 特征点提取研究现状在实际问题中图像可能受到噪声、背景的干扰，也可能发生平移、尺度、视角、光照等变化，如何选择合理的特征和描述算子，使得这些特征不仅具有良好的表征性能，而且在上述因素变化下保持相对不变(即不变性)，直接决定了基于特征点的图像匹配效果。以计算机视觉的不变理论为基础，对图像特征的不变性研究是目前图像处理的重要环节，吸引了众多研究工作者的兴趣。图像特征的不变性研究目前已取得了大量的研究成果。这些研究主要集中于以下几方面：1) 不变特征的选取，如图像的点

17、、线、轮廓，像素点的强度、曲率、矩、特征向量等。2) 不变性获取的途径，如通过特征变换、小波理论、神经网络、编码技术、特征描述子的构造等。3) 不变特征的描述，如SIFT描述子、PCA-SIFT描述子、不变矩描述子、傅里叶描述子、微分不变描述子、颜色描述子、链码描述子等。近年来，不变特征已引起国外研究者和研究机构的广泛关注。在相关领域中，具有代表性的研究机构是加拿大British Columbia大学智能计算实验室，该实验室开展了局部仿射不变特征提取方面的工作，其研究成果已应用于目标识别4、全景图拼接5、虚拟现实6、机器人自主导航7等领域。芬兰的Oulu大学机器视觉小组于2004年开始进行几何

18、不变性方面的研究，提出了一种具有完全仿射不变性的特征提取方法，并用于目标识别与配准。Oxford大学的机器人研究小组开展视觉不变性方面的研究，他们的主要成果是提出了一种仿射协变(Covariant)区域的检测方法，用于提取图像局部区域的仿射不变特征8。由于兴趣点(角点、拐点等)的信息含量高、数量相对较少且局部不变等特点，使其在基于特征的匹配中应用最广。目前在特征点提取方面，基于角点、局部不变特征点提取研究得到广泛关注。1. 角点检测方法一直以来角点没有明确的数学定义，人们普遍认为角点是二维图像亮度变化剧烈的点或图像边缘曲线上曲率极大值的点。这些点在保留图像图形重要特征的同时，可以有效地减少信息

19、的数据量，使其信息的含量很高，有效地提高了计算的速度，有利于图像的可靠匹配，使得实时处理成为可能。其在三维场景重建、运动估计、目标跟踪、目标识别、图像配准与匹配等计算机视觉领域起着非常重要的作用。目前角点的检测主要分为两大类：基于图像边缘的角点提取算法和直接基于图像灰度的角点检测。基于边缘提取的角点检测算法的基本思想是：角点是一种边缘上的点，它是一种特殊的边界点，即两条以上边界的交点。这类算法的基础就在于先检测出图像的边缘，然后再在此基础之上检测出边缘突然变换的点，就作为检测角点的结果。主要缺点是对边缘提取算法依赖性大，如果提取的边缘发生错误，或是边缘线发生中断(在实际中经常会遇到这种情况)，

20、则对角点的提取结果将造成较大影响。直接基于图像灰度的角点检测，依据角点是局部灰度和梯度变换剧烈的极大点，所以这类算法所应用的手段主要是通过计算曲率与梯度来达到检测角点的目的。由于它不需要进行边缘提取工作，所以在实际中得到了广泛的应用。目前国研究角点提取算法重点主要在已有算法的改进，如莉等基于SUSAN算法提出的RSUSAN (Redefined SUSAN)角点提取算法9，使用了更为有效和简便的计算USAN区域的方法，提高了计算速度；王建琦等人提出一种改进的角点提取方法10，该方法是基于MIC算法的改进，该算法采用了在方形窗边界上的线性插值，在插值的基础上计算出边缘角，通过它来对角点候选点做进

21、一步的筛选；华等人提出了一种新的基于形态骨架的快速拐点提取方法11，该方法基于物体条件骨架原理，采用改进的非对称开运算算子，并利用外骨架分别实现对物体凸点和凹点的提取，以保证拐点提取的完整性；坤华等人提出一种利用图像灰度特征和边界轮廓点特征相复合的角点提取方法12，克服了单一特征提取角点所带来的弊病，提高了角点提取的精度。2. 局部不变特征点提取方法局部不变特征点提取方法主要利用目标局部区域的信息来构造特征量，由于这些一定数目的局部区域可能离散地出现在目标的不同位置，当对每个区域独立地提取特征时，即使目标位于复杂环境中或有部分遮挡，通过局部特征提取仍可得到目标的部分信息，从而实现复杂背景中目标

22、的识别与确认。由于不用对目标进行分割或提取轮廓等预处理，不需要得到目标的全部信息，因此与全局的方法相比，其适用面更广。局部不变特征提取方法的研究已成为了一个非常活跃的研究方向13，出现了大批研究成果，其中部分成果已达到了实用阶段。局部不变特征提取需要解决两个问题：一是特征区域定位，即在哪里提取特征；二是区域信息描述，即用什么特征量来描述区域的信息。下面将分析和比较不同方法如何解决这两个问题。Lowe利用尺度空间性质，提出了一种尺度不变关键点(Keypoint)检测方法1415，以同时在尺度域和空间域取得极值的点作为关键点，并以关键点作为特征区域的中心，同时，关键点所在的尺度还用以确定特征区域的

23、大小。这种方法较好地同时解决了特征区域定位和大小选择的问题。在每个特征区域，Lowe以梯度方向的直方图为基础构造了一种称为SIFT（Scale Invariant Feature Transform）的局部不变特征提取性能的衡量标准。SURF是由Herbert Bay等2006年提出的另一种有效的特征提取方法16，与SIFT一样不仅可以检测出图像的兴趣点即特征，同时提供了一种创建具有不变描述器的方法。这样描述器独立地用于识别所找到的兴趣点，同时能在尺度变化、旋转、光照与视角变化与出现噪声情况下进行很好地匹配。这种不变性对于诸如需要稳定和重复性特点以用来支持目标的识别的移动机器人这样的应用程序是

24、相当重要的。通过研究SURF在处理模糊和旋转的图像时表现出很强的优点，而在视角变化和光照变化上略差一些。当相比于SIFT，SURF的速度要更快，但是在图像出现视角和光照变化上匹配的效果没有SIFT好。近年来还出现了许多局部不变特征提取方法，如基于视觉显著性的局部不变特征提取17和基于微分几何测地线概念的方法18，后者甚至对非仿射变换造成的几何形变具有很好的不变性。1.2.2 特征点匹配研究现状特征点匹配就是将不同图像上由同一场景点投影而成的特征点对找出来。由匹配线索不同，现有的匹配算法基本可以分为两大类：1) 基于窗口的匹配(Area-Based Matching,ABM)，窗口是由待匹配点附

25、近的像素灰度值组成的二维矩阵，其中最常用的是用交叉相关性来匹配，这是目前大多数匹配算法的基础。Rosenholm不使用固定大小的窗口，而是用连接窗(connected window)在全局围进行匹配)，该方法对于处理重复纹理具有较好的效果。2) 基于特征的匹配(Feature-Based Matching，FBM)，在匹配前先要抽取边或区域等特征。这些特征是图像容更抽象的描述，在不同的光照下具有更多的不变性。但是特征匹配往往有很高的计算代价。除此之外，各种匹配方法所采用的优化算法也不尽一样，有的使用全局优化算法，如动态规划法、穷举法、凸规划法和松弛法等；还有的使用一些非全局最优算法，如贪婪算法

26、，模拟退火算法和随机搜索算法等。以上的大多数方法都隐含地引入了一些约束，如动态规划法就需要顺序不变约束。当这些约束不满足时，相应的方法就无法使用。Maciel等使用线性规划的方法来解决匹配中产生的歧义问题，这种方法可以得到某种意义上的全局最优解，并且由于线性规划法已经很成熟。因此可以保证算法有较高的效率，但是线性规划法需要消耗大量的存并且要预先估计正确的匹配数。如何建立特征点之间的对应关系是基于特征点匹配方法的核心研究课题，虽然特征点匹配技术起步较晚，但是应用的迫切和前景的广泛使它引起了广大学者们的极大关注，在近十几年里得到了长足的发展，并出现大量的匹配方法。不同的图像变换模型又具有不同的匹配

27、方法，如在一些应用领域中，根据已有的先验知识可以直接计算出缩放比例，如在地球资源卫星图像的配准中，可以直接利用给定图像的比例信息，而只需要考虑在一些区域被遮挡的情况下存在的平移与旋转。这时相当于提供了一个不变量，即一幅图像中任意两个特征点的距离与另一幅图像对应的特征点之间的距离相等。这样使匹配算法能够简化为只考虑有平移、旋转的情况下求解点集之间的对应关系，但在很多实际应用中，由于存在图像噪声与视场变换还有不同时间和不同传感器获取的图像等因素，待匹配的两幅图像中不可避免出现虚假点、丢失点以与非刚性形变。基于特征点匹配方法主要分为如下几类：1)直接基于特征点属性的匹配方法(基于描述符的匹配方法)。

28、这类方法在提取特征点后，对特征点进行不同的描述，用来区别其它特征点，然后用描述符进行匹配。利用特征描述符进行匹配的方法是在特征点提取过程中，不仅得到特征点的位置，同时将得到特征点的其他仿射变换下不变的特征点描述。文献19利用颜色直方图进行描述，提出了一种快速的特征点匹配方法。SIFT描述符15将特征点周围的窗口分割成16个的子窗口，然后统计每个子窗口的方向梯度直方图。将每个子窗口的方向分成8个方向计算。一共具有个子窗口，每个窗口描述是8位的，描述8个方向的梯度的大小值，这样形成的描述符是维，匹配时只需利用描述符进行配对。2)基于特征点几何结构的匹配方法20。这类方法不直接对特征点逐一进行匹配，

29、它利用特征点之间相似和稳定几何结构，如边、三角形等进行匹配。近年来还出现了许多特征点匹配方法，如D Skea提出了一个累加器算法21，其核心思想是平面点模式匹配的一个框架，该算法对噪声和缺少点与伪点较为鲁棒，但计算复杂度较大。Sanjay Ranade and AzrielRosenfeld提出松弛法进行点匹配2，志刚等在其基础上通过构建三角形并利用其相似度来定义点特征的匹配度，提出了一种新的具有比例与旋转不变特性的点特征松弛匹配算法22。Shih-hsu Chang等人利用二维聚类进行匹配23，立华等利用不可约矩阵和相对不变量理论提出了几种点模式匹配新算法24，它们可分别用来解决相似变换和仿

30、射变换下具有一样点数的两个点模式的匹配问题。Li利用了几何不变量来进行点模式匹配25，Spirkovska和Reid利用了高阶神经网络进行匹配26。基于图像特征的匹配方法可以克服利用图像灰度信息进行匹配的缺点，由于图像的特征点比图像总的像素要少很多，这样就大大减少了匹配过程的计算量；而且特征点的提取过程可以减少噪声的影响，对灰度变化，图像形变以与遮挡等都有较好的适应能力。1.3 研究容特征点提取过程中，需要构建在多种变换下具有良好不变性的特征点提取算法以获得具有精确性高，区分度强的不变性图像特征，并综合特征局部结构信息，构造特征描述算子。由于时间、视角、环境的变化、多种传感器的使用等，使拍摄的

31、图像不仅受到噪声的影响，而且存在严重的灰度失真和几何畸变。在这种条件下，匹配算法如何达到精度高、匹配正确率高、速度快、鲁棒性和抗干扰性强以与并行实现成为人们追求的目标。本文在研究现有的一些特征检测算法与匹配方法基础上，以计算机视觉的不变理论为基础，本文主要研究容如下所述。1. 图像不变特征点提取算法研究图像特征点提取是基于特征点匹配方法的首要步骤，在实际问题中，图像可能受到噪声、背景的干扰，也可能发生光照、尺度、旋转、仿射等变化，如何选择合理的图像特征点，使得这些特征点不仅具有良好的抗噪性能，而且在上述变化下保持不变，直接决定了基于特征点的匹配方法效果。由于后续匹配方法需要图像在旋转和尺度变换

32、下仍满足一定比例的有效点，所以本文需要对旋转和尺度不变特征点的提取进行研究。2. 图像特征点匹配方法研究图像特征点匹配的目的是在两幅图像之间建立尽可能多的匹配点对。它是图像分析和处理的基本问题。图像特征点匹配方法目前主要分为两种，即为基于描述符的特征点匹配方法和基于特征点几何结构的匹配方法。基于描述符的匹配方法对有效点的要求低，适合图像视角变换、轻微变形情况，但是实现复杂，对图像纹理要就比较高；而基于几何结构的匹配方法实现简单、纹理要求低，但是抗图像形变、视角变化能力差，算法时间复杂度比较高。所以本文需要对图像特征点的匹配方法进行研究，探求更有效、性能更好的图像特征点匹配方法。1.4 论文组织

33、结构本文将图像特征点的提取方法以与特征点匹配方法作为主要研究对象，针对图像存在旋转和尺度变化的情况，利用改进H/S算法提取图像中特征点，并在分析比较两种常用特征点匹配方法基础上，提出了一种改进的相似三角形特征点匹配算法。本文的篇章结构安排如下：第一章为绪论，介绍了图像特征点、图像匹配基本概念，相关领域研究现状，最后阐述了本文的主要研究工作和篇章结构。 第二章主要比较目前常用的两种特征点匹配方法，分别介绍Harris角点检测算法和基于描述符的SIFT算法，并分析两种方法的优缺点和适用场合，第三章主要在分析特征点提取算法的基础上，着重介绍特征点检测实验效果好的Harris算法，针对传统Harris

34、算法存在的局限性，引入尺度空间理论和特征描述思想，提出改进的H/S算法。第四章在前面研究的基础上，提出一种改进的相似三角形特征点匹配方法，改进方法将传统被动的同向相似三角形检索方法变为在复数空间下选择基线后主动构造相似三角形，提高了算法的效率。并利用特征点组成基线向量后得到三角形组形成多个模板在实物图中进行匹配，提高了三角形匹配算法的实时性和稳定性。最后一章对全文工作进行总结，并提出今后研究的问题与方向。第二章 图像特征点提取算法研究图像特征点提取是图像处理和计算机视觉的基本技术，它也是特征点匹配方法的首要步骤。实际图像可能受到噪声、背景的干扰，也可能发生光照、尺度、旋转、仿射等变化，图像特征

35、点的选择合理和特征点提取质量，直接决定了特征点匹配方法的效果。本章针对实际情况的复杂多样性，对两种特征点提取方法(Harris算法和SIFT算法)进行分析研究。2.1 Harris特征点提取算法角点作为目前图像匹配中常用的特征点，它是二维图像亮度变化剧烈或图像边缘曲线上曲率极大值的点，决定了目标的轮廓特征，因此被广泛应用于摄像机标定、虚拟场景重建、运动估计、图像配准等计算机视觉处理任务中。角点检测方法分为基于边缘的提取方法和基于图像灰度的提取方法。前者往往需要对图像边缘进行编码，这在很大程度上依赖于图像的分割和边缘提取，而这两种操作本身就具有相当大的难度和计算量，况且一旦待检测目标局部发生变化

36、(例如被部分遮挡)，则很可能导致图像分割和图像边缘提取操作的失败，所以这种方法的适用围很小；而基于图像灰度的方法则避开了上述这些缺陷，它考虑的是像素点邻域的灰度变化，而不是整个目标的边缘轮廓。它通过计算曲率与梯度来达到检测角点的目的。由于它不需要进行边缘提取工作，所以在实际中得到了广泛的应用。目前在图像匹配中，常见的基于灰度的角点提取算法主要有Moravec算法，SUSAN算法和Harris算法等。Schmid27对Moravec，SUSAN和Harris等基于图像灰度的角点检测方法从重复率和角点周围的局部区域所包含的信息量两个方面进行了对比。实验结果表明Moravec，SUSAN算法存在较多

37、的误检测和漏检测现象，且对旋转前后的图像角点检测不一致，而Harris角点检测法具有最好的效果。因此本节主要分析Harris算法。2.1.1 Harris特征点检测原理Harris 角点检测算法是一种基于信号的点特征提取算子，它的思想是在图像中设计一个局部检测窗口，当该窗口沿各个方向作微小移动时，考察窗口的平均能量变化，当该能量变化值超过设定的阈值时，就将窗口的中心像素点提取为角点。Harris角点检测公式为： (2.1)其中，为窗函数，为图像灰度的梯度值。可为矩形窗或高斯窗。对于每个小的位移量，检测公式可双线性近似表示为： (2.2)其中 (2.3)设，是矩阵的两个特征值，则可表示局部自相关

38、函数的曲率。实际运用中用来计算角点的响应函数可以写成：(2.4)其中，当某个区域矩阵的主对角线之和很大时，则表明这是一条边；当矩阵的行列式很大时，则表明这是一条边或一个角点，一般取经验值0.04。2.1.2 Harris特征点检测步骤应用Harris方法提取图像中角点的过程可以分为以下几步：1) 计算图像像素点在水平和垂直方向上的梯度，以与两者的乘积，得到M公式(2.3)中4个元素的值, 其中，、分别表示在x ,y方向上的一阶导数。2) 对图像进行高斯滤波，得到新的M。离散二维零均值高斯函数(2.5)3) 计算原图像上对应的每个像素点的兴趣值，即R值(角点量cim)。(2.6)4) 选取局部极

39、值点。Harris方法认为，特征点是局部围的极大兴趣值对应的像素点。5) 设定阈值，选取一定量的角点。2.1.3实验分析实验实现Harris角点检测算法，测试其在图像存在旋转、尺度变化、噪声等情况下的检测效果，并分析Harris算法在设置不同阈值情况下提取角点。实验所提取的角点用十字划线来标识。1. 旋转不变性图2.1(a)为原图角点提取结果，图2.1(b)为经过逆时针旋转30度后的图像角点提取结果。从图中可以看出，Harris算法在图像旋转时检测得到角点的重复数很高，具有良好的抗旋转性能。(a)原图像(b)逆时针旋转30度图像图2.1 图像旋转角点提取结果图 2. 尺度变化不变性图像2.2(

40、a)为原图像，2.2(b)为尺度变化后图像角点检测结果，由结果图可以看出Harris算法在尺度发生变化时图像中检测得到的特征点与原图有较大差别。(a)原图像(b)放大2倍图像图2.2 图像尺度变化角点提取结果图3. 噪声情况下的不变性Harris角点检测算法对于噪声比较敏感，图2.3为原图像和增加10%高斯噪声后采用Harris提取出角点的结果图。图(a)为原图像，(b)为增加高斯噪声后图像，从结果图中可以明显看出，增加高斯噪声后运用Harris算法提取出的角点准确性下降。(a) 原图像(b) 添加10%高斯噪声图像图2.3 图像添加噪声时角点提取结果图4. 设置不同阈值时角点不变性由前文针对

41、Harris算法提取角点步骤可知，设置阈值大小不同时得到的角点数目也随之改变，图2.4为不同阈值条件下提取角点结果图。从图中可以看出，将阈值设定较高时，检测得到的角点数量明显下降。(a)阈值设置为5000(b)阈值设置为10000(c)阈值设为15000(d)阈值设置为20000图2.4 设置不同阈值时角点提取结果图通过对Harris算法提取图像特征点的原理与实验结果分析，可以看出Harris算法在图像存在旋转情况下有很高的点重复数，是一种比较有效的点特征提取算法。因此在图像配准常采用这种算法来提取特征点。但是Harris特征点检测算法也存在着一定的局限性。当图像间发生尺度变换时，Harris

42、角点就可能检测出不一致的角点。即当尺度变化时，可能检测出新的角点，或老的角点发生移位或消失。这样特征点的重复数下降，不利于后续特征点匹配。同时由于Harris算法采用了偏导来计算角点函数，虽然经过高斯滤波，但对噪声仍比较敏感。2.2 SIFT特征点提取算法由上节对Harris特征点提取算法局限性的分析，本节对目前国外研究广泛的局部不变特征点提取算法SIFT进行研究，该算法提取出的特征点对图像尺度和旋转不变性效果好，对光线变化和噪声变化也具有较好鲁棒性。2.2.1 SIFT特征点提取算法原理与步骤SIFT算法是Lowe14利用尺度空间性质提出的一种尺度不变关键点的检测方法，主要利用目标局部区域的

43、信息来构造特征量，它以同时在尺度域和空间域取得极值的点作为关键点，并以关键点作为特征区域的中心，同时关键点所在的尺度还用以确定特征区域的大小，在每个特征区域以梯度方向的直方图为基础得到局部不变特征向量。SIFT特征点提取方法首先对图像进行预处理，通过采用高斯差分金字塔分层结构提取出图像中的极值点作为侯选，并对这些侯选特征点进一步筛选掉其中低对比度和处于边缘的点，最终提取出稳定的特征点。SIFT特征点提取算法主要执行流程如图2.5所示。图2.5 SIFT算法流程1. 尺度空间极值求取SIFT方法第一步就是找出尺度空间的极值，首先构建图像的尺度空间函数。1) 高斯差分图像DOG生成高斯卷积核是实现

44、尺度变换的唯一线性核，一副输入图像: （2.7）其中是在和之间的卷积运算符， (2.8)是空间坐标，是尺度坐标。为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间(DOG scale-space)。利用不同尺度的高斯差分核与图像卷积生成。(2.9)一种有效的构建高斯差分函数的方法可以通过图2.6介绍。首先对图像进行预处理以消除图像模糊，对提取稳定的特征点有好处。采用高斯函数先对图像进行卷积运算，以达到预处理的目的。接着对图像使用不同的采样距离以形成一个金字塔图像分层结构，在第一次采样时每0.5个像素距离进行采样，这就意味着将原来图像放大一倍，第一次采样的图像作为第一组的图像，然后以

45、成倍的采样距离即1、2、4个像素再分别对图像进行采样从而产生第二、三、四组的图像。这样就形成一个金字塔形状的图像分层结构。不同采样形成金字塔分层结构，然后用高斯核函数对其进行滤波形成高斯金字塔图像分层结构，对各层图形进行高斯滤波时分别采用不同的高斯滤波因子。在图2.6左侧高斯金字塔各层中标识了高斯滤波函数的滤波因子。原始图像通过高斯函数进行卷积生成一组图像，这些图像在尺度空间中借助常量k被分离，如图2.6左侧所示。再将尺度空间中的每组分隔成一整数的间隔，令k =，所以，每组中的图像数必须为s+3个，极值检测才能覆盖一组中所有图像，论文中s为2。图2.6中的右列显示了将每组中相邻图像相减生成高斯

46、差分图像的结果。利用高斯差分金字塔分层结构提取出图像中的极值点作为候选特征点，并对这些候选特征点进一步筛选掉其中低对比度和处于边缘的特征点，最终提取出稳定的特征点。在文中取为，在图2.6中第二组中的第一层图像的滤波因子如图所示是取第一组中第三层中的图像的滤波因子，第二层滤波因子增加k倍，依次增加滤波因子直到最高层第五层。第三组和第四组中图像层的滤波因子也和上面的方法一样，依次增加滤波因子。 高斯 双高斯差（DoG）图2.6 候选特征点生成图2) 空间极值点检测为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图2.7所示，中间的检测点

47、和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。小尺度4x4中尺度2x2大尺度1x1图2.7 DoG尺度空间局部极值检测2. 特征点位置确定一旦通过上面步骤得到了侯选特征点，下一步就是确定稳定特征点的位置、尺度、曲率等信息。通过下面操作可以将侯选特征点中低对比度(对噪声敏感)或位于边缘的侯选特征点过滤掉。1) 精确确定极值点位置通过拟和三维二次函数以精确确定关键点的位置和尺度(达到亚像素精度)，同时去除低对比度的关键点和不稳定的边缘响应点(因为DoG算子会产生较强的边缘响应)，以增强匹配稳定性、提高抗噪声能力。2) 边

48、缘响应的去除一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在垂直边缘的方向有较小的主曲率。主曲率通过一个22的Hessian矩阵H求出: (2.10)导数由采样点相邻差估计得到。D的主曲率和H的特征值成正比，令为最大特征值，为最小的特征。(2.11)(2.12)令，则：(2.13)的值在两个特征值相等的时候最小，随着的增大而增大，因此，为了检测主曲率是否在某域值下，只需检测(2.14)在Lowe的文章15中，取10。3. 特征点方向确定基于图像属性为每个特征点赋一个方向，在后面特征点描述符中将会用到特征点的方向并对特征点的特性进行描述。利用关键点邻域像素的梯度方向分布特性为

49、每个关键点指定方向参数，使算子具备旋转不变性。在实际计算时，在以关键点为中心的邻域窗口采样，并用直方图统计邻域像素的梯度方向。梯度直方图的围是0360度，其中每10度一个柱，总共36个柱。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。在梯度方向直方图中，当存在另一个相当于主峰值80%能量的峰值时，则将这个方向认为是该关键点的辅方向。一个关键点可能会被指定具有多个方向(一个主方向，一个以上辅方向)，这可以增强匹配的鲁棒性。 4. 特征点描述符的确定通过以上步骤得到了每个特征点的位置、尺度、方向,下一步将为每个特征点建立一个描述符，使其不随各种变化而变化，比如光线变化、视角

50、变化等。并且特征点描述符要尽量与众不同，以便于特征点间的匹配。将坐标轴旋转为关键点的方向，以确保旋转不变性。为了增强匹配的稳健性，Lowe建议对每个关键点使用4×4共16个种子点来描述，这样对于一个关键点就可以产生128个数据，即最终形成128维的SIFT特征向量。此时SIFT特征向量已经去除了尺度变化、旋转等几何变形因素的影响，再继续将特征向量的长度归一化，则可以进一步去除光照变化的影响。2.2.2 实验分析实验测试SIFT不变特征提取算法与采用特征点欧氏距离法最近邻(NN)匹配方法的效果与性能，通过其在旋转、尺度变化、噪声干扰、照度变化等情况下的匹配实验的结果分析，验证该算法在图

51、像匹配时的有效性与适用性。实验实现SIFT与最近邻匹配算法时，利用了开源函数库(OpenCV)，它包含了一系列C函数和少量C+类。在安装好Visual C+的Windows操作系统下运行安装文件完成安装过程。每创建一个将要使用OpenCV的VC+Project都需要给它指定需要的lib菜单：Project->Settings,然后将Settings for选为All Configurations，选择右边的link标签，在Object/library modules附加上：Cxcore.lib cv.lib ml.lib cvaux.lib highgui.lib cvcam.lib。实

52、验结果图中提取出的特征向量用箭头表示，箭头起点表示特征点在图像中的二维坐标位置，箭头长度代表了关键点所处的尺度，箭头方向代表了该尺度下关键点所处邻域的主梯度方向。在匹配结果图中将识别出的匹配点用直线进行连接。1. 旋转不变性图2.8(a)为原图像特征向量提取图，图2.8(b)为经过逆时针旋转40度图像特征向量提取图，图像匹配结果如图2.8(c)所示。(a)中提取出149个特征点，(b)中提取出129个特征点，(c)中有70个特征点匹配到。在图像存在旋转情况下，两幅图像提取得到较多不变特征点，验证该算法在尺度变化时的不变性。图2.8(d)与(e)为对应的一个特征区域的局部放大图像，从图中可以看出

53、，这两个区域容基本一样。(a)原图特征向量(d)原图局部(b)旋转40度特征向量(c)图像旋转时匹配结果(e)旋转图局部图2.8 局部旋转不变特征提取与匹配图2. 一定围的尺度不变性图2.9(a)、(b)为原图与尺度变化时特征向量提取图，图像匹配结果如图2.9(c)，(a)中提取出129个特征点，(b)提取出99个特征点，(c)中有29个特征点匹配到，由匹配结果可以看出，在图像尺度发生变化时，两幅图像提取得到得不变特征点数量较少，表明其在尺度变化时仅能在较小围得到不变特征点。(a)原图特征向量(b)尺度变化图特征向量(c)图像尺度变化时匹配结果图2.9 图像尺度不变特征提取与匹配图 3. 图像

54、旋转、缩放共存条件时不变性图2.10(a)为原图特征向量提取图，2.10(b)为旋转、缩放共存时特征向量提取图，匹配结果如图2.10(c)所示。(a)中提取出846个特征点，(b)中提取出426个特征点，(c)中有163个特征点匹配到。(a)原图像特征向量(b)图像旋转、缩放共存时特征向量(c)图像旋转、缩放共存匹配结果图2.10 旋转、缩放共存时不变特征提取与匹配图4. 光照、噪声条件变化时不变性图2.11(a)、(b)为不同光照条件下特征向量提取图，(a)图提取出532个特征点，(b)图提取出446个特征点，匹配结果如图2.11(c)中有15个特征点匹配到；2.12(b)为在原图基础上添加

55、10%高斯噪声后特征点提取结果图。2.12(a)中提取出532个特征点，2.12(b)图提取出428个特征点，匹配结果如图2.12(c)中85个特征点匹配到。(a)原图特征向量(b)光照变化特征向量(c)图像光照变化时匹配结果图2.11 光照变化不变特征提取与匹配图(a)原图特征向量(b)添加10%噪声特征向量(c)图像添加10%噪声匹配图图2.12 添加噪声不变特征提取与匹配图根据前文对SIFT特征点提取算法原理研究，从实验结果可以看出该算法提取出的特征点对图像的旋转、缩放与光照、噪声变化时表现出较强的鲁棒性。但该算法在对提取出的特征点进行描述时，采用128维的高维度向量，算法速度较慢；其次

56、该算法基于局部区域描述，这就要求图像满足足够多的纹理，否则构造出的向量区别性就不是很大，容易造成误匹配。2.3 本章小结本章在分析特征点提取重要性的基础上，首先对Harris角点提取算法进行研究，实验表明该算法检测效率高，针对图像存在旋转情况下有很高的点重复率，是一种比较有效的点特征提取算法，但它在尺度和噪声发生变化情况下表现的鲁棒性差；针对Harris 算法的不足，对局部不变特征点提取SIFT算法进行研究，实验表明该算法提取出的特征点对图像的旋转、缩放与光照、噪声变化时表现出较强的鲁棒性，但该算法速度较慢，并且要求图像满足足够多的纹理。第三章 改进的H/S特征点提取算法经过前面章节的分析，不

57、同的特征点提取算法具有各自的优缺点，单一的方法在具体的应用中，具有一定的局限性。比较分析Harris角点检测算法和SIFT特征点提取算法，扬长避短，对它们进行有效的结合，使特征点的提取获得更好的效果。本章在改进Harris算法关键步骤的基础上，结合SIFT算法中所使用的多尺度理论和特征点描述思想进行结合的方案进行研究。提出了一种新的图像特征点提取算法H/S(Harris-SIFT)算法。3.1 H/S算法分析3.1.1 H/S算法提出的可行性分析上一章详细介绍了Harris角点检测算法和SIFT特征点提取算法，两种方法都有自己的优缺点，这给两种方法的结合形成新的特征点提取方法提供了条件。首先对于Harris角点检测算法来说，它是基于图像灰度的提取算法，通过计算曲率与梯度来达到检测角点的目的，特征点的检测效率高。特征点定位较准确，对局部噪声不敏感，且计算速度快，但是它是在单一尺度下检测角点，若选用较小窗口高斯卷积后提取角点时则会因为噪声等因素导致