Построение и исследование аналитических функций расстояния и их применение для анализа и синтеза изображений тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Семерий, Олег Сергеевич

• Семерий, Олег Сергеевич
• кандидат физико-математических наук
• 2004

Оглавление диссертации кандидат физико-математических наук Семерий, Олег Сергеевич

Глава 1. Исследование функций расстояния в n-мерном пространстве

1.1. Постановка задачи.

1.2. Основные понятия и определения.

1.3. Множества Вороного.

1.4. Исследование конструктивных операций.

1.5. Беззнаковые функции расстояния для комбинированных множеств

1.6. Знаковые функции расстояния для комбинированных множеств.

1.7. Дифференциальные свойства функций расстояния.

1.8. Функции верхнего расстояния.

1.9. Примеры функций расстояния в n-мерном пространстве.

1.10. Выводы.

Глава 2. Построение функций расстояния для множеств на плоскосгии

2.1. Постановка задачи.

2.2. Функции расстояния для комбинированных множеств на плоскости.

2.3. Алгебраические функции расстояния.

2.4. Функции расстояния для кривых второго порядка.

2.5. Численно-аналитические функции расстояния.

2.6. Функции верхнего расстояния на плоскости.

2.7. Выводы.

Глава 3. Построение функций расстояния для множеств в пространстве

3.1. Постановка задачи.

3.2. Преобразования функций расстояния, связанные с трансформациями множеств в пространстве.

3.3. Функции расстояния для плоских линий в пространстве.

3.4. Функции расстояния для поверхностей.

3.5. Функции расстояния для участков поверхностей.

3.6. Функции расстояния для комбинированных множеств в пространстве

3.7. Функции верхнего расстояния в пространстве.

3.8. Выводы.

Глава 4. Применение функций расстояния в задачах анализа и синтеза изображений

4.1. Постановка задачи.

4.2. Визуализация геометрических объектов с использованием функций расстояния.

4.3. Распознавание изображений с помощью функций расстояния.

4.4. Обобщение преобразования Хафа.

4.5. Применение функций расстояния в задачах робототехники.

4.6. Выводы.

Введение диссертации (часть автореферата) на тему «Построение и исследование аналитических функций расстояния и их применение для анализа и синтеза изображений»

Обработка графической информации1 является одной из основных областей деятельности практически любой компьютерной системы . Это обусловлено тем, что, во-первых, представление информации в графическом виде позволяет организовать эффективное человеко-машинное взаимодействие3 [1], так как такого рода информация значительно проще воспринимается людьми [2], во-вторых, при решении достаточно сложных задач автономная компьютерная система выступает в качестве замены человека и поэтому обычно получает и обрабатывает визуальную информацию. К таким интеллектуальным [3] задачам относятся анализ аэрофотоснимков [4], визуальный контроль трафика движения автотранспорта [5, 6], навигация мобильных роботов [4] и многие другие [7, 8].

Устройства ввода графической информации в компьютерную систему [9], такие как сканеры, фото и видеокамеры, а также устройства вывода, такие как дисплеи и принтеры, обуславливают форму представления графической информации в вид изображений [10]. С математической точки зрения, изображение является матрицей, элементы которой в двумерном случае называются пикселями, а в трёхмерном4 — вокселями. В простейшем случае пиксель принимает значение «1», если он соответствует точке изображённого объекта, и значение «0», если не соответствует. Эти изображения называются бинарными [10]. Существуют и другие виды изображений [11], например, полутоновые, в которых пиксель принимает значения, определяющие яркость соответствующей точки изображённого объекта. Отсюда, имеет смысл

1 Здесь под графической понимается информация, представленная в виде фотографий, рисунков и диаграмм.

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

3 Обратим внимание на то, что практически все современные операционные системы имеют графический интерфейс [12].

4 Примерами устройств ввода трёхмерных изображений являются томографические, магнитно-резонансные и ультразвуковые медицинские сканеры [4]. говорить о геометрической информации, представленной бинарным изображением, так как оно определяет только форму и положение соответствующего объекта5, который в этом случае называется геометрическим объектом6 [13].

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

Существуют исследования [14, 15], посвящённые теории представления геометрической информации, в соответствии с которыми, метод представления информации сопоставляет каждому допустимому геометрическому объекту его модель. Модель - это выражение, составленное из символов некоторого алфавита в соответствии с определёнными синтаксическими правилами. Метод представления информации должен обладать свойствами: а) полноты, т.е. моделировать все интересуемые виды геометрических объектов; б) адекватности - любая модель должна соответствовать некоторому реальному геометрическому объекту; в) однозначности - любой модели должен соответствовать единственный объект; г) уникальности — любому допустимому объекту должна соответствовать единственная модель;

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

4 С математической точки зрения геометрический объект может быть определён как множество точек в евклидовом пространстве, поэтому в диссертационной работе не делается различий между понятиями «геометрический объект» и «множество точек». д) краткости - модель должна представлять собой достаточно простое выражение; е) эффективности - должны существовать эффективные алгоритмы создания, обработки и визуализации моделей.

Наиболее известными методами представления геометрической информации являются [15, 16]: а) полигональное представление — представление в виде аппроксимации поверхности геометрического объекта многогранниками; б) конструктивная геометрия, создающая геометрические объекты из примитивов (кубов, сфер, конусов и т.п.) с помощью теоретико-множественных операций, таких как пересечение, объединение и вычитание; в) краевое представление, определяющее топологию объекта путём задания его клеточного разбиения [17].

Полигональное представление отличается наличием крайне эффектив ных с вычислительной точки зрения алгоритмов визуализации , но обладает и большим количеством недостатков: а) применяется для описания только трёхмерных объектов; б) форма объектов определяется приближённо9 [18]; в) практически не приспособлено для описания объектов, изменяющих свою форму; г) сложно решается задача обнаружения столкновений [19] при моделировании динамических сцен; д) конструирование моделей непосредственно в полигональном виде крайне неудобно.

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

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

9 Приближённость описания объектов эффективно маскируется различными методами наложения текстур и теней [21].

Конструктивная геометрия и краевое представление отличаются достаточным удобством при моделировании, но имеют не очень эффективные методы визуализации [15].

В виду того, что каждый из методов имеет определённые недостатки, существует большое количество алгоритмов преобразования конструктивных моделей в краевые [22, 23, 24, 25] и наоборот [22], а также тех и других в краевое представление [26].

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

27] и объектов нерегулярной формы10, таких как горы, шерсть, камни, ракушки и т.п. В числе этих методов — суперквадрики [18], мягкие объекты

28], капельные объекты [29], обобщённые цилиндры [30] и свёрточные поверхности [31]. Основные требования, предъявляемые к таким методам представления информации, - это максимальная полнота и эффективность визуализации [32].

Обратим внимание на то, что все эти методы определяют геометрические объекты с помощью неявно заданных функций [33], а именно функций, принимающих отрицательные значения внутри описываемого геометрического объекта и положительные - снаружи. В результате существует большое количество работ [32], посвящённых разработке эффективных методов визуализации неявно заданных функций, как с учётом особенностей конкретных моделей, так и без их учёта. Метод преобразования неявных функций в полигональное представление [26] в данном случае практически не применим из-за нерегулярной формы описываемых объектов, и фактически единственным методом визуализации таких неявно заданных функций является метод трассировка лучей [32], заключающийся в определении координат

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

Метод трассировки лучей позволяет визуализировать с заданной точностью сцены, содержащие полупрозрачные объекты, в условиях множественного отражения света. Обратной стороной таких возможностей является то, что алгоритмы трассировки лучей являются одними из самых неэффективных с вычислительной точки зрения, если не используются параллельные вычисления. Практически все усовершенствования метода трассировки лучей применительно к произвольным неявным функциям заключаются в оценке производных визуализируемой функции. На этом принципе основаны такие известные методы как Липшицев [34] и интервальный [35].

Наиболее эффективным методом можно признать такое обобщение липшицева метода как трассировка сфер Джона Харта [36]. Он использует понятие так называемой знаковой функции расстояния, т.е. функции, определяющей евклидово расстояние от данной точки пространства до ближайшей точки на описываемом ею объекте. Но, так как построение таких функций для сложных объектов - нетривиальная задача, то Джон Харт использовал понятие ограничивающей знаковой функции расстояния, возвращающей значения меньшие либо равные реальному расстоянию до объекта. Так как в алгоритме трассировки сфер функции расстояния рассчитываются преимущественно в точках вне объектов, то операции Ричи [37], используемые при формировании конструктивных моделей, позволяют описывать объекты с помощью ограничивающих функций расстояния. Как доказано в работе [36], сходимость метода трассировки сфер линейная, а в лучшем случае — квадратичная. Скорость визуализации достаточно сильно зависит от точности оценки функции расстояния. Более того, им было показано, что с помощью этого метода можно избавиться такого от такого неприятного эффекта трассировки лучей, как появление зубчатости на гранях изображённых геометрических объектов.

Кроме того, что моделирование с помощью функций расстояния позволяет разрабатывать эффективные алгоритмы визуализации, такие модели обладают ещё одной замечательной особенностью. В отличие от подавляющего большинства методов представления геометрической информации11, функции расстояния способны корректно моделировать геометрические объекты, содержащие компоненты различной размерности [38], при этом существуют алгоритмы визуализации таких объектов [39], основанные на методе трассировки лучей.

Следует отметить, что функции расстояния не являются принципиально новым математическим объектом. В частности, понятие функций расстояния используется при построении свёрточных поверхностей [31] и обобщённых цилиндров [30].

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

1 7

1. Выделение остова [40], часто применяемое при распознавании абстрактных двумерных объектов, таких как буквы, цифры и т.п.

2. Построение дистантных изображений13 [41], использующихся, например, при сравнении изображений.

Дистантные изображения формируются либо с помощью эвристических алгоритмов фильтрации изображений [41], либо путём решения так называемого уравнения эйконала [42, 43], которое является дифференциальным уравнением в частных производных. Решением уравнения эйконала и является функция расстояния. Данные методы весьма эффективны, но не решают проблему построения исходного бинарного изображения, задающего начальные условия для уравнения эйконала или алгоритма фильтрации. Эта про

11 Все рассмотренные ранее методы представления геометрической информации позволяют корректно моделировать только так называемые твёрдые тела [ 14], одной из особенностей которых является то, что это п-мерные [44] тела в n-мерном пространстве, и они не содержат элементов размерности меньше п.

12 Выделение остова заключается в утончении изображённых объектов.

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

Дистантные изображения являются мощным инструментом для сравнения различных изображений [41], построения непрерывных трансформаций одного изображения в другое [45], выделения остова [40] и построения эквидистантных поверхностей [46]. Дистантные изображения преимущественно используются при распознавании изображений.

Если же рассмотреть собственно задачу распознавания изображений, то обнаруживается следующий факт. Существует стандартный подход к определению положения и размеров изображённого объекта по его параметризованной модели - метод оценки параметров модели со среднеквадратичным критерием [47]. Как было показано в исследовании [47], если параметризованная модель задаётся функцией, фактически являющейся функцией расстояния, то параметры модели будут определены наиболее быстро и точно.

В присутствии сильного шума на изображениях применяются робаст-ные методы оценки параметров, например, метод М-оценок [47]. Анализ используемого в нём критерия близости [47] также показывает, что для него желательно описание объекта в виде функции расстояния. Существуют и конкретные работы, посвящённые распознаванию геометрических объектов по их функциям расстояния [48].

Таким образом, задача определения функций расстояния для различных геометрических объектов является крайне актуальной. Рассмотрим публикации, посвящённые выводу функций расстояния для конкретных геометрических объектов. Во-первых, это работа Дж. Харта о методе трассировки сфер [36], где были получены приближённые функции расстояния для различных тел и их объединений. Во-вторых, это работа В.Л. Рвачёва [49], по-свящённая теории R-функций. В ней автором было введено понятие беззнаковой функции расстояния и исследованы её свойства. Также была получена схема записи функций расстояния для фигур, представляющих собой конечное число отрезков прямых и дуг окружностей на плоскости. Им же было введено и исследовано понятие функции верхнего расстояния, определяющей евклидово расстояние от точки пространства до наиболее удалённой точки объекта. Существуют также работы, связанные с построением эвристических методов вычисления расстояний до многогранников [50]. И, наконец, определение расстояния до ближайшей точки на множестве является одной из основных задач вычислительной геометрии [51]. К сожалению, традиционно в качестве множеств, до которых определяется расстояние, выступают совокупности изолированных точек. При этом задача сводится к построению диаграмм Вороного, разделяющих пространство на многогранники Вороного [52], в приделах которых расстояние минимально до конкретной точки из рассматриваемого множества точек. Однако существуют работы, посвящён-ные построению диаграмм Вороного для множеств, содержащие отрезки кривых [53].

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

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

В соответствии с поставленной целью задачами диссертационного исследования являются:

1. Разработка методов построения функций расстояния для достаточно сложных двумерных и трёхмерных объектов.

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

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

4. Разработка и исследование методов распознавания с использованием функций расстояния.

5. Разработка обобщения преобразования Хафа для анализа сцен сложных объектов с использованием функций расстояния.

Структура диссертации. Материалы диссертационной работы распределены по главам в соответствии с перечисленными задачами.

Первая глава посвящена разработке метода записи функций расстояния для множеств в R". В начале главы вводится и исследуется понятие множества Вороного, обобщающего понятие области Дирихле. Затем анализируются свойства неявных функций, формируемых с помощью операций min(jc,j>) и max(jc,j>). Определяются условия, при которых эти функции являются функциями расстояния. Вводятся понятия комбинированного и разделяющего множеств. В результате разрабатываются оригинальные схемы записи знаковых и беззнаковых функций расстояния для объединения и пересечения множеств. Также формулируются условия для записи функций расстояния в виде алгебраических выражений, использующих конструктивные операции Ричи. Далее проводится анализ дифференциальных свойств функций расстояния. Выводятся выражения для вычисления частных производных различных порядков от функций расстояния, соответствующих комбинированным множествам. Исследуются свойства функций верхнего расстояния, разрабатываются методики их вычисления. В заключение выводятся формулы для вычисления знаковых и беззнаковых функций расстояния, соответствующих множествам изолированных точек, шарам, сферам, плоскостям и полупространствам в пространстве R".

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

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

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

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

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

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

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

3. Методика записи функций кратчайшего и верхнего расстояния для класса двумерных и трёхмерных множеств, ограниченных квадратичными линиями и поверхностями.

4. Обобщение преобразования Хафа для анализа сцен сложных объектов с использованием функций расстояния.

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

На основании теоретических результатов диссертационной работы было создано программное обеспечение на языке 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 наименований.

Заключение диссертации по теме «Теоретические основы информатики», Семерий, Олег Сергеевич

4.6. Выводы

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

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

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

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

Заключение

При решении поставленных в диссертационной работе задач получены следующие научные результаты:

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

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

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

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

5. Определена связь межу функциями расстояния для множеств на плоскости и функциями расстояния для тела вращения и цилиндрических тел.

6. Определены области Вороного для эллипсов, лежащих на поверхности цилиндров, полуконусов и полупространств.

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

Список литературы диссертационного исследования кандидат физико-математических наук Семерий, Олег Сергеевич, 2004 год

1. Грачёв Н.Н. Психология инженерного труда. - М.: Высш. шк., 1998.

2. ХорнБ., Минский М., Сираи И. и др. Психология машинного зрения. -М.: Мир, 1978.

3. ЧернухинЮ.В. Искусственный интеллект и нейрокомпьютеры. — Таганрог: ТРТУ, 1997.

4. Куафе Ф. Взаимодействие робота с внешней средой. — М.: Мир, 1985.

5. BeymerD., McLauchlan Ph., et al. A real-time computer vision system for measuring traffic parameters // Proc. of CVPR'1997. 1997. - pp.495-501.

6. Koller D., Daniilidis K., et al. Model-based object tracking in traffic scenes // Proc. ofECCV'1992.- 1992. -pp.437-452.

7. Верхаген К., Дёйн P., Грун Ф. и др. Распознавание образов: состояние и перспективы. М.: Радио и связь, 1985.

8. Горелик A.JL, Гуревич И.Б., Скрипкин В.А. Современное состояние проблемы распознавания: Некоторые аспекты. М.: Радио и связь, 1986.

9. Михайленко В.Е., Кислоокий В.Н., ЛященкоА.А. и др. Геометрическое моделирование и машинная графика в САПР. К.: Выща шк., 1991.

10. Ю.Павлидис Т. Алгоритмы машинной графики и обработки изображений. -М.: Радио и связь, 1986.11 .Gonzalez R.C. and Woods R.E. Digital image processing. MA.: Addison-Wesley, 1992.12,Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2002.

11. Васюков А.Н., Комаров Ю.А., Янович И.А. Логико-алгебраические методы решения геометрических задач и разработка программного обеспечения САПР. К.: Наук, думка, 1991.

12. Requicha A.A.G. Representation for rigid solids: Theory, Methods, and Systems // ACM Computing Surveys. 1980. - Vol.12, N.4. - pp. 437-464.

13. Hoffmann C.M. Geometric and solid modeling. San Mateo, California: Morgan Kaufmann, 1989.

14. MantylaM. An introduction to solid modeling. Rockville, Maryland: Computer Science Press, 1988.

15. Борисович Ю.Г. и др. Введение в топологию. М.: Наука, Физматлит, 1995.

16. Вяткин С.И., Долговесов Б.С., Есин А.В. и др. Геометрическое моделирование и визуализация функционально заданных объектов // Автометрия. -1999.-№6.-С. 84-92.

17. LinM. and Gottschalk S. Collision detection between geometric models: A survey // Proc. of IMA Conference on Mathematics of Surfaces, 1998.

18. Sung K. Area sampling buffer: Tracing rays with z-buffer hardware // Comput. Graph. Forum 11(3):299-310, 1992.

19. Ikedo Т., Ma J. An advanced graphics chip with bump-mapped Phong shading // Proc. of CGI'1997,1997.

20. Requicha A.A.G. and Voelcker H.B. Boolean operations in solid modeling: boundary evaluation and merging algorithms // Proc. of the IEEE, 73(1), 1985.

21. Miller J. and Goldman R. Combining algebraic rigor with geometric robustness for the detection and calculation of conic section in the intersection of two quadric surfaces // Proc. of ACM Solid Modeling, pp.221-233,1991.

22. Keyser J., Krishnan S., and Manosha D. Efficient and accurate b-rep generation of low degree sculptured solids using exact arithmetic: I representation // Computer Aided Geometric Design, 16(9):841-859, 1999.

23. Keyser J., Krishnan S., and Manosha D. Efficient and accurate b-rep generation of low degree sculptured solids using exact arithmetic: II computation // Computer Aided Geometric Design, 16(9):861-882,1999.

24. Bloomenthal J. Polygonization of implicit surfaces // CAD, 5(4):341-355, 1988.

25. Woodwark J.R. Blends in geometric modeling // In R.R. Martin, ed., The Mathematics of Surface II. Clarendon Press, 1997. - pp.255-297.

26. Wyvill G., McPheeters C., and Wyvill B. Data structure for soft objects // Visual Computer 2(4):227-234, 1986.

27. Wyvill В., Guy A., and Galin E. The BlobTree: Warping, blending and Boolean operations in an implicit surface model system // Computer Graphic Forum, 18(2):149-158,1999.

28. Agin CG.J. and Binford Т.О. Computer description of curved objects // IEEE Trans, on Computers, 24(4):439-449,1976.31 .Bloomenthal J. and Shoemake K. Convolution surfaces // Computer Graphics, 25(4):251-256,1991.

29. Hart J.C. Ray tracing implicit surfaces // WSU technical report EECS-93-014, 1993.

30. Bloomenthal J. Introduction to implicit surfaces. Morgan Kaufmann, 1997.

31. Karla D. and Barr A.H. Guaranteed ray intersections with implicit surfaces // Computer Graphics, 23(3):297-306,1989.

32. Snyder J.M. Interval analysis for computer graphics 7/ Computer Graphics, 26(2):121-130,1992.

33. Hart J.C. Sphere tracing: a geometric method for the antialiased ray tracing of implicit surfaces // The Visual Computer, 12(10):527-545, 1996.

34. Ricci D. A constructive geometry for computer graphics // Computer Journal, 1973.

35. Gomes J. and Faugeras O. Representing and evolution smooth manifolds of arbitrary dimension embedded in Rn as the intersection of n hypersurfaces: The vector distance functions // Technical Report 4012, INRIA, 2000.

36. Бутенков C.A., Семерий O.C. Аналитический подход к решению задач компьютерной графики // Искусственный интеллект. Донецк: ИЛИИ, 2000.-№3.-С. 428-437.

37. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.

38. Sethian J.A. Level set methods and fast matching methods evolving interface in computational geometry, fluid mechanics, computer vision, and material science. Cambridge University Press, 1999.

39. Болтянский В.Г., Ефремович B.A. Наглядная топология. M.: Наука, 1983.

40. Breen D. and Whitaker R. A level-set approach for the metamorphosis of solid models // IEEE Trans, on Visualization and Computer Graphics, 7(2): 173-192, 2001.

41. Barnhill R.E., Frost T.M., and Kersey S.N. Self-intersection and offset surfaces // In R.E. Barnhill, ed., Geometry Processing for Design and Manufacture, SLAM. —1992. pp.35-44.

42. Zhang Z. Parameter estimation techniques: a tutorial with application to conic fitting // Int. Journal of Image and Vision Computing, 15(l):59-76, 1997.

43. Сироджа И.Б. Алгоритм распознавания геометрических образов. // Известия АН СССР, Техническая кибернетика. 1967. - №5. - С. 136-144.

44. Рвачёв B.JI. Теория R-функций и некоторые её приложения. Киев: Наук, думка, 1982.

45. Huang J., LiY., et al. A complete distance field representation // Proc. 12th IEEE Visualisation. 2001. - pp.247-254.51 .Препарата Ф., Шеймос M. Вычислительная геометрия: Введение. — М.: Мир, 1989.

46. Aurenhammer F. and Klein R. Voronoi diagrams // In J. Sack and G. Urrutia, editors, Handbook of Computational Geometry. Elsevier Science Publishing, 2000. -pp 201-290.

47. Yap C.K. An 0(n log n) algorithm for the Voronoi diagram of set of simple curve segments // Discrete Comput. Geom., 2:365-393, 1987.

48. Breen D., Mauch S., and Whitaker R. 3D scan conversion of CSG models into distance, closest-point and color volumes // In M. Chen, A.E. Kaufman,

49. R. Yagel (eds.), Volume Graphics. London: Springer, 2000. - Chapter 8. -pp.135-158.

50. SiggC., PeikertR., and Gross M. Signed distance transform using graphics hardware // IEEE Visualization 2003. 2003. - pp.83-90.

51. Sethian J.A. A fast marching level set method for monotonically advancing fronts // Proc. Nat. Acad. Sci. 1996. - Vol. 94. - pp.1591-1595.

52. Mauch S. A fast algorithm for computing the closest point and distance transform // Technical report, Applied and computational mathematics, California Institute of technology. 2000.

53. Hoff K., Culver T., et al. Fast computation of generalized Voronoi diagrams using graphic hardware // SIGGRAPH 99. 1999. - pp.277-285.

54. Семерий O.C. Распознавание геометрических объектов с помощью функций расстояния // Сб. трудов Международной конференции «Распознавание образов и анализ изображений» (РОАИ-6-2002). — В.Новгород, 2002. -С. 486-490.

55. Семерий О.С. Математическое моделирование в техническом зрении // Сб. докладов Всероссийской конференции «Измерения, автоматизация и моделирование в промышленности и научных исследованиях-2000». -Бийск: АлтГТУ, 2000. С. 26-28.

56. Семерий О.С. Разработка математического метода геометрического моделирования // Сб. тезисов докладов 10-й Всероссийской конференции молодых учёных «Математическое моделирование в естественных науках». Пермь: ПГТУ, 2001. - С. 76.

57. Итенберг И.И., Бутенков С.А., Семерий О.С., Бачило С.А. Аналитический метод представления геометрической информации // Сб. докладов 3-ой

58. Семерий O.C., Бутенков C.A. Метод моделирования и распознавания симметрии в интеллектуальных системах // Сб. докладов Научной сессии МИФИ-2001. М.: МИФИ, 2001. - Т.З. - С. 162-163.

59. Семерий О.С., Бутенков С.А. Геометрическое моделирование с учётом симметрии // Обозрение прикладной и промышленной математики. М.: ТВП, 2001. - Т.8, Вып.1. - С. 319-320.

60. Бутенков С.А., Семерий О.С. Применение нечётких операторов в задачах агрегирования геометрической информации // Сб. трудов конгресса «Искусственный интеллект в XXI веке» (1САГ2001). — М., Физматлит, 2001. -Т.1.-С. 167-175.

61. Семерий О.С. Представление геометрической информации в задачах обнаружения столкновений // Сб. трудов Научной молодёжной школы «Интеллектуальные робототехнические системы-2001». Таганрог: ТРТУ, 2001.-С. 94-96.

62. Бутенков С.А., Семерий О.С. Аналитические модели в задачах компьютерной графики // Сб. тезисов докладов Международной научной конференции «Искусственный интеллект-2000». Таганрог: ТРТУ, 2000. -С. 168-170.

63. Бутенков С.А., Семерий О.С. Аналитические методы решения основных задач компьютерной графики // Обозрение прикладной и промышленной математики. М.: ТВП, 2000. - Т.7, Вып.2. - С. 325-326.

64. Семерий О.С. Метод максимальных площадей для выделения движущихся объектов по серии изображений // Сб. трудов ВНТК «Компьютерные технологии в инженерной и управленческой деятельности-98». Таганрог: ТРТУ, 1999.-С. 23-31.

65. Семерий О.С., Бутенков С.А. Оптимизация процесса распознавания изображений в параллельных системах // Сб. тезисов докладов Междун. конф. «Интеллектуальные многопроцессорные системы-99». — Таганрог: ТРТУ, 1999.-С. 92-93.

66. Бутенков С.А., Семерий О.С. Оптимизационный метод распознавания изображений с помощью аналитических моделей в параллельных системах // Сб. трудов Междун. конф. «Интеллектуальные многопроцессорные системы-99». Таганрог: ТРТУ, 1999.-С. 190-196.

67. Разработка методов распознавания изображений ограниченного класса сцен для задачи «Автопоиск»: Отчет о НИР (заключит.) / НКБ ВС; Руководитель А.Н. Каркищенко; А.Г. Броневич, С.А. Бутенков, О.С. Семерий и др. Таганрог, 1999. - 200 с.

68. Бутенков С.А., Бачило С.А., Семерий О.С. Динамические модели краёв в задачах обработки изображений // В сб. трудов Межд. научной конференции «Математические методы в технике и технологиях». С.-Петербург: СПбГТИ, 2000. - Т.4. - С. 26-28.

69. Семерий О.С. Методы динамической фильтрации изображений // Сб. тезисов докладов V Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (КРЭС-2000). Таганрог: ТРТУ, 2000. - С. 120-121.

70. Karkishchenko, A., Butenkov, S. and Semery, О. Analytical Parameterized Models in Computer Vision // Proc. of 6th Int. Conf. on Control, Robotics and Vision (ICARCV-2000). Singapore, 2000.

71. Разработка методов распознавания изображений ограниченного класса сцен для задачи «Автопоиск»: Отчет о НИР (итоговый) / НКБ ВС; Руководитель А.Н. Каркищенко; А.Г. Броневич, С.А. Бутенков, О.С. Семерий и др. Таганрог, 2000. - 122 с.

72. Butenkov, S., Semery, О., Karkishchenko, A. Analytical Approach for Recognition of Arbitrary Primitives // Proc. of the Fourth LAPR Int. Workshop on Graphics Recognition (GREC 2001). Kingston, Canada, 2001.

73. Бутенков C.A., Семерий О.С. Интеллектуальный подход в задаче распознавания символов текста // Сб. докладов Научной сессии МИФИ-2001. — М.г МИФИ, 2001.-Т.З.-С. 160-161.

74. Колесников А.А., Бутенков С.А., Семерий О.С. Синергетические методы в классификации состояния экологических систем // Известия ТРТУ. Таганрог: ТРТУ, 2001. - №2. - С. 52-56.

75. Каркищенко А.Н., Семерий О.С. Анализ сцен с использованием R-Моделей // Обозрение прикладной и промышленной математики. М.: ТВП, 2001. - Т.8, Вып.2. - С. 680-681.

76. Семерий О.С., Бутенков С.А. Оптимальный синергетический регулятор для управления манёврами ИСЗ на круговых орбитах // Известия ТРТУ. — Таганрог: ТРТУ, 2004. №4, книга 2. - С. 154-160.

77. Броневич А.Г., Семерий О.С. Яркостная сегментация изображений на основе меры информативности // Pattern Recognition and Image Analysis. — M.: Наука. №4, Вып. 14.

78. Ефимов H.B., Розендорн Э.Р. Линейная алгебра и многомерная геометрия. -М.: Наука, 1970.

79. Моденов П.С. Аналитическая геометрия. М.: Изд. МГУ, 1969.

80. Abramowitz М. and Stegun I.A. (Eds.). Handbook of mathematical functions with formulas, graphs, and mathematical tables. New York: Dover, 1972.

81. Hough P.V.C. Method and means for recognizing complex patterns // U.S. Patent 3,069,654, 1962.

82. Колесников А.А. Синергетическая теория управления. M.: Энергоатом-издат, 1994.

83. Мирошник И.В., Говядинкин Д.С., Дроздов В.Н. Система управления транспортной тележкой. // Сб. Управление в оптических и электромеханических системах. Ленинград, 1989.