一种预判随机抽样算法在像控点测量中的应用

陈尔东昊,黄磊(1.重庆数字城市科技有限公司,重庆 400020; 2.重庆市地理信息云服务企业工程技术研究中心,重庆 400020; .重庆市勘测院,重庆 400020)

一种预判随机抽样算法在像控点测量中的应用

陈尔东昊1,2∗,黄磊3
(1.重庆数字城市科技有限公司,重庆 400020; 2.重庆市地理信息云服务企业工程技术研究中心,重庆 400020; 3.重庆市勘测院,重庆 400020)

摘 要:像控点测量是航空摄影测量工作中必不可少的环节。为有效适应现代化航空摄影测量技术对像控点测量的要求,本文基于预判参数模型,利用RANSAC函数对SIFT匹配算法进行改进,并采用Visual Studio C++和OpenCV组件进行算法实现。实验结果表明,将改进后的算法应用到实际的像控点测量工作当中,不但能为航空影像匹配、像控点快速定位提供有效支持,并且能提高像控点测量野外作业的生产效率。

关键词:SIFT算法;RANSAC;像控点测量;图像匹配

1　引 言

目前,为了适应现代化高效率的航空影像生产,各生产单位引进了一些集群式遥感影像处理系统。在航空摄影测量中,采用先进的IMU/ DGPS辅助航空摄影,可以在摄影的瞬间获取影像的内外方位元素。并且,在数字摄影测量中采用了机载POS(Position and Orientation System)系统测定定位、定向参数,从而获得带有POS信息的航空数字影像。通过实际研究发现,带有POS辅助的空中三角测量成果更容易满足各项规范精度要求,而且较大地减少了野外像控点的布设密度以及节省了人力、物力,有力地推动项目的进展。然而,这一革新却给现实作业中的野外像控点测量带来了新问题,如像控点布点比传统胶片航摄和不带POS的数码航摄稀疏了很多,像控点之间缺乏连续性和关联性,相邻像控点之间的距离又很远。作业人员既要快速地确定像控点的实地位置,又要能以较快的速度确定像控点点与点之间最方便和快捷的交通路线,以提高野外作业的生产效率。如何解决以上问题,成为现阶段像控点测量的瓶颈所在。

为此,本文选择利用SIFT算法进行影像匹配以及像控区域快速定位。并且,针对SIFT的高误匹配率,提出了一种基于预判参数模型的随机抽样一致算法对SIFT算子改进的航空影像匹配方式,并将其应用到野外像控实际测量工作当中。

2　SIFT影像匹配

SIFT为“尺度不变特征转换(Scale-invariant feature transform,SIFT)”的简称,是一种对尺度、旋转、仿射以及亮度变化都有很好的不变性的特征[1～3]。SIFT算法实现图像之间的匹配主要包含了“尺度空间关键点定位”、“指定关键点方向参数”、“生成SIFT特征描述子”、“特征点对预匹配”4个步骤。

2.1尺度空间关键点定位

首先,在尺度空间中检测极值点。尺度空间理论的目的是模拟图像数据的多尺度特征,SIFT算法使用的是实现尺度变换的唯一线性核——高斯卷积核。将相邻尺度的图像进行差值运算从而得到一组高斯差分面DoG(Difference of Gaussian)图像[4]。在计算出高斯差分平面之后,对于其中的某一点,将它与周围的8个近邻点以及上下相邻尺度的对应位置的9×2个近邻点(共26个点)进行比较,如果这一个点都大于或者小于这26个点,那么该点就被选取出来作为极值点。

对于确定的极值点,利用Taylor公式展开式和Hessian矩阵进行辅助,从而获得关键点位置,并提高其在图像中的位置级空间尺度上的精度。

2.2指定关键点方向参数

SIFT利用关键点邻域像素的梯度方向分布特性为每一个关键点指定方向参数,使算子具备旋转不变性。SIFT用以关键点作为圆心的高斯加权窗口来对梯度模值进行加权。通过对梯度方向的直方图统计之后,将峰值处关键点的邻域梯度方向作为主方向,并取最大值80%以内的方向作为辅助方向[5],从而得到该关键点的方向。

2.3生成SIFT特征描述子

通过以上步骤,确定了关键点的尺度、位置以及方向,确保了其尺度缩放不变性及旋转不变性。Lowe[6]建议将每个关键点为中心的像素点划成4个4×4的小区域,每个小区域由对应的8个方向的梯度模值表示。因此,最终特征向量为:4×4×8 =128维的,这就是所生成的特征描述子。

2.4特征点对预匹配

利用对K-D tree改进后的最优接点优先(BBF)搜索算法[7]增快特征点的搜索速度。根据特征点的最邻近特征向量和次邻近特征向量的欧式距离比来获取预匹配点对。本文经过实验发现,当距离小于0.4时,可认为该特征点匹配对为有效的,并且距离比阈值决定了匹配点对的数量和质量。

特征点对预匹配并不能标志着算法的结束,因为SIFT算法在匹配的过程中会产生大量的错误匹配点,为了更好地获得匹配效果,往往会采用其他算法进行改进。本文采用带预判参数的随机抽样一致算法进行错误匹配点剔除,以矫正匹配效果。

3　利用预判RANSAC改进SIFT算法

3.1RANSAC算法介绍

RANSAC(Random Sample Consensus)算法[8],又称随机抽样一致算法,每次随机抽取出多个数据来确定模型参数,再根据估计参数对所有数据进行分类。当数据在该参数模型允许的误差范围之内,称之为内点,反之则为外点。该算法对错误率超过50%的数据仍能够进行处理,是最有效的鲁棒估计算法之一。但是RANSAC对于航飞影像这种大数据处理效率较低,且本文需要尽可能大数据量地过滤掉无效数据,因此在RANSAC的模型参数检验前,加入了预判参数的过程,提高RANSAC算法的整体效率。

3.2预判改进的RANSAC的算法

本文主要利用RANSAC方法来剔除误匹配点对,从而减小SIFT特征提取算法所得到的误匹配点对图像模板匹配造成的干扰,从而提高匹配成功率。

首先设定初始的最佳内点数Ni为0,然后进行算法实现:

(1)从样本集中随机抽选一个RANSAC样本,即4个匹配点对(每个平面中任意3个点不共面),两平面间变换矩阵参数H可以根据4组点进行线性计算[9]。

(2)计算剩下(I-4)个特征点经过变化矩阵的坐标值与它预匹配点之间的距离,如下式:

dv=d(A′i,HAi)2

如果小于阈值,则认为该特征点匹配对为内点,否则就为外点。

(3)通过Ni与当前内点数的对比,如果当前点数＞Ni,那么就将H作为当前最佳矩阵估计,并更新Ni值。

(4)重复(1)～(3)继续进行多次迭代的随机抽样计算,并在内点数基本稳定时,选择内点最多、误差函数最小的变换矩阵参数为图像间的投影变换矩阵,这样的变换矩阵已经相对比较精确。可是,其迭代次数与正确模型确定无法获得,所以运行效率会不可控。

通过上述RANSAC算法实现在理论上可以得到理想效果的矩阵模型,但是由于RANSAC只有一定的概率得到可信的模型,并且其有着迭代次数没有上线的确定,为提高匹配效果,以对航飞影像的大数据量特征点进行快速匹配,就需要对匹配正确模型进行预判断。具体实现如下,将m表示为从匹配点中选取的一个内点的概率,如公式:m=内点数量/所有特征点

由于事先不知道m的值,因此假设选定n个点, 用w表示一些迭代过程中从数据集中机选取出的点均为内点的概率,k为迭代次数。mn是就是n个点都是内点的概率。1-mn表示估计出了一个模型不佳。(1 -mn)k表示永远不会选择到n个都是内点的概率,并与1-w相同,所以:1-w=(1-mn)k

由于结果的假设n都是独立选择的,所以被选出来的点还可能会被后面的迭代过程重新选到,所以此处的k值被认为是选取不重复点的上限。要想从数据中选择合适的匹配直线,RANSAC算法通过每次迭代选择2个点,并且这两个点都是不重复的,将标准偏差或者它的乘积加到k上,得到k的标准偏差的定义:

对于RANSAC获得可信模型的概率和标准偏差是成正比的,有了标准偏差k就可以获得理论上推断出来的迭代次数,从而可以预判断出相对正确的可信模型。有了预判而得的正确模型,就可以对RANSAC的参数阈值和数据迭代进行改进,并对SIFT的特征点匹配进行改进,不仅可以有效地去除图像间错误匹配点对,而且能估算出图像之间的透视变化矩阵参数,从而进一步确定匹配位置,实现流程如图1所示:

图1　匹配点获取流程图

4　改进后SIFT对像控点测量工作的应用

改进后算法基于Visual studio C++语言,并结合跨平台计算机视觉库OpenCV进行实现。本文利用改进后的SIFT算法实验了多张航片的像控点自动预选、像控点测量区域快速匹配等功能。

4.1改进后的SIFT算法匹配

本文采用重庆市某区域同一航带上的相邻两张1∶5 000航飞影像作为实验对象。此处通过对改进前后算法的匹配效果进行分析,并验证RANSAC改进后SIFT算法对航飞影像的匹配效果。

(1)首先利用原始SIFT算子进行影像匹配,匹配效果如图2所示:

图2　原始SIFT算子影像匹配结果

(2)改进后的SIFT算子进行影像匹配,匹配效果如图3所示:

图3　改进后SIFT算子影像匹配结果

(3)匹配精度分析

实验统计了两种算法提取的特征点数级匹配点数,并采用分区域抽样统计法对匹配正确率统计,抽取匹配区域占总匹配点数30%以上的样本数据,且在抽取样本时保证样本数据在匹配区域分布较为均匀,得到的统计结果如表1所示:

由于像控点测量工作所需要获得的是准确的定位位置,并利用更为准确的匹配点进行判定,因此本文方法在选择迭代与预判的时候会进行更为严格的筛选。如表1所示,在城镇地区与非城镇地区,利用改进后的算法进行严格筛选,剔除大部分无效点,并减少了无效迭代所产生的重复与错误匹配点,所得到的有效匹配点数仅占原始的16.7%和18.6%,且匹配正确率大大提升。

原始与改进后SIFT算子影像匹配精度比较 表1

通过实验对比分析,可以很容易地看出通过预判RANSAC对SIFT算法进行改进之后,匹配准确率得到了大幅提高。

4.2像控点测量快速定位

在影像匹配精度满足生产需求之下,本文在快速匹配定位基础上,进一步完善了像控点测量工作中的大数据量与多度重叠影像之间的快速定位。

首先,利用改进后SIFT算法进行相邻航空影像重叠区域匹配,如图4所示:

图4　获取重叠区域

其次,通过SIFT匹配获取目标像控点和当前像控点影像在大幅影像中的大致位置。目标像控点将会在相邻航空影像的重叠区域中选择,因此将相邻航片的重叠区域提取出来与工作区底图进行匹配,如图5所示:

图5　目标区域定位

最后,通过重复一、二步骤,获取当天预计目标像控点区域位置,并在匹配重叠区域中预选出像控点目标位置,如图6所示:

图6　像控点预选

在匹配获得当前像控点和目标点位置之后,可以快速定位目标像控点位置,为接下来像控点测量的选点和路径规划提供支持,提高了像控点测量的工作效率。

5　结 语

利用预判模型改进后的SIFT算法对像控点测量工作进行辅助,不仅解决了由于航空摄影测量技术发展所带来的像控点布点稀疏所造成的定位困难,而且能有效支持像控点选点与交通路径规划。该算法提高了野外像控点测点的生产效率,优化了工作模式。

本文的研究结果在一定程度上促进了像控点测量工作的进展。在接下来的研究中,将进一步加强利用异源影像辅助像控点测量的研究,并在路径规划基础上研究实现工作路径自动导航与人员实时定位功能等。

参考文献

[1] MORTENSEN E N,Deng Hongli,SHAPIRO L.A SIFT Descriptor with Global Context[C].Computer Vision and Pattern Recognition,IEEE Computer Society Conference,2005: 184～190.

[2] EGENHOFER M.IEEE Symposium on Visual Languagers [C].IEEE Computer Society,1996:60～67.

[3] BRUNELLI R,MICH O.Image retrieval by examples[J].IEEE Trans.Multimedia,2000,2(3):164～171.

[4] 夏杰,李奇安,李悦等.基于改进SIFT算法的图像匹配方法研究[J].电子设计工程,2012,20(14):157～159.

[5] 黄超,齐英剑.SIFT算法研究和应用[J].中国传媒大学学报:自然科学版,2012,19(1):68～72.

[6] Lowe,DG.Object recognition from local scale-invariant features[C].Proceedings of Imternational Conference on Computer Vision.Corfu,Greece:IEEE,2009:1150～1157.

[7] Beis J S,Lowe D G.Shape imdexing using approximate nearest - neighbour search in high - dimensional spaces [ C].Conference on Computer Vision and Pattern Recognition.Washington D C,USA:IEEE Computer Society,1997:1000 ～1006.

[8] Wang Wei,HongJun,TangYiping.Image matching for geomorphic measurement based on sift and RANSAC methods [C].International Conference on Computer Science and Software Engineering.Wuhan, Huber: IEEE,2008:317～320.

[9] 黄有群,付裕,马广焜.基于RANSAC算法的柱面全景图拼接方法[J].沈阳工业大学学报,2008,20(4):461～465.

Applications of Preview Random Sampling Algorithm at Photograph Control Point Survey

Chen Er-dong-hao1,2,Huang Lei3
(1.Chongqing Cybercity Sci-tech Co.,Ltd,Chongqing 400020,China; 2.Chongqing Enterprise Engineering Technology Research Center on Geographic Information Cloud Service,Chongqing 400020,China; 3.Chongqing Survey Institute,Chongqing 400020,China)

Abstract:Photograph control point survey is an essential part of aerophotogrammetry.In order to adapt to the requirement of modern technology of aerophotogrammetry,this paper used RANSAC function to improve SIFT algorithm on the basis of the anticipation parameter model,and used Visual Studio C++ and OpenCV components to implement the algorithm.the result shows that,applying the improved algorithm to the photograph control point survey can not only effectively support the aerial image matching and rapid positioning of photograph control point,but also improve the production efficiency of photograph control point survey in field operations.

Key words:SIFT;RANSAC;photograph control point survey;image matching

文章编号:1672-8262(2015)01-101-04中图分类号:P231

文献标识码:A

收稿日期:∗2014—08—28

作者简介:陈尔东昊(1988—),女,硕士,助理工程师,主要研究方向为地理信息系统应用、地理信息数据建库等。