Содержание к диссертации
Введение
Глава 1. Исследование функций расстояния в n-мерном пространстве -17
1.1. Постановка задачи 17
1.2. Основные понятия и определения. 20
1.3. Множества Вороного 22
1.4. Исследование конструктивных операций 27
1.5. Беззнаковые функции расстояния для комбинированных множеств .29
1.6. Знаковые функции расстояния для комбинированных множеств 33
1.7. Дифференциальные свойства функций расстояния 35
1.8. Функции верхнего расстояния 37
1.9. Примеры функций расстояния в n-мерном пространстве 42
1.10. Выводы 45
Глава 2. Построение функций расстояния для множеств на плоскости ..46
2.1. Постановка задачи 46
2.2. Функции расстояния для комбинированных множеств на плоскости ..48
2.3. Алгебраические функции расстояния 58
2.4. Функции расстояния для кривых второго порядка 68
2.5. Численно-аналитические функции расстояния 72
2.6. Функции верхнего расстояния на плоскости 75
2.7. Выводы 77
Глава 3. Построение функций расстояния для множеств в пространстве
3.1. Постановка задачи 78
3.2. Преобразования функций расстояния, связанные с трансформациями множеств в пространстве 79
3.3. Функции расстояния для плоских линий в пространстве 82
3.4. Функции расстояния для поверхностей 85
3.5. Функции расстояния для участков поверхностей 88
3.6. Функции расстояния для комбинированных множеств в пространстве 93
3.7. Функции верхнего расстояния в пространстве 95
3.8. Выводы 98
Глава 4. Применение функций расстояния в задачах анализа и синтеза изображений ...99
4.1. Постановка задачи 99
4.2. Визуализация геометрических объектов с использованием функций расстояния 102
4.3. Распознавание изображений с помощью функций расстояния 105
4.4. Обобщение преобразования Хафа 108
4.5. Применение функций расстояния в задачах робототехники 119
4.6. Выводы 127
Заключение 128
Литература 129
- Беззнаковые функции расстояния для комбинированных множеств
- Функции расстояния для комбинированных множеств на плоскости
- Преобразования функций расстояния, связанные с трансформациями множеств в пространстве
- Визуализация геометрических объектов с использованием функций расстояния
Введение к работе
Обработка графической информации1 является одной из основных об-ластей деятельности практически любой компьютерной системы . Это обусловлено тем, что, во-первых, представление информации в графическом виде позволяет организовать эффективное человеко-машинное взаимодействие3 [1], так как такого рода информация значительно проще воспринимается людьми [2], во-вторых, при решении достаточно сложных задач автономная компьютерная система выступает в качестве замены человека и поэтому обычно получает и обрабатывает визуальную информацию. К таким интеллектуальным [3] задачам относятся анализ аэрофотоснимков [4], визуальный контроль трафика движения автотранспорта [5, 6], навигация мобильных роботов [4] и многие другие [7, 8].
Устройства ввода графической информации в компьютерную систему [9], такие как сканеры, фото и видеокамеры, а также устройства вывода, такие как дисплеи и принтеры, обуславливают форму представления графической информации в вид изображений [10]. С математической точки зрения, изображение является матрицей, элементы которой в двумерном случае называются пикселями, а в трёхмерном4 — векселями. В простейшем случае пиксель принимает значение «1», если он соответствует точке изображённого объекта, и значение «0», если не соответствует. Эти изображения называются бинарными [10]. Существуют и другие виды изображений [11], например, полутоновые, в которых пиксель принимает значения, определяющие яркость соответствующей точки изображённого объекта. Отсюда, имеет смысл
Здесь под графической понимается информация, представленная в виде фотографий, рисунков и диаграмм.
2 Компьютерной будем называть любую вычислительную, информационную или управляющую систему,
решающую достаточно сложные задачи.
3 Обратим внимание на то, что практически все современные операционные системы имеют графический
интерфейс [12]..
4 Примерами устройств ввода трёхмерных изображений являются томографические, магнитно-резонансные
и ультразвуковые медицинские сканеры [4].
говорить о геометрической информации, представленной бинарным изображением, так как оно определяет только форму и положение соответствующего объекта5, который в этом случае называется геометрическим объектом6 [13].
Следует отметить, что изображения являются далеко не единственным способом представления геометрической информации. Это связано с тем, что в большинстве случаев рассматриваются трёхмерные геометрические объекты, а использование трёхмерных изображений зачастую не выгодно уже из-за того, что они занимают колоссальные объёмы памяти.
Существуют исследования [14, 15], посвященные теории представления геометрической информации, в соответствии с которыми, метод представления информации сопоставляет каждому допустимому геометрическому объекту его модель. Модель - это выражение, составленное из символов некоторого алфавита в соответствии с определёнными синтаксическими правилами. Метод представления информации должен обладать свойствами:
а) полноты, т.е. моделировать все интересуемые виды геометрических объ
ектов;
б) адекватности - любая модель должна соответствовать некоторому реаль
ному геометрическому объекту;
в) однозначности - любой модели должен соответствовать единственный
объект;
г) уникальности — любому допустимому объекту должна соответствовать
единственная модель;
Обычно полагают, что геометрическая информация является частью графической. В частности полутоновое изображение представляет именно графическую информацию, так как определяет кроме геометрии изображённого объекта его яркость. Существует большое количество методов преобразования полутоновых изображений в бинарные [11].
* С математической точки зрения геометрический объект может быть определён как множество точек в евклидовом пространстве, поэтому в диссертационной работе не делается различий между понятиями «геометрический объект» и «множество точек».
д) краткости - модель должна представлять собой достаточно простое выра
жение;
е) эффективности - должны существовать эффективные алгоритмы созда-
ния, обработки и визуализации моделей.
Наиболее известными методами представления геометрической информации являются [15, 16]:
а) полигональное представление — представление в виде аппроксимации по
верхности геометрического объекта многогранниками;
б) конструктивная геометрия, создающая геометрические объекты из прими
тивов (кубов, сфер, конусов и т.п.) с помощью теоретико-множественных
операций, таких как пересечение, объединение и вычитание;
в) краевое представление, определяющее топологию объекта путём задания
его клеточного разбиения [17].
Полигональное представление отличается наличием крайне эффектов-ных с вычислительной точки зрения алгоритмов визуализации , но обладает и большим количеством недостатков:
а) применяется для описания только трёхмерных объектов;
б) форма объектов определяется приближённо9 [18];
в) практически не приспособлено для описания объектов, изменяющих свою
форму;
г) сложно решается задача обнаружения столкновений [19] при моделирова
нии динамических сцен;
д) конструирование моделей непосредственно в полигональном виде крайне
неудобно.
Здесь под визуализацией модели понимается получение изображения соответствующего объекта, прежде всего, чтобы отобразить его на экране дисплея или напечатать на принтере.
8Немаловажным является и тот факт, что большинство современных видеоадаптеров на аппаратном уровне решает часть проблем, связанных с визуализацией полигональных моделей [20].
9 Приближённость описания объектов эффективно маскируется различными методами наложения текстур и теней [21].
Конструктивная геометрия и краевое представление отличаются достаточным удобством при моделировании, но имеют не очень эффективные методы визуализации [15].
В виду того, что каждый из методов имеет определённые недостатки, существует большое количество алгоритмов преобразования конструктивных моделей в краевые [22, 23, 24, 25] и наоборот [22], а также тех и других в краевое представление [26].
В настоящее время не прекращаются попытки разработать более эффективные методы представления геометрической информации. При этом основные усилия сконцентрированы на моделировании сглаженных объектов [27] и объектов нерегулярной формы10, таких как горы, шерсть, камни, ракушки и т.п. В числе этих методов — суперквадрики [18], мягкие объекты [28], капельные объекты [29], обобщённые цилиндры [30] и свёрточные поверхности [31]. Основные требования, предъявляемые к таким методам представления информации, - это максимальная полнота и эффективность визуализации [32].
Обратим внимание на то, что все эти методы определяют геометрические объекты с помощью неявно заданных функций [33], а именно функций, принимающих отрицательные значения внутри описываемого геометрического объекта и положительные - снаружи. В результате существует большое количество работ [32], посвященных разработке эффективных методов визуализации неявно заданных функций, как с учётом особенностей конкретных моделей, так и без их учёта. Метод преобразования неявных функций в полигональное представление [26] в данном случае практически не применим из-за нерегулярной формы описываемых объектов, и фактически единственным методом визуализации таких неявно заданных функций является метод трассировка лучей [32], заключающийся в определении координат
Все стандартные методы геометрического моделирования предназначены для описания регулярных объектов, а именно объектов ограниченных квадратичными или кубическими поверхностями.
первой от наблюдателя точки пересечения визуализируемого объекта с заданным лучом.
Метод трассировки лучей позволяет визуализировать с заданной точностью сцены, содержащие полупрозрачные объекты, в условиях множественного отражения света. Обратной стороной таких возможностей является то, что алгоритмы трассировки лучей являются одними из самых неэффективных с вычислительной точки зрения, если не используются параллельные вычисления. Практически все усовершенствования метода трассировки лучей применительно к произвольным неявным функциям заключаются в оценке производных визуализируемой функции. На этом принципе основаны такие известные методы как Липшицев [34] и интервальный [35].
Наиболее эффективным методом можно признать такое обобщение липшицева метода как трассировка сфер Джона Харта [36]. Он использует понятие так называемой знаковой функции расстояния, т.е. функции, определяющей евклидово расстояние от данной точки пространства до ближайшей точки на описываемом ею объекте. Но, так как построение таких функций для сложных объектов - нетривиальная задача, то Джон Харт использовал понятие ограничивающей знаковой функции расстояния, возвращающей значения меньшие либо равные реальному расстоянию до объекта. Так как в алгоритме трассировки сфер функции расстояния рассчитываются преимущественно в точках вне объектов, то операции Ричи [37], используемые при формировании конструктивных моделей, позволяют описывать объекты с помощью ограничивающих функций расстояния. Как доказано в работе [36], сходимость метода трассировки сфер линейная, а в лучшем случае — квадратичная. Скорость визуализации достаточно сильно зависит от точности оценки функции расстояния. Более того, им было показано, что с помощью этого метода можно избавиться такого от такого неприятного эффекта трассировки лучей, как появление зубчатости на гранях изображённых геометрических объектов.
Кроме того, что моделирование с помощью функций расстояния позволяет разрабатывать эффективные алгоритмы визуализации, такие модели обладают ещё одной замечательной особенностью. В отличие от подавляющего большинства методов представления геометрической информации11, функции расстояния способны корректно моделировать геометрические объекты, содержащие компоненты различной размерности [38], при этом существуют алгоритмы визуализации таких объектов [39], основанные на методе трассировки лучей.
Следует отметить, что функции расстояния не являются принципиально новым математическим объектом. В частности, понятие функций расстояния используется при построении свёрточных поверхностей [31] и обобщённых цилиндров [30].
Кроме того, функция расстояния широко используется в задачах обработки изображений. Прежде всего, это следующие задачи.
Выделение остова [40], часто применяемое при распознавании абстрактных двумерных объектов, таких как буквы, цифры и т.п.
Построение дистантных изображений [41], использующихся, например, при сравнении изображений.
Дистантные изображения формируются либо с помощью эвристических алгоритмов фильтрации изображений [41], либо путём решения так называемого уравнения эйконала [42, 43], которое является дифференциальным уравнением в частных производных. Решением уравнения эйконала и является функция расстояния. Данные методы весьма эффективны, но не решают проблему построения исходного бинарного изображения, задающего начальные условия для уравнения эйконала или алгоритма фильтрации. Эта про-
" Все рассмотренные ранее методы представления геометрической информации позволяют корректно моделировать только так называемые твёрдые тела [14], одной из особенностей которых является то, что это п-мерные [44] тела в n-мерном пространстве, и они не содержат элементов размерности меньше п. 12 Выделение остова заключается в утончении изображённых объектов.
11 Каждый пиксель дистантного изображения принимает значение равное расстоянию до ближайшей точки соответствующего геометрического объекта.
блема решается путём создания и визуализации модели геометрического объекта, например, с помощью функции расстояния.
Дистантные изображения являются мощным инструментом для сравнения различных изображений [41], построения непрерывных трансформаций одного изображения в другое [45], выделения остова [40] и построения эквидистантных поверхностей [46]. Дистантные изображения преимущественно используются при распознавании изображений.
Если же рассмотреть собственно задачу распознавания изображений, то обнаруживается следующий факт. Существует стандартный подход к определению положения и размеров изображённого объекта по его параметризованной модели - метод оценки параметров модели со среднеквадратичным критерием [47]. Как было показано в исследовании [47], если параметризованная модель задаётся функцией, фактически являющейся функцией расстояния, то параметры модели будут определены наиболее быстро и точно.
В присутствии сильного шума на изображениях применяются робаст-ные методы оценки параметров, например, метод М-оценок [47]. Анализ используемого в нём критерия близости [47] также показывает, что для него желательно описание объекта в виде функции расстояния. Существуют и конкретные работы, посвященные распознаванию геометрических объектов по их функциям расстояния [48].
Таким образом, задача определения функций расстояния для различных геометрических объектов является крайне актуальной. Рассмотрим публикации, посвященные выводу функций расстояния для конкретных геометрических объектов. Во-первых, это работа Дж. Харта о методе трассировки сфер [36], где были получены приближённые функции расстояния для различных тел и их объединений. Во-вторых, это работа В.Л. Рвачёва [49], посвященная теории R-функций. В ней автором было введено понятие беззнаковой функции расстояния и исследованы её свойства. Также была получена схема записи функций расстояния для фигур, представляющих собой конечное число отрезков прямых и дуг окружностей на плоскости. Им же было
введено и исследовано понятие функции верхнего расстояния, определяющей евклидово расстояние от точки пространства до наиболее удалённой точки объекта. Существуют также работы, связанные с построением эвристических методов вычисления расстояний до многогранников [50]. И, наконец, определение расстояния до ближайшей точки на множестве является одной из основных задач вычислительной геометрии [51]. К сожалению, традиционно в качестве множеств, до которых определяется расстояние, выступают совокупности изолированных точек. При этом задача сводится к построению диаграмм Вороного, разделяющих пространство на многогранники Вороного [52], в приделах которых расстояние минимально до конкретной точки из рассматриваемого множества точек. Однако существуют работы, посвященные построению диаграмм Вороного для множеств, содержащие отрезки кривых [53].
Таким образом, актуальная задача записи функций расстояния в виде некоторых алгебраических выражений для объектов, более сложных, чем многогранники в пространстве, в настоящее время не решена.
Цель работы. Целью настоящей работы является разработка метода, позволяющего записывать функции расстояния для достаточно сложных двумерных и трёхмерных объектов, а также построение на его основе эффективных систем визуализации и распознавания изображений.
В соответствии с поставленной целью задачами диссертационного исследования являются:
Разработка методов построения функций расстояния для достаточно сложных двумерных и трёхмерных объектов.
Определение условия, при которых функции расстояния могут быть представлены в виде алгебраических выражений с использованием конструктивных операций Ричи.
Разработка и исследование методов визуализации геометрических моделей, заданных функцией расстояния.
Разработка и исследование методов распознавания с использованием функций расстояния.
Разработка обобщения преобразования Хафа для анализа сцен сложных объектов с использованием функций расстояния.
Структура диссертации. Материалы диссертационной работы распределены по главам в соответствии с перечисленными задачами.
Первая глава посвящена разработке метода записи функций расстояния для множеств bR". В начале главы вводится и исследуется понятие множества Вороного, обобщающего понятие области Дирихле. Затем анализируются свойства неявных функций, формируемых с помощью операций min(x,j>)
и max (*,>>). Определяются условия, при которых эти функции являются
функциями расстояния. Вводятся понятия комбинированного и разделяющего множеств. В результате разрабатываются оригинальные схемы записи знаковых и беззнаковых функций расстояния для объединения и пересечения множеств. Также формулируются условия для записи функций расстояния в виде алгебраических выражений, использующих конструктивные операции Ричи. Далее проводится анализ дифференциальных свойств функций расстояния. Выводятся выражения для вычисления частных производных различных порядков от функций расстояния, соответствующих комбинированным множествам. Исследуются свойства функций верхнего расстояния, разрабатываются методики их вычисления. В заключение выводятся формулы для вычисления знаковых и беззнаковых функций расстояния, соответствующих множествам изолированных точек, шарам, сферам, плоскостям и полупространствам в пространстве R".
Вторая глава посвящена записи функций расстояния для множеств на плоскости. В начале главы определяются условия, которым должна удовлетворять пара точек на линии для того, чтобы они образовывали разделяющее множество. Разрабатывается методика компактной записи знаковых и беззнаковых функций расстояния с помощью таблиц и схем комбинирования.
Приводятся примеры вычисления функций расстояния для различных комбинированных множеств на плоскости. Также выводятся функции расстояния для отрезка прямой и дуги окружности в виде алгебраического выражения с использованием конструктивных операций Ричи. Далее рассматриваются вопросы записи функций расстояния для различных некомбинированных множеств на плоскости. Доказывается, что среди функции от двух переменных, относящихся как к классу целых рациональных функций, так и к некоторым более широким классам функций, нет функций расстояния кроме тех, которые соответствуют точке, кругу, прямой и полуплоскости. Рассматриваются вопросы получения функций расстояния для кривых второго порядка, и выводится формула для вычисления расстояния до параболы. Даются рекомендации по оптимизации вычисления функций расстояния для кривых Безье. В заключение приводятся примеры записи функций верхнего расстояния для комбинированных множеств на плоскости.
В третьей главе определяются функции расстояния для трёхмерных тел, лежащих в некоторой плоскости, тел вращения и цилиндрических тел. Определяются разделяющие подмножества для такого рода множеств. Выводятся функции расстояния для прямых и окружностей в пространстве, а также для тора, цилиндра и конуса, трактуя их как плоские тела, цилиндрические тела или тела вращения. В результате получаются выражения для вычисления функций расстояния для трёхмерных комбинированных множеств, в которых участки поверхности образованы плоскостями, сферами, торами, цилиндрическими или коническими поверхностями, и ограничены контурами, состоящими из отрезков прямых и дуг окружностей, а также отрезков эллиптических кривых. Приводятся примеры записи функций расстояния и функций верхнего расстояния для комбинированных множеств в пространстве.
В четвёртой главе диссертационной работы рассматриваются вопросы практического применения функций расстояния. Демонстрируется тот факт, что многие геометрические объекты, определённые неявно заданной функци-
ей, могут быть визуализированы с приемлемой точностью только, если эта функция является функцией расстояния. Показывается, что алгоритмы визуализации, использующие функции расстояния, превосходят по вычислительной эффективности стандартные алгоритмы визуализации неявно заданных функций. Рассматривается метод распознавания путём идентификации параметров моделей, дающий наилучшие результаты при использовании функций расстояния в качестве параметризованных функций. Демонстрируется его высокая эффективность. Даётся оригинальная интерпретация метода преобразования Хафа, на базе которой проводится обобщение преобразования Хафа для распознавания произвольных геометрических объектов, заданных функциями расстояния. Предлагается соответствующий алгоритм. Разрабатываются рекомендации для записи функций расстояния, соответствующих эквидистантным поверхностям и сглаженным объектам. Проводится синтез управления мобильным роботом в общем виде с целью движения его вдоль кривой, заданной функцией расстояния.
Основные результаты работы. При решении поставленных в диссертационной работе задач получены следующие новые научные результаты, которые выносятся на защиту:
Методы построения знаковых и беззнаковых функций расстояния, а также функций верхнего расстояния для комбинированных множеств в п-мерном пространстве.
Условия, при которых беззнаковые функции расстояния представляются в виде алгебраических выражений с использованием конструктивных операций Ричи.
Методика записи функций кратчайшего и верхнего расстояния для класса двумерных и трёхмерных множеств, ограниченных квадратичными линиями и поверхностями.
Обобщение преобразования Хафа для анализа сцен сложных объектов с использованием функций расстояния.
Практическая ценность и внедрение. Разработанный математический аппарат представления геометрической информации может применяться для построения систем конструирования и распознавания изображений, навигации мобильных роботов, обнаружения столкновений.
На основании теоретических результатов диссертационной работы было создано программное обеспечение на языке Borland Delphi для конструирования моделей сложных объектов в виде унифицированных файлов моделей, а также конструирования и исследования систем распознавания изображений, планирования траектории движения роботов, обнаружения столкновений. Файлы моделей могут использоваться сторонними системами обработки изображений, работающими на различных аппаратно-программных платформах.
На языке Java создано программное обеспечение исследовательской системы распознавания малоразмерных зашумленных изображений с помощью разработанных моделей геометрических объектов. В универсальных системах математических исследований Maple и Mathcad разработаны подсистемы анализа геометрических моделей, обработки и распознавания изображений.
На основе функций расстояния было разработано программное обеспечение для распознавания низкокачественных изображений номерных знаков движущихся вагонов.
Апробация работы. Основные положения и результаты работы представлялись и обсуждались на Всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной и управленческой деятельности», Таганрог, 6-8 октября 1998 г.; Международной научно-технической конференции «Интеллектуальные многопроцессорные системы» (ИМС-99), Таганрог, Россия, 1-5 сентября 1999 г.; 1-ой Всероссийской научно-технической конференции «Измерения, автоматизация и моделирование в промышленности и научных исследованиях» (ИАМП-2000), Бийск, 8-9 июня 2000 г.; Международной научной конференции «Искусст-
венный интеллект - 2000» (ИИ-2000), п. Кацивели, Крым, Украина, 11-16 сентября 2000 г.; 5-ой Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (КРЭС-2000), Таганрог, 12-13 октября 2000 г.; 1-ом Всероссийском симпозиуме по прикладной и промышленной математике (осенняя сессия), Сочи, 1-6 октября 2000 г.; 7-ой Национальной конференции по искусственному интеллекту с международным участием (КИИ-2000), Переславль-Залесский, 24-27 октября 2000 г.; 3-ей Международной конференции «Цифровая обработка сигналов и её применение» Москва, Россия, 29 ноября-1 декабря 2000 г.; 6-ой Международной конференции по управлению, автоматизации, робототехнике и машинному зрению, Сингапур, 5-8 декабря 2000 г.; Научной сессии МИФИ-2001, Москва, 22-26 января 2001 г; 6-ой Международной конференции «Распознавание образов и анализ изображений», В.Новгород, 21-26 октября 2002, а также на ежегодных конференциях профессорско-преподавательского состава Таганрогского радиотехнического университета (2001,2002,2003, 2004 г).
Публикации. Опубликовано 32 работы, из них 28 по теме диссертации.
Структура и объём диссертации. Диссертационная работа состоит из введения, четырёх тематических глав, заключения, списка литературы и приложения. Объём диссертации - 140 страниц. Текст диссертации содержит 62 рисунка и 19 таблиц. Список литературы изложен на 8 страницах и включает 95 наименований.
Беззнаковые функции расстояния для комбинированных множеств
Конструктивная геометрия и краевое представление отличаются достаточным удобством при моделировании, но имеют не очень эффективные методы визуализации [15].
В виду того, что каждый из методов имеет определённые недостатки, существует большое количество алгоритмов преобразования конструктивных моделей в краевые [22, 23, 24, 25] и наоборот [22], а также тех и других в краевое представление [26].
В настоящее время не прекращаются попытки разработать более эффективные методы представления геометрической информации. При этом основные усилия сконцентрированы на моделировании сглаженных объектов [27] и объектов нерегулярной формы10, таких как горы, шерсть, камни, ракушки и т.п. В числе этих методов — суперквадрики [18], мягкие объекты [28], капельные объекты [29], обобщённые цилиндры [30] и свёрточные поверхности [31]. Основные требования, предъявляемые к таким методам представления информации, - это максимальная полнота и эффективность визуализации [32].
Обратим внимание на то, что все эти методы определяют геометрические объекты с помощью неявно заданных функций [33], а именно функций, принимающих отрицательные значения внутри описываемого геометрического объекта и положительные - снаружи. В результате существует большое количество работ [32], посвященных разработке эффективных методов визуализации неявно заданных функций, как с учётом особенностей конкретных моделей, так и без их учёта. Метод преобразования неявных функций в полигональное представление [26] в данном случае практически не применим из-за нерегулярной формы описываемых объектов, и фактически единственным методом визуализации таких неявно заданных функций является метод трассировка лучей [32], заключающийся в определении координат первой от наблюдателя точки пересечения визуализируемого объекта с заданным лучом.
Метод трассировки лучей позволяет визуализировать с заданной точностью сцены, содержащие полупрозрачные объекты, в условиях множественного отражения света. Обратной стороной таких возможностей является то, что алгоритмы трассировки лучей являются одними из самых неэффективных с вычислительной точки зрения, если не используются параллельные вычисления. Практически все усовершенствования метода трассировки лучей применительно к произвольным неявным функциям заключаются в оценке производных визуализируемой функции. На этом принципе основаны такие известные методы как Липшицев [34] и интервальный [35].
Наиболее эффективным методом можно признать такое обобщение липшицева метода как трассировка сфер Джона Харта [36]. Он использует понятие так называемой знаковой функции расстояния, т.е. функции, определяющей евклидово расстояние от данной точки пространства до ближайшей точки на описываемом ею объекте. Но, так как построение таких функций для сложных объектов - нетривиальная задача, то Джон Харт использовал понятие ограничивающей знаковой функции расстояния, возвращающей значения меньшие либо равные реальному расстоянию до объекта. Так как в алгоритме трассировки сфер функции расстояния рассчитываются преимущественно в точках вне объектов, то операции Ричи [37], используемые при формировании конструктивных моделей, позволяют описывать объекты с помощью ограничивающих функций расстояния. Как доказано в работе [36], сходимость метода трассировки сфер линейная, а в лучшем случае — квадратичная. Скорость визуализации достаточно сильно зависит от точности оценки функции расстояния. Более того, им было показано, что с помощью этого метода можно избавиться такого от такого неприятного эффекта трассировки лучей, как появление зубчатости на гранях изображённых геометрических объектов.
Кроме того, что моделирование с помощью функций расстояния позволяет разрабатывать эффективные алгоритмы визуализации, такие модели обладают ещё одной замечательной особенностью. В отличие от подавляющего большинства методов представления геометрической информации11, функции расстояния способны корректно моделировать геометрические объекты, содержащие компоненты различной размерности [38], при этом существуют алгоритмы визуализации таких объектов [39], основанные на методе трассировки лучей.
Следует отметить, что функции расстояния не являются принципиально новым математическим объектом. В частности, понятие функций расстояния используется при построении свёрточных поверхностей [31] и обобщённых цилиндров [30].
Кроме того, функция расстояния широко используется в задачах обработки изображений. Прежде всего, это следующие задачи. 1. Выделение остова [40], часто применяемое при распознавании абстрактных двумерных объектов, таких как буквы, цифры и т.п.
Функции расстояния для комбинированных множеств на плоскости
Также выводятся функции расстояния для отрезка прямой и дуги окружности в виде алгебраического выражения с использованием конструктивных операций Ричи. Далее рассматриваются вопросы записи функций расстояния для различных некомбинированных множеств на плоскости. Доказывается, что среди функции от двух переменных, относящихся как к классу целых рациональных функций, так и к некоторым более широким классам функций, нет функций расстояния кроме тех, которые соответствуют точке, кругу, прямой и полуплоскости. Рассматриваются вопросы получения функций расстояния для кривых второго порядка, и выводится формула для вычисления расстояния до параболы. Даются рекомендации по оптимизации вычисления функций расстояния для кривых Безье. В заключение приводятся примеры записи функций верхнего расстояния для комбинированных множеств на плоскости.
В третьей главе определяются функции расстояния для трёхмерных тел, лежащих в некоторой плоскости, тел вращения и цилиндрических тел. Определяются разделяющие подмножества для такого рода множеств. Выводятся функции расстояния для прямых и окружностей в пространстве, а также для тора, цилиндра и конуса, трактуя их как плоские тела, цилиндрические тела или тела вращения. В результате получаются выражения для вычисления функций расстояния для трёхмерных комбинированных множеств, в которых участки поверхности образованы плоскостями, сферами, торами, цилиндрическими или коническими поверхностями, и ограничены контурами, состоящими из отрезков прямых и дуг окружностей, а также отрезков эллиптических кривых. Приводятся примеры записи функций расстояния и функций верхнего расстояния для комбинированных множеств в пространстве.
В четвёртой главе диссертационной работы рассматриваются вопросы практического применения функций расстояния. Демонстрируется тот факт, что многие геометрические объекты, определённые неявно заданной функцией, могут быть визуализированы с приемлемой точностью только, если эта функция является функцией расстояния. Показывается, что алгоритмы визуализации, использующие функции расстояния, превосходят по вычислительной эффективности стандартные алгоритмы визуализации неявно заданных функций. Рассматривается метод распознавания путём идентификации параметров моделей, дающий наилучшие результаты при использовании функций расстояния в качестве параметризованных функций. Демонстрируется его высокая эффективность. Даётся оригинальная интерпретация метода преобразования Хафа, на базе которой проводится обобщение преобразования Хафа для распознавания произвольных геометрических объектов, заданных функциями расстояния. Предлагается соответствующий алгоритм. Разрабатываются рекомендации для записи функций расстояния, соответствующих эквидистантным поверхностям и сглаженным объектам. Проводится синтез управления мобильным роботом в общем виде с целью движения его вдоль кривой, заданной функцией расстояния.
Основные результаты работы. При решении поставленных в диссертационной работе задач получены следующие новые научные результаты, которые выносятся на защиту: 1. Методы построения знаковых и беззнаковых функций расстояния, а также функций верхнего расстояния для комбинированных множеств в п-мерном пространстве. 2. Условия, при которых беззнаковые функции расстояния представляются в виде алгебраических выражений с использованием конструктивных операций Ричи. 3. Методика записи функций кратчайшего и верхнего расстояния для класса двумерных и трёхмерных множеств, ограниченных квадратичными линиями и поверхностями. 4. Обобщение преобразования Хафа для анализа сцен сложных объектов с использованием функций расстояния.
Практическая ценность и внедрение. Разработанный математический аппарат представления геометрической информации может применяться для построения систем конструирования и распознавания изображений, навигации мобильных роботов, обнаружения столкновений.
На основании теоретических результатов диссертационной работы было создано программное обеспечение на языке Borland Delphi для конструирования моделей сложных объектов в виде унифицированных файлов моделей, а также конструирования и исследования систем распознавания изображений, планирования траектории движения роботов, обнаружения столкновений. Файлы моделей могут использоваться сторонними системами обработки изображений, работающими на различных аппаратно-программных платформах.
На языке Java создано программное обеспечение исследовательской системы распознавания малоразмерных зашумленных изображений с помощью разработанных моделей геометрических объектов. В универсальных системах математических исследований Maple и Mathcad разработаны подсистемы анализа геометрических моделей, обработки и распознавания изображений.
На основе функций расстояния было разработано программное обеспечение для распознавания низкокачественных изображений номерных знаков движущихся вагонов.
Преобразования функций расстояния, связанные с трансформациями множеств в пространстве
В данной главе диссертации решаются задачи построения функций расстояния для точечных множеств в пространстве К3. Эта задача с точки зрения практического применения является более актуальной, чем двумерный случай, рассмотренный во второй главе. При этом с точки зрения теоретических методов, разработанных в первой главе диссертации, нет принципиальной разницы между двумерным и трёхмерным случаем [63, 64, 65, 66, 67].
В частности, формулы для функций расстояния, соответствующих полупространству и шару, выглядят следующим образом.
Пусть [х,у] и (х,у) - векторное и скалярное произведения векторов X и у. Если полупространства H3(y,z,q) определяется своей границей dH3(y,z,q), проходящей через тройку точек y,z,q єR3, не лежащих на одной прямой, и вектором a = [ jr — z, z - у\ [q — z, z - у], который будучи отложенным от точки на dH3(y,z,q), заканчивается вне H3(y,z,q), то при г= -{а,у) верно /нъ{х y,z,q) = аххх +а2х2 +а3х3 +г. Функция расстояния для шара В\у,г) радиуса г и центром в у є R3 выглядит следующим образом:
Следует обратить внимание также на то, что известны формулы для определения расстояний до прямой в пространстве, тора, цилиндра, конуса [9, 91]. Таким образом, задача поиска наиболее широкого класса множеств, для которых может быть задана функция расстояния в виде аналитического выражения, в трёхмерном случае стоит менее остро, чем в двумерном [68].
С другой стороны, если для записи функции расстояния до отрезка линии, нужно, прежде всего, чтобы концевые точки этого отрезка были разделяющими, то для определения функции расстояния до участка поверхности, необходимо, чтобы весь контур на поверхности, ограничивающий рассматриваемый участок, был разделяющим. Получение ограничений на виды поверхностей и контуров, обладающих таким свойством, на первый взгляд не является тривиальной задачей. Для её решения следует обратить внимание на то, что такие поверхности как цилиндрическая, коническая и тор в аналитической геометрии [91] обычно определяются на базе так называемых двумерных направляющих. Быть может, полученные таким способом поверхности и тела будут наследовать свойства «разделяемости» от двумерных направляющих множеств.
Ещё одной особенностью трёхмерного случая является то, что линии сопряжения участков поверхностей для многих тел выходят за рамки отрезков прямых и дуг окружностей, что чревато как необходимостью вычислять расстояния до таких линий, так и проблемами с записью функций принадлежности для участков поверхностей, ограниченных такими линиями [69].
В рамках данной работы будут использоваться следующие понятия. Пусть множество ПсМ3 лежит в некоторой плоскости Пс= R3. Множество, образованное прямыми, проходящими через каждую точку Q перпендикулярно П, называется цилиндрическим телом или цилиндром. Множество называется телом вращения, если оно образовано окружностями, проходящими через каждую точку Q; причём окружности лежат в плоскостях, перпендикулярных некоторой прямой ЛсП,и имеют центры в точках Л. В обоих случаях Q называется направляющей. Прямая Л называется осью вращения:
Введём также следующие понятия. Цилиндрическое тело с направляющей - полосой, лежащей в некоторой плоскости, называется трёхмерной полосой. Аналогично, трёхмерным клином называется цилиндрическое тело с направляющей - клином, лежащим в некоторой плоскости. В этом случае вершине клина соответствует прямая, называемая осью трёхмерного клина.
Теорема 33. Пусть к условиям теоремы 3.1 добавлены следующие: Q3 cR3 — тело вращения с направляющей Q2 и осью вращения oxv а также, если х є SQ,, то х2 0. Тогда
К тому лее, если Ej cQ,, Е2 =#?(Ej) и S3 — тело вращения с направляющей Е2, то У(Т.Ъ П3) — тело вращения с направляющей g \y{bl 1 )1, и, если , —разделяющее, то и 3 -разделяющее. Также, если KczlR3 —трёхмерный клин с осью oxv то Q3n3K — разделяющее множество.
Доказательство. Пусть уєп(х). По теореме Пифагора /п(х1Ух2, x3) = J(y1-xl) + / і(Уі х2,х3) . Множество Q3 содержит окружность, проходящую через у, лежащую в плоскости, перпендикулярной оси охг, с центром - на охх. Отсюда точка у лежит в плоскости Псі3, определяемой как ох, сіП и лгєП, и образованной вращением плоскости ох1х2 вокруг оси ох1. Очевидно, точка у принадлежит такому множеству Q4 с: П, что существует взаимнооднозначное соответствие между множеством Q, и Q4. Откуда получается соотношение (3.3).
Визуализация геометрических объектов с использованием функций расстояния
В этой главе диссертационной работы рассматриваются вопросы применения функций расстояния для решения различных практических задач, точнее задач, связанных с анализом и синтезом неявно заданных функций, определяющих некоторую геометрическую информацию. Заметим, что функции расстояния могут непосредственно применяться для моделирования геометрических объектов, так как они однозначно определяют соответствующие тела. В этом смысле вторая и третья главы диссертации посвящены практическому применению функция расстояния для геометрического моделирования.
При этом следует обратить внимание на принципиальную разницу между моделированием с помощью функций расстояния и большинством существующих методов геометрического моделирования в виде неявно заданных функций, так как последние применяются только для описания так называемых твёрдых тел, т.е. тел, не содержащих элементов различной топологической размерности [70, 39, 71]. Хотя теоретически они и позволяют задавать геометрические объекты, содержащие элементы различной размерности, но используемые в них методы визуализации не дают возможности корректно отобразить эти объекты на изображениях. С другой стороны, как было показано в работе [36], описание объектов с помощью неявно заданных функций, фактически являющих функциями расстояния, позволяет значительно увеличить вычислительную эффективность существующих методов визуализации. Поэтому, имеет смысл проанализировать эту проблему.
Напомним, что под п -мерным изображением размерности тїхт2х...хтп понимается матрица А, элементы которой а. . 4 , і, = 1...w,, L=\...m2, ..., і =1.../и , называются пикселями. Тогда под визуализацией множества flcR" будем понимать процесс пометки тех пикселей at. 4 изображения А, для которых при д єМ" и Л 0 верно (j +A-jp y2+h-i2,...t yn+h-in)eQ.. В большинстве случаев можно считать, что у(0,0,...,0) и А = 1. Под изображением множества Q в зависимости от контекста будем понимать и изображение А с помеченными пикселями, и множество помеченных пикселей на А, и множество точек ( р/2»"-»0» ПРИ" надлежащих Q.
Геометрические объекты, определённые неявно заданными функциями, визуализируют или методом трассировки лучей, или методом попиксельного сканирования изображения [36]. Метод трассировки лучей применяется при визуализации трёхмерных множеств на двумерном изображении. Пусть множество Q задано функцией принадлежности gn(x). Тогда под трассировкой лучей понимается поиск для каждого пикселя at, такого минимального j, что (ї,,/2,г-у)єП, т.е. gn(ij,/2,r-y) 0. Здесь г - шаг трассировки. Метод попиксельного сканирования изображения заключается в последовательной пометке тех пикселей а..4 , для которых gCi(il,i2,...,in) 0. Если множество П задано функцией расстояния fn{x), то могут применяться те же методы визуализации, причём дополнительно возможно использование того факта, что, если /п( х) = г, то mtB"(x,r) пП = 0и дВ"(х,г) п& 0.
Следующей важной областью применения неявно заданных функций является распознавание изображений. Существуют различные подходы к анализу изображений [86, 80], но одним из наиболее известных является сведение задачи распознавания к оптимизационной задаче идентификации параметров модели распознаваемого объекта [47, 73, 74, 75]. Полагаем, что в качестве характеристик распознаваемого объекта на изображении выступают его контуры , т.е. некоторое множество точек yt, / = 1... N. Моделями распознаваемых объектов являются параметризованные функции j — \...M\ / eR , которые будем считать функциями принадлежности для распознаваемых образов Qj(p) ввиду того, что всевозможные контуры объ ектов могут быть получены путём визуализации множеств Qj(p) Тогда но мер модели, соответствующей распознаваемому объекту, может быть ВЫЧИС ЛИ 2 лен по формуле argmin [ (УІІР)) В работе [47] было показано, что идентификация параметров будет наиболее точной, если в качестве функций fj(x\p) использовать функции расстояния для образов Qy(p). Обратим внимание, что класс преобразований образов Qj(p) может быть ограничен преобразованием подобия, которое в соответствии с утверждением 3.1 не искажает функций расстояния.
К сожалению, так как критерий в методе идентификации параметров моделей в большинстве случаев оказывается многоэкстремальным, то область применения рассмотренного подхода к распознаванию ограничена этапом уточнения результата распознавания [59].
На ранних же этапах распознавания используются более робастные методы, например, метод преобразования Хафа [0]. Последний метод является крайне популярным, и существует огромное количество его модификаций. Он также используется для распознавания объектов пег заданным параметризованным моделям: Поэтому представляет интерес анализ возможности использования функций расстояния в качестве таких моделей.
