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

На правах рукописи

Семенов Андрей Борисович

МАТЕМАТИЧЕСКИЙ МЕТОД И КОМПЛЕКС ПРОГРАММ АППРОКСИМАЦИИ ФОРМЫ ИЗОБРАЖЕНИЙ ЦИРКУЛЯРНЫМИ ФИГУРАМИ

Специальность 05.13 18 математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Тверь 2005

Работа выполнена на кафедре информационных систем и технологий факультета прикладной математики и кибернетики Тверского государственного университета.

Научный руководитель:

доктор технических наук, профессор Л.М. Местецкий

Официальные оппоненты:

доктор физико-математических наук, профессор Е.А. Андреева доктор физико-математических наук, профессор С В. Клименко

Ведущая организация:

Вычислительный центр РАН

Защита состоится 30 сентября 2005 г. в 14:00 на заседании диссертационного совета Д212.263.04 при Тверском государственном университете по адресу: 170013, г. Тверь, ул. Желябова, 33.

С диссертацией можно ознакомиться в библиотеке Тверского государственного университета

Автореферат разослан 29 августа 2005 г.

Ученый секретарь диссертационного совета

доктор технических наук, профессор

В.Н. Михно

//¿fa

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Задача представления и анализа формы плоских фигур играет важную роль в системах компьютерной графики и машинною зрения. Для описания плоских фигур применяют несколько подходов. Известен подход описания фигур с помощью задания границы объекта. Граница плоской фигуры представляет собой совокупность контуров - простых замкнутых кривых'без самопересечения. Эти контура могут быть описаны либо в параметрической форме, т.е. уравнением вида F(t) = (x(t),y(t)), У(а)-У(Ь), либо с помощью

многоугольников в виде последовательного списка вершин. Граничное представление используется для анализа, распознавания и преобразования формы. Наряду с граничным представлением известен неявный способ описания плоского обьекта, который состоит в задании так называемой функции принадлежности, принимающей значение 1 внутри фигуры и 0 вне нее. Этот подход предназначен для прослеживания границы, для изображения фигуры на растровых устройствах (дисплей, принтер). Граничное и неявное описание формы хорошо подходят для задач, связанных с использованием локальных свойств границы фигуры, но не пригодно для исследования общей структуры объектов сложной формы в силу того, что довольно сложно получить информацию об интегральной структуре объекта из такого представления фигуры.

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

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

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

Целью диссертационного исследования является разработка нового

плоских

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЕКА СЛст«| О»

математического метода описания, анализа и

И1Ю1СЯЛ

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

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

Рис. 1

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

В-сплайновые кривые); О - множество конечных объединений жирных линий к

вида о) ~ Уд, Д е В, I -1, ,к, к<~с так называемых циркулярных фигур. Пусть а

- плоская фигура, представленная в виде растрового бинарного изображения; р(а,со) - мера близости объекта а и циркулярной фигуры со. Задача состоит в том, чтобы найти aeQ. такую, что ц(а,со)<е, где е - наперед заданная точность аппроксимации. В качестве меры близости может выступать, например, хаусдорфово расстояние.

Решение научной задачи основывается на следующих идеях: 1. Преобразование растрового бинарного изображения в непрерывное предрТ-щ^й^в вддр циркулярной фигуры:

i - л i а«! ■ ) 4

' '»¡vyqf -i* ■ |

>»» ОТ) f •

граница исходного дискретного образа аппроксимируется многоугольной фигурой, минимального периметра, разделяющей

точки объекта и фона;

- строится непрерывный скелет полученной многоугольной фигуры как множество центров максимальных вписанных в фигуру кругов;

- каждая отдельная ветвь скелета, представляющего собой планарный граф, аппроксимируется жирной линией.

2. Описание жирных линий с помощью математического аппарата В-сплайнов. Такое представление позволяет строить, преобразовывать, анализировать плоские фигуры, описанные как объединение жирных линий (циркулярные фигуры).

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

подхода к описанию формы плоских объектов, расширяющего возможности анализа, синтеза и преобразования объектов сложной формы.

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

1. использованием для описания жирных линий математического аппарата В-сплайновых кривых;

2. разработкой теории непрерывной аппроксимации дискретных изображений с помощью жирных линий этого класса;

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

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

Практическая значимость

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

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

Новые научные результаты, выносимые на защиту:

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

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

3. Метод сравнения формы изображений на основе циркулярного разложения бинарного образа, основанный на представлении исходных образов в виде совокупности жирных линий (циркулярное разложение) и сравнении их между собой. В качестве меры близости двух жирных линий при сравнении выступает симметрическая разность площадей сравниваемых примитивов.

Структура диссертации.

Диссертационная работа состоит из введения, пяти глав, заключения и списка литера гуры В первой главе проводится обзор математических методов описания плоских фигур и жирных линий. Определяется круг задач и приложений, в которых могут быть использованы эти геометрические примитивы, осуществляется постановка научной задачи, раскрывается структура метода ее решения и исследования Во второй главе описывается математическая теория жирных линий, вводятся определения и общие свойства жирных кривых. Рассматриваются задачи подгонки жирных линий и локализации точки относительно жирной линии. В третьей главе рассматривается задача описания формы объектов с помощью жирных линий, построения сложных форм из них, исследуется подход к аппроксимации с заданной точностью дискретных образов с помощью жирных линий. Четвертая глава посвящена приложению аппарата жирных В-силайновых кривых в задачах двумерной графики. Рассматривается задача преобразования цветных (текстурных) образов и задача анимации на основе жирных линий. В пятой главе исследуется вопрос использования жирных линий для построения меры сходства формы объектов В качестве применения рассматривается приложение к задаче биометрической идентификации личности по форме ладони. В заключении подводятся итоги работы Диссертация содержит 129 страниц машинописного текста, 81 рисунок. Список литературы включает 76 наименований.

Апробация. Представленные в работе результаты докладывались и обсуждались на 13-й и 14-й международных конференциях по компьютерной графике и машинному зрению «Графикон» (Москва 2003, 2004 года), 7-й

международной конференции «Распознавание образов и анализ изображений» (Санкт-Петербург, 2004 год), 3-м международном практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2005 год), научных семинарах факультета ПМиК ТвГУ.

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

Внедрение результатов. Выносимые на защиту методы были' реализованы, исследованы и использованы в рамках проектов Российского Фонда фундаментальных исследований (РФФИ): 02-01-00667 «Дискретно-непрерывные преобразования формы геометрических объектов в задачах обработки и анализа изображений», 04-01-08058 «Анализ и классификация формы изображений в задачах биометрической идентификации», 05-01-00542 «Методы распознавания формы изображений на основе дискретно-непрерывных преобразований».

СОДЕРЖАНИЕ РАБОТЫ

Введение содержит общую характеристику работы, обоснование актуальности темы исследования, цели и задачи диссертационного исследования.

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

Во второй главе приводится описание математической теории жирных линий.

Определение 1. Жирной линией Р - («(ОМ'),КО) называется множество точек, образованных объединением С = и С, однопараметрического семейства

А]

кругов С, = {{х,у)е Л2 (х-и(1))г+(у-г(1))2 ^ги)1} на евклидовой плоскости Л2, где - непрерывные дифференцируемые на [а,Ь] функции, причем

/-(О>0. Кривая />(/)-(и(1)М<))называется осью жирной линии, а г(1)- ее шириной.

Жирную линию можно рассматривать как след от перемещения окружности С, переменного радиуса вдоль осевой линии Р(1). Внешний вид и свойства жирной линии зависят от выбора типа функций ы(г)Х/),г(7) и от выбора отрезка числовой прямой 1а, Ь], на котором и определены эти функции. В качестве таких функций удобно взять полиномы небольших степеней и положить [а,Ь] = [0,1].

Определение 2. Элементарная кубическая жирная В-сплайновая кривая, заданная на отрезке [а, Ь] = [0,1], определяется следующим векторным

j 3

уравнением: С(/) - , где '£[0,1] - параметр кривой,

6

Я, ={#„,#,,#„}, г = 0, 3- множество контрольных кругов с центрами в и радиусами я„, а В,С/;- базисные функции кубического В-сплайна, имеющие следующий вид: В0(О = ( 1-03 в,(0-3г3 6г2 +4 В2(/) = -Зг3 + 3/2 + 3/ + 1 '

Пример элементарной кубической жирной В-сплайновой кривой с соответствующими контрольными кругами {//0, ,Я,} представлен на рис. 2.

И,

И,1

Рис.2

Элементарные кривые могут объединяться в более сложные графические примитивы - составные жирные линии.

Определение 3. Кривая у, которая представляется в виде объединения элементарных кубических В-сплайновых кривых 2>, называется

составной кубической В-сплайновой кривой с общим семейством контрольных кругов Я-(Я0, ,Я„,), где кривая имеет контрольные круги

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

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

Теорема 1. Граница элементарной жирной В-сплайновой кривой C(í) = (u(t),v(0,r( ох 1 е ГОЛ описывается дугами окружностей С(0), С(1) и сопряженными с ними двумя кривыми (x,(t),y {t)),(x¡(t),y2(t))!t е[0,1], определяемыми уравнениями.

иг Г V r\U +V -г

х\ = " ~ -,Г"И +-^—р-

и +V и +V

У\ '

где

u'r^lu'1

(1)

У i

V г г

v'r-Ju'2 +v'2 -г'2 ц'2 + у'2

u'rylu'2+v'2-r'2

и^+72

(2),

vr/ и v'

s.r'

-f'+3f2-3i + l

М

З?1 — 6t2 + 4

к +-

6

) UJ

-3r2 + 6Г-3

'iV 4V

9г2 -12г

+- к,

6

,

-9t + 6f + 3

+ 3i + 1 i3

fl + — 6

Л J

3f2 (и Г

+ Vз

6

,

(С,, V,, Я) - контрольный круг, задаваемый центром (£/,, V,) и радиусом

Если считать, что осевая линия ориентирована по направлению роста параметра г жирной линии, то уравнения (1) и (2) задают правую и левую огибающие соответственно. Так как огибающие заданы явно, можно построить их кусочно-линейную аппроксимацию ломаными линиями.

Теорема 2. Ось и границы составной жирной В-сплайновой кривой сохраняют гладкость (имеют непрерывную первую производную) вне зависимости от положения центров семейства ее контрольных кругов и величины их радиусов.

Задача локализации точки относительно жирной линии состоит в определении того, лежит ли произвольная точка плоскости внутри жирной линии либо снаружи. Решение этой задачи дает характеристическая функция [1, если точка принадлежит жирной линии [О, в противном случае

Теорема 3. Характеристическая функция элементарной жирной В-сплайновой кривой С(г) = (ы(/),у(г),г(г)). г е [ОД] есть

Г1, если и>(0) - »>(1) г 1 [О, в противном случае' где »'(0 - число перемен знака в ряде

ЧЧО = (х - ¿С/,в,(О)2 + (у - ¿К, 8, (О)3 - (£ Я, В,(О)2 и

жирной линии х(х< У) =

Штурма многочлена

=2>,<о

_(1 -о3

и,

Uoj

3/' -6i2 +4

"<V Г.

Л J

-v3 +ЗГ +3r+1

I «J

(ГУ.,V,,R,) - контрольный Kpyi с центром в (U,,V:) и радиусом Д,, i - О, ,3.

Задача восстановления кривой по точкам ("curve fitting1) является одной из фундаментальных в компьютерной графике. В диссертации эта задача обобщается на случай восстановления жирных В-сплайновых кривых по множеству кругов.

Пусть дана последовательность кругов Ga, ,G„_,, каждый из которых описывается в виде G] = (Gp,Glv,GJr), где (G^G,,)- координаты центра круга, а Gjr - его радиус. Требуется построить составную жирную В-сплайновую кривую C(i) = (it(t), v(t),r(t)), 1акую чтобы она точно проходила через все круги G. - задача интерполяции (3r = r, C(f,) = G,, i = 0,. либо достаточно близко от кругов

Gj - задача аппроксимации ( d / = г, p(C(t, ),G ) < к, i = 0,. , п -1).

Определение 4 Круги С^, ,С1!_1, через которые должна пройти жирная линия будем называть опорными.

Теорема 4. Интерполяционная жирная В-сплайновая кривая, проходящая через опорные круги сь, ,С„_,, имеет множество контрольных кругов Я0> ,Я„_ , получаемых из решения системы линейных уравнений: (О. = Я,

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

Выбор монотонно возрастающей последовательности ta,tv может быть получен как результат параметризации множества исходных опорных кругов следующим образом:

где /Ч0',,0 )= -С,)2 +(С„ ^(С,г-С^,)2 - мера близости дв>х опорных кругов С, и

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

На рис. За представлена последовательность из 30 опорных кругов, на рис. ЗЬ - интерполяционная жирная линия, проходящая через все опорные кру1И, на Зс - аппроксимирующая жирная линия с ошибкой аппроксимации с- 25. Величина ошибки аппроксимации е = 25 (выбрана для примера) равна длине отрезка, показанного на рис. Зс.

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

£ = 25

с

Рис.3

10

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

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

Решение задачи циркулярного разложения осуществляется в несколько шагов.

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

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

3. Третий шаг заключается в выделении так называемого базового скелета с помощью отсечения несущественных ветвей.

4. Последний шаг состоит в декомпозиции базового скелета на однопараметрические семейства кругов и аппроксимации их жирными В-сплайновыми кривыми методом, описанным в главе 2. Тем самым задача представления растрового образа сводится к задаче восстановления жирной В-сплайновой кривой по семейству кругов. Решения задач пунктов 1-3 представляют собой развитие методов,

описанных в работах Л.М. Местецкого и И.А. Рейера1.

Циркулярное разложение образа даст простую возможность для осуществления различных сложных топологических преобразований над фигурами, описанными таким способом (вытягивание, изгиб, изменение ширины отдельных частей или фигуры в целом) путем изменения центров контрольных кругов и их радиусов. На рис. 4 показан пошагово способ получения непрерывного представления растровой фигуры (1 - исходный растровый образ, 2 - аппроксимирующая полигональная область (граница). 3 -

1 Местецкий Л.М. Непрерывный скелет бинарного растрового изображения Труды межд. конф. "Графикон-98", Москва, 1998.

Местецкий Л.М., Рейер И.А. Непрерывное скелетное представление изображения с контролируемой точностью. Труды межд. конф. "Графикон-2003", Москва, 2003.

скелет полигональной области, 4 - базовый скелет, 5 - базовый скелет с кругами, 6 - аппроксимирующая циркулярная фигура).

Рис. 4

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

Преобразование жирной линии происходит через изменение положения центра и радиуса каждого контрольного круга в отдельности, не затрагивающее при этом остальные круги. Такая модель преобразования удобна, когда количество перемещаемых кругов невелико. Однако в практических задачах возникает необходимость в создании инструмента по управлению жирной линией как единого (целого) объекта. В диссертации разработан метод «вытягивания бус» применительно для семейства контрольных кругов, который позволил обеспечить простоту и удобство управления жирной В-сплайновой кривой.

Рис.5

12

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

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

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

Пусть задана жирная линия F = (u(t),v{t),r(t)). Рассмотрим семейство жирных линий вида F(Á) = (u(t),v(t),Ar(í)),A>0. Для различных значений Я жирные линии будут иметь одну и ту же осевую линию P(t) = (u(t),v(t)) и отличаться только шириной Mt).

Определение 6. F(X) называется Я - слоем жирной линии F.

Метод раскраски при программной реализации состоит в послойной дискретизации жирной кривой на m слоев, каждый из коюрых имеет глубину Я, =1 -i¡m, i = 0, ,т. Пусть для раскраски жирной линии заданы два цвета: сживет осевой линии и £л- цвет границы. Toi да цвет для каждого слоя вычисляется по следующей формуле ¿¡: = ^ *Я, + *П Я, ), Я, е [0 1] (рис. б).

Любая точка жирной линии является граничной для некоторого Я- слоя жирной линии и для каждой точки границы Л - слоя существует единственный круг в Л- слое, для которою эта точка является граничной: СТ(Л) = {(х,у)сГ? (х-и(т)У +(у-м(т)? <Щг)?}-

Каждый круг СДЯ) кроме круюв С,(Я) и Г,(Я) имеет две общие точки с границей по одну и по другую стороны от оси Я- слоя. Поэтому положение любой ючки внутри Я- слоя однозначно задается тройкой чисел (Я,г,<т), где

а

Рис. 6

<7 6 {-1,1}- параметр, определяющий положение точки относительно осевой линии (справа или слева) (рис. 7а). Для концевых кругов слоя С,(Л) и С, (Л) положение точки на границе требует уточнения, поскольку для всех точек соответствующей дуги Л и г - одинаковы. Поэтому для этих точек вводится четвертый параметр в, представляющий собой относи 1ельный угол, локализующий точку в концевых кру! ах (рис. 7Ь).

Рис.7

Таким образом, четверка (Л,т,0,<т) однозначно задает положение точки в жирной лини.

Определение 7. Циркулярными координатами точки называется четверка чисел (Л,т,0,а).

Условием принадлежности точки (X,У) Л- слою жирной кривой является существование некоторого /еГО,11 такого, что (Х-и(1))2 +{У-v(t)f < (Яг(г))2.

Алгоритм эталонной раскраски жирной линии заключается в сканировании попиксельно раскрашиваемой жирной линии (образа) и вычислении циркулярных координат Затем в эталонной жирной линии (прообразе) ищется точка с такими же циркулярными координатами и сканируемая точка закрашивается в цвет найденной точки (рис. 8).

Прообраз(эталон)

Рис. 8

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

осуществить морфинг образов с целью получения анимационного эффекта (рис. 9).

Рис. 9

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

• получение циркулярных фигур сравниваемых растровых бинарных образов на основе аппроксимации, описанной в главе 3;

• сравнение жирных линий, составляющих циркулярную фигуру между собой;

• получение интегральной оценки сравнения образов.

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

Рассмотрим произвольную жирную линию F (г) - (u(t)Mt),r(t)), с осью P(t)~\x{t),y(t) 1 и шириной ?•(/), t с [а, Ь\. Пусть / = /(/) функция длины оси жирной линии на отрезке [о,/], тогда t=f\l) Функция r(/) = r(/"'i7)) будет представлять собой зависимость ширины жирной линии от параметра /. На

Рис. 10

Рассмотрим теперь две произвольные жирные линии Г,(7), (<) и построим в общей системе координат графики функций г (I) и гг(1). Обозначим через ¿, -длину осевой линии жирной кривой /•,(/),<-1,2. Пусть £ = т доопределим функции г,(1) на [0,1] как г,(/) = 0 при /> /,,, если <Л. Пусть О, -область, ограниченная графиком функции г (/) и осью абсцисс, ; = 1,2.

Обозначим через «(Д1Ш2) - площадь объединения множеств Л,и О,, а через П О,) - площадь их пересечения. Определение 8. Мерой сходства двух жирных линий /^(г) и Рг(г) будем

называть величину А -- 11 ч - ь

|шш(г,(/),г2(0)й/

}тах(г,(/),г2(/М

о

На рис. 11 показана графически мера сходства двух жирных линий.

Рис. 11

Очевидно, что .9(0, и В2) > ¡(0 ПС2) и поэтому 0 < А < 1. Чем более похожи две жирные линии, тем ближе значение Л к 1. У абсолютно идентичных жирных линий величина сходства будет равна единице.

Предлагаемый подход в сравнении двух произвольных образов через ' сравнение жирных линий предоставляет возможность в качестве применения исследовать задачу биометрической идентификации личности по форме ладони. Системы подобного рода занимают третье место после распознавания отпечатков пальцев и черт лица и составляют порядка И процентов от всех биометрических устройств, применяемых в современном мире. Гипотеза, заложенная в данном подходе, состоит в том, что любого человека можно идентифицировать по форме его пальцев на ладони. Задача распознавания формы человеческой ладони в терминах жирных линий решается методом сравнения с эталоном. Предлагается следующий алгоритм сравнения двух силуэтов ладони.

1. Для каждого образа ладони строим циркулярное разложение.

2. Из каждого циркулярного разложения отбираем и идентифицируем пять самых длинных жирных линий.

3. Попарно проводим сравнение соответствующих жирных линий. Результатом сравнения г- ой пары будет, величина ф, е[0,1],/ -1, ,5, которая характеризует меру сходства двух жирных линий.

4. Результатом сравнения двух образов ладоней будет величина ф = .

Полученное значение фс[0,1] будет показывать относительную меру сходства двух образов ладони. Идея предлагаемого метода показана на рис. 12.

Рис. 12

Для экспериментальной оценки качества распознавания была создана база изображений ладоней. С помощью цифрового фотоаппарата, закрепленного на штативе, были сфотографированы ладони 13 человек Ладонь каждого человека фотографировалась 5 раз на белом фоне, при этом положение пальцев каждый раз было разным. В результате пороговой бинаризации было получено 65 ч/б изображений: /,, , /65. Все 65 изображений эталонов разбиты на 13 классов по 5 изображений. Каждый класс - это ладонь одного человека. Сам эксперимент состоял в следующем.

1. Для каждой пары образов из созданной базы прецедентов вычисляем меру сходства. Получаем матрицу сходства Ф =|| фч размером 65x65. Элемент ф,, показывает относительную близость образов /, и ¡/.

2. Для каждого образа (строки матрицы Ф) производим классификацию методом к -ближайших соседей по 64 сравнений с остальными образами.

3. Рассматривались значения к = 1,3,5,7.

к Число правильно распознанных образов j %

1 61 из 65 ! 93,84

3 62 из 65 1 95,38

5 63 из 65 1 96,92

7 63 из 65 | 96,92

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

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

Комплекс поддерживает следующие функции:

• ввод контрольных кругов;

• изображение жирных линий на растровых устройствах (дисплее);

• редактирование (перемещение центров и изменение радиусов контрольных кру! ов) жирной линии;

• построение огибающей (границы жирной кривой);

• раскраска жирной линии методом плавного перехода (перетекания) цветов и методом эталонной раскраски;

• получение из растрового бинарного изображения циркулярной фигуры с возможностью редактирования как отдельных контрольных кругов, так и жирной линии в целом (метод «вытягивания бус»);

• сравнение жирных линий и циркулярных фигур между собой;

• создание анимационных эффектов на основе морфинга жирных линий и циркулярных фигур.

Заключение содержит основные результаты диссертационного исследования.

Весь иллюстративный материал диссертации и автореферата был получен с использованием разработанного про!раммного комплекса.

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Л.М. Местецкий, А.Б. Семенов. Жирные линии на основе В-сплайнов Сложные системы: моделирование и оптимизация. Сборник научных трудов. Тверь, 2001.

2. Л.М. Местецкий, А.Б. Семенов. Преобразование цветных изображений на основе жирных В-сплайновых кривых. Труды 13 международной конференции ГРАФИКОН. Москва, 2003.

3. Л.М. Местецкий, А.Б. Семенов. Сравнение формы изображений на основе циркулярного разложения Труды 14 международной конференции ГРАФИКОН. Москва, 2004.

4. Л.М. Местецкий, А.Б. Семенов. Сравнение формы ладоней на основе жирных линий Труды 7-й международной конференции «Распознавание образов и анализ изображений: новые информационные технологии». Санкт-Петербург, 2004.

5. А.Б. Семенов. Жирные В-сплайновые кривые в задачах компьютерной графики и обработки изображений Труды 3-го международного практического семинара «Интегрированные модели и мягкие вычисления в искусственном интеллекте». Коломна, 2005.

6. L. Mestetskiy, A. Semenov. Palm shape comparison based on fat curves Pattern Recognition and Image Analysis, vol.15, #3, 2005.

Технический редактор A.M. Полякова Подписано в печать 8.08.2005. Формат 60 х 84 Vie-Бумага типографская № 1 Печать офсетная. Усл.печ л. 1,25. Уч.-изд л 1,1. Тираж 100 экз. Заказ № 343 Тверской государственный университет, Редакционно-издательское управление. Адрес: Россия. 170000, г. Тверь, ул. Желябова, 33 Тел. РИУ- (0822) 35-60-63.

p 1 5 1 6 2

РНБ Русский фонд

2006-4 11670

'Í

Г,

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОДЫ ПРЕДСТАВЛЕНИЯ ФОРМЫ ПЛОСКИХ ФИГУР.

1.1. Задачи анализа и синтеза формы плоских фигур.

1.2. Методы описания формы плоских фигур.

1.3. Методы анализа и преобразования формы плоских фигур.

1.4. Концепция жирных линий.

1.5. Выводы.

ГЛАВА 2. МАТЕМАТИЧЕСКАЯ ТЕОРИЯ ЖИРНЫХ В-СПЛАЙНОВЫХ КРИВЫХ.

2.1. Определение жирных линий.

2.2. Представление оси жирной линии обыкновенными В-сплайновыми кривыми.

2.3. Представление ширины жирной линии В-сплайновыми кривыми.

2.4. Вычисление границы жирной В-сплайновой кривой.

2.5. Локализация точки относительно жирной В-сплайновой кривой.

2.6. Интерполяция жирной В-сплайновой кривой.

2.7. Аппроксимация жирной В-сплайновой кривой.

2.8. Выводы.

ГЛАВА 3. ОПИСАНИЕ ФОРМЫ ОБЪЕКТОВ С ПОМОЩЬЮ ЖИРНЫХ В-СПЛАЙНОВЫХ КРИВЫХ.

3.1. Жирная линия как новый геометрический примитив.

3.2. Получение циркулярного разложения растрового бинарного образа.

3.3. Получение гранично-скелетного представления.

3.4. Аппроксимация гранично-скелетного представления циркулярной фигурой.

3.5. Программный комплекс и вычислительные эксперименты.:.

3.6. Выводы.:.

ГЛАВА 4. ДВУМЕРНАЯ ГРАФИКА НА ОСНОВЕ ЖИРНЫХ В-СПЛАЙНОВЫХ КРИВЫХ.

4.1. Раскраска жирной В-сплайновой кривой методом цветового перехода.

4.2. Раскраска жирной В-сплайновой кривой через циркулярные координаты.

4.3. Раскраска жирной В-сплайновой кривой через триангуляцию.

4.4. Преобразование цветных изображений с помощью жирных В-сплайновых кривых.

4.5. Анимация жирных линий на основе морфинга.

4.6. Выводы.

ГЛАВА 5. РАСПОЗНАВАНИЕ ФОРМЫ НА ОСНОВЕ ЖИРНЫХ В-СПЛАЙНОВЫХ КРИВЫХ.

5.1. Задача сравнения формы изображений.

5.2. Сравнение жирных линий.

5.3. Сравнение циркулярных разложений.

5.4. Сравнение формы ладоней на основе циркулярного разложения.

5.5. Выводы.

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

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

Известно также несколько математических моделей для непрерывного представления фигур. Наиболее распространенным является подход к описанию фигур путем задания границы плоского объекта. Граница в этом случае может представлять собой совокупность замкнутых простых непересекающихся линий (контуров). Эти линии описываются либо в параметрической форме непрерывной векторной функцией V(t) = (x(t)>y(t)),te[a,b\,V(a) = V(b), либо простыми многоугольниками, т.е. последовательностями вершин вида Р, =(лг,.,ys), i = l,.,iV, Pl = PN. Одним из главных достоинств граничного представления является возможность геометрических преобразований над всей фигурой: растяжение, сжатие, масштабирование, поворот. К тому же описание границы в параметрическом виде позволяет вычислять признаки, имеющие непрерывную природу: гладкость, кривизну и т.п. Граничное описание формы хорошо подходит для задач, связанных с использованием локальных свойств границы фигуры, но не вполне пригодно для исследования общей структуры объектов сложной формы в силу того, что довольно сложно получить информацию об интегральной структуре объекта из такого представления фигуры.

Наряду с граничным представлением известен неявный способ описания плоского объекта, который состоит в задании так называемой функции принадлежности (или характеристической функции), определенной для всех точек плоскости и принимающей значение 1 внутри или на границе фигуры и 0 вне нее. Этот подход удобен для прослеживания границы и для изображения фигуры на растровых устройствах (дисплей, принтер).

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

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

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

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

Целью диссертации является разработка нового математического . метода описания, анализа и преобразования формы плоских объектов, обеспечивающего большую гибкость и информативность в интересах повышения эффективности систем графики и машинного > зрения. Достижение цели обеспечивается разработкой новых математических моделей описания площадных фигур, численных методов аппроксимации и преобразования изображений с помощью предложенных моделей, создания комплекса программ для обоснования достоверности полученных щ результатов и возможностей их применения для решения практических задач. Таким образом, тема и содержание проводимого исследования соответствуют специальности 05.13.18 — математическое моделирование, численные методы и комплексы программ.

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

Рис. 1

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

Научной задачей является построение математического метода с численной его реализацией для аппроксимации с заданной точностью сложных изображений с помощью графических примитивов нового класса (жирных линий), обладающих существенными преимуществами перед известными в части анализа и синтеза изображений. Формально задача аппроксимации ставится следующим образом. Пусть В - множество плоских жирных линий определенного класса (в нашем случае это жирные Всплайновые кривые); Q - множество конечных объединений жирных линий к вида & = Уд, Д е В, i = к < оо так называемых циркулярных фигур. Пусть 1 а - плоская фигура, представленная в виде растрового бинарного изображения; /л(а,со) - мера близости объекта а и циркулярной фигуры с. Задача состоит в том, чтобы найти oeQ такую, что /л(а,а>) <е, где е наперед заданная точность аппроксимации. В качестве меры близости может выступать, например, хаусдорфово расстояние.

Решение научной задачи основывается на следующих идеях:

• Преобразование растрового бинарного изображения в непрерывное представление: граница исходного дискретного образа аппроксимируется многоугольной фигурой минимального периметра, разделяющей точки объекта и фона;

- строится непрерывный скелет полученной многоугольной фигуры как множество центров максимальных вписанных в фигуру кругов;

- вычисляется базовый скелет путем отсечения несущественных ветвей скелета (стрижка скелета);

- каждая отдельная ветвь скелета, представляющего собой планарный граф, аппроксимируется жирной линией.

• Описание жирных линий с помощью математического аппарата В-сплайнов. Такое представление позволяет строить, преобразовывать, анализировать плоские формы, описанные как объединение жирных линий (циркулярные фигуры).

• Построение, преобразование и анализ плоских фигур, описанных в виде объединения жирных линий (циркулярные фигуры).

• Сравнение формы плоских объектов через построение меры сходства жирных линий.

Новые научные результаты, выносимые на защиту:

• Математический метод представления жирных линий с помощью В-сплайнов третьего порядка. Существующие методы математического описания подобных геометрических объектов не предоставляют возможности для осуществления сложных не аффинных преобразований объектов, сохраняющих гладкость границы. В отличие от них предлагаемый метод позволяет довольно просто описывать такие преобразования;

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

• Метод и алгоритм сравнения формы изображений на основе циркулярного разложения бинарного образа. Предлагаемый подход основан на представлении исходных образов в виде совокупности жирных линий (циркулярное разложение) и сравнении их между собой. В качестве меры близости двух жирных линий при сравнении выступает площадь симметрической разности сравниваемых примитивов.

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

Научная новизна работы определяется:

• использованием для описания жирных линий математического аппарата В-сплайновых кривых третьего порядка;

• непрерывной аппроксимацией дискретных изображений с помощью таких кривых;

• алгоритмами построения, преобразования, визуализации и анализа плоских объектов, составленных из них.

Практическая значимость

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

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

Структура диссертации > ' .

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

5.5 Выводы

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

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

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

• скелетизация растрового изображения ладони;

• очистка скелета и идентификация пальцев руки;

• аппроксимация изображения ладони жирными линиями;

• построение характеристических функций пальцев руки;

• сравнение характеристических функций по критерию близости их графиков.

4. Метод сравнения и идентификации формы ладоней не требует жесткого позиционирования ладони на поле контроля. Возможен даже вариант развития метода, при котором не требуется контакта ладони с платформой.

5. Представлены результаты апробации разработанного метода на множестве прецедентов, включающим 65 изображений ладоней (13 • человек, по 5 изображений ладони каждого человека) и дающие : я процент правильно распознанных образов 96 процентов. Эксперименты показали, что метод идентификации личности по геометрическим характеристикам ладони с помощью жирных линий является перспективным для включения в промышленные системы биометрической идентификации.

Заключение

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

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

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

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

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

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

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

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

В рамках проводимого исследования и проверки достоверности получаемых результатов был разработан программный комплекс, алгоритмы и методы которого могут найти применение в качестве встраиваемых модулей (plug-in) в системах двумерной компьютерной графики, обработки и анализа изображений.

1. Blum Н. A transformation for extracting new descriptors of shape. W. Wathen-Dunn, ed., Models for perception of speech and visual form, MIT Press, 1967.

2. Britt J., Duynstee T. Professional Visual Basic 6 XML. Wrox Press Ltd. 2000.

3. Bulatov Y., Jambawalikar S., Kumar P., Sethia S. Hand recognition using geometric classifiers. 2002

4. Castelman K.R. Digital image processing. Prentice-Hall, 1996.

5. Choi H.I., Choi S.W., Moon H.P. Mathematical theory of medial axis transform //Pacific. J. of Math.- 1997.-Vol. 181, No. 1.-P.57-88.

6. Chua Y. Bezier brushstrokes. CAD, vol.22 (9), 1991.

7. Chung J., Ohnishi N. Chain of circles for matching and recognition of planer shapes. IDY97-52, 1997.

8. Collins C., Stephenson K. A Circle Packing Algorithm. Computational Geometry: Theory and Applications, 25,2003.

9. Costa L.F., Cesar R.M. Shape analysis and classification: theory and practice. CRC Press, 2001.

10. Cox M.G. The numerical evaluation of B-splines. Natioanl Physical * Laboratory DNAC 4,1971.11 .de Boor C. On calculation with B-splines. J. Approx. Theory, Vol. 6, 1972.

11. Ghosh P., Mudur S. The brush-trajectory approach to figure specification: some algebraic-solutions. ASM Trans, on graphics, vol.3 (2), 1984.

12. HaSIS A Hand Shape Identification System, http://bias.csr.unibo.it/research/biolab/hand.html.

13. Hertzman A. Painterly rendering with curved brush strokes of multiple sizes. Siggraph, 1998.

14. Hsu C.-C., Huang J.S. Partitioned Hough transform for ellipsoid detection. Pattern Recognition. Vol. 23,1990.

15. Hsu S.C., Lee I.H.H. Drawing and animation using skeletal strokes. In Proceedings of SIGGRAPH 1994, pp. 109-118, July 1994

16. Jain A. K., Duta N. Deformable matching of hand shapes for verification, Proceedings of IEEE International Conference on Image Prcoessing, October 25-28, Kobe, Japan, 1999.

17. Jain A. K., Ross A., and Prabhakar S. Biometrics-based Web Access, MSU Technical Report, TR98-33, 1998.

18. Jain A.K., Ross A. and Pankanti S. A Prototype Hand Geometry-based Verification System, 2nd Int'l Conference on Audio- and Video-based Biometric Person Authentication (AVBPA), Washington D.C., pp. 166-171, March 22-24, 1999.

19. Knuth D.E. METAFONT, A system for alphabet design, apart 3 of TeX and METAFONT: New directions in typesetting, American Mathematical Society and Digital Press, Bedford, Mass, 1979.

20. Lee D.T. Medial axis transformation of a planar shape // IEEE Trans. PAMI. 1982. -Vol. PAMI-4, No. 4. - P. 363-369.

21. Lee I.-K., Kim M.-S., Elber G. Planar curve offset based on circle approximation. To appear in CAD, 1996.26.bin Q., Rokne J. Fitting fat curves. Mathl. Comput. Modelling, Vol. 27(6), 1998.

22. Mestetskii L.M. Fat curves and representation of planar figures. Computers and Graphics, Vol. 24(1-2), 2000.

23. Nishita Т. Application of Bezier clipping method and their Java applets. Proc. Of SCCG98,1998

24. Nishita Т., Takita S., Nakamae E. A display algorithm of brush strokes using Bezier functions, 1993.

25. Pahm B. Expressive brush strokes. Graphical models and image processing, vol.53 (1), 1991.

26. Pavlidis T. A thinning algorithm for discrete binary images // CGIP. — 1980. Vol. 13. P.142-157.

27. Ramer U.E. An iterative procedure for the polygonal approximation of plane curves. Comput. Graphics Image Process, Vol.16 1972.

28. Ranjian V., Fournier A. Matching and interpolation of shapes using unions of circles. EUROGRAPHICS'96, Vol. 15(3), 1996.

29. Rodgers D.F., Fog N.G. Constrained B-spline curve and surface fitting. CADJ, Vol.21, 1989.

30. Ruprecht D., Muller H. Image warping with scattered data interpolation methods. Computer Graphics and Applications. 1995. <

31. Schneider P.J. An algorithm for automatically fitting digitized curves. Graphics Gems, A.S. Glassner ed., Academic Press, 1990.

32. Sebastian Т., Kimia B. Curves vs skeletons in object recognition. IEEE International Conference of Image Processing, 2001.

33. Su S., Xu Y-Q., Shum H-Y., Chen F. Simulating artistic brushstrokes using interval splines. 2000.

34. Wong H.T.F., Ip H.H.S. Virtual brush: a model-based synthesis of Chinese calligraphy. Computers and Graphics, Vol. 24, 2000.

35. Wu J., Leou J. New polygonal approximation schemes for object shape representation. Pattern recognition, Vol. 26,1993.

36. Yao C., Rokne J. Fat curves. Computer graphics forum, 10, 1991.

37. Younes L. Computable elastic distance between shapes. SIAM Journal on Applied Mathematics, 1995.

38. Zunkel R. Hand geometry based verification, in Biometrics: Personal Identification in Networked Society, A. Jain, R. Bolle and S. Pankanti (Eds), pp. 87-101, Kluwer Academic, 1998.

39. Архипов Г.И., Садовничий B.A., Чубариков B.H. Лекции по математическому анализу. М.: "Высшая школа", 1999.

40. Введение в контурный анализ и его приложения к обработке изображений. Под ред. Фурмана Я.А. М.: ФИЗМАТЛИТ, 2002.

41. Де Бор К. Практическое руководство по сплайнам. Москва, 1983.

42. Журавлев Ю.И. Непараметрические задачи распознавания образов. Избранные научные труды. М.,"Магистр", 1998.

43. Завьялов Ю.С., Квасов Б.И., Мирошниченко В.Л. Методы сплайн-функций. Москва, 1980.

44. Иванов Д., Кузьмин Е. Эффективный алгоритм построения остова растрового изображения // Труды межд. конф. Графикон-98, Москва,1998. С. 65-68.

45. Карр Д. Биометрические устройства новой волны. Открытые системы. LAN№ 12, 2001.

46. Катыс Г.П. Обработка визуальной информации. — М.: Машиностроение, 1990.

47. Короткий С. Введение в распознавание образов. Журнал Монитор, 8, 1994.

48. Кострикин А.И. Введение в алгебру Учебник для вузов. 2001.

49. Кузнецов И. Графика и 2Э-анимация. "Компьютер-ИНФО" № 3, 2000.

50. Курош А.Г. Курс высшей алгебры. Физматгиз, Москва, 1975.

51. Лагно Д., Соболев А. Модифицированные алгоритмы Форчуна и Ли скелетизации многоугольной фигуры // Труды межд. конф. "Графикон-2001", Нижний Новгород, 2001. С. 120-125.

52. Линейное и нелинейное программирование. Под общей редакцией проф. И.Н.Ляшенко. Киев, 1975.

53. Местецкий JI.M. Компьютерная графика на основе жирных линий. Труды международной конференции по компьютерной графике «Графикон-2001», Москва, МГУ, 2001.

54. Местецкий JI.M. Непрерывный скелет бинарного растрового изображения // Труды межд. конф. "Графикон-98", Москва, 1998.

55. Местецкий JI.M. Скелетизация многоугольной фигуры на основе обобщенной триангуляции Делоне. Программирование, №3, 1999.

56. Норден А.П. Краткий курс дифференциальной геометрии. Москва. 1958.

57. Павлидис Т. Алгоритмы машинной графики и обработки изображений. Москва, Радио и связь, 1986.

58. Препарата Ф., Шеймос М. Вычислительная геометрия: введение // М.: Мир, Москва, 1989.

59. Прэтт У. Цифровая обработка изображений. Кн. 1,2. — М.: Мир, 1982.

60. Рейер И.А. Методы анализа формы изображений на основе непрерывного граично-скелетного представления. * ВЦРАН, диссертация на соискание ученой степени кандидата технических наук, Москва, 2004.

61. Роджерс Д., Адаме Дж. Математические основы машинной графики. Москва, Мир, 2001.

62. Строзотт Т., Шлехтвег Ш. Нефотореалистичная компьютерная графика: моделирование, рендеринг, анимация. Кудиц-образ, 2005.

63. Ту Д., Гонсалес Р. Принципы распознавания образов. — М.: Мир, 1978.

64. Форсайт Д., Понс Ж. Компьютерное зрение. Современный подход. Москва: Вильяме, 2004.

65. Шикин Е.В., Плис А.И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. Москва, 1996.

66. ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

67. Л.М. Местецкий, А.Б. Семенов. Жирные линии на основе Б-сплайнов. Сложные системы: моделирование и оптимизация. Сборник научных трудов. Тверской государственный университет. 2001.

68. Л.М. Местецкий, А.Б. Семенов. Преобразование цветных изображений на основе жирных В-сплайновых кривых. Труды 13 международной конференции. ГРАФИКОН-2003, Москва.

69. Л.М. Местецкий, А.Б. Семенов. Сравнение формы изображений на основе циркулярного разложения. Труды 14 международной конференции. ГРАФИКОН-2004, Москва.

70. Л.М. Местецкий, А.Б. Семенов. Сравнение формы ладоней на основе жирных линий. Труды 7-й международной конференции «Распознавание образов и анализ изображений: новые информационные технологии», Санкт-Петербург, 2004.

71. А.Б. Семенов. Жирные В-сплайновые кривые в задачах компьютерной графики и обработки изображений. Труды 3-го ^международного практического семинара «Интегрированные модели и мягкие вычисления в искусственном интеллекте». Коломна, 2005.

72. L. Mestetskiy, A. Semenov. Palm shape comparison based on fat curves. Pattern Recognition and Image Analysis, vol.15, #3,2005.