一种基于分块策略的SIFT特征快速提取与匹配方法

一种基于分块策略的 SIFT特 征 快 速提取与匹配方法 闸 旋1 ，王 慧2 ，程 挺3 ，李 烁2 ，郭忠磊1( 1 92859 部队，天津 300061; 2 信息工程大学，河南 郑州 450001;3 78155 部队，四川 成都610036)摘要:通过研究基于 GPGPU 的 SIFT 特征匹配，提出一种通过分块处理实现大面阵遥感影像快速匹配的方法。首先采用鲁棒性强的随机采样一致性算法来估计待匹配影像间的单应关系并剔除误匹配点; 然后通 过单应关系找到待匹配影像间的重叠区域，进而实现大面阵遥感影像的分块 SIFT 特征提取和匹配。试验 证明该算法可较快提取相应航摄测区的同名像点，为后续进行的光束法区域网平差提供了鲁棒的数据源。 关 键 词:图形处理单元; 尺度不变特征变换; 单应矩阵; 图像分块; 随机采样一致性中图分类号:P237文献标识码:ADOI 编码:10 3969 / j issn 1673-6338 2014 05 014A Fast SIFT Feature Detecting and MatchingMethod Based on Partitioning StrategyZHA Xuan1 ， WANG Hui2 ， CHENG Ting3 ， LI Shuo2 ， GUO Zhonglei1( 1 92859 Troops， Tianjin 300061， China; 2 Information Engineering University， Zhengzhou 450001， China;3 78155 Troops， Chengdu 610036， China )Abstract: After researching SIFT feature detecting and matching based on partitioning strategy， a feature matchingmethod apply to remote sensing imagery of bedding face array by blocking its area is proposed This method first a- dopt the robust ANSAC algorithm to estimate homography relationship between two images to be matched and e- liminate false matching points，then find overlapping area between two images via the homographic matrix so as to achieve SIFT feature partitioned detecting and matching on remote sensing imagery of bedding face array The pro- posed algorithm was experimented to verify that it can extract survey area corresponding points quickly， which can be provided as robust data foundation for bundle adjustment next to be conductedKey words: GPU; SIFT; homographic matrix; image block; random sample consensus近 10 多年来，图像局部不变特征一直是图像处理、模式识别领域研究的热点问题。Lindeberg1 奠定了局部不变特征方法的理论基础，而 Lowe2 则将 Lindeberg 这些 理 论 予 以 实 现，于 1999 年 提 出著名的尺度不变特征变换 SIFT( Scale Invariant Feature Transform) 描述子，并在 2004 年对其进行 完善3。SIFT 描述子的性能是公认的，其他大多 数描述 子 如 SUF4，GLOH5，PCA-SIFT6 和 形 状上下文7都是充分借鉴了 SIFT 的思想，并在该 描述子的基础上改进得到的。但 无 论 是 SIFT 算 法还是众多的改进算法，它们的特征提取过程都 具有较高的时间复杂度，且其特征点描述向量维数高，匹配也很难达到实时的要求。近年来，随着高性能并行计算技术的 飞 速 发 展以及在各领域的广泛应用，为加快遥感数据处 理速度提供了有效途径。图形处理器通用计算技 术 GPGPU( General Purpose Computing on Graphics Processing Units) 作为通用计算中并 行 计 算 的 一 个新分支，试图把个人计算机显卡上的 GPU 当做 CPU 这样的通用处理器来承担通用计 算 任 务。 GPGPU 不是单纯地使用 GPU 承担计算机中的通用计算任务，而是一种利用异构计算资源的大规 模并行计算，是计算密集型应用的高效解决方案。 相比 CPU 而言，GPU 在 体 积、功耗和性价比方面 收稿日期:2013-07-12; 修回日期:2014-03-08。作者简介:闸 旋( 1988 ) ，男，湖北武汉人，助理工程师，硕士，主要研究方向为数字摄影测量与并行计算。E-mail: 919898582 qq com506测 绘 科 学 技 术 学 报 2014 年算法11 具具有明显优势，已经成为越来越多的传统超级计算机的替代品，并在事实上作为第 2 个通用处理 器被大量软件和操作系统使用8。SIFTGPU 是一个 GPU 版本的 SIFT 描述子提 取和匹配的开源程序9。与 CPU 版本的 SIFT 相 比，SIFTGPU 通过充分利用现代显卡上的大量图 形处理单元，获得了良好的加速效果。但直接利 用 SIFTGPU 对面阵遥感影像进行 SIFT 特征提取 与匹配，要求计算机显卡具有足够大的显存空间 来存储运算过程中产生的中间数据。换言之，若 图像太大而显存不够存储计算过程的中间数据， 就无法成功利用 SIFTGPU 实现 SIFT 特征提取与 匹配。针对传统 SIFT 算法运算速度上的局限性，利 用 SIFTGPU 开源程序实现单 机 CPU + GPU 异 构 条件下 SIFT 算法的并行运行; 并设计相应的分块 优化策略，有效解决利用 SIFTGPU 进行大图像匹 配内存不足的问题，同时实现任意幅面面阵影像 快速 SIFT 特征提取与匹配。ANSAC( andom Sample Consensus)有实现简单和性能良好的优点，故采用该算法估计同名像对的透视变换参数。利用 ANSAC 算法估计图像透视变换关系 的中心思 想 是 将匹配所得同名点分为内点和外 点，其中内点为符合实际 模 型 的 点 ( 正 确 匹 配 点) ，外点为不符合实际模型的点( 误匹配点) ，最 后使用提纯后的内点估计矩阵 H。2基于重叠区域分块的特征点提取和匹配立体像对中存在共同的地物区域，这是影像能够成功匹配得到同名点的前提。在立体像对的重叠区域中寻找同名点，一方面避免了对影像中 非重叠区域进行特征提取的无效操作，节约了时 间; 另一方面有效避免了非重叠区域所提取的特 征点与重叠区域所提取特征点的误匹配，提高了 匹配成功率。2 1基于透视变换估计同名像对的重叠区域下面以图 1 说明如何根据两幅影像间单应矩阵估计两幅影像的重叠区域。在两幅影像间单应矩阵已知情况下，可根据式 ( 1) 计算出右影像上 对应左影像上的 4 个角点坐标的透视变换坐标， 以这 4 个透视变换坐标为顶点的四边形即为右影 像上这两幅影像的重叠区域; 同理可求得左影像 上两张影像的重叠区域。一般情况下所求得的重 叠区域为不规则四边形，但是为了便于后续分块 计算，取相应重叠区域的外接矩形为最终的重叠 区域( 图 1 中矩形框内的影像区域) 。1两幅影像之间的变换关系透视变换平面透视变换是关于齐次三维矢量的一种线性变换，可用一个非奇异的矩阵 H 表示为 h1h2h5h8h3 x1 x1 x = h42h6 x2 ，( 1) h7 x h9 x 33HX。其 中，H 称 为 单 应或更简洁 地 表 示 为 X=矩阵10。进行航空摄影测量时，被( homography)摄影地面的深度大小变化一般远小于地面与摄像机的距离，故可将被摄地面近似看作平面，即用平 面透视变换近似表示面阵相机的成像过程。由于 两透视变换的复合仍然是透视变换10，则可以用 式( 1) 来表示两幅图像间的透视变换关系。矩阵 H 乘以 任 意 一 个非零的比例因子不会 使透视变换改变。即 H 为一个齐次 矩 阵，有 意 义 的仅仅是矩阵元素的比率。矩阵 H 的 9 个元素中 有 8 个独立的比率，因此一个透视变换有 8 个独立 变量。对于一般的面阵遥感影像，由于摄影幅面大， 其图像特征十分丰富，往往可以得到大量的特征 点匹配对，而图像间透视变换关系的计算，只需要4 对个同名点便可完成，因此，这是一个数值分析 中的过定问题。同时考虑到匹配得到的同名点中 可能存在部分错误匹配点，故必须采用鲁棒性强 的算法进行单应矩阵估计。由于随机采样一致性( a)左影像( b)右影像图 1重叠区域的估计当影像尺寸较大时，检测两幅影像重叠区域 的算法并未直接在原始影像上进行，而是以缩放比例因子为 1 和 2 对原始影像进行降采样，形成大小为原始影像 1 / 1 和 1 / 2 的缩小影像。然 后，再对两幅缩小影像进行 SIFT 特 征 提 取 和 匹闸 旋，等: 一种基于分块策略的 SIFT 特征快速提取与匹配方法第 31 卷第 5 期507配，并利用 ANSAC 算法估计两幅缩小影像间的透视变换参数。不在原始影像上直接进行特征提 取和匹配的原因是，一方面可以避免当图像较大 情况下，中间过程数据过多而造成存储空间不足 的情况; 另一方面是即使计算机存储空间足够大， 可以在原始影像上直接进行特征点提取、匹配和 透视变换参数估计，但这种情况下提取特征点数 量极大，进行计算需耗费较长时间。但是在缩小影 像间估计得到的透视变换参数与原始影像间的透 视变换参数并不等价，可以通过一定的数学关系， 将缩小影像间估计得到的透视变换矩阵，反变换 计算出原始影像间的透视变换矩阵 H。下面推导 原始影像立体像对透视变换关系矩阵 H 与对 相 应的原始立体像对分别以比例因子 1 和 2 缩小 后所得立体像对的透视变换关系矩阵之间的数学 关系。单应矩阵之 后，即 可 根 据 式 ( 5 ) 计算得到原始像 对之间的单应矩阵 H。2 2分块特征点提取和匹配再以图 2 说 明 如 何 根 据 H 计算两幅影像的 重叠区域并进行分块提取和匹配。估 计 出 H 后可根据式( 1) 计算出右影像上对应左影像上的 4 个角点坐标的透视变换坐标，以这 4 个透视变换 坐标为顶点的四边形即为右影像上这两幅影像的 重叠区域。同理可求得左影像上两张影像的重叠 区域。一般情况下所求得的重叠区域为不规则四 边形，但是为了便于后续分块计算，取相应重叠区 域的外接矩形为最终的重叠区域。如图 2 中加粗 矩形框内的范围即为两幅影像的重叠区域。根据 求得的立体像对重叠区域范围，以左片重叠区域 为基准，进行分块。针对左片所分得的每一个子 块的 4 个角点的像素坐标，同样根据透视变换关 系，可得左影像每一子区域在右影像上相应的重 叠子区域。设原始 影 像 对上有同名像点 ( x，y)和 ( x，y) ，那么式( 1)可表示为h1 x + h2 y + h3 = h x + h y + h ;x789( 2)h4 x + h5 y + h6y= h x + h y + h 789设立体像对的两幅影像缩小因子分别为 1和 2 ，则同名像点( x，y) 和( x，y) 在缩小影像上 相应的坐标为 ( x / 1 ，y / 1 ) 和 ( x / 2 ，y / 2 ) ，仿 照式( 2) 可以得到 h1 ( x / 1 ) + h2 ( y / 1 )+ h3;+ hx / 2= h ( x / ) + h ( y / )图 2 重叠区域估计与子区域选取示意图取得左右两幅影像重叠子区域范围 之 后，对 该同 名子区域进行特征点提取和匹 配，利 用 ANSAC 剔除误匹配点后输出同名点信息。依次 对所有子区域进行如上操作，将所有子块所提取 的同名点信息进行合并，即可以得到原始像对的 同名点匹配结果。71819( 3)h4 ( x / 1 ) + h5 ( y / 1 )+ h6y / 2= h ( x / ) + h ( y / )+ h 71对式( 3) 整理得到819 ( 2 / 1 ) h1 x + ( 2 / 1 ) h2 y + 2 h3x=;( 1 / ) h x + ( 1 / ) h y + h17189( 4)( 2 / 1 ) h4 x + ( 2 / 1 ) h5 y + 2 h6y=( 1 / ) h x + ( 1 / ) h y + h171893实验与分析实 验 的 硬 件 环 境 为比较式( 3) 和式( 4) ，可 得 H 与缩小影像间的透 视变换矩阵之间的关系为双 核Intel i5CPU( 2 9 GHz) ，主 机 内 存 8 Gb，华 硕 GTX 570 显 卡( 显存 1 Gb) ; 软 件 环 境 为 Windows7 操 作 系 统、 Microsoft Visual Studio 2010 开 发 环 境、编 程 语 言 为 C + + ，并行开发包为 英伟达公司提供的 CU-DA 4 0。3 1单个像对 SIFT 特征提取和匹配图 3 和图 4 分别选取两组存在一定重叠的无 人机航摄影像像对( 其中图 4 的右影像相对于左 影像大致旋转 180) ，由于原始影像幅面大，故只 h1h2h5h8h3 h4h6 =H = h7h9 ( 2 / 1 ) h2 ( 2 / 1 ) h5 ( 1 / 1 ) h8 ( 2 / 1 ) h12 h3 ( 2 / 1 ) h42 h6 ( 5) ( 1 / 1 ) h7 h9利用 ANSAC 算法得到两幅缩小影像 间 的508测 绘 科 学 技 术 学 报 2014 年截取部分重叠区域显示同名影像对提取和匹配结果。所提取的同名特征点以“十字”标明其位置， 可以看出提出算法能够成功地对两组影像进行特 征点提取和匹配。表 1不同像幅 SIFT 特征提取和匹配得串并行性能对比GPU 并行分块串行处理GPU 并行不分块 ( 阈值取 512 像素)影像尺寸 /( 像素 像素)耗时 / s耗时 / s加速比耗时 / s加速比75 115150 230225 345300 460375 575450 690525 805600 920675 1 035750 1 150975 1 4951 125 1 7251 350 2 0701 500 2 3001 875 2 8752 250 3 4503 000 4 6003 750 5 7504 500 6 9005 250 8 0506 000 9 2006 750 10 3507 500 11 5000 0160 0620 1250 2490 4250 7020 9991 3891 9652 6376 0849 31317 06723 36948 36791 848258 0250 2990 3320 3910 4330 5730 6170 6960 7840 8210 8900 9420 10 20 30 60 71 11 41 83 43 06 5N N N N N N N N N N N NOO O O0 4320 5220 5810 6691 1631 1731 3691 5732 0172 2243 0203 9706 41010 14414 64420 26327 27637 49449 537NN N N0 981 31 72 02 12 24 45 98 510 516 023 140 6N N N N N N( a)图 3( b)左影像右影像同名影像对的提取和匹配结果( 正飞)分析表 1 实验结果，可得出如下结论。1)当影像像 幅 在 75 像 素 115 像 素 至 375( a)图 4左影像( b)右影像像素 575 像 素 之 间 时，串行算法比并行算法更 快。这是由于在对影像分块处理时需要进行降采 样操作，并在降采样的影像上提取和匹配特征点、 计算单应矩阵以及估计原始像对的重叠区域，这 些过程都耗费了一定时间。当影像较小时所获得 的加速效果还不足以抵消以上操作所造成的时间 消耗。2) 随着影像像幅逐渐增大，所获得的加速效 果不仅可以弥补以上操作所造成的时间消耗，出现并行版本算法比串行版本算法更快的情况，而且分块与不分块两种并行版本算法对串行版本算 法的加速比呈现出较快的增长趋势。同名影像对的提取和匹配结果( 反飞)3 2SIFT 特征提取和匹配加速性能对比实验选取由 UCD 航摄相机获取的一对立体 像对，每张影像大小为 7 500 像素 11 500 像素。通过对该立体像对进行降采样获得不同像幅大小 的立体像对，并对这些立体像对分别进行串行、基 于 GPU 并 行 但 不 分 块、基 于 GPU 并 行 且 分 块 3 种不同方式的 SIFT 特征点提取和匹配，并记录各 自运行时间。分 别 统 计 基 于 GPU 分 块 和 不 分 块 情况下算法耗时与相应串行算法耗时的比值，具 体结果如表 1 所示。表中，“ ”表示因影像幅面 过大使得运算数据量超出计算机存储空间限制导 致程序无法正常执行; “O”表示像幅幅面未超过 分块的要求，即程序实际计算过程中未进行分块， 故不作统计; “N”表示在相应串行或者并行算法 未执行情况下，加速比的值无法计算。GPU 分块 的阈值表示当原始影像宽或高中较长一边的边长 大于阈值时，计算重叠区域过程中采用的降采样 图像尺寸应遵循规则: 保存原始图像的长宽比进 行等比缩小，且生产的降采样图像较长的一边长 度与阈值相等。3)影像像幅在 375 像素 575 像素至 975 像素 1 495 像素之间时，分块提取和匹配与不分块提取和匹配的处理速度大致相当。随着影像像幅 的增加，分块数也随之增加，对每一子块提取和匹 配都存在内存和显存间的数据传输，这个过程耗 费了一定时间。分块数增多就使得更多时间消耗 在数据传输 这 一 环 节 之 中，所以当像幅达到 675 像素 1 035 像素时起，随着影像像幅的增加出现 分块处理较不分块处理速度慢的情况。闸 旋，等: 一种基于分块策略的 SIFT 特征快速提取与匹配方法第 31 卷第 5 期509所以当影像像幅小于 375 像 素 575 像 素时，直接使用 CPU 串 行 版 本 算 法进行匹配即可; 当影像像幅在 375 像素 575 像素至 975 像素 1 495 像素之间，可使用不分块版本进行特征提取 和匹配; 当影像像幅大于 975 像素 1 495 像素时 就应该使用分块版本进行特征提取和匹配。2)通过对两组航摄数据进行区域同名像点 的提取，表明提出算法可用于实际摄影测量任务，能够实现对区域进行同名像点快速提取。3)应用 GPGPU 技 术 对 SIFT 特 征 提 取 与 匹配的实验结果，对改进和提高其他基于局部特征描述符的特征提取与匹配的运算效率也具有一定 的借鉴意义。3 3区域 SIFT 同名点自动提取根据基于 GPGPU 的面阵遥感影像分块 SIFT参 考 文 献:特征提取和匹配算法，这里基于该单像对匹配算法编写实现了提取整个测区区域 SIFT 特征点，两 两匹配并进行同名像点的转点，实现了整个区域 像点 SIFT 特征提取和匹配以及形成同名像点功 能的程序。使用该程序对两组航空摄影影像数据 进行了区域同名像点自动提取，具体测区区域数 据信息和程序运行结果如表 2 所示。1LINDEBEG T Edge Detection and idge Detection with Au-tomatic Scale SelectionJ International Journal of ComputerVision，1998，30( 2) : 117-154LOWE D G Object ecognition from Local Scale-Invariant FeaturesC7th International Conference on Computer Vi- sion Corfu，1999: 1150-1157LOWE D G Distinctive Image Feature Form Scale-InvariantKeypoints J International Journal of Computer Vision，2004，60( 2) : 91-110BAY H，TUYTELAAS T，VAN GOOL L SUF: Speeded23表 2 区域信息与同名点提取结果测区航带数影像格式单幅影像尺寸 /( 像素 像素)提取同名点数生成时间 / min4影像数up obust FeaturesC ECCV 2006417Berlin，2006: 404-76468210灰度彩色5 344 4 0085 616 3 744480 4422 037 993281705MIKOLAJCZYK K，SCHMID C A Performance Evaluation ofLocal DescriptorsJ IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27( 10) : 1615-1630YE K，SUKTHANKA PCA-SIFT: A More Distinctive epresentation for Local Image EscriptorCIEEE Proceed- ings of the Conference on Computer Vision and Pattern ecog- nition