Содержание к диссертации
ВВЕДЕНИЕ З
ГЛАВА 1. МЕТОДЫ ПРЕДСТАВЛЕНИЯ ФОРМЫ ПЛОСКИХ ФИГУР
А/. Задачи анализа и синтеза формы плоских фигур. 4 11
Методы описания формы плоских фигур 16
Методы анализа и преобразования формы плоских фигур 20
Концепция жирных линий 25
Выводы 36
ГЛАВА 2. МАТЕМАТИЧЕСКАЯ ТЕОРИЯ ЖИРНЫХ В-СПЛАЙНОВЫХ КРИВЫХ.
Определение жирных линии 37
Представление оси жирной линии обыкновенными В-сплайновыми кривыми.... 39
Представление ширины жирной линии В-сплайновыми кривыми 46
Вычисление границы жирной В-сплайновой кривой , 48
Локализация точки относительно жирной В-сплайновой кривой 55
Интерполяция жирной В-сплайновой кривой 60
Аппроксимация жирной В-сплайновой кривой 63
Выводы 67
ГЛАВА 3. ОПИСАНИЕ ФОРМЫ ОБЪЕКТОВ С ПОМОЩЬЮ ЖИРНЫХ В-
СПЛАЙНОВЫХ КРИВЫХ
Жирная линия как новый геометрический примитив 68
Получение циркулярного разложения растрового бинарного образа 72
Получение гранично-скелетного представления т 75
Аппроксимация гранично-скелетного представления циркулярной фигурой 78
Программный комплекс и вычислительные эксперименты : 83
Выводы,.,;. 88
ГЛАВА 4- ДВУМЕРНАЯ ГРАФИКА НА ОСНОВЕ ЖИРНЫХ В-СПЛАЙНОВЫХ
КРИВЫХ „ -
4А. Раскраска жирной В-сплайновой кривой методом цветового перехода 90
Раскраска жирной В-сплайновой кривой через циркулярные координаты 93
Раскраска жирной В-сплайновой кривой через триангуляцию 98
Преобразование цветных изображений с помощью жирных В-сплайновых кривых 102
Анимация жирных линий на основе морфинга 104
Выводы 106
ГЛАВА 5. РАСПОЗНАВАНИЕ ФОРМЫ НА ОСНОВЕ ЖИРНЫХ В-СПЛАЙНОВЫХ
КРИВЫХ ~ - -
Задача сравнения формы изображений 107
Сравнение октрных линий 108
Сравнение циркулярных разложений 112
Сравнение формы ладоней на основе циркулярного разложения 115
Выводы 120
ЗАКЛЮЧЕНИЕ 122
СПИСОК ЛИТЕРАТУРЫ ~ 124
Введение к работе
Предметом настоящего исследования является разработка математического метода описания двумерных геометрических объектов сложной формы непрерывными графическими примитивами, называемыми жирными линиями (объединение однопараметрического семейства кругов переменного радиуса с центрами на гладких кривых) и компьютерное исследование его характеристик и свойств- Такой метод представления плоских фигур дает возможность осуществления широкого класса преобразований образа, сохраняющих непрерывность границы и внутренности плоского объекта.
В задачах компьютерной графики и машинного зрения плоские фигуры описываются как в дискретном, так и непрерывном виде. Дискретное представление — это бинарное растровое изображение (матрица) в виде точек одного цвета на фоне точек другого, например черное на белом. Преимущество дискретного подхода состоит в том, что большая часть алгоритмов растеризации машинной графики, алгоритмов ввода, сканирования фото и видеоинформации ориентирована именно на такой способ описания плоских фигур, В качестве недостатков можно отметить сложность геометрических преобразований формы фигуры и большую потребность в машинной памяти для хранения таких изображений.
Известно также несколько математических моделей для непрерывного
представления фигур. Наиболее распространенным является подход к
описанию фигур путем задания границы плоского объекта. Граница в этом
случае может представлять собой совокупность замкнутых простых
непересекающихся линий (контуров). Эти линии описываются либо в
параметрической форме непрерывной векторной функцией
V(t) = (дг(ґ)*;КО)*t є la*b\* У(аУ = УФ) у либо простыми многоугольниками, т.е. последовательностями вершин вида Ps =(xiJyi\i^\t..,iN^Pl=PNt Одним из
главных достоинств граничного представления является возможность геометрических преобразований над всей фигурой: растяжение, сжатие^
масштабирование, поворот, К тому же описание границы в параметрическом виде позволяет вычислять признаки, имеющие непрерывную природу: гладкость, кривизну и т.п. Граничное описание формы хорошо подходит для задач, связанных с использованием локальных свойств границы фигуры, но не вполне пригодно для исследования общей структуры объектов сложной формы в силу того, что довольно сложно получить информацию об интегральной структуре объекта из такого представления фигуры.
Наряду с граничным представлением известен неявный способ описания плоского объекта, который состоит в задании так называемой функции принадлежности (или характеристической функции), определенной для всех точек плоскости и принимающей значение 1 внутри или на границе фигуры и 0 вне нее. Этот подход удобен для прослеживания границы и для изображения фигуры на растровых устройствах (дисплей, принтер).
Для описания сложных форм используют представление в виде
объединения конечного числа более простых примитивов, обычно
многоугольников - полигональное представление. Однако оно не подходит
для описания составных объектов с гладкой границей. Описание формы с
помощью многоугольников позволяет вычислять такие характеристики
фигуры, как площадь, периметр, округлость (отношение площади к
периметру).
« В задачах, связанных с распознаванием и сравнением объектов,
имеющих сложную форму, применяют подход, основанный на построении и топологическом анализе серединных осей фигуры - так называемого скелета. Скелет плоской фигуры представляет собой множество центров максимальных вписанных в фигуру кругов. Скелетное представление более пригодно для исследования интегральной структуры объекта по сравнению с граничным или неявным представлениями, однако скелет не предоставляет возможности анализа ширины элементов фигуры и выполнения преобразований, связанных с изменением ширины отдельных элементов изображения.
*
Задача преобразования цветных растровых изображений представляет особый интерес в области обработки изображений и компьютерной графики. Существующие методы в своей основе используют подход, основанный на построении триангуляционной сетки на изображении с последующим ее преобразованием. Данный способ не предоставляет простой возможности для осуществления сложных не аффинных преобразований над цветными изображениями в силу того, что изменения (деформации триангуляционной сетки) носят локальный характер.
Недостатки традиционных методов представления формы приводят к необходимости их дальнейшего развития в интересах разработки современных систем компьютерной графики, визуализации и систем машинного зрения, что обосновывает актуальность темы исследования.
Целью диссертации является разработка нового математического
. метода описания, анализа и преобразования формы плоских объектов,
обеспечивающего большую гибкость и информативность в интересах
.'. повышения эффективности систем графики и машинного зрения.
Достижение цели обеспечивается разработкой новых математических
моделей описания площадных фигур, численных методов аппроксимации и
преобразования изображений с помощью предложенных моделей, создания
комплекса программ для обоснования достоверности полученных
«і результатов и возможностей их применения для решения практических
задач. Таким образом, тема и содержание проводимого исследования
соответствуют специальности 05.13.18 — математическое моделирование,
численные методы и комплексы программ.
Подход предлагаемый в диссертационной работе к разработке математического метода, основан на идее представления плоских фигур с помощью нового класса графических примитивов - так называемых жирных линий. Жирная линия представляет собой след от перемещения окружности переменного радиуса вдоль гладкой кривой (рис, 1).
Рисі
Жирные зшюїи позволяют описывать объекты сложной формы в виде, удобном іи\я синтеза, преобразования и анализа как общей структуры объекта, так и его лоюшьных свойств, ішїю*гая ширину отдельных элементов. В качестве матемштічеекого ашвдрата я-ш иаисания жирных линий предлагается использовать В-силайны третьей степени.
Наочніш ШЗШЗШ является построение математического методе с
численной его реализацией для аппроксимации с заданной точностью сложных изображений с помощью графических примитивов пового класса (жирных линий), обладающих существенными преимуществами перед известными в части анализа и синтеза шображенйй, Формшшно задача аппроксимации ставится следующим образом. Пусть В - множество плоских жирных линий определенного класса (в пашем случае это онлайновые кривые); О - множество конечных объ
m=*Г)0{! Д fS,r ї,.,.Д;ft <се так называемых циркулярных фиіур. і Іусть
і ї
а - плоская фигура, представленная в виде растрового бинарного изображения; /НАчЩ - мера близости объекта а и циркулярной фигуры с. Задана состоит в том, чтобы найти &ъП такую, что р(а*ш)<ъ\ где s -
наперед заданная точность аппроксимации. В качестве меры близости может выступать, например, хаусдорфово расстояние.
Решение научной задачи основывается на следующих идеях:
Преобразование растрового бинарного изображения в непрерывное
представление:
граница исходного дискретного образа аппроксимируется многоугольной фигурой минимального периметра, разделяющей точки объекта и фона;
строится непрерывный скелет полученной многоугольной фигуры как множество центров максимальных вписанных в фигуру кругов;
вычисляется базовый скелет путем отсечения несущественных ветвей скелета (стрижка скелета);
каждая отдельная ветвь скелета, представляющего собой шшнарный граф, аппроксимируется жирной линией.
Описание жирных линий с помощью математического аппарата В-сплайнов. Такое представление позволяет строить, преобразовывать, анализировать плоские формы, описанные как объединение жирных линий (циркулярные фигуры).
Построение, преобразование и анализ плоских фигур, описанных в виде объединения жирных линий (циркулярные фигуры).
Сравнение формы плоских объектов через построение меры сходства жирных линий.
Новые научные результаты, выносимые на защиту:
Математический метод представления жирных линий с помощью В-
сплайнов третьего порядка. Существующие методы математического
описания подобных геометрических объектов не предоставляют
возможности для осуществления сложных не аффинных
преобразований объектов, сохраняющих гладкость границы. В отличие
от них предлагаемый метод позволяет довольно просто описывать
такие преобразования;
Метод аппроксимации с заданной точностью дискретных изображений непрерывными объектами, составленными из жирных линий. Метод позволяет осуществлять широкий класс сложных преобразований над такими изображениями, включая возможность создания анимации, путем аппроксимации образов циркулярными фигурами и последующего морфинга жирных линий;
Метод и алгоритм сравнения формы изображений на основе циркулярного разложения бинарного образа. Предлагаемый подход основан на представлении исходных образов в виде совокупности жирных линий (циркулярное разложение) и сравнении их между собой* В качестве меры близости двух жирных линий при сравнении выступает площадь симметрической разности сравниваемых примитивов.
Научная значимость исследования состоит в разработке и обосновании нового математического метода описания формы плоских фигур, заданных в виде цифровых: описаний, непрерывными графическими примитивами.
Научная новизна работы определяется:
использованием для описания жирных линий математического аппарата В-сплайновых кривых третьего порядка;
непрерывной аппроксимацией дискретных изображений с помощью таких кривых;
алгоритмами построения, преобразования, визуализации и анализа плоских объектов, составленных из них.
Практическая значимость
Разработанные методы описания плоских фигур позволяют включить новые эффективные инструменты в системы компьютерной графики, использовать их в системах научной визуализации. Полученные результаты диссертационной работы могут найти применение в программных комплексах двумерной векторной графики (например, CorelDraw) в качестве
встраиваемых модулей. Новый эффективный метод построения информативного признакового описания плоских фигур является полезными для включения в системы преобразования, распознавания и анализа формы изображений. Разработанный комплекс программ для проверки и обоснования полученных научных результатов может послужить прототипом инструментов в системах компьютерной графики, обработки и анализа изображений- Разработанное программное обеспечение может быть использовано для создания системы биометрической идентификации личности по форме ладони.
Обоснованность и достоверность научных положений, выводов и
результатов подтверждается корректным использованием математического
аппарата В-сплайновых кривых для описания жирных линий, строгими
математическими доказательствами, программной реализацией и
вычислительными экспериментами, а также успешным использованием при
решении практических задач, > .:
Структура диссертации * +>
Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы. В первой главе проводится обзор математических методов описания плоских фигур и жирных линий. Определяется круг задач и приложений, в которых могут быть использованы эти геометрические примитивы, осуществляется постановка научной задачи, раскрывается структура метода ее решения и исследования. Во второй главе описывается математическая теория жирных линий, вводятся определения и исследуются общие свойства жирных кривых. Рассматриваются задачи подгонки жирных линий и локализации точки относительно жирной линии, В третьей главе рассматривается задача описания формы объектов с помощью жирных линий, построения сложных форм из них, исследуется подход к аппроксимации с заданной точностью дискретных образов с помощью жирных линий. Четвертая глава посвящена приложению аппарата жирных В-сплайновых кривых в задачах двумерной графики. Рассматривается задача
преобразования цветных (текстурных) образов и задача анимации на основе жирных линий, В пятой главе исследуется вопрос использования жирных линий для построения меры сходства формы объектов. В качестве применения рассматривается приложение к задаче биометрической идентификации личности по форме ладони. В заключении подводятся итоги работы. Диссертация содержит 129 страниц машинописного текста, 81 рисунок. Список литературы включает 76 наименований.
Апробация. Представленные в работе результаты докладывались и обсуждались на 13-й и 14-й международных конференциях по компьютерной графике и машинному зрению «Графикой» (Москва 2003, 2004 года), 7-й международной конференции «Распознавание образов и анализ изображений» (Санкт-Петербург, 2004 год), 3-м международном практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2005 год), научных семинарах факультета ПМиК ТвГУ,
По теме диссертации опубликовано 6 работ [71-76], достаточно полно отражающих ее содержание, включая 4 статьи в отечественных журналах и трудах международных конференций.
Внедрение результатов. Выносимые на защиту методы были реализованы, исследованы и использованы в рамках проектов Российского Фонда фундаментальных исследований (РФФИ): 02-01-00667 «Дискретно-непрерывные преобразования формы геометрических объектов в задачах обработки и анализа изображений», 04-01-08058 «Анализ и классификация формы изображений в задачах биометрической идентификации», 05-01-00542 «Методы распознавания формы изображений на основе дискретно-непрерывных преобразований».
