基于点云模型骨线提取算法的三维场景漫游路径查找∗

张双星 张 星

（华中科技大学自动化学院 武汉 430074）

基于点云模型骨线提取算法的三维场景漫游路径查找∗

张双星 张 星

（华中科技大学自动化学院 武汉 430074）

论文针对三维场景杂乱点云，通过逐渐增大采样点邻域半径，迭代计算骨线点并连接，获得代表三维点云整体结构信息的一维曲线，即点云模型的骨线。接着，论文通过应用点云的骨线信息，辅助性地改进了三维大场景内部漫游路径查找方法。论文实验数据为煤矿井下巷道的三维杂乱点云模型，实验表明，此改进很好地提高了路径的准确性并极大地缩减了三维大场景漫游的工作周期。

点云处理；骨线提取；三维漫游；OpenGL

1 引言

漫游路径的确定是三维场景漫游的核心环节。目前的三维漫游多用于游戏与影视领域，路径多是最先设定，在此基础上自绘三维场景实现效果渲染［1］。而工程领域中，需要由拼接而成的点云模型获取漫游路径，而传统的三维点云场景漫游路径查找需要人工完成。这需要在可视化软件（如CloudCompare）下手工地从点云模型上取出点云点，拟合直线函数，并进行平移和固定端点旋转操作，最后再对获得的分段直线进行连接，进而获得漫游路径。人工的路径查找有着诸多缺点，如效率低下、准确度不足、路径不平滑等，而且点云密度较大时，点云模型中的点不可肉眼分辨，只得利用外部的噪声点来确定位置，这又与点云预处理步骤中的除噪及精简相冲突，并且对操作人员的技术水平要求过高。面对点云预处理（滤波，精简，配准）算法与三维模型重建算法的飞速改进，路径提取已经成为三维场景动态可视化的瓶颈。

为了提高工作效率，本文提出一种点云模型骨线提取算法，该算法同时利用K-邻域与R-邻域两种邻域确定方法对采样点进行迭代更新，并逐渐合并连接，形成一维骨线。在此算法基础上，本文对结果曲线进行平滑处理，获取准确的三维场景的漫游路径，并基于OpenGL库实现了三维场景漫游。

本文所提出算法的实验数据以及应用效果评估均依赖于蒋盛锋［2］提出的基于三维激光雷达的集数据采集、预处理、路径查找、场景漫游于一体的漫游系统。

2 点云模型的骨线提取算法

2.1 算法整体流程

三维点云模型输入中包含很多种类的信息，如最基础的点的坐标以及附加信息如Mesh、法向量、点的颜色、强度等。针对不同内容的输入信息，骨线信息提取有着不同的算法。

比较有名的有 Tagliasacchi［3］提出的基于三维点坐标信息与其法向量信息的骨线提取算法，称作ROSA。此方法需要对点云模型进行预处理，添加法向量信息，复杂度较高，且对输入点云模型要求较高。本文的算法直接针对点云的坐标信息进行骨线提取，输入模型中不需含有其他任何种类的信息。

本文的骨线提取算法，主体思想是以采样点位置移动代表周围原始点的信息变化，并逐渐增大范围半径，得到最合适的采样点固定的位置，转化为骨线点，最后连接骨线点，形成骨线。

如图1所示算法流程图中，输入点云为已拼接、滤波、精简等预处理后的点云，具体预处理流程见文献［2］，这时的点云我们称作原始点云集O（Original Point Cloud），下一步，我们对原始点集进行随机下采样，得到采样点云集S（Sample Point Cloud），下采样过程采用C++库中随机函数实现。采样率用来表示采样密度，本文默认采样目标为每一个采样点初始半径邻域内约有10个邻域点。这样我们可以获得μ的经验值0.03，而且可以获取基于距离邻域确定方法的邻域初始径：

其中 ∆A=Amax-Amin(A=X，Y，Z)代表所有点云P(x，y，z)在各坐标轴下的最大差值。

得到了初始R-邻域半径R0，我们就可以开始进行采样点更新，不断地使采样点逼近特征描述点，这样一面利用基于采样点之间K-邻域的判定方法判断采样点是否已成为骨线点，一面增加R不断更新采样点，反复迭代，直至获取骨线点，与上图描述不太一致的地方在，骨线的连接与骨线点的确定是同步进行的。

下面分别介绍流程中各部分的概念及理论基础。

2.2 R-邻域与K-邻域的概念及快速搜索

两种邻域都比较容易理解，多维模型下，R-邻域指距离某点的欧几里德距离（2-范数）在R（R＞0）以内，而K-邻域［4］同样基于2-范数，却进行了一次比较，表示距离某点最近的K个点。相对来说，R-邻域更直观，而K-邻域更常用。

由图2对比可以看出，K-邻域特点为邻域内点的数量固定，而邻域半径不固定，R-邻域的特点为邻域半径固定而邻域内的点的数量随该采样点附近点云密度而改变。

图2 （a）K-邻域（k=3） 图2（b）R-邻域

回到我们的骨线提取算法，其核心第一步为移动采样点位置来表示“周围”原始点的信息，由于K-邻域受密度影响较大，不能代表这个步骤中“周围”一词的含义。因此选用R-邻域来确定周围原始点集，并加权计算更新采样点位置。相对而言，在采样点移动中如何判断其是否为骨线点，这就需要观察其“周围”的采样点的位置，此时我们并不知道附近采样点具体有多远，这就需要利用K-邻域需找附近固定数量的采样点。

图3以二维平面内的点给出了算法中两种邻域的应用。其中采样点为两圆共同的圆心，外圆圈为K-邻域示意，内圆圈为R-邻域示意。

关于两种邻域快速搜索的实现，方法都比较成熟。R-邻域快速搜索的一般方法为先对原始点云进行预处理，用三维立方体方格（立方体边长一般取现阶段的R）将点云点进行index建立，接着在采样点附近的魔方盒（周围27立方体方格）中基于距离查找邻域点。而K-邻域实现算法较多，一般采用Kd-tree数据结构［5～6］对原始点云点进行树化，接着在该Kd-tree中查找K-邻域点，本文K-邻域搜索基于PCL（Point Cloud Library）库实现。

图3 骨线提取算法中的K-邻域与R-邻域示意图

2.3 基于R-邻域的采样点迭代更新

以一个采样点位置代表周围特定范围内所有原始点，就是该步骤的目的。这样就有很多方式，一种方式为，使用周围点的位置坐标及法向量信息求得采样点需要更新的位置，这就是文献［3］提出的ROSA算法。文本采样一种通用的方法，该方法仅需要即利用加权p-范数进行采样点的迭代更新［7］。

其中用到了高斯权重函数：

其中d=‖x-po‖L2

式（2）中 po为原始点，‖xcur-po‖p指 p-范数，若 p=2，即为普通的基于欧几里德距离求平均，若p=1，则为1-范数，相对而言2-范数容易受到噪声点的影响而偏离几何中心，而1-范数不仅不容易受干扰，而且计算相对简单。当然2-范数也会被用到，这就是高斯加权函数中的距离项。

式（3）为高斯函数表达式，图4给出了高斯函数曲线（r=10）以及效果图，其中，颜色越深，权重却大，高斯函数很好地解决了弥补了基于魔方盒查找的R-邻域搜索算法的缺点，并一定意义上屏蔽了离群点。

图4 （a）高斯权重曲线 图4（b）高斯权重颜色效果

经由式（2）处理，采样点会不断地朝局部中心点移动，随着采样点移动，周围的邻域点也在不断地变化，这样反复迭代，会得到局部特征描述点如图（5）所示。

图5 采样点迭代移动示意图

2.4 基于K-邻域的骨线点确定与连接

此步骤判断采样点是否达到骨线点的标准。首先明确什么样的点才是骨线点，这部分需要对采样点K-邻域内的邻域点进行统计学分析，用以确定该采样点附近是否形成曲线环境。

PCA（Principal Component Analysis）是一种常用的数据分析方法。本文采用PCA权值来检测骨架点之间的关系，以给出骨架点能否相连的判断。对每一个局部固定采样点计算其加权协方差矩阵：

本部分实现依赖于人工神经网络算法［8～9］（ANN）库。接着我们对已确定骨线点进行算法性的忽略，排除到采样点外，并与附近的采样点“连接”，与表述不同的是，算法显示与算法输出是不同的，输出结果仅类似于树结构的带索引的点的List序列。

3 三维漫游路径的设定与实现

3.1 静态视景体概念

若要理解物体如何显示在屏幕上，必须理解投影。视觉相关的投影有两种，一为正视投影，一为透视投影。正射投影的最大一个特点是无论物体距离相机多远，投影后的物体大小尺寸不变。这种投影通常用在建筑蓝图绘制和计算机辅助设计等方面，这些行业要求投影后的物体尺寸及相互间的角度不变，以便施工或制造时物体比例大小正确。

图6 正视投影示意图

但是正视投影与人眼成像是不相符合的，因为视点不可能达到无线远。

图7 透视投影示意图

相对而言，透视投影更适合，该投影将近远两平面内的物体，以一定比例投影到近平面上。这样我们可以透过确定视点位置、视角、近平面距离、近平面高度，远平面距离来唯一确定一个梯形块，即为视景体［10］。该视景体内的物体均会通过透视投影显示到屏幕（前平面）上。

3.2 三维漫游的实现

从相对论的角度而言，有两种方式可以让视景体动起来，一为视点位置不变，变换视景体内的物体，一为物体坐标不变，动态改变视点的位置。对于三维点云模型而言，显然第二种方式更为适合。

本文使用前节算法所得到的骨线，将进行拉普拉斯平滑后的骨线序列点作为视点，设定特定方向的视景体，然后不断地在骨线一端上不断取点，设为视点，那么视景体不断变化，显示在屏幕上，即为三维漫游。

4 实验结果与分析

本文实验的软件环境为：Windows10 32位操作系统，VS2010集成开发环境，PCL库版本号为1.7.1，ANN库版本1.1.2，OpenGL3.0，并采用MFC做了简单的界面显示。

图8为算法过程截图及三维漫游部分截图。很直观的，骨线的形状随外部点云模型的几何特性而改变，具有一定的鲁棒性。

图8 井下巷道三维漫游实验结果图

本文还特意针对其他模型点云进行了骨线提取算法时间进行统计，如下表。如表中所示，算法对复杂点云模型依然有很好的效果，且时间随点数增加而变长。

表1 骨线算法实验数据

图9 骨线提取算法效果图

5 结语

本文给出了一种由三维点云模型获取路径的新方法，即先对点云模型进行骨线算法的提取，基于骨线信息制定路径，调整视点，实现三维场景漫游。此方法针对工程领域的场景漫游，很好地提高了路径的准确性并极大地缩减了三维大场景漫游的工作周期。

［1］葛翔.基于OpenGL的三维建筑仿真与漫游技术研究［D］.武汉：武汉理工大学，2006.GE Xiang.Research on 3D Building Simulation and Roaming Technology Based on OpenGL［D］.Wuhan：Wuhan University of Technology，2016.

［2］蒋盛锋.基于三维激光雷达的井下巷道场景漫游系统设计［J］.计算机与数字工程，2016，44（9）：1719-1722.JIANG Shengfeng.Design of Underground Roadway Roaming System Based on 3D Lidar［J］.Computer and Digital Engineering，2016，44（9）：1719-1722.

［3］Andrea Tagliasacchi，Hao Zhang 0002，Daniel Cohen-Or.Curve skeleton extraction from incomplete point cloud.［J］.ACM Trans.Graph，2009，28.

［4］刘艳丰.基于kd-tree的点云数据空间管理理论与方法［D］.长沙：中南大学，2009.LIU Yanfeng.The theory and method of point cloud data space management based on kdtree［D］.Changsha：Central South University，2009.

［5］Xiao Liang，Hongyu Yang，Yinling Qian，Yanci Zhang.A Fast Kd-tree Construction for Ray Tracing based on Efficient Ray Distribution［J］.Journal of Software，2014，93.

［6］Artur Santos，João Marcelo Teixeira，Thiago Farias，Veronic Teichrieb，Judih Kelner.Understanding the Efficiency of kD-tree Ray-Traversal Techniques over a GPGPU Architecture［J］.International Journal of Parallel Programming，2012，403.

［7］Hui Huang，Shihao Wu.L1-Medial Skeleton of Point ACM Transactions on Graphics，July 2013 ArticleNo.65.

［8］Weiwei Li，Xiaoli Wu，Weizhou Jiao，Guisheng Qi，Youzhi Liu.Modelling of dust removal in rotating packed bed using Artificial Neural Networks（ANN）［J］.Applied Thermal Engineering，2016.

［9］ Xiaoxiao Niu，Chuanlei Yang，Hechun WangYinyan Wang.Investigation of ANN and SVM based on limited samples for performance and emissions prediction of a CRDI-assisted marine diesel engine［J］.Applied Thermal Engineering，2016.

［10］黄常标，江开勇，林俊义.基于OpenGL视景体的三维CAD模型交互显示研究［J］.机械设计与制造，2011（10）：74-76.HUANG Changbiao，JIANG Kaiyong，LIN Junyi.Research on Interactive Display of 3D CAD Model Based on OpenGL view volume［J］.Mechanical design and manufacturing，2011（10）：74-76.

Roaming Path Searching of 3D Scene Based on Skeleton Curve Extraction Algorithm of Point Cloud Model

ZHANG ShuangxingZHANG Xing
（School of Automation，Huazhong University of Science and Technology，Wuhan 430074）

In this paper，one-dimensional skeleton curve representing the whole structure information of three-dimensional point clouds is obtained by gradually increasing the radius of the sampling points'neighbour and calculating the skeleton curve points by iterations.Then，by using the information of the skeleton curve of the point cloud，this method can improve the searching method of the inner roaming path of 3D scene.The experimental data in this paper are three-dimensional chaotic point cloud model of coal mine underground roadway.The experiment shows that this improvement can improve the accuracy of the path and greatly reduce the work cycle of 3D large-scale scene roaming.

point cloud processing，skeleton curve extraction，3D Roaming，OpenGL

TP391

10.3969/j.issn.1672-9722.2017.10.027

Class Number TP391

2017年4月9日，

2017年5月29日

张双星，男，硕士研究生，研究方向：三维点云数据处理及可视化。张星，男，硕士研究生，研究方向：三维点云数据处理，机器视觉与图像处理。