西南师范大学学报(自然科学版)   2019, Vol. 44 Issue (7): 87-92.  DOI: 10.13718/j.cnki.xsxb.2019.07.014
0
Article Options
  • PDF
  • Abstract
  • Figures
  • References
  • 扩展功能
    Email Alert
    RSS
    本文作者相关文章
    孔德武
    欢迎关注西南大学期刊社
     

  • 点云数据的三角剖分及计算机三维重建    [PDF全文]
    孔德武     
    河南工业和信息化职业学院 信息工程系, 河南 焦作 454000
    摘要:为了解决直接剖分法因点云数据拓扑结构复杂出现的自交现象,提出了一种基于分治策略的三角剖分方法.首先,对原始点云数据进行平面投影并执行区域分割;其次,在每一个区域内进行直接剖分,剖分过程遵循异侧剖分准则、法向量夹角最大剖分准则、阈值距离剖分准则、最小内角最大剖分准则.最后,按照空间Delaunay剖分准则完成区域之间的连接.实验结果表明,该文提出的剖分方法对于规则曲面点云和非规则曲面点云都具有理想的剖分效果,并且执行速度快.
    关键词点云数据    三角剖分    分治策略    三维重建    

    计算机仿真技术日益完善,使得虚拟现实、逆向工程等领域获得了快速发展[1].通过使用各种扫描设备获得真实物体的三维点云数据后,运用计算机三维重建仿真技术可以由点到线、由线到面完成点云到曲面的重建,在计算机上恢复出形象逼真的真实实物仿真形态[2].在点云数据的三维重建过程中,将三维点云数据进行一定规则的连线是曲面重建的基础.根据连线后形成的形状不同,可以分为三角剖分和多边形剖分[3].三角剖分可以为曲面重建提供最小的形状单位,有利于曲面形状的逼真重建,因此成为各种剖分中的主流技术.根据原理不同,三角剖分大致可以划分为平面投影法和直接剖分法两大类[4-5].平面投影法,先将三维点云数据投影到二维平面上,进而在平面上完成剖分,再将三角形各点的深度信息添加进去形成空间剖分效果[6].直接剖分法是在点云数据的中间位置开始构建第一个三角形,进而逐步添加周围的点,即直接在三维空间上进行剖分[7].无论是平面投影法还是直接剖分法,都需要借助一定的规则,选择更加合适的新点加入剖分过程.这些常见的规则有最小内角最大规则、最大空圆规则等等[8-10].采用平面投影法完成剖分,因为事先忽略了深度信息,有可能造成大量狭长三角形出现[11];采用直接剖分法完成剖分,当曲面散乱点集数据量庞大或拓扑结构复杂时容易产生自交现象,即新的三角面片与已有的三角面片在非公共边处产生自交[12].鉴于这两类方法都存在一定程度的问题,本文将构建一种基于分治策略的三角剖分方法,用于实现点云数据的计算机三维重建.

    1 基于分治策略的点云数据三角剖分方法 1.1 方法的设计思路

    直接剖分法可以避免平面投影法中出现的狭长三角形,并且执行的速度也比较快,但是受到点云拓扑结构复杂性的影响,在很多情况下会出现自交现象.为了发挥直接剖分方法的优势,本文提出一种基于分治策略的三角剖分方法,通过点云数据的区域分割、在区域内完成剖分,有效降低点云数据总体结构复杂性的影响,以避免自交问题的出现.整个方法的实现分为3个步骤:

    第一步,对点云数据进行区域分割.将已知的点云数据按照预定规则进行区域划分,这样分割成的区域将成为后续剖分的基础.因为每个区域内的点云数据量大为降低,其拓扑结构复杂性也大为降低,不会形成自交问题.

    第二步,在第一步分割出的各个区域内独立进行三角剖分,剖分过程按照一定的剖分准则进行,充分发挥直接剖分方法速度快的优势.

    第三步,将各个区域的剖分结果进行连接.因为各个区域内的剖分形成了相互独立的边界,为了实现各剖分区域之间的连接,将按照空间Delaunay方法进行边界处的剖分连接.

    1.2 点云数据的区域分割

    点云数据呈现三维形态空间分布.因此,为了进行有效的区域分割,需要先将这些点云数据投影到二维平面,在二维平面上进行区域分割.但是,投影过程中可能会出现两种情况,第一种情况就是所有点云数据在xyz坐标系下的x投影和y投影均无重叠现象,故只需按照各点的x坐标和y坐标排序后进行区域分割即可;第二种情况就是一部分点云数据在xyz坐标系下的x投影和y投影有重叠现象.这两种情况如图 1所示.

    图 1 点云数据的区域分割处理效果

    在实际操作中,如果出现第一种情况,即所有点云数据无重叠的情况,就直接向平面进行投影然后进行区域分割就可以了.如果出现第二种情况,即部分点云数据有重叠的情况,加入一个分割面β,将点云数据划分为两个子集合,再对每一个子集合内的数据进行分别投影,然后再各自进行区域划分.

    在实际情况中,可能会出现更为复杂的局面,如点云数据为褶皱式闭合曲面,这就需要加入更多的分割平面,避免出现重叠.

    区域分割的标准,应该确保每个区域内的点云数据量,其拓扑结构的复杂性不足以在直接剖分过程中产生自交现象.

    1.3 各个区域内的剖分

    经过区域分割后,原始点云数据被划分为一个个独立的区域,接下来的工作就是按照直接剖分方法的策略,在每一个区域内进行三角剖分.首先在区域中心选择2个点进行连线,条件是这2个点的距离比其他点近,其后就按照4个剖分准则逐步加入新点,完成剖分工作.这4个剖分准则的示意情况如图 2所示.

    图 2 局域内剖分的四个准则示意效果
    1.3.1 异侧剖分准则

    所谓异侧剖分准则,就是确定了一个三角形以后,再次寻找新点连接新的三角形时,必须使新点满足和剖分边所对应的第三顶点在剖分边的两侧,这一准则的效果如图 2(a)所示.在图 2(a)中,三角形△ABCAB边为待剖分边,根据空间解析几何的基本方法,就可以求得三角形△ABC的法向量n1,并且这个法向量的方向是从顶点A指向顶点B的右手螺旋定则方向.如果点P和点P′为可能加入的2个新点,那么可以计算出三角形△ABP的法向量n2,这个过程一样要保证这个法向量的方向是从顶点A指向顶点B的右手螺旋定则方向.至此,就可以计算出2个法向量之间的夹角余弦值cosα1.如果cosα1 < 0,那么就表明P点和C点分别位于AB这条边的两侧;如果cosα1>0,那么就表明P点与C点位于AB这条边的同侧.

    1.3.2 法向量夹角最大剖分准则

    所谓法向量夹角最大剖分准则是指,三角剖分过程中为了使得剖分后的空间曲面尽可能地光滑连续,需要满足剖分得到的新三角形和原三角形之间的法向量夹角最大.对照图 2(b),在边AB进行新三角形引入时,如果P点和P′点都满足异侧准则,需要进一步根据法向量夹角最大剖分准则完成新点的选择,也就是分别计算法向量n2与法向量n1、法向量n3与法向量n1所成的角度.可见,法向量n2与法向量n1所成的角度较大,这就表明P点优于P′点,因此应选择P点作为新点进行剖分.

    1.3.3 阈值距离剖分准则

    所谓阈值距离剖分准则,就是新点和剖分边之间的距离应在一个合理的阈值范围内.如图 2(c)所示,P点位于P′点下方,根据法向量夹角最大剖分准则应该选择P′点进行剖分.可是,P′点到AB边的距离远远超出了设定阈值,如果选择此点会出现狭长三角形进而导致曲面细节丢失.因此,这里的新点选择,根据阈值距离剖分准则仍然要选择P点.

    1.3.4 最小内角最大剖分准则

    所谓最小内角最大剖分准则,就是要新点加入后的剖分结果,形成的三角形最小内角应该尽可能地大.如果2个待选新点都满足向量夹角最大剖分准则和阈值距离剖分准则,那么就需要进一步执行最小内角最大剖分准则完成选点.在图 2(d)中,∠1是三角形△ABP的最小内角,∠2是三角形△ABP′的最小内角,经过比较可以看出∠1>∠2,故选择P点完成剖分优于P′点.

    1.4 各个区域间剖分结果的连接

    按照前述的处理,空间点云数据已经被分割成多个区域并在区域内完成了三角剖分.接下来,需要将这些区域的剖分结果连接起来.由于各区域剖分结果都形成了既定边界,无法继续按照前面的准则进行区域间连接.因此,选择空间Delaunay空圆准则进行区域间的连接剖分.需要注意的是,Delaunay剖分会产生新点,从而在一定程度上改变原有区域内剖分结果,但效果是使得剖分结构更加光滑连续,重建后曲面的视觉效果更好.

    2 点云数据的计算机三维重建实验

    验证本文提出的基于分治策略的三角剖分方法对于点云数据的剖分效果和重建效果,分别展开2组实验研究,①规则曲面点云数据的三角剖分实验,②非规则曲面点云数据的三角剖分实验.

    2.1 规则曲面点云数据的三角剖分实验结果

    规则曲面的实验点云分别选择了三维球面点云、Z曲面点云和LOG算子曲面点云.经过本文剖分方法获得的剖分结果如图 3所示.

    图 3 规则曲面点云数据的剖分实验结果

    图 3中的结果可知,按照本文提出的三角剖分方法完成点云数据剖分,形成的三角网格均匀连续,视觉效果逼真生动,较好地复原出了点云数据所对应的曲面.进一步观察3个曲面剖分重建完成的时间,如表 1所示.

    表 1 规则曲面点云数据的剖分时间

    表 1中的数据可知,本文提出的三角剖分方法对于规则曲面点云数据的剖分重建速度也是比较快的.

    2.2 非规则曲面点云数据的三角剖分实验结果

    第一组实验结果充分表明了本文提出的基于分治策略的三角剖分方法,对于规则曲面的点云数据具有理想的重建效果,不仅剖分和重建的视觉效果好,而且执行速度快.

    为了验证本文提出的剖分方法所具有的鲁棒性,进一步对非规则曲面、数据量较大的点云数据进行剖分实验,实验结果如图 4所示.

    图 4 非规则点云数据的剖分及重建结果

    图 4可知,这组点云的重建结果清晰地显示出一个人头像的形状.这组点云不仅数量大,而且同第一组实验相比是明显的非规则点云,同时表现出水平方向系数、垂直方向稠密的特征.经过本文方法的处理,获得了比较理想的三角剖分结果和重建结果.此组点云中点的数据量为4 822个,经过本文方法处理,剖分时间仅仅为5.634 s.

    3 结论

    在点云数据的三角剖分方法中,平面投影法会导致大量狭长三角形出现,直接剖分法会因点云拓扑结构的复杂性出现自交现象.为此,本文提出了一种基于分治策略的三角剖分方法.通过投影将复杂点云进行区域分割,之后在各个区域内按照四大准则进行三角剖分,最后执行Delaunay空圆准则完成区域之间的连接.针对规则曲面点云和非规则曲面点云分别执行剖分实验,实验结果表明,本文的剖分方法对于两类点云数据均具有理想的剖分效果,剖分重建出的曲面具有逼真的视觉效果,并且剖分速度快.

    参考文献
    [1]
    LHUILLIER M. Overview of Shelling for 2-Manifold Surface Reconstruction Based on 3D Delaunay Triangulation[J]. Journal of Mathematical Imaging and Vision, 2017, 59(2): 318-340. DOI:10.1007/s10851-017-0734-4
    [2]
    倪皓晨, 伍钟洁, 郏建, 等. 一种基于Delaunay三角网的栅格线划矢量化方法[J]. 武汉大学学报(信息科学版), 2016, 41(2): 184-189.
    [3]
    袁小翠, 吴禄慎, 陈华伟. Delaunay三角剖分算法改进与对比分析[J]. 计算机应用与软件, 2016, 33(9): 163-166. DOI:10.3969/j.issn.1000-386x.2016.09.039
    [4]
    WANG X J, XING F, LIU F. Stereo Matching of Objects with Same Features Based on Delaunay Triangulation and Affine Constraint[J]. Acta Optica Sinica, 2016, 36(11): 1115004. DOI:10.3788/AOS
    [5]
    王向军, 邢峰, 刘峰. Delaunay三角剖分和仿射约束的特征相同多物体同名点立体匹配[J]. 光学学报, 2016, 36(11): 197-204.
    [6]
    张蓓蓓, 李国清, 冯梅, 等. 基于Delaunay三角剖分的多尺度POI提取技术研究与实现[J]. 测绘与空间地理信息, 2018, 41(6): 119-121, 125. DOI:10.3969/j.issn.1672-5867.2018.06.035
    [7]
    ALAEDDINI A, MOTASEMI A, FARUQUI S H A. A Spatiotemporal Outlier Detection Method Based on Partial Least Squares Discriminant Analysis and Area Delaunay Triangulation for Image-Based Process Monitoring[J]. ⅡSE Transactions, 2018, 50(2): 74-87.
    [8]
    夏俊, 李映华. 球面凸类图形Delaunay三角剖分再分算法及其收敛性分析[J]. 计算机应用, 2017, 37(12): 3558-3562. DOI:10.11772/j.issn.1001-9081.2017.12.3558
    [9]
    HAKLı H, UĞUZ H, ÇAY T. A New Approach for Automating Land Partitioning Using Binary Search and Delaunay Triangulation[J]. Computers and Electronics in Agriculture, 2016, 125(10): 129-136.
    [10]
    寿涛, 刘朝晖. 基于Delaunay三角剖分处理二维欧式空间MTSP的近似算法[J]. 华东理工大学学报(自然科学版), 2017, 43(6): 895-898.
    [11]
    BOISSONNAT J D, DYER R, GHOSH A, et al. An Obstruction to Delaunay Triangulations in Riemannian Manifolds[J]. Discrete & Computational Geometry, 2018, 59(1): 226-237.
    [12]
    CAROLI M, TEILLAUD M. Delaunay Triangulations of Closed Euclidean d-Orbifolds[J]. Discrete & Computational Geometry, 2016, 55(4): 827-853.
    Triangulation and Computer Three-Dimensional Reconstruction of Point Cloud Data
    KONG De-wu     
    Department of Information Engineering, Henan Vocational College of Industry and Information Technology, Jiaozuo Henan 454000, China
    Abstract: In order to solve the self-intersection of point cloud data caused by complex topological structure, a triangulation method based on divide-and-conquer strategy has been proposed. Firstly, the original point cloud data are projected on a plane and partitioned into regions. Secondly, each region is partitioned directly. The partitioning process follows the criteria of lateral partitioning, maximum normal vector angle partitioning, threshold distance partitioning and maximum minimum internal angle partitioning. Finally, the connection between regions is completed according to the spatial Delaunay partition criterion. The experimental results show that the proposed method has ideal segmentation effect for both regular and irregular surface point clouds, and the execution speed is fast.
    Key words: point cloud data    triangulation    divide and conquer strategy    three-dimensional reconstruction    
    X