基于栅格的点云数据的边界探测方法

何 丽，李 嘉，郑德华

（河海大学 地球科学与工程学院，江苏 南京 210098）

边界是三维建模的重要几何特征信息。边界提取技术在医学图像、工业断层扫描图像等二维图像处理领域中应用广泛。在逆向工程中，点云数据的三维空间分布的不均匀性，难以建立严格的数学模型，使得点云数据的边界提取成为一项较复杂的工作。近年来对于点云数据边界的自动提取，国内外学者已有一些研究［1－3］。

为了简化算子结构，提高对大量复杂点云数据的处理速度，本文提出一种基于扫描线的点云数据边界探测算法，该算法的主要思想是利用点云数据的特征将三维点云数据转换为深度图像，对深度图像提取边缘信息，最后将其转换到三维空间中。

1 点云网格化及其转换

1.1 三维点云的特征

地面三维激光扫描仪原始观测值主要有：通过TOF（Time of Flight）脉冲测距法获得的仪器到扫描仪的距离值S；精密时钟控制编码器同步测量每个激光束的水平方向角度值α和竖直方向角度值θ；反射强度I。前两类数据用来计算扫描点的三维坐标值；反射强度用来给反射点匹配颜色。一般使用仪器内部坐标系统，如图1所示，三维扫描点P的坐标（Xp，Yp，Zp）的计算公式为

图1 三维激光扫描仪的内部坐标系

激光扫描所获得的是由离散矢量点构成的点云（Points Cloud）数据。总体上来讲，点云数据可以分为散乱点云和规则点云两大类。散乱点云没有明显的几何分布特征，扫描点之间没有明确的空间邻域和拓扑关系，无规则的分布于目标对象空间（见图2）。

图2 不同类型的数据点云

规则点云是按照一定的规则进行采集和存储的点云数据。规则点云一般有两种类型：

1）网格化点云。点云数据呈矩形分布，所有点都与参数域中一个均匀网格相对应。多为点云数据经过网格化插值得到。

2）扫描线点云。点云以扫描光刀面的形式进行储存，点云由一系列扫描线组成，在同一光刀面内的扫描点是共面的。

地面激光扫描仪以扫描线的形式进行数据采集和存储，一般通过扫描线分组和线内数据点排序的方法来建立扫描线点云的邻域关系和拓扑结构。

1.2 三维点云的栅格化

栅格化的目的是把三维点云映射为图像的二维矩阵表示形式，即将扫描点映射到XY平面。

1.2.1 确定X，Y轴上的值

目前，三维激光扫描文件一般无法直接读取距离及角度，利用式（1）中坐标与角度的关系，把坐标（Xp，Yp，Zp）依次转化为（α，θ，S）格式，如式（2）所示，得到一个二维点集，记为S：｛Pi（αi，θi）｜1≤i≤n｝，其中n为扫描点的总个数。

式中：α，θ为XY投影面横轴、竖轴上的值。α取值范围（0，2π），θ取值范围（－π/2，π/2）。计算XY平面内“点云”数据最小包围盒，得到α，θ最大最小值。

1.2.2 扫描线分组

遍历X轴方向的水平角值，其散点图如图3所示，由图中可见每一组的水平角为固定值，且水平角呈线性分布。因此，可通过相邻两个扫描点的水平角差值的变化确定扫描线的分组：当第i＋1个点与第i个点的水平角差值突然增大，且大于某一正数时，第i＋1个扫描点为下一组扫描线的第1个扫描点。N等于扫描线的总数。

图3 坐标转换后水平角值及其局部放大图

因扫描时存在误差，每组扫描线间隔不完全相等。可通过计算每组扫描线的水平角均值αavg来计算相邻两组扫描线之间的水平角差值，求其平均值即得扫描线平均间距Δα。

1.2.3 点云数据分行

遍历Y轴方向的竖直角值，其散点图如图4所示，由图中可见每组扫描线上的竖直角呈相同的线性分布。由此可计算每个扫描点在栅格中对应的位置。首先搜索每组扫描线的扫描点个数，取其最大值M为栅格的行数，则竖直角平均间距约为Δθ＝。在点云中选取西南角点（αmin，θmin）作为基准点，然后计算扫描点与基准点的相对位置。根据式（3）可计算出每个扫描点在栅格中的位置。

图4 坐标转换后竖直角值

其中，［］表示取整。

点云栅格化后生成M行N列的二维矩阵，建立矩阵与点云对应的索引矩阵。

1.3 深度图像的生成

深度图像实质就是带有距离信息的视觉图像。与传统的视觉图像相比，深度图像中的每个像素存放的不是灰度信息或者颜色信息，而是三维模型表面到成像面的距离信息，因此，深度图像既包含三维模型空间信息，又具有视觉图像的特点。

1988年，Besl提出了深度图像表达形式［5］

式中：d（i，j）表示深度信息，即扫描点到图像像面距离S；（i，j）表示像素点行列坐标。深度图像d（i，j）可看成二维矩阵，即有0≤i≤M－1，0≤j≤N－1；矩阵元素成为图像像素，M×N表示图像的大小，即行数和列数。

结合上面讨论的三维点云数据的栅格化，实现x，y方向的均匀规格采样，因此可快速实现深度图像的转换。

点云栅格化后生成的二维矩阵与图像的像素点是一对一的映射关系。因此，可根据扫描点在栅格中的位置（行列号）定位其在图像中的像元位置。根据扫描点到图像像面的距离S确定该点对应像元的灰度值，即Z方向代表深度，如式（5）所示。距离和灰度值成正比关系。

三维激光扫描过程中受到仪器误差、环境误差等影响，现场实测的三维数据在很多区域会出现数据缺失，如图5所示，进而导致映射的深度图像中对应像素数据的缺失。因此，需要对图像进行处理后再进行边界的提取。

图5 点云栅格示意图

2 图像边界探测算法

2.1 深度图像处理

2.1.1 图像插值

传统插值方法平滑效果较好，但会造成边缘和细节特征的模糊；基于区域的插值方法，可以保持图像的边缘特征，故使用基于区域的插值技术来恢复出缺失的像素。

此方法大致过程是：首先通过区域分割技术，将图像分为不同的区域，然后确定插值点所属的区域，在一般区域用邻域加权线性方法进行插值，对边缘区域则采用有针对性的插值方法。

2.1.2 深度图像滤波

三维数据映射为深度图像后，引入图像噪声。主要有脉冲型噪声、高斯噪声、椒盐噪声，如果直接对含有噪声的图像进行分割，会损失很多图像细节，或出现伪边缘，检测效果差。

本文采用中值滤波器，它是一种非线性滤波，可以有效地去除噪声，特别是对脉冲型噪声、椒盐噪声，而且可以较好地保护图像边缘。

2.2 深度图像边缘检测

边缘是图像中表面或者方向不连续的点。有多种算法可以检测深度图像边缘，如Roberts、Sobel、Prewitt、Kirsch和Laplacian等算子。但它们对噪声比较敏感，处理实际图像的效果并不理想。

本文采用Canny算子进行边缘提取，Canny算子满足3个判断准则：信噪比准则、定位精度准则、单边缘响应准则。Canny边缘检测算法是高斯函数的一阶导数，是对信噪比与定位精度之乘积的最优化逼近算子。其分为4步，分别是图像平滑、边缘检测、阈值分割及边缘定位，具体如下：

1）采用高斯滤波器，对图像f（x，y）进行平滑滤波，高斯函数公式为

2）用一阶偏导数的有限差分计算平滑后的图像的梯度▽g（x，y）和方向θ（x，y）。

式中：Fx（x，y）、Fy（x，y）由G（x，y）在x方向和y方向偏微分， 分别与图像卷积得到。

3）对梯度进行“非极大值抑制”，保留局部梯度极大值且在该点处梯度突变最大的像素点，目的是为了细化幅值图像中的屋脊带。

4）双阈值算法检测和边缘连接。利用Canny算子检测图像边缘的关键是选取适当的阈值以及σ，合理的高低阈值设定能检测出更多真实边缘，去除尽可能多的伪边缘。若高阈值设定过小会检测出的边缘中混有大量噪声，设定过大又会漏检真实边缘，对于低阈值，若设定过大会造成灰度值突变较小的边缘被漏检；另外，合理的σ大小也很重要，σ越大，使图像平滑程度越大，将导致图像细节消失，灰度突变也会远离原来边缘的位置，同时使高斯滤波器长度变长，加大计算量，反之，σ越小，则又会因为图像平滑不够使检测的边缘中混有许多噪声。

本文采用开放式阈值设置方法，用户可以自己调节高低阈值及σ大小，以得到最满意边界数据。

3 点云边界探测及显示

将图像的边界探测结果转换到三维空间中，即检测出点云数据中对应边界的扫描点。

因为点云数据与深度图像之间存在一对一的映射关系，由Canny算子检测得到的边界图像其像元位置没有发生改变，故可通过边界图像上边界线的像元的位置找到对应索引矩阵中的位置，从而得到边界点的坐标。即得图像边界位置的扫描点的空间位置信息。

4 实验结果

通过VC6.0调用OpenGL三维函数库，实现基于扫描线的地面激光扫描数据边界提取的程序开发，并进行了大量的实验，应用Jiang［7］等提出的评估方法进行评估，验证本文算法有较优的性能。

4.1 算法性能评估

应用软件对点云原始数据进行人工边界提取，得到的结果称为GT（ground truth），用算法自动边界提取的结果称为EM（machine－generated edge map）。当提取的边界点同属于GT和EM中时，则被认为是正确检测［8］。

4.2 实验结果分析

点云数据是由Trimble GXTM三维激光扫描仪采集，图6是在RealWorks软件中显示的原始点云，点云个数为688 716；对原始数据进行坐标变换并栅格化后得到深度图像，如图7所示，图像大小为1200×675像素，图中灰度值的大小代表扫描点到图像像面的距离S，灰度值为0的区域代表背景区域。由于这幅点云是在室外进行扫描，受到外界条件影响较大，故生成的图像空缺点较多。

对深度图像进行插值平滑处理后的图像如图8所示，其空点明显减少，图中右边桥梁上的大空洞是由扫描过程中遮挡物造成的，故无法平滑。

调节Canny算子阈值，当高低阈值分别为10、30时，边缘提取的结果如图9所示，此时桥梁边缘线连接程度较好，边界表示完整，边缘线较细。通过边界图像上边界线的像元的位置找到对应索引矩阵中的位置，从而得到边界点的坐标，将边界线转换到三维空间中，其边界点云（EM图）如图10所示，检测到的边界点总数为18 264。

图10 边界点云（EM图）

图11是在软件中对原始点云进行人工提取边界得到的GT图。采用文献［2］中直接提取算法得到的结果如图12所示，可以看出，提取出的边界点不连续，甚至发生跳变，边缘错位。表1所示为本文算法与直接提取法的结果比较。

表1 两种算法实验结果比较

基于栅格化的扫描线法的正确检测率较高，可以较好地平衡边缘定位精度和抗噪声性能的矛盾，其性能优于其他算法。这对后续的处理工作非常有利。但是结果与相应的GT图像还有一定的差距。

为了对算法的适应性进行实验，选取了一幅复杂的点云数据进行处理，其原始的数据点云如图13所示，共有746 252个点，包含曲面物体、平面物体等。图14是其边界探测的结果，可见该算法对于任意形状的物体都适用，具有很强的适应性和应用性。

图13 原始点云显示

图14 边界探测结果

5 结 论

本文分析三维点云和深度图像的数据结构特征，提出一种基于栅格化的扫描线点云数据边界提取方法。采用该方法能对大量的复杂点云数据进行直接、有效的提取，其具有以下特点：

1）边界提取方法简单，用户可以自动调节Canny算子的高低阈值，得到最完整的边界数据。

2）特别适合于曲面特征多的点云数据，对其他特征的数据也同样适用。

3）运行速度较快，对点云数据的边界提取质量高，可以满足点云数据后续处理的要求。

4）可应用在基于边界特征的点云数据的多视拼接与配准、点云数据的角点检测、点云数据的分割、点云的重构建模等后续处理工作。

［1］Alrashdan A，Motavalli S，Fallahi B.Automatic Segmentation of digitized data for reverse engineerng applications［J］.IEEE Transaction on Design and Manufacturing，2000，32（4）：59－69.

［2］柯映林，范树迁.基于点云的边界特征直接提取技术［J］.机械工程学报，2004，40（6）：116－120.

［3］李江雄.反求工程中复杂曲面边界线的自动提取技术［J］.机械设计与制造工程，2000，9（2）：26－28.

［4］郑德华，沈云中，刘春.三维激光扫描仪及其测量误差影响因素分析［J］.测绘工程，2005，14（2）：32－34.

［5］Besl P J，Jain R C.Jain.Segmentation through variable－order surface fitting［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1988，10（2）：167－192.

［6］孙晓兰，赵慧洁.基于网格采样的深度图像表面 特征提取算法［J］.中国图像图形学报，2007，12（6）：1091－1097.

［7］Jiang X Y，Bunke H.Edge detection in range images based on scan line approximation［J］.Computer Vision and Image Understanding，1999，73（2）：183－199.

［8］Hoover A，Jean－Baptiste G，Jiang X Y，et al.An experimental comparison of range image segmentation algorithms［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1996，18（7）：673－689.