Data fitting with Bezier curves | Статья в сборнике международной научной конференции

Отправьте статью сегодня! Журнал выйдет 13 марта, печатный экземпляр отправим 17 марта.

Опубликовать статью в журнале

Автор:

Рубрика: 1. Математика

Опубликовано в

XI международная научная конференция «Исследования молодых ученых» (Казань, июнь 2020)

Дата публикации: 02.06.2020

Статья просмотрена: 9 раз

Библиографическое описание:

Акопян, К. Г. Data fitting with Bezier curves / К. Г. Акопян. — Текст : непосредственный // Исследования молодых ученых : материалы XI Междунар. науч. конф. (г. Казань, июнь 2020 г.). — Казань : Молодой ученый, 2020. — С. 1-5. — URL: https://moluch.ru/conf/stud/archive/374/15894/ (дата обращения: 04.03.2021).



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).
Основные термины (генерируются автоматически): CAGD, URL.

Ключевые слова

Bezier Curve, data fitting

Похожие статьи

Рейтинг GaWC как метод оценки позиции городов в глобальной...

В данной статье анализируется метод оценки уровня глобализированности городов, рассматривается его теоретическая база, сильные и слабые стороны, а также приводятся...

Автоматическая поддержка документации Asp.Net Core и Angular...

В данной статье рассматривается автоматизация генерации и сопровождения документации Asp.Net Core и Angular приложения, с автоматической публикацией в GitLab.

English and Turkmen pronunciation: common errors and their causes

Эффективность использования словаря по иностранному языку... Леушиншин М.В. Использование принципа наглядности в процессе обучения [электронный ресурс]: URL...

Перспективы использования топливной системы HEUI...

URL: https://moluch.ru/archive/244/56209/ (дата обращения: 02.06.2020). На сегодняшний день неуклонно увеличивается парк автомобилей как в нашей стране в целом так, и в Вооруженных...

The description of the toponyms in Firdavs ul-Ikbаl | Статья в журнале...

URL: https://moluch.ru/archive/211/51652/ (дата обращения: 01.06.2020). The article studies toponyms from the work of Munis and Agakhi «Firdavs ul Iqbal» and their classification based on the...

Модификация архитектуры web-приложения, основанной на...

В работе рассматривается способ организации архитектуры web-приложения на основе паттерна CQRS. В основе архитектуры лежит разделение на write- и read- модели, которые используют...

Требования к разработке специализированных меток для...

Данная статья посвящена теме разработки и корректуры маркеров для AR-приложений. В настоящей работе отображается процесс взаимодействия с алгоритмом анализа маркеров...

Системы сбора информации в аспекте кибербезопасности

Данная статья заключает в себе обзор агентов и инструментов сбора данных, для наблюдения за поведением пользователей на рабочих станциях, поиска вирусов, угроз сети и ботнетов.

GRU и LSTM: современные рекуррентные нейронные сети

URL: https://moluch.ru/archive/95/21426/ (дата обращения: 04.06.2020). Рекуррентные нейронные сети (Recurrent Neural Network, RNN) — класс моделей машинного обучения...

Moodle as a successful platform for teaching foreign languages

The main objective of the paper is to show the necessity of implementing modern technologies into the process of foreign languages teaching through the example of Moodle. The paper states the major...

Похожие статьи

Рейтинг GaWC как метод оценки позиции городов в глобальной...

В данной статье анализируется метод оценки уровня глобализированности городов, рассматривается его теоретическая база, сильные и слабые стороны, а также приводятся...

Автоматическая поддержка документации Asp.Net Core и Angular...

В данной статье рассматривается автоматизация генерации и сопровождения документации Asp.Net Core и Angular приложения, с автоматической публикацией в GitLab.

English and Turkmen pronunciation: common errors and their causes

Эффективность использования словаря по иностранному языку... Леушиншин М.В. Использование принципа наглядности в процессе обучения [электронный ресурс]: URL...

Перспективы использования топливной системы HEUI...

URL: https://moluch.ru/archive/244/56209/ (дата обращения: 02.06.2020). На сегодняшний день неуклонно увеличивается парк автомобилей как в нашей стране в целом так, и в Вооруженных...

The description of the toponyms in Firdavs ul-Ikbаl | Статья в журнале...

URL: https://moluch.ru/archive/211/51652/ (дата обращения: 01.06.2020). The article studies toponyms from the work of Munis and Agakhi «Firdavs ul Iqbal» and their classification based on the...

Модификация архитектуры web-приложения, основанной на...

В работе рассматривается способ организации архитектуры web-приложения на основе паттерна CQRS. В основе архитектуры лежит разделение на write- и read- модели, которые используют...

Требования к разработке специализированных меток для...

Данная статья посвящена теме разработки и корректуры маркеров для AR-приложений. В настоящей работе отображается процесс взаимодействия с алгоритмом анализа маркеров...

Системы сбора информации в аспекте кибербезопасности

Данная статья заключает в себе обзор агентов и инструментов сбора данных, для наблюдения за поведением пользователей на рабочих станциях, поиска вирусов, угроз сети и ботнетов.

GRU и LSTM: современные рекуррентные нейронные сети

URL: https://moluch.ru/archive/95/21426/ (дата обращения: 04.06.2020). Рекуррентные нейронные сети (Recurrent Neural Network, RNN) — класс моделей машинного обучения...

Moodle as a successful platform for teaching foreign languages

The main objective of the paper is to show the necessity of implementing modern technologies into the process of foreign languages teaching through the example of Moodle. The paper states the major...