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

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

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

Известно также несколько математических моделей для непрерывного представления фигур. Наиболее распространенным является подход к описанию фигур путем задания границы плоского объекта. Граница в этом случае может представлять собой совокупность замкнутых простых непересекающихся линий (контуров). Эти линии описываются либо в параметрической форме непрерывной векторной функцией 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) в системах двумерной компьютерной графики, обработки и анализа изображений.