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

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

Surface approximation with rational B-splines

Many modern geometric modelers use nonuniform rational B-spline curves and surfaces as their canonical representations. Rational B-splines are a versatile representation, encompassing integral B-splines and the basic classical primitives such as conics, quadrics, and torii. However, rational B-splines representations other than these classical primitives have found little application in surface modeling. In this paper we develop approximation algorithms based on the general rational B-spline formulation. Numerical experiments indicate that rational B-splines allow a significantly more compact approximation of two classes of parametric surfaces in comparison to integral B-splines. The two classes of surfaces studied are generalized cylinders and offsets of a rational B-spline surface patch progenitor.     

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

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

基于双正交非均匀B样条小波的曲线逼近方法

针对B样条曲线逼近有序数据点在应用最小二乘法时出现的计算量较大问题,提出一种基于双正交非均匀B样条小波的曲线逼近方法。其基本思想是：先用最小二乘法生成初始B样条逼近曲线,再用细节曲线逼近误差向量,接着将细节曲线叠加于原逼近曲线得到新的B样条曲线,这个过程是迭代的。细节曲线的基函数是双正交非均匀B样条小波。与传统最小二乘法相比,该方法仅需计算新增线性系统,避免重复计算原系统,降低了计算量,提高了运算效率;此外,给出了B样条逼近曲线的一种多分辨率表示形式。     

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

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

用LS-SVMs整体构造B样条曲线

由给定的空间数据点集构造B样条曲线是CAGD中一个重要研究课题,常用的逼近方法实质上是基于“经验风险”意义下的最小二乘逼近。文章讨论了基于“结构风险”意义下用最小二乘支持向量回归机整体构造B样条曲线的逼近问题,其出发点是最小化结构风险,而不是传统学习的经验风险最小化,从而在理论上保证了好的推广能力,能够实现对原始曲线的逼近而不仅仅是对测量数据点的逼近。文章建立了B样条曲线拟合的数学模型,并构造了一种特殊的核函数来保证曲线的B样条表示形式。该方法为曲线拟合问题提供了新思路,数值实验证实了可行性。     

数控加工中的二次曲线拟合与最优插补控制算法

本文提出一种基于二次B样条曲线对G01代码的拟合及插补方法,先通过自适应方法选取G01代码所描述的加工轨迹形状特征的各个特征点,再用通过所有特征点的二次B样条曲线拟合待加工路径.由于Timar等人提出的最优速度规划算法对于三次及三次以上的高阶次样条曲线的计算极为复杂,本文提出了一种改进的基于二次B样条曲线的时间最优插补计算方法.最后,将所提出的算法应用到实际的图案加工仿真与实际数控加工中.     

Curve fitting and optimal interpolation on CNC machines based on quadratic B-splines

In this paper,curve fitting of 3-D points generated by G01 codes and interpolation based on quadratic B-splines are studied.Feature points of G01 codes are selected using an adaptive method.Next,quadratic B-splines are obtained as the fitting curve by interpolating these feature points.Computations required in implementing the velocity planning algorithm mentioned by Timer et al.are very complicated because of the appearance of high-order curves.An improved time-optimal method for the quadratic B-spline cur...     

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.     

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     

Data reduction using cubic rational B-splines

A geometric method for fitting rational cubic B-spline curves to data representing smooth curves, such as intersection curves or silhouette lines, is presented. The algorithm relies on the convex hull and on the variation diminishing properties of Bezier/B-spline curves. It is shown that the algorithm delivers fitting curves that approximate the data with high accuracy even in cases with large tolerances. The ways in which the algorithm computes the end tangent magnitudes and inner control points, fits cubic curves through intermediate points, checks the approximate error, obtains optimal segmentation using binary search, and obtains appropriate final curve form are discussed     

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

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

基于遗传算法的B样条曲线和Bézier曲线的最小二乘拟合

考虑用B样条曲线拟合平面有序数据使得最小二乘拟合误差最小.一般有两种考虑,一种是保持B样条基函数的节点不变,选择参数使得拟合较优.参数的选择方法包括均匀取值、累加弦长法、centripetal model、Gauss-Newton迭代法等.另一种则是先确定好参数值(一般用累加弦长法),然后再用.某一算法计算出节点,使得拟合较优.同时把两者统一考虑,用遗传算法同时求出参数、节点使得拟合在最小二乘误差意义下最优.与Gauss-Newton迭代法、Piegl算法相比,本方法具有较好的鲁棒性(拟合曲线与初始值无关)、较高的精度及控制顶点少等优点.实验结果说明采用遗传算法得到的曲线逼近效果更好.用遗传算法对Bezier曲线拟合平面有序数据也进行了研究.     

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.     

曲线曲面拟合中型值点参数的最优化

曲线、曲面光顺拟合的关键是寻找与型值点相应的最优参数,然后即可按最小二乘法通过建立最佳拟合方程来求出控制顶点.现有的各种参数选取法,由于没有体现最优参数的几何特征,从而使得最终的拟合精度偏低和计算的时间复杂性偏大.为了提高曲线、曲面拟合精度和计算速度,提出了一种型值点参数最优化的算法,该算法先利用点到曲线、曲面的正交投影,结合参数坐标邻域的搜索来提高计算速度,然后在曲线、曲面的迭代过程中不断修正参数,最终产生具有明显几何意义的型值点参数,以达到最佳拟合效果.与Hoschek,Carlos以及Piegl等算法的拟合结果比较表明,该算法迭代次数减少了10%～90%,计算时间复杂度降低了20%～70%,计算精确度提高了40%左右.     

Recursively generated B-spline surfaces on arbitrary topological meshes

This paper describes a method for recursively generating surfaces that approximate points lying-on a mesh of arbitrary topology. The method is presented as a generalization of a recursive bicubic B-spline patch subdivision algorithm. For rectangular control-point meshes, the method generates a standard B-spline surface. For non-rectangular meshes, it generates surfaces that are shown to reduce to a standard B-spline surface except at a small number of points, called extraordinary points. Therefore, everywhere except at these points the surface is continuous in tangent and curvature. At the extraordinary points, the pictures of the surface indicate that the surface is at least continuous in tangent, but no proof of continuity is given. A similar algorithm for biquadratic B-splines is also presented.     

基于动态参数化的二次B样条插值曲线

参数化为构造B样条插值曲线提供了自由度,但在以往的研究中,这些自由度并未得到充分利用．该文给出的二次B样条曲线插值方法充分利用了参数化的自由度,直接利用插值曲线直观的几何约束条件如曲线在数据点处的切向、曲线段的相对高度等进行参数化,使得构造出的插值曲线不仅在两端,而且在中间各段具有预期的几何性质．该文的方法比起以往的参数化方法来,能更直观有效地控制插值曲线的形状．而且,所构造的插值曲线具有局部性质或近似局部性质,即当改变某个数据点的位置时,插值曲线的形状只作局部改变或除局部范围外,曲线形状改变很小或完全不变．不同于以往的插值方法,该文的方法在构造插值曲线的过程中根据曲线的几何约束条件动态地递推确定参数值、节点向量和控制顶点,整个过程不必解方程组,计算简便．该文还给出了相应的算法和应用例子．实验结果表明,该文的方法十分有效．     

燃气燃爆实验数据的多约束B 样条曲线拟合

样条拟合是数据处理的重要方法,该文给出一个实际工程中多条件约束拟合的典型 实例。燃气燃爆分析是涉及安全生产的重要问题,精确安全的燃爆边界有助于危险预测和控制。 该文对消防公司的实验数据进行分析,基于多约束样条拟合方法,给出了油气燃爆界和爆炸强度 曲线。具体地,将燃气燃爆不同特性转化数学约束条件并做合理简化,在这些约束条件下进行曲线 拟合,得到具备燃爆特征的爆炸强度曲线。该方法不受维数限制,可以推广用于多因素燃爆分析。     

带法向约束的隐式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样条曲线相比,本文方法减少了控制系数的数量,提高了运算速度。     

Efficient planar object tracking and parameter estimation usingcompactly represented cubic B-spline curves

In this paper, we consider the problem of matching 2D planar object curves from a database, and tracking moving object curves through an image sequence. The first part of the paper describes a curve data compression method using B-spline curve approximation. We present a new constrained active B-spline curve model based on the minimum mean square error (MMSE) criterion, and an iterative algorithm for selecting the “best” segment border points for each B-spline curve. The second part of the paper describes a method for simultaneous object tracking and affine parameter estimation using the approximate curves and profiles. We propose a novel B-spline point assignment algorithm which incorporates the significant corners for interpolating corresponding points on the two curves to be compared. A gradient-based algorithm is presented for simultaneously tracking object curves, and estimating the associated translation, rotation and scaling parameters. The performance of each proposed method is evaluated using still images and image sequences containing simple objects