Кубический шлиц Эрмита

В численном анализе , A Сплайн Эрмита или кубический интерполятор Эрмита является сплайн , где каждая часть третьей степени многочлена , указанный в Эрмита форме , то есть, его ценности и первых производных в конечных точках соответствующего домена интервала. ^[1]

Кубические сплайны Эрмита обычно используются для интерполяции числовых данных, указанных при заданных значениях аргументов , для получения непрерывной функции . Данные должны состоять из желаемого значения функции и производной по каждому из них . (Если указаны только значения, производные должны оцениваться по ним.) Формула Эрмита применяется к каждому интервалу отдельно. Результирующий сплайн будет непрерывным и будет иметь непрерывную первую производную. ${\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n}}$ ${\ displaystyle x_ {k}}$ ${\ displaystyle (x_ {k}, x_ {k + 1})}$

Кубические полиномиальные сплайны могут быть заданы другими способами, кубика Безье является наиболее распространенной. Однако эти два метода обеспечивают одинаковый набор сплайнов, и данные можно легко преобразовать между формами Безье и Эрмита; поэтому имена часто используются как синонимы.

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

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

Кубические сплайны часто называют сплайнами , особенно в компьютерной графике. Шлицы Hermite названы в честь Чарльза Эрмита .

Интерполяция на одном интервале [ править ]

Единичный интервал (0, 1) [ править ]

На единичном интервале , учитывая начальную точку в и конечную точку в с начальной касательной в и конечной касательной в , многочлен может быть определен как ${\ displaystyle (0,1)}$ ${\boldsymbol {p}}_{0}$ $t=0$ ${\boldsymbol {p}}_{1}$ $t=1$ ${\boldsymbol {m}}_{0}$ $t=0$ ${\boldsymbol {m}}_{1}$ $t=1$

{\boldsymbol {p}}(t)=(2t^{3}-3t^{2}+1){\boldsymbol {p}}_{0}+(t^{3}-2t^{2}+t){\boldsymbol {m}}_{0}+(-2t^{3}+3t^{2}){\boldsymbol {p}}_{1}+(t^{3}-t^{2}){\boldsymbol {m}}_{1}

Четыре базисные функции Эрмита. Интерполянт в каждом подынтервале представляет собой линейную комбинацию этих четырех функций.

где t ∈ [0, 1].

Интерполяция на произвольном интервале [ править ]

Интерполяция в произвольном интервале делается путем отображения последнего через аффинный (степень 1) изменение переменного. Формула $x$ $(x_{k},x_{k+1})$ $[0,1]$

{\boldsymbol {p}}(x)=h_{00}(t){\boldsymbol {p}}_{k}+h_{10}(t)(x_{k+1}-x_{k}){\boldsymbol {m}}_{k}+h_{01}(t){\boldsymbol {p}}_{k+1}+h_{11}(t)(x_{k+1}-x_{k}){\boldsymbol {m}}_{k+1}.

с и относится к базовым функциям, определенным ниже. Обратите внимание, что значения тангенса были масштабированы по сравнению с уравнением на единичном интервале. $t=(x-x_{k})/(x_{k+1}-x_{k})$ $h$ $x_{k+1}-x_{k}$

Уникальность [ править ]

Указанные выше формулы обеспечивают уникальный полиномиальный путь третьей степени между двумя точками с заданными касательными.

Доказательство. Пусть - два полинома третьей степени, удовлетворяющие заданным граничным условиям. Затем определите : $P,Q$ $R=Q-P,$

R(0)=Q(0)-P(0)=0,

R(1)=Q(1)-P(1)=0.

Поскольку оба и являются многочленами третьей степени, не более чем полиномы третьей степени. Так должно быть в форме: $Q$ $P$ $R$ $R$

R(x)=ax(x-1)(x-r),

вычисление производной дает:

R'(x)=ax(x-1)+ax(x-r)+a(x-1)(x-r).

Кроме того, мы знаем, что:

R'(0)=Q'(0)-P'(0)=0

R'(0)=0=ar

( 1 )

R'(1)=Q'(1)-P'(1)=0

R'(1)=0=a(1-r)

( 2 )

Складывая ( 1 ) и ( 2 ) вместе, мы выводим, что и, следовательно, таким образом, $a=0$ $R=0,$ $P=Q.$

Представления [ править ]

Мы можем записать интерполяционный полином в виде

{\boldsymbol {p}}(t)=h_{00}(t){\boldsymbol {p}}_{0}+h_{10}(t){\boldsymbol {m}}_{0}+h_{01}(t){\boldsymbol {p}}_{1}+h_{11}(t){\boldsymbol {m}}_{1}

где , , , являются Эрмит базисных функций. Их можно записать по-разному, каждый из которых раскрывает разные свойства. $h_{00}$ $h_{10}$ $h_{01}$ $h_{11}$

	расширенный	факторизованный	Бернштейн
$h_{00}(t)$	$2t^{3}-3t^{2}+1$	$(1+2t)(1-t)^{2}$	$B_{0}(t)+B_{1}(t)$
$h_{10}(t)$	$t^{3}-2t^{2}+t$	$t(1-t)^{2}$	${\frac {1}{3}}\cdot B_{1}(t)$
$h_{01}(t)$	$-2t^{3}+3t^{2}$	$t^{2}(3-2t)$	$B_{3}(t)+B_{2}(t)$
$h_{11}(t)$	$t^{3}-t^{2}$	$t^{2}(t-1)$	$-{\frac {1}{3}}\cdot B_{2}(t)$

Столбец «развернутый» показывает представление, используемое в приведенном выше определении. Столбец "Факторизованный" сразу показывает, что и на границах равны нулю. Далее вы можете сделать вывод, что и иметь ноль кратности 2 в 0 и и иметь такой ноль в 1, таким образом, они имеют наклон 0 на этих границах. В столбце «Бернштейн» показано разложение базисных функций Эрмита на полиномы Бернштейна 3-го порядка: $h_{10}$ $h_{11}$ $h_{01}$ $h_{11}$ $h_{00}$ $h_{10}$

B_{k}(t)={3 \choose k}\cdot t^{k}\cdot (1-t)^{3-k}

Используя эту связь, вы можете выразить кубическую интерполяцию Эрмита в терминах кубических кривых Безье относительно четырех значений и выполнить интерполяцию Эрмита с использованием алгоритма де Кастельжау . Он показывает, что в кубическом фрагменте Безье две контрольные точки в середине определяют касательные кривой интерполяции в соответствующих внешних точках. ${\boldsymbol {p}}_{0},{\boldsymbol {p}}_{0}+{\frac {{\boldsymbol {m}}_{0}}{3}},{\boldsymbol {p}}_{1}-{\frac {{\boldsymbol {m}}_{1}}{3}},{\boldsymbol {p}}_{1}$

Интерполяция набора данных [ править ]

Набор данных, для , можно интерполировать, применяя описанную выше процедуру на каждом интервале, где касательные выбраны разумным образом, это означает , что касательные для интервалов , разделяющих конечные точки равны между собой . Тогда интерполированная кривая состоит из кусочно-кубических сплайнов Эрмита и глобально непрерывно дифференцируема в . $(x_{k},{\boldsymbol {p}}_{k})$ $k=1,\ldots ,n$ $(x_{1},x_{n})$

Выбор касательных не уникален, есть несколько вариантов.

Конечная разница [ править ]

Пример с конечно-разностными касательными

Самый простой выбор - трехточечная разность, не требующая постоянной длины интервала,

{\boldsymbol {m}}_{k}={\frac {1}{2}}\left({\frac {{\boldsymbol {p}}_{k+1}-{\boldsymbol {p}}_{k}}{x_{k+1}-x_{k}}}+{\frac {{\boldsymbol {p}}_{k}-{\boldsymbol {p}}_{k-1}}{x_{k}-x_{k-1}}}\right)

для внутренних точек и одностороннее различие в конечных точках набора данных. $k=2,\ldots ,n-1$

Кардинальный сплайн [ править ]

Пример кардинального сплайна в 2D. Линия представляет собой кривую, а квадраты - контрольные точки . Обратите внимание, что кривая не достигает первой и последней точек; однако эти точки влияют на форму кривой. Используемый параметр натяжения - 0,1

{\boldsymbol {p}}_{k}

Кардинал сплайна , иногда называют каноническим сплайн , ^[2] получается ^[3] , если

{\boldsymbol {m}}_{k}=(1-c){\frac {{\boldsymbol {p}}_{k+1}-{\boldsymbol {p}}_{k-1}}{x_{k+1}-x_{k-1}}}

используется для вычисления касательных. Параметр $c$ - это параметр натяжения, который должен находиться в интервале $[0,1]$ . В некотором смысле это можно интерпретировать как «длину» касательной. Выбор $c = 1$ дает нулевые касательные, а выбор $c = 0$ дает сплайн Катмалла – Рома.

Сплайн Катмулла – Рома [ править ]

Геометрическая интерпретация кубической интерполяции черной точки с равномерно расположенными абсциссами. ^[4]

Для касательных выбранных

{\boldsymbol {m}}_{k}={\frac {{\boldsymbol {p}}_{k+1}-{\boldsymbol {p}}_{k-1}}{x_{k+1}-x_{k-1}}}

получается сплайн Катмулла – Рома , являющийся частным случаем кардинального сплайна. Это предполагает одинаковый интервал между параметрами.

Кривая названа в честь Эдвина Катмалла и Рафаэля Рома . Основным преимуществом этого метода является то, что точки вдоль исходного набора точек также составляют контрольные точки для сплайновой кривой. ^[5] Требуются две дополнительные точки на обоих концах кривой. Единая реализация Катмулла – Рома может создавать петли и самопересечения. В хорде и центростремительные Катмуллы Rom реализации ^[6] решить эту проблему, но и использовать несколько иной расчет. ^[7] В компьютерной графике сплайны Катмулла – Рома часто используются для получения плавного интерполированного движения между ключевыми кадрами.. Например, большинство анимаций пути камеры, генерируемых из дискретных ключевых кадров, обрабатываются с помощью сплайнов Катмулла – Рома. Они популярны в основном из-за того, что их относительно легко вычислить, они гарантируют точное попадание в каждую позицию ключевого кадра, а также гарантируют, что касательные к сгенерированной кривой непрерывны по нескольким сегментам.

Сплайн Кочанека – Бартельса [ править ]

Kochanek-Бартелса сплайн является дальнейшее обобщение о том , как выбрать касательные заданные точки данных , и , с тремя параметрами возможных, напряжение смещения, и параметр непрерывности. ${\boldsymbol {p}}_{k-1}$ ${\boldsymbol {p}}_{k}$ ${\boldsymbol {p}}_{k+1}$

Монотонная кубическая интерполяция [ править ]

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

Интерполяция на единичном интервале с согласованными производными в конечных точках [ править ]

Учитывая единственную координату точек и значения, которые функция f ( x ) принимает на целочисленных ординатах x = n −1, n , n +1 и n +2, ${\boldsymbol {p}}_{n-1},{\boldsymbol {p}}_{n},{\boldsymbol {p}}_{n+1}$ ${\boldsymbol {p}}_{n+2}$

p_{n}=f(n)\quad \forall n\in \mathbb {Z}

Если, кроме того, касательные в конечных точках определены как центральные разности соседних точек,

m_{n}={\frac {f(n+1)-f(n-1)}{2}}={\frac {p_{n+1}-p_{n-1}}{2}}\quad \forall n\in \mathbb {Z}

Чтобы оценить интерполированное f ( x ) для действительного x , сначала разделите x на целую часть, n , и дробную часть, u

x=n+u

n=\lfloor x\rfloor =\operatorname {floor} (x)

u=x-n=x-\lfloor x\rfloor

0\leq u<1

Тогда сплайн Катмалла – Рома имеет вид ^[8]

{\begin{aligned}f(x)=f(n+u)&=\mathrm {CINT} _{u}\left(p_{n-1},p_{n},p_{n+1},p_{n+2}\right)\\[8pt]&={\begin{bmatrix}1&u&u^{2}&u^{3}\\\end{bmatrix}}\cdot {\begin{bmatrix}0&1&0&0\\-{\tfrac {1}{2}}&0&{\tfrac {1}{2}}&0\\1&-{\tfrac {5}{2}}&2&-{\tfrac {1}{2}}\\-{\tfrac {1}{2}}&{\tfrac {3}{2}}&-{\tfrac {3}{2}}&{\tfrac {1}{2}}\\\end{bmatrix}}\cdot {\begin{bmatrix}p_{n-1}\\p_{n}\\p_{n+1}\\p_{n+2}\\\end{bmatrix}}\\\\&={\frac {1}{2}}{\begin{bmatrix}-u^{3}+2u^{2}-u\\3u^{3}-5u^{2}+2\\-3u^{3}+4u^{2}+u\\u^{3}-u^{2}\end{bmatrix}}^{\mathrm {T} }\cdot {\begin{bmatrix}p_{n-1}\\p_{n}\\p_{n+1}\\p_{n+2}\end{bmatrix}}\\\\&={\frac {1}{2}}{\begin{bmatrix}u((2-u)u-1)\\u^{2}(3u-5)+2\\u((4-3u)u+1)\\u^{2}(u-1)\end{bmatrix}}^{\mathrm {T} }\cdot {\begin{bmatrix}p_{n-1}\\p_{n}\\p_{n+1}\\p_{n+2}\end{bmatrix}}\\\\&={\tfrac {1}{2}}{\bigg (}{\big (}u^{2}(2-u)-u{\big )}p_{n-1}\ +\ {\big (}u^{2}(3u-5)+2{\big )}p_{n}+\ {\big (}u^{2}(4-3u)+u{\big )}p_{n+1}\ +\ u^{2}(u-1)p_{n+2}{\bigg )}\\\\&={\tfrac {1}{2}}{\bigg (}(-u^{3}+2u^{2}-u)p_{n-1}\ +\ (3u^{3}-5u^{2}+2)p_{n}+\ (-3u^{3}+4u^{2}+u)p_{n+1}\ +\ (u^{3}-u^{2})p_{n+2}{\bigg )}\\\\&={\tfrac {1}{2}}{\bigg (}(-p_{n-1}+3p_{n}-3p_{n+1}+p_{n+2})u^{3}\ +\ (2p_{n-1}-5p_{n}+4p_{n+1}-p_{n+2})u^{2}\ +\ (-p_{n-1}+p_{n+1})u\ +\ 2p_{n}{\bigg )}\\\\&={\tfrac {1}{2}}{\bigg (}{\Big (}(-p_{n-1}+3p_{n}-3p_{n+1}+p_{n+2})u\ +\ (2p_{n-1}-5p_{n}+4p_{n+1}-p_{n+2}){\Big )}u\ +\ (-p_{n-1}+p_{n+1}){\bigg )}u\ +\ p_{n}\\\end{aligned}}

$\lfloor x\rfloor$ обозначает минимальную функцию, которая возвращает наибольшее целое число, не превышающее x, и обозначает транспонирование матрицы . Нижнее равенство отображает применение метода Хорнера . $\mathrm {T}$

Это письмо актуально для трикубической интерполяции , где одна оптимизация требует, чтобы вы вычислили CINT _u шестнадцать раз с одним и тем же u и разными p .

См. Также [ править ]

Бикубическая интерполяция , обобщение до двух измерений
Трикубическая интерполяция , обобщение до трех измерений
Эрмита интерполяция
Многомерная интерполяция
Сплайн-интерполяция
Дискретная сплайн-интерполяция

Ссылки [ править ]

^ Эрвин Крисзиг (2005). Высшая инженерная математика (9-е изд.). Вайли. п. 816. ISBN 9780471488859.
^ Петцольд, Чарльз (2009). «Канонические сплайны в WPF и Silverlight» .
^ "Кардинальные сплайны" . Сеть разработчиков Microsoft . Проверено 27 мая 2018 .
^ Кубическая интерполяция не уникальна: эта модель, использующая сплайн Катмулла-Рома и базисные полиномы Лагранжа, проходит через все четыре точки. Примечание. В левой трети желтое горизонтальное расстояние отрицательно, так как черная точка находится слева от желтой точки; в правой трети зеленое горизонтальное расстояние отрицательно, так как черная точка находится справа от зеленой точки.
^ Catmull, Эдвин ; Ром, Рафаэль (1974), «Класс локальных интерполирующих сплайнов», в Барнхилле, штат Рэпиз; Ризенфельд, РФ (ред.), Компьютерное геометрическое проектирование , Нью-Йорк: Academic Press, стр. 317–326.
^ Н. Дин, MS Floater, и К. Хорманн. Подразделение кривой по четырем точкам на основе повторной хордовой и центростремительной параметризации. Компьютерное геометрическое проектирование, 26 (3): 279 {286, 2009
^ П. Дж. Барри и Р. Н. Голдман. Рекурсивный алгоритм вычисления для класса сплайнов Катмулла-Рома. SIGGRAPH Computer Graphics, 22 (4): 199 {204, 1988.
^ Две иерархии сплайн-интерполяции. Практические алгоритмы многомерных сплайнов высшего порядка

Внешние ссылки [ править ]

Сплайновые кривые , профессор Дональд Х. Хаус Университет Клемсона
Многомерная интерполяция и аппроксимация Эрмита , профессор Чандраджит Баджадж, Университет Пердью
Введение в сплайны Катмалла – Рома , MVPs.org
Интерполяция кардинальных сплайнов и сплайнов Катмулла – Рома
Методы интерполяции: линейный, косинусный, кубический и эрмитовый (с источниками C)
Общие уравнения сплайна

[kreyszig-1] Эрвин Крисзиг (2005). Высшая инженерная математика (9-е изд.). Вайли. п. 816. ISBN 9780471488859.

[2] Петцольд, Чарльз (2009). «Канонические сплайны в WPF и Silverlight» .

[3] "Кардинальные сплайны" . Сеть разработчиков Microsoft . Проверено 27 мая 2018 .

[4] Кубическая интерполяция не уникальна: эта модель, использующая сплайн Катмулла-Рома и базисные полиномы Лагранжа, проходит через все четыре точки. Примечание. В левой трети желтое горизонтальное расстояние отрицательно, так как черная точка находится слева от желтой точки; в правой трети зеленое горизонтальное расстояние отрицательно, так как черная точка находится справа от зеленой точки.

[5] Catmull, Эдвин ; Ром, Рафаэль (1974), «Класс локальных интерполирующих сплайнов», в Барнхилле, штат Рэпиз; Ризенфельд, РФ (ред.), Компьютерное геометрическое проектирование , Нью-Йорк: Academic Press, стр. 317–326.

[6] Н. Дин, MS Floater, и К. Хорманн. Подразделение кривой по четырем точкам на основе повторной хордовой и центростремительной параметризации. Компьютерное геометрическое проектирование, 26 (3): 279 {286, 2009

[7] П. Дж. Барри и Р. Н. Голдман. Рекурсивный алгоритм вычисления для класса сплайнов Катмулла-Рома. SIGGRAPH Computer Graphics, 22 (4): 199 {204, 1988.

[8] Две иерархии сплайн-интерполяции. Практические алгоритмы многомерных сплайнов высшего порядка

[1]