贪婪投影算法Greedy Projection Algorithm |
您所在的位置：网站首页 › 贪婪原理 › 贪婪投影算法Greedy Projection Algorithm |
贪婪投影算法Greedy Projection Algorithm
|
参考资料： 贪婪投影算法原理贪婪投影算法Greedy Projection algorithmGopi, M. & Krishnan, A Fast and Efficient Projection-Based Approach for Surface Reconstruction, High Performance Computer Graphics, Multimedia and Visualisation, Volume 1, (2000), Number 1 pp. 1-12Navpreet, K. P., Surface Reconstruction from Point Clouds, Master Thesis, 2013算法实现：PCL贪婪投影三角化算法贪婪投影算法通过维护一个点列表，通过这个列表的点，不断的使网格生长（加入新点），直到所有可能的点被连接。其三角化，是局部的：对于选定点 p p p，将其邻域内的所有点通过 p p p点的法向量投影到一个平面，并通过某种算法将未连接的点加入到网格中。 该算法是基于增量表面生长原理[Mercl,1998]，是一种贪婪算法。该算法首先创建一个初始三角形，并继续添加新的三角形，直到考虑了点云中的所有点，或者没有更多地有效三角形可以连接到网格中。 依据点云三角化算法过程中的交互作用，点云中的点被标记为多种状态：自由(free)、边缘(fringe)、边界(boundary)和完成(completed)。 点云中所有的点都处于“自由”状态，自由点被定义为没有邻接三角形的点；当一个点的所有邻接三角形都被确定了，则该点标记为“完成”；当一个点被选为参考点但由于最大允许角度参数约束而具有一些缺失三角形时，它被称为边界点；边缘点是指未被选择作为参考点的点。算法流程： Kd-tree最近邻搜索：给定参考点 P P P，在半径为 r r r的球内搜索该点的最近k-领域来创建点p的领域。 r = μ d 0 r=\mu d_0 r=μd0，其中 d 0 d_0 d0是点 p p p和最近相邻点的距离； μ \mu μ是用户考虑点云密度的自定义常数。使用切平面的进行领域投影：将第一步找出来的点集 C r ( P ) C_r(P) Cr(P)，通过点 P P P的法向量投影到一个平面上，该平面与领域形成的表面大致相切，并按角度排序。修剪pruning：通过可见性和距离等标准，删除 C r ( P ) C_r(P) Cr(P)中的某些点。依次次连接到点 P P P，以及前后连接，形成满足(1)具有最大角度标准和(2)最小角度标准(可选的)的三角形。点云修剪一般会依赖于很多标准。 a. 按距离修剪：使用kd-tree搜索候选邻近点，排除距离特别远的点； b. 进一步排除：位于参考点为中心的球 S R S_R SR之外的其他点是不能作为候选点。 c. 投影：应用距离标准获得的选点集投影到近似切平面； d. 角度排序：以参考点为原点定义新的局部坐标系，前一步的投影平面作为xy平面；候选点集中的所有点都投影到这个平面。候选点的角度 θ \theta θ为局部坐标系的x轴与从原点 P P P到投影的候选点的向量的夹角；并将候选点按照角度排序。 f. 可见性准则：丢弃可能形成自相交网格的点。算法定义了两种边缘类型来检查这种情况: (1) 边界边：仅有一个相邻三角形的边，这些边连接“边缘”点或者“边界”点；(2) 内部边：连接“完成”点与其他任何点。下图展示了 R R R 点的可见性测试。所有黑色的点都在 R R R的边界边之外；白色的点则被其他边遮挡；而点 V V V则是因为 R R R点在它的边界边之外。 图片来源：论文Gopi, M. & Krishnan, A Fast and Efficient Projection-Based Approach for Surface Reconstruction, High Performance Computer Graphics, Multimedia and Visualisation, Volume 1, (2000), Number 1 pp. 1-12
贪婪投影三角化算法是一种对原始点云进行快速三角化的算法，该算法假设曲面光滑，点云密度变化均匀，不能在三角化的同时对曲面进行平滑和孔洞修复 |
【本文地址】