Elsevier

Computer-Aided Design

Volume 39, Issue 6, June 2007, Pages 439-451
Computer-Aided Design

B-spline curve fitting based on adaptive curve refinement using dominant points

https://doi.org/10.1016/j.cad.2006.12.006Get rights and content

Abstract

In this paper, we present a new approach of B-spline curve fitting to a set of ordered points, which is motivated by an insight that properly selected points called dominant points can play an important role in producing better curve approximation. The proposed approach 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, which basically transforms B-spline curve fitting into the problem of dominant point selection. We describe the properties of the knot placement including the property of local modification useful for adaptive curve refinement. We also present an algorithm for dominant point selection based on the adaptive refinement paradigm. The approach adaptively refines a B-spline curve by selecting fewer dominant points at flat regions but more at complex regions. For the same number of control points, the proposed approach can generate a B-spline curve with less deviation than the conventional approaches. When adopted in error-bounded curve approximation, it can generate a B-spline curve with far fewer control points while satisfying the desired shape fidelity. Some experimental results demonstrate its usefulness and quality.

Introduction

B-spline curve approximation is one of the classic problems that have been established in the field of computer aided geometric design [1], [2]. Nonetheless B-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 B-spline curves.

In B-spline curve approximation to a sequence of points, a B-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 B-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 B-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 B-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 B-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 B-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 B-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 B-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 B-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 B-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 B-spline curve approximation, playing an important role in generating a B-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 B-spline curve fitting are briefly described. In Section 3, details on the proposed approach for B-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 B-spline curves [1], [2]. A parametric B-spline curve C(t) of order (degree + 1) p is defined by C(t)=j=0nNj,p(t)bj(tp1ttn+1) where bj(j=0,,n) are control points and Nj,p(t) are the normalized B-spline functions of order p defined on a knot vector T={t0,t1,,tn+p1,tn+p}. 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 p as follows: t0=

Proposed approach

Based on the insight illustrated in Fig. 1, we propose a novel approach for B-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 B-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 B-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 B-spline curve fitting to a sequence of points. Once dominant points are selected, knots are determined using their parameters, and a B-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)

  • W. Li et al.

    Adaptive knot placement in B-spline curve approximation

    Computer-Aided Design

    (2005)
  • B. Hamann et al.

    Data point selection for piecewise linear curve approximation

    Computer Aided Geometric Design

    (1994)
  • G.H. Liu et al.

    Adaptive fairing of digitized data with discrete curvature

    Computer-Aided Design

    (2002)
  • Cited by (216)

    • Aero-engine pipe gap automatic detection based on 3D scanning point clouds

      2024, Measurement: Journal of the International Measurement Confederation
    View all citing articles on Scopus

    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.

    View full text