利用AlphaShapes算法提取离散点轮廓线

湖北广播电视大学学报Journal of HuBei TV University第 30 卷 第 2 期2010 年 2 月Vol.30, No.2February. 2010, 155156利用Alpha Shapes 算法提取离散点轮廓线周飞（武汉船舶职业技术学院，湖北武汉430050）内容提要 本文介绍了 Alpha Shapes 算法的原理和具体的实现方法，并将其应用到 LiDAR 离散点云数据的轮廓线提取，取得良好效果。关键词 Alpha Shapes 算法；轮廓线；LiDAR 点云中图分类号 TP31文献标识码 A文章编号 1008-7427（2010）02-0155-02界；如果 很大（ ）时，则求出的边界线为点集 s的凸包6。1引言自20世纪60年代末全世界第一部激光雷达诞生以来，机 载激光雷达（Light Detection And RangingLiDAR）技术作 为一种重要的航空遥感技术，已经为越来越多的学者们所关 注。迄今为止，机载激光雷达的研究与应用均取得了相当大 地进展，特别是由于近几年来比较成熟的商业化机载激光雷 达系统的出现，在欧洲和北美地区，机载激光雷达地应用很 活跃。在亚洲地区，机载激光雷达地应用主要集中在日本、 马来西亚。虽然机载激光雷达无法完全取代传统的航空摄影 测量作业方式，但可以预见，在未来的航空遥感领域，机载 激光雷达将成为主流之一。按照安装平台的不同，激光雷达 分为地面、机载和星载激光雷达。与地面和星载相比，机载 激光雷达的技术比较完善,有多家公司提供集成设备。目前， 机载激光雷达的后处理软件都由各个厂家提供，至今还没有 通用的软件系统出现，后处理技术的研究很多，但大部分算法还停留在研究阶段，还没有公认的成熟算法1。 机载激光雷达数据的获取、处理及发送都为数字格式，易于生成能满足各种需求的数字产品，其最简单的数据格式 为包涵X,Y,Z坐标数据的ASCII文件。这些坐标数据反映了 由激光雷达收集的地面上的3维信息，包括地表、建筑物、 树或任何反射物。通过特定的一些算法可以将点云分类，从 而提取各类地物。为了给GIS提供不同地物的三维矢量信 息，往往还需将点云数据的边缘进行矢量化，如提取建筑物 的边缘、水体边缘等等。利用平面点集求凸壳已经有相当成熟的算法，如著名的格雷汉姆方法2，但都只能求出点集边 缘的凸点。在图像处理领域也提出了许多边界提取方法，通 常采用的方法包括：局部算子法3。朱汗华等4对平面的离 散测量点首先进行三角化，得平面点集的三角形网格,而后 用网格的边界作为离散点的边界。陈涛等5提出一种使用搜 索盒的搜索平面离散点集边界的算法，该方法将离散点分配 到搜索盒中，遍历位于边界的搜索盒，将其中的点连接成边 界点链表，该搜索算法适应性强，但是实现起来比较复杂。 而本文采用Alpha Shapes算法6提取离散点轮廓线。2Alpha Shapes算法原理Alpha-Shapes可以用来从一堆无序的点集中提取边缘。 设有一点集 s 的Alpha-Shapes是一个多边形，这个多边形是 由点集 s 和半径参数 决定的且唯一。它的原理如图1所 示，可以想象成一个半径为 的园在点集 s 外滚动，当 足够大时，这个园就不会滚到点集内部，其滚动的痕迹就是 这个点集的边界线。因此，当 值很小，则每个点都是边图1 Alpha-Shapes提取边界示意图3.Alpha Shapes算法实现方法一个有限离散点集S如图1，由n个点构成，这n个点可以 组成 n (n 1) 条线段，那么如何判断哪些线段是边界线上 的线段。沈蔚等7通过如下的方法进行判断：在点集S内，过任意两点P1、P2绘制半径为 的圆，如 果这个圆内没有其他点，则认为点P1、P2是边界点，其连 线P1 P2 是边界线段。假设已知两点P1、P2 坐标分别是x1、y1 , x2、y2，求过这两点的圆的圆心P3，实际上就是求与这两点距离为 的点P3的坐标x3、y3。获得圆心后，要判断 圆内是否有其他点，则只需判断是否存在其他点到圆心的距 离小于 值。沈蔚等7的方法需要多次的判断点是否落在园内，计算 量较大。为了减少计算量，本文采用先建立三角网，再从三 角网的外边界开始进行判断，其流程如下：第1步：根据点集 s 建立Delaunay三角网； 第2步：在三角网上删除不符合Alpha-Shapes要求的三角型。先删除边长大于 2 的三角形；再递归判断要删除的 边缘三角型，若通过三角形外边两点并且半径为 的圆包 含其他点，则删除此边缘三角形。如图2所示，当前所要判断的三角型为 ABC ，外边两点 A 和 B ，半径为 并且 通过 A ， B 两点的圆包含点 C ，则从三角 网上删除 ABC 。添加新出现的边缘三角型 ACE 和 ABC 到 待处理堆栈中。图3 不规则的点云数据5结论图5 离散点云的边界轮廓线为了获得离散点的边界轮廓线，本文先建立三角网，再从三角网的边界开始搜索外边缘，利用Alpha-Shapes的原 理，快速地、稳健地提取出离散点的边缘轮廓线；从而为 GIS提供矢量信息。图 2 不满足 Alpha-Shapes 要求的三角形第3步：在删除不符合Alpha-Shapes要求的三角型后所 得到的三角网上求出三角网的边缘。该边缘即为点集 s 的边 缘线。4实验为了测试本算法的效果，选取一块具有不规则外形的LiDAR点云数据如图3所示，建立三角网后如图4所示。参考文献1 吴华意, 宋爱红, 李新科. 机载激光雷达系统的应用与数据后 处理技术J. 测绘与空间地理信息, 2006, (3).2 Peli T., Malah D. A study of edge detection algorithmsJ. Computer Graphics and Image Processing, 1982, (1).3 Graham R. An efficient algorith for determining the convex hull of a finite planar setJ. Information Processing Letters, 1972, 1 (4): 132-133.4 朱汉华, 刘正林. 航道疏浚区的测量点边界搜索方法J. 武汉理工大学学报：交通科学与工程版, 2002, 26 (003): 309-311.5 陈涛, 李光耀. 平面离散点集的边界搜索算法J. 计算机仿真,2004, 21 (3): 21-23,63.6 Akkiraju N., Edelsbrunner H., Facello M. Alpha Shapes: Definition and Software. http:/www.geom.uiuc.edu/-software/cglist/GeomDir/shapes95def/index.html, 2009.7 沈蔚, 李京, 陈云浩等. 基于 LIDAR 数据的建筑轮廓线提取 及规则化算法研究J. 遥感学报, 2008, 12 (5).图3 不规则的点云数据图4 不规则的点云数据利用Alpha-Shapes算法删除不符合条件的三角形后，其结果如图5所示，并将三角网的外边界连接起来，如图6所示。The use of Alpha Shapes Contour Extraction of discrete pointsZHOU FeiAbstract This paper describes the principles and specific implementations of Alpha Shapes algorithms, and its application to extract contour from the LiDAR point cloud data in discrete. Experiments show that the algorithm achieves good results.Key words Alpha Shapes algorithms; contour lines; LiDAR point-clouds中国人民大学复印报刊资料系列刊之社会学【内容简介】精选中外社会学理论、社会学史、人类学、民俗学、社会学分支、社会发展等方面的研究文献资料。【专家顾问】洪大用，中国人民大学社会学系、社会学理论与方法研究中心教授、 博士生导师。主要从事应用社会学、环境社会学和社会政策方面的教学与研究。月刊，16 开 96 页，单价 10.00 元年价：平装 120.00 元，合订 135.00 元订阅电话：010-82503438/39/40/41