Data fitting with Bezier curves



In the present paper Bezier curves for data fitting by least squares method is developed. The problem is solved by constructing so-called minimizing sequence of control points.

Keywords: Bezier Curve, data fitting.

Bezier curves are widely used in computer graphics to produce smooth curves. The curves are named after a French engineer Pierre Bezier who was an applied mathematician with the car manufacturer Renault. In the early 1960s, encouraged by his employer, he began searching for ways to automate the process of designing cars. His method has been the basis of the modern field of Computer Aided Geometric Design (CAGD), a field with practical applications in many areas.

One of the most common applications of Bezier curves is data fitting. Present study will consider this problem. Bezier curves have many applications in image processing, pattern control and computer graphics.

The Main Problem. Consider that there are n points in a plane:

(1)

where , and is the Bernstein polynomial (). The parametric curves that are defined by the (1) are called Bezier curve of degree n. points are called control points․

Suppose there are N points in the plane

Consider the following function

(2)

where the first N variables are changed in [0,1] interval and is the Bezier curve of degree n with control points.

The Main Problem. Find the minimum point of .

If , then we can find the control points, in case of which the value of F is equal to 0. Thus, we will consider those cases where . Note also that minimum of function F is not always available. For example, if we consider these points

then we can show that there is not Bezier curve of degree n, that can pass all points. But exists a sequence of Bezier curves of degree n, that approaches to these points.

Matrix Representation of Bezier Curves. Equation (1) showed that a Bezier curve is described by

(3)

, (4)

(5)

After above mentioned definitions B(t) will have the following form

(6)

Suppose are given (). Indicate with T the vector .

(7)

(8)

(9)

(10)

4. The Main Problem in Case of Fixed T. Before taking into consideration algorithm, that minimizes the F function defined by (2), let’s consider F function in case of fixed , that is the function is dependent only on control points.

(11)

Subproblem 1. Find such points, in case of which

(12)

The solution of this subproblem according to (9) is

(13)

where is ps––eudoinverse of W.

The Distance of aPoint from Bezier Curve. Suppose we have fixed point in a plane and also a fixed Bezier curve of degree n. Let’s define the following function

(14)

where B(t) is a Bezier curve of degree n.

Problem 5.1. Find , in case of which

(15)

In fact, is the closest point on the curve to the point .

Fig. 1

The algorithm, that solves problem 1 is described in [5; p. 3], which is the fastest algorithm that finds the closest point for Bezier curves.

The Main Problem in Case of Fixed Control Points. Let’s fix some control points and consider F function in case of fixed control points, that is

(16)

where B(t) is a Bezier curve of degree n.

Subproblem 2. Find such , in case of which

(17)

It is not difficult to note, that this problem is equivalent to find , such that . That is, for each should be solved problem 5.1 (find the closest point for on to ).

Fig. 2

Algorithm for minimizing the main problem. Using the solutions of subproblems 1, 2; let’s describe algorithm that minimizes the function F described by (2).

The Main Algorithm

1) Input data

2) First step of algorithm:

3)

Compute , where

….

….

Solve the subproblem2 for and assign the answer by . Calculate , where F is defined by (2).

4) In step k take numerical vector from step (k-1) and solve subproblem1 for and assign the answer by . Solve the subproblem2 for and assign the answer by . Calculate , where F is defined by (2.2). If , then pass point 4.

5) Output

End

Lemma. A sequence of numbers has limit.

Proof. As in each step of algorithm doesn’t increase and for

, so, it has limit.

AFew Experiments on The Basis of Main Algorithm. In this section we will represent the results of our main algorithm in case of and we will fit data with cubic Bezier curves.

Example 1. Suppose N=20 and as initial data take

Applying the main algorithm on the data after 31 steps we got the following result for control points

Fig. 3

In the table 1 we will represent values of in case

Table 1

1	166.687
3	7.91627
5	2.64736
15	1.41002
25	1.38272
31	1.38177

Example 2. Take N=50 and from square [-20,20]x [-20,20] choose 50 points randomly and match with .

Fig. 4

In this example algorithm made 9871 steps and we got the following results for control points

In the table 2 we will represent values for in case

Table 2

1	2723.89
25	1219.86
50	1207.84
100	1200.19
250	1194.24
500	1191.79
1000	1190.37
2000	1115.9
3000	1074.16
4000	1072.32
5000	1071.57
6000	1071.16
7000	1070.89
8000	1070.7
9871	1070.46

Conclusion. In this paper we have developed an approach to solve a problem regarding least squares data fitting by Bezier curves. To solve data fitting problem we have considered a minimizing algorithm. Numerical experiments confirm the practical effectiveness of the proposed method.

References:

1. Д.Роджерс, Дж. Адамс. Математические основы машинной графики.- М.: Мир, 2001.
2. G.Farin. Curves and Surfaces for Computer Aided Geometric Design.- Academic Press, 1997.
3. A.Quarteroni, R.Sacco, F.Saleri. Numerical Mathematics. - Springer, 2007.
4. L.Shao, H.Zhou. Curve fitting with Bezier cubics.- Graphical Models and Image Processing, v.58, No.3, 1996, 223–232.
5. Improved Algebraic Algorithm On Point Projection For Bézier Curves. — Текст: электронный // Hal-Inria: [сайт]. — URL: https://hal.inria.fr/file/index/docid/518379/filename/Xiao-DiaoChen2007c.pdf (дата обращения: 29.05.2020).