Аппроксимация данных сплайнами Безье

  Сплайн (от англ. spline, – гибкое лекало, гибкая плазовая рейка – полоса металла, используемая для черчения кривых линий) – функция, область определения которой разбита на конечное число отрезков, на каждом из которых сплайн совпадает с некоторым алгебраическим многочленом. Максимальная степень из использованных полиномов называется степенью сплайна. Разность между степенью сплайна и получившейся гладкостью называется дефектом сплайна. Например, непрерывная ломаная есть сплайн степени 1 и дефекта 1. В современном понимании сплайны – это решения многоточечных краевых задач сеточными методами.

  Чтобы наглядно продемонстрировать приведенные понятия сплайна, степени сплайна и дефекта сплайна, рассмотрим следующую задачу: имеется совокупность экспериментальных данных, необходимо максимально точность аппроксимировать последовательность данных полиномиальной функцией n-го порядка с достоверностью не менее 95 %. В качестве базового выбираем метод полиномиальной аппроксимации с помощью так называемого сплайна Безье. Данный метод наиболее актуален для реализации в компьютерном алгоритме.

   Сплайны (кривые) Безье или Кривые Бернштейна-Безье разработаны в 60-х годах XX века независимо друг от друга Пьером Безье из автомобилестроительной компании «Рено» и Полем де Кастельжо из компании «Ситроен», где применялись для проектирования кузовов автомобилей [1].

 Кривая Безье относится к полиномам третьего порядка и уникально определяется четырьмя точками. Обозначим эти точки p0 (начальная), p1, p2 (две управляющие) и p3 (конечная). Обозначенные точки будут иметь координаты: (x0, y0), (x1, y1), (x2, y2) и (x3, y3). Полином третьего порядка, задающий координаты точек в двумерном пространстве, выражается параметрическими уравнениями общего вида:

 

(1)


где ax, bx, cx, dx, ay, by, cy и dy – константы, a параметр t меняется от 0 до 1.

  Любая кривая Безье уникально определяется этими 8 константами. Их значения зависят от координат четырех точек, задающих кривую. Цель этой задачи – вывести уравнения для расчета восьми констант по заданным координатам четырех точек.

  Первое допущение для вывода этих уравнений заключается в том, что кривая Безье начинается в точке с координатами (x0, y0) при t = 0:

 Даже такое простое допущение позволяет продвинуться в выводе уравнений для констант. Подставив в параметрические уравнения t = 0, получим:

  Это означает, что две из констант – это просто координаты начальной точки:

(2)


(3)


   Второе допущение, касающееся кривой Безье: она заканчивается в точке с координатами (x3, y3) при t = 1:

   Подставив в параметрические уравнения (1) вместо t единицу, получаем:

что означает наличие следующей связи между константами и координатами конечной точки:

(4)


(5)


   Остальные допущения касаются первых производных параметрических уравнений, описывающих угол наклона кривой. Первую производную параметрического уравнения общего вида, задающего полином третьего порядка как функцию переменной t, можно записать так:

    Нас, в частности, интересует угол наклона кривой в конечных точках. Как известно, прямая, проведенная из начальной точки через первую управляющую точку, проходит по касательной к кривой Безье и направлена в ту же сторону, что и кривая. Обычно эту прямую задают параметрическими уравнениями:

где t изменяется от 0 до 1. Но можно задать ее иначе:

где t изменяется от 0 до 1/3.

   Почему именно 1/3? Дело в том, что длина той части кривой Безье, по касательной к которой проходит прямая, проведенная из точки p0 через p1, направленная в ту же сторону, что и кривая, равна 1/3 от общей длины кривой. Первые производные модифицированных параметрических уравнений можно записать так:

   Если нужно рассчитать по этим уравнениям угол наклона кривой Безье при t = 0, то:

   Подставив t = 0 в уравнение первой производной полинома третьего порядка, получим:

   Это позволяет записать равенство:

(6)


(7)


 Последнее допущение таково: прямая, проведенная из второй управляющей точки через конечную, является касательной к кривой Безье в ее конечной точке и направлена в ту же сторону, что и кривая. Иначе говоря:

    Из уравнений общего вида следует, что:

поэтому:

(8)


(9)


  Выражения (2), (4), (6) и (8) дают четыре уравнения с четырьмя неизвестными, которые можно решить относительно ax, bx, cx и dx, выразив их через x0, x1, x2 и x3. Выполнив ряд алгебраических преобразований, получаем:

  Выражения (3), (5), (7) и (9) позволяют сделать то же самое для коэффициентов y. После этого можно подставить константы обратно в параметрическое уравнение общего вида для полинома третьего порядка:

   В сущности, на этом можно было бы закончить. Но лучше раскрыть скобки и привести подобные слагаемые. В итоге получатся более элегантные параметрические уравнения, с которыми проще работать:

(10)


(11)


   Уравнения (10) и (11) позволяют построить кривую Безье в декартовых координатах.

  На первом этапе разработки компьютерного алгоритма аппроксимации экспериментальных данных мы будем задавать кривую Безье визуальным способом, перемещая ее узловые точки в декартовой системе координат графической области экрана. Пример графического представления кривой Безье представлен на рисунке 1. Точки P0 и P3 – начальная и конечная точки кривой соответственно, P1 и P2 – управляющие точки (или точки направляющих отрезков).

Рисунок 1  К построению кривой Безье

  В качестве средства разработки выбираем среду программирования Microsoft Visual Basic 6.0. На рисунке 2 представлена форма графического интерфейса, включающая графическое поле для построения кривых, и панель параметров, расположенную в левой части формы.

Рисунок 2  Графический интерфейс пользователя программы математической аппроксимации кривой Безье

   С помощью указателя мыши пользователем задаются положения точек P0, P1, P2 и P3 сплайна Безье. Центр системы координат можно смещать, перемещая указатель мыши в графической области при нажатой правой кнопке мыши.

 Далее проведем кривую полиномиальной функции n-го порядка по кривой построенного сплайна Безье. Целью данной процедуры является переход от параметрических уравнений сплайна Безье к аналитической функции вида y=f(x) при аппроксимировании данных. На панели параметров в левой части экрана пользователем выбирается степень n полиномиальной функции. От данного параметра зависит, сколько опорных точек будет выделено на сплайне Безье, через которые проходит полиномиальная кривая, и, следовательно, точность приближения полиномиальной кривой к сплайну, также будет зависеть от выбранной степени полинома.

 Принцип построения полиномиальной кривой базируется на вычислении коэффициентов полинома:

(12)


где n – число точек на сплайне Безье, через которые проходит полиномиальная кривая.

  Для вычисления коэффициентов Ci необходимо задать опорные точки на сплайне Безье, координаты которых вычисляются по известным параметрическим уравнениям Безье (10 и 11), и подставить координаты опорных точек (xi, yi) в уравнение (12). В таком случае мы получаем систему линейных уравнений с n неизвестными:



(13)


где ai – коэффициенты системы уравнений, а0 – свободные члены.

   В представленном алгоритме система линейных уравнений вида (13) решается методом Крамера, подразумевающем преобразование системы уравнений в матрицы 3×3, 4×4, 5×5 и 6×6 для полиномиальной функции 2, 3, 4 и 5-го порядков, соответственно. Программно вычисления производятся с использованием двумерных массивов, в которые записываются столбцы основной и вспомогательных матриц Крамера, после чего производится вычисление их определителей, и находятся коэффициенты полиномиального уравнения.

 В программе реализован алгоритм автоматической корректировки коэффициентов уравнения полинома. Сущность алгоритма заключается в цикличной проверке максимального расхождения полиномиальной кривой и кривой Безье в направлении оси Y (рисунок 3). Степень сплайна Безье es равна 3, а степень полиномиальной кривой ep выбирается пользователем (2, 3, 4 или 5). Теоретически, при epes расхождение кривых сводится к нулю.

Рисунок 3  К определению степени достоверности аппроксимации (до пересчета координат опорных точек)

   С заданным шагом (по оси абсцисс) вычисляются длины вертикальных отрезков, соединяющих кривую полинома и кривую Безье (закрашенная область на рисунке 3). Длины указанных отрезков записываются в одномерный массив, после чего определяется и фиксируется наибольшая длина отрезка (максимальная величина расхождения кривых Δ). С помощью генератора случайных чисел задаются новые координаты опорных точек на кривой Безье, тем самым происходит их случайное смещение по сплайну, при этом каждая итерация заканчивается пересчетом величины Δ. Если после новой итерации величина Δ уменьшилась по сравнению с предшествующей, то полиномиальная кривая перестраивается. Визуально мы наблюдаем сближение полиномиальной кривой со сплайном Безье (рисунок 4).

Рисунок 4  К определению степени достоверности аппроксимации (максимальное приближение аппроксимирующей кривой к сплайну Безье)

  Разработанный алгоритм является эффективным инструментом для обработки эмпирических данных с использованием сплайнов. К примеру, если речь идет об интегральных кривых распределения, сплайном Безье можно задавать аппроксимирующую функцию, которая будет проходить через экспериментальные точки. При этом, конфигурация сплайна может задаваться не только ручным способом с помощью конечных и управляющих точек, а процедурно, путем проверки расходимости координат экспериментальных точек и точек, выделенных на сплайне с равной абсциссой. В конечном итоге мы получаем полиномиальную функцию n-й степени, которая будет максимально точно описывать последовательность эмпирических данных (например, как на рисунке 5).

Рисунок 5  Схематичное представление процесса аппроксимации эмпирических данных

    В случае аппроксимации интегральных кривых распределения на выходе работы алгоритма мы получаем функцию y(x), дифференцирование которой позволит построить закономерную дифференциальную гистограмму распределения dy(x) (например, как на рисунке 6).

Рисунок 6  Построение дифференциальной гистограммы распределения по аппроксимирующей полиномиальной кривой

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

[1]  Кривая Безье: Материал из Википедии – свободной энциклопедии: Версия 64994710, сохраненная в 23:11 UTC 22 августа 2014 // Википедия, свободная энциклопедия. – Электрон. дан. – Сан-Франциско: Фонд Викимедиа, 2014.

При копировании материалов ссылка на сайт www.sunspire.ru обязательна. Также, вы можете использовать библиографическую ссылку на учебное пособие:

 

"Белов, В.В. Компьютерная реализация решения научно-технических и образовательных задач: учебное пособие / В.В. Белов, И.В. Образцов, В.К. Иванов, Е.Н. Коноплев // Тверь: ТвГТУ, 2015. 108 с."

Официальная группа ВК:

Сайты-партнеры:

Центр научно-образовательных электронных ресурсов Тверского государственного технического университета:

http://cdokp.tstu.tver.ru

 

Официальный сайт Тверского государственного технического университета:

http://www.tstu.tver.ru

Русскоязычный форум по языку программирования Dark Basic Professional:

http://area.mediahouse.ru/

Открытия, Изобретения, Новые технические разработки:

http://www.belashov.info

Электронный магазин 3D моделей CGTrader:

http://www.cgtrader.com

Рейтинг@Mail.ru
Яндекс.Метрика
Топ Разработка игр
Bourabai Research - Технологии XXI века