基于特征数据分块自适应切片的空洞修补

何桂珍

（华东交通大学土木建筑学院，江西南昌330013）

基于特征数据分块自适应切片的空洞修补

何桂珍

（华东交通大学土木建筑学院，江西南昌330013）

针对常用的空洞修补方法在修复具有多种曲面类型的空洞时失效和所修复的曲面不光顺等缺点，提出基于特征数据分块自适应切片的空洞修补。首先，在考虑特征信息的情况下基于聚类对散乱点云进行分块；然后利用特征进行自适应切片，获得曲线并进行拟合；最后，在线上取点填充缺失的点云，最终对完整的点云模型进行曲面重构建立实体模型。试验结果表明，采用自适应切片法修补空洞能够保留特征，所填充的点云数据精度较高，能够满足后续建模的需要。此外对该方法填充的点云进行了曲面重构及光顺，结果令人满意。

空洞修补；自适应切片；特征数据分块；散乱点云；虚拟修复

研究三维激光扫描技术逐步成为测绘界的一个热点，利用三维激光扫描仪采集数据过程中，由于环境影响或物件本身的损坏，使获得的样件表面数据存在一些不希望有的“空洞”［1］。这些空洞影响模型的重建及零件加工等后续处理，因此必须对这些数据空洞进行修补。空洞修补在航空、航天、船舶、汽车和模具等制造业得到了广泛的应用，也可应用于修复破损的艺术品或者被损零件［2］，例如修复破损的雕像、雕刻；修复由于常年使用造成的船舶破损；修缮古建筑等。此时并不需要对整个原型进行复制，而只需借助于逆向工程技术提取需要修复的零部件以实现缺损空洞的定位和逆向建模，仿真缺损物体的修理工艺，实现修复技术的现代化。在研究修复过程中，需要对三维激光扫描测量技术获取的点云数据进行空洞修复研究。

目前，比较常用的空洞修补方法是根据空洞周围的局部离散点来建立一张曲面片，然后采用面上取点的策略补出空洞部位所缺的点［3-5］。国内代表性的研究者邱泽阳提出的空洞识别算法首先通过人工交互的手段在空洞附近提取不共线的3个点，构成一个三角形，然后将局部测试点向该三角片所在平面投影，构造初始三角Bezier曲面片，并进行迭代求解，最后在满足条件的三角曲面片中取点，完成空洞修补；通过确定空洞邻近域的特征面和以特征面为基础的局部坐标系后，建立基于移动最小二乘法的隐式曲面，将空洞多边形变换到空洞局部坐标系下，并将空洞多边形投影到特征面上，然后对投影空洞多边形重新采样，最后将重新采样点的u，v坐标值代入计算出的隐式曲面函数方程，得到空洞填充点［6］。

从以上算法分析可知，都是将空洞看成是一种曲面区域，当空洞所在的区域为几种曲面区域时或者多个数据分块区域，上述方法就会失效。本文正是针对以上缺点提出的，所设计的修补方法适用于多种曲面的修补。克服特征信息缺失、所修复曲面不光顺等不足，这些优势可将该方法很好地应用于修复破损的雕像、雕刻或者复杂的破损零件。

1 算法概述

为了能够使修补的虚拟点云数据保持特征信息，就要实现自适应切片能够过特征点，即保持小特征，所以首先必须实现散乱点云特征提取，然后在保留特征的情况下进行自适应切片，具体算法如下：

1）基于特征的数据分块：首先用基于平均曲率的特征权值方法提取特征点，并用最小生成树连接成特征线［7］，然后通过聚类方法依据8种基本曲面类型将散乱数据点进行粗略划分，在所求的特征线约束下对曲面进行精确分块。

2）基于特征的自适应切片修补空洞：利用米形进行自适应切片，将所有切片通过特征性的区域拟合求交，对过空洞的切片进行曲线拟合，利用权值在曲线上取点，获得空洞区域填充的虚拟点云。

3）填充点云的曲面网格重构：在已有的空洞边界约束下利用射线法将填充的缺失点云进行逐层的表面重建，以利于表面特征信息的保留。具体修补流程如图1所示。

图1 空洞修补流程图Fig.1 Flowchart of patching hole

1.1 基于特征的数据分块

特征点提取阶段的主要任务是为点云中的每个采样点设置一个权值，使之与该点隶属于特征点的可能性大小成正比关系，称为特征权重。本文采用基于平均曲率的特征权值［8］。本文研究对象为散乱点云，采用局部曲面拟合的方法估算曲率，曲率越大，表示曲线或者曲面的弯曲程度越大。首先用该方法提取特征点，并用最小生成树连接成特征线，然后通过聚类方法依据8种基本曲面类型将散乱数据点进行粗略划分，在所求的特征线约束下对曲面进行精确分块。

利用计算出的高斯曲率和平均曲率根据Besl［9］提出的8种基本曲面类型将曲面初步分块。如果把相同类型的点组成一个曲面，就可得到8种基本曲面，任意复杂曲面可以由这8种基本曲面块组成。任意两曲面的接触边界散乱数据点，利用最小生成树连接形成特征线，在特征线的约束下，从一“种子点”开始，该点的类型就是块的类型，进行“区域生长”，找出具有相似特征的一组点构成一曲面片，直至周围邻域没有特征一致的点，且特征点的个数大于某一阈值，否则认为该特征点为噪音点而删除，获得精确曲面分块。

1.2 基于特征的自适应切片修补空洞

点云切片的实质是用某平面和点云进行求交得到的切片曲线，在实际应用中，由于点云密度总是有限的，不可能构造一条完整的截面曲线，所以可通过给定一个合适的带宽，这一带宽称为切片厚度δ，δ是一个比较难以确定的参数，以往研究者都使用了同一个切片厚度，但由于切片层有一定厚度，所以就会出现切片层范围内小特征遗失现象。针对此类问题，本文提出了一种基于特征的自适应切片方法，具体实现步骤如下：

1）随机计算n个点的k近邻点，n个点与其近邻点的平均距离表示点云密度，将密度值乘以层厚系数得切片厚度，通过邻域数据点配对连线并与切片求交获取切片数据点。该方法依据点云密度确定层厚，利用相同切片层厚进行初切片。

2）根据所提取的物体外边界线［10］，计算关联边界点的数据块Ft（t=0，1，2，…，k-1），拟合求特征交线，利用通过特征点位置增加切片，当确定切片平面位置时，需要自适应的根据与切片相垂直的散乱点云平面的曲率变化情况确定切片厚度。

3）计算散乱点云的质心，然后过质心做与切片平面相垂直的平面（设为m个，每个平面的旋转角360/m），则利用前述切片平面技术，获得m条截面曲线。根据曲率值变化，自适应地确定切片层厚度；依据横向水平层的点形成的曲线曲率变化程度给数据点分别赋予不同权值，然后对横向水平层依次旋转45度角，形成米字形切片层。

4）所有切片通过特征线的区域拟合求交，而不是在该区域通过散乱点求交获得切片数据点；切片通过平面数据分块区域时，数据点通过平面求交获得。

5）对过空洞的切片进行曲线拟合，根据曲线类型定义不同的权值，利用权值在曲线上取点，获得空洞区域填充的虚拟点云，如图2所示，为水平方向的切片填充的虚拟点，其他方向的切片也作相同的处理。

图2 基于自适应切片填充空洞Fig.2 Patching hole based on adaptive slicing

用本方法填充的虚拟点云，不仅与周围点之间光滑连续，同时，考虑空洞包含有不同曲面类型，填充的点云能够保持特征信息且分布也比较均匀，非常适合后续曲面构造的需要。

1.3 填充点云的曲面网格重构

为了提高修补效率，有时只需对所修补的虚拟点云进行曲面网格重构，而虚拟修复就是利用填充的虚拟点云重构曲面模型作为一个应用模块来替换或修补已损坏部分。在完成空洞边界提取和空洞填充的基础上，在已有的空洞边界约束下利用射线法将填充的缺失点云进行逐层地表面重建，以利于表面特征信息的保留。该方法主要思想是利用层剥法理论［11］。

1）计算自适应切片填充的虚拟点云的最小包围盒，然后利用八叉树数据结构进行组织，建立拓扑关系。

2）对于包围盒中的任一输入点p，根据上节介绍的方法计算该点的k近邻域并估计其法矢方向n，然后沿着n或者n的反方向确定一条射线。

3）判断该射线是否通过了全局法向映射测试：如果法向射线和八叉树中一个包含点的叶节点相交，该点沿着测试法向与其他表面片相交，认为该点q没有通过全局法向映射测试；相反，如果点p沿着法向n的射线和八叉树相交的节点均为空节点，则认为点p通过测试，如图3所示。

图3 全局法向映射测试Fig.3 Global normalmapping test

4）将最外层通过全局法向映射测试的散乱点作为同一投影平面内的二维点，以p为三角中心构建种子三角片，依据逐层生长法通过种子三角片构建三角网格模型。

5）完成最外层表面重建之后，再循环执行以上步骤，直到层层表面重建之后完成填充曲面模型重构完毕。

2 试验结果

为了验证本文方法的稳健性和可靠性，作者进行了实验验证。实验曲面包含多种曲面类型，不能用一种简单曲面进行处理，根据数据分块的方法，将空洞曲面类型分类，图中空洞区域有三种不同的曲面类型，分别用不同的颜色进行了表示，对每一同曲面进行修复，最终实现整个空洞修复。实验结果表明，该修复方法能够很好地保留不同曲面类型。

图4 空洞区域具有多种曲面类型的曲面修复Fig.4 Surface repair for hole area with a variety of surface types

为了评价本文方法的稳健性和适用性，从所修复曲面模型、修复误差和修复效率等方面横向比较该方法的优越性。比较效果如图5所示。

图5 两种方法修复曲面效果图Fig.5 Repaired surface by two ways

从图比较可知，本文提出的方法可以很好地保留模型的特征信息，文献［6］对于这种复杂曲面只能识别出存在一条空洞边界线，进行曲面修复后反面模型仍然存在空洞，而且模型的特征信息没有很好地被保留，所以从效果图可以直观地判断出本文方法更优越。

不但定性地比较各方法，还要从定量的角度实现精度评价，本实例应用修复后的曲面模型利用点到距离评价方法进行误差评定，为了从多角度比较各方法的优越性，增加时效性这一参数，计算结果如表1所示。

表1 复杂曲面修复分析结果Tab.1 Analysis of surface repair results

对表中的数据进行归纳分析，可得出以下结论：①对于这类具有复杂多类型的空洞应采用本文方法，修复精度高，最大修复误差都不超过1mm，平均误差很小；②文献方法由于没有考虑多种曲面类型和特征，所以造成曲面修复误差较大，最大误差达到2mm。由于本文方法在修复时考虑了特征信息，所以曲面上的复杂信息能很好地保留。

通过直观的曲面修复效果、修复误差、修复效率等三方面的分析归纳，可得出以下结论：本文方法适应性强，能够保留复杂曲面的特征信息，在修复雕像、古建筑等复杂物体时，优势较大。

3 结束语

针对曲面虚拟修复中的空洞修补问题，提出了一种保留特征的空洞修补方法，该方法通过计算曲数据进行粗略分块，在所求的特征线约束下对数据进行精细分块；基于特征数据块利用米形进行自适应切片，获得切片曲线并进行拟合，在线上取点填充缺失的点云，最终对完整的点云模型进行曲面重构建立实体模型。通过实验验证，本文提出的方法有较强的稳健性和适应性，不仅具有特征保留作用，而且不需要求“单类型”曲面，可很好地避免多种曲面类型修复不能保留特征和光顺等问题，能适应多种复杂曲面。

[1]姜振宇.逆向工程中点云孔洞填充算法的研究[J].机械制造,2005(43):43-45.

[2]龚志远,付伟.利用三坐标测量"点云"的曲面反求设计[J].华东交通大学学报,2004,21(5):116-118.

[3]PAVEL C,BERT J.Filling holes in point clouds[C]//Lecture Notes in Computer Science,2003:196-212.

[4]LIEPA P.Filling holes inmeshes[C]//Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, 2003:200-205.

[5]DAVIS J,MARSCHNE S R,GARR M,et al.Filling holes in complex surfaces using volumetric diffusion[C]//First International Symposium on 3D Data Processing,2002:428-861.

[6]邱泽阳.离散数据中的孔洞修补[J].工程图学学报,2004(4):85-89.

[7]蔡利栋.关于KH和KJ符号图的一些注解[J].中国图像图形学报,1998,7(3):562-564.

[8]BESL P J,JAIN R C.Segmentation through variable-order surface fitting[J].IEEE Transaction on Pattern Analysis and Machine Intelligence,1988,10(2):167-192.

[9]范德营,蒋先刚,丘赟立,等.车载红外视频图像快速彩色化技术研究[J].华东交通大学学报,2013,30(2):71-77.

[10]程效军,何桂珍.适用于多值曲面修复的空洞边界提取方法[J].测绘学报,2012(4):85-89.

[11]LIM C W,TAN T S.Surface reconstruction by layer peeling[J].The Visual Computer,2006,229(11):593-603.

Hole Patching of Adaptive Slicing Based on Feature-data Segmentation

He Guizhen
(School of Civil Engineering and Architecture,East China Jiaotong University,Nanchang 330013,China)

Since common hole patchingmethods have some shortcomings,such as failure in repairing a variety of surfaces or repaired surfaces being not smooth,a new hole patchingmethod is presented which uses adaptive slic⁃ing based on the feature data segmentation.Firstly,scattered point cloud is segmented based on cluster under the consideration of feature information;then adaptive slicing generates curves to be fitted with the features.Finally, virtual points are chosen from the curves to fill themissing parts of the point cloud.The surface of the complete point cloud is reconstructed to establish a physicalmodel.Test results show that the adaptive slicingmethod can keep patching hole feature and have high accuracy of filled point cloud,which canmeet the needs of the subse⁃quentmodeling.In addition,the results of surface reconstruction and smoothing obtained are satisfactory.

hole-patching;adaptive slicing;feature data segmentation;scattered point cloud;virtual repair

P234

A

2014-04-03

江西省青年科学基金项目（20142BAB217032）

何桂珍（1983—），女，讲师，博士，研究方向为近景摄影测量与三维建模。

1005-0523（2014）04-0095-05