王秋燕，陈犀力

（1.江苏联合职业技术学院南京分院；2.南京地铁运营有限责任公司）

1 引言

目前，较普遍的建筑物轮廓线提取方法，一般是采用插值算法，将三维点云的高程值赋给图像灰度值，进一步处理得到规则化的nDSM，最后图像分割，边缘检测或结合高分辨率影像进行建筑物轮廓线的提取[1～3]，如图1所示。对LIDAR点云插值生成深度影像，如图1a所示，然后使用具有代表性的图像边缘检测算子，如Canny算子、Sobel算子和Prewitt算子进行检测的结果分别如图1b，1c，1d所示。从实验结果分析，检测的边缘线会出现断裂、杂乱及不规则等问题，这些问题会对后期轮廓线的简化和规则化带来困难，如何连接断裂的边缘线以及如何判断并去除多余的非边界线等都是急需解决的难题。

图1 图像边缘检测算法轮廓线提取结果

2 Alpha Shapes算法

Alpha Shapes算法可从一堆离散的点集中进行几何形状的重建，如图2所示。最早是由H.Edelsbrunner，D.G.Kirckpatrick and R.Seidel[4]在1983年发表的文章《平面点集的形状》中正式提出。用一个半径为a的圆在点集周围滚动，当遍历所有的点之后，最终可以得出点集的内外轮廓线。当圆的半径 a较大时，圆在点集S的外部滚动，外部滚动的痕迹就是点集的边界轮廓线。当半径a值较小时，圆就滚动到点集S内部去，当a值足够小时，点集中的每个点都是边界点。圆半径a的取值与检测出来的建筑物轮廓线精细程度密切相关，如图3所示，半径相对较小时，检测出来的轮廓线较精细，半径相对较大时，检测出来的轮廓线略微粗糙。

图2 Alpha Shapes算法模型

针对离散的三维点云进行建筑物轮廓线提取及轮廓线的规则化研究，将Alpha Shapes算法[5]运用到本文的研究中，避免了插值算法带来的误差，解决边缘检测算法提取的轮廓线存在断裂，杂乱等问题。

3 Alpha Shapes算法的适用性研究

Alpha Shapes算法的适用范围较广，对于矩形、正方形、T形、工字型、环形、三角形、圆形和不规则凹凸多边形等都具有很好的适用性，其算法稳健性强，运算速度快。本文对Alpha Shapes算法的适用性进行了实验研究，其实验结果如图4所示。

4 改进的Alpha Shapes算法提取建筑物轮廓线

图3 Alpha值的大小与边缘精细程度的关系

本文针对城区较平坦地区的建筑物进行实验，利用改进的Alpha Shapes算法对机载LIDAR建筑物的轮廓线进行了提取，改进的Alpha Shapes算法对机载LIDAR点云数据先构建Delaunay三角网，再对构建的Delaunay三角网进行判断，从而快速有效地提取建筑物轮廓线。

改进的Alpha Shapes算法对实验数据一机载LIDAR点云数据构造的Delaunay三角网如图5所示，用Alpha Shapes算法提取的建筑物轮廓线如图6所示。图6c是算法提取的较为精细的建筑物轮廓线。此实验验证了改进的Alpha Shapes算法能够快速准确地将建筑物轮廓线提取出来。

图5 实验数据一 Delaunay三角网的生成

5 结语

综上所述，Alpha Shapes算法的适用范围较广，该算法提取的建筑物轮廓线都是闭合的曲线，不需要进行断裂线段的连接，算法不需要进行插值，避免了插值带来的误差，且在一定程度上解决了图像处理方法提取边缘线存在断裂、杂乱的问题。本文对Alpha Shapes算法进行了一定的改进，在进行建筑物的轮廓线提取前，先对LIDAR点云构造Delaunay三角网，再进行建筑物轮廓线的提取，提高了Alpha Shapes算法的运行效率。由此可知，Alpha Shapes算法较适用于离散点云的建筑物内外轮廓线提取，且该算法提取的建筑物轮廓线为后续轮廓线的简化和规则化研究做好了充分的数据准备。

图6 实验数据一 Alpha Shapes算法建筑物轮廓线提取