Алгоритм де Бурса - De Boors algorithm

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

Вступление

Общее введение в B-сплайны дано в основная статья. Здесь мы обсуждаем алгоритм де Бура, эффективную и численно стабильную схему для оценки сплайн-кривой. ${\displaystyle \mathbf {S} (x)}$ на позиции ${\displaystyle x}$. Кривая строится из суммы B-сплайновых функций ${\displaystyle B_{i,p}(x)}$ умноженный на потенциально векторные константы ${\displaystyle \mathbf {c} _{i}}$, называемые контрольными точками,

${\displaystyle \mathbf {S} (x)=\sum _{i}\mathbf {c} _{i}B_{i,p}(x).}$

B-шлицы порядка ${\displaystyle p+1}$ являются связными кусочно-полиномиальными функциями степени ${\displaystyle p}$ определяется сеткой узлов ${\displaystyle {t_{0},\dots ,t_{i},\dots ,t_{m}}}$ (в дальнейшем мы всегда используем индексы, начинающиеся с нуля). Алгоритм Де Бура использует О (п²) + О (p) операции для оценки сплайновой кривой. Обратите внимание основная статья о B-шлицах и классические публикации^[1] используйте другое обозначение: B-сплайн индексируется как ${\displaystyle B_{i,n}(x)}$ с ${\displaystyle n=p+1}$.

Местная поддержка

B-сплайны имеют локальную опору, что означает, что полиномы положительны только в конечной области и равны нулю в других местах. Формула рекурсии Кокса-де Бура^[4] показывает это:

${\displaystyle B_{i,0}(x):=\left\{{\begin{matrix}1&\mathrm {if} \quad t_{i}\leq x<t_{i+1}\\0&\mathrm {otherwise} \end{matrix}}\right.}$

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

Пусть индекс ${\displaystyle k}$ определить интервал узла, который содержит позицию, ${\displaystyle x\in [t_{k},t_{k+1})}$. Из формулы рекурсии видно, что только B-сплайны с ${\displaystyle i=k-p,\dots ,k}$ отличны от нуля на этом интервале узлов. Таким образом, сумма сводится к:

${\displaystyle \mathbf {S} (x)=\sum _{i=k-p}^{k}\mathbf {c} _{i}B_{i,p}(x).}$

Это следует из ${\displaystyle i\geq 0}$ который ${\displaystyle k\geq p}$. Точно так же мы видим в рекурсии, что местоположение самого высокого запрошенного узла находится в индексе ${\displaystyle k+1+p}$. Это означает, что любой интервал узлов ${\displaystyle [t_{k},t_{k+1})}$ который фактически используется, должен иметь как минимум ${\displaystyle p}$ дополнительные узлы до и после. В компьютерной программе это обычно достигается путем повторения первого и последнего использованного местоположения узла. ${\displaystyle p}$ раз. Например, для ${\displaystyle p=3}$ и реальные места узлов ${\displaystyle (0,1,2)}$, можно было бы добавить вектор узла к ${\displaystyle (0,0,0,0,1,2,2,2,2)}$.

Алгоритм

С этими определениями мы можем теперь описать алгоритм де Бура. Алгоритм не вычисляет B-сплайн-функции. ${\displaystyle B_{i,p}(x)}$ напрямую. Вместо этого он оценивает ${\displaystyle \mathbf {S} (x)}$ через эквивалентную формулу рекурсии.

Позволять ${\displaystyle \mathbf {d} _{i,r}}$ быть новыми контрольными точками с ${\displaystyle \mathbf {d} _{i,0}:=\mathbf {c} _{i}}$ за ${\displaystyle i=k-p,\dots ,k}$. За ${\displaystyle r=1,\dots ,p}$ применяется следующая рекурсия:

${\displaystyle \mathbf {d} _{i,r}=(1-\alpha _{i,r})\mathbf {d} _{i-1,r-1}+\alpha _{i,r}\mathbf {d} _{i,r-1};\quad i=k-p+r,\dots ,k}$

${\displaystyle \alpha _{i,r}={\frac {x-t_{i}}{t_{i+1+p-r}-t_{i}}}.}$

После завершения итераций у нас есть ${\displaystyle \mathbf {S} (x)=\mathbf {d} _{k,p}}$, означающий, что ${\displaystyle \mathbf {d} _{k,p}}$ желаемый результат.

Алгоритм Де Бура более эффективен, чем явный расчет B-сплайнов. ${\displaystyle B_{i,p}(x)}$ с формулой рекурсии Кокса-де Бора, поскольку она не вычисляет члены, которые гарантированно умножаются на ноль.

Оптимизация

Вышеупомянутый алгоритм не оптимизирован для реализации на компьютере. Требуется память для ${\displaystyle (p+1)+p+\dots +1=(p+1)(p+2)/2}$ временные контрольные точки ${\displaystyle \mathbf {d} _{i,r}}$. Каждая временная контрольная точка записывается ровно один раз и читается дважды. Путем обращения итерации на ${\displaystyle i}$ (обратный отсчет вместо восходящего), мы можем запустить алгоритм с памятью всего за ${\displaystyle p+1}$ временные контрольные точки, позволяя ${\displaystyle \mathbf {d} _{i,r}}$ повторно использовать память для ${\displaystyle \mathbf {d} _{i,r-1}}$. Точно так же есть только одно значение ${\displaystyle \alpha }$ используется на каждом шаге, поэтому мы также можем повторно использовать память.

Кроме того, удобнее использовать индекс, отсчитываемый от нуля. ${\displaystyle j=0,\dots ,p}$ для временных контрольных точек. Отношение к предыдущему индексу: ${\displaystyle i=j+k-p}$. Таким образом, мы получаем улучшенный алгоритм:

Позволять ${\displaystyle \mathbf {d} _{j}:=\mathbf {c} _{j+k-p}}$ за ${\displaystyle j=0,\dots ,p}$. Итерация для ${\displaystyle r=1,\dots ,p}$:

${\displaystyle \mathbf {d} _{j}:=(1-\alpha _{j})\mathbf {d} _{j-1}+\alpha _{j}\mathbf {d} _{j};\quad j=p,\dots ,r\quad }$ (${\displaystyle j}$ нужно вести обратный отсчет)

${\displaystyle \alpha _{j}:={\frac {x-t_{j+k-p}}{t_{j+1+k-r}-t_{j+k-p}}}.}$

После завершения итераций результат будет ${\displaystyle \mathbf {S} (x)=\mathbf {d} _{p}}$.

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

Следующий код в Язык программирования Python наивная реализация оптимизированного алгоритма.

def деБур(k: int, Икс: int, т, c, п: int):    "" "Оценивает S (x).    Аргументы    ---------    k: Индекс узлового интервала, который содержит x.    x: Позиция.    t: массив позиций узлов, необходимо дополнить, как описано выше.    c: массив контрольных точек.    p: Степень B-сплайна.    """    d = [c[j + k - п] за j в классифицировать(0, п + 1)]    за р в классифицировать(1, п + 1):        за j в классифицировать(п, р - 1, -1):            альфа = (Икс - т[j + k - п]) / (т[j + 1 + k - р] - т[j + k - п])            d[j] = (1.0 - альфа) * d[j - 1] + альфа * d[j]    возвращаться d[п]

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

• Алгоритм де Кастельжау
• Кривая Безье
• NURBS

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

• Алгоритм Де Бура
• Расчет ДеБура-Кокса

Компьютерный код

• PPPACK: содержит много сплайновых алгоритмов в Фортран
• Научная библиотека GNU: C-библиотека, содержит вспомогательную библиотеку для сплайнов, перенесенных из PPPACK
• SciPy: Python-библиотека, содержит подбиблиотеку scipy.interpolate со сплайн-функциями на основе ФИТПАК
• TinySpline: C-библиотека для сплайнов с оболочкой C ++ и привязками для C #, Java, Lua, PHP, Python и Ruby
• Einspline: C-библиотека для сплайнов в 1, 2 и 3 измерениях с оболочками Fortran

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

1. К. де Бур [1971], "Пакет подпрограмм для расчета с B-сплайнами", Techn.Rep. LA-4728-MS, Лос-Аламосская научная лаборатория, Лос-Аламос, штат Нью-Мексико; п. 109, 121.
2. Ли, Э. Т. Ю. (декабрь 1982 г.). «Упрощенная процедура вычисления B-сплайна». Вычисление. Springer-Verlag. 29 (4): 365–371. Дои:10.1007 / BF02246763.
3. Ли, Э. Т. Я. (1986). «Комментарии к некоторым алгоритмам B-сплайнов». Вычисление. Springer-Verlag. 36 (3): 229–238. Дои:10.1007 / BF02240069.
4. К. де Бур, стр. 90

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

• Карл де Бур (2003). Практическое руководство по сплайнам, переработанное издание. Springer-Verlag. ISBN  0-387-95366-3.