An Improved Region-Growing Surface Triangulation Algorithm for Urban Dense Point Cloud
-
摘要: 随着飞行平台与传感器技术的发展,空间信息的获取能力逐渐增强,特别是低空倾斜摄影及其数据处理方法的出现,使得城市真三维信息的获取手段变得更加丰富。针对现有区域生长算法在城市三维密集点云拐角处未能完全生长的问题,设计了点到边(point to edge,PTE)数据结构,提出了遍历PTE数据结构以完善构网的改进策略。实验结果表明,改进算法能对城市真三维密集点云进行较好的表面构网,并且能够解决现有方法在拐角处不能完全生长的问题。Abstract: With the development of flying UAV platforms, sensor technologies, and corresponding data processing methods, low-altitude oblique photography becomes a powerful method to obtain true three-dimensional urban spatial information. In existing region-growing methods however, corners within urban dense point clouds are not fully grown. In this paper, we propose an improvement over the previous mesh-growing algorithms for fast surface reconstruction, a PTE (point to edge) data structure and traversing algorithm. Experimental results show that the improved algorithm is able to handle dense true three-dimensional urban point clouds, and can solve most of the incomplete growing problems in corners, with better performance than the exiting methods.
-
地质构造的边界识别是指对地下断裂构造、块体边界等线性分布的地质构造在地面上的展布位置进行定位,判断地下不同物性差异(如密度、磁化率和电阻率等)的构造带、不同岩性差异地质块体等构造的线性特征位置分布和变化范围。在不同密度或磁化率变化差异的地质构造边界位置,重磁数据异常变化较为明显,因此位场数据被广泛应用到地下地质构造的线性特征增强和提取中,且有较好的应用效果[1-2]。目前,位场边界检测方法主要包括数值计算类和数理统计类两大类,均需导数或高阶导数运算,观测数据若存有干扰噪声,会放大计算过程中的数据误差,影响线性边界的准确定位。此外,小波模极大值(wavelet modulus maximum,WMM)方法是具有抗噪声干扰能力较强的位场边界检测方法,该方法即使在存有噪声异常干扰的情况下也可对线性构造进行清晰、准确的定位[3]。
地表观测得到的位场异常通常是地下不同埋深的构造或地质体在观测面产生的综合叠加响应,具有多源性、非线性、非稳态性的特征。在位场数据资料处理过程中,可从位场数据异常中提取研究对象所产生的异常信息[4-5]。二维经验模态分解(bi-dimensional empirical mode decomposition,BEMD)[6-7]方法能够自适应地将数据中的各种频率成分有效分离出来,具有多分辨率的特性,其多尺度分解过程可以从高频到低频进行逐次尺度滤波,各尺度分解分量都反映了不同频次的模态特征。文献[8-10]将BEMD方法应用到位场多尺度分解中,并结合径向对数功率谱曲线对分解各尺度异常进行了分析和解释,取得了较好的应用效果。
本文首先通过建立模型重力位场数据,验证WMM方法在存有噪声干扰的情况下对线性构造进行定位和提取的有效性;其次利用BEMD方法对研究地区布格重力异常进行自适应多尺度分解,获得不同深度上构造或岩体线性分布特征;然后充分利用BEMD和WMM方法各自的数据处理优势特征,联合上述两种方法实现对分解各尺度异常进行场源边界检测,获得了不同深度上的场源边界信息;最后结合研究区域地质构造变化特征对各尺度下的边界异常信息进行分析和解释。
1 基本原理
1.1 小波模极大值
文献[1]提出了利用小波模极大值进行边缘检测的基本原理,并在图像领域得到成功应用。假设存在函数
在整个二维平面的积分为1,且x、y在无限远处收敛到零,则称 为平滑函数。那么,平滑函数 在x、y方向上的一阶偏导数分别表示为: 因此,可以将函数
和 看作两个二维小波函数。 在尺度因子
的情况下,对于任意函数 ,则由 和 定义的小波变换具有两个分量,分别为: 梯度矢量可表示为:
梯度的模和相角分别表示为:
由二维网格数据结构可知,每个数据点周围有8个相邻数据点,分别用数字1~8标注,如图 1所示。由于梯度方向的对称性,只需考虑1~4区域,此时数据点(x0,y0)相角的正切值
必定落在 、 、 、 4个区间之一,与位于1~4区域中某个数据的正切值存在一一对应的关系。 首先计算
数值的大小,然后判断其落入的区间编号N,将 与N区间以及N区间对称梯度方向上相邻两个数据点进行比较,若 大于这两个点,则数据点(x0,y0)为局部极大值点,否则就不是局部极大值点。因此,小波模局部极大值点刻画了二维数据边缘的特征点,获取到的局部极大值点就是边界数据点。 1.2 二维经验模态分解
文献[11-12]提出了一种自适应性地处理非线性、非平稳信号的分析方法——经验模态分解(empirical mode decomposition,EMD)方法,文献[13-14]将一维EMD拓展应用到二维数据中,利用BEMD方法对二维图像数据进行筛分,得到若干个不同尺度下的二维固有模态函数(bi-dimensional intrinsic mode function,BIMF)和一个剩余分量(Residue,Res)。具体分解流程见图 2。
设存在一个二维信号
,其中x=1,2…m,y=1,2…n(m,n为正整数),利用BEMD方法对该信号进行多尺度分解,共得到K个二维固有模态函数BIMF和一个剩余分量Res,即: 2 算例与分析
文献[10]中通过建立球体组合模型试验,利用BEMD方法实现了对组合模型异常的多尺度分解,并结合径向对数功率谱方法实现对分解异常的定性、半定量分析,证明BEMD方法对位场进行多尺度分解是有效的,且分解各尺度异常具有实际地质含义。
为了验证利用WMM方法进行边界检测的有效性,建立了长方体组合模型进行实验,该组合模型是由3个不同形态、不同埋深、不同剩余密度的长方体组成,其空间分布见图 3,相关参数见表 1。组合模型正演重力异常见图 4(a),为模拟组合模型重力异常中混有噪声信号,且噪声信号幅值变化相对较小,因此,向组合模型重力异常中添加信噪比为1.8%的高斯白噪声(见图 4(b)),其中蓝色线框为水平长方体在平面位置投影。
表 1 组合模型相关参数Table 1. Related Parameters of the Combined Models模型编号 (长, 宽, 高)/m 上顶埋深/m 下底埋深/m 剩余密度/(g·cm-3) 模型1 (600, 300, 300) 150 450 0.8 模型2 (650, 300, 250) 100 350 0.6 模型3 (500, 350, 400) 200 600 1.0 本文分别利用总水平梯度倾斜角(the tilt angle of the horizontal gradient,TAHG)[15]和WMM方法对未加噪声和加有噪声的组合模型异常数据进行处理,图 5为TAHG边界检测结果,图 6为WMM方法边界检测结果。从图 5、图 6中可以看出,对未添加噪声的重力异常,两种方法均可以有效地提取长方体线性边界位置,与长方体实际边界位置能够较好地吻合,TAHG方法计算结果存在边界效应,并没有对内部数据造成较大影响;在添加噪声的情况下,由于TAHG方法属于数值类计算方法,在计算过程中需多次求导运算,高次求导运算会把噪声放大进而对整个数据造成污染,计算结果出现了较大偏差,获取的线性构造分布特征不明显,而WMM方法的计算结果仍能够准确、清晰地展现长方体边界位置,数据中噪声异常对计算结果未产生较大影响,具有较强的抗噪声干扰能力。
3 实际应用
三峡地区西邻青藏高原高山峡谷区域,东临长江中下游平原丘陵区域,区内断裂和褶皱构造发育,地质地貌特征复杂多样。在早期燕山运动中,该地区形成了巫山、大巴山等一系列褶皱山脉,这些山脉由西南-东北走向转为东西走向,地势由南向北逐渐降低。三峡地区断裂构造较发育,断裂带构造控制着该区域的构造演化过程,地质及其相关地球物理背景比较复杂,近几十年以来,该区域受到国内外地质工作者[16-18]的密切关注。
由于布格重力异常数据在横向上具有较高的分辨率,为了研究三峡地区线性构造变化特征,利用该地区布格重力异常进行相关数据处理、分析与解释,结果见图 7。由图 7可知,研究区域异常整体呈现负异常,异常数值自西向东逐渐增大,存在近北北东向重力变化梯度带,三峡大坝正位于这个梯度带上,重力高值主要集中在东部江汉平原一带,重力低值覆盖了西部整个秭归盆地地区。本文利用BEMD方法提取了研究区域不同深度层次上布格重力异常特征信息,在进行BEMD分解过程中,需要预先设置阈值参数ε判断是否已经筛分出分解分量,ε可设定为较小的数,数值越小,获得的BIMF分量异常越多,但可能导致分解耗时过长。因此,为了在分解过程中获得较多的异常细节信息,设置分解阈值ε = 0.001,运用BEMD方法对三峡地区布格重力异常进行了多尺度分解,共得到5个BIMF和一个Res,分解结果见图 8。
由图 8可知,随着分解阶次增加,不同尺度下的异常呈现不同的形态变化特征,表现为从高频到低频变化。BIMF1异常呈现零星状或条带状分布,且出现正负伴生的现象,异常幅值在-6.4 ~6.6 mGal之间变化,其主要是地表出露或埋藏较浅的不同密度和岩性地质体产生的;BIMF2异常多呈现条带状并伴有零星状分布,异常展布范围相对较小,异常幅值在-8.2 ~7.4 mGal之间变化,其反映了浅部岩体或线性构造变化特征;BIMF3异常幅值在-12.4~12.6 mGal之间变化,在研究区域中部位置存在明显的重力变化高值异常的区域,变化异常走向由北东走向转为北西走向,再转为北东走向,最后变成北西走向,形成一个整体近似菱形重力变化高值异常,异常幅值变化达12.6 mGal,三峡大坝就位于这个高异常条带的中部位置,且三峡大坝附近存有明显的低重力异常区域,在西北部神农架地区和西南部的恩施地区都存在重力高值;BIMF4异常呈现区域性变化异常,异常变化分布范围较广,在东南部江汉平原地区有条带状正异常,秭归盆地为负异常,西北部神农架地区为高值异常,其为扬子板块出露部分,异常幅值变化较大,反映了区域深部岩性密度或构造特征变化;BIMF5异常显示研究区域有正负伴生的区域异常,西部秭归盆地地区为负异常,东部江汉平原为正异常,异常幅值变化较大,反映了两个区域地层起伏变化特性;Res异常反映了该区域异常的变化趋势特征,区域异常表现为东高西低,显示了研究区域基底或者莫霍面西低东高的起伏变化情况,在大尺度上体现了该地区岩石圈变化特征。
另外,本文利用径向对数功率谱方法[19-20]计算了上述各级固有模态函数的功率谱曲线,结果见图 9,其中红色虚线为拟合直线。将图9(a)~ 9(f)中曲线拟合出的直线斜率代入计算公式,得到各固有模态函数对应的场源深度,分别为7.3 km、16.7 km、25.8 km、45.3 km、52.7 km、71.3 km。由此可知,随着分解的增加,各级固有模态函数的波长和其所对应的场源深度逐渐增大。
BIMF1、BIMF2和BIMF3异常分布比较零散,异常强度和面积相对较小,可能反映了岩体或隐伏岩体、构造、地质异常体的物性和产状变化等;BIMF4、BIMF5和Res异常分布较集中,分布范围较广,反映区域内岩性密度变化以及地层或基底界面起伏变化。
因此,将BIMF1、BIMF2和BIMF3相加重构出局部异常,将BIMF4、BIMF5和Res相加作为区域异常,重构结果见图 10。图 10(a)中正、负异常呈现零星或区域性变化,部分异常变化特征较明显,主要存在3处高值异常区域,其中位于中部位置多条条带状高值异常整体呈现近菱形状,分布范围较广,异常幅值变化达30 mGal。此外,BIMF3异常中仍存在一个类似菱形状高值异常,两个异常特征变化存在对应关系,因此该菱形状高值异常应给予关注,可能包含着某类岩性密度变化或地质构造信息。图 10(b)中重构区域异常呈现了西低东高的趋势异常形态,测区西部秭归盆地异常幅值变化最小,东南部的江汉平原地区存有最大幅值变化异常,整体上反映了该研究区域较深结晶基底界面或者地层埋深自西向东逐渐减小的起伏变化情况。
此外,研究区域存有的主要地质构造是黄陵背斜,在其周围存在一系列的断裂分布,主要形成于印支运动时期,主要包括新华断裂、仙女山断裂、渔阳关-土门断裂、远安断裂、雾渡河断裂和天阳坪断裂等,这些断裂形成一个整体近似菱形状的断裂带,控制着区域的地质构造演化过程,其中黄陵背斜的相对隆升以及当阳、秭归等盆地的相对沉降在某种程度上都受到该断裂带演化过程的影响。文献[21]利用布格重力异常进行三维反演,反演结果显示这些断裂构造的切割深度达到了中地壳上部,属于区域性断裂。
由于BEMD分解得到各级固有模态函数是具有实际地质含义的,反映了不同深度层次上场源特性变化信息,本文对三峡地区布格重力异常进行BEMD分解得到各级BIMF和Res,并利用WMM方法对各尺度异常进行边界检测,检测结果见图 11。
由图 11可知,各尺度下边界检测结果与BEMD分解各分量异常特征相关,反映了三峡地区不同深度上的岩体、构造空间展布特征。利用BIMF3尺度异常获得的线性构造特征中,在中部位置菱形状的线性构造提取得到的部分线性构造的展布位置与菱形断裂带构造(如新华断裂、渔阳关-土门断裂和雾渡河断裂等)存在对应关系,说明BIMF3异常所反映的场源似深度信息与菱形断裂带构造埋藏深度能够较好的吻合,具有一定实际地质含义。然而,利用其余分量异常获得的线性构造与菱形断裂带构造并不存在明显的对应关系,说明上述不同频率的分量异常是埋藏较浅的地质体或地质构造和埋藏较深的地层起伏或基底变化的响应,菱形断裂带场源异常在上述频段内分解分量异常上反映不明显。
同样地,本文利用WMM方法对BEMD分解重构局部和区域异常进行边界检测,检测结果见图 12。由图 12可以看出,利用重构和区域局部异常获得的线性构造特征中均包含重构各尺度异常识别出的边界信息,是不同深度层次上的场源边界信息的综合响应。
因此,联合BEMD和WMM方法获得了三峡地区不同深度层位上的岩体或构造线性分布特征,实现了位场数据异常多尺度边界检测,且BIMF3异常边界检测结果与区域地质构造特征能够较好的吻合,这比单纯地分析二分异常对应的边界检测结果具有更高的分辨率。
4 讨论与结论
BEMD方法能够自适应地实现位场数据的多尺度分离,且分解各尺度异常具有实际地质含义。在位场数据中有噪声干扰的情况下,WMM方法仍能够清晰、准确地获取地下地质体的边界信息。本文联合BEMD和WMM方法实现了三峡地区布格重力异常多尺度边界检测,充分发挥了上述两种数据处理方法的优势,对分解各尺度异常对应的不同深度层位上的岩体边界、地质构造线性分布特征进行清晰、准确的刻画,有助于了解地下目标体分布特征,能够对区域构造单元划分、地质填图、矿产资源圈定和结晶基底起伏变化特征等方面研究提供重要参考信息。
此外,BEMD方法在位场数据处理中取得了一定的应用效果,但在拓展应用过程中依然存在着一些缺陷和不足,包括边界效应、模态混叠和分解效率较低等问题,如何提高BEMD方法计算效率的同时又能获得较为准确的分解结果需作进一步研究。
-
表 1 容器包含的所有元素
Table 1 All Elements in Container
容器 元素 pV[v5] v1 v4 v1 v2 v2 v*6 v4 v8 v8 v*9 pv[v6] v*5 v2 v2 v3 v3 v7 v*9 v10 v10 v7 pv[v9] v8 v*5 v*6 v10 v8 v11 v11 v12 v12 v10 表 2 数据处理结果统计
Table 2 Statistics of Data Processing Results
区域 点云数量 算法 三角形个数 构网时间/s 漏洞个数 漏洞比例/‰ A 128 160 原始算法2 13 918 10.1 1 115 5.2 改进算法 215 325 10.5 321 1.5 B 322 319 原始算法 635 943 32.4 1 004 1.6 改进算法 638 126 33.5 278 0.4 -
[1] 穆超,余洁,许磊.基于高分辨率遥感影像的DSM建筑物点的提取研究[J]. 武汉大学学报·信息科学版,2009, 34(4):414-417 Mu Chao, Yu Jie, Xu Lei. Extracting Building Points from the DSM Data Combining the High-Resolution Remote Sensing Image[J]. Geomatics and Information Science of Wuhan University, 2009, 34(4):414-417
[2] 王刃, 徐青, 朱新慧.用多种策略从机载LiDAR数据中提取建筑脚点[J]. 武汉大学学报·信息科学版,2008,33(7):688-691 Wang Ren, Xu Qing. Zhu Xinhui. Picking up Foot Prints of Building from Airborne LiDAR Data with Multi-strategies[J]. Geomatics and Information Science of Wuhan University, 2008, 33(7):688-691
[3] Poullis C, You S. Automatic Creation of Massive Virtual Cities[C]. IEEE Virtual Reality Conference, Louisiana, 2009
[4] 李镇洲,张学之.基于倾斜摄影测量技术快速建立城市3维模型研究[J]. 测绘与空间地理信息,2012,35(4):117-119 Li Zhenzhou, Zhang Xuezhi. Research on the Quick Construction of 3D Model of City Based on Oblique Photogrammetric Technique[J]. Geomatics & Spatial Information Technology, 2012, 35(4):117-119
[5] Musialski P, Wonka P, Aliaga D G, et al. A Survey of Urban Reconstruction[J]. Computer Graphics Forum, 2013, 32(6):146-177
[6] Merchan P, Adan A, Salamanca S, et al. Geometric and Colour Data Fusion for Outdoor 3D Models[J]. Sensors, 2012, 12(6):6893-6919
[7] Kuschk G. Large Scale Urban Reconstruction from Remote Sensing Imagery[J]. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2013, XL-5/W1:139-146
[8] Kuschk G. Model-Free Dense Stereo Reconstruction for Creating Realistic 3D City Models[C]. Urban Remote Sensing Event, IEEE Joint, Brazil, 2013
[9] Canciani M, Falcolini C, Saccone M, et al. From Point Clouds to Architectural Models:Algorithms for Shape Reconstruction[J]. International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2013, XL-5/W1:27-34
[10] Boissonnat J D. Geometric Structures for Three Dimensional Shape Representation[J]. ACM Transactions on Graphics, 1984, 3(4):266-286
[11] Kolluri R. Provably Good Moving Least Squares[J]. ACM Transactions on Algorithms, 2005, 4(2):782-795
[12] Kazhdan M, Bolitho M, Hoppe H. Poisson Surface Reconstruction[C]. Eurographics Symposium on Geometry Processing, Switzerland, 2006
[13] Amenta N. A New Voronoi-based Surface Reconstruction Algorithm[C]. ACM Conference on Computer Graphics and Interactive Techniques, Atlanta, 1998
[14] Dey T K, Goswami S. Tight Cocone:A Water-Tight Surface Reconstructor[C]. ACM Symposium on Solid Modeling and Applications, Seattle, 2003
[15] Cohen-Steiner D, Da F. A Greedy Delaunay-based Surface Reconstruction Algorithm[J]. The Visual Computer, 2004, 20(1):4-16
[16] Bernardini F. The Ball-Pivoting Algorithm for Surface Reconstruction[J]. Visualization and Computer Graphics, 1999, 5(4):349-359
[17] Li X, Han C Y, Wee W G. On Surface Reconstruction:A Priority Driven Approach[J]. Computer-Aided Design, 2009, 41(9):626-640
[18] Di Angelo L. A New Mesh-Growing Algorithm for Fast Surface Reconstruction[J]. Computer-Aided Design, 2011, 43(6):639-650
-
期刊类型引用(1)
1. 杨亚斌,荆磊,徐梦龙,韩革命,邱隆君,吴新刚,郜晓亮,郝国江,孙诚业,张光之,苏振宁. 陆域重力勘探进展. 物探化探计算技术. 2022(06): 722-741 . 百度学术
其他类型引用(3)