Алгоритм де Бура (Glikjnmb ;y >rjg)

Перейти к навигации Перейти к поиску

Алгоритм де Бура[1] — это численный метод вычисления значения B-сплайна в заданной точке; является обобщением алгоритма де Кастельжо для кривых Безье. Оригинальная версия алгоритма, разработанная Карлом де Буром в 1971 году, имеет полиномиальную вычислительную сложность, но отличается хорошей численной устойчивостью. Последующие модификации, появившиеся в попытке упростить и ускорить алгоритм, демонстрируют сравнительно худшую устойчивость.[2][3]

Алгоритм де Бура предназначен для вычисления сплайна при фиксированном значении аргумента . Сам сплайн представляется в виде линейной комбинации контрольных точек (векторов, не зависящих от ), коэффициенты которой суть базисные сплайн-функции :

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

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

Ограниченность носителя

[править | править код]

Каждый базисный сплайн имеет компактный (ограниченный) носитель, что означает, что он принимает ненулевое значения только на конечном отрезке. Это видно из рекурсивной формулы Кокса—де Бура:

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

Заметим, что индекс сумирования принимает осмысленные значения () только при . С другой стороны, рекурсивная формула для -го сегмента включает узлы с индексами до . Следовательно, чтобы находить значение сплайна для любого из отрезка , необходимо иметь не менее дополнительных узлов до и после него. На практике этого обычно достигают, дублируя первый и последний узел нужное число раз. Например, если и даны узлы в точках , то расширенный массив узлов будет иметь вид:.

Теперь мы готовы непосредственно описать алгоритм де Бура. Он не вычисляет B-сплайны напрямую, а находит значение по эквивалентной рекурсивной формуле.

Введём новый набор контрольных точек ; положим для , а остальные найдём, последовательно применяя для слудующую формулу:

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

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

Оптимизации

[править | править код]

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

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

  1. Устанавливаем для .
  2. Повторяем для всех :
    , где .
  3. Возвращаем ответ: .

Пример реализации

[править | править код]

Ниже приводится код усовершенствованного алгоритма на языке Python.

def deBoor(k: int, x: int, t, c, p: int):
    """Вычисление сплайна S(x) по алгоритму де Бура.

    Входные параметры
    -----------------
    k: Индекс сегмента, содержащего x.
    x: Точка, в которой требуется вычислить сплайн.
    t: Массив узлов (расширенный дополнительными узлами, см. статью).
    c: Массив контрольных точек.
    p: Степень сплайна.
    """
    d = [c[j + k - p] for j in range(0, p + 1)] 

    for r in range(1, p + 1):
        for j in range(p, r - 1, -1):
            alpha = (x - t[j + k - p]) / (t[j + 1 + k - r] - t[j + k - p]) 
            d[j] = (1.0 - alpha) * d[j - 1] + alpha * d[j]

    return d[p]

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

[править | править код]

Промышленные реализации

[править | править код]

Алгоритм де Бура реализован во многих популярных библиотеках на разных языках программирования:

  • PPPACK: содержит алгоритмы для работы со сплайнами на языке Fortran.
  • GNU Scientific Library: библиотека на языке C, включает в себя портированную версию предыдущей библиотеки.
  • SciPy: библиотека для Python; функции для работы со спалайнами содержатся в модуле scipy.interpolate, они основываются на FITPACK.
  • TinySpline: специализированная библиотека на C, имеет также интерфейсы для C++, C#, Java, Lua, PHP, Python и Ruby.
  • Einspline: ещё реализация на C с обёрткой для Fortran; поддерживает 1-, 2- и 3-мерные сплайны.

Примечания

[править | править код]
  1. C. de Boor [1971], "Subroutine package for calculating with B-splines", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; p. 109, 121.
  2. Lee, E. T. Y. (December 1982). "A Simplified B-Spline Computation Routine". Computing. 29 (4). Springer-Verlag: 365—371. doi:10.1007/BF02246763. S2CID 2407104.
  3. Lee, E. T. Y. (1986). "Comments on some B-spline algorithms". Computing. 36 (3). Springer-Verlag: 229—238. doi:10.1007/BF02240069. S2CID 7003455.

Литература

  • Carl de Boor. A Practical Guide to Splines, Revised Edition. — Springer-Verlag, 2003. — ISBN 0-387-95366-3.