Универсальный Метод

В 1999 году Choong-Gyoo Lim предложил интересный метод выбора параметров. В предыдущих методах мы находили параметры, а потом получали узловой вектор. Метод Lim, известный как универсальный метод, работает по-другому, используя равномерно распределенные узлы для вычисления параметров.

Допустим, нам нужны n +1 параметров, по одному на каждую исходную точку, а степень желаемой интерполтрованной кривой равна p. Затем, количество узлов равно m +1, где m = n + p + 1. Lim предложил равномерно распределить эти узлы. Говоря точнее, первые p +1 узлов равны 0, последние p +1 узлов равны 1, а оставшиеся n - p узлов равномерно делят область [0,1]. Таким образом, узлы равны:

Этот набор узлов фиксированного типа определяет n +1 базисных функций B-spline. Затем, параметры выбираются так, чтобы у них были значения, в которых соответствующие им базисные функции достигали максимума. Взгляните на следующий рисунок, где n = 6 (т.e. 7 исходных точек), p = 4, а m = 11 (т.e. 12 узлов). Так как мы используем фиксированные узлы, то 0 и 1 - это два узла множественности 5 (т.e. p +1) и есть только два внутренних узла в 1/3 и 2/3. Заметьте, что всего n +1 базисных функции B-spline, а максимумы первой и последней равны 0 и 1, соответственно. Другие максимумы помечены голубыми квадратиками, а параметры помечены желтыми кружками.

Приведем пример с расчетами вручную. Допустим, у нас есть 4 исходных точки (т.e. n =3) и степень p =2. Таким образом, количество узлов равно 7 (т.e. m = n + p + 1 = 6). Так как узлы равномерно распределены, то они равны

u 0 = u 1 = u 2	u 3	u 4 = u 5 = u 6
	0.5

Затем можно вычислить желаемые базисные функции B-spline. Начнем со степени 0 (т.e. p = 0). Нажмите тут, чтобы посмотреть определение базисных функций B-spline, и тут, для примеров по вычислениям. Полученные результаты:

Узловой интервал	Базисная функция
[ u 0, u 1) = [0,0)	N 0,0(u) = 0
[ u 1, u 2) = [0,0)	N 1,0(u) = 0
[ u 2, u 3) = [0,0.5)	N 2,0(u) = 1
[ u 3, u 4) = [0.5,1)	N 3,0(u) = 1
[ u 4, u 5) = [1,1)	N 4,0(u) = 0
[ u 5, u 6) = [1,1)	N 5,0(u) = 0

Затем вычисляем базисные функции 1 степени. Так как и N _0,0(u), и N _1,0(u) равно 0, то N _0,1(u) везде равно нулю. Аналогично, N _4,1(u) также равно нулю везде. Таким образом, для базисных функций 1 степени, нам нужно вычислить только N _1,1(u), N _2,1(u) и N _3,1(u) как показано ниже:

Базисная Функция	Уравнение	Ненулевая Область
N 0,1(u)		везде
N 1,1(u)	1-2 u	[0,0.5)
N 2,1(u)	2 u	[0,0.5)
2(1- u)	[0.5,1)
N 3,1(u)	2 u -1	[0.5,1)
N 4,1(u)		везде

Базисные функции 2 степени вычисляются следующим образом:

Базисная Функция	Уравнение	Ненулевая Область
N 0,2(u)	(1-2 u)^2	[0,0.5)
N 1,2(u)	2 u (2-3 u)	[0,0.5)
2(1- u)^2	[0.5,1)
N 2,2(u)	2 u ^2	[0,0.5)
-2(1-4 u +3 u ^2)	[0.5,1)
N 3,2(u)	(2 u -1)^2	[0.5,1)

Следующий рисунок показывает все четыре базисные функции B-spline 2 степени.

Нетрудно проверить, что максимумы N _0,2(u), N _1,2(u), N _2,2(u) и N _3,2(u) равны 1 при u = 0, 2/3 при u = 1/3, 2/3 при u = 2/3 и 1 при u = 1. Таким образом, по универсальному методу, узловой вектор равен { 0, 0, 0, 0.5, 1, 1, 1}, а вектор параметров равен { 0, 1/3, 2/3, 1}. В данном случае у нас равномерно распределенные параметры. Тем не менее, в общем случае параметры не обязательно должны быть равномерно распределены, хотя распределение параметров обычно довольно ровное. Из-за этого факта универсальный метод работает похоже на метод равномерного распределения.

Из-за того, что узлы равномерно распределены, множественных узлов нет и все базисные функции являются C^{p -1}-непрерывными. Нажмите тут, чтобы узнать больше о непрерывности базисных функций B-spline. Таким образом, на практике, максимум базисной функции B-spline не нужно вычислять точно. Опыт показывает, что подбор некоторых значений на ненулевой области и затем выбор из них одного с максимальным значением функции обычно дает довольно точный результат. Если желательно найти точные максимумы, то можно использовать одномерный поиск, например, по методу золотого сечения. Область поиска - это, конечно, ненулевая область базисной функции B-spline.

У универсального метода есть очень интересное свойство. А именно - он является инвариантным для преобразований подобия. Это значит, что трансформированная интерполированная кривая B-spline может быть получена трансформированием исходных точек. Это похоже на свойство инвариантности преобразований подобия для кривых B-spline. Исходя из такого вывода, сразу можно сказать, что тем же свойством обладает и метод равномерного распределения, потому что узловой вектор вычисляется из набора равномерно распределенных параметров, которые неизменны до и после трансформации. Но например, метод длины хорды и центростремительный методы не являются инвариантными для преобразований подобия.

Дата добавления: 2015-10-29