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