-
随着逆向工程和三维建模技术的不断发展,三角网格模型被广泛应用于快速成型、虚拟现实以及工业设计中,并且贯穿于模型的整个生命周期。在三维激光扫描系统中[1, 2, 3],由于待测模型自身缺陷或采样点数据不足等因素的影响,测量结果中存在数据丢失现象,这使得重建网格模型[4, 5]中可能存在空洞缺陷。这些空洞不仅影响重建模型的视觉效果,而且影响模型快速重建、有限元分析等后续处理的有效性。空洞识别是指通过某种途径将网格模型中的空洞缺陷识别出来,以便进行空洞修复。因此,空洞识别技术是否完善直接关系到网格模型空洞修复的整体效果,在网格模型的建立过程中起到举足轻重的作用。
目前,主要的空洞识别与修复技术包括基于点云模型的修复技术[6, 7]和基于网格模型的修复技术[8, 9, 10, 11, 12, 13]。在基于点云模型的修复技术中,Min等人[6, 7]采用层次空间剖分技术进行空洞识别,利用张量理论提取发生剧烈变化的点云区域并消除噪声的影响。但是,该方法在提取空洞周围点云数据的拓扑信息时存在较高的计算复杂度。相对而言,基于网格模型的修复技术更容易实现,其中,王乾等人[8, 9]对点云模型中的空洞进行分类,并分别给出了对应的识别与修复算法。该类方法虽然能够进行有针对性的空洞修复,但是,分类过程带来了额外的运算量且所分类别很难涵盖所有情况下的空洞。Wang等人[10, 11]分别提出了将曲面空洞周围的灰度信息以及拐点等特征信息作为辅助的空洞修复方法,该类方法受空洞的个体差异影响较为明显。高旋辉等人[12, 13]提出了基于邻接三角形中边界边性质的空洞识别方法,该类方法具有较强的通用性,但是在进行特殊空洞的识别过程中鲁棒性较低且容易破坏网格模型的原始数据结构。
针对上述问题,本文在系统分析普通空洞与特殊空洞结构特性的基础上,提出了一种无需对各种情况进行分别判断即可有效识别出曲面空洞的具有强鲁棒性的空洞识别与修复方法。通过为边界边重新分配长度的方法对网格中的空洞进行数学建模,将图论中的Floyd最短路径选择算法[14]与空洞识别过程有效结合,采用经典的波前法处理空洞边集生成修复后的三维曲面。
-
设有节点集V={v1,v2,…,vn},当存在关系R将V中的某些节点相互连接生成边集E={e1,e2,…,em}时,称节点集V和边集E组成图G,记为G=(V,E),关系R称为图G的路由矩阵。Floyd算法是一种用于计算图G中多源节点之间最短路径的算法,该算法使用大小均为n×n的距离矩阵和路由矩阵,距离矩阵记为W=[wij]n×n,其中wij表示图G中vi和vj两点之间的路径长度。路由矩阵记为R=[rij]n×n,其中rij表示vi至vj经过的转接点(中间节点)。Floyd算法的基本思想是首先写出初始的W矩阵和R矩阵,然后,按顺序依次将节点集中的各个节点作为中间节点,计算节点集中任意两个其它节点的径长,如果计算结果小于W矩阵中记录的径长,则更新W矩阵和R矩阵,如果计算结果大于或等于W矩阵中记录的径长则不变,以此不断更新W矩阵和R矩阵,直至W中的数值收敛,从最后得到的W和R中便可以找到任何节点间最短路径的径长和路由。
-
本文将三角网格中只参与构成一个三角形和未参与构成三角形的边定义为边界边,将三角网格中至少连接有一条边界边的顶点定义为边界点,多条边界边首尾相连构成了三维曲面的空洞。基于Floyd算法的空洞识别与修复过程如图 1所示。
-
由于边界点和边界边是空洞存在的必要非充分条件,因此,本文的空洞识别算法将边界点和边界边作为分析数据。如图 2(a)所示,点A01为对三角网格进行遍历搜索过程中发现的一个未经处理的边界点,在树搜索算法中,首先,将点A01作为树搜索的第0级节点并初始化距离矩阵W、路由矩阵R以及搜索点集P,图 3中的左侧为初始化数据,搜索点集P记录了搜索点在构成整个三维曲面的散点集中的编号(P的第一行数据)以及搜索点在树搜索过程中的搜索级别(P的第二行数据);然后,采用迭代的方法获取与当前最高搜索级别中的所有节点直接相连的全部边界点作为下一搜索级节点。当下一搜索级中的节点数量为零或者当前搜索的空洞尺寸超过了空洞的最大修复尺寸或者下一搜索级节点中出现了与搜索点集P中重复的节点时,迭代结束。图 2中各边界点下角标的第一个数字表示该点的搜索级别,第二个数字表示该点在本搜索级别中的编号,点A11和点A12为与点A01直接相连的边界点,该两个点即为第1搜索级中的节点。
-
对于树搜索算法搜索到的边界点,如果该点不与搜索点集P中的点重复,则将W中该点到其它非直接相连点的距离设置为∞(无穷远),该点到前一搜索级中直接相连节点的距离设置为该点的搜索级别;将该点与搜索点集P中每个点的路由关系存储到路由矩阵R中;将该点在三维曲面散点集中的编号以及搜索级别存储到搜索点集P中。图 2(a)中第1级搜索结束后对W、R和P的更新结果如图 3右侧数据所示。路由矩阵R中的非零数字表示其所在列的对应节点在P中的编号,例如,R(1,2)表示点A11是P中保存的第2个点。
图 3 距离矩阵W、路由矩阵R以及搜索点集P更新过程
Figure 3. Renewal process of distance matrix W,routing matrix R and search points set P
如果树搜索算法搜索到的边界点与搜索点集P中的某个点发生重复,表明此处可能存在空洞,则在更新距离矩阵W时存在 图 2(a) 和图 2(b) 两种情况。在图 2(a) 中,按照树搜索算法的搜索顺序,点A 31首先通过点A 21搜索得到并将相关数据更新到W、R和P中,然后,在搜索与点A 22相连的边界点时再次得到了点A 31,此时,重复点A 31与点A 22不属于同一搜索级别,对于这种情况,在进行数据更新时,将距离矩阵W中重复点A31到点A 22间的距离设定为点A 31的搜索级别3(此前为∞);而在图 2(b) 中,在搜索与点B 21相连的边界点时得到点B 22,此时,重复点B 22与点B 21属于同一搜索级别,与图 2(a) 中的情况不同,在进行数据更新时,将距离矩阵W中重复点B 22到点B 21间的距离设定为0。两种情况均将重复点与当前搜索点的路由关系更新到路由矩阵R中而不对搜索点集P进行更新。图 2(a) 的数据更新结果为 式中,WA、RA 和PA 分别为图 2(a) 的距离矩阵、路由矩阵和搜索点集,图 2(b) 的数据更新结果为 式中,WB、RB 和PB 分别为图 2(b) 的距离矩阵、路由矩阵和搜索点集,WA 和WB 中由虚线圈出的数值,即为图 2(a) 和图 2(b) 两种情况对距离矩阵的影响。采用对边界边重新分配长度的方法构建了以处理点(图 2中的点A01和点B01)为中心的边界点拓扑结构,重新分配的边界边长度表征了边界点与处理点间的相关性强度,即,到处理点所经由的边界边数量越少的边界点与处理点的相关性越强,到处理点的距离也越近。
-
本文定义构成空洞的边界点中搜索级别最低的点为空洞端点。图 2(a)和图 2(b)的空洞端点分别为点A01和点B01,从图 2中可以看出,重复点与空洞端点之间有两条长度相等的最短路径,且这两条最短路径包含的边界边即为构成空洞的边集。因此,只需找到重复点对应的空洞端点,即可实现曲面空洞的有效识别。
在获取空洞边集的过程中,首先,利用本文改进的Floyd算法处理距离矩阵W和路由矩阵R,在依次将节点集中的各个节点作为中间节点。计算节点集中任意两个其它节点的径长时,如果计算结果等于W矩阵中记录的径长,表明出现了两条长度相等的最短路径,传统的Floyd算法直接将后出现的路径舍掉,而改进的Floyd算法将这两条最短路径同时保存下来。用改进的Floyd算法对 图 2(a) 的距离矩阵和路由矩阵进行处理的结果为 式中,WFA 和RFA 分别为WA 和RA 的处理结果,改进的Floyd算法将路由矩阵的行数扩展为原来的2倍,路由矩阵中的每两行数据分配给一个边界点,其中第二行数据保存可能出现的第二条最短路径的情况,从RFA 中可以看出,点A 01到点A 31有两条最短路径,同时,点A 21到点A 22也有两条最短路径。然后,利用计算得到的距离矩阵和路由矩阵确定空洞端点,空洞端点需满足以下条件:(1)空洞端点到重复点有两条最短路径,重复点到空洞端点也有两条最短路径;
(2)在所有满足条件(a)的边界点中,空洞端点到重复点的距离最短;
(3)如果同时满足条件(a)和条件(b)的边界点不止一个,则任取其中之一即可。
在图 2(a)中,由WFA和RFA可以确定空洞端点为点A01。最后,利用路由矩阵,将构成重复点到空洞端点的两条最短路径的边界边提取出来生成空洞边集。
如果空洞边集中边界边的数量为3,表明搜索到的并不是空洞而是一个孤立的三角形,对于这种情况,本文继续进行树搜索算法获取边界点;反之,则修复搜索到的空洞并重新搜索边界点。
本文定义空洞尺寸为构成空洞的边界边数量,由于三维激光扫描系统获取的点云密度相对均匀,因此,构成空洞的边界边数量越多,空洞的空间面积越大。本文通过设定空洞的最大修复尺寸来提高所提算法的灵活性并避免将三维曲面的轮廓判断为空洞,操作人员根据扫描对象的精度要求设定最大修复尺寸。
-
本文采用波前法[15]对空洞进行修复,该方法将搜索到的空洞边集作为迭代计算的初始数据,在迭代过程中,首先,依次计算当前空洞边集中每两条相邻边界边的夹角并记录构成最小夹角的边界边;然后,连接构成最小夹角的两条边界边的非公共端点生成新的三角形以缩小空洞的尺寸;接下来,在空洞边集中,用新生成的边界边替换与其一起构成三角形的两条边界边,如果更新后的空洞边集中包含的边界边数量大于3,则重复上述过程继续进行迭代,反之,则将空洞边集中包含的这三条边界边构成三角形并结束迭代;最后,对构成空洞的所有边界点采用二面角最大化的三角网格优化准则[16, 17]使修复后的空洞更加平滑。图 4为空洞修复示意图,图中点C、D、E、F和G构成了一个由五条边界边组成的空洞,在第一次迭代中,搜索到∠EFG为空洞的最小内角,连接点E和点G生成△EFG并用边EG替换空洞边集中的EF和FG,由于此时空洞边集中包含4条边界边,因此继续进行迭代;第二次迭代中,由于连接点C和点E后空洞边集中只剩下3条边界边,因此,迭代结束并生成△CDE和△CEG。
-
为了证明所提方法与其它方法相比具有更高的鲁棒性以及对复杂空洞具有更准确的识别能力,实验中对特殊形状的空洞进行了处理分析,图 5(a)为一个与孤立边相连的空洞,图 5(b)为文献[12]的处理结果,由于文献[12]将只属于一个三角形的边识别为空洞的边界边,而图 5(b)中虚线圈出的两条边不属于任何三角形,因此,文献[12]无法对空洞进行有效识别,图 5(c)为文献[13]的处理结果,文献[13]首先将孤立边删除,然后对空洞进行修复,该方法虽然能够成功检测到空洞,但是删除了原始数据的一条边,破坏了数据的完整性。图 5(d)为本文所提方法的处理结果,从图中可以看出,本文所提方法不仅能够有效识别到空洞,而且不需要删除孤立边,保证了原始数据的完整性。
图 6(a)为两个相邻空洞的情况,由于文献[13]通过对边界边进行依次搜索的方法来判断空洞的存在。该方法在识别相邻空洞时存在图 6(b)和图 6(c)两种情况的不唯一性,其中,图 6(b)能够成功的将两个空洞识别出来,而图 6(c)却将围成两个相邻空洞的边界边识别为一个大的空洞,图 6(c)中识别到的空洞的修复结果如图 6(d)所示,从图 6(d)中可以看出,两个相邻空洞的公共边(虚线内的边界边)并没有参与空洞修复而是成为了一条孤立边悬浮于曲面之外,显然,图 6(c)的空洞识别结果是不正确的,文献[13]无法对两个相邻空洞的情况进行有效识别和修复。由于文献[12]将只属于一个三角形的边识别为空洞的边界边,因此,文献[12]也只识别到了一个大的空洞(修复结果如图 6(e)所示)。在本文所提方法中,由于采用树搜索算法对所有空洞进行并行搜索,可以有效识别出相邻的两个空洞,本文所提方法的空洞修复结果如图 6(f)所示。
图 7(a)为由三维激光扫描仪生成的包含多个空洞的三维曲面,图 7(b)、图 7(c)和图 7(d)分别为文献[12]、文献[13]以及本文所提方法的修复结果。从图中可以看出,本文所提方法的修复效果明显优于文献[12]和文献[13]。构成图 7中4个曲面的边数量、三角形数量以及3种方法修复的空洞数量如表 1所示,与文献[12]和文献[13]相比,本文所提方法的空洞修复数量分别提高了54.1%和21.3%,同时,从表 1中可以看出,文献[13]的修复曲面与本文所提方相比只少了4个三角形,但是构成曲面的边却减少了40条,进一步证明了文献[13]由于删除曲面中的孤立边导致原始数据的完整性遭到破坏的问题。
表 1 原始曲面与修复后曲面参数
Table 1. Parameters of the original surface and the repaired surfaces
图 7(d)中空洞的最大修复尺寸为60,曲面的最大修复尺寸不仅能够有效界定三维曲面的外轮廓与空洞,而且,在实际应用中,操作人员可以通过改变最大修复尺寸来获取不同尺寸空洞在曲面中的统计分布,同时,并非所有空洞都是需要进行修复的,对于一些大尺寸的空洞,修复算法会带来较大误差,操作人员可以通过设定最大修复尺寸来屏蔽掉这些较大尺寸的空洞,而通过再次扫描的方式用真实数据来填充剩余空洞。
-
本文提出了一种三维曲面空洞的识别与修复方法,该方法将树搜索算法中的搜索级别作为边界边的长度,利用Floyd最短路径算法对存在的空洞进行识别,采用波前法修复发现的空洞。本文所提方法不仅能够识别出由只属于一个三角形的边界边围成的普通空洞,而且能够在保证原始数据完整性的前提下对连接有孤立边的空洞进行识别。对于两个空洞相邻的情况,传统方法会将其识别为一个大的空洞,而本文所提方法能够对其进行准确判断,与传统方法相比,空洞修复数量提高了21.3%以上。
Recognition and repairing of surface hole in three dimensional laser scanning system
-
摘要: 为了解决三维激光扫描系统中重构曲面存在的空洞问题,提出了基于Floyd最短路径选择算法的空洞识别与修复方法。该方法对三维曲面中所有可能构成空洞的边界点进行逐个处理,采用树搜索算法获得与处理点直接或间接相连的边界点;将搜索到的边界点作为路径选择的节点,将连接节点的边界边作为路径选择的边并根据节点的搜索级别设置边的长度。当新搜索到的边界点与已搜索点发生重复时,首先,利用Floyd算法处理距离矩阵和路由矩阵找到空洞端点;然后,根据重复点与空洞端点生成空洞边集,最后,采用波前法对空洞边集进行处理。实验结果表明:本文所提方法能够准确识别连接有孤立边的空洞以及两个相邻空洞的特殊空洞结构,与传统方法相比,该方法具有更强的通用性和鲁棒性,空洞修复数量与两个传统方法相比分别提高了54.1%和21.3%。Abstract: To solve the hole-problem of the reconstructed surface in three dimensional laser scanning system, the hole-recognition and repair method based on the Floyd shortest path selection algorithm is proposed.We process one by one all the boundary points of the three dimensional surface which might constitute a hole, and adopt the tree search algorithm to obtain the boundary points, which are directly or indirectly connected to the processed point, and use them as the routing nodes, then the boundary sides which are connected with the nodes are used as the routing sides, and we set the length of the boundary sides according to the search level of the nodes.When the newly searched boundary point overlap with the already searched points, we firstly process the distance matrix and the routing matrix to find the hole endpoint by the Floyd algorithm, and then make use of the repeated point and the hole endpoint to generate the hole boundary sides set.Finally, we deal with the hole boundary sides set using the wave front method.The experimental results show that the proposed method can accurately identify the special hole-structures, such as a hole connected with an isolated boundary side and two adjacent holes, and has better versatility and robustness compared with the traditional method.Compared with two traditional methods, the number of the repaired holes has been increased by 54.1% and 21.3%, respectively.
-
Key words:
- three dimensional reconstruction /
- hole-recognition /
- surface repair
-
-
[1] [1] 王飞,汤伟,王挺峰,等.8×8APD阵列激光三维成像接收机研制[J].中国光学,2015,8(6):422-427.WANG F,TANG W,WANG T F,et al..Design of 3D laser imaging receiver based on 8×8 APD detector array[J].Chinese Optics,2015,8(6):422-427.(in Chinese)
[2] 徐正平,沈宏海,许永森.直接测距型激光主动成像系统发展现状[J].中国光学,2015,8(1):28-38.XU ZH P,SHEN H H,XU Y S.Review of the development of laser active imaging system with direct ranging[J].Chinese Optics,2015,8(1):28-38.(in Chinese)
[3] WANG Z,ZHANG L Q,FANG T,et al..A multiscale and hierarchical feature extraction method for terrestrial laser scanning point cloud Classification[J].IEEE Transactions on Geoscience and Remote Sensing,2015,53(5):2409-2425.
[4] WANG H Y,WANG C,LUO H,et al..3-D point cloud object detection based on supervoxel neighborhood with hough forest framework[J].IEEE J.Selected Topics in Applied Earth Observations and Remote Sensing,2015,8(4):1570-1581.
[5] 曾蔚,王汇源,刘莹奇,等.基于IR-SFS算法空间目标红外影像3D重建[J].中国光学,2014,7(3):376-388.ZENG W,WANG H Y,LIU Y Q,et al..3Dreconstruction of space target IR image based on IR-SFS algorithm[J].Chinese Optics,2014,7(3):376-388.(in Chinese)
[6] 罗德安,张腾波,廖丽琼.基于建筑结构分布规律的点云孔洞修补[J].大地测量与地球动力学,2014,34(1):59-62.LUO D A,ZHANG T B,LIAO L Q.Repairing holes of point cloud based on distribution regularity of building façade components[J].J.Geodesy and Geodynamics,2014,34(1):59-62.(in Chinese)
[7] MIN K P,LEE S J,LEE K H.Multi-scale tensor voting for feature extraction from unstructured point clouds[J].Graphical Models,2012,74(4):197-208.
[8] 王乾.三角网格模型过渡与孔洞修补算法的研究及应用[D].南京:南京航空航天大学,2007.WANG Q.Research and application of triangle mesh models transition & hole repairing algorithm[D].Nanjing:Nanjing University of Aeronautics and Astronautics,2007.(in Chinese)
[9] 岳杰,陆声链,孙智慧,等.三维点云孔洞修补算法及在植物形态建中的应用[J].农机化研究,2013,5:190-195.YUE J,LU SH L,SUN ZH H,et al..The repair algorithm of 3D point cloud holes and the application of the reconstruction in plant forms[J].J.Agricultural Mechanization Research,2013,5:190-195.(in Chinese)
[10] WANG L C,HUNG Y C.Hole filling of triangular mesh segments using systematic grey prediction[J].Computer-Aided Design,2012,44(12):1182-1189.
[11] WANG X C,LIU X P,LU L F,et al..Automatic hole-filling of CAD models with feature-preserving[J].Computers & Graphics,2012,36(2):101-110.
[12] 刘咏梅,李凤霞,雷正朝,等.基于边界特征增长的孔洞修补算法[J].系统仿真学报,2014,26(9):1916-1921.LIU Y M,LI F X,LEI ZH CH,et al..New hole filling algorithm based on boundary-feature growing[J].J.System and Simulation,2014,26(9):1916-1921.(in Chinese)
[13] 高旋辉,鲍苏苏,范应方,等.一种基于三角网格模型的空洞填补方法[J].计算机应用与软件,2014,31(6):188-191.GAO X H,BAO S S,FAN Y F,et al..A method for holes filling in triangular mesh model[J].Computer Application and Software,2014,31(6):188-191.(in Chinese)
[14] FLOYD R W.Algorithm 97:shortest path[J].Communications of the Association for Computing Machinery,1962,5(6):345.
[15] ZHAO W,GAO S M,LIN H W.A robust hole-filling algorithm for triangular mesh[J].The Visual Computer,2007,23(12):987-997.
[16] TSAI Y C,HUANG Y,LIN K Y.Development of automatic surface reconstruction technique in reverse engineering[J].The International J.Advanced Manufacturing Technology,2009,42:152-167.
[17] ZHOU M,WANG M Y.Engineered model simplification for simulation based structural design[J].Computer-Aided Design and Applications,2012,9(1):87-94. -