本科毕业设计(论文) 题目名称：
学院：
专业年级：
学生姓名：
班级学号：
指导教师：
二O一O年月日
目录
摘要 ................................................................................................................................ III ABSTRACT ....................................................................................................................... IV 第一章绪论 (1)
1.1 研究背景 (1)
1.2 研究现状综述 (2)
1.2.1 特征点提取研究现状 (2)
1.2.2 特征点匹配研究现状 (4)
1.3 研究内容 (5)
1.4 论文组织结构 (6)
第二章图像特征点提取算法研究 (8)
2.1 Harris特征点提取算法 (8)
2.1.1 Harris特征点检测原理 (8)
2.1.2 Harris特征点检测步骤 (9)
2.1.3 实验分析 (9)
2.2 SIFT特征点提取算法 (12)
2.2.1 SIFT特征点提取算法原理及步骤 (12)
2.2.2 实验分析 (16)
2.3 本章小结 (19)
第三章改进的H/S特征点提取算法 (20)
3.1 H/S算法分析 (20)
3.1.1 H/S算法提出的可行性分析 (20)
3.1.2 H/S算法结合方案研究 (21)
3.2 H/S算法实现 (22)
3.2.1 多尺度特征点检测 (22)
3.2.2 特征点描述 (23)
3.3 实验分析 (25)
3.3.1 算法评价标准 (25)
3.3.2 分情况特征点提取结果分析 (25)
3.4 本章小结 (28)
第四章基于H/S的特征点匹配方法 (29)
4.1 相似三角形方法局限性分析 (29)
4.1.1 三角形匹配原理 (29)
4.1.2 三角形相似方法局限性 (31)
4.2 改进的相似三角形匹配方法实现 (31)
4.2.1 三角形选取方案研究 (32)
4.2.2 相似三角形检索方法改进 (33)
4.2.3 多模板改进方法分析 (35)
4.3 实验结果与分析 (36)
4.4 本章小结 (39)
第五章工作总结与展望 (40)
5.1 工作总结 (40)
5.2 工作展望 (41)
致谢 (42)
参考文献 (43)
摘要
图像匹配是图像处理领域的基础课题，在图像拼接、全景视图、对象识别等计算机视觉方面有广泛应用。图像匹配分为基于灰度的方法和基于特征的方法，前者简单易行，但算法时间复杂度高，难以处理图像存在旋转和尺度变化等情况，后者在适应性和速度方面有很大优势，但图像特征的提取以及如何建立特征之间的对应关系一直是这类方法的研究难题。本文提出了一种新的特征点检测算法，并根据三角形相似原理，提出一种改进特征点匹配方法。
本文首先对两种特征点提取算法(Harris算法和SIFT算法)进行分析比较，Harris 角点检测算法效率高，但对尺度变化和抗噪性的鲁棒性差，SIFT算法对尺度变化及抗噪性鲁棒性好，但算法时间复杂度高，且对图像纹理要求高，本文结合两种算法的优点，提出了一种新的H/S特征点提取算法，该算法特征点检测效率高，并且尺度不变性及抗噪性得到很大改善。
在采用新的H/S特征点提取算法得到图像中特征点后，对特征点匹配方法进行研究。传统的三角形相似匹配方法虽然实现简单，鲁棒性好，但时间复杂度高，针对此局限性，本文提出了一种改进三角形匹配方法，将传统方法被动搜索相似三角形变为在复数空间下选择基线后主动构造相似三角形，并利用特征点组成基线向量对应三角形组得到多个模板在实物图中匹配，提高了改进算法的实时性和稳定性。
关键词特征点，H/S算法，机器视觉，相似三角形检索
ABSTRACT
Image 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. The former method is simple, but the time complexity of this algorithm is high, especially it’s 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 corresponding 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 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 texture. 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 using 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 triangles, 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 WORDS feature points, H/S algorithm, computer vision, similar triangles retrieval
第一章绪论
1.1 研究背景
图像特征点提取和匹配是图像处理研究领域中的基础课题，也是机器视觉的关键技术之一，广泛应用于虚拟现实、视频压缩、图像复原、图像数据库检索等技术中，具有广泛的应用前景及社会经济价值。因此，特征点的提取和匹配越来越得到研究人员的关注。
图像匹配可以认为是在不同时间或相同时间、从不同视角或相同视角对同一场景拍摄的两幅或者多幅图像进行的空间域上的匹配过程。它通过建立两幅图像之间的对应关系，确定相应的几何变换参数，对两幅图像中的同一目标进行匹配。近几年在许多领域中，都对图像配准进行了大量的研究，比较有代表的有：模式识别、自动导航、遥感领域、医学诊断、计算机视觉等。
经过国内外研究者多年的努力，人们提出了多种图像匹配方法。这些方法大致可分为基于灰度值的方法和基于特征的方法两大类[1]。基于灰度的匹配就是逐像素地把一个以一定大小的实时图像窗口的灰度矩阵与实际图像的所有可能的窗口灰度矩阵按某种相似性度量方法进行搜索比较的匹配方法。为了克服基于灰度匹配方法缺点，提出了基于特征的匹配方法。特征匹配方法首先对图像进行预处理来提取其高层次的特征，然后建立两幅图像之间特征的匹配对应关系，常用的特征基元有点特征、边缘特征和曲线轮廓及区域特征等。由于兴趣点(角点、拐点等)的信息含量高、数量相对较少且局部不变等特点，使其在基于特征的匹配中有更加广泛的应用。如何建立图像兴趣点之间的对应关系一直是这类方法的研究热点。目前已有许多有关此类问题的如Sanjay Ranade等提出的松弛算法[2]、Zsolt Miklós等提出的三角形匹配算法[3]等。
特征点匹配方法首先依赖于好的特征提取方法，特征点提取方法是从众多特征中求出那些对分类识别最有效的特征，从而实现特征空间维数或数据量的压缩。特征提取方法一般包含两个阶段：一是对图像进行分割，提取目标区域或其边界，抽取目标的基本特征，如灰度、纹理、形状描述。二是找出或构造目标作某种运动或无论目标作何种运动都不变化的目标图像特性的特征不变量。当提取特征点数目过多时就会存在大量的干扰信息(如：伪匹配点)，这将影响匹配的正确率和速度，当提取特征点过少时，将不利于精确匹配。同时特征点匹配方法需要保证在两幅图像点集中存有大量有效点，而当图像特征点较多时，算法复杂度较大。
本文基于以上热点问题展开研究，首先对两种特征点提取算法(Harris算法和
SIFT算法)进行原理分析及实验比较，得出Harris角点检测算法效率高，但对尺度变化和噪声干扰鲁棒性差，以及SIFT算法对尺度变化及抗噪性鲁棒性好，但算法时间复杂度高，且对图像纹理要求高等结论，提出一种在多尺度下提取图像稳定特征点的H/S(Harris/SIFT)算法，并在此基础上采用复数空间中相似三角形多模版匹配算法进行特征点间匹配，通过理论分析及实验证明该方法在时间复杂度方面的改进和在图像存在旋转、缩放情况时匹配的准确性和有效性。
1.2 研究现状综述
1.2.1 特征点提取研究现状
在实际问题中图像可能受到噪声、背景的干扰，也可能发生平移、尺度、视角、光照等变化，如何选择合理的特征和描述算子，使得这些特征不仅具有良好的表征性能，而且在上述因素变化下保持相对不变(即不变性)，直接决定了基于特征点的图像匹配效果。以计算机视觉的不变理论为基础，对图像特征的不变性研究是目前图像处理的重要环节，吸引了众多研究工作者的兴趣。
图像特征的不变性研究目前已取得了大量的研究成果。这些研究主要集中于以下几方面：1) 不变特征的选取，如图像的点、线、轮廓，像素点的强度、曲率、矩、特征向量等。2) 不变性获取的途径，如通过特征变换、小波理论、神经网络、编码技术、特征描述子的构造等。3) 不变特征的描述，如SIFT描述子、PCA-SIFT描述子、不变矩描述子、傅里叶描述子、微分不变描述子、颜色描述子、链码描述子等。
近年来，不变特征已引起国内外研究者和研究机构的广泛关注。在相关领域中，具有代表性的研究机构是加拿大British Columbia大学智能计算实验室，该实验室开展了局部仿射不变特征提取方面的工作，其研究成果已应用于目标识别[4]、全景图拼接[5]、虚拟现实[6]、机器人自主导航[7]等领域。芬兰的Oulu大学机器视觉小组于2004年开始进行几何不变性方面的研究，提出了一种具有完全仿射不变性的特征提取方法，并用于目标识别与配准。Oxford大学的机器人研究小组开展视觉不变性方面的研究，他们的主要成果是提出了一种仿射协变(Covariant)区域的检测方法，用于提取图像局部区域的仿射不变特征[8]。
由于兴趣点(角点、拐点等)的信息含量高、数量相对较少且局部不变等特点，使其在基于特征的匹配中应用最广。目前在特征点提取方面，基于角点、局部不变特征点提取研究得到广泛关注。
1. 角点检测方法
一直以来角点没有明确的数学定义，人们普遍认为角点是二维图像亮度变化剧烈的点或图像边缘曲线上曲率极大值的点。这些点在保留图像图形重要特征的同时，可以有效地减少信息的数据量，使其信息的含量很高，有效地提高了计算的速度，
有利于图像的可靠匹配，使得实时处理成为可能。其在三维场景重建、运动估计、目标跟踪、目标识别、图像配准与匹配等计算机视觉领域起着非常重要的作用。目前角点的检测主要分为两大类：基于图像边缘的角点提取算法和直接基于图像灰度的角点检测。
基于边缘提取的角点检测算法的基本思想是：角点是一种边缘上的点，它是一种特殊的边界点，即两条以上边界的交点。这类算法的基础就在于先检测出图像的边缘，然后再在此基础之上检测出边缘突然变换的点，就作为检测角点的结果。主要缺点是对边缘提取算法依赖性大，如果提取的边缘发生错误，或是边缘线发生中断(在实际中经常会遇到这种情况)，则对角点的提取结果将造成较大影响。
直接基于图像灰度的角点检测，依据角点是局部内灰度和梯度变换剧烈的极大点，所以这类算法所应用的手段主要是通过计算曲率及梯度来达到检测角点的目的。由于它不需要进行边缘提取工作，所以在实际中得到了广泛的应用。
目前国内研究角点提取算法重点主要在已有算法的改进，如杨莉等基于SUSAN 算法提出的RSUSAN (Redefined SUSAN)角点提取算法[9]，使用了更为有效和简便的计算USAN区域的方法，提高了计算速度；王建琦等人提出一种改进的角点提取方法[10]，该方法是基于MIC算法的改进，该算法采用了在方形窗边界上的线性插值，在插值的基础上计算出边缘角，通过它来对角点候选点做进一步的筛选；李华等人提出了一种新的基于形态骨架的快速拐点提取方法[11]，该方法基于物体条件骨架原理，采用改进的非对称开运算算子，并利用内外骨架分别实现对物体凸点和凹点的提取，以保证拐点提取的完整性；张坤华等人提出一种利用图像灰度特征和边界轮廓点特征相复合的角点提取方法[12]，克服了单一特征提取角点所带来的弊病，提高了角点提取的精度。
2. 局部不变特征点提取方法
局部不变特征点提取方法主要利用目标局部区域的信息来构造特征量，由于这些一定数目的局部区域可能离散地出现在目标的不同位置，当对每个区域独立地提取特征时，即使目标位于复杂环境中或有部分遮挡，通过局部特征提取仍可得到目标的部分信息，从而实现复杂背景中目标的识别与确认。由于不用对目标进行分割或提取轮廓等预处理，不需要得到目标的全部信息，因此与全局的方法相比，其适用面更广。局部不变特征提取方法的研究已成为了一个非常活跃的研究方向[13]，出现了大批研究成果，其中部分成果已达到了实用阶段。局部不变特征提取需要解决两个问题：一是特征区域定位，即在哪里提取特征；二是区域内信息描述，即用什么特征量来描述区域内的信息。下面将分析和比较不同方法如何解决这两个问题。
Lowe利用尺度空间性质，提出了一种尺度不变关键点(Keypoint)检测方法[14][15]，以同时在尺度域和空间域取得极值的点作为关键点，并以关键点作为特征区域的中心，同时，关键点所在的尺度还用以确定特征区域的大小。这种方法较好地同时解
决了特征区域定位和大小选择的问题。在每个特征区域内，Lowe以梯度方向的直方图为基础构造了一种称为SIFT（Scale Invariant Feature Transform）的局部不变特征提取性能的衡量标准。
SURF是由Herbert Bay等2006年提出的另一种有效的特征提取方法[16]，与SIFT 一样不仅可以检测出图像的兴趣点即特征，同时提供了一种创建具有不变描述器的方法。这样描述器独立地用于识别所找到的兴趣点，同时能在尺度变化、旋转、光照及视角变化及出现噪声情况下进行很好地匹配。这种不变性对于诸如需要稳定和重复性特点以用来支持目标的识别的移动机器人这样的应用程序是相当重要的。通过研究SURF在处理模糊和旋转的图像时表现出很强的优点，而在视角变化和光照变化上略差一些。当相比于SIFT，SURF的速度要更快，但是在图像出现视角和光照变化上匹配的效果没有SIFT好。
近年来还出现了许多局部不变特征提取方法，如基于视觉显著性的局部不变特征提取[17]和基于微分几何测地线概念的方法[18]，后者甚至对非仿射变换造成的几何形变具有很好的不变性。
1.2.2 特征点匹配研究现状
特征点匹配就是将不同图像上由同一场景点投影而成的特征点对找出来。由匹配线索不同，现有的匹配算法基本可以分为两大类：1) 基于窗口的匹配(Area-Based Matching,ABM)，窗口是由待匹配点附近的像素灰度值组成的二维矩阵，其中最常用的是用交叉相关性来匹配，这是目前大多数匹配算法的基础。Rosenholm不使用固定大小的窗口，而是用连接窗(connected window)在全局范围内进行匹配)，该方法对于处理重复纹理具有较好的效果。2) 基于特征的匹配(Feature-Based Matching，FBM)，在匹配前先要抽取边或区域等特征。这些特征是图像内容更抽象的描述，在不同的光照下具有更多的不变性。但是特征匹配往往有很高的计算代价。除此之外，各种匹配方法所采用的优化算法也不尽相同，有的使用全局优化算法，如动态规划法、穷举法、凸规划法和松弛法等；还有的使用一些非全局最优算法，如贪婪算法，模拟退火算法和随机搜索算法等。以上的大多数方法都隐含地引入了一些约束，如动态规划法就需要顺序不变约束。当这些约束不满足时，相应的方法就无法使用。Maciel 等使用线性规划的方法来解决匹配中产生的歧义问题，这种方法可以得到某种意义上的全局最优解，并且由于线性规划法已经很成熟。因此可以保证算法有较高的效率，但是线性规划法需要消耗大量的内存并且要预先估计正确的匹配数。
如何建立特征点之间的对应关系是基于特征点匹配方法的核心研究课题，虽然特征点匹配技术起步较晚，但是应用的迫切和前景的广泛使它引起了广大学者们的极大关注，在近十几年里得到了长足的发展，并出现大量的匹配方法。不同的图像变换模型又具有不同的匹配方法，如在一些应用领域中，根据已有的先验知识可以
直接计算出缩放比例，如在地球资源卫星图像的配准中，可以直接利用给定图像的比例信息，而只需要考虑在一些区域被遮挡的情况下存在的平移与旋转。这时相当于提供了一个不变量，即一幅图像中任意两个特征点的距离与另一幅图像对应的特征点之间的距离相等。这样使匹配算法能够简化为只考虑有平移、旋转的情况下求解点集之间的对应关系，但在很多实际应用中，由于存在图像噪声及视场变换还有不同时间和不同传感器获取的图像等因素，待匹配的两幅图像中不可避免出现虚假点、丢失点以及非刚性形变。
基于特征点匹配方法主要分为如下几类：1)直接基于特征点属性的匹配方法(基于描述符的匹配方法)。这类方法在提取特征点后，对特征点进行不同的描述，用来区别其它特征点，然后用描述符进行匹配。利用特征描述符进行匹配的方法是在特征点提取过程中，不仅得到特征点的位置，同时将得到特征点的其他仿射变换下不变的特征点描述。文献[19]利用颜色直方图进行描述，提出了一种快速的特征点匹配方法。SIFT描述符[15]将特征点周围的1616
?窗口分割成16个44
?的子窗口，然后统计每个子窗口的方向梯度直方图。将每个子窗口的方向分成8个方向计算。一共具有44
?个子窗口，每个窗口描述是8位的，描述8个方向的梯度的大小值，这样形成的描述符是844128
??=维，匹配时只需利用描述符进行配对。2)基于特征点几何结构的匹配方法[20]。这类方法不直接对特征点逐一进行匹配，它利用特征点之间相似和稳定几何结构，如边、三角形等进行匹配。
近年来还出现了许多特征点匹配方法，如D Skea提出了一个累加器算法[21]，其核心思想是平面点模式匹配的一个框架，该算法对噪声和缺少点及伪点较为鲁棒，但计算复杂度较大。Sanjay Ranade and AzrielRosenfeld提出松弛法进行点匹配[2]，陈志刚等在其基础上通过构建三角形并利用其相似度来定义点特征的匹配度，提出了一种新的具有比例与旋转不变特性的点特征松弛匹配算法[22]。Shih-hsu Chang等人利用二维聚类进行匹配[23]，张立华等利用不可约矩阵和相对不变量理论提出了几种点模式匹配新算法[24]，它们可分别用来解决相似变换和仿射变换下具有相同点数的两个点模式的匹配问题。Li利用了几何不变量来进行点模式匹配[25]，Spirkovska和Reid 利用了高阶神经网络进行匹配[26]。
基于图像特征的匹配方法可以克服利用图像灰度信息进行匹配的缺点，由于图像的特征点比图像总的像素要少很多，这样就大大减少了匹配过程的计算量；而且特征点的提取过程可以减少噪声的影响，对灰度变化，图像形变以及遮挡等都有较好的适应能力。
1.3 研究内容
特征点提取过程中，需要构建在多种变换下具有良好不变性的特征点提取算法
以获得具有精确性高，区分度强的不变性图像特征，并综合特征局部结构信息，构造特征描述算子。由于时间、视角、环境的变化、多种传感器的使用等，使拍摄的图像不仅受到噪声的影响，而且存在严重的灰度失真和几何畸变。在这种条件下，匹配算法如何达到精度高、匹配正确率高、速度快、鲁棒性和抗干扰性强以及并行实现成为人们追求的目标。
本文在研究现有的一些特征检测算法及匹配方法基础上，以计算机视觉的不变理论为基础，本文主要研究内容如下所述。
1. 图像不变特征点提取算法研究
图像特征点提取是基于特征点匹配方法的首要步骤，在实际问题中，图像可能受到噪声、背景的干扰，也可能发生光照、尺度、旋转、仿射等变化，如何选择合理的图像特征点，使得这些特征点不仅具有良好的抗噪性能，而且在上述变化下保持不变，直接决定了基于特征点的匹配方法效果。由于后续匹配方法需要图像在旋转和尺度变换下仍满足一定比例的有效点，所以本文需要对旋转和尺度不变特征点的提取进行研究。
2. 图像特征点匹配方法研究
图像特征点匹配的目的是在两幅图像之间建立尽可能多的匹配点对。它是图像分析和处理的基本问题。图像特征点匹配方法目前主要分为两种，即为基于描述符的特征点匹配方法和基于特征点几何结构的匹配方法。基于描述符的匹配方法对有效点的要求低，适合图像视角变换、轻微变形情况，但是实现复杂，对图像纹理要就比较高；而基于几何结构的匹配方法实现简单、纹理要求低，但是抗图像形变、视角变化能力差，算法时间复杂度比较高。所以本文需要对图像特征点的匹配方法进行研究，探求更有效、性能更好的图像特征点匹配方法。
1.4 论文组织结构
本文将图像特征点的提取方法以及特征点匹配方法作为主要研究对象，针对图像存在旋转和尺度变化的情况，利用改进H/S算法提取图像中特征点，并在分析比较两种常用特征点匹配方法基础上，提出了一种改进的相似三角形特征点匹配算法。
本文的篇章结构安排如下：
第一章为绪论，介绍了图像特征点、图像匹配基本概念，相关领域研究现状，最后阐述了本文的主要研究工作和篇章结构。
第二章主要比较目前常用的两种特征点匹配方法，分别介绍Harris角点检测算法和基于描述符的SIFT算法，并分析两种方法的优缺点和适用场合，第三章主要在分析特征点提取算法的基础上，着重介绍特征点检测实验效果好的Harris算法，针对传统Harris算法存在的局限性，引入尺度空间理论和特征描述
思想，提出改进的H/S算法。
第四章在前面研究的基础上，提出一种改进的相似三角形特征点匹配方法，改进方法将传统被动的同向相似三角形检索方法变为在复数空间下选择基线后主动构造相似三角形，提高了算法的效率。并利用特征点组成基线向量后得到三角形组形成多个模板在实物图中进行匹配，提高了三角形匹配算法的实时性和稳定性。
最后一章对全文工作进行总结，并提出今后研究的问题与方向。
第二章图像特征点提取算法研究
图像特征点提取是图像处理和计算机视觉的基本技术，它也是特征点匹配方法的首要步骤。实际图像可能受到噪声、背景的干扰，也可能发生光照、尺度、旋转、仿射等变化，图像特征点的选择合理和特征点提取质量，直接决定了特征点匹配方法的效果。本章针对实际情况的复杂多样性，对两种特征点提取方法(Harris算法和SIFT算法)进行分析研究。
2.1 Harris特征点提取算法
角点作为目前图像匹配中常用的特征点，它是二维图像亮度变化剧烈或图像边缘曲线上曲率极大值的点，决定了目标的轮廓特征，因此被广泛应用于摄像机标定、虚拟场景重建、运动估计、图像配准等计算机视觉处理任务中。
角点检测方法分为基于边缘的提取方法和基于图像灰度的提取方法。前者往往需要对图像边缘进行编码，这在很大程度上依赖于图像的分割和边缘提取，而这两种操作本身就具有相当大的难度和计算量，况且一旦待检测目标局部发生变化(例如被部分遮挡)，则很可能导致图像分割和图像边缘提取操作的失败，所以这种方法的适用范围很小；而基于图像灰度的方法则避开了上述这些缺陷，它考虑的是像素点邻域的灰度变化，而不是整个目标的边缘轮廓。它通过计算曲率及梯度来达到检测角点的目的。由于它不需要进行边缘提取工作，所以在实际中得到了广泛的应用。目前在图像匹配中，常见的基于灰度的角点提取算法主要有Moravec算法，SUSAN 算法和Harris算法等。Schmid[27]对Moravec，SUSAN和Harris等基于图像灰度的角点检测方法从重复率和角点周围的局部区域所包含的信息量两个方面进行了对比。实验结果表明Moravec，SUSAN算法存在较多的误检测和漏检测现象，且对旋转前后的图像角点检测不一致，而Harris角点检测法具有最好的效果。因此本节主要分析Harris算法。
2.1.1 Harris特征点检测原理
Harris 角点检测算法是一种基于信号的点特征提取算子，它的思想是在图像中设计一个局部检测窗口，当该窗口沿各个方向作微小移动时，考察窗口的平均能量变化，当该能量变化值超过设定的阈值时，就将窗口的中心像素点提取为角点。
Harris角点检测公式为：
∑-
+
+
=
y
x
y x I
v
y
u
x
I
y
x
w
v
u
E
,
2
)] ,
(
)
,
(
)[
,
(
)
,
((2.1)
其中，),(y x w 为窗函数，2)],(),([y x I v y u x I -++为图像灰度的梯度值。),(y x w 可为矩形窗或高斯窗。对于每个小的位移量),(v u ，检测公式可双线性近似表示为：
(2.2)
其中 ∑??
??
??=y x Y Y x Y x x I I I I I I y x w M ,22),( (2.3) 设1λ，2λ是矩阵M 的两个特征值，则可表示局部自相关函数的曲率。实际运用中用来计算角点的响应函数可以写成：
)()d e t (2M k t r a c e M
R -= (2.4) 其中21)det(λλ=M ，21)(λλ+=M trace 当某个区域矩阵M 的主对角线之和很大时，则表明这是一条边；当矩阵M 的行列式很大时，则表明这是一条边或一个角点，k 一般取经验值0.04。
2.1.2 Harris 特征点检测步骤
应用Harris 方法提取图像中角点的过程可以分为以下几步：
1) 计算图像像素点在水平和垂直方向上的梯度，以及两者的乘积，得到M 公式
(2.3)中4个元素的值, 其中2x x x I I I =?，y y y I I I ?=2，x I 、y I 分别表示在x ,y 方向
上的一阶导数。
2) 对图像进行高斯滤波，得到新的M 。
离散二维零均值高斯函数
222exp 2x y Gauss σ??+=- ???
(2.5) 3) 计算原图像上对应的每个像素点的兴趣值，即R 值(角点量cim)。
22222*()
x y x y x y I I I I R I I -=+ (2.6)
4) 选取局部极值点。Harris 方法认为，特征点是局部范围内的极大兴趣值对应的像素点。
5) 设定阈值，选取一定量的角点。
2.1.3实验分析
实验实现Harris 角点检测算法，测试其在图像存在旋转、尺度变化、噪声等情况下的检测效果，并分析Harris 算法在设置不同阈值情况下提取角点。实验所提取的角点用十字划线来标识。
??
?????v u M v u v u E ],[),(
1. 旋转不变性
图2.1(a)为原图角点提取结果，图2.1(b)为经过逆时针旋转30度后的图像角点提取结果。从图中可以看出，Harris算法在图像旋转时检测得到角点的重复数很高，具有良好的抗旋转性能。
(a)原图像(b)逆时针旋转30度图像
图2.1 图像旋转角点提取结果图
2. 尺度变化不变性
图像 2.2(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. 设置不同阈值时角点不变性
由前文针对Harris算法提取角点步骤可知，设置阈值大小不同时得到的角点数目也随之改变，图2.4为不同阈值条件下提取角点结果图。从图中可以看出，将阈值设定较高时，检测得到的角点数量明显下降。
(a)阈值设置为5000 (b)阈值设置为10000
(c)阈值设为15000 (d)阈值设置为20000
图2.4 设置不同阈值时角点提取结果图
通过对Harris算法提取图像特征点的原理及实验结果分析，可以看出Harris算法在图像存在旋转情况下有很高的点重复数，是一种比较有效的点特征提取算法。因此在图像配准中通常采用这种算法来提取特征点。但是Harris特征点检测算法也存在着一定的局限性。当图像间发生尺度变换时，Harris角点就可能检测出不一致的角点。即当尺度变化时，可能检测出新的角点，或老的角点发生移位或消失。这样
特征点的重复数下降，不利于后续特征点匹配。同时由于Harris算法采用了偏导来计算角点函数，虽然经过高斯滤波，但对噪声仍比较敏感。
2.2 SIFT特征点提取算法
由上节对Harris特征点提取算法局限性的分析，本节对目前国内外研究广泛的局部不变特征点提取算法SIFT进行研究，该算法提取出的特征点对图像尺度和旋转不变性效果好，对光线变化和噪声变化也具有较好鲁棒性。
2.2.1 SIFT特征点提取算法原理及步骤
SIFT算法是Lowe[14]利用尺度空间性质提出的一种尺度不变关键点的检测方法，主要利用目标局部区域的信息来构造特征量，它以同时在尺度域和空间域取得极值的点作为关键点，并以关键点作为特征区域的中心，同时关键点所在的尺度还用以确定特征区域的大小，在每个特征区域内以梯度方向的直方图为基础得到局部不变特征向量。
SIFT特征点提取方法首先对图像进行预处理，通过采用高斯差分金字塔分层结构提取出图像中的极值点作为侯选，并对这些侯选特征点进一步筛选掉其中低对比度和处于边缘的点，最终提取出稳定的特征点。
SIFT特征点提取算法主要执行流程如图2.5所示。
图2.5 SIFT算法流程
1. 尺度空间极值求取
SIFT方法第一步就是找出尺度空间的极值，首先构建图像的尺度空间函数。
1) 高斯差分图像DOG生成
高斯卷积核是实现尺度变换的唯一线性核，一副输入图像(,,)I x y σ:
(,,)(,,)(,)L x y G x y I x y σσ=* （2.7） 其中*是在x 和y 之间的卷积运算符，
222()/221(,,)2x y G x y e σσπσ
-+= (2.8) ()y ，x 是空间坐标，σ是尺度坐标。
为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间(DOG scale-space)。利用不同尺度的高斯差分核与图像卷积生成。
),,(),,(),()),,(),,((),,(σσσσσy x L k y x L y x I y x G k y x G y x D -=*-= (2.9)
一种有效的构建高斯差分函数),,(σy x D 的方法可以通过图2.6介绍。首先对图像进行预处理以消除图像模糊，对提取稳定的特征点有好处。采用高斯函数先对图像进行卷积运算，以达到预处理的目的。接着对图像使用不同的采样距离以形成一个金字塔图像分层结构，在第一次采样时每0.5个像素距离进行采样，这就意味着将原来图像放大一倍，第一次采样的图像作为第一组的图像，然后以成倍的采样距离即1、2、4个像素再分别对图像进行采样从而产生第二、三、四组的图像。这样就形成一个金字塔形状的图像分层结构。
不同采样形成金字塔分层结构，然后用高斯内核函数对其进行滤波形成高斯金字塔图像分层结构，对各层图形进行高斯滤波时分别采用不同的高斯滤波因子。在图2.6左侧高斯金字塔各层中标识了高斯滤波函数的滤波因子。原始图像通过高斯函数进行卷积生成一组图像，这些图像在尺度空间中借助常量k 被分离，如图2.6左侧所示。再将尺度空间中的每组分隔成一整数s 的间隔，令k =s /12，所以，每组中的图像数必须为s+3个，极值检测才能覆盖一组中所有图像，论文中s 为2。图2.6中的右列显示了将每组中相邻图像相减生成高斯差分图像的结果。利用高斯差分金字塔分层结构提取出图像中的极值点作为候选特征点，并对这些候选特征点进一步筛选掉其中低对比度和处于边缘的特征点，最终提取出稳定的特征点。
在文中取σ为2/2，在图2.6中第二组中的第一层图像的滤波因子如图所示是取第一组中第三层中的图像的滤波因子，第二层滤波因子增加k 倍，依次增加滤波因子直到最高层第五层。第三组和第四组中图像层的滤波因子也和上面的方法相同，依次增加滤波因子。
高斯 双高斯差（DoG ）
图2.6 候选特征点生成图
2) 空间极值点检测
为了寻找尺度空间的极值点，每一个采样点要和它所有的相邻点比较，看其是否比它的图像域和尺度域的相邻点大或者小。如图2.7所示，中间的检测点和它同尺度的8个相邻点和上下相邻尺度对应的9×2个点共26个点比较，以确保在尺度空间和二维图像空间都检测到极值点。
图2.7 DoG 尺度空间局部极值检测
2. 特征点位置确定
一旦通过上面步骤得到了侯选特征点，下一步就是确定稳定特征点的位置、尺度、曲率等信息。通过下面操作可以将侯选特征点中低对比度(对噪声敏感)或位于边缘的侯选特征点过滤掉。
1) 精确确定极值点位置
通过拟和三维二次函数以精确确定关键点的位置和尺度(达到亚像素精度)，同时去除低对比度的关键点和不稳定的边缘响应点(因为DoG 算子会产生较强的边缘响应)，以增强匹配稳定性、提高抗噪声能力。
2) 边缘响应的去除 一个定义不好的高斯差分算子的极值在横跨边缘的地方有较大的主曲率，而在
大尺度1x1
中尺度2x2
小尺度4x4
垂直边缘的方向有较小的主曲率。主曲率通过一个2?2的Hessian 矩阵H 求出:
xx xy xy
yy D D H D D ??=???? (2.10)
导数由采样点相邻差估计得到。 D 的主曲率和H 的特征值成正比，令α为最大特征值，β为最小的特征。
()xx yy Tr H D D αβ=+=+ (2.11)
2()()xx yy xy Det H D D D αβ=-= (2.12)
令αγβ=，则：
2
2
222()()(1)()Tr H αβγββγαβγβγ+++=== (2.13)
γγ/)1(2+的值在两个特征值相等的时候最小，随着γ的增大而增大，因此，为了检测主曲率是否在某域值γ下，只需检测
2
()(1)()Tr H Det H γγ
+< (2.14) 在Lowe 的文章[15]中，取γ＝10。
3. 特征点方向确定
基于图像属性为每个特征点赋一个方向，在后面特征点描述符中将会用到特征点的方向并对特征点的特性进行描述。
利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备旋转不变性。 在实际计算时，在以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度方向。梯度直方图的范围是0～360度，其中每10度一个柱，总共36个柱。直方图的峰值则代表了该关键点处邻域梯度的主方向，即作为该关键点的方向。在梯度方向直方图中，当存在另一个相当于主峰值80%能量的峰值时，则将这个方向认为是该关键点的辅方向。一个关键点可能会被指定具有多个方向(一个主方向，一个以上辅方向)，这可以增强匹配的鲁棒性。
4. 特征点描述符的确定
通过以上步骤得到了每个特征点的位置、尺度、方向,下一步将为每个特征点建立一个描述符，使其不随各种变化而变化，比如光线变化、视角变化等。并且特征点描述符要尽量与众不同，以便于特征点间的匹配。将坐标轴旋转为关键点的方向，
图像匹配的主要方法分析 在我国的图像处理中，有很多的关键技术正在不断的发展和创新之中。这些相关技术的发展在很大程度上推动了我国图像处理事业的发展。作为图像处理过程中的关键技术，图像匹配技术正在受到越来越多的关注。文章针对图像匹配的主要方法进行详细的论述，希望通过文章的阐述和分析能够为我国的图像匹配技术的发展和创新贡献微薄力量，同时也为我国图像处理技术的发展贡献力量。 标签：图像处理；图像匹配；特征匹配；方法 在我国的图像处理技术中，图像的匹配技术不仅仅是其中的重要组成部分，同时还是很多图像技术的发展创新的技术基础。例如图像技术中的立体视觉技术；图像技术中的运动分析技术以及图像技术中的数据融合技术等。通过上述内容可以看出，在我国的图像技术中，图像匹配技术具有非常广泛的应用。随着我国的相关技术不断的创新和发展，对于图像匹配技术的要求也是越来越高。这样就要求我国的图像匹配技术有更深层次的研究和发展。我国现阶段的研究主要是针对图像匹配过程中的匹配算法进行研究，希望借助研究能够更加有效的提升在实际的工作应用中的图像质量，同时也能够在很大程度上提升图像处理的图像分别率。文章的主要陈述点是通过图像匹配技术的具体方法进行优点和缺点的分析，通过分析优点和缺点来论述我国图像处理技术中的图像匹配技术的发展方向以及改进措施。近些年出现了很多的图像匹配方法，针对现阶段的新方法以及新的研究思路我们在实际的应用过程中要有一个非常清醒的选择。文章针对这一问题主要有三个内容的阐述。第一个是图像匹配技术的算法融合；第二个是图像匹配技术中的局部特征算法；最后一个是图像匹配技术中的模型匹配具体算法。 1 现阶段在世界范围内较为经典的图像匹配技术的算法 关于现阶段在世界范围内的较为经典的图像匹配技术的算法的阐述，文章主要从两个方面进行分析。第一个方面是ABS图像匹配算法。第二个方面是归一化相互关图像匹配算法。下面进行详细的论述和分析。 （1）算法一：ABS图像匹配算法。ABS图像匹配算法最主要的原理就是要使用模板的图像以及相应的匹配图像的搜索用窗口之间的转换差别来显示两者之间的关联性。图像匹配的大小在数值上等同于模板图像的窗口滑动顺序。窗口的每一次滑动都会引起模板图像的匹配计算。现阶段ABS的算法主要有三个，如下： 在选择上述三种计算方法的过程中要根据实际情况社情相应的阀值，否则会出现很高的失误率。上述的三种算法使用范围较狭窄。只使用与等待匹配的图像在模板影像的计算。 （2）算法二：归一化相互关图像匹配算法。归一化相互关的图像匹配算法在现阶段是较为经典的算法。通常专业的称法为NC算法。此计算方法主要是采
角点提取与匹配算法实验报告 1 说明 本文实验的目标是对于两幅相似的图像，通过角点检测算法，进而找出这两幅图像的共同点，从而可以把这两幅图像合并成一幅图像。 下面描述该实验的基本步骤: 1.本文所采用的角点检测算法是Harris 角点检测算法，该算法的基本原理是取以目标像素点为中心的一个小窗口，计算窗口沿任何方向移动后的灰度变化，并用解析形式表达。设以像素点(x,y)为中心的小窗口在X 方向上移动u ，y 方向上移动v ，Harris 给出了灰度变化度量的解析表达式： 2 ,,|,|,,()(x y x y x u y v x y x y I I E w I I w u v o X Y ??= -=++??∑∑ (1) 其中，,x y E 为窗口内的灰度变化度量；,x y w 为窗口函数，一般定义为2 2 2 ()/,x y x y w e σ +=； I 为图像灰度函数，略去无穷小项有： 222222 ,,[()()2]2x y x y x y x y E w u I v I uvI I Au Cuv Bv = ++=++∑ （2） 将,x y E 化为二次型有： ,[]x y u E u v M v ?? =???? (3) M 为实对称矩阵： 2 ,2 x y x x y x y y I I I M w I I I ???= ???????∑ (4) 通过对角化处理得到： 11 ,200x y E R R λλ-??= ??? (5) 其中，R 为旋转因子，对角化处理后并不改变以u,v 为坐标参数的空间曲面的形状，其特征值反应了两个主轴方向的图像表面曲率。当两个特征值均较小时，表明目标点附近区域为“平坦区域”；特征值一大一小时，表明特征点位于“边缘”上；只有当两个特征值均比较大时，沿任何方向的移动均将导致灰度的剧烈变化。Harris 的角点响应函数(CRF)表达式由此而得到： 2 (,)det()(())C RF x y M k trace M =- (6)
SIFT 特征提取算法总结 主要步骤 1)、尺度空间的生成； 2)、检测尺度空间极值点； 3)、精确定位极值点； 4)、为每个关键点指定方向参数； 5)、关键点描述子的生成。 L(x,y,σ), σ= 1.6 a good tradeoff
D(x,y,σ), σ= 1.6 a good tradeoff
关于尺度空间的理解说明：图中的2是必须的，尺度空间是连续的。在 Lowe 的论文中， 将第0层的初始尺度定为1.6，图片的初始尺度定为0.5. 在检测极值点前对原始图像的高斯平滑以致图像丢失高频信息，所以Lowe 建议在建立尺度空间前首先对原始图像长宽扩展一倍，以保留原始图像信息，增加特征点数量。尺度越大图像越模糊。 next octave 是由first octave 降采样得到（如2） ， 尺度空间的所有取值，s为每组层数，一般为3~5 在DOG尺度空间下的极值点 同一组中的相邻尺度（由于k的取值关系，肯定是上下层）之间进行寻找
在极值比较的过程中，每一组图像的首末两层是无法进行极值比较的，为了满足尺度 变化的连续性，我们在每一组图像的顶层继续用高斯模糊生成了 3 幅图像， 高斯金字塔有每组S+3层图像。DOG金字塔每组有S+2层图像.
If ratio > (r+1)2/(r), throw it out (SIFT uses r=10) 表示DOG金字塔中某一尺度的图像x方向求导两次 通过拟和三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度）？
直方图中的峰值就是主方向，其他的达到最大值80%的方向可作为辅助方向 Identify peak and assign orientation and sum of magnitude to key point The user may choose a threshold to exclude key points based on their assigned sum of magnitudes. 利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备 旋转不变性。以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度 方向。梯度直方图的范围是0～360度，其中每10度一个柱，总共36个柱。随着距中心点越远的领域其对直方图的贡献也响应减小.Lowe论文中还提到要使用高斯函 数对直方图进行平滑，减少突变的影响。
关于图像特征提取 特征提取是计算机视觉和图像处理中的一个概念。它指的是使用计算机提取图像信息，决定每个图像的点是否属于一个图像特征。特征提取的结果是把图像上的点分为不同的子集，这些子集往往属于孤立的点、连续的曲线或者连续的区域。 特征的定义 至今为止特征没有万能和精确的定义。特征的精确定义往往由问题或者应用类型决定。特征是一个数字图像中“有趣”的部分，它是许多计算机图像分析算法的起点。因此一个算法是否成功往往由它使用和定义的特征决定。因此特征提取最重要的一个特性是“可重复性”：同一场景的不同图像所提取的特征应该是相同的。 特征提取是图象处理中的一个初级运算，也就是说它是对一个图像进行的第一个运算处理。它检查每个像素来确定该像素是否代表一个特征。假如它是一个更大的算法的一部分，那么这个算法一般只检查图像的特征区域。作为特征提取的一个前提运算，输入图像一般通过高斯模糊核在尺度空间中被平滑。此后通过局部导数运算来计算图像的一个或多个特征。 有时，假如特征提取需要许多的计算时间，而可以使用的时间有限制，一个高层次算法可以用来控制特征提取阶层，这样仅图像的部分被用来寻找特征。 由于许多计算机图像算法使用特征提取作为其初级计算步骤，因此有大量特征提取算法被发展，其提取的特征各种各样，它们的计算复杂性和可重复性也非常不同。 边缘 边缘是组成两个图像区域之间边界（或边缘）的像素。一般一个边缘的形状可以是任意的，还可能包括交叉点。在实践中边缘一般被定义为图像中拥有大的梯度的点组成的子集。一些常用的算法还会把梯度高的点联系起来来构成一个更完善的边缘的描写。这些算法也可能对边缘提出一些限制。 局部地看边缘是一维结构。 角 角是图像中点似的特征，在局部它有两维结构。早期的算法首先进行边缘检测，然后分析边缘的走向来寻找边缘突然转向（角）。后来发展的算法不再需要边缘检测这个步骤，而是可以直接在图像梯度中寻找高度曲率。后来发现这样有时可以在图像中本来没有角的地方发现具有同角一样的特征的区域。 区域 与角不同的是区域描写一个图像中的一个区域性的结构，但是区域也可能仅由一个像素组成，因此许多区域检测也可以用来监测角。一个区域监测器检测图像中一个对于角监测器来说太平滑的区域。区域检测可以被想象为把一张图像缩小，然后在缩小的图像上进行角检测。 脊 长条形的物体被称为脊。在实践中脊可以被看作是代表对称轴的一维曲线，此外局部针对于每个脊像素有一个脊宽度。从灰梯度图像中提取脊要比提取边缘、角和区域困难。在空中摄影中往往使用脊检测来分辨道路，在医学图像中它被用来分辨血管。 特征抽取 特征被检测后它可以从图像中被抽取出来。这个过程可能需要许多图像处理的计算机。其结果被称为特征描述或者特征向量。 常用的图像特征有颜色特征、纹理特征、形状特征、空间关系特征。 一颜色特征 （一）特点：颜色特征是一种全局特征，描述了图像或图像区域所对应的景物的表面性质。一般颜色特征是基于像素点的特征，此时所有属于图像或图像区域的像素都有各自的贡献。由于颜色对图像或图像区域的方向、大小等变化不敏感，所以颜色特征不能很好地捕捉图像中对象的局部特征。另外，仅使用颜色特
诚信声明 本人声明： 我所呈交的本科毕业设计论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人完全意识到本声明的法律结果由本人承担。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期：2010 年05 月20日
毕业设计（论文）任务书 设计（论文）题目： 学院：专业：班级： 学生指导教师（含职称）：专业负责人： 1．设计（论文）的主要任务及目标 (1) 了解图象匹配技术的发展和应用情况，尤其是基于特征的图象匹配技术的发展和应用。 (2) 学习并掌握图像匹配方法，按要求完成算法 2．设计（论文）的基本要求和内容 （1）查阅相关中、英文文献，完成5000汉字的与设计内容有关的英文资料的翻译。（2）查阅15篇以上参考文献，其中至少5篇为外文文献，对目前国内外图象匹配技术的发展和应用进行全面综述。 （3）学习图象匹配算法，尤其是基于特征的图象匹配算法。 （4）实现并分析至少两种基于特征的图象匹配算法，并分析算法性能。 3．主要参考文献 [1]谭磊, 张桦, 薛彦斌．一种基于特征点的图像匹配算法[J]．天津理工大学报，2006， 22(6)，66-69． [2]甘进，王晓丹，权文．基于特征点的快速匹配算法[J]．电光与控制，2009，16(2)， 65-66． [3]王军，张明柱．图像匹配算法的研究进展[J]．大气与环境光学学报，2007，2(1)， 12-15．
图像匹配与拼接 分匹配和拼接两部分 一、匹配 当然匹配的方法，有sift，surf什么的，这里主要就介绍一下我自己的方法啦！ 特征点提取是必须的，不然搜索范围太大哇！并且可能不可靠，所以特征点提取是必须的。什么点适合做特征点呢？这方面的论文很多啦，主要还是看你用什么方法匹配了，如果是用互相关作为相似性准则的话，那自相关系数随各个方向变化大的点就适合作特征点了，当然还要考虑稳定性，即特征点应该不太受光照、噪声、缩放、旋转等的影响，这样的才是好的特征点。当然，如果确定了应用坏境，不一定要满足不受上四个因素影响的，比如平行的双目匹配、全景图的匹配等，具体问题具体分析吧！角点特征是个人比较喜欢的特征。这里我自己定义了一种局部特征，效果还行，匹配采用互相关为准则的匹配，大概效果如下： 目测这几个匹配点还是正确的哇！在一些应用中，可能需要的匹配点数相当多，这就需要较密集的匹配了。密集的匹配可以根据初始的匹配结果估计搜索范围，这可以加速搜索，同时也要提取更多的特征点呀！话不多说了，下面是密集的匹配：
虽然这样的密度对于三维重构来说还不够，但对于一般的图像拼接来说足够了。匹配完了，下面就要将第二步了。 二、矫正 匹配好两幅图像了，接下来干啥呢？把它们对准呗。可惜了，两幅图像之间不但存在平移，还存在旋转缩放什么的，更复杂的，可能还存在所谓的3D变换，那就复杂啦！不管怎么样，所谓的对准，也就是矫正，总是基于一定的模型的，即基于相机拍摄两幅图像的相对姿态。对于全景图拼接（个人觉得是最简单的且较实用的拼接），需要根据相机焦距或者视场角投影到柱面上，然后两幅图像间的位置就只有一维的平移关系了。但是这对拍摄的相机也是有要求的，就是要保证拍摄两幅图像时，物防焦点是重合的，这样才能根据稀疏的几个点确定所有重叠区域内点的相对位置呀！但实际中很难做到物方焦点重合，比如数码相机或者所谓的智能手机的全景图拍摄，一般人都是拿着相机或者手机绕人旋转，而非绕物方焦点旋转拍摄的，这样拼接起来是绝对有误差的呀！特别是拼接近景，误差就更大了，远景还好。怎么克服这个缺点呢？简单的改进方法就是绕着摄像头旋转吧，虽然这也不是严格绕物方焦距旋转，但起码误差小得多啦，拼接的效果当然也就好得多了，可以试一试哦！ 不扯了，第二种模型就是认为两幅图像间存在的变换关系是有2D旋转、缩放、平移的，可以通过一个旋转、缩放、平移矩阵来矫正，这个也不难，但是应用范围却相当有限，不详说了。 第三种模型就是不用模型，或者说认为两幅图像间的对应点存在的是一种线性变换关系，这样只要解一个线性方程组就可以了，似乎也挺简单的。但可惜的是，不是任给的两幅图像间都只存在线性变换呀！它可能是一个3D的线性变换，那就麻烦了，这个必须需要密匹配呀！不然就一定是有误差的，即不能通过稀疏的匹配点来矫正两幅图像的所有对应点的。 还有更多的模型，比如各方位的全景图，需要投影到球面上的哇！不过这个模型也不难。最难的当然是拍摄两幅图像时，相机不同，相机姿态也不同了，这个是很有挑战的，我也很惧怕这个。下面展示三种矫正结果： 1、2D线性模型： 2D矫正，认为匹配点之间存在线性变换，X=ax+by+c，Y=dx+ey+e这样的模型，业内称之放射变换，其中x，y是第一幅点的坐标，X,Y是对应的第二幅图像中的点坐标，使用最小二乘法计算a、b、c、d、e、f，第二幅图相对于第一幅图矫正的结果就是这样的了
图像常见特征提取方法简介 常用的图像特征有颜色特征、纹理特征、形状特征、空间关系特征。 一、颜色特征 （一）特点：颜色特征是一种全局特征,描述了图像或图像区域所对应的景物的表面性质。一般颜色特征是基于像素点的特征，此时所有属于图像或图像区域的像素都有各自的贡献。由于颜色对图像或图像区域的方向、大小等变化不敏感，所以颜色特征不能很好地捕捉图像中对象的局部特征。另外，仅使用颜色特征查询时，如果数据库很大，常会将许多不需要的图像也检索出来。颜色直方图是最常用的表达颜色特征的方法，其优点是不受图像旋转和平移变化的影响，进一步借助归一化还可不受图像尺度变化的影响，基缺点是没有表达出颜色空间分布的信息。 （二）常用的特征提取与匹配方法 （1）颜色直方图 其优点在于：它能简单描述一幅图像中颜色的全局分布，即不同色彩在整幅图像中所占的比例，特别适用于描述那些难以自动分割的图像和不需要考虑物体空间位置的图像。其缺点在于：它无法描述图像中颜色的局部分布及每种色彩所处的空间位置，即无法描述图像中的某一具体的对象或物体。 最常用的颜色空间：RGB颜色空间、HSV颜色空间。 颜色直方图特征匹配方法：直方图相交法、距离法、中心距法、参考颜色表法、累加颜色直方图法。 （2）颜色集 颜色直方图法是一种全局颜色特征提取与匹配方法，无法区分局部颜色信息。颜色集是对颜色直方图的一种近似首先将图像从RGB颜色空间转化成视觉均衡的颜色空间（如HSV 空间），并将颜色空间量化成若干个柄。然后，用色彩自动分割技术将图像分为若干区域，每个区域用量化颜色空间的某个颜色分量来索引，从而将图像表达为一个二进制的颜色索引集。在图像匹配中，比较不同图像颜色集之间的距离和色彩区域的空间关系 （3）颜色矩 这种方法的数学基础在于：图像中任何的颜色分布均可以用它的矩来表示。此外，由于颜色分布信息主要集中在低阶矩中，因此，仅采用颜色的一阶矩（mean）、二阶矩（variance）和三阶矩（skewness）就足以表达图像的颜色分布。 （4）颜色聚合向量 其核心思想是：将属于直方图每一个柄的像素分成两部分，如果该柄内的某些像素所占据的连续区域的面积大于给定的阈值，则该区域内的像素作为聚合像素，否则作为非聚合像素。（5）颜色相关图 二纹理特征 （一）特点：纹理特征也是一种全局特征，它也描述了图像或图像区域所对应景物的表面性质。但由于纹理只是一种物体表面的特性，并不能完全反映出物体的本质属性，所以仅仅利用纹理特征是无法获得高层次图像内容的。与颜色特征不同，纹理特征不是基于像素点的特征，它需要在包含多个像素点的区域中进行统计计算。在模式匹配中，这种区域性的特征具有较大的优越性，不会由于局部的偏差而无法匹配成功。作为一种统计特征，纹理特征常具有旋转不变性，并且对于噪声有较强的抵抗能力。但是，纹理特征也有其缺点，一个很明显的缺点是当图像的分辨率变化的时候，所计算出来的纹理可能会有较大偏差。另外，由于有可能受到光照、反射情况的影响，从2-D图像中反映出来的纹理不一定是3-D物体表面真实
本文基于相关性分析来实现图像匹配 第一步：读取图像。 分别读取以下两幅相似的图片，显示效果如下： 第二步：选择一副图像的子区域。用户可以通过鼠标选择需要截取的图像部分，用于匹配。随机选取图片的一块区域，如下图：
第三步：使用相关性分析两幅图像 采用协方差的方式计算相关系数，分析图片的相似性。 1．协方差与相关系数的概念 对于二维随机变量(,)X Y ，除了关心它的各个分量的数学期望和方差外，还需要知道这两个分量之间的相互关系，这种关系无法从各个分量的期望和方差来说明，这就需要引进描述这两个分量之间相互关系的数字特征——协方差及相关系数。 若X Y 与相互独立,则()( )0 Y E X EX Y EY σ--???? =≠;若()()0E X EX Y EY --≠????,则表 示X 与Y 不独立,X 与Y 之间存在着一定的关系 设 (,)X Y 是二维随机变量， 则称()()E X EX Y EY --????为X 与Y 的协方差（Covariance ），记为 ()cov ,X Y 或XY σ，即 ()()()cov ,XY X Y E X EX Y EY σ==--???? 若 0X σ≠ 且0Y σ=≠，则称 XY XY X Y σρσσ== 为X 与Y 的相关系数（Correlation Coefficient ）。()c o v ,X Y 是 有量纲的量，而XY ρ则是无量纲的量．协方差常用下列公式计算
()() =-? cov,X Y E XY EX EY 2．用全搜索和协方差计算截取图片与另外一幅图片的各点的相似度。c=normxcorr2(sub_I1(:,:,1),I2(:,:,1)); 第四步：找到整幅图像的偏移。 [max_c,imax]=max(abs(c(:))); [ypeak,xpeak]=ind2sub(size(c),imax(1)); [m,n]=size(sub_I1); xbegin=xpeak-n+1; ybegin=ypeak-m+1; xend=xpeak; yend=ypeak; 从原图像提取匹配到的图像 extracted_I1=I2(ybegin:yend,xbegin:xend,:); 第五步：显示匹配结果。 相关性匹配图： 找出峰值即最相似区域的中心
研究配准进两年的时间，有幸看到一个技术文档，做了一下的总结，如有不妥之处敬请大家谅解，多提出意见 废话不多说，书归正传！ 这里主要讲解的是多模态或者说是多序列MRI图像配准。采用的图片是人体膝盖图。配准暂且分为五部 Step1. 下载图片 Step2. 初始配准（粗配准） Step3. 提高配准精度 Step4. 利用初始条件提高配准精度配准 Step5. 结果满意不满意，你说了算 下面一一详细说明以上几个步骤！ 一，下载图片 这里采用的图片是matlab子带的两张MR膝盖图， “knee1.dcm”作为参考图像，"knee2.dcm"为浮动图像！ Plain Text code ? 1 2 fixed = dicomread('knee1.dcm'); % 读参考图像fixed moving = dicomread('knee2.dcm'); % 读浮动图像moving 可能接下来大家关注的问题就是这两幅图像到底有什么区别，这种区别又有多大的可视化程度，下面就为推荐两个比较好用的函数用于观测两幅图像的区别。Plain Text code ? 1 2 figure, imshowpair(moving, fixed, 'method'); title('Unregistered'); imshowpair函数就是指以成双成对的形式显示图片，其中一个重要的参数就是‘method’，他又4个选择 （1）‘falsecolor’字面意思理解就是伪彩色的意思了，其实就是把两幅图像的差异用色彩来表示，这个是默认的参数。 （2）‘blend’这是一种混合透明处理类型，技术文档的翻译是 alpha blending，大家自己理解吧。 （3）‘diff’这是用灰度信息来表示亮度图像之间的差异，这是对应 ‘falsecolor’的一种方式。 （4）参数‘monotage’可以理解成‘蒙太奇’，这是一种视频剪辑的艺术手法，其实在这里我们理解成拼接的方法就可以了。 为什么在这里罗里吧嗦的说这么多的显示呢，大家知道"人靠衣装，美靠...."(就不多说了吧)，总之就是一个好的视觉效果能给人以耳目一新的效果。
SIFT 特征点匹配算法 基于SIFT 方法的图像特征匹配可分为特征提取和特征匹配两个部分，可细化分为五个部分： ① 尺度空间极值检测（Scale-space extrema detection ）； ② 精确关键点定位（Keypoint localization ） ③ 关键点主方向分配（Orientation assignment ） ④ 关键点描述子生成（Keypoint descriptor generation ） ⑤ 比较描述子间欧氏距离进行匹配（Comparing the Euclidean distance of the descriptors for matching ） 1.1 尺度空间极值检测 特征关键点的性质之一就是对于尺度的变化保持不变性。因此我们所要寻找的特征点必须具备的性质之一，就是在不同尺度下都能被检测出来。要达到这个目的，我们可以在尺度空间内寻找某种稳定不变的特性。 Koenderink 和Lindeberg 已经证明，变换到尺度空间唯一的核函数是高斯函数。因此一个图像的尺度空间定义为：(,,)L x y σ，是由可变尺度的高斯函数(,,)G x y σ与输入图像(,)I x y 卷积得到，即： ),(),,(),,(y x I y x G y x L *=σσ （1.1） 其中：2222/)(221 ),,(σπσσy x e y x G +-= 在实际应用中，为了能相对高效地计算出关键点的位置，建议使用的是差分高斯函数（difference of Gaussian ）(,,)D x y σ。其定义如下： ) ,,(),,() ,()),,(),,((),,(σσσσσy x L k y x L y x I y x G k y x G y x D -=*-= （1.2） 如上式，D 即是两个相邻的尺度的差（两个相邻的尺度在尺度上相差一个相乘系数k ）。
图像特征提取方法 摘要 特征提取是计算机视觉和图像处理中的一个概念。它指的是使用计算机提取图像信息，决定每个图像的点是否属于一个图像特征。特征提取的结果是把图像上的点分为不同的子集，这些子集往往属于孤立的点、连续的曲线或者连续的区域。 至今为止特征没有万能和精确的图像特征定义。特征的精确定义往往由问题或者应用类型决定。特征是一个数字图像中“有趣”的部分，它是许多计算机图像分析算法的起点。因此一个算法是否成功往往由它使用和定义的特征决定。因此特征提取最重要的一个特性是“可重复性”：同一场景的不同图像所提取的特征应该是相同的。 特征提取是图象处理中的一个初级运算，也就是说它是对一个图像进行的第一个运算处理。它检查每个像素来确定该像素是否代表一个特征。假如它是一个更大的算法的一部分，那么这个算法一般只检查图像的特征区域。作为特征提取的一个前提运算，输入图像一般通过高斯模糊核在尺度空间中被平滑。此后通过局部导数运算来计算图像的一个或多个特征。 常用的图像特征有颜色特征、纹理特征、形状特征、空间关系特征。当光差图像时，常 常看到的是连续的纹理与灰度级相似的区域，他们相结合形成物体。但如果物体的尺寸很小 或者对比度不高，通常要采用较高的分辨率观察：如果物体的尺寸很大或对比度很强，只需 要降低分辨率。如果物体尺寸有大有小，或对比有强有弱的情况下同事存在，这时提取图像 的特征对进行图像研究有优势。 常用的特征提取方法有：Fourier变换法、窗口Fourier变换（Gabor)、小波变换法、最 小二乘法、边界方向直方图法、基于Tamura纹理特征的纹理特征提取等。
设计内容 课程设计的内容与要求（包括原始数据、技术参数、条件、设计要求等）：一、课程设计的内容 本设计采用边界方向直方图法、基于PCA的图像数据特征提取、基于Tamura纹理特征的纹理特征提取、颜色直方图提取颜色特征等等四种方法设计。 （1）边界方向直方图法 由于单一特征不足以准确地描述图像特征,提出了一种结合颜色特征和边界方向特征的图像检索方法.针对传统颜色直方图中图像对所有像素具有相同重要性的问题进行了改进,提出了像素加权的改进颜色直方图方法;然后采用非分割图像的边界方向直方图方法提取图像的形状特征,该方法相对分割方法具有简单、有效等特点,并对图像的缩放、旋转以及视角具有不变性.为进一步提高图像检索的质量引入相关反馈机制,动态调整两幅图像相似度中颜色特征和方向特征的权值系数,并给出了相应的权值调整算法.实验结果表明,上述方法明显地优于其它方法.小波理论和几个其他课题相关。所有小波变换可以视为时域频域的形式，所以和调和分析相关。所有实际有用的离散小波变换使用包含有限脉冲响应滤波器的滤波器段(filterbank)。构成CWT的小波受海森堡的测不准原理制约，或者说，离散小波基可以在测不准原理的其他形式的上下文中考虑。 通过边缘检测，把图像分为边缘区域和非边缘区域，然后在边缘区域内进行边缘定位．根据局部区域内边缘的直线特性，求得小邻域内直线段的高精度位置；再根据边缘区域内边缘的全局直线特性，用线段的中点来拟合整个直线边缘，得到亚像素精度的图像边缘．在拟合的过程中，根据直线段转角的变化剔除了噪声点，提高了定位精度．并且，根据角度和距离区分出不同直线和它们的交点，给出了图像精确的矢量化结果 图像的边界是指其周围像素灰度有阶跃变化或屋顶变化的那些像素的集合，边界广泛的存在于物体和背 景之间、物体和物体之间，它是图像分割所依赖的重要特征．边界方向直方图具有尺度不变性，能够比较好的 描述图像的大体形状．边界直方图一般是通过边界算子提取边界，得到边界信息后，需要表征这些图像的边 界，对于每一个边界点，根据图像中该点的梯度方向计算出该边界点处法向量的方向角，将空间量化为M级， 计算每个边界点处法向量的方向角落在M级中的频率，这样便得到了边界方向直方图． 图像中像素的梯度向量可以表示为[ ( ，)，)，( ，)，)] ，其中Gx( ，)，)，G ( ，)，)可以用下面的
二分图的最优匹配（KM算法） KM算法用来解决最大权匹配问题：在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。 基本原理 该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成立。 KM算法的正确性基于以下定理： 若由二分图中所有满足A[ i ]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中，X点集中的所有点都有对应的匹配或者是 Y点集中所有的点都有对应的匹配，则称该匹配为完备匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。 初始时为了使A[ i ]+B[j]>=w[i,j]恒成立，令A[ i ]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现： 1）两端都在交错树中的边(i,j)，A[ i ]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。 2）两端都不在交错树中的边(i,j)，A[ i ]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。 3）X端不在交错树中，Y端在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。 4）X端在交错树中，Y端不在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。（针对之后例子中x1->y4这条边） 现在的问题就是求d值了。为了使A[ i ]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于： Min{A[i]+B[j]-w[i,j] | Xi在交错树中，Yi不在交错树中}。 改进 以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A[ i ]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y 顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的不在交错树中的Y顶点的slack值都减去d（因为：d的定义为 min{ (x,y)| Lx(x)+ Ly(y)- W(x,y), x∈ S, y? T }
图像特征特点及常用的特征提取与匹配方法 常用的图像特征有颜色特征、纹理特征、形状特征、空间关系特征。 一颜色特征 （一）特点：颜色特征是一种全局特征,描述了图像或图像区域所对应的景物的表面性质。一般颜色特征是基于像素点的特征，此时所有属于图像或图像区域的像素都有各自的贡献。由于颜色对图像或图像区域的方向、大小等变化不敏感，所以颜色特征不能很好地捕捉图像中对象的局部特征。另外，仅使用颜色特征查询时，如果数据库很大，常会将许多不需要的图像也检索出来。颜色直方图是最常用的表达颜色特征的方法，其优点是不受图像旋转和平移变化的影响，进一步借助归一化还可不受图像尺度变化的影响，基缺点是没有表达出颜色空间分布的信息。 （二）常用的特征提取与匹配方法 （1） 颜色直方图 其优点在于：它能简单描述一幅图像中颜色的全局分布，即不同色彩在整幅图像中所占的比例，特别适用于描述那些难以自动分割的图像和不需要考虑物体空间位置的图像。其缺点在于：它无法描述图像中颜色的局部分布及每种色彩所处的空间位置，即无法描述图像中的某一具体的对象或物体。 最常用的颜色空间：RGB颜色空间、HSV颜色空间。 颜色直方图特征匹配方法：直方图相交法、距离法、中心距法、参考颜色表法、累加颜色直方图法。 （2） 颜色集 颜色直方图法是一种全局颜色特征提取与匹配方法，无法区分局部颜色信息。颜色集是对颜色直方图的一种近似首先将图像从RGB颜色空间转化成视觉均衡 的颜色空间（如HSV 空间），并将颜色空间量化成若干个柄。然后，用色彩自动分割技术将图像分为若干区域，每个区域用量化颜色空间的某个颜色分量来索引，从而将图像表达为一个二进制的颜色索引集。在图像匹配中，比较不同图像颜色集之间的距离和色彩区域的空间关系 （3） 颜色矩
图像处理技术——模板匹配算法 左力2002．3． 认知是一个把未知与已知联系起来的过程。对一个复杂的视觉系统来说，它的内部常同时存在着多种输入和其它知识共存的表达形式。感知是把视觉输入与事前已有表达结合的过程，而识别也需要建立或发现各种内部表达式之间的联系。 匹配就是建立这些联系的技术和过程。建立联系的目的是为了用已知解释未知。 章毓晋《图像工程下册》P.163 一．模板匹配的基本概念 模板就是一幅已知的小图像。模板匹配就是在一幅大图像中搜寻目标，已知该图中有要找的目标，且该目标同模板有相同的尺寸、方向和图像，通过一定的算法可以在图中找到目标，确定其坐标位置。 以8位图像(其1个像素由1个字节描述)为例，模板T( m ? n个像素)叠放在被搜索图S( W ? H个像素)上平移，模板覆盖被搜索图的那块区域叫子图Sij。i，j为子图左上角在被搜索图S上的坐标。搜索范围是： 1 ≤ i ≤ W – M 1 ≤ j ≤ H – N 通过比较T和Sij的相似性，完成模板匹配过程。 注意：图像的数据是从下到上、从左到右排列的。 可以用下式衡量T和Sij相似性： ∑∑ = =- = N n ij M m n m T n m S j i D 12 1 )] , ( ) , ( [ ) ,(被搜索图 S 模板 T m i {
∑∑ ∑∑ ∑∑ ======+?-=N n M m N n ij M m N n ij M m n m T n m T n m S n m S 1 2 1 1 1 1 2 1 )] ,([),(),(2)],([ 上式的第一项为子图的能量，第三项为模板的能量，都与模板匹配无关。第二项是模板和子图的互相关，随( i, j )而改变。当模板和子图匹配时，该项有极大值。将其归一化，得模板匹配的相关系数： ∑∑∑∑∑∑======?= N n M m N n ij M m N n ij M m n m T n m S n m T n m S j i R 1 2 1 1 2 1 1 1 )] ,([)],([) ,(),(),( 当模板和子图完全一样时，相关系数R( i, j ) = 1。在被搜索图S 中完成全部搜索后，找出R 的最大值Rmax( im, jm )，其对应的子图Simjm 即为匹配目标。显然，用这种公式做图像匹配计算量大、速度较慢。 另一种算法是衡量T 和Sij 的误差，其公式为： ∑∑ ==-=N n ij M m n m T n m S j i E 1 1 |),(),(|),( E( i, j )为最小值处即为匹配目标。为提高计算速度，取一个误差阈值E 0，当E( i, j )> E 0时就停止该点的计算，继续下一点计算。 试验结果如下： 注：以上试验是在赛扬600 PC 机上用VC6.0进行的。 结果表明：被搜索图越大，匹配速度越慢；模板越小，匹配速度越快。误差法速度较快，阈值的大小对匹配速度影响大，和模板的尺寸有关。 二．改进模板匹配算法 我在误差算法的基础上设计了二次匹配误差算法： 第一次匹配是粗略匹配。取模板的隔行隔列数据，即四分之一的模板数据，在被搜索图上进行隔行隔列扫描匹配，即在原图的四分之一范围内匹配。由于数据量大幅度减少，匹配速度显著提高。 为了合理的给出一个误差阈值E0，我设计了一个确定误差阈值E0的准则： E 0 = e 0 * (m+1)/2 * (n+1)/2
二 特征点提取算法 1、基于SIFT （Scale Invariant Feature Transform ）方法的图像特征匹配 参看David G. Lowe 的“Distinctive Image Features from Scale-Invariant Keypoints ” 基于SIFT 方法的图像特征匹配可分为特征提取和特征匹配两个部分，可细化分为五个部分： ① 尺度空间极值检测（Scale-space extrema detection ）； ② 精确关键点定位（Keypoint localization ） ③ 关键点主方向分配（Orientation assignment ） ④ 关键点描述子生成（Keypoint descriptor generation ） ⑤ 比较描述子间欧氏距离进行匹配（Comparing the Euclidean distance of the descriptors for matching ） 1.1 尺度空间极值检测 特征关键点的性质之一就是对于尺度的变化保持不变性。因此我们所要寻找的特征点必须具备的性质之一，就是在不同尺度下都能被检测出来。要达到这个目的，我们可以在尺度空间内寻找某种稳定不变的特性。 Koenderink 和Lindeberg 已经证明，变换到尺度空间唯一的核函数是高斯函数。因此一个图像的尺度空间定义为：(,,)L x y σ，是由可变尺度的高斯函数(,,)G x y σ与输入图像(,)I x y 卷积得到，即： ),(),,(),,(y x I y x G y x L *=σσ （1.1） 其中：2222/)(221 ),,(σπσσy x e y x G +-= 在实际应用中，为了能计算的相对高效，所真正使用的是差分高斯尺度空间（difference of Gaussian ）(,,)D x y σ。其定义如下： ) ,,(),,() ,()),,(),,((),,(σσσσσy x L k y x L y x I y x G k y x G y x D -=*-= （1.2） 如上式，D 即是由两个相邻的尺度的差（两个相邻的尺度在尺度上相差一个相乘系数k ）。
Histograms of for Human Detection Navneet Dalal and Bill Triggs INRIA Rh?o ne-Alps,655avenue de l’Europe,Montbonnot38334,France {Navneet.Dalal,Bill.Triggs}@inrialpes.fr,http://lear.inrialpes.fr Abstract We study the question of feature sets for ob-ject recognition,adopting linear SVM based human detec-tion as a test case.After reviewing existing edge and gra-dient based descriptors,we show experimentally that grids of Histograms of Oriented Gradient(HOG)descriptors sig-ni?cantly outperform existing feature sets for human detec-tion.We study the in?uence of each stage of the computation on performance,concluding that?ne-scale gradients,?ne orientation binning,relatively coarse spatial binning,and high-quality local contrast normalization in overlapping de-scriptor blocks are all important for good results.The new approach gives near-perfect separation on the original MIT pedestrian database,so we introduce a more challenging dataset containing over1800annotated human images with a large range of pose variations and backgrounds. 1Introduction Detecting humans in images is a challenging task owing to their variable appearance and the wide range of poses that they can adopt.The?rst need is a robust feature set that allows the human form to be discriminated cleanly,even in cluttered backgrounds under dif?cult illumination.We study the issue of feature sets for human detection,showing that lo-cally normalized Histogram of Oriented Gradient(HOG)de-scriptors provide excellent performance relative to other ex-isting feature sets including wavelets[17,22].The proposed descriptors are reminiscent of edge orientation histograms [4,5],SIFT descriptors[12]and shape contexts[1],but they are computed on a dense grid of uniformly spaced cells and they use overlapping local contrast normalizations for im-proved performance.We make a detailed study of the effects of various implementation choices on detector performance, taking“pedestrian detection”(the detection of mostly visible people in more or less upright poses)as a test case.For sim-plicity and speed,we use linear SVM as a baseline classi?er throughout the study.The new detectors give essentially per-fect results on the MIT pedestrian test set[18,17],so we have created a more challenging set containing over1800pedes-trian images with a large range of poses and backgrounds. Ongoing work suggests that our feature set performs equally well for other shape-based object classes. We brie?y discuss previous work on human detection in §2,give an overview of our method§3,describe our data sets in§4and give a detailed description and experimental evaluation of each stage of the process in§5–6.The main conclusions are summarized in§7. 2Previous Work There is an extensive literature on object detection,but here we mention just a few relevant papers on human detec-tion[18,17,22,16,20].See[6]for a survey.Papageorgiou et al[18]describe a pedestrian detector based on a polynomial SVM using recti?ed Haar wavelets as input descriptors,with a parts(subwindow)based variant in[17].Depoortere et al give an optimized version of this[2].Gavrila&Philomen [8]take a more direct approach,extracting edge images and matching them to a set of learned exemplars using chamfer distance.This has been used in a practical real-time pedes-trian detection system[7].Viola et al[22]build an ef?cient moving person detector,using AdaBoost to train a chain of progressively more complex region rejection rules based on Haar-like wavelets and space-time differences.Ronfard et al[19]build an articulated body detector by incorporating SVM based limb classi?ers over1st and2nd order Gaussian ?lters in a dynamic programming framework similar to those of Felzenszwalb&Huttenlocher[3]and Ioffe&Forsyth [9].Mikolajczyk et al[16]use combinations of orientation-position histograms with binary-thresholded gradient magni-tudes to build a parts based method containing detectors for faces,heads,and front and side pro?les of upper and lower body parts.In contrast,our detector uses a simpler archi-tecture with a single detection window,but appears to give signi?cantly higher performance on pedestrian images. 3Overview of the Method This section gives an overview of our feature extraction chain,which is summarized in?g.1.Implementation details are postponed until§6.The method is based on evaluating well-normalized local histograms of image gradient orienta-tions in a dense grid.Similar features have seen increasing use over the past decade[4,5,12,15].The basic idea is that local object appearance and shape can often be characterized rather well by the distribution of local intensity gradients or 1