基于安德森加速的快速 B 样条拟合算法

曲线拟合技术已被广泛地应用于图像处理、工程实验等领域。其中,B 样条曲线拟 合是曲线拟合中最常见的方法,它具有局部性好、连续性好等优点,但拟合精度一般较低。在实 际应用中,B 样条曲线拟合对于精度和速度的要求都较高。为了提升平面 B 样条曲线拟合速度, 将安德森加速的想法应用到曲线拟合的方法之中,提出一种基于安德森加速的拟牛顿方法。首先 设定一个初始形状,然后根据初始形状找到其每个数据点的投影点的位置参数,然后利用安德森 加速计算出控制点的相应位置,迭代进行以上 2 步,直到结果收敛。实验结果表明,该方法在收 敛速度和迭代时间上均优于其他方法。     

带法向约束的隐式T样条曲线重构

目的 隐式曲线能够描述复杂的几何形状和拓扑结构,而传统的隐式B样条曲线的控制网格需要大量多余的控制点满足拓扑约束。有些情况下,获取的数据点不仅包含坐标信息,还包含相应的法向约束条件。针对这个问题,提出了一种带法向约束的隐式T样条曲线重建算法。方法 结合曲率自适应地调整采样点的疏密,利用二叉树及其细分过程从散乱数据点集构造2维T网格;基于隐式T样条函数提出了一种有效的曲线拟合模型。通过加入偏移数据点和光滑项消除额外零水平集,同时加入法向项减小曲线的法向误差,并依据最优化原理将问题转化为线性方程组求解得到控制系数,从而实现隐式曲线的重构。在误差较大的区域进行T网格局部细分,提高重建隐式曲线的精度。结果 实验在3个数据集上与两种方法进行比较,实验结果表明,本文算法的法向误差显著减小,法向平均误差由10^-3数量级缩小为10^-4数量级,法向最大误差由10^-2数量级缩小为10^-3数量级。在重构曲线质量上,消除了额外零水平集。与隐式B样条控制网格相比,3个数据集的T网格的控制点数量只有B样条网格的55.88%、39.80%和47.06%。结论 本文算法能在保证数据点精度的前提下,有效降低法向误差,消除了额外的零水平集。与隐式B样条曲线相比,本文方法减少了控制系数的数量,提高了运算速度。     

An error-bounded B-spline curve approximation scheme using dominant points for CNC interpolation of micro-line toolpath

This paper presents a unified framework for computing a B-spline curve to approximate the micro-line toolpath within the desired fitting accuracy. First, a bi-chord error test extended from our previous work is proposed to select the dominant points that govern the overall shape of the micro-line toolpath. It fully considers the geometric characteristics of the micro-line toolpath, i.e., the curvature, the curvature variation and the torsion, appropriately determining the distribution of the dominant points. Second, an initial B-spline curve is constructed by the dominant points in the least square sense. The fitting error is unpredictable and uncontrollable. It is classified into two types: (a) the geometric deviations between the vertices of the polygon formed by the data points and the constructed B-spline curve; (b) those between the edges of the polygon and the constructed B-spline curve. Herein, an applicable dominant point insertion is employed to keep the first geometric deviation within the specified tolerance of fitting error. A geometric deviation model extended from our previous work is developed to estimate the second geometric deviation. It can be effectively integrated into global toolpath optimization. Computational results demonstrate that the bi-chord error test applies to both the planar micro-line toolpath and the spatial micro-line toolpath, and it can greatly reduce the number of the control points. Simulation and experimental results demonstrate that the proposed B-spline approximation approach can significantly improve machining efficiency while ensuring the surface quality.     

Contour curve reconstruction from cloud data for rapid prototyping

In this study, a method for generation of sectional contour curves directly from cloud point data is given. This method computes contour curves for rapid prototyping model generation via adaptive slicing, data points reducing and B-spline curve fitting. In this approach, first a cloud point data set is segmented along the component building direction to a number of layers. The points are projected to the mid-plane of the layer to form a 2-dimensional (2D) band of scattered points. These points are then utilized to construct a boundary curve. A number of points are picked up along the band and a B-spline curve is fitted. Then points are selected on the B-spline curve based on its discrete curvature. These are the points used as centers for generation of circles with a user-define radius to capture a piece of the scattered band. The geometric center of the points lying within these circles is treated as a control point for a B-spline curve fitting that represents a boundary contour curve. The advantage of this method is simplicity and insensitivity to common small inaccuracies. Two experimental results are included to demonstrate the effectiveness and applicability of the proposed method.     

Control point adjustment for B-spline curve approximation

Pottmann et al. propose an iterative optimization scheme for approximating a target curve with a B-spline curve based on square distance minimization, or SDM. The main advantage of SDM is that it does not need a parameterization of data points on the target curve. Starting with an initial B-spline curve, this scheme makes an active B-spline curve converge faster towards the target curve and produces a better approximating B-spline curve than existing methods relying on data point parameterization. However, SDM is sensitive to the initial B-spline curve due to its local nature of optimization. To address this, we integrate SDM with procedures for automatically adjusting both the number and locations of the control points of the active spline curve. This leads to a method that is more robust and applicable than SDM used alone. Furthermore, it is observed that the most time consuming part of SDM is the repeated computation of the foot-point on the target curve of a sample point on the active B-spline curve. In our implementation, we speed up the foot-point computation by pre-computing the distance field of the target curve using the Fast Marching Method. Experimental examples are presented to demonstrate the effectiveness of our method. Problems for further research are discussed.     

基于正则渐进迭代逼近的自适应B 样条曲线拟合

基于渐进迭代逼近(PIA)的数据拟合方法以其简单和灵活的特性获得了广泛的关 注。为了获得高保真度的拟合曲线,提出了一种基于主导点选取和正则渐进迭代逼近(RPIA)的 自适应B 样条曲线拟合算法。首先根据数据点的曲率估计选取初始主导点并生成初始PIA 曲线。 然后,借助于拟合误差和数据点集的曲率分布选取加细的主导点及实现PIA 曲线的更新。得益 于基于曲率分布的主导点选取,使得拟合曲线在复杂区域分布较多的控制顶点,而在平坦区域 则较少。通过正则参数的引入构造了一种RPIA 格式,提升了渐进迭代控制的灵活性。最后, 数值算例表明相比于传统最小二乘曲线拟合该算法在使用较少数量的控制顶点时可实现较高的 拟合精度。     

基于差分进化算法的B 样条曲线曲面拟合

应用B 样条曲线曲面拟合内在形状带有间断或者尖点的数据时,最小二乘法得到的 拟合结果往往在间断和尖点处误差较大,原因在于最小二乘法将拟合函数B 样条的节点固定。本 文在利用3 次B 样条曲线和曲面拟合数据时,应用差分进化算法设计出一种能够自适应地设置B 样条节点的方法,同时对节点的数量和位置进行优化,使得B 样条拟合曲线曲面在间断和尖点处 产生拟多重节点,实现高精度地拟合采样于带有间断或尖点的曲线和曲面数据。     

基于改进麻雀搜索算法的B样条曲线拟合方法

航空发动机叶片气动性能设计的改进要求叶片加工系统采用高精度、高效率的加工工艺，基于传统建模方法的叶片加工系统已难以满足当前的加工需求。提出一种基于改进麻雀搜索算法(SSA)的拟合方法，旨在利用最少控制点高效地达到曲线拟合的目标精度，进而提升传统建模方法的精度和效率，建立适用于数字孪生生产环境的高精度、高实时性的三维叶片模型，提高航空发动机叶片的加工合格率。启发式优化算法在B样条曲线拟合中存在收敛慢的问题，而SSA不断跃向最优解的特性使其能快速收敛。基于此，改进SSA的位置更新函数并给出内节点向量更新范围的概念，通过自动迭代内节点向量配置，利用最小二乘法计算最优控制点，依据局部和全局误差计算适应度值并参与下次迭代，多次迭代后得到符合目标精度的拟合曲线。此外，为提高SSA搜索最少控制点的效率，设计一种二分搜索方法。采用某型叶片截面数据进行拟合验证，结果表明，与传统定义节点向量方法和经典优化算法相比，该方法具有较高的拟合精度和收敛效率，在20和80个控制点下分别取得了1e-3 mm和1e-5 mm左右的拟合精度，在5e-3 mm目标精度下，收敛效率较粒子群优化算法、标准SSA分别提升了14....     

B-spline surface fitting based on adaptive knot placement using dominant columns

By expanding the idea of B-spline curve fitting using dominant points (Park and Lee 2007 [13]), we propose a new approach to B-spline surface fitting to rectangular grid points, which is based on adaptive knot placement using dominant columns along u- and v-directions. The approach basically takes approximate B-spline surface lofting which performs adaptive multiple B-spline curve fitting along and across rows of the grid points to construct a resulting B-spline surface. In multiple B-spline curve fitting, rows of points are fitted by compatible B-spline curves with a common knot vector whose knots are computed by averaging the parameter values of dominant columns selected from the points. We address how to select dominant columns which play a key role in realizing adaptive knot placement and thereby yielding better surface fitting. Some examples demonstrate the usefulness and quality of the proposed approach.     

基于自适应遗传算法的B样条曲线拟合的参数优化

在B样条曲线的最小二乘拟合平面有序数据问题中,经常采用遗传算法进行优化。但随机选取初始种群的遗传算法,容易使得结果陷入局部最优。要达到较高的拟合精度,则需要增加更多的控制顶点。为克服这一缺点,提出了一种自适应的遗传算法对B样条曲线的参数优化。用平均有序数据参数法,将数据参数和节点建立关联,极大提高初始种群的平均适应度;通过优化遗传策略,加快种群进化。实验表明,该算法能用最少的控制顶点和进化代数进行B样条曲线的拟合,得到的拟合曲线逼近效果更好。     

基于遗传算法的B样条曲线拟合改进算法

B样条曲线拟合应用于绘制离散数据点的变化趋势,一般采用数据逼近或者迭代的方法得到,是图像处理和逆向工程中的重要内容。针对待拟合曲线存在多峰值、尖点、间断等问题,提出一种基于遗传算法的B样条曲线拟合算法。首先利用惩罚函数将带约束的曲线优化问题转换为无约束问题,然后利用改进的遗传算法来选择合适的适应度函数,再结合模拟退火算法自适应调整节点的数量和位置,在寻优的过程中找到最优的节点向量,持续迭代直到产生最终的优良重建曲线为止。实验结果表明,该算法有效地提高了精度并加快了收敛速度。     

DFP优化的数据点渐进迭代拟合方法

DFP方法(由Davidon,Fletcher和Powell 3人共同提出)是求解无约束优化问题的一种经典方法,文中指出数据点的拟合问题可转化为无约束优化问题的求解,并基于DFP优化方法给出了一种大规模数据点拟合方法,称之为DFP渐进迭代拟合方法.文中证明了该方法生成的极限曲线为初始数据点的最小二乘拟合曲线;它承袭了经典最小二乘渐进迭代逼近算法的众多优良性质,如具备直观的几何意义、可灵活地拟合大规模数据点、初始控制顶点的选择不影响最终迭代结果等.数值实例进一步表明,同等条件下,文中方法的收敛速度明显优于现有的几种数据点拟合方法.     

基于渐进迭代逼近的矢量地图曲线化简方法

矢量地图化简在地形仿真、制图综合等研究中具有重要应用。针对已有算法难以兼顾化简曲线 的整体形态和局部特征点精度的问题,提出一种基于 B 样条曲线渐进迭代逼近(PIA)的矢量地图曲线化简方法。 首先筛选出能保持曲线轮廓、具有最大信息量的特征点列,将其作为初始控制点列,得到相应的非均匀 3 次 B 样条拟合曲线;然后根据拟合曲线与特征点的误差进行迭代调整控制点,逐步得到一系列逼近曲线,直至最终 满足精度要求。实验表明,PIA 方法不仅保持了化简曲线的整体几何形态,而且能在满足全局误差要求的情况 下,实现特征点处的高精度逼近。     

Constructing iterative non-uniform B-spline curve and surface to fit data points

In this paper, based on the idea of profit and loss modification, we presentthe iterative non-uniform B-spline curve and surface to settle a key problem in computeraided geometric design and reverse engineering, that is, constructing the curve (surface)fitting (interpolating) a given ordered point set without solving a linear system. We startwith a piece of initial non-uniform B-spline curve (surface) which takes the given point setas its control point set. Then by adjusting its control points gradually with iterative formula,we can get a group of non-uniform B-spline curves (surfaces) with gradually higherprecision. In this paper, using modern matrix theory, we strictly prove that the limit curve(surface) of the iteration interpolates the given point set. The non-uniform B-spline curves(surfaces) generated with the iteration have many advantages, such as satisfying theNURBS standard, having explicit expression, gaining locality, and convexity preserving,etc     

空间曲线基于内在几何量的高质量采样和B样条拟合

为解决均匀参数采样在许多情况下得到质量不高的采样点,进而生成不理想的B样条拟合曲线,提出空间曲线基于内在几何量的均匀采样方法,以获得给定总数且具有代表性的采样点.首先定义基于弧长、曲率和挠率加权组合的特征函数,通过调整组合参数更好匹配不同的曲线形状;然后提出空间曲线基于内在几何量的自适应采样方法,迭代生成满足给定距离阈值的采样点.采用最大绝对误差和均方根误差作为评价指标,与均匀弧长采样方法和基于弧长和曲率平均的均匀采样方法进行对比,并通过实例进行验证.结果表明,文中方法在采样质量和B样条拟合结果上获得明显改善.     

Constrained fitting for 2D profile-based reverse modeling

Profile curve reconstruction is crucial to surface reconstruction in reverse engineering. In this paper, we present a new constrained fitting method involving lines, circular arcs and B-spline curves for profile curve reconstruction. By using similarity transformation, we reduce the condition number of the Hessian matrix involved in the optimization process and, therefore, the numerical stability is significantly improved. Several industrial examples are presented to demonstrate the efficiency of our method. This paper describes a 2D constrained fitting method for profile curve reconstruction in reverse engineering. The method is an extension to the published methods for 2D constrained fitting. Further more, the numerical problem associated with constrained fitting is tackled in our paper. The described method has been implemented in RE-SOFT, which is a feature-based reverse engineering software developed by the CAD/CAE/CAM Lab of Zhejiang University.     

基于B样条隶属函数的模糊推理系统

隶属函数和推理规则的确定是模糊推理的难点。通过研究模糊推理过程和B样条函数的特性,对应用B样条函数拟合模糊隶属函数进行推理的方法进行改进。通过对误差极值点、曲率极值点的计算和筛选,得到B样条函数的型值点。反算求得控制点之后,通过自适应增加控制点对曲线进行调整,增加曲线对隶属函数的拟合度,解决了B样条函数对隶属函数的拟合问题。建立B样条推理规则,构造实现了B样条推理系统,并求出该系统的最终结果为B样条超曲面。最后,通过实验验证了该方法的有效性和可行性。     

隐式B-样条曲线重建的直接Greville纵标法

提出了一种以隐式B-样条曲线为表达形式,基于直接Greville纵标的曲线重建方法。根据点云建立有向距离场,并作为B-样条函数的Greville纵标,然后根据高影响区内的平均代数误差优化Greville纵标;得到一个隐式B-样条函数,该函数的零点集即为重建曲线。该方法具有模型简单,重建速度快,无多余分支,无需手工调节任何参数的优点。实验结果证实了该直接法的效率明显高于点拟合法和普通场拟合法,以几何误差为准则的精度亦优于普通场拟合方法。     

关键点选取的最小二乘渐进迭代逼近

目的 最小二乘渐进迭代逼近（LSPIA）方法多以均匀参数化或弦长参数化的形式均匀地确定初始控制点,虽然取得了良好效果,但在处理复杂曲线时,迭代速度相对较慢且误差精度不一定能达到预期设定值。为了进一步提高迭代效率和误差精度,本文提出了基于关键点（局部曲率最大点和极端曲率点）的最小二乘渐进迭代逼近方法。方法 首先计算所有数据点的离散曲率,筛选出局部曲率最大点;接着设定初始的曲率下限,筛选出极端曲率点;然后将关键点与均匀选取的控制点按参数顺序化,并将其作为迭代的初始控制点;最后利用LSPIA方法对数据点进行拟合。结果 对同一组数据点,分别采用LSPIA方法和基于关键点的LSPIA方法,本文方法较好地提高了收敛速度;在相同的控制点数目下,与LSPIA算法相比,本文方法的误差精度较小。结论 本文方法适合于比较复杂的曲线,基于曲率分布的关键点的选取,可以更好地反映曲线的几何信息。数值实例表明,结合关键点筛选策略的LSPIA算法提高了计算效率,取得了更好的拟合效果。     

Fitting unorganized point clouds with active implicit B-spline curves

In computer-aided geometric design and computer graphics, fitting point clouds with a smooth curve (known as curve reconstruction) is a widely investigated problem. In this paper, we propose an active model to solve the curve reconstruction problem, where the point clouds are approximated by an implicit B-spline curve, i.e., the zero set of a bivariate tensor-product B-spline function. We minimize the geometric distance between the point clouds and the implicit B-spline curve and an energy term (or smooth term) which helps to extrude the possible extra branches of the implicit curve. In each step of the iteration, the trust region algorithm in optimization theory is applied to solve the corresponding minimization problem. We also discuss the proper choice of the initial shape of the approximation curve. Examples are provided to illustrate the effectiveness and robustness of our algorithm. The examples show that the proposed algorithm is capable of handling point clouds with complicated topologies.