基于SIFT和三角网格的VHR建筑物检测技术
«上一篇
文章快速检索     高级检索
下一篇»
  应用科技  2017, Vol. 44 Issue (6): 48-52  DOI: 10.11991/yykj.201610001
0

引用本文  

白鹤, 郑丽颖. 基于SIFT和三角网格的VHR建筑物检测技术[J]. 应用科技, 2017, 44(6), 48-52. DOI: 10.11991/yykj.201610001.
BAI He, ZHENG Liying. Building detection from VHR based on SIFT and Delaunay triangulation[J]. Applied Science and Technology, 2017, 44(6), 48-52. DOI: 10.11991/yykj.201610001.

基金项目

国家自然科学基金项目(61771155)

通信作者

郑丽颖,E-mail:zhengliying@hrbeu.edu.cn

作者简介

白鹤(1991−),男,硕士研究生;
郑丽颖(1976−),女,教授

文章历史

收稿日期:2016-10-25
网络出版日期:2017-04-28
基于SIFT和三角网格的VHR建筑物检测技术
白鹤, 郑丽颖    
哈尔滨工程大学 计算机视觉与听觉实验室,黑龙江 哈尔滨 150001
摘要:传统尺度不变特征变换(scale-invariant feature transform,SIFT)算法的误配准问题导致基于该算法的建筑物检测率较低,因此提出一种改进的高分辨率(very high resolution,VHR)遥感卫星图像中建筑物的检测方法。首先通过改进传统的SIFT配准方法,使其能够更加准确地描述VHR遥感卫星图像中的建筑物信息,之后通过欧氏距离获得2幅图像的初始匹配点集,然后将配准后的一幅图像中所得到的配准点作为Delaunay三角剖分的初始点集,根据Delaunay三角剖分特性,剔除SIFT算法中误匹配的特征点,得到最终的结果。实验结果表明,研究所提出的算法可以有效地检测出一幅VHR遥感卫星图像中的建筑物信息,在时间效率、配准精度、建筑物的检测普遍性上,都能得到很好的预期效果。
关键词遥感图像    建筑物检测    SIFT算法    关键点    欧氏距离    Delaunay三角剖分    匹配点    配准精度    
Building detection from VHR based on SIFT and Delaunay triangulation
BAI He, ZHENG Liying    
Computer Vision and Audition Lab, Harbin Engineering University, Harbin 150001, China
Abstract: The mis-registration problem of traditional scale-invariant feature transform (SIFT) algorithm results in a low detection rate of buildings based on this algorithm. Therefore, this paper proposed an improved detection method of buildings in very high resolution (VHR) satellite imagery. First, the traditional SIFT registration method was improved to characterize the building information in VHR remote sensing satellite images. Then, the set of initial matching points of two images could be obtained with Euclidean distance, followed by taking matched registration points in an image as the initial point set of the Delaunay triangulation. Finally, the result was got by removing mismatched feature points according to Delaunay triangulation properties. Experimental results show that the algorithm proposed in this paper can effectively detect the building information in a VHR remote sensing satellite image. Moreover, the proposed algorithm performs well in terms of time efficiency, registration accuracy and universality in detection of buildings.
Key words: remote sensing image    building registration    SIFT algorithm    key points    Delaunay triangulation    Euclidean distance    matched points    registration accuracy    

近些年,随着高分辨率(very high resolution,VHR)遥感卫星图像获取的分辨率不断提高,建筑物的识别和检测成为研究热点。目前大量的VHR遥感卫星图像检测的研究工作主要集中在机场、桥梁等图像的提取与检测上,VHR中建筑物的主要特点是反射较强,灰度值要比背景高[1]。对于建筑物这一类目标检测尚没有足够多的文献描述,但与建筑物检测的相关技术不胜枚举[2]。雷小群等[3]依据传统SIFT算法在遥感影像配准应用中存在的不足,从特征点匹配精度上进行了改进,然后利用匹配点对作为配准用控制点对,分别对不同时相、不同分辨率遥感影像进行仿射变换和小面元微分纠正配准,这一思想给本文提供了很好的思路。Chao Tao等[4]提出的使用聚集的SIFT特征点和区域信息检测遥感卫星图像中的机场区域取得了很好的实验结果。而Mahdi Amiri等[5]提出的匹配局部图像兴趣点的保持旋转和尺度不变性的RASIM方法,可以很好地检测出目标图像中感兴趣区域。但是目前的配准和检测方法由于没有考虑图像的全局特性,普遍存在配准精度较低的问题[6]

针对VHR遥感卫星图像中检测建筑物的问题,文中提出一种SIFT配准技术和Delaunay三角剖分算法相结合的检测方法。因为综合考虑了待检测建筑物的矩形边缘特性和与其他目标的差异性,使得文中算法检测精度大大提高,而且时间效率上也较为理想。

1 改进的SIFT算法

在图像的目标检测方面,提取图像的特征算子可以很好地描述目标的局部信息,而SIFT特征点提取方法是目前使用最为广泛的方法。传统的SIFT算法提取图像特征点的过程如下:

1)尺度空间极值点检测,以初步确定关键点位置和所在尺度;

2)通过拟合三维二次函数以确定关键点的位置和尺度,同时去除低对比度的关键点和不稳定的边缘响应点,以增强匹配稳定性,提高抗噪声能力;

3)利用关键点邻域像素的梯度方向、分布特性为每个关键点指出方向参数,使算子具备旋转不变性;

4)生成SIFT特征向量。

文中依据VHR遥感卫星影像中建筑物异于普通目标的重要特性,对传统的SIFT算法的参数信息描述方面加以改进。在待检测卫星图像中,图像边缘的颜色变化差异不大。根据SIFT算法的特点可知,这会导致当边缘四周提取的特征点足够多的时候,越靠近中心的区域提取的关键点越少。所以文中通过去除部分边缘响应,保留靠近中心的关键点可以更好地保留图像中的重要信息。

首先,通过高斯模糊来获得尺度空间。然后,用高斯金字塔表示尺度空间。因为尺度规范化的LoG (Laplacion of Gaussian)算子具有真正的尺度不变性,因此本文通过LoG算子检测尺度空间的关键点。最后,通过拟合三维二次函数来确定关键点的位置和尺度,同时去除低对比度的关键点和不稳定的边缘响应点,以增强匹配稳定性、提高抗噪声能力。

本文通过实时调整SIFT参数剔除不稳定的边缘响应点。考虑到在滤除边缘响应阶段,传统的SIFT算法会消除目标区域邻近中心的关键点,因此通过加入“中心因子”的方法,平衡这种误删除操作,降低误配准率,具体算法如下。

获取特征点处的Hessian矩阵,主曲率通过一个2×2的Hessian矩阵H求出:

${H} = \left[ {\begin{array}{*{20}{c}}{{D_{xx}}} & {{D_{xy}}}\\{{D_{xy}}} & {{D_{yy}}}\end{array}} \right]$

式中Dxx表示DoG金字塔中某一尺度的图像x方向求导2次。

D的主曲率和H的特征值成正比,令α为最大特征值,α为最小特征值,则

$\alpha = r\beta $
$\frac{{{\rm{Tr}}{{(H)}^2}}}{{{\rm{Det}}(H)}} = \frac{{{{(\alpha + \beta )}^2}}}{{\alpha \beta }} = \frac{{{{(r + 1)}^2}}}{r}$ (1)
${\rm{Tr}}(H) = {D_{xx}} + {D_{yy}}$ (2)
${\rm{Det}}(H) = {D_{xx}} \times {D_{yy}} - {D_{xy}} \times {D_{xy}}$ (3)

式(1)在2个特征值相等时达到最小,而随着r的增长而增长,实验发现,r取7~8较合适。式(2)表示矩阵H对角线元素之和,式(3)表示矩阵H的行列式。

$\frac{{{\rm{Tr}}{{(H)}^2}}}{{{\rm{Det}}(H)}} < \frac{{{{(r + 1)}^2}}}{r}$ (4)

当式(4)成立时,将关键点保留,反之则剔除。

通过观察建筑物的俯视图发现,越靠近图像的几何中心点,图像表面越平滑,提取的特征点也越少,而在滤除边缘响应阶段也会或多或少地消除临近中心的关键点,所以文中通过加入中心因子的方法,平衡这种误删除操作,如式(5)所示。

$\frac{{{\rm{Tr}}{{(H)}^2}}}{{{\rm{Det}}(H)}} < \left( {\frac{{{{(r + 1)}^2}}}{r} + \frac{K}{{{\rm{Point}}(x,y)}}} \right)$ (5)

式中:

${\rm{Point}}(x,y) = \sqrt {{{{\rm{(}}{P_{c{\rm{,}}x}}{\rm{ - 90)}}}^{\rm{2}}} + {{{\rm{(}}{P_{c{\rm{,}}y}}{\rm{ - 30)}}}^{\rm{2}}}} $

式中:K为中心因子系数,取值范围为(0.00<K≤2.00), ${P_{c{\rm{,}}x}}$ ${P_{c{\rm{,}}y}}$ 分别是关键点的横坐标与纵坐标,而90和30是文中选取的参考图像像素值。

2 基于三角剖分技术的误匹配剔除方法

通过三角剖分算法,将遍布在图像中的关键点连接成三角形网格,最后形成一个凸多边形大网格[7],可以很好地弥补SIFT算法的缺陷,达到精确检测的目的。

2.1 Delaunay简介

Delaunay三角剖分是将空间点连接为三角形,使得所有三角形中最小角最大的一个技术。Delaunay三角剖分算法主要用于数字地形建模中,不规则三角网(TIN)通过不规则分布的数据点生成的连续三角面来逼近地形表面[8]。迄今为止出现了不少成熟的Delaunay三角剖分法,如分割−合并算法、逐点插入法以及三角网生长法等[9]。目前国内外多数的研究主要集中在逐点插入算法和分治算法两个方面[10]

文中选取的是逐点插入法,它不仅时间效率较高(最坏时间复杂度的O(N2),平均时间复杂度的O(N3/2)),而且占用空间较小[11],综合考虑,性价比最高且应用也最为广泛[12]

2.2 应用Bowyer-Watson算法剔除误匹配

文中采用的Bowyer-Watson算法就是逐点插入算法的一种,建筑物的俯视图的配准到的特征点大多集中在边缘,越向中心靠近,特征点越少(越靠近中心越平滑,特征点越少),所建的三角网格会大量聚集到图像的边缘处,所以文中为了尽可能地运用三角网格域中的三角形的边长信息,应用Bowyer-Watson算法的点−边−三角形(即所谓的Quad_Edge结构)数据结果构建三角网,这样,明确边的数据结构的设计,可以使与边有关的属性的存储和维护更为方便,当计算三角形的边长信息时,也变得更为方便,而且三角网间的拓扑关系也会更加明确。Bowyer-Watson算法的主要步骤如下。

1)建立初始三角网格。针对给定的点集V,找到一个包含该点集的矩形R, 称R为辅助窗口。连接R的任意一条对角线,形成2个三角形,作为初始Delaunay三角网格。

2)逐点插入。假设目前已经有一个Delaunay三角网格T,现在在它里面再插入一个点P,需要找到该点P所在的三角形。从P所在的三角形开始,搜索该三角形的邻近三角形,并进行空外接圆检测。找到外接圆包含点P的所有的三角形并删除这些三角形,形成一个包含P的多边形空腔,称之为Delaunay空腔。然后连接P与Delaunay腔的每一个顶点,形成新的Delaunay三角网格。

3)删除辅助窗口R。重复步骤2), 当点集V中所有点都已经插入到三角形网格中后,将顶点包含辅助窗口R的三角形全部删除[9]

文中把辅助窗口R设置为参考图像和待配准图像块的外边框。为了减少时间上的花费,文中将SIFT算法配准后得到的关键点坐标存储在struct结构体中,并依据横坐标将其排序,而三角网格域的每一个顶点就是改进的SIFT算法所得到的配准点。

图12所示,若A点和A'点分别对应于SIFT算法配准后所得到的相匹配的关键点,在图像块1中,与A点相关联的三角形有△ABC、△ACD、△ADE,在图像块2中,与A'点相关联的三角形有△A'B'C'、△A'C'D'、△A'D'E',在图像块1中的任何一块三角形就会遍历图像块2中的所有三角形,并通过三角形的相似性,将含有A点的三角形重点标识出来,最后比较图像块1中含有A点的所有三角形是否与图像块2中含有A'点的所有三角形是否“匹配”。文中将“匹配”的标准设置为,2个三角形集中包含的所有三角形的总长度是否满足公式(6)所示的阈值要求。

图 1 图像块1中的三角网格域
图 2 图像块2中的三角网格域
$T = \frac{{C_{ABC}^{} + {C_{ACD}} + {C_{ADE}}}}{{C_{A'B'C}^{} + {C_{A'C'D'}} + {C_{A'D'E'}}}}$ (6)

式中:T表示匹配阈值,而C表示三角形的周长。

3 改进的建筑物检测方法

文中实验的整体流程图如图3所示。

图 3 实验流程

首先,文中将待检测图像输入到程序中,通过手动调整待匹配的图像窗口,将移动的窗口均匀地向右移动检测建筑物图像像素的1/4,而向下将移动的窗口均匀地移动检测建筑物图像像素的1/3。接下来在模拟图像数据的多尺度特征过程中,文中图像的尺度空间L(x, y, σ)定义为一个变化尺度的高斯函数L(x, y, σ)与原图I(x, y)的卷积。

$L(x,y,\sigma ) = G(x,y,\sigma ) * I(x,y)$

式中*表示卷积运算。

式中:mn表示的是高斯模板的维度(维度由(12σ+2确定),(xy)代表图像的像素位置,σ是尺度空间因子,将尺度空间因子增大,在一定程度上可以更加详细地描述图像的总体特征。文中经过实验发现,对于建筑物的配准,将图片的初始尺度定为0.7~0.9较合适。

求得2幅图像(参考图像和待检测图像块中的图像)的欧式距离后,可以获得初始匹配集。文中通过Bowyer-Watson算法构建参考图像和待配准图像块中的图像的三角网格。当参数T选取较低时,剔除错匹配效果不是很明显,所以我们取0.8≤T≤1.2,最终可以得到建筑物检测结果。使用opencv的cvLine绘图函数将待检测的一类建筑物分别标识出来。

4 实验结果与分析 4.1 实验环境与图像来源

基于pentium Duel-core CPU,主频为2.1 GHz和内存为2 GB的主机,采用VC6.0实验开发环境,并结合opencv计算机视觉库,开发语言采用C语言。所选择的高分辨率遥感卫星图像是谷歌地图中截取的大量高清建筑物图像,分辨率是2 560 ppi×1 440 ppi,定位精度为2 m。

4.2 参数K对算法的影响

文中研究了50个样本的剔除错匹配结果,实验结果如图4所示。K值的选取,文中的定义是0~5,而当K>2时,剔除错匹配的效果会大大降低,所以图4中,K值只取到1.35,随着K值越靠近1,剔除的匹配点越多,剔除的误匹配点也会越多,但两者只是存在正相关关系。

图 4 K阈值的选取与SIFT匹配特征点的错匹配点的剔除关系
4.3 三角网格实验与分析

应用Bowyer-Watson算法可以将改进的SIFT算法配准后得到的关键点进行三角网格化,实验结果如图5所示。

Bowyer-Watson算法所要求输入的特征点较少,当构建建筑物的三角网时,不会出现交叉的情况,反之使用该算法就有可能使生成的三角网出现交叉现象。因为文中的建筑物图像较小,而且改进的SIFT的特征点不会产生大量离散的现象,所以构建的三角网较为均匀。

图 5 建立三角网格域
4.4 算法对建筑物配准的有效性分析

在遥感图像中,目标配准方法的基本评估指标有:检测率P与误检率Q。文中将配准到的正确目标数定义为x,配准到的错误目标数定义为y,实际的目标数定义为z,则配准率定义为

$P = x/z$ (7)
${\rm{Q}} = y/z$ (8)

由式(7)、(8)可知,配准率越接近1,误检率越接近0,表明配准方法的性能越好。文中分别对比了传统的SIFT算法,SURF以及文中所提出的算法与Bowyer-Watson算法相结合配准建筑物的性能,实验结果如图6~8所示。

图 6 SIFT+Bowyer-Watson算法配准结果
图 7 SURF+Bowyer-Watson算法配准结果
图 8 改进的SIFT+Bowyer-Watson算法配准结果

3种配准算法的结果分析如表1所示。对50幅图像的配准结果表明,文中所提出算法与Bowyer-Watson相结合的配准率为91.87%,传统SIFT与Bowyer-Watson相结合的配准率为81.25%,SUFT与Bowyer-Watson相结合的配准率为75.63%。建筑物区域与停车场、过街天桥较为类似,配准结果会有一定的误检率,文中所提出的算法与Bowyer-Watson相结合误检率为6.25%,相较于其他与Bowyer-Watson结合的算法,误检率最低。实验结果表明了文中算法对于住宅区域的建筑目标配准具有有效性,且算法执行速度快,便于实际工程应用。

表 1 配准结果对比
5 结论

本文研究了VHR遥感卫星图像目标的检测技术,提出了在滤除边缘响应阶段加入“中心因子”,将SIFT算法与三角网格技术相结合的改进算法。结果表明:1)通过与Delaunay三角剖分算法相结合,构建的三角网较为均匀;2)改进的SIFT算法可以减少误检目标,效果优于传统的SIFT算法和SURF。因此,本文提出的改进的SIFT算法更加适合描述VHR图像中建筑物的矩形信息,可以更好地配准建筑物目标信息。

参考文献
[1] 杨益军, 赵荣椿, 汪文秉. 航空图像中人工建筑物的自动检测[J]. 计算机工程, 2002, 28(8): 20-22. (0)
[2] HUA Tao, ZHAO Yong. An novel location technology based on SIFT features matching[J]. Journal of astronautic metrology and measurement, 2014, 125(1): 3385-3388. (0)
[3] 雷小群, 李芳芳, 肖本林. 一种基于改进SIFT算法的遥感影像配准方法[J]. 测绘科学, 2010, 35(3): 143-145. (0)
[4] TAO Chao, TAN Yihua, CAI Huajie, et al. Airport detection from large IKONOS images[J]. IEEE geoscience and remote sensing letters, 2011, 8(1): 128-132. (0)
[5] RASIMMAHDI A, RABIEE H R. RASIM: a novel rotation and scale invariant matching of local image interest point[J]. IEEE geoscience and remote sensing letters, 2011, 20(12): 3580-3591. (0)
[6] 刘佳, 傅卫平, 王雯, 等. 基于改进SIFT算法的图像匹配[J]. 仪器仪表学报, 2013, 34(5): 1108-1112. (0)
[7] 丁永祥, 夏巨湛, 王英, 等. 任意多边形的Delaunay三角剖分[J]. 计算机学报, 1994, 17(4): 270-275. (0)
[8] 万琳. 基于三角网格的图像表示方法研究[D]. 武汉: 华中科技大学, 2009: 1-92. (0)
[9] 田军委, 程钢. 改进Delaunay三角剖分算法[J]. 西安工业大学学报, 2011, 31(4): 334-338. (0)
[10] 基于Bowyer-Watson三角网生成算法的研究[J]. 计算机工程与应用, 2013, 49(6): 198-200. (0)
[11] 贺强, 张树生, 白晓亮, 等. 基于邻域相似性的三角网格光顺算法[J]. 计算机科学, 2010, 37(3): 289-291. (0)
[12] 时永杰, 宋杰, 徐丹. 基于等边三角形网格化的二维图像变形[C]//中国计算机图形学大会. 昆明, 中国, 2012: 139-145. (0)