点云重建三角网格(共8页)

1、点云重建三角(snjio)网格三角网格重建的研究(ynji)现状曲面重建技术(jsh)在逆向工程57、数据可视化58、机器视觉59、虚拟现实60、医疗技术61等领域中得到了广泛的应用。网格重建作为曲面重建的重要前处理一直是研究的热点。近十几年来，国内外学者提出了许多网格重建的算法。根据重建过程中采用的具体方法可以将网格重建算法分为基于Delaunay重建法、区域扩张重建法、基于隐式曲面重建法和基于统计学重建法。基于Delaunay重建方法，具有很强的数学基础，一般能精确地重建物体表面，但计算量比较大，对带有噪声的物体和尖锐特征的物体，采用该方法重建并不能取得比较理想的结果。Boissonnat

2、62通过采用三维Delaunay三角剖分得到数据点的凸包，然后逐步剥离冗余四面体，使所有数据点可见，最终重建出物体的网格模型。在采样点足够稠密的情况下，该方法能重建出与物体拓扑一致的网格模型，但当采样点不均匀以及存在噪声数据时，不能构造出与物体拓扑等价的网格模型，同时计算复杂，内存消耗比较多。Edelsbrunner63提出一种-shape方法，该方法通过删除四面体凸包中包围球或者外半径大于的四面体、三角面片和边重建测量数据的网格模型，但-shape不是流形结构，必须经过后续处理才能得到正确的二维流形网格64，同时该方法对采样不均匀的点云难以选择合适的值重建出正确的网格模型。Amenta656

3、667对扫描数据进行Voronoi图分解，然后通过Delaunay三角化方法重建网格模型。该方法能精确地通过扫描数据点，但对噪声模型和具有尖锐特征的模型不能取得理想的效果。Floater68将数据点投影到平面，在平面采用Denaulay三角化方法，生成平面网格，并将拓扑关系映射回空间数据点，从而达到网格重建的目的，该方法简单高效，但只适用于单值曲面。属于该类的方法还有Crust方法69和Cocone方法70。基于隐式表面重建方法，可以有效处理噪声数据，但不能有效地处理具有尖锐特征的模型，一般只用于计算机视觉和虚拟现实中。Hoppe71首先给出了一个刻画点集密度的方法，引入了密度样本的定义，通过

4、计算点的法矢，得到数据点局部处的切平面，用切平面线性逼近待重建网格的局部形状，从而建立距离场函数，通过提取等值曲面得到三角网格。该方法通常涉及复杂的法矢一致性调整，不能较好地重建细节特征。周儒荣72对Hoppe的方法进行了改进，提出以切平面中心代替数据点，改善网格质量，较好地处理了法矢传播中的孤岛问题。Curless73提出了以扫描图像作为加权距离场函数，通过合并多幅图像的方法进行网格重建，能处理上百万的数据。Car74等提出通过径向基函数进行网格重建，他们以径向基作为基函数，建立插值函数，通过求解线性方程组，达到网格重建的目的，但由于约束点比较多，方程为全局方程，需要消耗较多的内存和计算时间

5、。Ohtake76、朱心雄77提出一种MPU ( Multilevel Partition of Unity)方法，该方法克服了一般隐式表面重建法不能还原尖锐特征的缺点。Kazhdan78通过泊松等式f= div(n)建立隐式曲面，然后提取等值面，从而达到网格重建的目的。属于这类的方法还有717374757778。水平集的方法，最早是由Osher 和Sethian7980于1988 年提出的，它的基本思想是将曲线或者曲面看成是某一更高维函数的零水平集，利用函数的演化与Hamilton-Jacobi方程的相似性，将曲线或者曲面的演化过程转化为函数的演化过程. Whitaker81、Zhao82、

6、Sethian83、Osher84、Zhao85等人也提出将水平集方法应用到曲面重构中，并取得了较好的结果.变形表面方法与之类似，从初始表面开始，在能量函数的驱动下可以逼近真实表面。区域扩张法，一般都是从一个初始种子出发，不断向周边扩张直到所有数据点都被处理，其中初始种子可以是一个三角面片或者(huzh)一条边。Bernardinit在-shape理论(lln)基础上提出了BPA算法，通过使用一个给定半径或者使用不同半径的球绕着活动边转动，直到找到另外(ln wi)一点，生成新的三角面片。该算法需要点的法矢信息，而且不容易取到合适的半径。Crossno86提出螺旋边准则，根据边界边最小内切圆准

7、则寻找一个新的顶点并构建新三角形，逐步覆盖整个数据集，该方法能高效地处理均匀数据点。Huang64将K个临近点投影到活动边所在三角面片的平面上，剔除不可见的点，然后利用最小长度准则在剩余点中选择一点构造新的三角面片。Lin87提出IPD算法，该算法定义了采样点均匀度，利用该均匀度建立活动边的影响区域，从而获得候选点集合，然后根据加权边长和最小准则选择一点构造新的三角面片。属于区域扩张法的还有8687，该类方法思想简单、实现容易、效率高，可以处理复杂拓扑模型的重建，但现有的该类方法尖锐特征重建效果不是很理想。基于统计学方法，将统计学习和机器学习的方法运用于网格重建。Kohonen88提出基于自我

8、组织学习的网格重建算法，最先将统计学方法引入网格重建中。将反向传播用于网格重建，建立四层BP神经网格，以网格曲面或者B样条曲面作为样例训练该神经网络，不断调整神经网络的权值，将数据点与重建曲面转化为非线性问题，通过梯度方向搜索使数据点与重建曲面的方差最小，重建出来的曲面一般精度比较高，但它存在收敛性问题。Ivrissimtzis89将神经网络引入网格模型重建，该方法将三角网格作为神经网络，将数据点作为信号，通过信号刺激神经网络，逐步更新网格。Diebel90将贝叶斯框架引入了网格重建。另外属于这个范畴的方法还有919293。多种子点和平坦部分优先生长方法的点云到网格重建(a) (b) (c)

9、(d) (e)Fig.1. The flat (horizontal or vertical) portions of the object have a higher priority to be triangulated than the places with sharp curvature change. (a) an flat portions; (b) rightly growing; (c) falsely growing; (c) falsely growing; (d) multi-seeds mesh; (e) the finished mesh.点云中的点有四种状态：自由

10、点，候选点，已接受点，和异常点。首先，把散乱点集的所有点放入方便查找相邻点的哈希表，全标记为自由状态，然后在平坦(水平或者垂直)的区域构造种子三角形，种子三角形的边放入作为前沿边堆栈。然后从前沿边堆栈中弹出一个前沿边，用与BPA相似的方法以当前前沿边的中心为球心作一个范围球，球内点就是候选点。按四个原则从候选点中选择一个作为邻近点，连接成新三角形，把相应边存入前沿边堆栈，改变邻近点的状态为已接受点。从候选点中选择邻近点的四个原则是：邻近点与当前前沿边构成的角不能太大也不能太小；新三角形与当前三角形构成的角不能太大；新三角形应该与已成的网格不相交；与当前前沿边距离小。其中的三个原则构成一个代价函

11、数，计算每个候选点的代价函数，从中选择最小代价的作为邻近点。如果没有合适的邻近点，则前前沿边搁置，不构造新三角形。从前沿边堆栈中弹出新的当前前沿边，继续生长，直到前沿边堆栈空。网格完成时，可能会还有自由点，此时的自由点被认为是异常点。当前前沿边的邻近(ln jn)点，不一定是自由点，也可能是已接受的、在前沿边上的点。我们称已接受的、在前沿边上的点为前沿点。在构造新三角形时，根据邻近点的属性，有四种操作：(1)加入(jir)：如果邻近点是自由的候选点，加入新三角形，推进前沿边；Fig.2. Mesh Growing. 1 is the seed triangle, and 2 the finis

12、hed triangle, 3 a front edge, 4 the current front edge, 5 the free points, 6 the bounding ball, 7 the close point, 8 the reference point.(2)填充：如果邻近点是已接受点，并且邻近点与前沿(qinyn)边的两端点的连接边已存在，那么这里有一个孔洞，把邻近点和前沿边构造成新三角形，从前沿边堆栈中删除邻近点与前沿边的两端点的连接边；(3)连接：如果邻近点是已接受点，但是邻近点与前沿边的某一个端点的连接边已存在，而与前沿边的另一个端点的连接边不存在，把邻近点和前沿边

13、构造成新三角形，从前沿边堆栈中删除邻近点与前沿边间已存在的连接边，把新三角形的另一边加入前沿边堆栈；(a) (b) (c)Fig.3. Topological Operations. (a) a mesh with the current front edge e1; (b) the mesh growing process; (c) the temporal result mesh after 4 topological operations.(4)缝接：如果邻近点是已接受点，但是邻近点与当前前沿边的端点间没有已存在的连接边，把邻近点和当前前沿边构造成新三角形，同时以邻近点和当前前沿边的一端

14、点为前沿边再构造另一新三角形，把两新三角形的二个外侧边加入前沿边堆栈；Fig.4. Triangulation.三角形都是有方向的，按逆时针方向建构，这样表面的方向都指向外面。前沿边也始终是封闭的有向曲线，数目始终在变化。加入操作会新填二个前沿边，删除一个(y )前沿边；填充操作不会新填前沿边，但会删除三个前沿边；连接操作会删除一个前沿边，新填一个前沿边；缝接操作会删除二个前沿边，新填二个前沿边。如果在填充、连接或者缝接时发现新三角形的某两条边是前沿边，并且方向不一致，那么网格在此处发生了纠缠。 (a) (b) (c) (d)Fig.5. Reconstruct the head model:

15、 (a) Points; (b) Merge local triangular mesh; (c) Mesh optimize; (d) Geometric model after normal consistent.点云到网格的重建一向有两个困难：自相交和拓朴。但是这两个问题在多种子点和平坦部分优方法下得到(d do)了解决。但是这个方法中也存在以下几个难点：(1)算法的第一步，寻找平坦部位的种子点，如果需要计算每个三角形的法向才能知道哪些三角形是平坦的，计算成本高，需要更有效(yuxio)的方法；(2)从当前前沿边的中心构造范围球时，球的半径如何选择才合适。球的半径太大，会多产生异常点，甚

16、至得到错误的拓朴连接；但是多数范围球内至少应该有超过一个的候选点。但是无论如果，范围球的半径与点间的平均距离有关系。如果需要范围球的半径与局部自适应，那么可以计算出局部点云的平均距离。平均距离由点云的包围盒和点的数目计算而来；(3)新三角形应该与已成的网格不相交，相交性检测是一个费时的计算。可以在新三角形上取一个比范围球更大的区域，检测是否有已成的网格，新三角形的三个顶点是否落在每个网格平面的同一边；(4)从候选点集中选取邻近点的代价函数，其实是在邻近点与当前三角形的夹角、法向变化和邻近点与当前边距离这三者考虑何者优先。如果重建对象平坦光滑，那么法向变化应该小，距离可以取得大一些；相反，法向变

17、化可以取得大，距离应该取得小。各个局部的情况与此相同。而且在种子生长阶段和最后表面缝合阶段，代价函数也应不同；因此，代价函数中三个因素间的系数应该是与局部情况相适应的；(5)既然是平坦部分优先生长(shngzhng)，那么当前前沿(qinyn)边应该(ynggi)是前沿边中最平坦的部分。因此前沿边堆栈也需要按平坦程度排序。点云到网格的重建1.1哈希表的构造方法 一般的线性表、树中，记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录，

18、因此必须(bx)在记录的存储位置和它的关键字之间建立一确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此不需要进行比较便可直接取得所查记录。在此，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表（又称为杂凑法或散列表）。哈希表不可避免冲突(collision)现象：对不同的关键字可能得到同一哈希地址 即key1key2，而f(key1)=f(key2)。具有相同函数值的关键字对该哈希函数来说称为(chn wi)同义词(synonym)。 因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。可如下描述哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上并以关键字在地址集中的“象”作为相应(xingyng)记录在表中的存储位置，这种表被称为哈希表。注：这个函数f(key)为哈希函数。(注意：这个函数并不一定是数学函数) 哈希函数是