半自动点云模型线性骨架提取技术

摘  要：本文基于ROSA（Rotational Symmetry Axis）和中轴的骨架提取算法，搭建一个半自动的点云模型线性骨架提取实验平台，系统地分析了基于勾画的交互方式进行点云模型骨架提取的实验平台的结构与特点，并阐述了骨架结点位置提取、骨架连接关系提取、骨架编辑等各个功能模块在实验平台中的具体实现和功能，最后对实验平台的开发工作进行了总结。

关键词：点云;点云法向量;ROSA;线性骨架提取

中图分类号：TP391.41      文献标识码：A 文章编号：2096-4706（2019）08-0089-03

Abstract：Based on ROSA（Rotational Symmetry Axis）and mid-axis skeleton extraction algorithm，this paper builds a semi-automatic linear skeleton extraction experimental platform for point cloud model，systematically analyses the structure and characteristics of the experimental platform for point cloud model skeleton extraction based on skeleton-based interactive method，and expounds the skeleton node location extraction，skeleton connection extraction，skeleton editing and other functional modules in the experimental platform. Finally，the development of the experimental platform is summarized.

Keywords：point cloud;point cloud normal vector;ROSA;linear skeleton extraction

0  引  言

模型的线性骨架既保持了原始模型的拓扑结构，同时又能够反映模型的形状，能够大幅度减少模型的冗余信息。受点云数据获取技术的限制，扫描得到的原始点云数据中噪声、外点和孔洞等不可避免，为了让计算机正确理解模型的外观，从不理想的点云数据中准确提取线性骨架有待进一步研究和探讨。

1  研究背景及意义

现存的点云的线性骨架提取算法[1-9]受原始点云数据的限制，在自动提取线性骨架时，容易出现理解模型外观不正确的现象，想要得到正确的点云模型的线性骨架，就需要人工干涉。本文基于ROSA和中轴的骨架提取算法，开发半自动的交互式线性骨架提取实验平台，让用户参与并体验骨架提取的过程;同时，利用本系统人工勾画输入，交互式编辑自动提取出来的存在误差的骨架，借助人为干涉修改线性骨架，提高结果骨架的准确性。

2  点云数据的预处理

2.1  基于KD-树的k邻域

本系统先采用KD-树对点云在空间上进行分割，再查找k邻域。KD-树是区分k维空间中的数据点的平衡二叉树数据结构。KD-树按照一定的规则，把三维空间分割成多个空间。利用回溯算法，从树的底层自底向上扩大搜索范围，使用KD-树这种平衡二叉树的数据结构，查找最近点的时间复杂度约为O（nlogn），大幅度提高了在三维空间中搜索邻近点的效率。

2.2  点云法向量

法向量是三维点云数据的一个重要局部特征，其获取方法主要有：通过光度立体法来获取，或者通过计算得到。一般三维扫描获得的采样点的信息只是记录每一个离散点的空间坐标数据，并未记录点间的相互关系。点的法向量主要通过对局部点云集合的属性进行分析，采用二次曲面拟合或平面拟合得到采样点的法向量。

3  半自动线性骨架提取系统

本系统的输入是三维模型的点云数据，用户借助触摸屏简略勾画，系统根据切割平面的邻近关系计算出该笔画在三维空间中对应的点集;然后选择合适的算法计算出对应点集的几何中心，得到新的骨架结点。选择骨骼增加功能时，用户在屏幕上点击任意两个骨架结点后，系统自动计算这两个结点的连接关系，把连接这两个结点的骨骼存入骨架表中;选择骨骼删除功能时，用户只需单击对应骨骼即可把该骨骼信息从骨架表中刪除，最终得到新的骨架。

3.1  半自动骨架提取实验平台

近六十年来，模型骨架提取方面出现各种骨架提取算法，然而精准度高通适性强的骨架提取算法仍未找到。丢失大量重要数据的点云模型，更加难以实现准确的骨架提取，为此建立本半自动骨架提取系统，对三维离散点云模型展开骨架提取和骨骼编辑操作，得到更准确的点云模型骨架。系统的核心功能如下：中心点计算功能、勾画输入功能、交互功能、三维显示功能等。

3.2  骨架提取算法的实现

对点云进行立体空间区域划分是骨架提取的首要任务，第二步是通过计算得到点云法向量的近似值，接下来就是根据用户的判断，选择相应的最佳算法，计算得到准确度高的骨架结点。系统主要提供“中轴点提取法”和“ROSA点提取法”两种骨架结点计算方法。

3.2.1  骨架结点定义

（1）中心点的定义。在三维空间中，中心点就是到点集S中的每个点的距离平方和最小的点。如果切割平面的点集有重大缺失，则计算出的中心点不在正确中心位置，骨架结点采用中心点的前提是切割平面的点集相对完整，数据缺失不严重。

（2）ROSA点的定义。Tagliasacchi[2]等人率先提出：到点集S中的每个点的法线方向所在的直线平方距离和最小的点r就是ROSA点，也就是说，点集S对应的ROSA点r的坐标值xr满足：

其中，点集S中的任意一点表示为pi=（xi，vi）。ROSA点的法线方向vr满足：

其中，<，>表向量的夹角，vi为点集S中任意一点的法线方向。

利用ROSA点作为骨架结点的优势在于，利用点集S中所有点的法线方向，可以弥补数据大、面积缺失的不足。当出现有重大数据缺失的不完整点云时，利用仅存的少量点的法线方向信息可以高效弥补缺失，保持ROSA点的位置和方向的稳定。

3.2.2  最佳切割平面

设点pi=（xi，vi）是原始模型点云P中的任意点，切割平面为πi过点pi，其法向量为vi，点集Ni距离平面πi的距离小于δ，厚度值δ可变，其初值设定为整个点云模型的包围盒对角线长度的2%。利用欧几里得距离和马哈拉诺比斯距离确定切割平面的邻点集Ni。以pi为根展开广度优先搜索，递归增加切割平面πi附近的点。

利用过点pi的最佳切割平面πi*计算局部ROSA，关于点集Ni中的所有点的法向量旋转对称性最强的就是最佳切割平面的法向量。使用迭代逼近解决对应非线性的复杂优化问题。初始方向vi0经过下列变分问题使方向得到逐步更新：

（3）

Ni（t）是切割平面第t次迭代的邻点，n（pj）是点pj的单位法向量。当其能够被改写为最小化二次型vTMv，当‖v‖=1且M=时，式（3）有闭合形式解。

其中，x表示Ni（t）内点的法向量的x分量，y表示Ni（t）内点的法向量的y分量，z表示Ni（t）内点的法向量的z分量， 表示点集Ni（t）的平均值。

3.2.3  计算骨架结点位置

对于切割平面附近的点云数据，当其完整时，可以直接选择中心作为骨架结点;当其存在重大数据缺失时，需要选择利用ROSA算法，通过勾画输入的方式，定位点pi和过点pi的最佳切割平面πi*后，接下来计算局部旋转对称中心，即相应的ROSA点ri*，利用约束，定义该骨架结点的位置为：

Ni*是切割平面相关邻点，式（4）是标准的最小化二次型，其闭合形式解可以通过直接微分求出。

3.2.4  骨架连接关系位置的提取

在已经获取骨架结点的前提下，只需在骨骼添加模式下，点击两个骨架结点，系统通过两点的坐标计算得到三维空间中两结点之间的线性骨骼。为了便于用户对骨架进行修改，系统还具备交互式骨架编辑功能。用户可以根据自己的判断增删骨架结点或骨骼。

3.3  实验结果

使用的点云模型数据来自黄惠等人[8]研究点云的L1中值骨架的点云模型数据。对三维点云模型展开骨架提取时，用户根据模型点云数据特点，选择合适的算法计算相应的骨架结点，然后连接生成骨骼，直到完整的线性骨架提取完毕。借助人工辅助提取得到无误的骨架。

4  结  论

本文分析了基于ROSA的骨架提取算法的思路和优势，系统地分析了半自动可视化点云模型骨架提取的实验平台，详述了各功能模块的作用，能够为想了解三维点云模型骨架提取技术的人提供一定参考。点云骨架提取领域仍然有许多未知有待探索。

参考文献：

[1] 李义琛.点云模型骨架提取算法的研究与实现 [D].南京：南京师范大学，2012.

[2] Andrea Tagliasacchi，Hao Zhang，Daniel Cohen-Or.Curve skeleton extraction from incomplete point cloud [J].ACM Transactions on Graphics，2009，28（3）：1.

[3] 车武军，杨勋年，汪国昭.动态骨架算法 [J].软件学报，2003，14（4）：818-823

[4] 张绍广，李凤亭，马惠敏.一种基于权值的骨架算法 [J].微计算机信息，2007，23（6）：255-256.

[5] WU FC，MA WC，et al.Skeleton Extraction of 3D Objects with Visible Repulsive Force [C].Eurographics Symp. On Geometry Processing，2003.

[6] 王刚，高新波，姬红兵，等.基于区域增长技术的树状器官的骨架提取算法 [J].西安电子科技大学学报，2003，30（5）：594-597.

[7] 邹万红，陈志杨，叶修梓，等.一种新的点云数据特征骨架提取方法 [J].浙江大学学报（工学版），2008，42（12）：2103-2107.

[8] HUANG Hui，WU Shihao，Daniel Cohen-Or，et al.L1-Medial Skeleton of Point Cloud [J].ACM Transactions on Graphics，2013，32（4）：65.

[9] 段红娟.点云图像交互式曲线骨架提取技术及其应用 [D].成都：西南交通大学，2015.

作者简介：段红娟（1982-），女，汉族，湖北宜昌人，计算机应用讲师，硕士，研究方向：數字图像处理和模式识别。