《ASIFT算法参考模板.doc》由会员分享，可在线阅读，更多相关《ASIFT算法参考模板.doc（15页珍藏版）》请在三一文库上搜索。
1、1. 绪论目标识别是在图像或视频中寻找目标的过程。在目标识别的应用中，特征提取和特征选择是第一个步骤，而且也是决定最后效果最重要的一个步骤之一。如果说一个完整应用是一个系统的话，那么特征就代表着由输入数据转化而来的，传送给系统其它部分的数据。很多时候最终能否得到一个理想的结果，在很大程度上依赖于能否找到最具代表性的特征。好的特征将会较大地降低后续工作的难度;不好的特征则会对系统后续处理产生干扰甚至使系统产生错误的输出。良好的特征也降低了系统后续处理的复杂度，为其广泛应用提供了可能。 SIFT(Scale-Invariant Feature Transform, 尺度不变特征转换)特征是一个检测
2、和描述图像局部特征的算法，这种算法具有优良的特性，能较准确地用于特征匹配。它具有广泛的用途，包括目标识别，三维重建、表情识别以及视频和运动追踪。SIFT基于两个大的组成部分，并使用了多种改进技术以改善各项指标。这里简要介绍经典SIFT算法和基于SIFT的目标识别应用。为后面介绍ASIFT算法作铺垫。 SIFT是一种检测与描述图像局部特征的方法。为了识别和描述图像中的目标，需要从图像中提取出与目标相联系的特征。利用这些特征可以从众多背景目标中识别出所需目标。为了确保准确无误地识别出目标，要求在各种视角、光照、距离以及噪声条件下仍然可以准确地进行匹配。SIFT使用不同的技术解决以上问题。对物体距离
3、远近，大小和噪声条件的适应由高斯尺度空间来完成，而视角、光照等条件则对应于特征描述符。SIFT并不是一开始就以解决上述问题为设计目标，而是先提出一种算法，而后发现它有诸多优良的性质。在SIFT算法提出以前，若干技术已经趋于成熟，而SIFT则成功地把它们整合为一个整体，并包括一些创新点。SIFT的两个主要组成部分是尺度空间检测和特征描述符。图像的特征点一般都比周围的点显著，比如位于极值点或灰度值变化加速率大的位置。特征的类型一般包括点、块、边缘、脊等。SIFT主要检测块状特征。借助一种旋转不变微分算子，SIFT可以在尺度空间中检测到特征点的所在位置和尺度。虽然存在很多其它的微分算子，SIFT却依
4、赖于LoG算子。其原因之一是实现方便，原因之二是LoG检测的特征比较稳定性。块状特征位于尺度空间的极值点，它们的一阶导数为零，而LoG算子并不是为了检测这些特征。LoG算子检测的是像素灰度值变化加速率极大和极小的位置。因为有些尺度空间上的极值点满足LoG的检测条件，所以SIFT检测到的特征既有块状特征，也有非块状特征。基于以上的分析可以看出，SIFT检测的特征点的标准比较严格，因而特征点也比较稳定，可以免受一定程度的外在影响。通过使用高斯差分空间(DoG)，可以相对较快地寻找到特征点位置。SIFT特征也具有尺度和旋转无关特性，也就是说，不管图像中的对象如何改变大小和旋转，其SIFT特征都是不变
5、的。这两种不变性是由特征检测和特征描述共同完成的。首先，基于尺度空间的LoG算子可以检测到任意方向、大小的特征，并且获得检测尺度参数。2 / 15SIFT的特征描述算法通过统计一阶微分向量的方向、大小来找到一个主方向，而后根据特征的检测尺度选择邻域范围，并产生描述符。SIFT特征的描述符是基于一阶微分，能应对相当程度的光照及视角的变化。为了获得最佳效果，SIFT将特征邻域分成4x4区域，并根据方向、大小作一阶向量的直方图统计。SIFT描述符覆盖的范围与LoG检测尺度有关，半径大概为检测尺度的6倍，因此能包括与特征有关的绝大多数信息。这个原则在工业界也称为6准则。为了区别不同位置的重要性，SIF
6、T用高斯窗口对各一阶微分向量的长度进行加权，使得远离特征中心的位置所占权重较小。传统上SIFT的匹配是通过最近邻方法查找的。为了加快查找速度，Lowe提出一种称为Best Bin First的近似方法，大大加快了匹配速度。在获得了大量的特征点以后，可以使用Hough变换和线性最小平方验证目标。目标识别是利用计算机在图像或视频序列中识别目标的任务。人类和动物可以利用视觉轻易地识别各种目标，包括物体、图像、绘画、影片等。人类可以在不同视角、大小、位移和旋转角的情况下，轻易地在图像中识别出多个物体。用机器来实现人类这种识别能力是一个前沿课题，目前利用特征来进行目标识别是一个主流的研究方向。图像和目标
7、经常会经历各种变化，但特征一般保持相对的稳定性，这使得利用特征研究目标识别问题成为了可能。基于特征的目标识别是伴随着计算机视觉的发展而出现的一种应用。基于图像特征的目标识别研究最近受到了广泛的关注。很多在某一方面性能出色的特征都被推广到一般的目标识别，这时其局限性也就显现了。这使得SIFT在目标识别方面的研究日益引起人们的注意。 基于SIFT的目标识别，是一种利用SIFT特征在图像中识别目标的应用。其目的是利用SIFT特征，根据视觉库提供的信息，从图像或视频中快速找出查询目标的过程。之所以“基于SIFT”是因为SIFT特征具有一系列优点，它在准确性和速度较其它特征有明显的优势。通过对视觉信号逐
8、层进行处理、分解和综合，获得所需目标并根据它进行识别。作为一个通用的特征，SIFT综合了各方面的优点。在SIFT提出之前，很多其它的方法利用目标的信息，比如形状、颜色、大小等进行识别。以往与应用紧密相关的特征方案不能明确保留图像的主要信息，要求人工调整参数来获得理想的结果，所以常常无法满足实时化、自动化和灵活性等方面的使用要求。为了满足以上目标识别要求，就要求特征能够尽量保留图像有关的信息量。换句话说，图像内容所传达的关于目标的信息更为重要。这就要求在提取特征的过程中去伪存真。这也需要详细研究目标成像的过程，以提取相关信息。同时采取措施抵消成像过程中造成的不利影响。 为了利用特征识别目标，需要
9、解决若干问题。首先是特征的表示。在目标经历各种位置、大小、角度、背景、光照之后，特征仍能正确表示目标。这个问题由SIFT特征部分地解决了。第二个问题是有了特征以后，如何识别目标。针对这方面的研究，主要可以分为两类。第一类是利用传统的SIFT特征在图像之间直接进行匹配，然后通过广义Hough变换或线性最小平方来计算目标形状，并删除离群值。很多其它方法都是在此基础上进行的推广。第二类是将SIFT特征进行向量量化，并用量化值来识别目标，比如通过直方图、分类器等方法。2ASIFT算法的基本原理2.1 算法概述由于相机正面拍摄物体时，相机的光轴方向可能发生变化，带来扭曲，所以第一步是对每张图片进行变换，
10、模拟所有可能的仿射扭曲。这些扭曲由两个参量决定：水平角度 和垂直角度 。将图像旋转 度由倾斜度参数 t 完成：t = 1 cos。设原始图像为 u ( x , y )，原始图像在 X 轴上倾斜度为 t 的变换由 u ( x , y ) u (t x , y)得到。对数字图像来说，倾斜图像由具有方向性的 t 倍二次采样(t-subsampling)得到。它要求之前在 X 轴上有一次抗走样处理(antialiasing filter)，最大限度的减少图像失真。该滤波由标准差为c的高斯卷积完成。在文献1中 Lowe 建议该值取c = 0.8。文献15中证明了该取值图像失真度较小。对图像进行旋转变换和
11、倾斜变换可以模拟有限的一些不同水平角度，垂直角度拍摄图像。对这些参数进行采样能保证模拟图像在不同的 和 引起的视角变换下保持近似。所有模拟倾斜后的图像将由 SIFT 算法进行匹配比较。2.2 水平和垂直采样 ASIFT 算法中水平角度和垂直角度的采样方式规定如下： 垂直角度 的抽样：垂直倾斜程度依次取几何级数：1,a, ,.,(a1)。在文献12中，Morel 指出 a = 2时，匹配的精确度和稀疏度达到较好的折衷。n 值可以是 5 或者更大。在随之发生的斜率转换中，倾斜度 t 可以达到 32 或者更大。水平角度 所对应的每个倾斜度是一组等差数列：0, b / t ,.k b / t ,当 b
12、 72度时取得较好的折衷，k 为当 kb / t 180度时的最大整数。 图 3-5 显示了 ASIFT 算法概貌：正方形 A,B 分别代表被比较的图像 u 和 v。ASIFT 算法模拟了所有相机视轴坐标方向变化引起的扭曲。图中的平行四边形代表模拟扭曲后的图像，该图像将运用 SIFT 进行后续的匹配计算。2.3 采样范围 倾斜度参数 t 的采样范围非常关键。只有当目标是一个完美的二维平面，或者是个反射光强弱完全相同的物体时，才有可能在任何倾斜视角下做到目标识别。现实中找不到这样的物体。因此，需要通过实验比较室内外拍摄的图片对，并找出可行的 t 的上界。每对图片由正面视角拍摄的图片和倾斜角度拍摄
13、的图片组成。文 献12给 出 倾 斜 度 t 的 上 限 是4， 对 应 的 视 角 最 大 值 为=arccos80度。=4的最大采样范围意味着 ASIFT 算法可以在= 32的范围内保持倾斜尺度不变性。2.4 采样步骤: 为使 ASIFT 算法对任何仿射变换具有不变性，倾斜度t和角度 必须具有较高精度。采样间隔由自然图像的多次实验得到。 在较大的 下，较小的 改变便能使图像产生较大的扭曲。对t 进行几何级数的采样可满足这一需求。一般来说，采样比率 t=应与角度无关。文献12中提出，倾斜度最佳采样间隔应是 t =。 同样的，对水平采样来说，当 = arccos1/t增加时，水平采样的精度必须
14、增加。在较大的垂直角度下，图像水平角度 较小的变化即能使图像产生较大扭曲。文献12中提出，水平最佳采样间隔应是 =。 经过采样间隔 t=和 =生成的模拟倾斜图像将放入SIFT算法进行匹配。图 3-6 说明了不规则采样参数 = arccos1/t和 在半球体上的显示情况。采样点集中在赤道区域。 图 3-6 按照参数 = arccos1/t和 进行抽样。黑色为采样点。左图为半球体沿Y 轴半球体透视图。右图为沿 Z 轴的半球体透视图。 值如图所示。2.5 针对不同图像分辨率的计算 在实际应用中，可能会存在不同分辨率下的图像匹配问题。ASIFT 遇到不同分辨率的图像时可归结到低分辨率下去实现。首先，程
15、序选择低分辨率搜索下会产生匹配对的仿射变换，然后在原始查询图像以及搜索图库中模拟所选的仿射变换，最后运用 SIFT 算法比较模拟仿射变换后的图片。两种不同分辨率下的解决办法如下所述： （1）、采用系数 K K二次采样查询图片 u 和待搜索图片 v。u = V=。且是反走样高斯离散滤波器，为 KK二次采样。 （2）、低分辨率下的 ASIFT 算法：对查询图片u 和搜索图片v 应用 3.3.1 节所述的 ASIFT 算法； （3）、确定u 和v 中可能产生最多匹配对的 M 种仿射变换; （4）、高分辨率下的 ASIFT：在原始图像 u 和 v 上使用 ASIFT 算法，但是模拟倾斜时只使用这 M
16、种仿射变换。 图 3-7 显示了两种不同分辨率下的 ASIFT 算法。左图为低分辨率的 ASIFT 算法，采用了3 3次二次采样。找到 19 个匹配点。右图为高分辨率 ASIFT 算法，找到 51 个点。2.6 ASIFT 算法复杂度 ASIFT 算法的复杂度计算基于最大极端的情况：倾斜度及角度范围=1,4且 =0度，180度,采样间隔为 t =， = 。由原图同一方向上的 t 次二次采样模拟倾斜率为 t 的图像，再将查询图片和搜索图片进行低分辨率下的 ASIFT 算法，做 K K= 3 3次双线性插值。确定 M 值后，在M 个最佳仿射变换下模拟高分辨率的 ASIFT 算法，寻找有无足够多的匹
17、配点。在实际应用中，当查询图片在海量数据库中进行匹配搜索时，大多数低分辨率步骤下的 ASIFT 匹配会不成立。高分辨率 ASIFT 只计算低分辨率下匹配的图片。 评估 ASIFT 复杂度归结起来是计算低分辨率下被模拟的图像区域。图像局部特征的计算量与输入图像面积成比例。ASIFT 模拟的全部图像区域与模拟的倾斜度 t 成正比。最复杂情况下模拟倾斜次数为=6。当二次采样因子 K K= 3 3时，ASIFT 算法进行计算的图像区域为原始图像的 1.5 倍。如下式所示。 在此情况下的 ASIFT 算法的倾斜度不变范围为 32。更大倾斜尺度不变范围可以通过更大的实现。和倾斜变换不变性(transiti
18、on tilt invariance)的指数增长相比，复杂度则为线性增长。 低分辨率 ASIFT 算法模拟了原始图像 1.5 倍的区域，并因此在查询图像及搜索图像上产生了 1.5 倍的更多特征点。因此低分辨率下的 ASIFT 算法特征匹配的复杂度是 SIFT 算法的= 2.25倍。 SIFT 的优化方式可以应用于 ASIFT 算法。目前有许多研究机构在致力于 SIFT算法速度的提高15-17。SIFT 算法曾在 FPGA18和 GPU19上被实现，但 ASIFT 算法目前尚无机构放入 DSP 中实现。3实验为验证本文所述asift算法的图像匹配方法的可行性与可靠性，本文最后将对自行手机拍摄的图
19、像进行ASIFT算法的图像匹配实验测试。本文图像匹配实验的软件实现条件是vc2010和opencv2.2。实验图像匹配的步骤如下：(1) 查找图像A和B的特征点；(2) 特征点匹配。(3) 特征点匹配图解：实验测试图像和实验匹配结果如下图所示： 匹配结果：图像匹配坐标点共有442个，此处只举例列出个别匹配点：164.307 260.589 118.654 262.953179.136 80.9082 133.056 81.9846118.836 129.792 91.2172 138.501117.983 130.06 89.6702 138.892187.622 107.185 139.42
20、4 107.32145.348 214.321 107.376 217.70643.5071 100.739 44.2185 120.834131.153 138.872 98.3331 145.883146.643 257.581 107.014 259.551190.384 96.7718 141.975 96.1417106.882 73.141 82.9933 87.0162106.055 175.642 82.004 182.547169.152 96.8202 126.89 99.6282207.588 95.4045 154.304 91.8537164.74 94.1928 1
21、21.845 97.8747129.501 138.537 97.7932 145.725155.304 80.6872 116.519 85.9208118.118 131.11 90.0714 139.839164.477 253.942 119.167 256.449135.59 254.042 99.8283 255.912166.707 111.546 124.111 114.79542.6098 98.7902 43.7896 119.218146.048 107.495 110.119 113.659127.82 222.562 95.5762 225.859126.947 14
22、0.983 97.1969 148.239142.367 110.089 107.323 116.763实验算法程序结果如下：在计算两个图像关键点14189 ASIFT 关键点被找到.6900 ASIFT关键点被找到.关键点计算完成了3秒.关键点匹配中.两幅图像匹配! 442 匹配点确定. log(nfa)=-740.035.关键点匹配3秒完成.实验结论：在pc上采用C+实验ASIFT算法的运行速度较慢。但还是验证了ASIFT算法的图像匹配功能。4.致谢 本文的研究和编写得到了多方面的支持，非常感谢涂老师的指导和帮助。感谢物理与电子信息学院老师对我的培养，是你们给了我这个再教育再学习的机会，你
23、们的广博知识和严谨的教学态度使我受益匪浅。最后对评审论文的各位专家、老师表示衷心的感谢，祝大家身体健康，一生幸福！参考文献1 D.G Lowe. Distinctive image features from scale-invariant key points. IJCV, 60(2):91110,2004.2 Young R A.The Gaussian derivative theory of spatial vision:Analysis of cortical cell receptive field line-weighting profiles. Technical Report
24、 GMR-4920,Computer Science Department, General Motors Research Lab.,Warren Michigan,19853 T. Lindeberg. Scale-space theory: a basic tool for analyzing structures at different scales.Journal of Applied Statistics, 21(1):225270, 1994.4 Lowe D G.Object recognition from local scale-invariant features.In
25、 International Conference on Computer Vision,Corfu,Greece,19995 Mikolajczyk K,Schmid C. An affine invariant interest point detector.In Proceedings of the International Conference on Computer Vision,Vancouver,Canda,20026 Lindeberg T.Shape from texture from a multi-scale perspective.In Proc. Internati
26、onal Conference on Computer Vision,Germany,19937 Beis J,Lowe D G.Shape indexing using approximate nearest-neighbour search in high dimensional spaces. In Conference on computer Vision anf Pattern Recognition,Puerto Rico.19968 J.M. Morel and G.Yu, Is SIFT Scale Invariant?, Inverse Problems and Imagin
27、g, vol 5, no. 1, Feb., 20119 Harris C G,StePhens M J.A Combined Cornerand Edge Deteetorc.Proceedings Fourth Alvey Vision Conference,Manehest78ef,147-151. 198810 Schmid, C., andMohr, R. Local grayvalue invariants for image retrieval. IEEE Trans. on Pattern Analysis and Machine Intelligence, 19(5):530
28、-534. 199711 Edelman, S., Intrator, N. and Poggio, T. Complex cells and object recognition. Unpublished manuscript. 1997.http:/kybele.psych.cornell.edu/edelman/archive.html12 G. Yu and J.M. Morel, A Fully Affine Invariant Image Comparison Method, Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Taipei, 2009.13 J.M. Morel and G.Yu, ASIFT: A New Framework for Fully Affine Invariant Image Comparison, SIAM Journal on Imaging Sciences, vol. 2, issue 2, pp. 438-469, 2009.