一种无人机影像分块的亚像素角点快速检测算法

2012-12-27 06:41何海清
自然资源遥感 2012年4期
关键词:角点分块邻域

何海清

(武汉大学测绘学院,武汉 430079)

一种无人机影像分块的亚像素角点快速检测算法

何海清

(武汉大学测绘学院,武汉 430079)

为满足无人机(unmanned aerial vehicle,UAV)影像角点快速检测的需要,针对Harris角点检测算法提取的角点是像素级的、且存在定位不精确和计算效率低的问题,提出了一种改进的、适用于无人机影像的角点检测算法。该算法首先根据最近邻域和对角邻域方向相似像素点特征数目初步筛选角点;然后对无人机影像进行分块处理,进行Harris自适应角点检测;最后,利用加权最小二乘欧几里德距离实现了亚像素角点的快速精确定位。实验验证了该算法的有效性和可行性,所检测的角点分布均匀,显著提高了角点检测速度。

无人机(UAV)影像;Harris算法;角点检测;亚像素角点;欧几里德距离

0 引言

近年来,无人机(unmanned aerial vehicle,UAV)低空数字摄影测量(以下简称无人机航测)作为新兴的测量技术发展迅猛,在资源勘查、城镇建设、防灾减灾以及应急保障等方面发挥了重要作用。然而,无人机航测存在平台姿态不稳定、获取的影像数据量大等问题,这给影像数据后期处理带来了困难。在无人机影像内业处理中,像对间特征点的提取是数据处理的重要步骤之一。然而,由于单个测区无人机影像多达几百张甚至上千张,因此,全自动精确快速提取影像特征点是一项非常迫切的工作。国内外学者对影像特征点检测展开了广泛研究。目前,最为流行的是应用SIFT算法提取特征点,但该算法速度较慢,难于满足对无人机影像快速检测的需要。最具代表性且速度较快的角点检测算法有Moravec,Harris和SUSAN等算法,其中Harris算法最为常用[1]。然而,Harris提取的角点是像素级的,角点位置可能发生偏移,难于满足摄影测量精度要求;同时,在Harris角点提取中,由于模板卷积运算过多,计算量大,难于满足无人机航测大数据量快速处理的需求。为此,许多学者对Harris算法进行了改进,并将其应用到遥感数据处理中。具有代表性的有Mikolajezyk等人[2]提出的尺度与仿射不变性的Harris角点检测法;Rosten等人[3]提出的基于机器学习的Harris快速角点检测法;白瑞林等人[4]提出的X型靶标亚像素角点提取法;郭永芳等人[5]提出的Harris与MIC相结合的快速角点检测法;王崴等人[6]提出的通过统计像素点八邻域相似的像素点数目剔除非角点的Harris算法;杨常清等人[7]采用改进的Harris算法进行航空影像自动配准;王志强等人[8]通过Harris角点预处理加快航空影像镶嵌中特征点检测速度,等等。但上述改进的Harris角点检测方法不能同时兼顾提取的亚像素精度及算法的高效率,从而难于满足无人机航测中角点精确、快速检测的需要。

本文针对Harris角点检测算法存在的定位不精确等问题,并为实现Harris算法在无人机影像处理中自动精确快速的角点检测,通过角点初筛选,剔除无人机影像中较为平滑区域的非角点和伪角点,然后对影像进行分块处理,利用最小二乘加权法来修正Harris初始角点坐标,从而实现无人机影像亚像素角点精确快速定位。实验表明,该方法在无人机影像角点检测中具有较强的实用性。

1 Harris角点检测算法

Harris角点检测算法[1]是 Harris和 Stephens通过对Moravec角点检测算法[9]进行改进后提出的。Moravec算法不能准确提取全部角点,对孤立像素点、噪声和边缘的强度变化较为敏感,角点不具有旋转不变性[10]。Harris角点检测算法改进了Moravec算法的上述不足,利用微分算子计算像素点在任意方向上的灰度变化,当目标像素点的角点响应函数值CRF(corner response function)大于设定的阈值时,则把该像素点视为角点。在Harris算法中,像素点I(x,y)灰度变化表示为

式中:u,v分别为 X,Y方向上的邻域范围;wu,v=exp[-(u2+v2)/2σ2]为高斯滤波。

式(1)还可表示为

式中M为图像X,Y方向上与梯度自相关函数相联系的矩阵,表示为

式中:Ix,Iy分别为图像X,Y方向的一阶梯度。若自相关矩阵M的2个特征值(α,β)都相对较大,则把该像素点视为角点。为了更好地检测角点,采用角点响应函数值CRF来确定角点,计算式为

式中:det M=α β;tr M=α +β;k为常数项,其取值范围为0.04~0.06。设定CRF阈值并执行非极大值抑制,当CRF大于设定阈值时,则把该像素点视为角点。

2 改进的Harris角点检测算法

Harris算法虽然具有简单高效、检测角点稳定等特点,但角点检测仅为像素级,无法到达亚像素级,因此难于满足角点定位精度要求较高的摄影测量需要。且由于无人机影像上角点特征明显的地物常分布不均匀,检测到的角点可能出现聚簇现象。为此,本文通过影像分块的亚像素检测方法来改进Harris角点检测。

采用影像固定数分块的原则进行角点检测,以确保整个影像区域角点分布均匀,可减少摄影测量中匹配误差,提高无人机影像相对定向外方位元素的解算精度,同时分块处理过程中可及时释放内存,减少计算机负担,提高效率。

为尽量避免非角点和伪角点参与角点检测运算,以减小数据冗余,在Harris运算前,对具有代表性的L型、Y型、T型、Arrow型和X型5种类型的角点进行初筛选。5种不同类型的角点如图1所示。

图1 5种不同类型的角点Fig.1 5 types of corners(L,Y,T,Arrow,X)

以各影像块标准差作为自适应阈值,对像素点周围8邻域依图2的最近邻和对角线方向进行相似像素点数筛选,统计角点、边缘及平滑区域相似像素点个数(表1)。

图2 相似像素筛选Fig.2 Similar pixels screening

表1 相似像素个数统计Tab.1 Number of similar pixels

由表1可知,在最近邻、对角线方向的角点都满足相似像素点数≤2,而在最近邻、对角线方向的孤立像素点相似像素点数都为零。因此,本文设定角点初筛选条件为像素点周围8邻域最近邻、对角线方向都满足0<NUM≤2。此筛选方法虽然可能会导致部分角点漏检,但对于无人机影像而言,分布合理、数量足够的角点即可满足影像匹配需要。

本文在传统Harris算法的基础上,充分顾及CRF极大值附近像素点的影响,以CRF非极大值抑制得到的角点作为初始角点,然后,将其作为中心像素在周围5×5模板范围内搜索角点簇(图3),利用最小二乘欧几里德距离原理,并以各像素点的CRF作为权重,求解角点精确的亚像素坐标。欧几里德距离D表达式为

图3 5×5模板亚像素角点定位Fig.3 Sub-pixel location within 5×5 template

式中:矩阵 X 为[x-x1,y-y1,…,x-xn,y-yn];权矩阵P为Diag(p1,p2,…pn),各项权计算公式为即权值为第i个元素与角点簇中所有元素CRF总和的比值。

根据最小二乘原理求解亚像素角点坐标(x,y)为

式中(xi,yi)为模板范围内角点簇的第i个像素点。

本文无人机影像分块的亚像素角点检测流程如图4所示。

图4 本文方法技术流程Fig.4 Flow chart for the method

3 实验结果及分析

为了验证本文改进的Harris算法在无人机影像角点检测中的精度和效率,选取灰度分布不均匀且差异较大,具有代表性的2幅无人机机载相机Cannon EOS 5D MarkⅡ获取的5616×3744像幅大小的影像为实验影像(图5)。

图5 2幅实验影像Fig.5 2 test images

采用传统的Harris算法、8邻域改进的Harris算法[6]以及本文算法对实验影像进行角点检测,以固定影像块数作为单元分块进行实验,通过VC++编程实现角点检测,其结果如图6—图8所示。

图6 传统Harris角点检测结果Fig.6 Results of traditional Harris corner detection

图7 8邻域改进的Harris角点检测结果Fig.7 Results of improved Harris corner detection by eight neighborhood pixels

图8 本文方法角点检测结果Fig.8 Results of the method for corner detection

从3种方法的角点检测结果对比可知,传统Harris算法检测到的角点含有大量的伪角点,且有些角点定位有偏差;8邻域改进的Harris算法虽然减少了伪角点,但检测出的角点分布不均匀,漏检的角点相对较多;本文检测方法在含有建筑物的区域检测到的角点簇明显减少,而在平滑区域检测到的角点增加,漏检的角点较少,整个图像区域角点分布均匀,有利于减小影像后期的匹配误差,同时,角点达到了亚像素级,检测精度大为提高。

通过最近邻、对角线方向相似像素特征初筛选角点后,像素点减少了近80%(图8),剔除了大量的非角点,极大地减少了数据的冗余度。由于一次乘法运算时间要远长于一次加法运算[6],因此初选角点主要采用加法运算,这样在初筛选角点后可避免大量乘法运算,使改进后的角点检测效率得到显著提高。为了便于比较,在传统Harris算法、8邻域改进的Harris算法和本文方法设置相同角点响应函数非极大值抑制阈值情况下,经本文改进的角点检测算法所耗时间分别仅为传统Harris算法和8邻域改进算法的8.8%和28.3%。显然,本文方法在无人机影像角点精确快速定位方面具有很强的实用性。角点的定位精度和计算效率。该方法在角点检测前,通过最近邻和对角线方向相似像素点的特征初筛选角点;对影像分块处理,自适应设定阈值,以实现Harris角点定位;利用角点簇加权最小二乘欧几里德距离完成亚像素角点定位。通过对无人机影像的角点检测实验,表明该方法检测角点可实现亚像素定位精度,算法简单高效,可明显减少计算量,显著提高了检测效率;检测的角点分布更为均匀,大大提高了Harris算法在无人机影像角点检测中的实用性,可满足无人机影像大数据量角点精确快速检测需要。

4 结论

本文对传统的Harris算法进行了改进,提高了

[1]Schmid C,Mohr R,Bauckhage C.Evaluation of Interesting Point Detectors[J].International Journal of Computer Vision,2000,37(2):151-172.

[2]Mikolajezyk K,Schmid C.Scale & Affine Invariant Interest Point Detectors[J].International Journal of Computer Vision,2004,60(1):63-86.

[3]Rosten E,Porter R,Drummond T.Faster and Better:A Machine Learning Approach to Corner Detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence(TPAMI),2010,32(1):105-119.

[4]白瑞林,李 杜,赵晶晶,等,一种实用的X型靶标亚像素角点提取方法[J].光学技术,2010,36(4):560 -565.Bai R L,Li D,Zhao J J,et al.A Practical Method for Detection of Sub - pixel Corners for X - target[J].Optical Technique,2010,36(4):560-565(in Chinese with English Abstract).

[5]郭永芳,于 明,孙以材.一种改进的快速角点检测方法研究[J].计算机工程与应用,2011,47(12):159 -161.Guo Y F,Yu M,Sun Y C.Study on Advanced Rapid Corner Detection Method[J].Computer Engineering and Applications,2011,47(12):159 -161(in Chinese with English Abstract).

[6]王 崴,唐一平,任娟莉,等.一种改进的Harris角点提取算法[J].光学精密工程,2008,16(10):1995 -2001.Wang W,Tang Y P,Ren J L,et al.An Improved Algorithm for Harris Corner Detection[J].Optics and Precision Engineering,2008,16(10):1995 -2001(in Chinese with English Abstract).

[7]杨常清,王孝通,徐晓刚,等.基于特征空间的航空影像自动配准算法[J].测绘学报,2005,34(3):218 -222.Yang C Q,Wang X T,Xu X G,et al.Automatic Registration of Aerophotos Based on Feature Space[J].Acta Geodaetica Et Cartographica Sinica,2005,34(3):218 -222(in Chinese with English Abstract).

[8]王志强,程 红,孙文邦,等.一种基于特征的航空遥感影像自动镶嵌方法[J].计算机与现代化,2009,12:85 -88.Wang Z Q,Cheng H,Sun W B,et al.A Method of Aerial Remote Sensing Image Automatic Mosaics Based on Feature[J].Computer and Modernization,2009,12:85 -88(in Chinese with English Abstract).

[9]Moravec H P.Towards Automatic Visual Obstacle Avoidance[C]//Proceedings of International Joint Conference on Artificial Intelligence.Cambridge,MA:William Kaufmann,USA:1977:584-590.

[10]张小洪,李 博,杨 丹.一种新的Harris多尺度角点检测[J].电子与信息学报,2007,29(7):1735 -1738.Zhang X H,Li B,Yang D.A Novel Harris Multi-scale Corner Detection Algorithm[J].Journal of Electronics& Information Technology,2007,29(7):1735 -1738(in Chinese with English Abstract).

A Rapid Sub-pixel Corners Detection Method for UAV Image Based on Image Block

HE Hai-qing
(School of Geodesy and Geomatics,Wuhan University,Wuhan 430079,China)

A rapid sub-pixel corners detection method based on image block for UAV(unmanned aerial vehicle)image is proposed with the purpose of improving the pixel level precision of corners location and the efficiency in Harris algorithm.With this method,we can screen corners by similar pixels in nearest and diagonal neighborhood direction,carry out Harris corners detection by auto-adaptive threshold based on image block,and then refine the initial corner by traditional Harris algorithm from the Euclidean distance between corners cluster and ideal corner by the least square method with weight.Tests show that the method is effective and practical for UAV image corners detection,and can improve Harris corners detection process speed greatly due to the reduction of the computation and also make corners well distributed.

UAV(unmanned aerial vehicle)image;Harris algorithm;corner detection;sub-pixel corner;Euclidean distance

TP 75

A

1001-070X(2012)04-0021-05

2012-02-23;

2012-04-26

国家863计划资助项目(编号:2009AA12Z311)、精密工程与工业测量国家测绘地理信息局重点实验室基金项目(编号:PF2011-11)和中央高校基本科研业务费专项基金项目共同资助。

10.6046/gtzyyg.2012.04.04

何海清(1983-),男,博士研究生,主要从事地形变形监测、灾害预报及无人机应用等研究。E-mail:hyhqing@163.com。

(责任编辑:刁淑娟)

猜你喜欢
角点分块邻域
面向量化分块压缩感知的区域层次化预测编码
基于混合变邻域的自动化滴灌轮灌分组算法
钢结构工程分块滑移安装施工方法探讨
多支撑区域模式化融合角点检测算法仿真
关于4×4分块矩阵的逆矩阵*
角点检测技术综述①
基于灰度差预处理的改进Harris角点检测算法
尖锐特征曲面点云模型各向异性邻域搜索
懒交互模式下散乱不规则分块引导的目标跟踪*
基于FAST角点检测算法上对Y型与X型角点的检测