保留边界的点云简化方法

针对点云简化算法中边界点丢失的问题,提出了一种保留边界的三维散乱点云的非均匀简化算法。首先利用kd-tree建立散乱数据点云的空间拓扑关系,计算出每个数据点的k邻域;然后针对目前依据点云分布均匀性算法提取边界效率低的问题,提出一种改进的点云边界点判定算法;最后保留所有边界点,对非边界点,根据曲面变分值和k邻域点已保留比例,进行点云的非均匀简化。实验结果表明,该算法精度高,空间复杂度低,而且简化后点云边界保留完整。     

点模型的几何图像简化法

提出一种基于几何图像的曲率自适应点模型简化算法.首先将点模型的球面极坐标映射到平面上,构造其几何图像;然后利用几何图像确定点模型中点的k-最近邻域及其曲面变分;最后结合曲面变分和简化密度对点集曲面重采样,并通过移动最小二乘曲面评估简化的误差.实验结果表明,该算法执行速度快、易于控制采样密度和保持曲面细节,且能够生成高质量的简化曲面.     

利用连续变形技术的三维点云简化方法

针对曲率变化较大的三维点云表面模型简化方法中容易出现失真的问题,提出了一种利用连续变形技术的三维点云简化方法。算法采用包围盒法构造分割面,分割面将三维点云处理成按扫描线存储的"结构化"测量点集;逐线生成点集的凸包多边形,按一定准则将剩余的离散点集归类到对应的凸包边,引入变换程度参数,通过计算离散点的选取时机参数对其进行选取,获得不同简化比率的连续变化的点云简化模型。随后以右心室、佛像、雕刻面板为典型实例,分别对具有不同表面特征的三维点云模型进行了简化验证,并通过移动最小二乘曲面,评估简化曲面的误差。结果表明,该方法能够有效地简化三维点云,对曲率变化比较大的表面仍然能很好地保留原始模型的几何特征。     

基于欧氏距离及向量内积的骨架提取算法

对骨架算法进行研究,提出一种骨架提取算法.通过对图像内部像素点进行距离变换得到其最近边界点的位置,将内部像素点到最近边界点的向量定义为边界向量,根据物体内部相邻边界向量的方向,计算每个像素点的内积值和其8邻域的最小内积值,得到的最小内积点,以确定的阈值从最小内积点中选取骨架种子点,再对骨架种子点进行处理,得到连通的骨架.试验证明这种算法能保证骨架具的完整性和连通性,正确反映物体的拓扑结构.     

特征保持的基于紧支径向基函数的点云简化

提出一种特征保持的基于紧支径向基函数的点云简化算法.算法采用迭代简化的策略:使用改进的k近邻算法计算点的k邻域,并根据每个点的局部最小二乘拟合曲面多项式计算每个点的高斯曲率;根据选择的紧支径向基函数,建立与点曲率和基函数支撑半径内点云密度相关的评估函数来评估点的重要性,删除函数值最小的点;更新与删除点相关的函数值,迭代删除值最小的点直到满足简化要求.实验结果表明,该方法能够精确地控制简化后点云的数量,尖峰信噪比高,且能够较好地保持点云的特征.     

基于Delaunay三角化的噪声点云非均匀采样

针对基于Delaunay三角化曲面重建方法要求点云密度满足ε-sample条件,提出了一种基于Delaunay三角化的噪声点云非均匀采样算法。首先,利用k-邻近点的Voronoi顶点计算出各点的负极点来逼近曲面中轴(MA);然后,根据近似中轴估计出曲面局部特征尺度(LFS);最后,结合Bound Cocone算法,删除多余的非边界点。实例表明,该算法可以准确、稳健地简化噪声点云,同时可以很好地保留曲面边界特征,经简化后的点云适用于基于Delaunay三角化的曲面重建方法。     

基于曲率特征的点云快速简化算法

为了提高实体反求的效率,提出一种点云快速简化算法.该算法依据特征点群曲率变化的特点在点云邻域拟合曲面上搜寻特征点并进行储存,依据搜寻结果对点云进行特征点分布评估,并根据评估结果设定相应的简化距离对点云进行简化.算法充分保留了特征区域点云,使得简化后的点云能够较好地表达形状,整个搜寻过程只针对高斯曲率极值点的附近点,相对于需要在全局上进行曲率计算的传统简化算法,该算法在运行速度上具有明显优势.     

多阈值提取平面点云边界点的方法

针对基于切片技术的点云数据重建算法需要提取切片内点云边界点,及现有算法效率低、提取效果不好等问题,提出一种多阈值提取平面点云边界点的算法。通过选取判断点的k个近邻点,计算相邻两点与判断点连线间夹角,由于边界点必存在最大夹角,通过判断最大夹角是否超过设定阈值,从而快速提取边界点。通过对阈值设值分析,不同点云数据的边界提取实验及几种方法间比较,该方法不受点云形状影响,均能较好提取边界点,且优于其他3种算法。结果表明该方法在保证原始点云特征信息的前提下,可较好提取边界点,提高后续点云重建速度与效率。     

针对密集点云的快速曲面重建算法

为了能够快速地从高密度散乱点云生成三角形网格曲面,提出一种针对散乱点云的曲面重建算法.首先通过逐层外扩建立原始点云的近似网格曲面,然后对近似网格曲面进行二次剖分生成最终的精确曲面;为了能够处理噪声点云,在剖分过程中所有网格曲面顶点都通过层次B样条进行了优化.相比于其他曲面重建方法,该算法剖分速度快,且能够保证点云到所生成的三角网格曲面的距离小于预先设定容限.实验结果表明,文中算法能够有效地实现高密度散乱点云的三角剖分,且其剖分速度较已有算法有大幅提高.     

点云模型自适应增加采样点算法

提出一种新的点集模型自适应增加啊采样算法.算法利用最小二乘法求出点云模型上每个点的局部光滑曲面片,并由所求得的曲面多项式计算点集曲面上每个点的曲率.通过对每个点及其邻点进行Voronoi剖分,求取每个点所控制的有效采样区域,然后根据曲率在有效区域内建立采样栅格,求取有效区域内的栅格点在曲面上的投影点即为新增采样点.该方法得到的增加采样模型可以较好地保持原点云模型曲面的几何性质,同时还可以通过选择不同的栅格得到适用于不同处理要求的点云模型.     

Computing hierarchical curve-skeletons of 3D objects

A curve-skeleton of a 3D object is a stick-like figure or centerline representation of that object. It is used for diverse applications, including virtual colonoscopy and animation. In this paper, we introduce the concept of hierarchical curve-skeletons and describe a general and robust methodology that computes a family of increasingly detailed curve-skeletons. The algorithm is based upon computing a repulsive force field over a discretization of the 3D object and using topological characteristics of the resulting vector field, such as critical points and critical curves, to extract the curve-skeleton. We demonstrate this method on many different types of 3D objects (volumetric, polygonal and scattered point sets) and discuss various extensions of this approach.     

Exploration of local surface geometry with minimum number of contact points and surface normal information

In this paper, we propose a method of exploring the surface geometry of an unknown object by touch. The method is based on the idea that a three-dimensional surface geometry can be reconstructed from two principal curvatures of the object which are estimated from three concurrent curves. First, the process to minimize the number of contact points is addressed for the approximation of an arbitrary curve, which uses normal vectors at the contact points. Then, an algorithm for reconstructing a three-dimensional local surface from four contact points, two of which can be used to compute a normal curvature, is presented. Lastly, our method is applied to cylindrical, spherical and planar objects in simulation and experiments for validation.     

一种基于投影不变量的目标跟踪方法

提出了一种基于平面投影不变量的目标跟踪算法．算法从图像中提取直线边缘计算投影不变量,用于对目标建模并跟踪．为提取直线边缘,使用改进的序列细化算法将边缘细化为单像素宽,而后用一种快速曲率估计方法估算边缘点的曲率,并保留估算值很小（约等于零）的点拟合直线．在所得直线族中按照邻近规则或者窗口规则挑选直线计算投影不变量．图像处理实验给出了用文中提出的图像预处理算法获得的直线边缘效果,并通过使用所得直线计算不变量的值衡量了所得不变量的稳定性和视角不变性．跟踪实验检验了跟踪算法的鲁棒性和实用性．     

结合插值细分和径向基函数的3维扫描数据孔洞修补

目的 逆向工程中3维扫描数据通常产生孔洞影响逆向造型精度.针对已有算法补洞会导致的边界突变问题,提出基于插值细分和基于径向基函数的孔洞修复算法。方法 首先,对有噪声孔洞边界进行拉普拉斯平滑预处理;其次,通过快速重心插值细分孔洞;然后,结合孔洞周围曲率信息,利用边界和法线约束点进行隐式曲面求解;最后,利用求得的隐式曲面方程,利用梯度下降法调整孔洞插值点,获得平滑修补孔洞结果。结果 对3维经典造型以及实际机械工件等两类不同的数据进行扫描并进行孔洞修补实验。由于算法针对有噪声孔洞结合了孔洞周围曲率信息并通过插值细分进行约束求解,保证了补洞效果的平滑性。实验结果表明,本文算法使得基于径向基函数隐式曲面对有噪声孔洞的适应性更强,其修补结果更加平滑,符合周围曲率变化,改进了已有孔洞修补的边缘突变和修补痕迹明显问题。结论 本文算法针对基于径向基函数的隐式曲面求解对噪声敏感的局限性,进行平滑预处理,结合孔洞周围曲率,提高了孔洞修补效果。由于基于径向基函数的隐式曲面对光顺的流形曲面模拟较好,所以算法对特征孔洞的修补存在一定的不足,快速重心插值法针对不规则孔洞也有一定的局限性。     

基于GAC模型实现交互式图像分割的改进算法

提出了一种改进的交互式图像分割算法。采用全变分去噪模型对图像进行预处理,在去除噪声的同时更好地保护了边缘;提出了一种对梯度模值进行曲率加权的边缘检测方法,采用该方法获得图像的边缘点集;将边缘点集中曲率较大的边缘点作为候选边界点推荐给用户;用户通过主观判断,在候选边界点中选择合适的"初始边界点",算法便可采用GAC模型完成对目标的分割。实验结果表明,改进算法提高了交互式图像分割的自动化程度,有效地减少了交互过程中的人工参与量。     

Fast Force Field Approximation and its Application to Skeletonization of Discrete 3D Objects

In this paper we present a novel method to approximate the force field of a discrete 3d object with a time complexity that is linear in the number of voxels. We define a rule, similar to the distance transform, to propagate forces associated with boundary points into the interior of the object. The result of this propagation depends on the order in which the points of the object are processed. Therefore we analyze how to obtain an order‐invariant approximation formula. With the resulting formula it becomes possible to approximate the force field and to use its features for a fast and topology preserving skeletonization. We use a thinning strategy on the body‐centered cubic lattice to compute the skeleton and ensure that critical points of the force field are not removed. This leads to improved skeletons with respect to the properties of centeredness and rotational invariance.     

A multi-threaded algorithm for computing the largest non-colliding moving geometry

In this article we present an algorithm to compute the maximum size of an object, in three dimensions, that can move collision-free along a fixed trajectory through a virtual environment. This can be seen as a restricted version of the general problem of computing the maximum size of an object to move collision-free from a start position to a goal position. We compute the maximum size by dividing the object into numerous small boxes and computing which ones collide with the virtual environment during the movement along the given trajectory. The algorithm presented is optimized for multi-threaded computer architectures and also uses data structures that leave a small memory footprint making it suitable for use with large virtual environments (defined by, e.g., millions or billions of points or triangles).     

Domain connected graph: the skeleton of a closed 3D shape for animation

In previous research, three main approaches have been employed to solve the skeleton extraction problem: medial axis transform (MAT), generalized potential field and decomposition-based methods. These three approaches have been formulated using three different concepts, namely surface variation, inside energy distribution, and the connectivity of parts. By combining the above mentioned concepts, this paper creates a concise structure to represent the control skeleton of an arbitrary object. First, an algorithm is proposed to detect the end, connection and joint points of an arbitrary 3D object. These three points comprise the skeleton, and are the most important to consider when describing it. In order to maintain the stability of the point extraction algorithm, a prong-feature detection technique and a level iso-surfaces function-based on the repulsive force field was employed. A neighborhood relationship inherited from the surface able to describe the connection relationship of these positions was then defined. Based on this relationship, the skeleton was finally constructed and named domain connected graph (DCG). The DCG not only preserves the topology information of a 3D object, but is also less sensitive than MAT to the perturbation of shapes. Moreover, from the results of complicated 3D models, consisting of thousands of polygons, it is evident that the DCG conforms to human perception.     

Efficient surface reconstruction using generalized coulomb potentials

We propose a novel, geometrically adaptive method for surface reconstruction from noisy and sparse point clouds, without orientation information. The method employs a fast convection algorithm to attract the evolving surface towards the data points. The force field in which the surface is convected is based on generalized Coulomb potentials evaluated on an adaptive grid (i.e., an octree) using a fast, hierarchical algorithm. Formulating reconstruction as a convection problem in a velocity field generated by Coulomb potentials offers a number of advantages. Unlike methods which compute the distance from the data set to the implicit surface, which are sensitive to noise due to the very reliance on the distance transform, our method is highly resilient to shot noise since global, generalized Coulomb potentials can be used to disregard the presence of outliers due to noise. Coulomb potentials represent long-range interactions that consider all data points at once, and thus they convey global information which is crucial in the fitting process. Both the spatial and temporal complexities of our spatially-adaptive method are proportional to the size of the reconstructed object, which makes our method compare favorably with respect to previous approaches in terms of speed and flexibility. Experiments with sparse as well as noisy data sets show that the method is capable of delivering crisp and detailed yet smooth surfaces.     

3D object segmentation using B-Surface

3D object segmentation is important in computer vision such as target detection in biomedical image analysis. A new method, called B-Surface algorithm, is generated for 3D object segmentation. An improved 3D external force field combined with the normalized GVF is utilized. After the initialization of a surface model near the target, B-Surface starts to deform to locate the boundary of the object. First, it overcomes the difficulty that comes from analyzing 3D volume image slice by slice. And the speed of B-Surface deformation is enhanced since the internal forces are not needed to compute in every iteration deformation step. Next, the normal at every surface point can be calculated easily since B-Surface is a continuous deformable model. And it has the ability to achieve high compression ratio (ratio of data to parameters) by presenting the whole surface with only a relatively small number of control points. Experimental results and analysis are presented in this paper. We can see that the B-Surface algorithm can find the surface of the target efficiently.