Алгоритм Де Бура

Метод оценки сплайновых кривых

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

Введение

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

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

B-сплайны имеют локальную поддержку, что означает, что полиномы положительны только в конечной области и равны нулю в других местах. Формула рекурсии Кокса-де Бура ^[4] показывает это: $${\displaystyle B_{i,0}(x):={\begin{cases}1&{\text{if }}\quad t_{i}\leq x<t_{i+1}\\0&{\text{otherwise}}\end{cases}}}$$ $${\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).}$$

Пусть индекс определяет интервал узла, содержащий позицию, . Мы можем видеть в формуле рекурсии, что только B-сплайны с являются ненулевыми для этого интервала узла. Таким образом, сумма уменьшается до: ${\displaystyle k}$ ${\displaystyle x\in [t_{k},t_{k+1})}$ ${\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}$

Пусть для . Итерация для : Обратите внимание, что j должен отсчитываться в обратном порядке. После завершения итераций результат будет . ${\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 \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  deBoor ( k :  int ,  x :  int ,  t ,  c ,  p :  int ): """Оценивает S(x). Аргументы --------- k: Индекс интервала узла, содержащего x. х: Позиция. t: Массив позиций узлов, необходимо дополнить, как описано выше. c: Массив контрольных точек. p: Степень B-сплайна. """ d  =  [ c [ j  +  k  -  p ]  для  j  в  диапазоне ( 0 ,  p  +  1 )]  для  r  в  диапазоне ( 1 ,  p  +  1 ): для  j  в  диапазоне ( p ,  r  -  1 ,  - 1 ): альфа  =  ( х  -  т [ j  +  к  -  р ])  /  ( т [ j  +  1  +  к  -  р ]  -  т [ j  +  к  -  р ])  d [ j ]  =  ( 1,0  -  альфа )  *  d [ j  -  1 ]  +  альфа  *  d [ j ] возврат  d [ p ]

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

• Алгоритм Де Кастельжау
• кривая Безье
• Неравномерный рациональный B-сплайн

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

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

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

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

Ссылки

1. C. de Boor [1971], "Пакет подпрограмм для вычислений с B-сплайнами", Techn.Rep. LA-4728-MS, Los Alamos Sci.Lab, Los Alamos NM; стр. 109, 121.
2. Ли, ETY (декабрь 1982 г.). «Упрощенная процедура вычисления B-сплайна». Computing . 29 (4). Springer-Verlag: 365–371. doi :10.1007/BF02246763. S2CID  2407104.
3. Ли, ETY (1986). «Комментарии к некоторым алгоритмам B-сплайна». Вычислительная техника . 36 (3). Springer-Verlag: 229–238. doi :10.1007/BF02240069. S2CID  7003455.
4. К. де Бур, стр. 90

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

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