В математическое подполе численного анализа, B-сплайн или базисный сплайн - это сплайн функция, имеющая минимальное значение поддерживают в отношении заданной степени, гладкости и раздела домена. Любая сплайн-функция заданной степени может быть выражена как линейная комбинация B-сплайнов этой степени. Кардинальные B-шлицы имеют узлы, равноудаленные друг от друга. B-сплайны могут использоваться для аппроксимации кривой и численного дифференцирования экспериментальных данных.
В автоматизированном проектировании и компьютерной графике сплайн-функции строятся как линейные комбинации B-сплайнов с набором контрольных точек.
Термин «B-сплайн» был придуман Исааком Якобом Шенбергом и является сокращением от слова «базис». сплайн. Сплайн-функция порядка - это кусочно полиномиальная функция степени в переменной . Места, где встречаются части, называются узлами. Ключевым свойством сплайн-функций является то, что они и их производные могут быть непрерывными, в зависимости от кратности узлов.
B-сплайны порядка - это базисные функции для сплайн-функций того же порядка, определенных для одних и тех же узлов, что означает, что все возможные сплайн-функции могут быть построены из линейной комбинации B-сплайнов, и существует только одна уникальная комбинация для каждой сплайн-функции.
Сплайн порядка представляет собой кусочно полином функция степени в переменной . Значения там, где встречаются части многочлена, называются узлами и обозначаются и отсортированы в порядке неубывания. Когда узлы различны, первые производные частей многочлена являются непрерывными для каждого узла. Когда узлы совпадают, тогда только первые производные сплайна являются непрерывно через этот узел.
Для данной последовательности узлов существует, с точностью до коэффициента масштабирования, уникальный сплайн удовлетворение
Если мы добавим дополнительное ограничение, которое для всех между первым и последним узлами, затем коэффициент масштабирования становится фиксированным. Результирующие сплайновые функции называются B-сплайнами.
В качестве альтернативы, B-сплайны могут быть определены путем построения с помощью формулы рекурсии Кокса – де Бора. Дана последовательность узлов , тогда B-сплайны порядка 1 определяются как
Они удовлетворяют для всех , потому что для любого ровно один из , и все другие равны нулю.
B-сплайны более высокого порядка определяются рекурсией
где
Функция B-сплайна представляет собой комбинацию гибких полос который проходит через множество точек, называемых контрольными точками, и создает плавные кривые. Эти функции позволяют создавать сложные формы и поверхности и управлять ими с помощью ряда точек. B-сплайн и функции Безье широко применяются в методах оптимизации формы.
B-сплайн порядка - это кусочно-полиномиальная функция степени в переменной . Он определяется в местоположениях , называемых узлами или точками останова, которые должны быть в порядке убывания . B-сплайн вносит вклад только в диапазоне между первым и последним из этих узлов и равен нулю в других местах. Если каждый узел разделен одинаковым расстоянием (где ) от своего предшественника, узловой вектор и соответствующие B-сплайны называются «равномерными» (см. кардинальный B-сплайн ниже).
Для каждого конечного интервала узлов, где он не равен нулю, B-сплайн представляет собой полином степени . B-сплайн - это непрерывная функция в узлах. Когда все узлы, принадлежащие B-сплайну, различны, его производные также непрерывны до производной степени . Если узлы совпадают при заданном значении , непрерывность производного порядка уменьшается на 1 для каждого дополнительного совпадающего узла. B-сплайны могут иметь общие подмножества своих узлов, но два B-сплайна, определенные над одними и теми же узлами, идентичны. Другими словами, B-сплайн однозначно определяется своими узлами.
Различают внутренние узлы и конечные точки. Внутренние узлы покрывают -домен, который интересует. Поскольку один B-сплайн уже простирается на узлов, из этого следует, что внутренние узлы необходимо удлинить с помощью конечных точек с каждой стороны, чтобы обеспечить полную поддержку первой и последний B-шлиц, влияющий на внутренние интервалы узлов. Значения конечных точек не имеют значения, обычно первый или последний внутренний узел просто повторяется.
Полезность B-сплайнов заключается в том, что любую сплайн-функцию порядка на данном наборе узлов можно выразить как линейную комбинацию B-шлицев:
B-шлицы играют роль базисные функции для пространства сплайн-функций, отсюда и название. Это свойство следует из того факта, что все части имеют одинаковые свойства непрерывности в пределах их индивидуального диапазона поддержки в узлах.
Выражения для полиномиальных частей могут быть получены с помощью рекурсивной формулы Кокса – де Бура.
То есть является кусочно-постоянным единицей или нулем, указывающим, в каком промежутке узла x находится (ноль, если узел j повторяется). Уравнение рекурсии состоит из двух частей:
изменяется от нуля до единицы при изменении x от до и
изменяется от единицы до нуля при изменении x от до . Соответствующие B равны нулю вне этих соответствующих диапазонов. Например, - это треугольная функция, которая равна нулю ниже , переход к единице при и обратно к нулю в . Однако, поскольку базисные функции B-сплайна имеют локальную поддержку , B-сплайны обычно вычисляются алгоритмами, которым не нужно оценивать базисные функции, где они равны нулю, например, алгоритм де Бура.
Это соотношение ведет непосредственно к алгоритму BSPLV, закодированному на FORTRAN, который генерирует значения B-сплайнов порядка n в точке x. На следующей схеме показано, как каждая часть порядка n представляет собой линейную комбинацию частей B-сплайнов порядка n-1 слева от нее.
Применение формулы рекурсии с узлами в дает части однородного B-сплайна порядка 3
Эти части показаны на диаграмме. Свойство непрерывности квадратичной сплайн-функции и ее первой производной во внутренних узлах проиллюстрировано следующим образом
Вторая производная B-сплайна степени 2 разрывна в узлах:
Были предложены более быстрые варианты алгоритма де Бура, но они страдают сравнительно меньшей стабильностью.
Кардинальный B-сплайн имеет постоянное разделение, h, между узлами. Кардинальные B-сплайны для данного порядка n - это просто сдвинутые копии друг друга. Их можно получить из более простого определения.
Обозначение «заполнитель» используется для обозначения того, что n-я разделенная разность функции из двух переменных t и x следует взять, зафиксировав x и учитывая как функция только от t.
Кардинальный B-сплайн имеет равномерно распределенные узлы, поэтому интерполяция между узлами равняется свертке со сглаживающим ядром.
Пример, если мы хотим интерполировать три значения между узлами B-сплайна (), мы можем записать сигнал как:
Свертка сигнала с функцией прямоугольника дает интерполированные значения b-сплайна первого порядка. B-сплайновая интерполяция второго порядка - это свертка с функцией прямоугольника дважды , путем итеративной фильтрации с помощью прямоугольной функции получается интерполяция более высокого порядка.
Быстрая интерполяция b-сплайном на однородной области выборки может быть выполнена с помощью итеративной фильтрации среднего значения. В качестве альтернативы функция прямоугольника равна Sinc в области Фурье. Следовательно, интерполяция кубическим сплайном равняется умножению сигнала в области Фурье на Sinc ^ 4.
См. Распределение Ирвина – Холла # Особые случаи для алгебраических выражений для кардинальных B-сплайнов степени 1-4.
Термин P-spline означает «B-сплайн с ограничениями». Это относится к использованию B-сплайнового представления, в котором коэффициенты определяются частично данными, которые должны быть подобраны, а частично дополнительной функцией штрафа , которая направлена на обеспечение гладкости, чтобы избежать переобучения.
Дву- и многомерные P-сплайновые аппроксимации данных могут использовать произведение граней матриц для минимизации вычислительных операций.
Производная B-сплайна степени k является просто функцией B-сплайнов степени k-1.
Отсюда следует, что
который показывает, что существует простая взаимосвязь между производной сплайновой функции и B-сплайнами степени на единицу меньше.
Одномерные B-сплайны, т. Е. B-сплайны, где положения узлов лежат в одном измерении, могут использоваться для представления одномерных функций плотности вероятности . Примером является взвешенная сумма базисных функций B-сплайна порядка , каждая из которых является областью- нормализовано к единице (т. е. не оценивается напрямую с помощью стандартного алгоритма де-Бура)
и с ограничением константы нормализации . K-й необработанный момент нормализованного B-сплайна можно записать как среднее значение Дирихле Карлсона , которое, в свою очередь, может быть решено точно с помощью контурного интеграла и итерационной суммы как
с
и . Здесь представляет вектор с положениями узлов и вектор с соответствующими кратностями узлов. Следовательно, можно точно вычислить любой момент функции плотности вероятности , представленной суммой базисных функций B-сплайна, не прибегая к численным методам.
A Кривая Безье также является полиномиальной кривой, определяемой с использованием рекурсии из кривых более низкой степени того же класса и закодированной в терминах контрольных точек, но ключевое отличие заключается в что все термины в рекурсии для сегмента кривой Безье имеют одну и ту же область определения (обычно ), тогда как поддерживает двух членов в B-сплайн-рекурсии различны (крайние подынтервалы не являются общими). Это означает, что кривая Безье степени , заданная как , контрольные точки состоят примерно из в основном независимые сегменты, тогда как B-сплайн с теми же параметрами плавно переходит от подынтервала к подинтервалу. Чтобы получить что-то сопоставимое с кривой Безье, нужно наложить условие гладкости на переходы между сегментами, что приведет к некоторому виду сплайна Безье (для которого многие контрольные точки будут определяться требованием гладкости).
A кусочно / составная кривая Безье представляет собой серию кривых Безье, соединенных по крайней мере с непрерывностью C0 (последняя точка одной кривой совпадает с начальной точкой следующей кривой). В зависимости от приложения могут быть добавлены дополнительные требования к гладкости (например, непрерывность C1 или C2). Непрерывные кривые C1 имеют идентичные касательные в точке излома (где встречаются две кривые). Непрерывные кривые C2 имеют одинаковую кривизну в точке излома.
Чтобы получить непрерывность C2, кривая Безье теряет локальный контроль, потому что для обеспечения непрерывности C2 контрольные точки зависят друг от друга. Если перемещается одна контрольная точка, необходимо повторно оценить весь сплайн. B-сплайны имеют как непрерывность C2, так и локальное управление, но они теряют свойство интерполяции кусочного Безье.
Обычно в подгонке кривой, набор точки данных соответствуют кривой, определяемой некоторой математической функцией. Например, обычные типы аппроксимации кривой используют полином или набор экспоненциальных функций. Когда нет теоретической основы для выбора функции аппроксимации, кривая может быть аппроксимирована сплайновой функцией, составленной из суммы B-сплайнов, с использованием метода наименьших квадратов. Таким образом, целевая функция минимизации методом наименьших квадратов для сплайновой функции степени k:
W (x) - это вес, а y (x) - это значение в точке x. Коэффициенты - это параметры, которые необходимо определить. Значения узлов могут быть фиксированными или их также можно рассматривать как параметры.
Основная трудность при применении этого процесса заключается в определении количества используемых узлов и их расположения. де Бур предлагает различные стратегии решения этой проблемы. Например, расстояние между узлами уменьшается пропорционально кривизне (2-я производная) данных. Было опубликовано несколько приложений. Например, было исследовано использование B-сплайнов для аппроксимации одиночных кривых лоренцевой и гауссовой кривых. Рассчитаны оптимальные сплайн-функции степеней 3-7 включительно, основанные на симметричном расположении узлов 5, 6 и 7 узлов, и метод применен для сглаживания и дифференцирования спектроскопических кривых. В сопоставимом исследовании двумерная версия фильтрации Савицкого-Голея и сплайн-метода дали лучшие результаты, чем скользящее среднее или фильтрация Чебышева.
В приложениях автоматизированного проектирования и компьютерной графики сплайн-кривая иногда представляется как , параметрическая кривая некоторого реального параметра . В этом случае кривая может рассматриваться как две или три отдельные координатные функции или . Координатные функции , и - каждая сплайн-функция с общим набором узловых значений .
Поскольку B-сплайны образуют базисные функции, каждая из координатных функций может быть выражена как линейная сумма B-сплайнов, поэтому мы имеем
Веса , и можно объединить в точки в 3-м пространстве. Эти точки обычно известны как контрольные точки.
Работая в обратном порядке, последовательность контрольных точек, значений узлов и порядка B-сплайна определяет параметрическую кривую. Это представление кривой с помощью контрольных точек имеет несколько полезных свойств:
Менее желательной особенностью является то, что параметрическая кривая не интерполирует контрольные точки. Обычно кривая не проходит через контрольные точки.
В автоматизированном проектировании, автоматизированное производство и компьютерная графика, мощным расширением B-сплайнов являются неоднородные рациональные B-сплайны (NURBS). NURBS - это, по сути, B-сплайны в однородных координатах. Как и B-сплайны, они определяются своим порядком, вектором узла и набором контрольных точек, но, в отличие от простых B-сплайнов, каждая контрольная точка имеет вес. Когда вес равен 1, NURBS представляет собой просто B-сплайн, и, как таковой, NURBS обобщает как B-сплайны, так и кривые Безье и поверхности, основное различие заключается во взвешивании контрольных точек, что делает NURBS кривые "рациональные".
Оценивая NURBS при различных значениях параметров, кривую можно проследить в пространстве; аналогично, оценивая NURBS-поверхность при различных значениях двух параметров, поверхность может быть представлена в декартовом пространстве.
Подобно B-сплайнам, контрольные точки NURBS определяют форму кривой. Каждая точка кривой вычисляется путем взвешивания суммы нескольких контрольных точек. Вес каждой точки зависит от управляющего параметра. Для кривой степени d влияние любой контрольной точки ненулевое только в d + 1 интервалах (узлах) пространства параметров. В пределах этих интервалов вес изменяется в соответствии с полиномиальной функцией (базисными функциями) степени d. На границах интервалов базисные функции плавно уходят в нуль, причем гладкость определяется степенью полинома.
Узловой вектор - это последовательность значений параметров, которая определяет, где и как контрольные точки влияют на кривую NURBS. Количество узлов всегда равно количеству контрольных точек плюс градус кривой плюс один. Каждый раз, когда значение параметра входит в новый диапазон узлов, новая контрольная точка становится активной, а старая контрольная точка отбрасывается.
NURBS-кривая имеет следующий вид:
Здесь обозначения следующие. u - независимая переменная (вместо x), k - количество контрольных точек, N - это B-сплайн (используется вместо B), n - степень полинома, P - контрольная точка, а w - вес. Знаменатель - это нормализующий коэффициент, который дает единицу, если все веса равны единице.
Обычно это пишут как
, в котором функции
известны как рациональные базисные функции.
NURBS-поверхность получается как тензорное произведение двух NURBS-кривых с использованием двух независимых параметров u и v (с индексами i и j соответственно):
с
как рациональные базисные функции.
Цитированные работы