1. Методы и алгоритмы формирования контурных изображений

1.4. Интерполяция и аппроксимация кривых произвольного типа

1.4.4. Сплайновая интерполяция

Методы аппроксимации функций с помощью сплайнов, предложенные впервые в 40-х годах, получили широкое распространение только в последнее время.

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

Английское слово spline означает «упругая рейка». Такую рейку используют в качестве гибкого лекала при вычерчивании плоских кривых по опорным точкам.

Основная идея применения сплайнов состоит в следующем. Интервал, на котором восстанавливают функцию, разбивают на подинтервалы (рис.1.16), на каждом из которых функцию задают полиномом достаточно низкой степени и обеспечивают непрерывность кривой в точках “склейки” путем приравнивания значений полиномов на границах подинтервалов.  

Рис. 1.16. Восстановление сигналов при помощи сплайнов.  

При этом важным условием является также непрерывность нескольких производных. Таким образом, сплайном P_n называют совокупность многочленов P_ni степени n, заданных на i-том шаге дискретизации и удовлетворяющих условию 

P_ni(t_i) = P_n(i-1)(t_i),

т.е. степени n сплайн-функциями, составленными из «кусочков» многочленов данной степени, которые состыкованы так, чтобы получившаяся функция была непрерывной и имела несколько непрерывных производных.

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

Известно, что когда однородный брус закрепить в двух произвольных точках и предать его оси заданный наклон в этих точках, то форма кривой бруса описывается полиномом третьей степени.

Предположим, что кубическая парабола, заданная в параметрической форме

P(t) = a₃t³ + a₂t² + a₁t + a₀

проходит через две точки P(t₁) и P(t₂), в которых известны значения производных Р^/(t₁) и Р^/(t₂). Это означает, что заданы четыре необходимых и достаточных условия для определения четырех неизвестных коэффициентов в приведенном выше выражении. Этот многочлен называют кубическим интерполяционным многочленом Эрмита.

Параметрическое представление кривой имеет то преимущество, что можно выбрать произвольный диапазон изменения параметра. Для простоты вычислительного процесса будем считать, что параметр t в пределах каждого сегмента изменяется в диапазоне от 0 до 1 (0£t£1).

Нетрудно заметить, что P(0)=a₀, P(1)=a₀+a₁+a₂+a₃.

Определим производную Р^/(t): Р^/(t)=3a₃t²+2a₂t+ a₁.

Отсюда следует, что Р^/(0)=a₁, Р^/(1)=3a₃ +2a₂+a₁.

Из приведенных выражений легко определить неизвестные a₀, a₁, a₂, a₃:

                    a₀=P(0),

                    a₁=Р^/(0),

                    a₂=3 [P(1)–P(0)]–4Р^/(0)–Р^/(1),

Рассмотренная процедура выполняется для каждой пары заданных точек кривой. Так, определив кубическую параболу между точками P(t₁) и P(t₂) на интервале t₁t₂, для нахождения следующей дуги кривой на интервале t₂t₃ необходимо на границе интервала (точка t₂) приравнять значения как самих кривых, так и их первых производных, т.е. выполнить “склеивание”.

Определим выражение для кубической кривой X(t) в форме Эрмита в матричной форме, если известны конечные точки и касательные вектора к кривой в этих точках.

Определим, что Р1, Р4 – точки; R1, R4 – касательные. 

X(0) = P_1x                       X(1) = P_4x

X(0) = R_1x                       X(1) = R_4x

или 

X(t) = TC_x     (*),

где   T = [t³, t², t, 1], C = [a₀, a₁, a₂, a₃],

X(0) = P_1x = [0,0,0,1]C_x,

X(1) = P_4x = [1,1,1,1]C_x ,

X^/(t) = [3t², 2t, 1, 0]C_x,

X^/(0) = R_1x = [0,0,1,0]C_x,

X^/(1) = R_4x = [3,2,1,0]C_x.

P₁          0, 0, 0, 1

P₄          1, 1, 1, 1

R₁        0, 0, 1, 0

R₄       3, 2, 1, 0

Обращая матрицу размером 4x4, получаем

M_h – называется матрицей Эрмита, G_hх – геометрическим вектором Эрмита.

Подставив С_x в (*), получим:  

X(t)=TMG.

Найдем произведение ТМ:

  TM=(2t³–3t²+1)(–2t³+3t²)(t³–2t²+t)(t³–t²).

Перемножая это выражение справа на G_hx, получим:

  X(t)=TM_hG_hx=P_1x(2t³–3t²+1)+P_4x(–2t³+3t²)+R_1x(t³–2t²+t)+R_4x(t³–t²)

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

С помощью первых двух функций определяются точки Р₁ и Р₄, а с помощью других получим сглаженное объединение. Чем больше касательный вектор, тем круче сама кривая.

К недостаткам такого подхода следует отнести необходимость задания производных в узлах. Для их нахождения используют ряд подходов.

Наиболее просто использовать вместо производных их приближенные значения, полученные в результате других аппроксимаций. Например, для каждого узла по значениям функций в ближайших 2m узлах строится многочлен степени 2m+1, производные которого затем используются для построения эрмитового сплайна.

При представлении кривой в форме Безье для нахождения производных P^/(t_i) и P^/(t_i+1) используются две дополнительные точки (рис.1.17) R_i и R_i+1, которые задают два касательных вектора P(t_i)R_i и P(t_i+1)R_i+1.  

Рис. 1.17. Нахождение поризводных по методу Безье

Производные P^/(t_i) и P^/(t_i+1) определяют по следующим выражениям:

R₁=3(P₂–P₁)=P’(0),

R₄=3(P₄–P₃)=P’(1).

Это соотношение между матрицей Эрмита G_h и геометрической матрицей Безье. Подставляя полученные значения, получаем

X(t)=TM_hG_h =TM_hM_bG_b

Обозначив произведение M_hM_b через М получаем соотношение X(t)=TMG_b, которое имеет форму Бєзье.  

Форма Безье используется в машинной графике чаще, чем форма Эрмита. Причины в следующем:

*  во-первых, в случае формы Эрмита касательные векторы должны задаваться в явном виде. В форме Безье касательные находят “локатором”;

*  во-вторых, в форме Безье четыре точки задают выпуклый многоугольник, который можно выполнить резиновой нитью.

Определим  Х = TM_bG_b.

X=TM_bG_b=(1–t)³P₁+3t(t–1)²P₂+3t³(1–t)P₃+t³P_4.

Можно показать, что сумма всех коэффициентов при t равна 1, что определяет оптимальное среднее значение для четырех управляющих точек.

Разработан подход, согласно которого производные в промежуточных точках находят путем решения матричного уравнения вида:  

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

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

В общем случае, когда в моменты времени e=0,1,2,… заданы дискретные отсчеты сигнала x₀, x₁, x₂,…, восстанавливающая дискретизированный сигнал сплайн-функция n-ой степени имеет вид :  

где B_n(e) – некоторый сплайн степени n (B-сплайн Шенберга) и называемый ядром сплайна. Функция B_n(e) описывается следующим образом:

где C – число сочетаний из (n+1) по k.

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

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

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

Контрольные  вопросы.

5.   Какие цели преследуются при переходе от интерполяции многочленами к интерполяции сплайнами?    

     Содержание