Knot calculation for spline fitting via sparse optimization

Curve fitting with splines is a fundamental problem in computer-aided design and engineering. However, how to choose the number of knots and how to place the knots in spline fitting remain a difficult issue. This paper presents a framework for computing knots (including the number and positions) in curve fitting based on a sparse optimization model. The framework consists of two steps: first, from a dense initial knot vector, a set of active knots is selected at which certain order derivative of the spline is discontinuous by solving a sparse optimization problem; second, we further remove redundant knots and adjust the positions of active knots to obtain the final knot vector. Our experiments show that the approximation spline curve obtained by our approach has less number of knots compared to existing methods. Particularly, when the data points are sampled dense enough from a spline, our algorithm can recover the ground truth knot vector and reproduce the spline.     

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

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

B-Spline Curve Approximation by Utilizing Big Bang-Big Crunch Method

The location of knot points and estimation of the number of knots are undoubtedly known as one of the most difficult problems in B-Spline curve approximation. In the literature, different researchers have been seen to use more than one optimization algorithm in order to solve this problem. In this paper, Big Bang-Big Crunch method (BB-BC) which is one of the evolutionary based optimization algorithms was introduced and then the approximation of B-Spline curve knots was conducted by this method. The technique of reverse engineering was implemented for the curve knot approximation. The detection of knot locations and the number of knots were randomly selected in the curve approximation which was performed by using BB-BC method. The experimental results were carried out by utilizing seven different test functions for the curve approximation. The performance of BB-BC algorithm was examined on these functions and their results were compared with the earlier studies performed by the researchers. In comparison with the other studies, it was observed that though the number of the knot in BB-BC algorithm was high, this algorithm approximated the B-Spline curves at the rate of minor error.     

Approximation and estimation bounds for free knot splines

The fitting to data by splines has long been known to improve dramatically if the knots can be adjusted adaptively. To demonstrate the quality of the obtained free knot spline, it is essential to characterize its generalization ability. By utilizing the powerful techniques of the empirical process and approximation theory to address the estimation and approximation error bounds, respectively, the generalization ability of the free knot spline learning strategy is successfully characterized. We show that the Pseudo-dimension of free knot splines is essentially a linear function of the number of knots. A class of rather general loss functions is considered here and the squared loss is specially treated for its excellent property. We also provide some numerical results to demonstrate the utility of these theoretical results in guiding the process of choosing the appropriate knot numbers through the training data to avoid the overfitting/underfitting problem.     

Fitting optimal piecewise linear functions using genetic algorithms

Constructing a model for data in R² is a common problem in many scientific fields, including pattern recognition, computer vision, and applied mathematics. Often little is known about the process which generated the data or its statistical properties. For example, in fitting a piecewise linear model, the number of pieces, as well as the knot locations, may be unknown. Hence, the method used to build the statistical model should have few assumptions, yet, still provide a model that is optimal in some sense. Such methods can be designed through the use of genetic algorithms. We examine the use of genetic algorithms to fit piecewise linear functions to data in R². The number of pieces, the location of the knots, and the underlying distribution of the data are assumed to be unknown. We discuss existing methods which attempt to solve this problem and introduce a new method which employs genetic algorithms to optimize the number and location of the pieces. Experimental results are presented which demonstrate the performance of our method and compare it to the performance of several existing methods, We conclude that our method represents a valuable tool for fitting both robust and nonrobust piecewise linear functions     

Data fitting with a spline using a real-coded genetic algorithm

To obtain a good approximation for data fitting with a spline, frequently we have to deal with knots as variables. The problem to be solved then becomes a continuous nonlinear and multivariate optimization problem with many local optima. Therefore, it is difficult to obtain the global optimum. In this paper, we propose a method for solving this problem by using a real-coded genetic algorithm. Our method can treat not only data with a smooth underlying function, but also data with an underlying function having discontinuous points and/or cusps. We search for the best model among candidate models by using the Bayes Information Criterion (BIC). With this, we can appropriately determine the number and locations of knots automatically and simultaneously. Five examples of data fitting are given to show the performance of our method.     

A new iterative mutually coupled hybrid GA–PSO approach for curve fitting in manufacturing

Fitting data points to curves (usually referred to as curve reconstruction) is a major issue in computer-aided design/manufacturing (CAD/CAM). This problem appears recurrently in reverse engineering, where a set of (possibly massive and noisy) data points obtained by 3D laser scanning have to be fitted to a free-form parametric curve (typically a B-spline). Despite the large number of methods available to tackle this issue, the problem is still challenging and elusive. In fact, no satisfactory solution to the general problem has been achieved so far. In this paper we present a novel hybrid evolutionary approach (called IMCH-GAPSO) for B-spline curve reconstruction comprised of two classical bio-inspired techniques: genetic algorithms (GA) and particle swarm optimization (PSO), accounting for data parameterization and knot placement, respectively. In our setting, GA and PSO are mutually coupled in the sense that the output of one system is used as the input of the other and vice versa. This coupling is then repeated iteratively until a termination criterion (such as a prescribed error threshold or a fixed number of iterations) is attained. To evaluate the performance of our approach, it has been applied to several illustrative examples of data points from real-world applications in manufacturing. Our experimental results show that our approach performs very well, being able to reconstruct with very high accuracy extremely complicated shapes, unfeasible for reconstruction with current methods.     

Automatic knot adjustment using an artificial immune system for B-spline curve approximation

Reverse engineering transforms real parts into engineering concepts or models. First, sampled points are mapped from the object’s surface by using tools such as laser scanners or cameras. Then, the sampled points are fitted to a free-form surface or a standard shape by using one of the geometric modeling techniques. The curves on the surface have to be modeled before surface modeling. In order to obtain a good B-spline curve model from large data, the knots are usually respected as variables. A curve is then modeled as a continuous, nonlinear and multivariate optimization problem with many local optima. For this reason it is very difficult to reach a global optimum. In this paper, we convert the original problem into a discrete combinatorial optimization problem like in Yoshimoto et al. [F. Yoshimoto, M. Moriyama, T. Harada, Automatic knot placement by a genetic algorithm for data fitting with a spline, in: Proceedings of the International Conference on Shape Modeling and Applications, IEEE Computer Society Press, 1999, pp. 162-169] and Sarfraz et al. [M. Sarfraz, S.A. Raza, Capturing outline of fonts using genetic algorithm and splines, in: Fifth International Conference on Information Visualisation (IV’01), 2001, pp. 738-743]. Then, we suggest a new method that solves the converted problem by artificial immune systems. We think the candidates of the locations of knots as antibodies. We define the affinity measure benefit from Akaike’s Information Criterion (AIC). The proposed method determines the appropriate location of knots automatically and simultaneously. Furthermore, we do not need any subjective parameter or good population of initial location of knots for a good iterative search. Some examples are also given to demonstrate the efficiency and effectiveness of our method.     

带参数的多结点样条

多结点样条函数是在通常样条函数中引入更多的附加结点，其优越性表现在使插值过程无须求解任何方程组，而且有局部性，对多结点样条函数做进一步研究，构造了一类带参数的多结点样条基本函数．该类函数不仅保持了一般多结点样条函数的优点，而且由于参数的引进，使得基数型的插值公式可形成一族，可以根据实际问题的需要在函数(曲线)族中作出最优选择．文中研究的带参数的多结点样条函数，除了能用于表达平滑的数据及几何造型之外。尤其能适应波动较大、频率较高的数据拟合问题，有助于解决信号处理及非规则几何造型的一些问题。     

Surface reconstruction using bivariate simplex splines on Delaunay configurations

Recently, a new bivariate simplex spline scheme based on Delaunay configuration has been introduced into the geometric computing community, and it defines a complete spline space that retains many attractive theoretic and computational properties. In this paper, we develop a novel shape modeling framework to reconstruct a closed surface of arbitrary topology based on this new spline scheme. Our framework takes a triangulated set of points, and by solving a linear least-square problem and iteratively refining parameter domains with newly added knots, we can finally obtain a continuous spline surface satisfying the requirement of a user-specified error tolerance. Unlike existing surface reconstruction methods based on triangular B-splines (or DMS splines), in which auxiliary knots must be explicitly added in advance to form a knot sequence for construction of each basis function, our new algorithm completely avoids this less-intuitive and labor-intensive knot generating procedure. We demonstrate the efficacy and effectiveness of our algorithm on real-world, scattered datasets for shape representation and computing.     

Iterative two-step genetic-algorithm-based method for efficient polynomial B-spline surface reconstruction

Surface reconstruction is a very challenging problem arising in a wide variety of applications such as CAD design, data visualization, virtual reality, medical imaging, computer animation, reverse engineering and so on. Given partial information about an unknown surface, its goal is to construct, to the extent possible, a compact representation of the surface model. In most cases, available information about the surface consists of a dense set of (either organized or scattered) 3D data points obtained by using scanner devices, a today’s prevalent technology in many reverse engineering applications. In such a case, surface reconstruction consists of two main stages: (1) surface parameterization and (2) surface fitting. Both tasks are critical in order to recover surface geometry and topology and to obtain a proper fitting to data points. They are also pretty troublesome, leading to a high-dimensional nonlinear optimization problem. In this context, present paper introduces a new method for surface reconstruction from clouds of noisy 3D data points. Our method applies the genetic algorithm paradigm iteratively to fit a given cloud of data points by using strictly polynomial B-spline surfaces. Genetic algorithms are applied in two steps: the first one determines the parametric values of data points; the later computes surface knot vectors. Then, the fitting surface is calculated by least-squares through either SVD (singular value decomposition) or LU methods. The method yields very accurate results even for surfaces with singularities, concavities, complicated shapes or nonzero genus. Six examples including open, semi-closed and closed surfaces with singular points illustrate the good performance of our approach. Our experiments show that our proposal outperforms all previous approaches in terms of accuracy and flexibility.     

A distributed graph algorithm for the detection of local cycles andknots

In this paper, a distributed cycle/knot detection algorithm for general graphs is presented. The algorithm distinguishes between cycles and knots and is the first algorithm to our knowledge which does so. It is especially relevant to an application such as parallel simulation in which 1) cycles and knots can arise frequently 2) the size of the graph is very large, and 3) it is necessary to know if a given node is in a cycle or a knot. It requires less communication than previous algorithms-2m vs. (at least) (4m) for the Chandy and Misra algorithm, where m is the number of links in the graph. It requires O (nlog (n)) bits of memory, where n is the number of nodes. The algorithm differs from the classical diffusing computation methods through its use of incomplete search messages to speed up the computation. We introduce a marking scheme in order to identify strongly connected subcomponents of the graph which cannot reach the initiator of the algorithm. This allows us to distinguish between the case in which the initiator is in a cycle (only) or is in a knot     

Iteration and optimization scheme for the reconstruction of 3D surfaces based on non-uniform rational B-splines

Curve or surface reconstruction is a challenging problem in the fields of engineering design, virtual reality, film making and data visualization. Non-uniform rational B-spline (NURBS) fitting has been applied to curve and surface reconstruction for many years because it is a flexible method and can be used to build many complex mathematical models, unlike certain other methods. To apply NURBS fitting, there are two major difficult sub-problems that must be solved: (1) the determination of a knot vector and (2) the computation of weights and the parameterization of data points. These two problems are quite challenging and determine the effectiveness of the overall NURBS fit. In this study, we propose a new method, which is a combination of a hybrid optimization algorithm and an iterative scheme (with the acronym HOAAI), to address these difficulties. The novelties of our proposed method are the following: (1) it introduces a projected optimization algorithm for optimizing the weights and the parameterization of the data points, (2) it provides an iterative scheme to determine the knot vectors, which is based on the calculated point parameterization, and (3) it proposes the boundary-determined parameterization and the partition-based parameterization for unorganized points. We conduct numerical experiments to measure the performance of the proposed HOAAI with six test problems, including a complicated curve, twisted and singular surfaces, unorganized data points and, most importantly, real measured data points from the Mashan Pumped Storage Power Station in China. The simulation results show that the proposed HOAAI is very fast, effective and robust against noise. Furthermore, a comparison with other approaches indicates that the HOAAI is competitive in terms of both accuracy and runtime costs.     

Approximate merging of B-spline curves via knot adjustment and constrained optimization

This paper addresses the problem of approximate merging of two adjacent B-spline curves into one B-spline curve. The basic idea of the approach is to find the conditions for precise merging of two B-spline curves, and perturb the control points of the curves by constrained optimization subject to satisfying these conditions. To obtain a merged curve without superfluous knots, we present a new knot adjustment algorithm for adjusting the end k knots of a kth order B-spline curve without changing its shape. The more general problem of merging curves to pass through some target points is also discussed.     

基于极小化二阶导矢确定节点

构造参数拟合曲线的关键问题之一是为每个数据点指定一个参数值（节点）。提出了一种确定节点的新方法。对于每个数据点,新方法由相邻的三个数据点构造一条二次多项式曲线,二次曲线的节点通过极小化其二阶导矢的平方确定。两个相邻数据点间的节点区间由两条二次曲线确定。为使节点计算公式能有效反映出相邻数据点的变化情况,新方法改进了修正弦长方法并应用于节点计算。新方法是一个局部化方法,因此适合于曲线曲面的交互设计。实验结果说明,新方法比其他节点计算方法有效。     

基于改进YOLOv3的木结缺陷检测方法研究

针对木条表面死结和活结缺陷在检测过程中定位困难、平均识别精确度较低、检测速度较慢的问题,在分析木结缺陷特点和改进深度学习YOLOv3模型的基础上,研究其应用于改善木结缺陷检测时的精确度和速度。首先,对活结缺陷图像进行数据扩增,以解决类别不平衡问题。然后,改进k-means++算法,提升木结缺陷目标框的维度聚类效果,得到更合适的初始目标框个数与尺寸;通过缩减YOLOv3中多尺度检测网络、改进损失函数,以减少检测时间和提高目标识别精确度。最后,对木结缺陷进行拼接得出位置坐标。试验结果表明,较改进前YOLOv3算法,mAP值提升7.47%,检测速度提高35%;较Faster R-CNN算法mAP值提升11.68%,检测速度提高约15倍,改进后模型能精确地检测出死结和活结缺陷。因此,在后续研究中,可考虑以YOLOv3算法作为检测木结缺陷模型,进一步改进YOLOv3网络,以提高检测实时性和精确度。     

Algorithm/algorithmus 42 an algorithm for cubic spline fitting with convexity constraints

In this paper an algorithm is presented for fitting a cubic spline satisfying certain local concavity and convexity constraints, to a given set of data points. When using theL ₂ norm, this problem results in a quadratic programming problem which is solved by means of the Theil-Van de Panne procedure. The algorithm makes use of the well-conditioned B-splines to represent the cubic splines. The knots are located automatically, as a function of a given upper limit for the sum of squared residuals. A Fortran IV implementation is given.     

Suboptimal Robot Joint Interpolation Within User-Specified Knot Tolerances

Approximation of a desired robot path can be accomplished by interpolating a curve through a sequence of joint-space knots. A smooth interpolated trajectory can be realized by using trigonometric splines. But, sometimes the joint trajectory is not required to exactly pass through the given knots. The knots may rather be centers of tolerances near which the trajectory is required to pass. In this article, we optimize trigonometric splines through a given set of knots subject to user-specified knot tolerances. The contribution of this article is the straightforward way in which intermediate constraints (i.e., knot angles) are incorporated into the parameter optimization problem. Another contribution is the exploitation of the decoupled nature of trigonometric splines to reduce the computational expense of the problem. The additional freedom of varying the knot angles results in a lower objective function and a higher computational expense compared to the case in which the knot angles are constrained to exact values. The specific objective functions considered are minimum jerk and minimum torque. In the minimum jerk case, the optimization problem reduces to a quadratic programming problem. Simulation results for a two-link manipulator are presented to support the results of this article.     

Knot placement for piecewise polynomial approximation of curves

For piecewise polynomial representation of curves, an algorithm to create knots is presented. The aim is to minimize the interpolation error for a given number of knots or, conversely, the number of knots needed to interpolate within a tolerance. The method used is a modification of de Boor's knot placement scheme. The algorithm described in this paper has been realized in the CADCAM system SYRKO, a Daimler-Benz development for car body design and manufacturing.