Исследование методов, разработка алгоритмического и программного обеспечения пространственного анализа графической информации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Утешева, Тамара Шатовна

• Утешева, Тамара Шатовна
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Утешева, Тамара Шатовна

Аннотация

Введение

Глава 1. Иерархические структуры представления графической информации и метод от общего к частному в задачах вычислительной геометрии

Глава 2. Алгоритмы решения задач вычислительной геометрии на базе метода от общего к частному

2.1. Планарные алгоритмы

2.1.1. Вычисление расстояния от точки до кривой на плоскости

2.1.2. Поиск кривой из множества, ближайшей к заданной точке 32 ^ 2.1.3. Алгоритм поиска ближайшей к заданной кривой точки из множества точек к

2.1.4. Алгоритм определения пересечений луча с кривой

2.1.5. Алгоритм определения положения точки относительно области

2.1.6. Вычисление расстояния между кривыми на плоскости

2.1.7. Алгоритм определения участков примыкания двух кривых

2.1.8. Алгоритм определения участков совпадения и точек пересечения двух кривых

2.1.9. Алгоритм определения частей структурированных кривых, попадающих внутрь области

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

2.2. Алгоритмы задач вычислительной геометрии в пространстве R

2.2.1. Вычисление расстояния от точки до поверхности

2.2.2. Вычисление расстояния между поверхностью и кривой

2.2.3. Вычисление расстояния между двумя поверхностями

2.2.4. Алгоритм определения пересечений луча с поверхностью 2.3. Классификация алгоритмов решения задач ВГ на базе метода от общего к частному по типу порядка обхода УБРД

Глава 3 Оптимизация временных характеристик алгоритмов решения планарных задач вычислительной геометрии на базе иерархических структур представления данных

3.1. Метод оптимизации на базе использования сортировки существенных отсчетов верхнего уровня иерархического представления данных

3.1.1. Выбор эффективного значения максимальной длины сортируемых отрезков

3.2. Метод оптимизации на базе использования фактора множественности

3.3. Метод оптимизации на базе использования сетки квадратов

3.4. Сравнение эффективности различных методов оптимизации временных характеристик решения задач вычислительной геометрии

Глава 4 Использование базовых геометрических алгоритмов в прикладных задачах обработки картографической информации

4.1. Алгоритм построения цепочно-узловой (сегментной) модели описания метрической информации картографических объектов

4.2. Алгоритм построения поля квадратов (списка окон) объектной области

4.3. Алгоритм определения допустимых участков дорожной сети по критерию видимости

4.3.1. Определение значения функции F(X, Y) на кусочнолинейных участках маршрута

4.3.2. Определение видимости точки поверхности из заданной точки наблюдения

Глава 5. Разработка и создание проблемно - ориентированного программного обеспечения для решения задач вычислительной геометрии в ГИС

5.1. Комплекс программ для решения задач вычислительной геометрии

5.2. Подсистема построения цепочно-узловой (сегментной) модели описания метрической информации графических объектов

5.3. Подсистема формирования пространственно - обусловленных связей

5.4. Учебно-исследовательская система "Методы и алгоритмы вычислительной геометрии на базе иерархических структур представления графической информации"

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

Цифровая обработка графической информации (ГИ) отаосится к числу наиболее трудоемких задач современной кибернетики, информатики и вычислительной техники. При этом ГИ является наиболее естественным носителем исходной информации практически во всех областях науки и техники. Цифровая обработка изображений и графической информации широко используется при решении многих важных отраслевых задач, автоматизации проектирования (САПР), автоматизации научных исследований (АСНИ), в робототехнике, медицинской и технологической диагностике, мониторинге природных ресурсов, геоинформационных технологиях и системах (ГИС), и т. д.

В последние годы рынок геоинформационных технологий и систем выходит на лидирующие позиции. Все ГИС системы базируются на информационных технологиях создания, обработки и комплексного анализа сложно-структурированной цифровой графической информации, которые, кроме того, включают в себя и приложения, ориентированные на принятие решений на базе этих данных. Обрабатываемая в ГИС информация — это, как правило, очень большая совокупность объектов (линейных, площадных и дискретных) между которыми существуют сложные метрические и семантические отношения. Причем, метрическая составляющая этих объектов составляет порядка 60 - 70% всей информации. Поэтому большая часть технологических этапов ГИС направлена на обработку именно метрической части картографических объектов, и они наиболее ресурсоемкие.

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

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

Сложно-структурированный, семантически насыщенный документ - это материальный объект (конструкторские проекты, географические и топографические карты, графические материалы медицинской диагностики и др.), содержащий образно-знаковые модели действительности в форме графических изображений и терминов естественного языка. Размеры документов могут достигать порядка 1000 х 1000 мм2 и более, объекты могут изменяться от 0.1 мм до нескольких метров, точность обработки составляет порядка 0.1мм. Это предопределяет огромные размеры исходных данных — порядка 104- 105 Кбайт.

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

Все это определяет актуальность проблемы разработки новых подходов и методов обработки и анализа сложно-структурированной ГИ, в число которых входят методы и алгоритмы вычислительной геометрии.

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

1. Статическая задача. Все элементы множества графических объектов заданы и доступны для обработки.

2. Динамическая задача. Частным случаем ее является on-line постановка (реального времени, префиксного режима), когда элементы обрабатываются по одному. В общем случае допускается появление новых элементов и удаление старых (операции вставить, удалить [5,6]) .

3. Задача с предобработкой. При многократном решении одной и той же задачи на некотором множестве объектов можно получить меньшую временную сложность за счет предобработки исходного множества.

4. Приближенное решение задачи. Вместо точного решения ищется приближенное с оценкой приближения.

5. Параллельная обработка. При постановке задачи предполагается, что можно использовать f(n) процессоров, где п - размер входа задачи.

Центральной проблемой при решении комбинаторно - геометрических ' задач является построение эффективных алгоритмов по временной и емкостной сложности. Многие задачи решаются простыми переборными методами. Но основные усилия прилагаются к созданию "быстрых" или оптимальных • алгоритмов.

Эффективные алгоритмы для решения геометрических задач часто конструируются при помощи общих методов теории алгоритмов, таких, как "разделяй и властвуй", балансировка, рекурсия и динамическое программирование [15,16,60].

Однако существуют методы, которые подсказаны исключительно природой некоторых геометрических задач. Один из таких методов — метод заметания [60]. Наиболее часто встречаются примеры плоского заметания (в двух измерениях) и пространственного заметания (в трех измерениях). Основная идея плоского заметания (ее можно весьма просто обобщить на случай трех измерений) состоит в следующем. Есть вертикаль, которая заметает плоскость слева на право, останавливаясь в особых точках, именуемых "точками событий". Пересечение заметающей прямой с входными данными задачи содержит всю полезную для продолжения поиска информацию. При этом имеется две основных структуры.

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

2) Статус заметающей прямой - адекватное описание пересечения этой заметающей прямой с заметаемой геометрической структурой. "Адекватное"

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

В [60] описано применение этого метода в задачах локализации точки (сложность 0(N logN')) и в задачах поиска пересечений многоугольников сложность 0((N+K) logN), где К - число пересечений, встреченных алгоритмом).

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

В [60] приводятся и другие методы решения задачи локализации точки.

Алгоритм, основанный на определении количества точек пересечения произвольной прямой, проходящей через рассматриваемую точку, со сторонами многоугольника имеет сложность 0(N).

Алгоритм, основанный на разбиении звездного N - угольника на клинья, использующий бинарный поиск, имеет сложность 0( logN) при затратах 0(N) на предварительную обработку, которая состоит в поиске ядра многоугольника.

Метод полос (Добкин и Липтон) требует 0(N2) временных затрат, а метод цепей - 0(log*N) при затратах 0(NlogN) времени на предобработку.

Дальнейшее развитие метод полос получил в алгоритме Препарата и Биларди, который назван методом трапеций. Этот метод имеет чрезвычайно простую процедуру поиска 0( logN), но использует очень много памяти 0(N2) в худшем случае.

Довольно широко исследована задача построения выпуклой оболочки конечного множества точек, и особенно в случае точек на плоскости. Это объясняется тем, что она является центральной в целом ряде приложений, например, в распознавании образов, обработке изображений, в задачах раскроя и компоновки материала. Наиболее наглядный и наименее продуктивный алгоритм, который состоит в удалении точек, не являющихся крайними и в упорядочивании оставшихся крайних точек требует времени 0(N*).

Метод обхода Грэхема состоит в упорядочивании точек множества в соответствии с полярным углом и расстоянием до некоторой внутренней точки множества. При этом выпуклая оболочка N точек на плоскости может быть найдена за время 0(N logN) при памяти 0(N) с использованием только арифметических операций и сравнений.

Алгоритм Джарвиса обходит кругом выпуклую оболочку (обход Джарвиса), порождая в нужном порядке последовательность крайних точек по одной на каждом шаге. В худшем случае временные затраты алгоритма определяются как 0(N2), но он очень эффективен, когда заранее известно, что число вершин выпуклой оболочки h мало 0(h N).

Быстрый метод построения выпуклой оболочки (Eddy, Bykat, Green, Silverman) имеет временные затраты 0(N logN).

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

При решении задач близости метод простого перебора имеет сложность

0(N2).

Применение метода диаграммы Вороного сокращает это время до 0(N logN).

Естественным расширением задач о принадлежности и близости является широкий класс задач вычислительной геометрии о пересечении. Одна из важнейших задач машинной графики, которая входит в этот класс - это задача удаления невидимых линий и поверхностей. Она привлекала внимание многих исследователей [ Desens, Freeman, Loutel, Galimbert, Warnock, Watkins ] в связи с потребностями развития САПР, а в настоящее время бурное развитие ^ машинной графики, компьютерных игр, мультимедиа поддерживает этот интерес.

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

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

Простейший случай - пересечение выпуклых многоугольников.

Одним из наиболее простых алгоритмов для решения этой задачи (кроме, разумеется, простого перебора отрезков, который имеет сложность 0(L • М), где L и М - количество вершин двух выпуклых многоугольников), является алгоритм Сазерленда — Ходжмана. Он сводит исходную задачу к серии более

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

Алгоритм Шеймоса и Хоуи базируется на упорядочивании набора лучей, исходящих из удаленной точки О плоскости и проходящих через вершины многоугольников, по величине угла. Ключевым моментом является то, что пересечение каждого сектора с выпуклым многоугольником образует четырехугольник, а в случае бесконечного удаления точки О, прямоугольник.

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

В начале обзора существующих методов и алгоритмов рассматривался метод заметания. Он применим для этого класса задач и дает временную сложность вычисления 0(N logN).

Одним из способов оптимизации алгоритмов решения задач поиска пересечений, и всех задач, которые к ним сводятся — является построение ограничивающих тел {Bounding Volumes) [76-79]. Вокруг каждого объекта описывается тело достаточно простого вида (прямоугольники — на плоскости, прямоугольные параллепипеды с ребрами, параллельными осям - в трех — мерном пространстве). Если эти тела не пересекаются, то и содержащиеся в них объекты не пересекаются. При пересечении описывающих тел поиск пересечений соответствующих объектов ведется обычным образом.

Еще одним методом, позволяющим упростить анализ взаимного расположения объектов и использовать когерентность как на плоскости так и в пространстве, является разбиение плоскости (пространства) (Spatial Subdivision) [47].

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

Кроме того, одним из методов оптимизации алгоритмов, используемых в настоящее время в машинной графике, является представление графической информации в виде иерархических структур {Hierarchies) [47,78,79]. Стандартными формами таких структур являются восьмеричные, тетрарные и бинарные деревья.

Одной из сравнительно простых структур является иерархия ограничивающих тел. Сначала ограничивающее тело описывается вокруг всех объектов. На следующем шаге объекты разбиваются на несколько компактных групп и вокруг каждой из них описывается свое ограничивающее тело и т. д. Иерархические структуры строятся и на основе разбиения плоскости (пространства). Каждая клетка разбиения разрезается на части, которые, в свою очередь, также могут быть разбиты, и т.д. При этом каждая клетка разбиения соответствует узлу дерева.

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

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

Одним из методов представления ГИ, реализующим иерархию аппроксимаций является полосное дерево, предложенное D.H.Ballard [84]. Исходная кривая представляется в виде иерархии полос, которая имеет топологию бинарного дерева. Корнем этого дерева является полоса, параллельная отрезку, соединяющему концевые точки кривой и имеющая ширину W|+\vr, где W| и Wj - максимальные отклонения исходной кривой влево и вправо от аппроксимирующего отрезка. Это - самый грубый k-ый уровень аппроксимации. Для перехода к (к-1)-му уровню приближения выбирается любая промежуточная точка исходной кривой и строятся две аппроксимирующие полосы (к-1)-го уровня. Процесс разбиения продолжается до тех пор, пока величина vvi+wr превышает некоторую заданную погрешность. К недостаткам этого метода можно отнести избыточность задействованной под хранение структуры памяти - одной вершине полосного дерева соответствует 6 действительных чисел и 2 указателя. Кроме того, такой подход невозможно применить непосредственно к замкнутым кривым, и кривым, промежуточные точки участков которых располагаются вне области полосы, ограниченной перпендикулярами' к концевым точкам отрезков, аппроксимирующих соответствующие участки кривой.

Эти проблемы частично разрешены предложенным W. Burton в работе [87] методом построения дугового дерева. Для хранения одной вершины дугового дерева необходимо 2 действительных числа и 2 ссылки. Исходная кривая при данном подходе параметризируется в зависимости от длины и затем представляется в виде иерархии эллипсов, в фокусах которых лежат точки разбиения кривой. Иерархия имеет вид двоичного дерева.

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

В работе [89] приведены алгоритмы определения положения точки относительно кривой и поиска пересечения кривых с .использованием представления данных в виде дуговых деревьев. Отмечается быстрая сходимость этих алгоритмов.

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

1. использование общих методов теории алгоритмов;

2. методы, естественно вытекающие из самой природы геометрических задач и ограниченные жесткими условиями конкретной задачи (например, многоугольник - выпуклый);

3. методы разбиения пространства (плоскости);

4. методы ограничивающих тел;

5. методы построения иерархических структур, и др.

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

Это связано с тем, что технология автоматического анализа графической информации - сложный многоэтапный процесс, включающий в себя большое количество методов и алгоритмов обработки - фильтрации, сжатия, хранения и поиска, анализа и принятия решений. Для эффективной работы этого "конвейера" необходимо, чтобы все методы и алгоритмы, а также структуры представления данных, что очень важно, были взаимоувязаны и взаимоэффективны, так как очевидно, что сколь угодно высокая эффективность на каком-то отдельном участке обработки может быть сведена на нет на других этапах. Таким образом, методы обработки должны быть технологичны и удовлетворять некоторым общим требованиям, предопределенным эффективностью решения задач анализа графической информации в целом. Однако, в настоящее время большинство методов, позволяющих решать частную задачу, практически не пригодны для эффективной работы в "конвейере" обработки ГИ.

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

Таким образом, основные требования, предъявляемые к методам и алгоритмам вычислительной геометрии в ГИС следующие:

• технологичность;

• высокая емкостная и временная эффективность;

• естественная интегрируемость в общую схему ГИС.

В НИИ ПМК ННГУ был разработан новый подход к задачам обработки ГИ, ориентированный на анализ больших массивов графических данных (Ю.Г.Васин) [11-14]. В его основе лежат методы конструктивного формирования и принятия решений на базе локальных однородных хорошо приспособленных базисных функций (ЛОХПБФ).

Важным преимуществом предложенного подхода является то, что наряду с простотой реализации, он позволяет строить эффективные рекурсивные алгоритмы адаптивного сжатия, фильтрации и принятия, решений. Причем, алгоритмы адаптивного сжатия и фильтрации на базе ЛОХПБФ на выходе предопределяют эффективную иерархическую регулярную структуру хранения и обработки информации. Указанная структура представления графической информации позволяет оптимизировать время принятия решений для разнообразных задач, распараллеливать процесс обработки графических данных, организовывать эффективную обработку ГИ по принципу от общего к частному, эффективно решать задачи вычислительной геометрии.

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

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

Для достижения этой цели в диссертации решены следующие задачи:

• Изучены геоинформационные технологии с целью выявления основных задач ВГ, используемых в этих технологиях. Проведен анализ существующих методов решения задач ВГ. Выработаны основные требования к методам и алгоритмам решения задач ВГ для ГИС.

• Исследованы и развиты эффективные методы и алгоритмы решения задач ВГ, а также тематических прикладных задач анализа пространственных отношений графических объектов на базе иерархического представления данных в ГИС.

• Исследованы и развиты методы и алгоритмы оптимизации временной сложности решения задач ВГ.

• Проведены экспериментальные исследования и даны сравнительные оценки эффективности разработанных алгоритмов ВГ.

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

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

Научная новизна диссертационной работы заключается в следующем:

• В разработке и развитии новых эффективных базовых алгоритмов вычислительной геометрии для решения разнообразных задач анализа положения и пространственно-обусловленных связей дискретных, линейных и площадных объектов на плоскости и в пространстве в ГИС на основе иерархических структур представления данных и метода от общего к частному;

• В разработке новых методов и алгоритмов оптимизации временной сложности базовых алгоритмов вычислительной геометрии.

• В оценке временной сложности основных базовых алгоритмов вычислительной геометрии.

• В разработке новых эффективных процедур решения прикладных тематических задач в ГИС на базе иерархических структур представления данных и метода от общего к частному.

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

Практическая ценность. В основу диссертационной работы положены результаты, полученные автором в ходе исследований, проводимых в рамках НИОКР Министерства науки и образования РФ, Федеральной службы геодезии и картографии России, Главного управления навигации и океанографии МО РФ.

Работа выполнена при финансовой поддержке РФФИ, грант поддержки ведущих научных школ № 00-15 -96108 и ФЦП "Интеграция" проект /С-03392.

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

Апробация полученных результатов. Разработанное алгоритмическое и программное обеспечение внедрено:

• в геоинформационных центрах Федеральной службы геодезии и картографии России в рамках технологии создания цифровых карт и планов городов всего масштабного ряда;

• в Главном управлении навигации и океанографии ВМФ МО РФ (ЦКП-280.ВМФ МО РФ) в автоматизированных системах создания мировой коллекции электронных морских навигационных карт;

• в НИИ прикладной математики и кибернетики ННГУ в объектно-ориентированной интеллектуальной геоинформационной системе "ГИС-Терра";

• в НижНовЭнерго в проблемно-ориентированной ГИС "Кабельные сети";

• в учебном процессе на факультете Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского (кафедра Интеллектуальные информационные системы и геоинформатика);

Результаты диссертационной работы докладывались и обсуждались на 3-ей Всесоюзной, 5-ой и 8-ой Всероссийской научных конференциях "Методы и средства обработки сложной графической информации" (Нижний Новгород 1988, 1998, 2003гг.), 2-ой, 3-ей и 5-ой Всероссийской и международной конференциях "Распознавание образов и анализ изображений: Новые информационные технологии" (Н.Новгород 1997г., Самара 2000г., С.Петербург 2004г.).

Основные положения работы освещены в десяти опубликованных печатных работах.

Содержание работы. Диссертация состоит из пяти глав.

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

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

2. Алгоритмы решения задач вычислительной геометрии на базе метода от общего к частному.

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

3. Оптимизация временных характеристик алгоритмов решения планарных задач вычислительной геометрии на базе иерархических структур представления данных.

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

4. Использование базовых геометрических алгоритмов в прикладных задачах обработки картографической информации.

В главе предлагаются разработанные новые эффективные процедуры решения прикладных тематических задач в ГИС на базе иерархических структур представления данных и метода от общего к частному.

5. Разработка и создание проблемно - ориентированного программного обеспечения для решения задач вычислительной геометрии в ГИС.

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Утешева, Тамара Шатовна

Заключение

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

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

Разработаны алгоритмы решения задач вычислительной геометрии в пространстве /?3: вычисление расстояния от точки до поверхности; вычисление расстояния между поверхностью и кривой; вычисление расстояния между двумя поверхностями; алгоритм определения пересечений луча с поверхностью.

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

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

Предложенные алгоритмы отвечают поставленным требованиям, а именно обеспечивают:

• высокую вычислительную и емкостную эффективность;

• полную технологическую совместимость с информационными технологиями создания, обработки и комплексного анализа сложноструктурированной графической информации геоинформационной системы, разработанной в НИИПМК ННГУ.

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

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

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

Предложен оптимизационный метод, основанный на использовании фактора множественности объектов.

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

Разработаны методы и алгоритмы решения прикладных тематических задач в ГИС на базе иерархических структур представления данных и метода от общего к частному.

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

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

Эксплуатация в реальных производственных условиях разработанных программных комплексов и систем в различных организациях и предприятиях

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

Список литературы диссертационного исследования кандидат технических наук Утешева, Тамара Шатовна, 2005 год

1. Абламейко С.В., Лагуновский Д.М. Обработка изображений: технология, методы, применение: Учебное пособие Минск: Амалфея, 2000.

2. Абраш, Майкл Программирование графики. Таинства Киев: ЕвроСиб, 1995.

3. Александров В.В., Горский Н.Д. Представление и обработка изображений. Рекурсивный подход Л.: Наука, 1985.

4. Артамонов Г.Т., Пержу В.Л. Построение адаптивных вычислительных средств обработки изображений / Автоматика и телемеханика. -1994.- № 10.

5. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман Структуры данных и алгоритмы Москва: Издательский дом "Вильяме", 2001.

6. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман Построение и анализ вычислительных алгоритмов М.: Мир, 1979.

7. Боресков А.В., Шикин Е.В. Компьютерная графика. Динамика, реалистические изображения М.: ДИАЛОГ- МИФИ, 1995 .

8. Бутаков Е.А. Обработка изображений на ЭВМ М.: Радио и связь, 1987.

9. Васин Ю.Г. Сжатие исходного описания ЭКГ-сигнала / Республиканская конференция. Теория и практика разработки автоматизированных медицинских информационных систем на курортах. Киев. ИК АН УССР-1975.- С.69-75.

10. Васин Ю.Г. Нерегулярные выборки отсчетов исходной информации и задача кодирования электрокардиографических данных / Кибернетика и вычислит, техника. 1978. - Вып.42. - С. 98 - 104.

11. Н.Васин Ю.Г. "Хорошо приспособленные" базисы и задачи обработки экспериментальной информации: Учебное пособие / Горьк. гос. ун-т -Горький, 1979,- 129с.Щ

12. Васин Ю.Г. Оптимизация описания исходных данных в диалоговых системах решения задач классификации // Современное состояние теории исследования операций / Под ред. М.Н. Моисеева. М.: Наука - 1979. -С.424-450.

13. Васин Ю.Г. "Хорошо приспособленные" базисы в задачах обработки данных в АСНИ // Труды 1-ой международной школы по АСНИ / Науч. центр биохимич. исследований АН СССР. Пущино, 1982. С.226-233.

14. Ю.Г. Васин, А.Д. Крахнов Метод от общего к частному в задачах дискретной геометрии / Методы и средства обработки графической информации: Межвуз. сб. / Под ред. Ю.Г. Васина / Горьк. гос. ун-т. -Горький, 1986.-С. 67-80.

15. Ю.Г. Васин, О.А. Башкиров, Б.М. Чудинович Комбинаторно-<• геометрический подход в задачах анализа сложной графической информации /

16. Автоматизация обработки сложной графической информации: Межвуз. сборник / Под ред. Ю.Г. Васина / Горьк. гос. ун-т. Горький, 1987.- С. 5-32.

17. Ю.Г. Васин, А.Д. Крахнов, Т.Ш. Утешева Метод от общего к частному при решении пространственных задач дискретной геометрии // Автоматическая обработка сложной графической информации: Межвуз. сборник / Горьк. гос. ун-т Горький, 1988. - С. 73-83.

18. Ю.Г. Васин, А.Д. Крахнов, Т.Ш. Утешева Определение видимости точек поверхности, заданной изолиниями Ташкент: Издательство "Фан" (Наука), 1992.- 86-92.

19. Yu.G. Vasin, A.D. Krakhnov, and Т. Sh. Utesheva Computing the Visibility of Points a Surface Given by Isolines // Pattern Recognition and Image Analysis. -2001.-VI1 -№1.- P.261-262.

20. Ю.Г. Васин, Т.Ш. Утешева Учебная программа по технологии решения задач дискретной геометрии // Методы и средства обработки сложной графической информации: Тезисы докладов VII Всероссийской с участием стран СНГ конференции Н.Новгород, 2003. - С. 99-100.

21. Yu. G. Vasin, A.D. Krakhnov, and Т. Sh. Utesheva Methods of discrete geometry in the problems of processing complex graphic information // Pattern Recognition and Image Analysis.- 2005.- VI1. №1.

22. Ю.Г. Васин, А.В. Плесков Выделение контурных перепадов на полутоновом изображении с предварительным сжатием информации // Автоматизация обработки сложной графической информации: Межвуз. сб. науч. тр. / Горьк. гос. ун-т. Горький, 1985. - С. 17-32.

23. Виттих В.А., Сергеев В.В., Сойфер В.А. Обработка изображений в автоматизированных системах исследований. М.: Наука, 1982.

24. И. Гардан, М.Люка Машинная графика и автоматизация конструирования -М.: Мир, 1982.

25. В. Гилой Интерактивная машинная графика Москва: Мир, 1981.

26. Д. Гильберт, С. Кон-Фоссен Наглядная геометрия — Москва: Наука, 1981.

27. Н.Д. Горский Рекурсивная модель представления изображений / Автоматизация обработки сложной графической информации: Межвуз. сб. науч. тр. / Горьк. гос. ун-т Горький, 1984. — С. 159 - 178.

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

29. Ю.И. Журавлев Об алгоритмическом подходе к решению задач распознавания или классификации / Проблемы кибернетики. М., 1978 -Вып.ЗЗ.-С. 5-68.

30. О. Зенкевич, К. Морган Конечные элементы и аппроксимация Москва: Мир, 1986.

31. В.А. Евстигнеев, В.Н. Касьянов Алгоритмы на деревьях Новосибирск: ВЦ, 1989.

32. А.П. Кирсанов Комбинаторно-геометрический метод описания и отождествления изображений / Изв. АН СССР, Техн. кибирнет. 1991. -№ 4. - С. 81 - 90.

33. Кнут Д. Искусство программирования для ЭВМ: в 3 т. Т1: Основные алгоритмы Москва: Мир, 1976.

34. Кнут Д. Искусство программирования для ЭВМ в 3 т. ТЗ: Сортировка и поиск Москва: Мир, 1976.

35. Н. Кристофидес Теория графов: Алгоритмический подход М.: Мир, 1987.

36. Кричевский, Р.Е. Сжатие и поиск информации М: Радио и связь, 1989.

37. Кунт М., Икономопулос А., Кошер М. Методы моделирования изображений второго поколения / ТИИЭР, 1985.- Т.73.- № 4.

38. М. Ласло Вычислительная геометрия и компьютерная графика на С++ -Москва: БИНОМ, 1997.

39. М.М. Ланге Древовидная сегментация образов для ускорения анализа сцен / Прикладные проблемы искусственного интеллекта: Сб. науч. тр. М.: ИФТП, 1991.

40. Г. Майерс Надежность программного обеспечения: пер. с англ. М.: Мир, 1980.

41. Математика и САПР В двух книгах. Книга 2. Вычислительные методы. Геометрические методы М.: Мир, 1989.

42. Методы компьютерной обработки изображений / Под ред. В.А. Сойфера М.: Физматлит, 2001.

43. Ю.И. Неймарк, Ю.Г. Васин Кодирование больших массивов информации в связи с задачами распознавания образов / Динамика систем: Межвуз. тематич. сборник научн. тр. под ред. Ю.И. Неймарка / Нижегор. Гос. ун-т -Н.Новгород, 1995.

44. Ф.А. Новиков Дискретная математика для программистов Санкт-Петербург: Питер, 2001.

45. У. Ньюмен, Р. Спрулл Основы интерактивной графики Москва: Мир, 1985.

46. Т. Павлидис Алгоритмы машинной графики и обработки изображений -Москва: Радио и связь, 1986 .

47. М. Петров О некоторых задачах обработки сложной графической информации / Автоматизация обработки сложной графической информации: Межвуз. сборник / Горьк. гос. ун-т. Горький, 1984. - С. 3 -12.

48. Алексей Поляков Методы и алгоритмы компьютерной графики в примерах на Visual С++ Санкт-Петербург: БХВ-Петербург, 2002.

49. В.Н. Пореев Компьютерная графика С.Пб.: BHV, 2002.

50. Ф. Препарата, М.Шеймос Вычислительная геометрия. Введение М.: Мир, 1989.

51. У. Претт Цифровая обработка изображений, в 2 т., Т. 1, 2 -Москва: Мир, 1982.

52. Д. Роджерс Алгоритмические основы машинной графики М.: Мир, 1989.

53. Д. Роджерс, Дж. Адаме Математические основы машинной графики -Москва: Машиностроение, 1980.

54. Д. Роджерс Математические основы машинной графики Москва: Мир, 2001.

55. В.Ю. Романов Популярные форматы файлов для хранения графических изображений на IBM PC М: Унитех, 1992.

56. В.А. Семенов, П.Б. Крылов, С.В. Морозов, М.Г. Роминов, О.А. Таралапан Объектно-ориентированная методология разработки интегрированных приложений моделирования и визуализации / Труды Института системного программирования РАН М.: Открытые системы, 2000.

57. Е. А. Староденко Элементы вычислительной геометрии Минск: Наука и техника, 1986.

58. Т. Сван Программирование для Windows в Borland С++, Пер. с англ. -М: Бином, 1995.

59. Стронгин Р.Г. Численные методы в многоэкстремальных задачах М.: Наука, 1978.

60. Ю. Тихомиров Программирование трехмерной графики Санкт Петербург: BHV, 1998.

61. Учебник Maplnfo Professional. Режим доступа: http://www.esti-map.ru.

62. Ю.В. Чуркин Структуры данных для представления изображений / Зарубежная радиоэлектроника 1983. - № 8.

63. А. Фокс, М. Пратт Вычислительная геометрия. Применение в проектировании и на производстве М.: Мир, 1982.

64. Дж. Фоли, А. вэн Дэм Основы интерактивной машинной графики -Москва: Мир, 1987.

65. В.М. Шарыганов Быстрое вычисление расстояний между плоскими кривыми / Теор. и прикл. вопросы распознавания изображений /АН УССР, Ин-т кибернетики, Науч. совет УССР по проблемам кибернетики Киев, 1991.

66. Е.В. Шикин, А.В.Боресков, А.А.Зайцев Начала компьютерной графики М.: ДИАЛОГ-МИФИ, 1993.

67. Е.В. Шикин, А.В. Боресков Компьютерная графика М.: Диалог МИФИ, 1997.

68. Е.В. Шикин, А.В. Боресков Компьютерная графика. Полигональные модели -М.: Диалог МИФИ, 2005.

69. Е.В. Шикин, А.В. Боресков Компьютерная графика. Полигональные модели М.: ДИАЛОГ- МИФИ, 2000.

70. В. Я. Цветков Геоинформационные системы и технологии М.: Финансы и статистика, 1998.

71. Э. Эйнджел Интерактивная компьютерная графика. Вводный курс на базе OpenGL, 2 изд. Пер. с англ. Москва: Вильяме, 2001.

72. Эсти Мэп Геоинформационные системы - Режим доступа: http://www.esti-map.ru/magellan.htm.

73. В.В. Яншин Анализ и обработка изображений: принципы и алгоритмы М.: Машиностроение, 1995.

74. D.H. Ballard Strip trees: A hierarchical representation for curves / Comm. of the ACM 1981.- May.

75. Ilia A. Bogaevski, Edward A. Kopylov An Implicit Approach to Cloth Synthesis / Computer Graphics & Geometry, Internet Journal 2004.

76. W. Brodlie, J. R. Gallop, A. J. Grant, J. Haswell, W. T. Hewitt, S. Larkin, С. C. Lilley, H. Morphet, A. Townend, J. Wood, H. Wright Review of Visualization Systems Advisory Group on Computer Graphics / Technical Report -1999.

77. W. Burton Representation of many-sided polygons and polygonal lines for rapid processing / Comm. of the ACM 1977. - March.

78. G. Farin Curves and surfaces for computer aided geometric design. A practical guide / Academic Press 1990.

79. O. Gunter Efficient structures for geometric data management / // LNCS 1988. -V.337.

80. Vis. Hyper Teaching Scientific Visualization Using Hypermedia / ACM SIGGRAPH Education Committee, 1999.

81. V. Ivannikov, S. Morozov, V. Semenov, 0. Tarlapan, R. Rasche, T. Jung Parallel object-oriented modeling and visualization in Open MV environment / Proceedings of GraphiCon'99 Moscow, 1999. - August 26 - September 1.

82. V.N. Kozlov Visual Pattern and Geometric Transformations of Images // Pattern Recognition and Image Analysis.- 2000.- V10. №3.- P.320-342.

83. P.A. Kim, V.P. Pyatkin, and E.V. Rusin Tree Massively Parallel Algorithms for Solving Computational Geometry Problems by Using Euclidean Distance Transform // Pattern Recognition and Image Analysis.- 2004.- VI4. №2.- P.267-275.

84. M.M. Lange and A.M. Lange Invariant Representation of Grayscale Patterns by Trees of Geometric Primitives // Pattern Recognition and Image Analysis.- 2003.-V13. -№1.-P.138-141.

85. Mohamed Ali Said Approximation Of Single-Valued Digital Curves Using Alternating Convex Hulls / Computer Graphics & Geometry , Internet Journal -2004.

86. Palacions-Veles О. and Renaud B.C. A Dynamic Hierarchical subdivision algorithm for computing Delaunau triangulations and other closest point problems / ACM Trans, on Math. Soft- 1990.- № 16.

87. Samet H. Computing Perimeters of Regions In Images Represented By Quadtrees / Trans. Of Pattern Anal, and Math. Intell. 1982. - V.4. - P. 524 - 528.

88. Samet H. The quadtree and related hierarchical data structures / Computing Surveys.-1984.-16,2 (June 1984).-P. 187-260.

89. Semenov V., Morozov S., Tarlapan O., Belyaeva A. Component-based development of scientific computing applications in OpenMV environment / Proceedings of 16th IMACS World Congress, Lausanne, Switzerland, 2000. -August 21-25.

90. H. Senay, E. Ignatus Rules and Principles of Scientific Data Visualization / Tech. Report, George Washington University, Department of Electrical Engineering and Computer Science 1999.-February.

91. Semenov V., Morozov S., Tarlapan O., Jung T. An object-oriented architecture for integrated CAD systems / Proceedings of CAD'2000, Berlin, Germany, 2000.-March 1-3.- pp.195-217.

92. Semenov V.A., Alekseeva E.V., Morozov S.V., Tarlapan O.A. A Map-Based Programming Approach To Visualization Applications / Proceedings of Institute for System Programming / ed. V.P. Ivannikov, vol. 5. Moscow, ISP RAS, 2004. - pp. 161-195.

93. Semenov V.A., Alekseeva E.V., Morozov S.V. Virtual Construction Using Map-Based Approach / Proceedings of X International Conference on Computing in Civil and Building Engineering, Weimar, 2004. June 02-04. - pp. 254-255.

94. T. Schreiber Clustering for Data Reduction and Approximation / Computer Graphics & Geometry, Internet Journal 2004.

95. Vasin Yu.G., Zherzdev S.V. Information Techniques for Hierarchical image Coding // Pattern Recognition and Image Analysis.- 2003.- V13. №3.- pp.539548.

96. Краткое описание и основные технические характеристики внедряемой продукции, отличительные черты, положительные качества и технико экономические преимущества.

97. Алгоритмическое и программное обеспечение обработки метрической информации картографических объектов реализует методы вычислительной геометрии (ВГ) на базе иерархических структур представления графических данных.

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

99. Краткое описание и основные технические характеристики внедряемой продукции, отличительные черты, положительные качества и технико -экономические преимущества.

100. Среди отличительных и уникальных особенностей разработанных программных комплексов можно отметить следующие:

101. Библиотечные функции могут использоваться при разработке приложений в среде визуальной системы программирования C++Builder (начиная с версии 3) для работы в среде операционных систем Windows 9x/ME/NT/XP.