Point set silhouettes via local reconstruction

We present an algorithm to compute the silhouette set of a point cloud. Previous methods extract point set silhouettes by thresholding point normals, which can lead to simultaneous over- and under-detection of silhouettes. We argue that additional information such as surface curvature is necessary to resolve these issues. To this end, we develop a local reconstruction scheme using Gabriel and intrinsic Delaunay criteria and define point set silhouettes based on the notion of a silhouette-generating set. The mesh umbrellas, or local reconstructions of one-ring triangles surrounding each point sample, generated by our method enable accurate silhouette identification near sharp features and close-by surface sheets, and provide the information necessary to detect other characteristic curves such as creases and boundaries. We show that these curves collectively provide a sparse and intuitive visualisation of point-cloud data.     

基于三维点云模型的特征线提取算法

针对以往算法存在无法区分尖锐和非尖锐特征点、提取的特征点与视角有关、特征点未连线等问题, 提出一种基于高斯映射和曲率值分析的三维点云模型尖锐特征线提取算法。该算法先进行点云数据点的离散高斯映射, 并将映射点集聚类; 然后使用自适应迭代过程得到两个或多个面的相交线上曲率值和法向量发生突变的尖锐特征点, 这些点与视角无关; 最后, 用改进的特征折线生长算法, 将特征点连接, 得到光顺特征线。实验证明, 该算法具有良好的自适应性、抗噪性和准确性, 是一种有效的三维模型特征线提取算法。     

Surface reconstruction by layer peeling

Given an input point cloud P in ?³, this paper proposes a novel algorithm to identify surface neighbors of each point p∈P respecting the underlying surface S and then to construct a piecewise linear surface for P. The algorithm utilizes the simple k-nearest neighborhood in constructing local surfaces. It makes use of two concepts: a local convexity criterion to extract a set of surface neighbors for each point, and a global projection test to determine an order for the reconstruction. Our algorithm not only produces a topologically correct surface for well-sampled point sets, but also adapts well to handle under-sampled point sets. Furthermore, the computational cost of the algorithm increases almost linearly in the size of the point cloud. It, thus, scales well to deal with large input point sets.     

Feature Preserving Mesh Generation from 3D Point Clouds

We address the problem of generating quality surface triangle meshes from 3D point clouds sampled on piecewise smooth surfaces. Using a feature detection process based on the covariance matrices of Voronoi cells, we first extract from the point cloud a set of sharp features. Our algorithm also runs on the input point cloud a reconstruction process, such as Poisson reconstruction, providing an implicit surface. A feature preserving variant of a Delaunay refinement process is then used to generate a mesh approximating the implicit surface and containing a faithful representation of the extracted sharp edges. Such a mesh provides an enhanced trade‐off between accuracy and mesh complexity. The whole process is robust to noise and made versatile through a small set of parameters which govern the mesh sizing, approximation error and shape of the elements. We demonstrate the effectiveness of our method on a variety of models including laser scanned datasets ranging from indoor to outdoor scenes.     

基于多判据的散乱点云特征点提取算法

为了有效获取散乱点云中的尖锐特征点和边界特征点,提出一种利用多判据融合的特征点提取算法。首先利用一种改进的k-d tree构建点云拓扑,搜索样点的K局部邻域;然后利用法向夹角判定准则、核密度判定准则、场力和判定准则分别求取各个样点局部邻域的三个特征参数,最后通过加权计算特征参数得到每个样点的特征值与全局判定阈值,特征值比阈值大的点即为特征点。实验证明,该算法能有效的获取散乱点云中边沿特征点与尖锐特征点。     

Constrained curve fitting on manifolds

When designing curves on surfaces the need arises to approximate a given noisy target shape by a smooth fitting shape. We discuss the problem of fitting a B-spline curve to a point cloud by squared distance minimization in the case that both the point cloud and the fitting curve are constrained to lie on a smooth manifold. The on-manifold constraint is included by using the first fundamental form of the surface for squared distance computations between the point cloud and the fitting curve. For the solution we employ a constrained optimization algorithm that allows us to include further constraints such as one-sided fitting or surface regions that have to be avoided by the fitting curve. We illustrate the effectiveness of our algorithm by means of several examples showing different applications.     

规则特征曲面点云法向估计

目的 针对特征曲面点云法矢估计不准确,点云处理时容易丢失曲面的细节特征等问题,提出基于高斯映射的特征曲面散乱点云法向估计法。方法 首先,用主成分分析法粗略地估算点云法向和特征点;其次,将特征点的各向同性邻域映射到高斯球,用K均值聚类法对高斯球上的数据分割成多个子集,以最优子集对应的各向异性邻域拟合曲面来精确估算特征点的法向量;最后,通过测试估计法向与标准法向的误差来评价估计法矢的准确性,并且将估计的法向应用到点云曲面重建中来比较特征保留效果。结果 本文方法估计的法向最小误差接近0,对噪声有较好的鲁棒性,重建的曲面能保留曲面的尖锐特征,相比于其他法向估计法,所提出的方法估计的法向更准确。结论 本文方法能够比较准确的估算尖锐特征曲面法向量,对噪声鲁棒性强,具有较高的适用性。     

基于曲率法线流的树点云骨架提取方法

针对树木点云拓扑结构复杂、特征细节繁多等问题,提出一种基于点云收缩提取曲线骨架的算法。首先,为了在点云表面直接应用网格收缩算法,对点云进行局部主成分分析和Delaunay三角剖分;其次,针对树木点云拓扑结构复杂和末枝细节繁多等问题,用曲率法线流算子对点云进行收缩,针对树木枝条细长且弯曲幅度平缓等特点,利用改进后的QEM网格简化方法将三角网格折叠成一维曲线骨架;最后,将得到的曲线骨架进行连通和居中处理。该算法直接在点云上进行操作,不需要额外的信息和预处理操作,对噪声和残缺点云有良好的鲁棒性。实验证明,该算法提取的树木点云骨架充分表达了树木在自然环境下的生物性结构和特征,相对于rosa、L1-中轴等经典算法,在树木点云的骨架提取速度上提高3倍以上,枝条重建度提高25%。     

Skeleton-based intrinsic symmetry detection on point clouds

We present a skeleton-based algorithm for intrinsic symmetry detection on imperfect 3D point cloud data. The data imperfections such as noise and incompleteness make it difficult to reliably compute geodesic distances, which play essential roles in existing intrinsic symmetry detection algorithms. In this paper, we leverage recent advances in curve skeleton extraction from point clouds for symmetry detection. Our method exploits the properties of curve skeletons, such as homotopy to the input shape, approximate isometry-invariance, and skeleton-to-surface mapping, for the detection task. Starting from a curve skeleton extracted from an input point cloud, we first compute symmetry electors, each of which is composed of a set of skeleton node pairs pruned with a cascade of symmetry filters. The electors are used to vote for symmetric node pairs indicating the symmetry map on the skeleton. A symmetry correspondence matrix (SCM) is constructed for the input point cloud through transferring the symmetry map from skeleton to point cloud. The final symmetry regions on the point cloud are detected via spectral analysis over the SCM. Experiments on raw point clouds, captured by a 3D scanner or the Microsoft Kinect, demonstrate the robustness of our algorithm. We also apply our method to repair incomplete scans based on the detected intrinsic symmetries.     

保持尖锐特征的隐式曲线绘制算法

隐式曲线在生物、医学、气象、地学、石油勘探及物探等领域有着广泛的应用。 提出一种绘制带有尖锐特征的平面隐式曲线的算法,能有效地提取隐式曲线的尖锐特征。该算 法首先确定曲线的绘制区域,采用自上而下的方式生成绘制区域的四叉树表示,并在四叉树节 点表示的每个单元格内生成一个数值场特征点;然后连接特征点生成对偶网格;最后,利用 Marching Squares 算法生成曲线。实验结果表明,该算法能在网格较稀松的情况下绘制出隐式 曲线,并且可以实现曲线的尖锐特征。     

自适应K-means聚类的散乱点云精简

目的 点云精简是曲面重建等点云处理的一个重要前提,针对以往散乱点云精简算法的精简结果存在失真较大、空洞及不适用于片状点云的问题,提出一种自适应K-means聚类的点云精简算法。方法 首先,根据k邻域计算每个数据点的曲率、点法向与邻域点法向夹角的平均值、点到邻域重心的距离、点到邻域点的平均距离,据此运用多判别参数混合的特征提取方法识别并保留特征点,包括曲面尖锐点和边界点;然后,对点云数据建立自适应八叉树,为K-means聚类提供与点云密度分布相关的初始化聚类中心以及K值;最后,遍历整个聚类,如果聚类结果中含有特征点则剔除其中的特征点并更新聚类中心,计算更新后聚类中数据点的最大曲率差,将最大曲率差大于设定阈值的聚类进行细分,保留最终聚类中距聚类中心最近的数据点。结果 在聚类方面,将传统的K-means聚类和自适应K-means聚类算法应用于bunny点云,后者在聚类的迭代次数、评价函数值和时间上均优于前者;在精简方面,将提出的精简算法应用于封闭及片状两种不同类型的点云,在精简比例为1/5时fandisk及saddle模型的精简误差分别为0.29×10^-3、-0.41×10^-3和0.037、-0.094,对于片状的saddle点云模型,其边界收缩误差为0.030 805,均小于栅格法和曲率法。结论 本文提出的散乱点云精简算法可应用于封闭及片状点云,精简后的数据点分布均匀无空洞,对片状点云进行精简时能够保护模型的边界数据点。     

Curve skeleton extraction by coupled graph contraction and surface clustering

In this paper, we present a practical algorithm to extract a curve skeleton of a 3D shape. The core of our algorithm comprises coupled processes of graph contraction and surface clustering. Given a 3D shape represented by a triangular mesh, we first construct an initial skeleton graph by directly copying the connectivity and geometry information from the input mesh. Graph contraction and surface clustering are then performed iteratively. The former merges certain graph nodes based on computation of an approximate centroidal Voronoi diagram, seeded by subsampling the graph nodes from the previous iteration. Meanwhile, a coupled surface clustering process serves to regularize the graph contraction. Constraints are used to ensure that extremities of the graph are not shortened undesirably, to ensure that skeleton has the correct topological structure, and that surface clustering leads to an approximately-centered skeleton of the input shape. These properties lead to a stable and reliable skeleton graph construction algorithm.Experiments demonstrate that our skeleton extraction algorithm satisfies various desirable criteria. Firstly, it produces a skeleton homotopic with the input (the genus of both shapes agree) which is both robust (results are stable with respect to noise and remeshing of the input shape) and reliable (every boundary point is visible from at least one curve-skeleton location). It can also handle point cloud data if we first build an initial skeleton graph based on k-nearest neighbors. In addition, a secondary output of our algorithm is a skeleton-to-surface mapping, which can e.g. be used directly for skinning animation.Highlights(1) An algorithm for curve skeleton extraction from 3D shapes based on coupled graph contraction and surface clustering. (2) The algorithm meets various desirable criteria and can be extended to work for incomplete point clouds.     

Multi-scale tensor voting for feature extraction from unstructured point clouds

Identifying sharp features in a 3D model is essential for shape analysis, matching and a wide range of geometry processing applications. This paper presents a new method based on the tensor voting theory to extract sharp features from an unstructured point cloud which may contain random noise, outliers and artifacts. Our method first takes the voting tensors at every point using the corresponding neighborhoods and computes the feature weight to infer the local structure via eigenvalue analysis of the tensor. The optimal scale for a point is automatically determined by observing the feature weight variation in order to deal with both a noisy smooth region and a sharp edge. We finally extract the points at sharp features using adaptive thresholding of the feature weight and the feature completion process. The multi-scale tensor voting of a given point set improves noise sensitivity and scale dependency of an input model. We demonstrate the strength of the proposed method in terms of efficiency and robustness by comparing it with other feature detection algorithms.     

Robust and Efficient Implicit Surface Reconstruction for Point Clouds Based on Convexified Image Segmentation

We present an implicit surface reconstruction algorithm for point clouds. We view the implicit surface reconstruction as a three dimensional binary image segmentation problem that segments the entire space $\mathbb R ^3$ or the computational domain into an interior region and an exterior region while the boundary between these two regions fits the data points properly. The key points with using an image segmentation formulation are: (1) an edge indicator function that gives a sharp indicator of the surface location, and (2) an initial image function that provides a good initial guess of the interior and exterior regions. In this work we propose novel ways to build both functions directly from the point cloud data. We then adopt recent convexified image segmentation models and fast computational algorithms to achieve efficient and robust implicit surface reconstruction for point clouds. We test our methods on various data sets that are noisy, non-uniform, and with holes or with open boundaries. Moreover, comparisons are also made to current state of the art point cloud surface reconstruction techniques.     

基于多判别参数混合方法的散乱点云特征提取

针对以往散乱点云特征提取算法存在尖锐特征点提取不完整以及无法保留模型边界点的问题,提出了一种多个判别参数混合方法的特征提取算法。首先,对点云构建k-d tree,利用k-d tree建立点云k邻域;然后,针对每个k邻域计算数据点曲率、点法向与邻域点法向夹角的平均值、点到邻域重心的距离、点到邻域点的平均距离;最后,据此四个参数定义特征阈值和特征判别参数,特征判别参数大于阈值的点即为特征点。实验结果表明,与已有算法相比,该算法不仅可以有效提取尖锐特征点,而且能够识别边界点。     

一种基于球面调和分析的三维模型检索算法

提取关于坐标旋转不变的特征描述符以及提高特征描述符对噪声的鲁棒性是基于内容三维模型检索技术中有待进一步研究解决的问题之一。将三维模型表面离散成三维点数据,然后使用球面调和方法对得到的点数据进行调和分析得到三维模型旋转不变的特征向量,并且能够增加算法对模型表面噪声的鲁棒性提高检索准确度。实验证明该算法在检索准确度和对噪声的鲁棒性上都有所提高。     

面向RGBD深度数据的快速点云配准方法

目的 真实物体的3维重建一直是计算机图形学、机器视觉等领域的研究热点。针对基于RGBD数据的非匀速非固定角度旋转物体的3维重建问题,提出一种利用旋转平台重建物体3维模型的配准方法。方法 首先通过Kinect采集位于旋转平台上目标物的深度数据和颜色数据,对齐融合并使用包围盒算法去除背景噪声和不需要的外部点云,获得带有颜色信息的点云数据。并使用基于标定物不同角度上的点云数据标定出旋转平台中心轴的位置,从而获得Kinect与旋转平台之间的相对关系;然后通过曲率特征对目标点云进行特征点提取并寻找与相邻点云的对应点;其中对于特征点的选取,首先针对点云中的任意一点利用kd-tree搜寻其k个邻近点,对这些点进行曲面拟合,进而计算其高斯曲率,将高斯曲率绝对值较大的n个点作为点云的特征点。n的取值由点云的点个数、点密度和复杂度决定,具体表现为能反映物体的大致轮廓或表面特征信息即可。对于对应点的选取,考虑到欧氏距离并不能较好反映点云中的点对在旋转过程中的对应关系,在实际配准中,往往会因为点云重叠或距离过远等原因找到大量错误的对应点。由于目标物在扫描过程中仅绕旋转轴进行旋转,因此采用圆弧最小距离寻找对应点可有效减少错误点对。随后,使用二分迭代寻找绕中心轴的最优旋转角度以满足点云间的匹配误差最小;最后,将任意角度获取的点云数据配准到统一的坐标系下并重建模型。结果 使用斯坦福大学点云数据库和自采集数据库分别对该方法和已有方法在算法效率和配准结果上进行对比实验,实验结果显示在拥有平均75 000个采样点的斯坦福大学点云数据库上与传统ICP算法和改进ICP算法相比,迭代次数分别平均减少86.5%、57.5%,算法运行时间分别平均减少87%、60.75%,欧氏距离误差平方和分别平均减少70%、22%;在具有平均57000个采样点的自采集点云数据库上与传统ICP算法和改进ICP算法相比,迭代次数分别平均减少94%、75%,算法运行时间分别平均减少92%、69%,欧氏距离误差平方和分别平均减少61.5%、30.6%;实验结果显示使用该方法进行点云配准效率较高且配准误差更小;和KinectFusion算法相比在纹理细节保留上也表现出较好的效果。结论 本文提出的基于旋转平台标定的点云配准算法,利用二分迭代算法能够有效降低算法复杂度。与典型ICP和改进的ICP算法的对比实验也表明了本文算法的有效性。另外,与其他方法在具有纹理的点云配准对比实验中也验证了本文配准方法的优越性。该方法仅采用单个Kinect即可实现对非匀速非固定角度旋转物体的3维建模,方便实用,适用于简单快速的3维重建应用场合。     

Sharp feature preserving MLS surface reconstruction based on local feature line approximations

Sharp features in manufactured and designed objects require particular attention when reconstructing surfaces from unorganized scan point sets using moving least squares (MLS) fitting. It is an inherent property of MLS fitting that sharp features are smoothed out. Instead of searching for appropriate new fitting functions our approach computes a modified local point neighborhood so that a standard MLS fitting can be applied enhanced by sharp features reconstruction.We present a two-stage algorithm. In a pre-processing step sharp feature points are marked first. This algorithm is robust to noise since it is based on Gauss map clustering. In the main phase, the selected feature points are used to locally approximate the feature curve and to segment and enhance the local point neighborhood. The MLS projection thus leads to a piecewise smooth surface preserving all sharp features. The method is simple to implement and able to preserve line-type features as well as corner-type features during reconstruction.     

大规模点云选择及精简

点云选择与精简是三维扫描系统中应对背景数据、冗余采样、分布不均匀 等问题的必要后处理步骤。针对定制低成本三维扫描系统的需求,传统方法仍有很多局限性。 这是由于研究领域未提供支持套索UI 接口的点云选择算法;传统点云精简方法侧重曲率自 适应分布,无法保证平坦区域的均衡分布。论文提出一种支持套索UI 接口的点云选择算法, 通过构建套索形状矩形覆盖与点云八叉树剔除大部分点在多边形内的判断;提出一种基于 Poisson-disk 采样的均衡分布的点云精简算法,并以采样点邻域球布尔交运算来定义曲面上 的圆盘半径度量,具有保持尖锐边特征及边界的性质。实验结果表明,论文方法能够较好满 足低成本三维扫描系统中点云删减处理的需求。