Трибрат
Артем
Александрович

Факультет КИТА
Группа КСД 00а
Научный руководитель: Адамов В.Г.
Тема магистрской работы: "Построение автоматизированной системы определения контура объекта на примере изображения клеток"

Содержание

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

1.В-сплайны.

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

(1)

Единственное ограничение заключается в том, что В-сплайны должны отвечать условию

(2)

Рис. 1. В-сплайн первого порядка.

В особенности

подразумевает

(3)

Из этих уравнений В-сплайнов первых порядков можно получить В-сплайны высоких порядков рекуррентным отношением:

(4)

где

Таким образом В-сплайны второго порядка определяются как

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

Рис. 2. В-сплайн второго порядка.

В-сплайны третьего порядка определяются как

(7)

Таким образом  состоит из трех квадратичных частей.

Рис.3. В-сплайн третьего порядка.

После шагов, получим  в следующем виде

с каждым степень полинома , так как это сумма  полиномов.

2. Сплайны.

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

(9)

множеством всех таких сплайнов. Обратим особое внимание на следующую последовательность узлов:

(10)

которая является множеством всех целых чисел.

Сплайн, связанный с этой последовательностью, называется основной сплайн. Поскольку из-за однородности последовательности узлов  формулы, вовлекающие основной  В-сплайн, являются часто намного более простыми, чем соответствующие формулы для общих B-сплайнов. Для начала, все основные B-сплайны данного порядка переводимы друг в друга. С индексированием , имеем

(11)

и

(12)

Рекуррентное отношение выглядит следующим образом

(13)

3. Кубические В-сплайны и аппроксимация многоугольниками.

Причина выбора B-сплайнов, а не так называемые естественные сплайны, с которыми мы знакомый из классической теории интерполяции, является так называемым локальным контролем свойств В-сплайнов. Полиномиальные коэффициенты естественных сплайнов требуют всех  узловых точек. Их вычисление вовлекает обращение  матриц. В этом имеется два недостатка: перемещение одной узловой точки затрагивает всю кривую и во время обращения матрицы можно столкнуться с быстрым изменением кривой. С другой стороны, В-сплайны состоят из сегментов кривых, зависящих только от нескольких узловых точек. Это называется локальным контролем. Таким образом, перемещение узловой точки затрагивает только маленькую часть кривой. B-сплайны имеют ту же самую непрерывность, как естественные сплайны, но не интерполируют их узловые точки. Поэтому, мы говорим о приближении многоугольника, а не о вставке узловой точки.

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

1. Полиномы нижних степеней дают слишком низкую гибкость в управлении формой кривой. Сплайны первого порядка (прямые линии) не дают удовлетворительной гладкости аппроксимирующей кривой. Сплайны второго порядка (квадратичные кривые) дают гладкую кривую, но проблема возникает в точках, где соединяются сегменты кривой. Чтобы понять эту проблему, мы введем новый критерий:

Определение 1. Обозначим  сегмент кривой. Если направление и величина  и  равны в точке соединения, кривая, состоящая из этих двух сегментов, называется  непрерывной.

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

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

3. Говоря, что кубические сплайны дают "удовлетворительную" непрерывность, имеется в виду, что глаз не может обнаружить геометрическую неоднородность степени выше, чем два и практически достаточно использовать сплайны третьей степени.

Наконец, покажем математическое описание кривой snake как взвешенной суммы В-сплайнов.

Параметрические сплайновые кривые

(14)

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

Для каждой базисной функции  определена узловая точка , и кривая snake является взвешенной суммой узловых точек

(15)

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

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

, где

(16)

Далее, функция координат может быть записана как

(17)

и

(18)

где  это вектор функций В-сплайнов. Параметрическая кривая  имеет следующий вид

(19)

где

(20)

где - операция Кронекера.

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

(21)

описывающий форму кривой. В этом случае матричный оператор  имеет вид

(22)

где элементы матрицы  получаются как .

Можно переписать выражение (15) в следующем виде. Ограничивая  интервалом , можем определить это как полином  степени . В этом разделе всегда подразумевается, что интервал  фактически ; это может быть получено  аффинным преобразованием переменной. Каждый  полином может быть записан как ряд Тейлора. Таким образом, можно записать

(23)

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

	(24)

Пусть имеется множество точек . Сперва проведем параметризацию множества:

(25)

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

Затем,производим расчет сплайнов, используя рекуррентные формулы (4). Видно,  что сплайны первого порядка локально контролируются тремя узлами, сплайны второго порядка локально контролируются четырьмя узлами, сплайны третьего порядка – пятью узлами. Начнем расчет выражения  на каждом интервале  для узлов 0, 1, 2,3, 4.

	(26)

Далее, получим

		для	(27)
		для
		для
		для

Для данного случая функцию  (соответственно ) можно представить в виде:

(28)