Алгоритм Де Бура
Метод оценки сплайновых кривых

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

Введение

Общее введение в B-сплайны дано в основной статье . Здесь мы обсуждаем алгоритм де Бура, эффективную и численно устойчивую схему для оценки сплайновой кривой в позиции . Кривая строится из суммы функций B-сплайна , умноженных на потенциально векторные константы , называемые контрольными точками, B-сплайны порядка связаны кусочно-полиномиальными функциями степени, определенной по сетке узлов (в дальнейшем мы всегда используем индексы, отсчитываемые от нуля). Алгоритм де Бура использует операции O (p 2 ) + 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).} p + 1 {\displaystyle p+1} p {\displaystyle p} t 0 , … , t i , … , t m {\displaystyle {t_{0},\dots ,t_{i},\dots ,t_{m}}} B i , n ( x ) {\displaystyle B_{i,n}(x)} n = p + 1 {\displaystyle n=p+1}

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

B-сплайны имеют локальную поддержку, что означает, что полиномы положительны только в конечной области и равны нулю в других местах. Формула рекурсии Кокса-де Бура [4] показывает это: B i , 0 ( x ) := { 1 if  t i ≤ x < t i + 1 0 otherwise {\displaystyle B_{i,0}(x):={\begin{cases}1&{\text{if }}\quad t_{i}\leq x<t_{i+1}\\0&{\text{otherwise}}\end{cases}}} B i , p ( x ) := x − t i t i + p − t i B i , p − 1 ( x ) + t i + p + 1 − x t i + p + 1 − t i + 1 B i + 1 , p − 1 ( x ) . {\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-сплайны с являются ненулевыми для этого интервала узла. Таким образом, сумма уменьшается до: k {\displaystyle k} x ∈ [ t k , t k + 1 ) {\displaystyle x\in [t_{k},t_{k+1})} i = k − p , … , k {\displaystyle i=k-p,\dots ,k} S ( x ) = ∑ i = k − p k c i B i , p ( x ) . {\displaystyle \mathbf {S} (x)=\sum _{i=k-p}^{k}\mathbf {c} _{i}B_{i,p}(x).}

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

Алгоритм

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

Пусть будут новыми контрольными точками с для . Для применяется следующая рекурсия: d i , r {\displaystyle \mathbf {d} _{i,r}} d i , 0 := c i {\displaystyle \mathbf {d} _{i,0}:=\mathbf {c} _{i}} i = k − p , … , k {\displaystyle i=k-p,\dots ,k} r = 1 , … , p {\displaystyle r=1,\dots ,p} d i , r = ( 1 − α i , r ) d i − 1 , r − 1 + α i , r d i , r − 1 ; i = k − p + r , … , k {\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} α i , r = x − t i t i + 1 + p − r − t i . {\displaystyle \alpha _{i,r}={\frac {x-t_{i}}{t_{i+1+p-r}-t_{i}}}.}

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

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

Оптимизации

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

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

Пусть для . Итерация для : Обратите внимание, что j должен отсчитываться в обратном порядке. После завершения итераций результат будет . d j := c j + k − p {\displaystyle \mathbf {d} _{j}:=\mathbf {c} _{j+k-p}} j = 0 , … , p {\displaystyle j=0,\dots ,p} r = 1 , … , p {\displaystyle r=1,\dots ,p} d j := ( 1 − α j ) d j − 1 + α j d j ; j = p , … , r {\displaystyle \mathbf {d} _{j}:=(1-\alpha _{j})\mathbf {d} _{j-1}+\alpha _{j}\mathbf {d} _{j};\quad j=p,\dots ,r\quad } α j := x − t j + k − p t j + 1 + k − r − t j + k − p . {\displaystyle \alpha _{j}:={\frac {x-t_{j+k-p}}{t_{j+1+k-r}-t_{j+k-p}}}.} S ( x ) = d 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 ]

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

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

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

  • 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. ^ ab 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=De_Boor%27s_algorithm&oldid=1222413890"