5-9 В-СПЛАЙНЫ

С математической точки зрения кривая, заданная вершинами многоугольника, зависит от интерполяции или аппроксимации, устанавливающей связь кривой и многоугольника. Здесь основой является выбор базисных функций. Как было отмечено в разд. 5-8, базис Бернштейна порождает кривые Безье вида (5-62), но он обладает двумя свойствами, которые ограничивают гибкость кривых. Во-первых, количество вершин многоугольника жестко задает порядок многочлена. Например, кубическая кривая должна быть задана четырьмя вершинами и тремя отрезками. Многоугольник из шести точек всегда порождает кривую пятого порядка. Единственный способ понизить степень кривой - это сократить количество вершин, а повысить степень кривой - увеличить их число.

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

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

Существует неглобальный базис, называемый базисом В-сплайна, включающий базис Бернштейна как частный случай. В-сплайны неглобальны, так как с каждой вершиной  связана своя базисная функция. Поэтому влияние каждой вершины на кривую проявляется только при тех значениях параметра, где соответствующая базисная функция не равна нулю. Базис В-сплайна также позволяет менять порядок базисных функций и, следовательно, всей кривой без изменения количества вершин. Теория В-сплайнов была предложена в работе [5-20]. Рекурсивное определение для численного решения было выведено независимо Коксом [5-21] и де Буром [5-22]. Гордон и Ризенфельд [5-15], [5-23] определяли кривые через базис В-сплайна.

Пусть  определяет кривую как функцию от параметра , тогда В-сплайн имеет вид

, ,           ,              (5-83)

где  есть  вершина многоугольника, a  - нормализованные функции базиса В-сплайна.

Для -й нормализованной функции базиса порядка  (степени ) функции базиса  определяются рекурсивными формулами Кокса-де Бура:

                    (5-84а)

и

.            (5-84b)

Величины  - это элементы узлового вектора, удовлетворяющие отношению . Параметр  изменяется от  до  вдоль кривой . Считается, что .

Формально В-сплайн определяется как полиномиальный сплайн порядка  (степени ), так как он удовлетворяет следующим условиям:

Функция  является полиномом степени  на каждом интервале .

 и ее производные порядка  непрерывны вдоль всей кривой.

Так, например, В-сплайн четвертого порядка - это кусочная кубическая кривая.

Из того что В-сплайн задается базисом В-сплайна, сразу следует еще несколько его свойств:

Сумма базисных функций В-сплайна для любого значения параметра  (см. работы [5-15] и [5-22])

.                       (5-85)

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

Кроме , все базисные функции имеют ровно один максимум.

Максимальный порядок кривой равен количеству вершин определяющего многоугольника.

Кривая обладает свойством уменьшения вариации. Кривая пересекает любую прямую не чаще, чем ее определяющий многоугольник.

Общая форма кривой повторяет форму определяющего многоугольника.

Чтобы применить к кривой любое аффинное преобразование, необходимо применить его к вершинам определяющего многоугольника.

Кривая лежит внутри выпуклой оболочки определяющего многоугольника.

Последнее свойство В-сплайна сильнее, чем у кривых Безье. У В-сплайна порядка  (степени ) точки кривой лежат внутри выпуклой оболочки  соседних точек. Таким образом, все точки на В-сплайне должны лежать внутри объединения всех выпуклых оболочек  последовательных вершин. На рис. 5-32 приводится иллюстрация для различных значений , причем выпуклые оболочки выделены серым цветом. В частности, при  выпуклая оболочка совпадает с многоугольником, т. е. В-сплайн - это сам многоугольник.

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

Если имеется  совпадающих вершин, т.е. , то выпуклая оболочка вершин от  до  - это сама вершина. Отсюда следует, что В-сплайн должен проходить через вершину . На рис. 5-34 изображен пример такой точки для . Далее, так как В-сплайн везде  непрерывен, он также  непрерывен в .

Наконец, заметим, что свойство непрерывности плавно переводит В-сплайн во вложенные отрезки прямой, как показано на рис. 5-35.

Уравнения (5-84) указывают, что выбор узлового вектора оказывает существенное влияние на базисные функции В-сплайна  и, следовательно, на сам В-сплайн. Единственное требование к узловому вектору: , т. е. это монотонно возрастающая последовательность вещественных чисел. Обычно используются три типа узловых векторов: равномерные, открытые равномерные (или открытые) и неравномерные.

Отдельные узловые значения равномерного узлового вектора распределены на одинаковом расстоянии, например

.

В частности, равномерные узловые векторы обычно начинаются в нуле и увеличиваются на 1 к некоторому максимальному значению или нормируются в диапазоне между 0 и 1 равными десятичными значениями, например,

.

Рис. 5-32 Свойства выпуклой оболочки В-сплайнов.

Рис. 5-33 Свойства выпуклой оболочки В-сплайнов для коллинеарных сегментов кривой. (а) Внутренние вершины определяющего многоугольника; (b) вершины в конце определяющего многоугольника.

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

.

То есть каждая функция базиса - это параллельный перенос другой функции, см. рис. 5-36.

У открытого равномерного узлового вектора количество одинаковых узловых значений в концах равно порядку  базисной функции В-сплайна. Внутренние узловые значения распределены равномерно.

Рис. 5-34 Выпуклая оболочка для кратных вершин, .

Рис. 5-35 Плавное  превращение в отрезки прямой.

Рис. 5-36 Базисные функции периодического равномерного В-сплайна, , , .

Несколько примеров с целыми приращениями:

              ,

               ,

или для нормализованных приращений

              ,

               ,

              .

Рис. 5-37 Базисные функции открытого равномерного В-сплайна, , , .

Формально открытый равномерный узловой вектор определяется как

  ,

        ,

  .

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

.

В результате мы имеем кубическую кривую Безье - В-сплайн. Соответствующие базисные функции изображены на рис. 5-27b. На рис. 5-37 приведен еще один пример открытых базисных функций.

Неравномерные узловые векторы отличаются тем, что их внутренние узловые величины располагаются на разном расстоянии друг от друга и/или совмещаются.

Векторы могут быть периодическими или открытыми, например

,

,

.

На рис. 5.38b-е показаны примеры неравномерных базисных функций В-сплайна порядка . У соответствующих узловых векторов на концах находится по  совмещенных одинаковых значений. Для сравнения на рис. 5-38а приведены базисные функции для открытого равномерного вектора. Отметим, что на рис. 5-38а и b функции симметричны, а также что у неравномерных базисов симметрия нарушается: 5-38с-е. Кроме того, при совмещенных узловых значениях у одной из функций появляется излом. На рис. 5-38d и е видно, что положение излома зависит от расположения совмещенного значения в узловом векторе.

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

.

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

.

Рассмотрим пример расчета базисных функций.

Пример 5-9 показывает, как построить базис  по функциям базиса более низкого порядка. На рис. 5-39а изображены функции первого порядка из примера 5-9, на рис. 5-39b - второго порядка, и на рис. 5-39с - третьего порядка. Обратим внимание на то, как растягивается диапазон ненулевых значений функций с увеличением их порядка. Говорят, что функция базиса обеспечивает поддержку на интервале от  до .

Внимательно рассматривая рис. 5-36, можно заметить важное свойство функций равномерного базиса. Из уравнения (5-85) известно, что  для любого значения параметра . Отсюда следует, что все множество периодических базисных функций для  определено только в диапазоне . За его границами . Для равномерного начинающегося с 0 узлового вектора с целыми приращениями пригодный диапазон параметра: . Для более общих или нормализованных векторов сокращение диапазона параметра соответствует потере  интервала узловых значений на каждом конце вектора.

Рис. 5-39 Построение периодических базисных функций . (а) ; (b) ; (c).

Сравнивая результаты примера 5-10 (рис. 5-40) и 5-9 (рис. 5-39), мы видим, что они существенно различаются для периодического и открытого равномерного узловых векторов. В частности, отметим, что у открытых равномерных узловых векторов на всем диапазоне изменения параметра определен полный набор базисных функций; т.е.  для всех . У периодического вектора диапазон параметра уменьшается.

Рис. 5-40 Построение открытых базисных функций . (а) ; (b) ; (с) .

Рис. 5-41 Зависимость формы В-сплайна от его порядка.

Из вышесказанного видно, какое влияние оказывает выбор узлового вектора на вид базисных функций В-сплайна и, следовательно, на форму В-сплайна.

Гибкость базиса В-сплайна позволяет воздействовать на форму кривой разными способами:

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

Меняя порядок  базисных функций.

Меняя количество и расположение вершин определяющего многоугольника.

Используя повторяющиеся вершины.

Используя повторяющиеся узловые значения в узловых векторах.

Рассмотрим эти способы сначала для открытых В-сплайнов, затем для равномерных периодических и неравномерных В-сплайнов.

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

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

Рис. 5-42 Влияние кратности вершины на форму В-сплайна, .

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

На рис. 5-42 изображается влияние повторяющихся или совпадающих вершин. Все В-сплайны имеют порядок . Нижняя кривая определена четырьмя вершинами с узловым вектором . У средней кривой пять определяющих вершин, причем две из них повторяются во второй вершине многоугольника . Узловой вектор - . Верхняя кривая определена шестью вершинами с тремя повторяющимися в точке . Узловой вектор - . Соответствующие многоугольники для трех кривых соответственно таковы: ;  и .

Нижняя кривая состоит из единственного кубического сегмента. Средняя кривая состоит из двух сегментов, соединенных между  и . Верхняя кривая состоит из трех сегментов: первый от  до , второй от  до середины между  и , третий от этой точки до . Обратим внимание на то, что с увеличением кратности вершины  кривая все ближе подходит к . Когда кратность достигается , возникает острый угол в соответствии со свойством выпуклой оболочки В-сплайнов. При внимательном изучении рис. 5-42 можно заметить, что на обеих сторонах кратной вершины имеется линейный участок.

Несмотря на наличие углов, сохраняется  дифференцируемость кривой. На первый взгляд это может показаться противоречием, однако излом определяется нулевым касательным вектором, что не исключает непрерывности его изменения. Возможность включения острых углов и изломов в непрерывно  дифференцируемые кривые это важное свойство В-сплайнов.

Наконец, заметим, что у всех кривых наклон в концах одинаков.

На рис. 5-43 показаны три В-сплайна четвертого порядка. Каждый определяющий многоугольник состоит из восьми вершин. Кривые отличаются тем, что точка  передвигается в  и . Передвижение точки воздействует на кривую только локально: изменяются лишь сегменты, отвечающие отрезкам ,  и , .

Рис. 5-43 Локальная коррекция В-сплайна.

В общем случае затрагиваются только  отрезков вокруг сдвинутой точки.

Для иллюстрации рассмотрим пример.

Рис. 5-44 Зависимость формы периодического В-сплайна от его порядка.

Теперь займемся периодическими В-сплайнами. На рис. 5-44 показаны три периодических В-сплайна разного порядка. Все кривые определены теми же вершинами, что и для открытых В-сплайнов на рис. 5-41. Для  В-сплайн опять совпадает с определяющим многоугольником. Отметим, однако, что у периодического сплайна при  первая и последняя точки на кривой не совпадают с первой и последней точками многоугольника. Наклон в первой и последней точках также может отличаться от наклона соответствующих сторон многоугольника. Для  В-сплайн начинается в середине первого ребра и оканчивается в середине последнего, как отмечено стрелками. Это происходит из-за сокращения диапазона параметра для базисных функций периодического В-сплайна. Для  периодический узловой вектор -  с диапазоном параметра . Для  периодический узловой вектор -  с диапазоном параметра . Для  периодический узловой вектор -  с диапазоном параметра .

Сравнение полученных результатов и результатов для открытых узловых векторов на рис. 5-41 показывает, что кривую можно определить на полном диапазоне параметра, задавая кратные узловые значения на концах векторов. При этом кривая растягивается к концам многоугольника.

В данном случае кривая четвертого порядка опять состоит из единственного кубического сегмента; кривая третьего порядка - из двух параболических сегментов, соединенных в середине второго ребра с непрерывностью ; кривая второго порядка - из трех линейных сегментов, соединенных во второй и третьей вершинах с  непрерывностью. Увеличение порядка опять сглаживает кривую, но в то же время и укорачивает ее.

Рис. 5-45 показывает, что воздействие кратных вершин одинаково для периодических и открытых В-сплайнов. Область вокруг точки изображена более подробно.

Рис. 5-45 Влияние кратности вершины на форму периодического В-сплайна, .

Периодические В-сплайны очень удобны для построения замкнутых кривых. На рис. 5-46а изображен периодический В-сплайн четвертого порядка , построенный для замкнутого многоугольника .

Первая вершина совпадает с последней. В-сплайн получается незамкнутым из-за ограниченного диапазона параметра. Здесь периодический равномерный узловой вектор:  с диапазоном параметра .

Повторяя всего  вершин в начале и/или конце замкнутого многоугольника, получаем замкнутый периодический В-сплайн. (Далее в этом разделе обсуждается другой метод в матричной формулировке.) Результат показан на рис. 5-46b, где определяющий многоугольник -  с периодическим равномерным узловым вектором  и диапазоном параметра . Альтернативные многоугольники  или  приводят к тому же самому результату.

На рис. 5-47 одна вершина многоугольника  передвинута на другое место. Ее воздействие распространяется на сегменты кривой, соответствующие  ребрам многоугольника по обе стороны от сдвинутой точки. На рис. 5-48 показан эффект кратной вершины . Область вокруг  изображена более подробно. Опять отметим, что ее влияние распространяется также только на  сегмента кривой по обе стороны кратной вершины.

Теперь рассмотрим неравномерные В-сплайны. На рис. 5-49 кривая изменяется под воздействием кратных внутренних узловых значений.

Рис. 5-46 Замкнутый периодический В-сплайн. (а)  определяющий многоугольник; (b)  - определяющий многоугольник.

Рис. 5-47 Изменение формы В-сплайна после перемещения одной вершины многоугольника.

Верхняя кривая третьего порядка  рассчитана для открытого узлового вектора . Базисные функции для этой кривой изображены на рис. 5-38а. Нижняя кривая третьего порядка построена с неравномерным узловым вектором . Ее базисные функции - на рис. 5-38d.

Рис. 5-48 Влияние кратных вершин на форму замкнутого периодического В-сплайна.

Такая же кривая получается с неравномерным узловым вектором  и базисными функциями на рис. 5-38е.

Из рис. 5-49 видно, что кратные внутренние узловые значения порождают излом в вершине . Кратное значение порождает ребро нулевой длины, поэтому уменьшается диапазон поддержки базисных функций. Далее, кратные внутренние узловые значения, в отличие от кратных вершин многоугольника, снижают дифференцируемость базисной функции в  до , где  равно кратности внутреннего узлового значения. Локально неравномерная кривая на рис. 5-49   непрерывная в окрестности , что и приводит к появлению угла.

Открытые неравномерные В-сплайны третьего порядка  на рис. 5-50 построены с помощью узлового вектора с внутренними значениями, пропорциональными длинам ребер между вершинами многоугольника. Узловой вектор имеет вид

  ,

,           ,

, ,                     (5-86)

где . Для вершин, находящихся на одинаковом расстоянии друг от друга, узловой вектор имеет целые равномерно распределенные значения, т.е. вектор является открытым и равномерным. В работе [5-25] предложен похожий метод, позволяющий получить отдельные внутренние узловые значения.

Рис. 5-49 Неравномерные В-сплайны, . (а) ; (b) .

Рис. 5-50 Сравнение открытых неравномерных В-сплайнов: (a) равномерный узловой вектор; (b) неравномерный узловой вектор, пропорциональный длинам хорд; (c) неравномерный узловой вектор, пропорциональный длинам хорд, с двойной вершиной в .

Для сравнения приведена кривая с открытым равномерным вектором, а также кривая с парой совпадающих вершин .

Отсюда следует, что неравномерные В-сплайны не сильно отличаются от равномерных при небольшом изменении относительного расстояния между вершинами. Рассмотрим пример.

Уравнения В-сплайна можно записать в матричной форме, подобно кубическим сплайнам, параболической интерполяции и кривым Безье (см. уравнения (5-27б), (5-44) и (5-67). У периодических В-сплайнов матричная форма особенно проста.

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

, , ,                (5-87)

где  - счетчик сегментов кривой, а  на единицу меньше количества вершин. Заметим, что уравнение (5-87) содержит только  членов:

.

Для  базисные функции на интервале параметра

,

,

.

Тогда уравнение (5-87) принимает вид

.

Перепишем в матричной форме:

.                    (5-88)

Аналогично, для  базисные функции на интервале параметра  таковы:

,

,

,

.

Матричная форма для  имеет вид

.    (5-89)

Уравнения (5-87) и (5-89) содержат произведение весовой функции и геометрической матрицы (см. уравнения (5-27), (5-44), (5-67); т.е.

     ,         ,                   (5-90)

где

 содержит геометрию - вершины многоугольника, a  состоит из соответствующих базисных функций.

В работе [5-19] показано, что для периодических В-сплайнов общий вид :

,                (5-91)

где

,                 , .

Вспомним, что у периодических замкнутых В-сплайнов необходимо повторить некоторые вершины, чтобы ликвидировать разрыв. В матричном виде это очень просто. Замкнутый периодический сплайн имеет вид

, .                   (5-92)

Или в матричном виде

,                  (5-93)

где  и  взяты из уравнения (5-90), a  - остаток; например, .

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

,                        (5-94)

где

,

а элементы  и  получены по алгоритму Кокса-де Бура (уравнение (5-84)) для каждого ненулевого интервала вектора . У В-сплайнов низкого порядка, заданных большим количеством точек, большинство членов  равны нулю. Используя это свойство, можно значительно сэкономить вычисления.

В работе [5-19] приведена обобщенная формулировка для  на нормализованном интервале ; однако из-за кратности концевых узловых значений первые и последние   матриц являются частными случаями. Рассмотрим пример матричного метода.

Производная в любой точке В-сплайна вычисляется формальным дифференцированием. Из уравнения (5-83)

              (5-83)

первая производная:

             (5-95)

и вторая производная:

.                       (5-96)

Штрихи обозначают дифференцирование по параметру .

Производные базисных функций также получают формальным дифференцированием. После однократного дифференцирования уравнения (5-84) имеем

.                    (5-97)

Из уравнения (5-84а) следует, что  для всех . Следовательно, для  уравнение (5-97) принимает вид

.               (5-98)

Вторые производные базисных функций получаем, дифференцируя уравнение (5-97),

.                     (5-99)

Здесь как , так и  равны нулю для всех . Следовательно, для  уравнение (5-97) имеет вид

.                    (5-100)

На рис. 5-51 изображены несколько базисных функций В-сплайна и их производные для . Отметим, что при  каждая базисная функция - кусочно кубическая, первая производная - кусочно параболическая, вторая производная - кусочно линейная. Третья производная разрывна и состоит из различных констант.

Рассмотрим пример.