-spline curve fitting based on adaptive curve refinement using dominant points
Introduction
-spline curve approximation is one of the classic problems that have been established in the field of computer aided geometric design [1], [2]. Nonetheless -spline curve approximation is still an essential operation in many applications. For example, large amounts of data created in various processes of engineering design must be approximated by smooth -spline curves.
In -spline curve approximation to a sequence of points, a -spline curve is sought that approximates the points in a way that the curve satisfies a criterion of approximation quality. In practical applications, a tolerance is specified in order to obtain a -spline curve satisfying that the distance between the curve and the given points should be less than the tolerance. The resulting curve is called error-bounded. The important issue in -spline curve approximation is to reduce the number of knots and the number of control points while keeping the desired accuracy. As it is usually not known in advance how many control points are required to obtain the accuracy, the problem generally requires an iterative process that adjusts the number of control points, the parameter values, and the knots to maintain an error bound [1], [2], [3], [4], [5]. Least-squares curve fitting is often used as one step in this iterative process.
In this paper, we present a new approach for -spline curve fitting to a set of ordered points. This work stems from an insight that some points properly selected from the given points play an important role in yielding better approximations. These points are called dominant points. Fig. 1 is an example showing a comparison between the conventional approach and the proposed approach. Fig. 1(a) shows 101 input points sampled from the side profile of the human facial shape. Their parameter values are drawn below the point set. Fig. 1(b) shows a cubic -spline curve obtained by the traditional approach with 15 control points. Its knot vector is drawn below the curve. Note that significant gaps between the curve and the point set are found around the nose and the mouth. Fig. 1(c) shows 15 dominant points chosen from the point set. Big solid dots denote dominant points. The parameter values of the dominant points and the knots are drawn in the lowest part of the figure. Fig. 1(d) shows a cubic -spline curve obtained by the proposed approach with 15 control points. Its knot vector is drawn below the curve. Note that the gaps between the curve and the point set are reduced significantly. Compare the knot vectors obtained by the two approaches.
The proposed approach for -spline curve fitting takes four main steps: parameterization, dominant point selection, knot placement, and least-squares minimization. The approach is substantially different from the conventional approaches in knot placement and dominant point selection. In the knot placement, the knots are determined by averaging the parameter values of the dominant points. Thus the approach basically transforms -spline curve fitting into the problem of selecting dominant points among the given points. We present the properties of the knot placement including the property of local modification useful for adaptive refinement of a -spline curve. We also present an algorithm for proper selection of dominant points based on the adaptive refinement paradigm.
With the knot placement and the dominant point selection presented, the proposed approach can realize the concept of adaptive curve refinement that fewer curve segments are generated at flat regions but more at complex regions. Consequently, for the same number of control points, the approach can generate a -spline curve with less deviation from the point set than the conventional approaches presented in previous works [1], [2], [3], [6]. The proposed approach can be adopted as a key ingredient for the iterative process of error-bounded -spline curve approximation, playing an important role in generating a -spline curve with far fewer control points while satisfying the desired shape fidelity.
The rest of the paper is organized as follows: In Section 2, related works on -spline curve fitting are briefly described. In Section 3, details on the proposed approach for -spline curve fitting are described. In Section 4, experimental results are given to demonstrate the usefulness and quality of the approach. In Section 5, the proposed approach is further discussed. Section 6 closes the paper.
Section snippets
Related works
We assume that the reader is familiar with the concepts of -spline curves [1], [2]. A parametric -spline curve of order (degree + 1) is defined by where are control points and are the normalized -spline functions of order defined on a knot vector . The knot vector T consists of non-decreasing real-valued knots and mostly its first and last knots are repeated with multiplicity equal to order as follows:
Proposed approach
Based on the insight illustrated in Fig. 1, we propose a novel approach for -spline curve fitting, which takes the following steps:
- (1)
Compute the parameter values of all the given points.
- (2)
Select a specified number of dominant points from the points.
- (3)
Determine knots by using the parameter values of the selected dominant points.
- (4)
Using Eq. (2), perform the least-squares minimization in order to obtain a -spline curve that approximates all the points.
Throughout the paper, the proposed approach is
Experimental results
We implemented the proposed approach (DOM) with the conventional approaches to -spline curve fitting using the knot placement techniques KTP and NKTP. The implementation was performed in the C language on an IBM compatible personal computer with an Intel Pentium IV processor. Using various point sets, we firstly compared the proposed approach with the approaches using KTP and NKTP by the deviation incurred with a given number of control points. The results have shown that the proposed approach
Discussion
The proposed approach is discussed in computational performance and robustness to noise, and it is briefly described how to combine the approach with the others for further improvement of the quality of a resulting curve.
Concluding remarks
We have proposed a new approach for -spline curve fitting to a sequence of points. Once dominant points are selected, knots are determined using their parameters, and a -spline curve is easily obtained by least squares minimization. We described the interesting properties of the knot placement using dominant points. Among them, the property of local modification has been found to be very useful for adaptive curve refinement. We also presented an algorithm for dominant point selection based on
Hyungjun Park received his BS, MS, and PhD in Industrial Engineering from POSTECH (Pohang University of Science and Technology), Korea, in 1991, 1993, and 1996, respectively. From 1996 to 2001, he worked as a senior researcher at Samsung Electronics, Korea. He involved in developing commercial CAD/CAM software and in-house software for modeling and manufacturing aspheric lenses used in various optical products. Since 2001, he has been a faculty member of Industrial Engineering at Chosun
References (26)
- et al.
Constrained -spline curve and surface fitting
Computer-Aided Design
(1989) - et al.
Parameter optimization in approximating curves and surfaces to measurement data
Computer Aided Geometric Design
(1991) An error-bounded approximate method for representing planar curves in -splines
Computer Aided Geometric Design
(2004)- et al.
Multidimensional curve fitting to unorganized data points by nonlinear minimization
Computer-Aided Design
(1995) - et al.
Optimization of a NURBS representation
Computer-Aided Design
(1993) Intrinsic parameterization for approximation
Computer Aided Geometric Design
(1988)- et al.
Global reparametrization for curve approximation
Computer Aided Geometric Design
(1998) Fair interpolation and approximation of -splines by energy minimization and points insertion
Computer-Aided Design
(1996)- et al.
A method for approximate NURBS curve compatibility based on multiple curve refitting
Computer-Aided Design
(2000) - et al.
Knot removal for parametric -spline curves and surfaces
Computer Aided Geometric Design
(1987)
Adaptive knot placement in -spline curve approximation
Computer-Aided Design
Data point selection for piecewise linear curve approximation
Computer Aided Geometric Design
Adaptive fairing of digitized data with discrete curvature
Computer-Aided Design
Cited by (216)
The deep neural network solver for B-spline approximation
2024, CAD Computer Aided DesignAero-engine pipe gap automatic detection based on 3D scanning point clouds
2024, Measurement: Journal of the International Measurement ConfederationAn adaptive B-spline representation of topology optimization design for Additive Manufacturing
2023, Advances in Engineering SoftwareA residuals-distribution-guided local optimization approach to B-spline fitting in capturing image outlines
2023, Computers and Graphics (Pergamon)2D NURBS Curve discretization method with double constraints of area and chord error and contour accuracy prediction modeling
2023, Simulation Modelling Practice and Theory
Hyungjun Park received his BS, MS, and PhD in Industrial Engineering from POSTECH (Pohang University of Science and Technology), Korea, in 1991, 1993, and 1996, respectively. From 1996 to 2001, he worked as a senior researcher at Samsung Electronics, Korea. He involved in developing commercial CAD/CAM software and in-house software for modeling and manufacturing aspheric lenses used in various optical products. Since 2001, he has been a faculty member of Industrial Engineering at Chosun University, Korea. His current research interests include geometric modeling, virtual prototyping of engineered products, 3D shape reconstruction using reverse engineering, bio-medical engineering, and CAD/CAM/CG applications.
Joo-Haeng Lee received his BS, MS, and PhD in Computer Science from POSTECH, Korea, in 1994, 1996 and 1999, respectively. He joined ETRI (Electronics and Telecommunications Research Institute), Korea in 1999, and is a Senior Researcher at Digital Actor Team, Digital Contents Division. His research interests include geometric modeling and processing algorithms for computer graphics, CAD, and robotics. He is also interested in embedding intelligence for computer graphics, CAD, and robotics applications.