B-сплайн

Сплайн-функция

Сплайновая кривая, нарисованная как взвешенная сумма B-сплайнов с контрольными точками/контрольным полигоном и отмеченными компонентными кривыми

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

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

Введение

По словам Джеральда Фарина, B-сплайны были исследованы еще в девятнадцатом веке Николаем Лобачевским в Казанском университете в России. ^[1] Термин «B-сплайн» был придуман Исааком Якобом Шёнбергом ^[2] в 1978 году и является сокращением от базисный сплайн. ^{[3] Сплайн-} функция порядка является кусочно- полиномиальной функцией степени . Места, где части встречаются, известны как узлы. Ключевое свойство сплайн-функций заключается в том, что они и их производные могут быть непрерывными, в зависимости от кратности узлов. ${\displaystyle n}$ ${\displaystyle n-1}$

B-сплайны порядка являются базисными функциями для сплайн-функций того же порядка, определенных над теми же узлами, что означает, что все возможные сплайн-функции могут быть построены из линейной комбинации B-сплайнов, и существует только одна уникальная комбинация для каждой сплайн-функции. ^[4] ${\displaystyle n}$

Определение

Кардинальный квадратичный B-сплайн с узловым вектором (0, 0, 0, 1, 2, 3, 3, 3) и контрольными точками (0, 0, 1, 0, 0), а также его первая производная

Кардинальный кубический B-сплайн с узловым вектором (−2, −2, −2, −2, −1, 0, 1, 2, 2, 2, 2) и контрольными точками (0, 0, 0, 6, 0, 0, 0), а также его первая производная

Кардинальный квартикальный B-сплайн с вектором узла (0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 5, 5, 5, 5) и контрольными точками (0, 0, 0, 0, 1, 0, 0, 0, 0), а также его первые и вторые производные

B-сплайн порядка представляет собой набор кусочно -полиномиальных функций степени от переменной . Значения, где встречаются части полинома, называются узлами, обозначаются и сортируются в неубывающем порядке. ${\displaystyle p+1}$ ${\displaystyle B_{i,p}(t)}$ ${\displaystyle p}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t_{0},t_{1},t_{2},\ldots ,t_{m}}$

Для заданной последовательности узлов существует, с точностью до масштабного коэффициента, уникальный сплайн, удовлетворяющий условию ${\displaystyle B_{i,p}(t)}$

${\displaystyle B_{i,p}(t)={\begin{cases}{\text{non-zero}}&{\text{if }}t_{i}\leq t<t_{i+p+1},\\0&{\text{otherwise}}.\end{cases}}}$

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

${\displaystyle \sum _{i=0}^{m-p-1}B_{i,p}(t)=1}$

для всех между узлами и , то масштабный коэффициент становится фиксированным. Узлы между (и не включая) и называются внутренними узлами. ${\displaystyle t}$ ${\displaystyle t_{p}}$ ${\displaystyle t_{m-p}}$ ${\displaystyle B_{i,p}(t)}$ ${\displaystyle t_{p}}$ ${\displaystyle t_{m-p}}$

B-сплайны могут быть построены с помощью рекурсивной формулы Кокса–де Бура. Начнем с B-сплайнов степени , т.е. кусочно-постоянных полиномов. ${\displaystyle p=0}$

${\displaystyle B_{i,0}(t):={\begin{cases}1&{\text{if }}t_{i}\leq t<t_{i+1},\\0&{\text{otherwise}}.\end{cases}}}$

B-сплайны более высокой степени определяются рекурсией ${\displaystyle (p+1)}$

${\displaystyle B_{i,p}(t):={\dfrac {t-t_{i}}{t_{i+p}-t_{i}}}B_{i,p-1}(t)+{\dfrac {t_{i+p+1}-t}{t_{i+p+1}-t_{i+1}}}B_{i+1,p-1}(t).}$

Характеристики

Функция B-сплайна представляет собой комбинацию гибких полос, которая контролируется несколькими точками, называемыми контрольными точками, создавая плавные кривые. Эти функции используются для создания и управления сложными формами и поверхностями с использованием нескольких точек. Функция B-сплайна и функции Безье широко применяются в методах оптимизации формы. ^[5]

B-сплайн порядка — это кусочно-полиномиальная функция степени переменной . Она определяется по позициям , называемым узлами или точками разрыва, которые должны быть в неубывающем порядке . B-сплайн вносит вклад только в диапазоне между первым и последним из этих узлов и равен нулю в остальных местах. Если каждый узел отделен от своего предшественника одинаковым расстоянием (где ), вектор узла и соответствующие B-сплайны называются «равномерными» (см. кардинальный B-сплайн ниже). ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle x}$ ${\displaystyle 1+n}$ ${\displaystyle t_{j}}$ ${\displaystyle t_{j}\leq t_{j+1}}$ ${\displaystyle h}$ ${\displaystyle h=t_{j+1}-t_{j}}$

Для каждого конечного интервала узлов, где он не равен нулю, B-сплайн является полиномом степени . B-сплайн является непрерывной функцией в узлах. ^{[примечание 1]} Когда все узлы, принадлежащие B-сплайну, различны, его производные также непрерывны вплоть до производной степени . Если узлы совпадают при заданном значении , непрерывность порядка производной уменьшается на 1 для каждого дополнительного совпадающего узла. B-сплайны могут совместно использовать подмножество своих узлов, но два B-сплайна, определенные над точно такими же узлами, идентичны. Другими словами, B-сплайн однозначно определяется своими узлами. ${\displaystyle n-1}$ ${\displaystyle n-2}$ ${\displaystyle x}$

Различают внутренние узлы и конечные точки. Внутренние узлы охватывают интересующую нас область. Поскольку один B-сплайн уже простирается над узлами, следует, что внутренние узлы должны быть расширены конечными точками с каждой стороны, чтобы обеспечить полную поддержку первому и последнему B-сплайну, которые влияют на интервалы внутренних узлов. Значения конечных точек не имеют значения, обычно первый или последний внутренний узел просто повторяется. ${\displaystyle x}$ ${\displaystyle 1+n}$ ${\displaystyle n-1}$

Полезность B-сплайнов заключается в том, что любая сплайновая функция порядка на заданном наборе узлов может быть выражена как линейная комбинация B-сплайнов: ${\displaystyle n}$

${\displaystyle S_{n,\mathbf {t} }(x)=\sum _{i}\alpha _{i}B_{i,n}(x).}$

B-сплайны играют роль базисных функций для пространства сплайновых функций, отсюда и название. Это свойство следует из того факта, что все части имеют одинаковые свойства непрерывности в пределах их индивидуального диапазона поддержки в узлах. ^[6]

Выражения для полиномиальных частей можно вывести с помощью рекурсивной формулы Кокса–де Бура ^[7]

${\displaystyle B_{i,0}(x):={\begin{cases}1&{\text{if }}t_{i}\leq x<t_{i+1},\\0&{\text{otherwise}}.\end{cases}}}$

${\displaystyle B_{i,k}(x):={\frac {x-t_{i}}{t_{i+k}-t_{i}}}B_{i,k-1}(x)+{\frac {t_{i+k+1}-x}{t_{i+k+1}-t_{i+1}}}B_{i+1,k-1}(x).}$

То есть, является кусочно-постоянной единицей или нулем, указывающей, в каком узле x находится промежуток (нуль, если промежуток j повторяется). Уравнение рекурсии состоит из двух частей: ${\displaystyle B_{j,0}(x)}$

${\displaystyle {\frac {x-t_{i}}{t_{i+k}-t_{i}}}}$

изменяется от нуля до единицы, когда x изменяется от до , и ${\displaystyle t_{i}}$ ${\displaystyle t_{i+k}}$

${\displaystyle {\frac {t_{i+k+1}-x}{t_{i+k+1}-t_{i+1}}}}$

изменяется от единицы до нуля, когда x изменяется от до . Соответствующие B s равны нулю вне соответствующих диапазонов. Например, — треугольная функция , равная нулю ниже , изменяется до единицы при и снова до нуля при и далее . Однако, поскольку базисные функции B-сплайна имеют локальную поддержку , B-сплайны обычно вычисляются алгоритмами, которым не нужно оценивать базисные функции там, где они равны нулю, например, алгоритмом де Бура . ${\displaystyle t_{i+1}}$ ${\displaystyle t_{i+k+1}}$ ${\displaystyle B_{i,1}(x)}$ ${\displaystyle x=t_{i}}$ ${\displaystyle x=t_{i+1}}$ ${\displaystyle x=t_{i+2}}$

Это соотношение приводит непосредственно к алгоритму BSPLV, закодированному на FORTRAN , который генерирует значения B-сплайнов порядка n в точке x . ^[8] Следующая схема иллюстрирует, как каждый фрагмент порядка n является линейной комбинацией фрагментов B-сплайнов порядка n  − 1 слева от него.

${\displaystyle {\begin{matrix}&&0\\&0&\\0&&B_{i-2,2}\\&B_{i-1,1}&\\B_{i,0}&&B_{i-1,2}\\&B_{i,1}&\\0&&B_{i,2}\\&0&\\&&0\end{matrix}}}$

Применение формулы рекурсии с узлами в дает части однородного B-сплайна порядка 3 ${\displaystyle (0,1,2,3)}$

${\displaystyle {\begin{aligned}B_{1}&=x^{2}/2,&0&\leq x<1,\\B_{2}&=(-2x^{2}+6x-3)/2,&1&\leq x<2,\\B_{3}&=(3-x)^{2}/2,&2&\leq x<3.\end{aligned}}}$

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

${\displaystyle {\begin{aligned}&{\text{At }}x=1\colon \ B_{1}=B_{2}=0.5,\ {\frac {dB_{1}}{dx}}={\frac {dB_{2}}{dx}}=1.\\[6pt]&{\text{At }}x=2\colon \ B_{2}=B_{3}=0.5,\ {\frac {dB_{2}}{dx}}={\frac {dB_{3}}{dx}}=-1.\end{aligned}}}$

Вторая производная B-сплайна степени 2 разрывна в узлах:

${\displaystyle {\frac {d^{2}B_{1}}{dx^{2}}}=1,\ {\frac {d^{2}B_{2}}{dx^{2}}}=-2,\ {\frac {d^{2}B_{3}}{dx^{2}}}=1.}$

Были предложены более быстрые варианты алгоритма де Бура, но они страдают от сравнительно меньшей стабильности. ^{[9] [10]}

Кардинальный B-сплайн

Кардинальный B-сплайн имеет постоянное разделение h между узлами. Кардинальные B-сплайны для заданного порядка n являются просто сдвинутыми копиями друг друга. Их можно получить из более простого определения. ^[11]

${\displaystyle B_{i,n,t}(x)={\frac {x-t_{i}}{h}}n[0,\dots ,n](\cdot -t_{i})_{+}^{n-1}.}$

Обозначение «заполнитель» используется для указания того, что n -ная разделенная разность функции двух переменных t и x должна быть взята путем фиксации x и рассмотрения как функции только t . ${\displaystyle (t-x)_{+}^{n-1}}$ ${\displaystyle (t-x)_{+}^{n-1}}$

Кардинальный B-сплайн имеет равномерно расположенные узлы, поэтому интерполяция между узлами эквивалентна свертке со сглаживающим ядром.

Например, если мы хотим интерполировать три значения между узлами B-сплайна ( ), мы можем записать сигнал как ${\displaystyle {\textbf {b}}}$

${\displaystyle \mathbf {x} =[\mathbf {b} _{1},0,0,\mathbf {b} _{2},0,0,\mathbf {b} _{3},0,0,\dots ,\mathbf {b} _{n},0,0].}$

Свертка сигнала с функцией прямоугольника дает интерполированные значения B-сплайна первого порядка. Интерполяция B-сплайна второго порядка представляет собой свертку с функцией прямоугольника дважды ; путем итеративной фильтрации с функцией прямоугольника получается интерполяция более высокого порядка. ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {h} =[1/3,1/3,1/3]}$ ${\displaystyle \mathbf {y} =\mathbf {x} *\mathbf {h} *\mathbf {h} }$

Быстрая интерполяция B-сплайна на однородной выборочной области может быть выполнена с помощью итеративной фильтрации среднего. В качестве альтернативы, функция прямоугольника равна sinc в области Фурье . Таким образом, интерполяция кубическим сплайном равна умножению сигнала в области Фурье на sinc ⁴ .

См. распределение Ирвина–Холла#Особые случаи для алгебраических выражений для кардинальных B-сплайнов степени 1–4.

P-сплайн

Термин P-сплайн означает «штрафной B-сплайн». Он относится к использованию представления B-сплайна, где коэффициенты определяются частично данными, которые должны быть подобраны , и частично дополнительной штрафной функцией , которая направлена ​​на обеспечение гладкости , чтобы избежать переобучения . ^[12]

Двумерные и многомерные P-сплайновые аппроксимации данных могут использовать произведение матриц для минимизации вычислительных операций. ^[13]

Производные выражения

Производная B-сплайна степени k — это просто функция B-сплайнов степени k  − 1: ^[14]

${\displaystyle {\frac {dB_{i,k}(x)}{dx}}=k\left({\frac {B_{i,k-1}(x)}{t_{i+k}-t_{i}}}-{\frac {B_{i+1,k-1}(x)}{t_{i+k+1}-t_{i+1}}}\right).}$

Это подразумевает, что

${\displaystyle {\frac {d}{dx}}\sum _{i}\alpha _{i}B_{i,k}=\sum _{i=r-k+2}^{s-1}k{\frac {\alpha _{i}-\alpha _{i-1}}{t_{i+k}-t_{i}}}B_{i,k-1}\quad {\text{on}}\quad [t_{r},t_{s}],}$

что показывает, что существует простая связь между производной сплайн-функции и B-сплайнами степени на единицу меньше.

Моменты одномерных B-сплайнов

Одномерные B-сплайны, т.е. B-сплайны, где положения узлов лежат в одном измерении, могут использоваться для представления 1-мерных функций плотности вероятности . Примером является взвешенная сумма базисных функций B-сплайнов порядка , каждая из которых нормализована по площади до единицы (т.е. не оценивается напрямую с использованием стандартного алгоритма де-Бура) ${\displaystyle p(x)}$ ${\displaystyle i}$ ${\displaystyle n}$

${\displaystyle p(x)=\sum _{i}c_{i}\cdot B_{i,n,{\textbf {norm}}}(x)}$

и с нормализацией константы ограничения . K -й сырой момент нормализованного B-сплайна может быть записан как среднее Дирихле Карлсона ^[15], которое в свою очередь может быть решено точно с помощью контурного интеграла и итеративной суммы ^[16] как ${\displaystyle \sum _{i}c_{i}=1}$ ${\displaystyle \mu _{k}}$ ${\displaystyle B_{i,n,{\textbf {norm}}}}$ ${\displaystyle R_{k}}$

${\displaystyle \mu _{k}=R_{k}(\mathbf {m} ;\mathbf {t} )=\int _{-\infty }^{\infty }x^{k}\cdot B_{i,n,{\textbf {norm}}}(x\mid t_{1}\dots t_{j})\,dx={\frac {\Gamma (k+1)\Gamma (m)}{\Gamma (m+k)}}\cdot D_{k}(\mathbf {m} ,\mathbf {t} )}$

с

${\displaystyle D_{k}={\frac {1}{k}}\sum \limits _{u=1}^{k}\left[\left(\sum \limits _{i=1}^{j}m_{i}\cdot {t_{i}}^{u}\right)D_{k-u}\right]}$

и . Здесь представляет собой вектор с позициями узлов и вектор с соответствующими кратностями узлов. Таким образом, можно точно вычислить любой момент функции плотности вероятности, представленной суммой базисных функций B-сплайна, не прибегая к численным методам. ${\displaystyle D_{0}=1}$ ${\displaystyle \mathbf {t} }$ ${\displaystyle j}$ ${\displaystyle \mathbf {m} }$ ${\displaystyle p(x)}$

Отношение к кусочно-составной кривой Безье

Кривая Безье также является полиномиальной кривой, определяемой с помощью рекурсии из кривых более низкой степени того же класса и закодированной в терминах контрольных точек, но ключевым отличием является то, что все члены в рекурсии для сегмента кривой Безье имеют одну и ту же область определения (обычно ), тогда как опоры двух членов в рекурсии B-сплайна различны (самые внешние подынтервалы не являются общими). ​​Это означает, что кривая Безье степени, заданной контрольными точками, состоит из в основном независимых сегментов, тогда как B-сплайн с теми же параметрами плавно переходит от подынтервала к подынтервалу. Чтобы получить что-то сопоставимое с кривой Безье, нужно было бы наложить условие гладкости на переходы между сегментами, что привело бы к некоторому виду сплайна Безье (для которого многие контрольные точки были бы определены требованием гладкости). ${\displaystyle [0,1]}$ ${\displaystyle n}$ ${\displaystyle m\gg n}$ ${\displaystyle m/n}$

Кусочно /составная кривая Безье представляет собой ряд кривых Безье, соединенных с непрерывностью не менее C0 (последняя точка одной кривой совпадает с начальной точкой следующей кривой). В зависимости от приложения могут быть добавлены дополнительные требования к гладкости (такие как непрерывность C1 или C2). ^[17] Непрерывные кривые C1 имеют идентичные касательные в точке разрыва (где встречаются две кривые). Непрерывные кривые C2 имеют одинаковую кривизну в точке разрыва. ^[18]

Подгонка кривой

Обычно при подгонке кривой набор точек данных подгоняется под кривую, заданную некоторой математической функцией. Например, общие типы подгонки кривой используют полином или набор экспоненциальных функций . Когда нет теоретической основы для выбора подгоночной функции, кривая может быть подогнана под сплайн-функцию, составленную из суммы B-сплайнов, с использованием метода наименьших квадратов . ^{[19] [примечание 2]} Таким образом, целевая функция для минимизации наименьших квадратов для сплайн-функции степени k равна :

${\displaystyle U=\sum _{{\text{all}}~x}\left\{W(x)\left[y(x)-\sum _{i}\alpha _{i}B_{i,k,t}(x)\right]\right\}^{2},}$

где W ( x ) — вес, а y ( x ) — начальное значение в точке x . Коэффициенты — это параметры, которые необходимо определить. Значения узлов могут быть фиксированными или рассматриваться как параметры. ${\displaystyle \alpha _{i}}$

Основная сложность в применении этого процесса заключается в определении количества используемых узлов и места их размещения. Де Бур предлагает различные стратегии для решения этой проблемы. Например, расстояние между узлами уменьшается пропорционально кривизне (второй производной) данных. ^{[ требуется ссылка ]} Было опубликовано несколько приложений. Например, было исследовано использование B-сплайнов для подгонки отдельных кривых Лоренца и Гаусса . Были вычислены оптимальные сплайн-функции степеней 3–7 включительно, основанные на симметричном расположении 5, 6 и 7 узлов, и метод был применен для сглаживания и дифференциации спектроскопических кривых. ^[20] В сопоставимом исследовании двумерная версия фильтрации Савицкого–Голея и метод сплайнов дали лучшие результаты, чем скользящее среднее или фильтрация Чебышева . ^[21]

Компьютерное проектирование и компьютерная графика

В приложениях автоматизированного проектирования и компьютерной графики сплайновая кривая иногда представляется как , параметрическая кривая некоторого действительного параметра . В этом случае кривая может рассматриваться как две или три отдельные функции координат , или . Функции координат , и являются каждая сплайновой функцией с общим набором значений узлов . ${\displaystyle C(t)}$ ${\displaystyle t}$ ${\displaystyle C(t)}$ ${\displaystyle (x(t),y(t))}$ ${\displaystyle (x(t),y(t),z(t))}$ ${\displaystyle x(t)}$ ${\displaystyle y(t)}$ ${\displaystyle z(t)}$ ${\displaystyle t_{1},t_{2},\ldots ,t_{n}}$

Поскольку B-сплайны образуют базисные функции, каждая из координатных функций может быть выражена как линейная сумма B-сплайнов, поэтому мы имеем

${\displaystyle {\begin{aligned}X(t)&=\sum _{i}x_{i}B_{i,n}(t),\\Y(t)&=\sum _{i}y_{i}B_{i,n}(t),\\Z(t)&=\sum _{i}z_{i}B_{i,n}(t).\end{aligned}}}$

Веса , и могут быть объединены для формирования точек в трехмерном пространстве. Эти точки обычно известны как контрольные точки. ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$ ${\displaystyle z_{i}}$ ${\displaystyle P_{i}=(x_{i},y_{i},z_{i})}$ ${\displaystyle P_{i}}$

Работая в обратном направлении, последовательность контрольных точек, значений узлов и порядок B-сплайна определяют параметрическую кривую. Это представление кривой контрольными точками имеет несколько полезных свойств:

1. Контрольные точки определяют кривую. Если все контрольные точки преобразуются вместе каким-либо образом, например, переносятся, вращаются, масштабируются или перемещаются любым аффинным преобразованием, то соответствующая кривая преобразуется таким же образом. ${\displaystyle P_{i}}$
2. Поскольку B-сплайны не равны нулю только для конечного числа интервалов узлов, при перемещении одной контрольной точки соответствующее изменение параметрической кривой будет находиться чуть выше диапазона параметров небольшого числа интервалов узлов.
3. Поскольку , и в любое время каждый , то кривая остается внутри ограничивающего прямоугольника контрольных точек. Также, в некотором смысле, кривая в целом следует контрольным точкам. ${\displaystyle \sum _{i}B_{i,n}(x)=1}$ ${\displaystyle B_{i,n}(x)\geq 0}$

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

Кубические B-сплайны

Кубическая B-сплайновая кривая с нормализованным параметром определяется четырьмя узлами (т.е. контрольными точками ) , , , и . Она образует полином степени 3, который можно записать как ${\displaystyle \mathbf {C} (t)}$ ${\displaystyle t\in [0,1]}$ ${\displaystyle {\textbf {b}}_{0}}$ ${\displaystyle {\textbf {b}}_{1}}$ ${\displaystyle {\textbf {b}}_{2}}$ ${\displaystyle {\textbf {b}}_{3}}$

${\displaystyle \mathbf {C} (t)={\frac {1}{6}}\;{\begin{bmatrix}t^{3}&t^{2}&t&1\end{bmatrix}}{\begin{bmatrix}-1&3&-3&1\\3&-6&3&0\\-3&0&3&0\\1&4&1&0\end{bmatrix}}{\begin{bmatrix}\mathbf {b} _{0}\\\mathbf {b} _{1}\\\mathbf {b} _{2}\\\mathbf {b} _{3}\end{bmatrix}}}$.

Это соответствует полиномам B-сплайна.

${\displaystyle {\begin{aligned}B_{0}(t)&={\frac {1}{6}}(-t^{3}+3t^{2}-3t+1)\\B_{1}(t)&={\frac {1}{6}}(3t^{3}-6t^{2}+4)\\B_{2}(t)&={\frac {1}{6}}(-3t^{3}+3t^{2}+3t+1)\\B_{3}(t)&={\frac {1}{6}}t^{3}\end{aligned}}}$

и кривая может быть оценена как . Расширяя это, мы можем записать полную полиномиальную форму, как показано ниже ${\displaystyle \mathbf {C} (t)=\sum _{i=0}^{3}B_{i}(t)\,\mathbf {b} _{i}}$

${\displaystyle \mathbf {C} (t)={\frac {1}{6}}{\biggl (}(-\mathbf {b} _{0}+3\mathbf {b} _{1}-3\mathbf {b} _{2}+\mathbf {b} _{3})t^{3}+(3\mathbf {b} _{0}-6\mathbf {b} _{1}+3\mathbf {b} _{2})t^{2}+(-3\mathbf {b} _{0}+3\mathbf {b} _{2})t+(\mathbf {b} _{0}+4\mathbf {b} _{1}+\mathbf {b} _{2}){\biggr )}}$.

Поскольку это кубический многочлен, мы также можем записать его как кубическую кривую Безье с контрольными точками , , , и , такими, что ${\displaystyle {\textbf {P}}_{0}}$ ${\displaystyle {\textbf {P}}_{1}}$ ${\displaystyle {\textbf {P}}_{2}}$ ${\displaystyle {\textbf {P}}_{3}}$

${\displaystyle {\begin{aligned}\mathbf {P} _{0}&={\frac {1}{6}}(\mathbf {b} _{0}+4\mathbf {b} _{1}+\mathbf {b} _{2}),\\\mathbf {P} _{1}&={\frac {1}{3}}(2\mathbf {b} _{1}+\mathbf {b} _{2}),\\\mathbf {P} _{2}&={\frac {1}{3}}(\mathbf {b} _{1}+2\mathbf {b} _{2}),\\\mathbf {P} _{3}&={\frac {1}{6}}(\mathbf {b} _{1}+4\mathbf {b} _{2}+\mathbf {b} _{3}).\end{aligned}}}$

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

НУРБС

NURBS-кривая – полиномиальная кривая, заданная в однородных координатах (синяя) и ее проекция на плоскость – рациональная кривая (красная)

В автоматизированном проектировании , автоматизированном производстве и компьютерной графике мощным расширением B-сплайнов являются неоднородные рациональные B-сплайны (NURBS). NURBS по сути являются B-сплайнами в однородных координатах . Как и B-сплайны, они определяются своим порядком, вектором узла и набором контрольных точек, но в отличие от простых B-сплайнов, каждая контрольная точка имеет вес. Когда вес равен 1, NURBS является просто B-сплайном, и как таковой NURBS обобщает как B-сплайны, так и кривые и поверхности Безье , основное отличие заключается во взвешивании контрольных точек, что делает кривые NURBS «рациональными».

Оценивая NURBS при различных значениях параметров, можно проследить кривую в пространстве; аналогично, оценивая поверхность NURBS при различных значениях двух параметров, можно представить поверхность в декартовом пространстве.

Как и B-сплайны, контрольные точки NURBS определяют форму кривой. Каждая точка кривой вычисляется путем взятия взвешенной суммы ряда контрольных точек. Вес каждой точки изменяется в зависимости от управляющего параметра. Для кривой степени d влияние любой контрольной точки не равно нулю только в d +1 интервалах (узловых промежутках) пространства параметров. Внутри этих интервалов вес изменяется в соответствии с полиномиальной функцией (базисными функциями) степени d . На границах интервалов базисные функции плавно стремятся к нулю, причем гладкость определяется степенью полинома.

Вектор узла — это последовательность значений параметров, которая определяет, где и как контрольные точки влияют на кривую NURBS. Количество узлов всегда равно количеству контрольных точек плюс степень кривой плюс один. Каждый раз, когда значение параметра входит в новый диапазон узла, новая контрольная точка становится активной, а старая контрольная точка отбрасывается.

Кривая NURBS имеет следующий вид: ^[22]

${\displaystyle C(u)={\frac {\sum _{i=1}^{k}N_{i,n}(u)w_{i}P_{i}}{\sum _{i=1}^{k}N_{i,n}(u)w_{i}}}}$

Здесь обозначения следующие. u — независимая переменная (вместо x ), k — количество контрольных точек, N — B-сплайн (используется вместо B ), n — степень полинома, P — контрольная точка, а w — вес. Знаменатель — нормирующий множитель, который равен единице, если все веса равны единице.

Это принято писать как

${\displaystyle C(u)=\sum _{i=1}^{k}R_{i,n}(u)P_{i}}$

в котором функции

${\displaystyle R_{i,n}(u)={\frac {N_{i,n}(u)w_{i}}{\sum _{j=1}^{k}N_{j,n}(u)w_{j}}}}$

известны как рациональные базисные функции.

Поверхность NURBS получается как тензорное произведение двух кривых NURBS, при этом используются два независимых параметра u и v (с индексами i и j соответственно): ^[23]

${\displaystyle S(u,v)=\sum _{i=1}^{k}\sum _{j=1}^{\ell }R_{i,j}(u,v)P_{i,j}}$

с

${\displaystyle R_{i,j}(u,v)={\frac {N_{i,n}(u)N_{j,m}(v)w_{i,j}}{\sum _{p=1}^{k}\sum _{q=1}^{\ell }N_{p,n}(u)N_{q,m}(v)w_{p,q}}}}$

как рациональные базисные функции.

Смотрите также

• кривая Безье
• Шлицевой шлиц
• Алгоритм Де Бура
• I-сплайн
• М-сплайн
• Сплайн-вейвлет
• Т-образный шлиц

Примечания

1. Строго говоря, B-сплайны обычно определяются как непрерывные слева.
2. де Бур приводит процедуры на языке FORTRAN для аппроксимации экспериментальных данных методом наименьших квадратов.

Ссылки

1. Фарин, GE (2002). Кривые и поверхности для CAGD: практическое руководство . Morgan Kaufmann. стр. 119.
2. де Бур, стр. 114.
3. Гэри Д. Нотт (2000), Интерполяция кубических сплайнов . Springer. стр. 151.
4. Хартмут Праутч; Вольфганг Бём; Марко Палушны (2002). Методы Безье и B-сплайна . Математика и визуализация. Берлин, Гейдельберг: Springer Science & Business Media. п. 63. дои : 10.1007/978-3-662-04919-8. ISBN 978-3-540-43761-1. OCLC  851370272.
5. Talebitooti, ​​R.; Shojaeefard, MH; Yarmohammadisatri, Sadegh (2015). «Оптимизация конструкции формы цилиндрического резервуара с использованием b-сплайновых кривых». Computer & Fluids . 109 : 100–112. doi :10.1016/j.compfluid.2014.12.004.
6. де Бур, стр. 113.
7. де Бур, стр. 131.
8. де Бур, стр. 134.
9. Ли, ETY (декабрь 1982 г.). «Упрощенная процедура вычисления B-сплайна». Computing . 29 (4): 365–371. doi :10.1007/BF02246763. S2CID  2407104.
10. Ли, ETY (1986). «Комментарии к некоторым алгоритмам B-сплайна». Computing . 36 (3): 229–238. doi :10.1007/BF02240069. S2CID  7003455.
11. де Бур, стр. 322.
12. Эйлерс, PHC и Маркс, BD (1996). Гибкое сглаживание с B-сплайнами и штрафами (с комментариями и возражениями). Статистическая наука 11(2): 89–121.
13. Эйлерс, Пол ХК; Маркс, Брайан Д. (2003). «Многомерная калибровка с температурным взаимодействием с использованием двумерной регрессии штрафного сигнала». Хемометрика и интеллектуальные лабораторные системы . 66 (2): 159–174. doi :10.1016/S0169-7439(03)00029-7.
14. де Бур, стр. 115.
15. Карлсон, BC (1991). «B-сплайны, гипергеометрические функции и средние Дирихле». Журнал теории приближений . 67 (3): 311–325. doi : 10.1016/0021-9045(91)90006-V .
16. Glüsenkamp, ​​T. (2018). «Вероятностная обработка неопределенности из конечного размера взвешенных данных Монте-Карло». EPJ Plus . 133 (6): 218. arXiv : 1712.01293 . Bibcode : 2018EPJP..133..218G. doi : 10.1140/epjp/i2018-12042-x. S2CID  125665629.)
17. Евгений В. Шикин; Александр И. Плис (14 июля 1995 г.). Справочник по сплайнам для пользователя. CRC Press. С. 96–. ISBN 978-0-8493-9404-1.
18. Wernecke, Josie (1993). "8". The Inventor Mentor: Programming Object-Oriented 3D Graphics with Open Inventor, Release 2 (1st ed.). Бостон, Массачусетс, США: Addison-Wesley Longman Publishing Co., Inc. ISBN 978-0201624953.
19. де Бур, Глава XIV, с. 235.
20. Ганс, Питер; Гилл, Дж. Бернард (1984). «Сглаживание и дифференциация спектроскопических кривых с использованием сплайн-функций». Прикладная спектроскопия . 38 (3): 370–376. Bibcode : 1984ApSpe..38..370G. doi : 10.1366/0003702844555511. S2CID  96229316.
21. Vicsek, Maria; Neal, Sharon L.; Warner, Isiah M. (1986). «Фильтрация во временной области двумерных данных флуоресценции». Applied Spectroscopy . 40 (4): 542–548. Bibcode : 1986ApSpe..40..542V. doi : 10.1366/0003702864508773. S2CID  28705788. Архивировано из оригинала 23 июня 2017 г.
22. Пигль и Тиллер, глава 4, раздел 2.
23. Пигль и Тиллер, глава 4, раздел 4.

Цитируемые работы

• Карл де Бур (1978). Практическое руководство по сплайнам . Спрингер-Верлаг. ISBN 978-3-540-90356-7.
• Пигль, Лес; Тиллер, Уэйн (1997). Книга NURBS (2-е изд.). Springer. ISBN 978-3-540-61545-3.

Дальнейшее чтение

• Ричард Х. Бартельс; Джон К. Битти; Брайан А. Барски (1987). Введение в сплайны для использования в компьютерной графике и геометрическом моделировании . Морган Кауфманн. ISBN 978-1-55860-400-1.
• Жан Галлье (1999). Кривые и поверхности в геометрическом моделировании: теория и алгоритмы. Морган Кауфманн. Глава 6. B-сплайновые кривые.Эта книга больше не издается и доступна бесплатно у автора.
• Хартмут Праутч; Вольфганг Бём; Марко Палушны (2002). Методы Безье и B-сплайна . Springer Science & Business Media. ISBN 978-3-540-43761-1.
• Дэвид Саломон (2006). Кривые и поверхности для компьютерной графики . Springer. Глава 7. Аппроксимация B-сплайнами. ISBN 978-0-387-28452-1.
• Хови, Чад (2022). Формулировка и реализация на Python геометрии Безье и B-сплайна. SAND2022-7702C. (153 страницы)

Внешние ссылки

• Вайсштейн, Эрик В. "B-сплайн". MathWorld .
• Руф, Йоханнес. "B-сплайны третьего порядка на неравномерной сетке" (PDF) . Архивировано из оригинала (PDF) 2013-11-06 . Получено 2012-05-02 .
• двумерный B-сплайн из numpy
• Интерактивные B-сплайны с JSXGraph
• TinySpline: C-библиотека с открытым исходным кодом и привязками к различным языкам
• Равномерные нерациональные B-сплайны, Моделирование кривых в 2D пространстве. Автор: Стефан Г. Бек
• Редактор B-сплайнов от Шуканта Пала