B-шлиц - B-spline

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

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

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

Вступление

В срок «B-сплайн» был изобретен Исаак Якоб Шенберг[1] и является сокращением от основного сплайна.[2] Сплайн-функция порядка это кусочно многочлен функция степени в переменной . Места, где встречаются части, называются узлами. Ключевым свойством сплайн-функций является то, что они и их производные могут быть непрерывными, в зависимости от кратности узлов.

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

Определение

Кардинальный квадратичный 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-сплайнами.

Альтернативно, B-сплайны могут быть определены путем построения с помощью формулы рекурсии Кокса – де Бора. Учитывая последовательность узлов , то B-сплайны порядка 1 определяются равенствами

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

B-сплайны более высокого порядка определяются рекурсией

куда

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

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

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

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

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

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

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

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

[7]

То есть, кусочно-постоянная единица или ноль, указывающая на какой узел Икс находится в (нуле, если узел j повторяется). Уравнение рекурсии состоит из двух частей:

пандусы от нуля до единицы как Икс идет от к и

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

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

Применение формулы рекурсии с узлами при дает куски однородного B-сплайна порядка 3

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

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

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

Кардинальный B-шлиц

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

Обозначение "заполнитель" используется, чтобы указать, что пth разделенная разница функции двух переменных т и Икс следует принять путем фиксации Икс и учитывая как функция т один.

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

Например, если мы хотим интерполировать три значения между узлами B-сплайна (), мы можем записать сигнал как:

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

Быстрая интерполяция b-сплайном на однородной области выборки может выполняться с помощью итеративной фильтрации среднего значения. В качестве альтернативы функция прямоугольника равна Sinc в области Фурье. Следовательно, интерполяция кубическим сплайном равняется умножению сигнала в области Фурье на Sinc ^ 4.

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

P-шлиц

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

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

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

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

Отсюда следует, что

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

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

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

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

с

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

Отношение к кусочно / составному Безье

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

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

Чтобы получить непрерывность C2, кривая Безье теряет локальный контроль, потому что для обеспечения непрерывности C2 контрольные точки зависят друг от друга. Если движется одна контрольная точка, необходимо переоценить весь сплайн. B-сплайны имеют как непрерывность C2, так и локальное управление, но они теряют свойство интерполяции кусочного Безье.[19]

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

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

W (х) это вес и у (х) является исходным значением в Икс. Коэффициенты - параметры, которые предстоит определить. Значения узлов могут быть фиксированными или их также можно рассматривать как параметры.

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

Компьютерный дизайн и компьютерная графика

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

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

Веса , и могут быть объединены в точки в 3-м пространстве. Эти точки широко известны как контрольные точки.

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

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

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

NURBS

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

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

Surface Modelling.svg

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

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

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

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

Обозначения здесь следующие. ты - независимая переменная (вместо Икс), k - количество контрольных точек, N B-сплайн (используется вместо B), п - степень полинома, п это контрольная точка и ш это вес. Знаменатель - это нормализующий коэффициент, который дает единицу, если все веса равны единице.

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

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

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

NURBS-поверхность получается как тензорное произведение двух кривых NURBS, таким образом используя два независимых параметра ты и v (с индексами я и j соответственно):[24]

с

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

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

Примечания

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

Рекомендации

  1. ^ де Бур, стр. 114
  2. ^ Гэри Д. Нотт (2000), Интерполяция кубических сплайнов. Springer. п. 151
  3. ^ Hartmut., Prautzsch (2002). Безье и методы B-сплайна. Математика и визуализация. Бём, Вольфганг., Палушны, Марко. Берлин, Гейдельберг: Springer Berlin Heidelberg. п. 63. Дои:10.1007/978-3-662-04919-8. ISBN  9783662049198. OCLC  851370272.
  4. ^ Talebitooti, ​​R .; Shojaeefard, M.H .; Ярмохаммадисатри, Садех (2015). «Оптимизация формы цилиндрического резервуара с использованием b-шлицевых кривых». Компьютер и жидкости. 109: 100–112. Дои:10.1016 / j.compfluid.2014.12.004.
  5. ^ де Бур, стр.113.
  6. ^ де Бур, стр. 131.
  7. ^ де Бур, стр. 131
  8. ^ де Бур, стр. 134.
  9. ^ Ли, Э. Т. Ю. (декабрь 1982 г.). «Упрощенная процедура вычисления B-сплайна». Вычисление. 29 (4): 365–371. Дои:10.1007 / BF02246763.
  10. ^ Ли, Э. Т. Ю. (1986). «Комментарии к некоторым алгоритмам B-сплайнов». Вычисление. 36 (3): 229–238. Дои:10.1007 / BF02240069.
  11. ^ де Бур, стр. 322.
  12. ^ Эйлерс, P.H.C. и Маркс, Б. (1996). Гибкое сглаживание с помощью B-сплайнов и штрафов (с комментариями и репликой). Статистическая наука 11 (2): 89-121.
  13. ^ Eilers, Paul H.C .; Маркс, Брайан Д. (2003). «Многомерная калибровка с температурным взаимодействием с использованием двумерной регрессии сигнала со штрафами». Хемометрия и интеллектуальные лабораторные системы. 66 (2): 159–174. Дои:10.1016 / S0169-7439 (03) 00029-7.
  14. ^ де Бур, стр. 115
  15. ^ Карлсон, Б. (1991). «B-сплайны, гипергеометрические функции и средние Дирихле». Журнал теории приближений. 67 (3): 311–325. Дои:10.1016 / 0021-9045 (91) 90006-В.
  16. ^ Глюзенкамп, Т. (2018). «Вероятностная обработка неопределенности от конечного размера взвешенных данных Монте-Карло». EPJ Plus. 133 (6): 218. arXiv:1712.01293. Bibcode:2018EPJP..133..218G. Дои:10.1140 / epjp / i2018-12042-x.)
  17. ^ Евгений В. Шикин; Александр И. Плис (14 июля 1995 г.). Справочник по шлицам для пользователя. CRC Press. С. 96–. ISBN  978-0-8493-9404-1.
  18. ^ Вернеке, Джози (1993). "8". Наставник Inventor: программирование объектно-ориентированной трехмерной графики с помощью Open Inventor, выпуск 2 (1-е изд.). Бостон, Массачусетс, США: Addison-Wesley Longman Publishing Co., Inc. ISBN  978-0201624953.
  19. ^ Зорин, Денис (2002), Кривые Безье и B-сплайны, Цветение (PDF), Нью-Йоркский университет, получено 4 января 2015
  20. ^ де Бур, Глава XIV, стр. 235
  21. ^ Ганс, Питер; Гилл, Дж. Бернард (1984). «Сглаживание и дифференцирование спектроскопических кривых с помощью сплайн-функций». Прикладная спектроскопия. 38 (3): 370–376. Bibcode:1984ApSpe..38..370G. Дои:10.1366/0003702844555511.
  22. ^ Вичек, Мария; Neal, Sharon L .; Уорнер, Исайя М. (1986). "Фильтрация данных двумерной флуоресценции во временной области". Прикладная спектроскопия. 40 (4): 542–548. Bibcode:1986ApSpe..40..542V. Дои:10.1366/0003702864508773.
  23. ^ Пигль и Тиллер, глава 4, сек. 2
  24. ^ Пигль и Тиллер, глава 4, сек. 4

Процитированные работы

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

  • Ричард Х. Бартельс; Джон С. Битти; Брайан А. Барский (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.

внешняя ссылка