图像拼接系统算法研究及实现

1、四川大学硕 士 学 位 论 文题 目 图像拼接系统算法研究及实现 作 者 华骅 完成日期 2007年5月11日 培 养 单 位 四川大学 指 导 教 师 罗代升 专 业 电路与系统专业 研 究 方 向 智能系统与设计 授予学位日期 2007 年 6 月 日 - 105 -图像拼接系统算法研究及实现电路与系统专业研究生 华骅 指导老师 罗代升 教授摘要：随着数字成像设备的普及，人们对大视角图像有了越来越迫切的需求。获取这种图像有两种方法，第一是用专业设备拍摄，第二是多幅图像拼接，前者几何失真大难以校正，细节不足；后者几何失真小，细节充分，但难以拼接。本文按照实现一个图像拼接系统所需步骤，首先针对

2、传统基于像素的匹配方法和使用Harris角点法的不足，使用SIFT算法实现了旋转不变、放缩不变，而且能够适应一定光照和视点变化的特征提取。为获得各幅图像之间重叠部分的关系，需对提出的特征进行匹配，针对传统最近邻查找方法速度缓慢的缺点，提出了采用位置敏感散列算法，提高了匹配速度，并详细讨论了它的原理和实现细节。还将随机选取一致性算法用于错误匹配点对的筛除，解决了匹配结果会有很多错匹配的问题，可以获得完全正确的匹配点对。通过对成像几何的分析，说明了基于变换矩阵的拼接方法，并指出它的不足和解决办法。为从根本上避免变换矩阵法的不足，在深入研究基于拍摄模型的方法后，建立了球体模型的拼接流程，并使用一种普

3、遍适应的扫描模型，在统一的优化框架下解决了扫描图像拼接问题。还讨论了多种图像插值方法，并对拍摄模型法进行了拓展，使其适应性能更佳，鲁棒性更好。研究了多种拼接缝消除技术，揭示了在图像间有较大光照或色彩差异的情况下仅采用拼接缝消除技术所带来的不足，针对有较大光照或色彩差异的情况，采用了一种基于直方图的光照和色彩平衡方法，进行统一调整，然后再使用接缝消除技术能得到效果良好的拼接图像。讨论了全自动图像拼接系统所需要的技术细节和实现方法，实验表明本系统具有很好的鲁棒性和自动拼接能力。关键词：图像拼接 SIFT算法 位置敏感散列算法 鲁棒估计 球体模型 图像融合Study on Image Mosaic

4、SystemCircuit and SystemGraduate Student: HUA Hua Advisor: Luo DaishengABSTRACT With the popularity of digital imaging equipment, image with wide field of view are need more and more urgent. There are two methods to get such images, the first is that image with wide field are captured with professio

5、nal equipment, and the second is get the images with field with the technology of image mosaic. The geometric distortion of the former is large, hard to correlation and has insufficient details, and that of the latter is small and has full details. However the latter is difficult to mosaic.In this p

6、aper, according to the realization step for a Image Stitching System, first we point out the inadequate of traditional pixel-based matching methods and the Harris corner method, use SIFT algorithm to extract interest points which can achieve rotate invariant and scale invariant, and able to adapt to

7、 some changes in light and viewpoint.To obtain the image overlap between parts of the relationship, it is necessary to match the interest point. The traditional method of nearest neighbor search has very slow speed, to overcome the shortcoming, Locality Sensitive Hashing algorithm is used, and repre

8、sent detailed discussion of its principles and implementation details. In addition, Random Sample Consensus method is being used to remove mismatching interest points, in the result we get the complete correct matching point pairs.Based on the analysis of imaging geometry, we represent homography ma

9、trix stitching, and point out its shortcomings and solutions. In order to avoid homography matrix method shortcomings fundamentally, after in-depth study on shoot model method, a sphere stitching workflow is being established. And presents a general model of scanning image stitching which can adapt

10、to many scan-like situatons. Achieve a unified framework to resolve the problem of scanning images. Also discussed a wide range of image interpolation method, and expand shooting model method to make better adapability and robustness.We study some seamlines eliminating technicals, and reveal the ins

11、ufficiency of the way which only uses seamlines eliminating technical to the image in a large light or color difference. In order to deal with large differences of illumination and color situation, a method based on light and color histogram balance is proposed. Use that method to align all images i

12、nto same illumination or color situation, and then use seamlines eliminating technical will achieve excellent result.Discussed the technical details and implement methods of automatic image stitching system, the experiments show that the system is robust and has automatic stitching capability.Keywor

13、ds image mosaic, SIFT algorithm, Locality Sensitive Hashing algorithm, robust estimate, sphere model, image blending目 录1.绪论11.1.课题研究的意义与背景11.2.图像拼接技术的现状21.3.本课题的主要工作41.4.论文的组织结构52.图像特征提取62.1.尺度空间理论62.2.SIFT算法82.2.1.尺度空间极值提取82.2.2.亚像素精度122.2.3.候选特征点筛选142.2.4.候选特征方向赋值162.2.5.提取特征点描述182.2.6.算法流程212.3.本

14、章小节213.特征点匹配233.1.最近邻查找问题233.1.1.k-d树算法253.1.2.位置敏感散列算法273.2.特征匹配筛选383.2.1.粗筛选383.2.2.鲁棒估计393.2.3.RANSAC算法403.2.4.去除错误匹配点对413.2.5.试验结果443.3.本章小结454.拼接图像的生成464.1.成像几何464.1.1.成像模型464.1.2.照相机运动494.2.基于变换矩阵的拼接514.2.1.求解变换矩阵参数524.2.2.捆绑调整534.3.基于拍摄模型的拼接544.3.1.像素焦距554.3.2.球体模型564.3.3.参数优化求解594.3.4.扫描模型64

15、4.4.拓展和细节664.4.1.模型拓展664.4.2.图像插值684.5.本章小节725.图像融合735.1.平均值法735.2.加权平均值法745.3.最佳拼接缝法755.4.多分辨率法775.4.1.高斯金字塔785.4.2.拉普拉斯金字塔795.4.3.边界处理805.4.4.算法流程815.4.5.实验结果815.5.光照和色彩平衡855.6.本章小结906.总结和展望916.1.总结916.2.展望92参考文献93科研成果98声明99学位论文版权使用授权书99致谢100图像拼接系统算法研究及实现1. 绪论1.1. 课题研究的意义与背景数字成像设备（数码相机、数码摄像机等）的普及，

16、使得数码图像得到了越来越广泛的应用。在实际的科学研究和工程项目中，经常会用到超过人眼视角的超宽视角图像。由于距离的限制，普通数码相机的视角往往不能满足需要，某些超大尺寸的物体无法用一张照片拍摄下来。为了得到大视角的高分辨率图像，人们往往利用广角镜头来解决这一问题。然而，在一些特殊环境下，由于设备本身的限制使得数字图像和视频的视场宽度不能满足应用要求，例如利用广角镜头虽然也可得到宽视角的图像，但广角镜头的边缘会产生难以避免的扭曲变形。而且像广角镜头这样的特殊设备往往价格昂贵，使用费用较高。随着计算机和图像处理技术的发展，图像拼接技术为得到超宽视角图像提供了很好的解决方案。它可将一系列有重叠边界的

17、普通图像或视频图像进行无缝拼接，从而得到超宽视角图像。图像拼接技术的出现使采集图像的设备更普通化，利用普通的数码照相机即可得到满足要求的图像。在虚拟现实领域中，人们可以利用图像拼接技术来得到超宽视角图像，用来虚拟实际场景。这种基于超宽视角图像的虚拟现实系统，通过超宽视角图像的深度信息抽取，恢复场景的三维信息，进而建立三维模型。这个系统允许用户在虚拟环境中的一点作水平环视以及一定范围内的俯视和仰视，同时允许在环视的过程中动态地改变焦距。这样的超宽视角图像相当于人站在原地环顾四周时看到的情形。在医学图像处理方面，显微镜或超声波的视野较小，医师无法通过一幅图像进行诊视，同时对于大目标图像的数据测量也

18、需要把不完整的图像拼接为一个整体。所以把相邻的各幅图像拼接起来是实现远程数据测量和远程会诊的关键环节。在遥感技术领域中，利用图像拼接技术中的图像配准技术可以对来自同一区域的两幅或多幅图像进行比较，也可以利用图像拼接技术将遥感卫星拍摄到的有失真地面图像拼接成比较准确的完整图像，作为进一步研究的依据。在军事领域的夜视成像技术中，无论夜视微光还是红外成像设备都会由于摄像器材的限制而无法拍摄视野宽阔的图片。但是在实际应用中，很多时候需要将360度所拍摄的很多张图片合成一张图片，从而可以使观察者可以观察到周围的全部情况。使用图像拼接技术，在根据拍摄设备和周围景物的情况进行分析后，就可以将通过转动的拍摄器

19、材拍摄的涵盖周围360度景物的多幅图像进行拼接，从而实时地得到超大视角图像。这在红外预警中起到了很大的作用。本文研究了利用图像拼接技术突破成像设备本身的物理限制，得到大超宽视角图像像的理论和方法。1.2. 图像拼接技术的现状在早期，为了获得一个场景的超宽视角图像，人们采用的一种方法是直接利用全景照相机直接拍摄获取全景图像，如Meehan提出了一种利用全景照相机将拍摄的图像记录在长的胶片上直接获取一个全景图的方法1，Xiong Y.和Turkowski2利用自标定的鱼眼镜头拍摄全景图片来构造虚拟场景。虽然上述这些方法可以通过相机直接拍摄获取场景的全景图像，但是均需要昂贵的硬件来支持，而且所拍摄的

20、图像一般都具有一定的形变。另一种方法就是本文所讨论的图像拼接技术。关于图像拼接的原理和方法国内外已有不少的论文发表。国外具有代表性的研究人员有微软研究院的Richard Szeliski教授和匹兹堡大学的Sevket Gumustekin博士等人。Sevket Gumustekin博士主要对消除在固定点旋转摄像机拍摄自然景物时形成的透视变形，以及将捕获的图像拼接为全景图进行了研究。主要的研究成果是通过标定摄像机来建立成像模型，再利用成像模型将捕获到的图像投影到统一的高斯球面上，从而获得拼接图像34。用这种方法效果好、可靠性高，但是该方法要求对摄像机进行精确的标定，同时要求摄像机透镜本身的畸变参

21、数引起的图像变形可以忽略不计。在摄像机绕垂直轴线旋转的前提下，Mc Milliams和BiShop5提出了一种算法，依据摄像机绕轴旋转360所拍摄的图像序列求解摄像机参数，进而进行全景图拼接，但这种算法对相邻帧间摄像机的转动角度作了严格的限制，要求相邻帧间有2/3以上的重叠；Stein提出6了在相邻帧间进行纹理特征跟踪，进而求摄像机焦距和帧间偏移距离的算法，该算法能取得较好的精度，但是对纹理特征的检测和跟踪产生了巨大的计算量。Szeliski教授提出通过迭代求解每幅图像对应的旋转矩阵和摄像机焦距，来实现拼接的方法78。这种方法在一定程度上减少了拍摄图像时对摄像机运动的限制，但计算量却大大增加，

22、拼接结果也不稳定。Shmuel Peleg, Benny Rousso, Alex Rav-Acha和Assaf Zomet在Richard Szeliski的基础上做了进一步的改进，提出了自适应的图像拼接模型9，它是根据相机的不同运动，自适应选择拼接模型，通过把图像分成狭条进行多重投影来完成图像的拼接。在国内，图像拼接技术起步相对较晚，但现在已经发展起来了。国内浙江大学CAD&CG国家重点实验室和中国科学院自动化所模式识别国家重点实验室在图像匹配和拼接方面做了较多的研究工作1011。研究的成果主要是利用模板匹配的方法进行搜索来确定重叠区边界或最佳匹配位置，从而获得拼接图像。他们分别对微血管循

23、环的图像拼接和集成电路的图像拼接进行了研究。该方法的优点是原理比较直观，相对来说容易实现，缺点是计算量大，容易发生误匹配。浙江大学的许雷、张恒义等利用基于傅立叶变换的相位相关法对眼底图像的拼接进行了研究12。香港大学的Paul Bao和西北工业大学的张素等则对基于小波变换的图像拼接方法进行了研究1314。基于傅立叶变换和小波变换的方法有匹配准确率高和拼接效果好等优点，但是也有计算量大和受噪声干扰影响大的缺点。清华大学的研究人员提出了一种针对图像拼接过程中计算量与拼接精度之间进行折衷的方案，该方案用三角架保证摄像机基本绕垂直轴旋转，但是不对摄像机的旋转角度作严格限制15。同年，华中科技大学的研究

24、人员提出了依据变形图像推导出相邻两幅变形图像间的数学关系，用相关法识别特征点，经过几何变形校正以构成大图像的算法16。综上所述，由于图像拼接技术的应用前景和理论意义，因此引起了广大研究人员极大的兴趣。但是，总的来说图像拼接技术还处于研究的初始阶段，有待进一步的研究开发。1.3. 本课题的主要工作本课题的主要目标是实现一个鲁棒性强，自动化能力高的图像拼接系统，能够对照相机拍摄的图像、微观显微镜采集的图像、岩心扫描仪采集的图像和网络摄像头采集的图像进行自动拼接。本文所做的具体工作包括以下几个方面：1. 对获得图像间位置关系的方法进行了研究，分析了直接基于像素的方法存在的不足，并对传统的特征提取法H

25、arris角点法的不足也做了讨论。然后详细分析了鲁棒性能强的SIFT算法，详细阐述了它的原理和细节。2. 针对特征描述向量匹配速度缓慢的问题进行了研究，给出了最近邻查找的精确定义，对传统查找最近邻的方法进行了总结。详细论述了一种新颖的算法位置敏感散列算法，并提出用其对特征点进行匹配，具有良好的速度表现。3. 由于初匹配结果存在很多的错误，在具有大量错误干扰的情况下，本文对匹配点对的筛选方法进行了研究，将模型估计中的随机选择一致性算法推广到特征点匹配中，有效地去除了所有错误匹配点对，为实现全自动化拼接系统打下了坚实的基础。4. 通过对成像几何的分析，推导出了传统拼接中常用的8参数转换矩阵法，并讨

26、论了8参数转换矩阵法的不足和解决办法。本文深入研究了基于拍摄模型的拼接方法，并采用这种方法实现拼接，从根本上解决了转换矩阵法的不足。在此基础上又采用一种扫描模型，在拍摄模型法的统一框架下解决扫描图像拼接问题。最后还对基于拍摄模型的拼接法进行了拓展，使其适应性更佳，鲁棒性更强，并说明了实现时需要注意的细节问题。5. 对拼接缝消除技术进行深入研究，讨论了常用的拼接缝消除方法，本文采用具有最佳效果的多分辨率法对图像进行融合，有效地消除了拼接缝。在实际应用中发现，使用拼接缝消除算法对光照或色彩差异比较大的图像不能取得良好的结果，因此针对此问题使用了一种基于直方图的光照和色彩平衡算法，对全图进行校正，实

27、验表明能得到很好的结果。6. 对所有算法编写代码，进行实现，完成了一个自动化较佳，鲁棒性较强的拼接系统。1.4. 论文的组织结构第一章 阐述了图像拼接技术应用的场合和研究的必要性，说明了国内外图像拼接技术的研究现状。给出了选题背景和主要工作以及论文结构。第二章 比较基于像素和基于特征的方法，重点分析了对具有旋转、放缩和仿射变形都能适应的图像提取特征的算法SIFT算法。第三章 提出了用位置敏感散列算法对取得的图像特征点进行匹配，具有比较满意的匹配速度。研究了使用鲁棒估计方法来筛除错误的匹配点对，获得了完全正确的匹配效果。第四章 介绍了成像几何和基于变换矩阵的拼接方法。针对变换矩阵法的不足，论述了

28、基于模型的拼接方法，采用一种扫描模型用于扫描图像的拼接。最后还对模型进行了拓展，阐述了实现的一些细节。第五章 说明了拼接缝生成的原因，介绍了消除拼接缝的多种方法，并给出了实验结果。针对现有消除拼接缝方法的不足，使用一种光照和色彩平衡的方法对全图进行调整。第六章 本章对论文做了一个简单的总结，并指出了今后有必要开展的相关工作。2. 图像特征提取一般来说图像拼接的任务是把多幅具有重叠部分的图像进行整合，对于全自动拼接来说，要求计算机必须能够自动的识别出图像间的相同部分和它们的位置关系。由于图像之间相同部分的位置关系是后续拼接步骤的基础，所以对自动识别的正确性和鲁棒性提出了较高的要求。当前提取图像间

29、位置关系的方法主要可以分为两类，分别为基于像素的方法和基于特征的方法。基于像素的方法直接计算两幅图像素灰度的差值，认为相同部分的像素灰度差值应该比不同部分的差值要小。这种方法简单直观，但是计算量很大，而且在图像有较大旋转，较大光照、色彩差异等情况下往往会失败。基于特征的方法没有上述缺陷，所以近年来得到了广泛的研究。利用Harris角点作为特征点是一种使用较多的方法，但是角点检测会出现像素级的误差，这在图像拼接中会导致明显可见的图像错位，而且在一些特定情况下图像全部都为圆形特征，找不到角点。本章首先介绍尺度空间理论，这个是放缩不变性的基础。然后详细讨论了一种具有放缩，旋转和仿射不变性，能够抗拒一

30、定光照变化和视点变换的算法SIFT算法。此算法的强鲁棒性使得拼接系统的自动化水平和准确度得到了很大提升。2.1. 尺度空间理论当物体在某一种尺度标准下时，我们对物体的感知才是有意义的。比如对一个树木的认识，当我们离它几厘米的时候只能感知到树叶，在几米或更远的距离观察时，才能感知到树木。事实上物体在不同的尺度下表现出不同的特征，图像数据可以被表示为多重尺度的特征，这种多重尺度的表示方式称为尺度空间理论。图像尺度空间理论的主要思想是通过对原始图像进行尺度变换，获得图像多尺度下的尺度空间表示序列，然后可以对这些序列进行尺度空间特征提取。对信号多尺度表示的研究有较长的历史。早期的思想由Rosenfel

31、d和Thurston于1971年提出，他们发现了在边缘提取中使用不同大小的算子所带来的好处。Klinger17、Uhr18、Hanson和Riseman19、Tanimoto和Pavlidis20等人进行了后续研究，他们使用不同的空间分辨率来表示数字图像，比如，采用不同的算法对图像进行放缩。尺度空间理论最早出现于计算机视觉领域，其目的是模拟图像数据的多尺度特征21。信号的尺度空间定义如下22：设表示任意给定的信号，的尺度空间是一族信号的集合，这族信号是原信号在不同尺度下的尺度空间表征：其中，为原信号在尺度时的尺度空间表征。*为卷积运算，为尺度参量，且有，是尺度空间核。作为尺度空间理论中的一个重

32、要概念，尺度空间核定义为：对于所有的信号，若它与变换核卷积后得到的信号：中的极值数，即一阶微分过零点数，不超过原信号的极值数，则称为尺度空间核，所进行的卷积运算称为尺度变换。Lindeberg等人证明高斯卷积核是唯一的线性核。在图像中常用的二维高斯函数定义如下：其中是均值为0，方差为的正态分布。数字图像处理中，不同尺度下的尺度空间可以由图像与高斯函数进行卷积得到：其中为待处理的图像，是高斯函数的标准差，这里也可以理解为尺度空间的空间尺度因子。在实际图像卷积计算中，可以认为高斯函数作用半径为宽度，因为3个标准差宽度时曲线下的面积占全部高斯函数面积的。由于决定了平滑范围的大小，所以选择合适的尺度因

33、子进行平滑是建立尺度空间的关键。从尺度空间定义可以看出，尺度空间通过在图像数据中引入一个尺度维，提供了一个表达各个尺度层之间相互关系的途径，由此可以在所有尺度上分析图像，使不同尺度上的特征以一种精确的方式联系起来。2.2. SIFT算法Lowe23总结了现有的特征提取方法，并提出了一种新型高效的特征检测描述方法SIFT（Scale Invariant Feature Transform）。SIFT的主要思路是：首先建立图像的尺度空间表示，然后在尺度空间中搜索图像的极值点，由极值点再建立特征描述向量，最后用特征描述向量进行相似度匹配。采用SIFT方法提取的图像特征具有放缩不变性、旋转不变性，仿射

34、不变性，还有一定的抗光照变化和抗视点变换性能。该特征还具有高度的可区分性，能够在一个具有大量特征数据的数据库中精确的匹配。SIFT还使用金字塔算法大大缩小了提取特征时的运算量。计算方法分为四个步骤：尺度空间极值提取，特征点定位，特征方向赋值和提取特征点描述。2.2.1. 尺度空间极值提取尺度空间极值提取的任务就是将图像用多尺度空间表示，然后查找每一个尺度空间中的极值点，得到极值点所在像素的位置。这些位置将作为候选特征点在后面的步骤中被提炼和操作，以找到在不同视图下位置和大小能够反复出现的同一个物体。为了达到放缩不变性，需要在所有可能的尺度空间中搜索稳定的特征位置。将待处理的图像全部转换为灰度图

35、像，并归一化像素灰度范围为，使用式和式对图像做高斯卷积处理，在获得卷积后图像L后，使用高斯差函数DOG（Difference-of-Gaussian）建立尺度空间：k为固定的系数。Lindeberg24使用尺度归一化的高斯拉普拉斯函数LOG（Laplacian-of-Gaussian)进行极值提取，并且证明了这种方法的放缩不变性质，高斯拉普拉斯函数定义为，由式给出。这里使用高斯差函数代替了LOG，它们之间的关系可以通过热扩散方程来导出：根据微分公式，有：于是DOG和LOG的关系可以表示为：可以看出高斯差函数是高斯拉普拉斯函数的一个近似，乘子对所有的尺度起恒定的放大作用，因此不会影响极值点出现的

36、位置。当k趋近于1时，误差消失，但在实际实验中我们发现k的取值对极值位置的稳定性几乎没有任何影响。式表明计算高斯差图像D时，可以先对图像进行不同尺度的高斯卷积，然后相减即可。图2-1 高斯差图像生成过程创建的实际过程如图2-1所示，左边是对原始图像I做迭代的高斯卷积处理，并对长宽进行放缩的过程；右边为左边图像两两相减形成DOG，建立尺度空间后的结果。由于迭代的高斯卷积会去除原图大部分纹理细节，所以缩小图像不会减少图像中的信息量，而且还能大大提高运算处理速度。定义不同尺度之间高斯函数的标准差为倍数关系，即：设在每一尺度中有s幅高斯差图像，如图2-1右边所示，为了在尺度间达到式的关系，可以得出。在

37、每个尺度中，上层的高斯卷积图像是通过对下层的图像进行高斯卷积得到的，如：表示尺度n中的第p幅图像，为了满足上式，需要求出。高斯函数有如下性质：所以有：最终得到迭代递推关系：高斯卷积图像两两相减得到高斯差图像后，即可进行求极值的过程。将高斯差图像中的每个像素与它的邻域、它对应上一层图像的邻域、对应下一层图像的邻域一共26个像素点比较，如其灰度值为最大或者最小，则记录此点的位置和它所在的尺度，作为候选特征点，如图2-2所示。因为大多数点在前几次比较中就已经可以排除了，所以这个操作运算量较小。图2-2 极值点查找前面已经假设每一尺度中有s个高斯差图像，因此高斯卷积图像L必须有幅，为了在s幅高斯差图像

38、中能够保证查找到极值点，高斯卷积图像又需要增加2幅，所以在实际运算中高斯卷积图像L有幅。图2-3所示为的情况。图2-3 原图像与高斯差图像的数量关系图2-4是对一个办公桌照片做高斯差图像的例子，采用，共5个尺度。图2-4 高斯差图像2.2.2. 亚像素精度在尺度空间极值提取步骤中已经取得了以整数形式表示的候选特征点坐标位置，我们需要进一步确定特征点的亚像素精度，即获得以浮点数表示的精确位置。实验表明获得亚像素精度后的特征点在匹配性能和稳定性能上都有显著的提高。图2-5 亚像素精度极值点位置如图2-5，设极值点为，它与候选特征点的距离为，在邻域中一定为极值，把在处泰勒展开：其中，D为高斯差图像，

39、对式求导并令其等于0即可解出相对极值的偏移，有：由式极值点可由候选特征点得到，称为Hessian矩阵，称为Jacobian矩阵，也称为梯度：在数字图像中像素为离散信号，导数可以通过差分得到：其中为候选特征点所在的高斯差图像，为候选特征点上一层的高斯差图像，为候选特征点下一层的高斯差图像，即为候选特征点本身的灰度值。通过由式可以计算出Jacobian矩阵。对于二阶偏导和求法如下：其中：所以得出：同理可以推导出：由式、式和式可以计算出Hessian矩阵，代入到式得到偏移值，从而得到极值点的亚像素位置。当偏移值大于0.5时（方向或者方向）说明更靠近另一侧的像素点，此时让另一侧像素成为候选特征点，然后

40、重复上述计算，得到新的亚像素精度位置。最后，使用亚像素精度位置替换所有尺度的候选特征点的位置。2.2.3. 候选特征点筛选极值点的灰度值可以用来判断特征点是否处于低对比度的地方，低对比度容易受到噪声的干扰，这样的情况下特征点不稳定，应该舍去。将偏移值代入式可以得到极值点的灰度值：我们的实验表明在的时候选特征点应该被舍去。为了保证特征匹配的稳定性，仅仅去掉处于低对比度的特征点是不够的。高斯差函数还会在边缘处产生很强的响应，但不是所有处于边缘的候选特征点都是稳定的，需要去掉那些在边缘上容易受噪声影响的候选特征点。边缘上容易受噪声影响的位置一般具有较大的主曲率，但在垂直方向上的曲率又较小。主曲率可以

41、使用的Hessian矩阵计算：其中可以通过式和式得来。的特征值与D的主曲率成正比。由于我们只在乎它们的比值，所以可以避免显式计算的特征值25。设为较大的那个特征值，为较小的特征值，则它们的和为矩阵的迹，它们相乘为矩阵的行列式：设为和的比值，即，可以仅用来表示它们的比值：当两个特征值相等时式获得最小值，两个特征值差别越大时其值越大。因此，对于一个给定的阈值，仅仅需要检查：这样的算法使得运算量得以大大减少，检测一个候选特征点低于20次浮点运算。我们的实验中阈值取为20。图2-6表示了筛选前后的候选特征点位置和个数的关系，图2-6(a)中共有1033个候选特征点，图2-6(b)共有候选特征点461个

42、，可见有以上的候选特征点被删除。 （a）所有候选特征点 （b）筛选后的候选特征点图2-6 提取出的候选特征点2.2.4. 候选特征方向赋值特征方向赋值就是对每一个候选特征点，我们通过计算它们所在局部位置的信息给它们赋予一个主方向。每个候选特征点都有一个属于自己的主方向，后面计算出的特征点描述向量根据这个主方向进行旋转，这样的特征点描述向量就具有了旋转不变性。首先获得候选特征点对应的高斯卷积图像L（本文选择两两相减的下层高斯卷积图），这样可以保持放缩不变性。对一个候选特征点，可以通过它的四邻域得到它所在位置的梯度幅度大小和梯度方向：但是仅仅对候选特征点的位置计算梯度幅度大小和梯度方向是不够的，因

43、为单个像素点极易受到噪声的干扰。为了提高鲁棒性，我们对候选特征点所在位置的一个邻域进行梯度方向的统计。为了凸显候选特征点的作用，在邻域上使用高斯窗函数进行加权。此处采用作为高斯窗函数的标准差，其中为候选特征点所在DOG图像的尺度（即DOG对应的高斯函数标准差）。如2.1节所述，高斯窗函数的作用半径为三倍标准差范围，所以我们对候选特征点半径为的邻域进行梯度方向和幅度的统计，统计方法如下：对半径邻域范围内的所有像素计算式，获得对应的梯度幅度大小和梯度方向。梯度方向的度数范围为，把此范围划分为36个区间，每个区间10度，则形成了一个直方图（记为bin）。根据邻域范围内像素的梯度方向，可以求出此梯度方

44、向属于的区间号，然后赋予此区间的值为原值加上此像素点的梯度幅度与高斯窗函数的加权。使用伪代码语言表示如下：bin为具有36个区间的直方图，i为像素梯度方向所属的区间，为高斯窗加权函数，它的中心为候选特征点所在位置，为偏离中心的距离。直方图中值最大的区间代表了候选特征点局部邻域中梯度的主要方向，最大值代表了这个方向上梯度的幅度大小。我们把候选特征点局部邻域中梯度的主要方向作为候选特征点的一个信息保存下来，在后面提取特征点描述向量时使用。若直方图中存在某些区间值大于最大值的，那么也记录下这些区间所代表的方向，然后创建新的候选特征点，这些新创建的候选特征点的坐标位置与原来的候选特征点相同，所属于的尺

45、度也相同，唯一的差别就是梯度方向不同。需要创建新候选特征点的概率不大，但是这些新建的候选特征点能在匹配中提供更好的稳定性。为了得到更准确的精度，我们对直方图的区间和区间值进行抛物线拟合，获得精确的梯度幅度最大值和最大值对应的梯度方向。建立坐标如图2-7所示：图2-7 抛物线拟合设坐标点为，其中为直方图中最大值的区间号，为直方图中的最大值，和分别为最大值左边和右边的区间对应的幅度。认为这三个坐标点符合抛物线函数，把坐标点代入抛物线方程即可解得参数：于是，经过拟合后最大值为b，对应的梯度方向为c（由于c是相对于坐标位置0的，需要转换为真实梯度方向）。最后，使用梯度方向c替换候选特征点中的主梯度方向

46、信息。2.2.5. 提取特征点描述通过2.2.1节至2.2.4节的算法，候选特征点具有如下信息：精确的位置，它所在的尺度和对应主梯度方向，并且已经淘汰了处于低对比度和处于不良边缘的不稳定候选特征点。此时已经具有亚像素精度、放缩不变性和旋转不变性，候选特征点可正式称为特征点。提取特征点描述的任务就是找到描述特征点信息的最优方法，力求达到高度可区分性，即具有微小差别的特征点都应该具有不同的特征点描述向量，并进一步达到对光照和视点的不变性。直接使用特征点周围像素的灰度值来描述特征点信息是最简单、直观的方法，但是这种方法极易受到噪声、光照、变形等的影响，最后导致匹配失败。由于人类的视觉系统远远比当前的

47、计算机视觉系统高级，使用计算机来模仿和借鉴生物视觉过程有很大潜力，而且近年来对生物怎样识别物体的研究有了很大进展，Lowe采用的算法灵感就来源于Edelman26等人对生物大脑识别物体方式的研究结果。Edelman指出灵长类动物初级视觉系统大脑皮层中的复杂神经元对某些特殊方向的梯度和空间频率敏感，他们设计的生物实验证明了对梯度进行匹配能够达到很好的结果。首先，使用式计算特征点对应的高斯卷积图像L中周围像素的梯度幅度大小和梯度方向。同样的，为了凸显特征点的主要作用，使用高斯窗函数对邻域梯度幅度大小进行加权。此处采用作为高斯窗函数的标准差，其中为特征点的邻域半径，在图2-8中用圆圈表示。采用高斯窗

48、函数加权还可以避免由于邻域位置出现微小变动而造成特征描述向量突变的现象。把特征点邻域范围划分为的像素块，如图2-8左边所示。在每个的像素块中建立梯度方向直方图，与2.2.4节中不同，此处划分为8个区间，并统计像素块中每个像素梯度方向属于的区间，这个区间的值为所有梯度方向属于这个区间的像素的梯度幅度大小高斯加权后的累加，在图2-8右边使用箭头长度表示，伪代码表示类似于式。因此每个像素块都可以用一个长度为8维的特征描述向量表示，每一维对应于直方图的一个区间。本文在特征点周围统计邻域范围的像素用以描述其特征点的特征，生成16（）个直方图，每个直方图包含8个特征。所以对于每一个特征点，一共使用维的特征

49、描述向量对其进行描述，如图2-8右边所示。图2-8 提取特征点描述记特征描述向量为，为了使其具有光照不变性，我们把特征描述向量归一化为单位长度，方法如下式：光照对图像的影响如下式表示：具体来说，图像亮度的改变实际上是对图像中每一个像素点都加上（或减去）去某个固定值，这样的操作不会改变图像梯度方向和梯度幅度大小，所以不会对特征描述向量造成任何影响，特征具有亮度不变性。图像对比度的改变实际上是对图像中每一个像素乘以一个固定值，这个操作使梯度幅度大小也乘上了相同的固定值，但是不会影响梯度方向。对特征描述向量归一化后，对梯度幅度大小的影响也就消失了，特征具有了对比度不变性。上述的光照变化模型为线型模型

50、，光照的非线型变化虽然不常见，但是也可能由相机底片的动态范围限制（底片能表现的最暗到最亮的范围远远比人眼能分辨的范围要窄）或者某些三维物体不同表面的不同反射造成。这些情况下会对图像中某些梯度幅度大小造成很大影响，但是对梯度方向的影响不大，所以需要对特征描述向量中梯度幅度大小的作用加以限制，降低它的重要性，强调梯度方向的分布规律。为了达到上述目的，我们使用阈值对归一化后的特征描述向量进行限制，令所有高于阈值的向量元素都等于阈值，然后使用式再次对限制后的特征描述向量进行归一化。本文的阈值采用建议值0.2。2.2.6. 算法流程图2-9说明了整个SIFT算法的流程。2.3. 本章小节在图像拼接的过程

51、中，图像特征提取是相当重要的环节，它的性能会对特征点匹配的准确度产生很大影响。SIFT是一种优秀的特征提取算法，提取效果不受图像质量的影响，能够正确的提取出描述物体本质的信息。本章详细描述了SIFT算法的理论和各个实现细节，这些细节是保证SIFT算法能够做到旋转，放缩和仿射不变的关键，同时也考虑了光照变化等因素的影响，最后还给出了完整的算法流程图。图2-9 SIFT算法流程图3. 特征点匹配获得了特征点描述向量后，就需要对两幅图像的特征点进行匹配。特征点匹配是指在一幅图像中查找它每一个特征点在另外一幅图像中的最近邻，理想状态下两幅图像相同部分的特征点应该具有相同的特征描述向量，所以它们之间的距

52、离应该最近。由于我们提取的特征点处于128维的空间中，而且每幅图像都对应着大量的特征点，在高维空间中查找最近邻需要极多的时间和空间，如何快速的查找到它们对应的最近邻是本章要解决的问题。最近邻查找在计算机算法中占有重要的地位，应用范围非常广泛，例如在模式识别2728、多媒体数据检索29、数据压缩30、数值统计31和数据融合32等中都有应用。本章给出了最近邻问题以及近似最近邻问题的定义，讨论了常用的几种能够快速查找匹配的数据结构和算法。提出了用位置敏感散列算法对图像特征点进行匹配，具有良好的匹配速度。并对位置敏感散列算法进行了全面的研究，说明了一些具体实现中需要注意的细节问题。由于图像之间存在不重

53、叠的部分，这些区域中的特征点在另一幅图像中并没有与之对应的特征点存在，但是最近邻算法仍然会给出一个相对的最近邻做为它的匹配点，这些匹配点对明显是错误的。为了排除这些错误的匹配点对，本章采用基于鲁棒估计的随机选取一致性算法对其进行筛选，并讨论了算法特点和实现细节，在最后实验中取得了很好的效果。3.1. 最近邻查找问题最近邻查找问题在欧式空间中的定义如下：定义（最近邻问题）：在d维空间中，对一个点集建立一个数据结构，能够对任意给定的点q，在M中高效的查找到距离它最近的点p。对于向量，定义距离为：式也称为范数。最近邻查找的一个简单而直观的算法如下：对于给定的点q，计算它对于子集M中每一个点的距离，最

54、后统计出距离最短的那一个点，记为p。这种方法有多种名称，如线型扫描法、线性搜索法、暴搜法等等。它的搜索时间为，这个运算时间在数据量很小的时候还是可以接受的，当数据量增大后运算时间就会很长。Lipton33和Shamos3435指出当所有点都在同一平面的时候，最近邻查找问题可以在时间和空间内解决，但是在我们的问题中，需要匹配的特征描述向量不能满足在同一平面内这个要求。Clarkson36提出了一种在固定维数上基于Voronoi图的随机提取特征子集的算法，即RPO树算法，但是这种算法在最坏的情况下效率仍然很低下。Yao37提出的改进算法能够再提高一点效率，但是提高幅度太小，不具有实用性。当前使用最

55、广泛的算法是由Friedman、Bentley和Finkel38提出的k-d树算法，在输入点集满足一定的限定条件时k-d树算法的运算时间可为对数时间。低维（如13维）情况下的最近邻查找问题已经有很好的解决方法39，比如在一维情况下使用折半查找算法，复杂度为。现在的主要方向是解决维数较高情况下的近邻查找问题，在维数“足够”大时，上述所有方法与线性搜索法相比效率没有什么实质上的提高，这也称为“维数灾”情况。由于长久以来对高维最近邻的研究都没有取得实质性进展，所以很多学者猜测不存在一个高效的算法能够彻底解决“维数灾”情况，进而研究近似最近邻问题的高效求解算法。使用表示点q到点p的距离，具体定义参见式

56、，近似最近邻问题有如下几种定义：定义（-近似最近邻问题）：在d维空间中，对一个点集建立一个数据结构，能够对任意给定的点q，在M中高效的查找到点，使，其中p为q的最近邻，。定义（c-近似最近邻问题）：在d维空间中，对一个点集建立一个数据结构，能够对任意给定的点q，在P中高效的查找到点，使，其中p为q的最近邻，。从上述两种定义可以看出当时两种定义等价。近似最近邻问题还有以下其他的定义方法：定义（R-近邻）：在点集中，如果点p和点q的距离至多为R，则称点p是点q的R-近邻。图3-1(a)表示了对于点q的最近邻和R-近邻之间的关系。(a) (b)图3-1 近邻定义示意图定义（随机c-近似最近邻问题）：在d维空间中，对一个点集建立一个数据结构，能够对任意给定的点q，在M中完成以下运算：如果存在q的R-近邻，那么返回cR-近邻的概率为。其中，。图3-1(b)表示了对于点q而言的cR-近邻的概念。特殊的，当我们选取最近邻作为R-近邻，并且让，随机c-近似最近邻问题就转化为c-近似最近邻问题。3.1.1. k-d树算法对于d维空间中给定的n个点（即点集M），k-d树采用迭代的方法