Содержание к диссертации
Введение
Глава 1. Иерархические структуры представления графической информации и метод от общего к частному в задачах вычислительной геометрии 18
Глава 2. Алгоритмы решения задач вычислительной геометрии на базе метода от общего к частному 28
2.1. Планарные алгоритмы 28
2.1.1. Вычисление расстояния от точки до кривой на плоскости 28
2.1.2. Поиск кривой из множества, ближайшей к заданной точке 32
2.1.3. Алгоритм поиска ближайшей к заданной кривой точки из множества точек . к 33
2.1.4. Алгоритм определения пересечений луча с кривой 34
2.1.5. Алгоритм определения положения точки относительно
области 36
2.1.6. Вычисление расстояния между кривыми на плоскости 37
2.1.7. Алгоритм определения участков примыкания двух кривых 39
2.1.8. Алгоритм определения участков совпадения и точек пересечения двух кривых 42
2.1.9. Алгоритм определения частей структурированных кривых, попадающих внутрь области 44
2.1.10. Алгоритм определения частей структурированных кривых, попадающих внутрь области, граница которой задана структурированной кривой 45
2.2. Алгоритмы задач вычислительной геометрии в пространстве R3 46
2.2.1. Вычисление расстояния отточки до поверхности 46
2.2.2. Вычисление расстояния между поверхностью и кривой 49
2.2.3. Вычисление расстояния между двумя поверхностями 51
2.2.4. Алгоритм определения пересечений луча с поверхностью 53
2.3. Классификация алгоритмов решения задач ЯГ на базе метода от общего к частному по типу порядка обхода УБРД 54
Глава 3 Оптимизация временных характеристик алгоритмов решения планарных задач вычислительной геометрии на базе иерархических структур представления данных 60
3.1. Метод оптимизации на базе использования сортировки существенных отсчетов верхнего уровня иерархического представления данных 61
3.1.1. Выбор эффективного значения максимальной длины сортируемых отрезков 65
3.2. Метод оптимизации на базе использования фактора множественности 68
3.3. Метод оптимизации на базе использования сетки квадратов 71
3.4. Сравнение эффективности различных методов оптимизации временных характеристик решения задач вычислительной геометрии 76
Глава 4 Использование базовых геометрических алгоритмов в прикладных задачах обработки картографической информации 79
4.1. Алгоритм построения цепочно-узловой (сегментной) модели описания метрической информации картографических объектов 81
4.2. Алгоритм построения поля квадратов (списка окон) объектной области 85
4.3. Алгоритм определения допустимых участков дорожной сети по критерию видимости 89
4.3.1. Определение значения функции F(X, Y) на кусочно-линейных участках маршрута 90
4.3.2. Определение видимости точки поверхности из заданной точки наблюдения 93
Глава 5. Разработка и создание проблемно - ориентированного программного обеспечения для решения задач вычислительной геометрии в ГИС 99
5.1. Комплекс программ для решения задач вычислительной геометрии 106
5.2. Подсистема построения цепочно-узловой (сегментной) модели описания метрической информации графических объектов 108
5.3. Подсистема формирования пространственно - обусловленных связей 111
5.4. Учебно-исследовательская система "Методы и алгоритмы вычислительной геометрии на базе иерархических структур представления графической информации" 114
Заключение 118
Список литературы 121
- Иерархические структуры представления графической информации и метод от общего к частному в задачах вычислительной геометрии
- Вычисление расстояния от точки до кривой на плоскости
- Выбор эффективного значения максимальной длины сортируемых отрезков
- Алгоритм построения поля квадратов (списка окон) объектной области
Введение к работе
Цифровая обработка графической информации (ГИ) относится к числу наиболее трудоемких задач современной кибернетики» информатики и вычислительной техники. При этом ГИ является наиболее естественным носителем исходной информации практически во всех областях науки и техники. Цифровая обработка изображений и графической информации широко используется при решении многих важных отраслевых задач, автоматизации проектирования (САПР), автоматизации научных исследований (АСНИ), в робототехнике, медицинской и технологической диагностике, мониторинге природных ресурсов, геоинформационных технологиях и системах {ГИС), и т. д.
В последние годы рынок геоинформационных технологий и систем выходит на лидирующие позиции. Все ГИС системы базируются на информационных технологиях создания, обработки и комплексного анализа сложно-структурированной цифровой графической информации, которые, кроме того, включают в себя и приложения, ориентированные на принятие решений на базе этих данных. Обрабатываемая в ГИС информация - это, как правило, очень большая совокупность объектов (линейных, площадных и дискретных) между которыми существуют сложные метрические и семантические отношения. Причем, метрическая составляющая этих объектов составляет порядка 60 — 70% всей информации. Поэтому большая часть технологических этапов ГИС направлена на обработку именно метрической части картографических объектов, и они наиболее ресурсоемкие.
При обработке метрической информации в ГИС огромная роль отводится методам вычислительной геометрии (ВГ), лежащим в основе геометрических и логических операций над графическими объектами (поиск пересечений, примыканий, вхождений, удаление в пределах заданного расстояния, оверлейные операции и др.), а также приложений, основная вычислительная нагрузка которых приходится на решение задач ВГ. Это такие прикладные задачи ГИС, как: сегментация, установление пространственных и логических связей, построение буферных зон, поля квадратов, генерализация, разграфка, сшивка и т.д.
Расширение сфер, требующих автоматизации обработки графической информации, привело к качественному усложнению графических документов большие размеры, отсутствие строгих ограничений на шрифт и типоразмеры, наличие фона, большое количество пространственно-логических и топологических связей и метрических отношений между линейными, площадными и дискретными объектами. Практикой выдвинута проблема обработки сложно-структурированных графических документов.
Сложно-структурированный, семантически насыщенный документ - это материальный объект (конструкторские проекты, географические и топографические карты, графические материалы медицинской диагностики и др.), содержащий образно-знаковые модели действительности в форме графических изображений и терминов естественного языка. Размеры документов могут достигать порядка 1000 х 1000 мм2 и более, объекты могут изменяться от 0.1 мм до нескольких метров, точность обработки составляет порядка 0.1мм. Это предопределяет огромные размеры исходных данных — порядка 10-10 Кбайт.
Кроме того, большое число задач требует производить обработку графической информации в реальном масштабе времени и при ограниченных ресурсах памяти.
Все это определяет актуальность проблемы разработки новых подходов и методов обработки и анализа сложно-структурированной ГИ, в число которых входят методы и алгоритмы вычислительной геометрии.
В настоящее время в вычислительной геометрии рассматриваются следующие варианты постановок задач:
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 — угольника на клинья, использующий бинарный поиск, имеет сложность O(togN) при затратах 0(N) на предварительную обработку, которая состоит в поиске ядра многоугольника.
Метод полос (Добкин и Липтон) требует 0(N) временных затрат, а метод цепей - Oflog N) при затратах 0(NlogN) времени на предобработку.
Дальнейшее развитие метод полос получил в алгоритме Препарата и Биларди, который назван методом трапеций. Этот метод имеет чрезвычайно простую процедуру поиска O(IogN), но использует очень много памяти OfN2) в худшем случае.
Довольно широко исследована задача построения выпуклой оболочки конечного множества точек, и особенно в случае точек на плоскости. Это объясняется тем, что она является центральной в целом ряде приложений, например, в распознавании образов, обработке изображений, в задачах раскроя и компоновки материала. Наиболее наглядный и наименее продуктивный алгоритм, который состоит в удалении точек, не являющихся крайними и в упорядочивании оставшихся крайних точек требует времени
Метод обхода Грэхема состоит в упорядочивании точек множества в соответствии с полярным углом и расстоянием до некоторой внутренней точки множества. При этом выпуклая оболочка N точек на плоскости может быть найдена за время 0(N logN) при памяти 0(N) с использованием только арифметических операций и сравнений.
Алгоритм Джарвиса обходит кругом выпуклую оболочку (обход Джарвиса), порождая в нужном порядке последовательность крайних точек по одной на каждом шаге. В худшем случае временные затраты алгоритма определяются как 0(N3), но он очень эффективен, когда заранее известно, что число вершин выпуклой оболочки h мало 0(h N). Быстрый метод построения выпуклой оболочки (Eddy, Bykat, Green, Silverman) имеет временные затраты 0(NlogN).
Хорошо исследован большой класс задач вычислительной геометрии, который анализирует близость: ближайшая пара двух точек, поиск ближайших соседей в окрестности фиксированного радиуса, все ближайшие соседи, к -ближайших соседей. К этому же классу принадлежат задачи построения минимального остовного дерева и триангуляции.
При решении задач близости метод простого перебора имеет сложность 0(N2).
Применение метода диаграммы Вороного сокращает это время до 0(NlogN).
Естественным расширением задач о принадлежности и близости является широкий класс задач вычислительной геометрии о пересечении. Одна из важнейших задач машинной графики, которая входит в этот класс - это задача удаления невидимых линий и поверхностей. Она привлекала внимание многих исследователей [ Desens, Freeman, Loutel, Galimbert, Warnock, Watkins ] в связи с потребностями развития САПР, а в настоящее время бурное развитие машинной графики, компьютерных игр, мультимедиа поддерживает этот интерес.
Большое количество алгоритмов предложено для., задач удаления невидимых линий и поверхностей в растровом формате. Предметом нашего обзора являются алгоритмы для работы в векторном формате.
Основная вычислительная задача при удалении невидимых линий состоит в формировании пересечений двух многоугольников.
Простейший случай - пересечение выпуклых многоугольников.
Одним из наиболее простых алгоритмов для решения этой задачи (кроме, разумеется, простого перебора отрезков, который имеет сложность 0(L • M}s где L и М - количество вершин двух выпуклых многоугольников), является алгоритм Сазерленда Ходжмана. Он сводит исходную задачу к серии более простых задач об отсечении многоугольника вдоль прямой, проходящей через одно из ребер отсекающего многоугольника.
Алгоритм Шеймоса и Хоуи базируется на упорядочивании набора лучей, исходящих из удаленной точки О плоскостн и проходящих через вершины многоугольников, по величине угла. Ключевым моментом является то, что пересечение каждого сектора с выпуклым многоугольником образует четырехугольник, а в случае бесконечного удаления точки О, прямоугольник. Поэтому внутри каждого сектора пересечением многоугольников будет пересечение двух четырехугольников, которое можно найти за константное время. Результирующие фрагменты собираются воедино за один проход секторов, а затем требуется еще один очищающий просмотр для удаления ложных вершин, которые возникают на границах между секторами.
Доказывается, что сложность этого алгоритма 0(L+ М).
В начале обзора существующих методов и алгоритмов рассматривался метод заметания. Он применим для этого класса задач и дает временную сложность вычисления 0(NlogN).
Одним из способов оптимизации алгоритмов решения задач поиска пересечений, и всех задач, которые к ним сводятся — является построение ограничивающих тел {Bounding Volumes) [76-79]. Вокруг каждого объекта описывается тело достаточно простого вида (прямоугольники - на плоскости, прямоугольные параллепипеды с ребрами, параллельными осям - в трех — мерном пространстве). Если эти тела не пересекаются, то и содержащиеся в них объекты не пересекаются. При пересечении описывающих тел поиск пересечений соответствующих объектов ведется обычным образом.
Еще одним методом, позволяющим упростить анализ взаимного расположения объектов и использовать когерентность как на плоскости так и в пространстве, является разбиение плоскости (пространства) {Spatial Subdivision) [47].
С этой целью плоскость разбивается на квадраты и для каждой клетки разбиения составляется список всех тех объектов, которые ее пересекают или содержатся в ней. При неравномерном распределении объектов имеет смысл использовать неравномерное (адаптивное) разбиение плоскости (пространства в случае R3).
Кроме того, одним из методов оптимизации алгоритмов, используемых в настоящее время в машинной графике, является представление графической информации в виде иерархических структур {Hierarchies) [47,78,79]. Стандартными формами таких структур являются восьмеричные, тетрарные и бинарные деревья.
Одной из сравнительно простых структур является иерархия ограничивающих тел. Сначала ограничивающее тело описывается вокруг всех объектов. На следующем шаге объекты разбиваются на несколько компактных групп и вокруг каждой из них описывается свое ограничивающее тело и т. д.
Иерархические структуры строятся и на основе разбиения плоскости (пространства). Каждая клетка разбиения разрезается на части, которые, в свою очередь, также могут быть разбиты, и т.д. При этом каждая клетка разбиения соответствует узлу дерева.
Примером алгоритма, основанного на разбиении объектной области на части является алгоритм Варнака (Warnock) [60]. Исследуемая область плоскости разбивается на четыре равные части и рассматривается, каким образом могут соотноситься между собой графические объекты в каждой из них. Существуют варианты взаимного расположения объектов, которые определяются однозначно. Те части разбиения, в которых однозначность не достигнута, подвергаются дальнейшему разбиению. Возникает вопрос о критерии, на основании которого следует прекратить процедуру разбиения. Он решается исходя из требуемой точности вычисления или отображения.
Логическим развитием рассмотренных иерархических методов представления и обработки данных являются методы, использующие иерархию аппроксимаций. В данном случае структуризации подвергается не объектная область (объектное пространство), а сами объекты, которые представляются в виде иерархии" приближений, верхние уровня которых соответствуют более грубому описанию объектов.
Одним из методов представления ГИ, реализующим иерархию аппроксимаций является полосное дерево, предложенное D.H.Ballard [84]. Исходная кривая представляется в виде иерархии полос, которая имеет топологию бинарного дерева. Корнем этого дерева является полоса, параллельная отрезку, соединяющему концевые точки кривой и имеющая ширину U +M , , где » и Wf - максимальные отклонения исходной кривой влево и вправо от аппроксимирующего отрезка. Это - самый грубый k-ый уровень аппроксимации. Для перехода к (к-І)-му уровню приближения выбирается любая промежуточная точка исходной кривой и строятся две аппроксимирующие полосы (к-І)-го уровня. Процесс разбиения продолжается до тех пор, пока величина Vf+wr превышает некоторую заданную погрешность. К недостаткам этого метода можно отнести избыточность задействованной под хранение структуры памяти - одной вершине полосного дерева соответствует б действительных чисел и 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- окрестностями,
2. Алгоритмы решения задач вычислительной геометрии на базе метода от общего к частному.
В главе предлагаются эффективные алгоритмы решения задач вычислительной геометрии методом от общего к частному на базе иерархических структур представления данных. Приводятся алгоритмы определения взаимного положения графических объектов на плоскости и в пространстве R . Вводится классификация этих алгоритмов по типу порядка обхода усеченных разностных бинарных деревьев представления графической информации и дается оценка временной и емкостной сложности.
3. Оптимизация временных характеристик алгоритмов решения планарных задач вычислительной геометрии на базе иерархических структур представления данных.
В главе дается описание разработанных методов оптимизации временных характеристик алгоритмов решения задач вычислительной геометрии на базе иерархических структур. Приводятся экспериментально полученные сравнительные оценки эффективности различных методов оптимизации временных характеристик.
4. Использование базовых геометрических алгоритмов в прикладных задачах обработки картографической информации.
В главе предлагаются разработанные новые эффективные процедуры решения прикладных тематических задач в ГИС на базе иерархических структур представления данных и метода от общего к частному.
5. Разработка и создание проблемно - ориентированного программного обеспечения для решения задач вычислительной геометрии в ГИС.
В главе приводится описание реализованного программного обеспечения. Дается описание разработанного информационного обеспечения, архитектуры программных комплексов и подсистем, программного обеспечения для ГИС,, реализующих предложенные методы и алгоритмы.
Иерархические структуры представления графической информации и метод от общего к частному в задачах вычислительной геометрии
Построение эффективных моделей описания различных видов входной информации в ГИС является важной задачей при создании различных систем обработки и принятия решений. Основными требованиями к таким моделям являются устранение избыточности, эффективные структуры представления в памяти ЭВМ, обеспечивающие быстрый доступ к отдельным элементам информации, возможность распараллеливания вычислений, а также эффективность процедур принятия решений на базе таких моделей.
В работах [9-15] был предложен новый подход к обработке болыпеформатных видеоданных (сложная графическая информация, полутоновые монохромные и полноцветные изображения) на базе локальных однородных хорошо приспособленных базисных функций (ДОХПБФ), предопределяемые ими иерархические структуры представления данных и методы принятия решений на этих структурах. .. На основе ЛОХЛБФ были разработаны эффективные алгоритмы адаптивного сжатия и фильтрации [П-14] с контролем максимальной покоординатной ошибки, на выходе которых исходная информация представляется в виде иерархических регулярных разностных бинарных деревьев существенных отсчетов.
Каждый уровень отсчетов отбирается с использованием ЛОХЛБФ и представляет исходные данные с некоторой контролируемой погрешностью в виде иерархической структуры. Чем более высокий уровень иерархии представления используется, тем точнее описывается исходное поле. В совокупности иерархическая структура содержит неизбыточный набор существенных отсчетов и ошибок описания на соседних уровнях, позволяющих провести восстановление исходной информации с заданной точностью. Указанная структура может быть представлена в виде усеченных бинарных разностных деревьев для различного типа графических данных в геоинформационных технологиях и системах.
Таким образом, последовательность каждого уровня иерархии представляет собой прореженную вдвое последовательность следующего уровня, а последовательность нулевого уровня представлена двумя точками. Отсчеты исходной последовательности упорядочиваются в иерархическую структуру, соответствующую двоичному (бинарному) дереву существенных отсчетов (рис.1.2,а). При этом каждый уровень такого дерева содержит отсчеты соответствующего уровня. Отсчеты данного уровня двоичного дерева составляют множество отсчетов, которые необходимы для получения последовательности отсчетов соответствующего уровня иерархии из последовательности предыдущего уровня.
Mv:/ 2iv (1 / 2V-\ I v 0. (1.3) Учитывая (1.1), (1.2) и (1.3), уровень v двоичного дерева содержит отсчеты р% принадлежащие последовательности ранга (уровня) v, но отсутствующие в последовательностях предыдущих уровней иерархии (рангов) (р,р\ ... ,р4 1)-
При замене в бинарном дереве отсчетов значений отсчетов ошибками аппроксимации, будет получено разностное бинарное дерево для изображений. В случае исключения вершин, со значением ошибок аппроксимации не превышающих заданную величину точности представления исходного изображения, формируется усеченное разностное бинарное дерево.
Сформированное бинарное дерево отсчетов соответствует разбиению плоскости задания изображения на последовательность вложенных прямоугольных и квадратных областей.
Можно построить бинарное дерево отсчетов либо усеченное разностное бинарное дерево при разбиении плоскости заданного изображения на последовательности вложенных треугольников. На рис. 1.4. приведен пример такого разбиения и получено соответствующее усеченное бинарное дерево отсчетов.
Факт представления графической информации в виде усеченных бинарных разностных структур, которые относятся к группе иерархических методов представления и, в частности,, являются иерархией аппроксимаций, позволяет эффективно использовать метод от общего к частному в задачах анализа графической информации [14-16].
Геометрические задачи решаются путем последовательных приближений: поиск решения начинается с корня иерархии (корень дерева) и завершается при возможно более грубом представлении данных. Информация уточняется там, где это необходимо, то есть на участках, определяющих решение задачи, используется более точное описание данных.
Это позволяет производить обработку методом от общего к частному, когда искомое решение, либо искомое решение и область его поиска, найденные на данном уровне структуры, поэтапно уточняются на основе последовательного анализа графической информации по мере спуска на нижележащие уровни.
При этом на верхних уровнях дерева формируются некоторые промежуточные решения, которые, во-первых, могут использоваться как некоторое приближение к искомому решению, во-вторых, они применяются для оценок перспективных направлений дальнейшего поиска окончательного решения. При реализации такого подхода важно уметь получать критерии, используя которые можно осуществлять отбор перспективных участков аппроксимаций, уточнение которых заведомо приведет к искомому решению. В противном случае возможен неверный результат. Синтез таких критериев при решении широкого класса задач требует в каждой вершине дерева на каждом уровне иметь ограничивающие оценки, такие, что исходная информация, соответствующая данным существенным отсчетам не может отклониться за их пределы. Указанная информация отсутствует в усеченных бинарных разностных деревьях. Учитывая это, было предложено при решении задач анализа графических данных использовать усеченные бинарные разностные деревья с D-окрестностями.
Вычисление расстояния от точки до кривой на плоскости
Пусть на плоскости заданы: точка с координатами (p,q) и кривая последовательностью точек fa yj, i=I,2 л, предварительно обработанная по алгоритмам на базе ЛОХПБФ и представленная в виде УБРД с D- окрестностями: К = ) Xj,yj,rjdj,kj)], где г,- - ранг вершины, d/ — максимальная величина отклонения точек кривой от аппроксимирующего отрезка, к/ - код вершины, определяющий наличие подчиненных вершин, j= ],2,...,N. Требуется определить расстояние от заданной точки до исходной кривой R minRi{(p,q)[(Xiyi);(xn.lyH/)]}, где Rt -расстояние от точки (p,q) до отрезка с координатами
Для решения поставленной задачи методом от общего к частному необходимо ввести критерий поуровневой оценки искомого значения с целью отбора перспективных участков поиска окончательного решения при движении сверху вниз по структуре представления исходной кривой. Для этого введем следующие определения. Пусть точки айве координатами (ха, yt) и (хъ, yt) соответственно являются концами отрезка [а,Ь]. Как отмечено выше, на к-ом уровне представления исходная кривая определяется набором отрезков, соединяющих существенные отсчеты не ниже к-го уровня, и при этом гарантировано, что исходная кривая не может на данном участке выходить за пределы jD-окрестности соответствующего аппроксимирующего отрезка.
На первом этапе решения задачи вычисления расстояния от точки до кривой рассматривается аппроксимирующая кривая к-го уровня и формируется список составляющих ее отрезков для перехода к отсчетам (к-І)-го уровня. В список включены номера всех отрезков с числами А, В для которых не существует другого отрезка структурированной кривой с числами А , В такого, что В1 А. Ясно, что расстояние от заданной точки до исходной кривой будет равно расстоянию до частей исходной кривой, соответствующих отрезкам, попавшим в список. Для всех отрезков, попавших в список, опускаясь по структуре, выбираются существенные отсчеты (к І)-го уровня и тем самым восстанавливаются соответствующие части структурированной кривой (к-ї)-го уровня. Для отрезков, составляющих эти части, создается список отрезков, удовлетворяющих приведенному выше условию. По этому списку с помощью того же условия формируется новый список и т.д., пока за конечное число шагов не придем к отрезкам кривой самого нижнего уровня. Минимальное из расстояний до этих отрезков и будет искомым расстоянием. Для того, чтобы найти ближайшую к заданной точку на кривой, достаточно найти эту точку на отрезках кривой, попавших в последний список.
Из описания алгоритма видно, что в данной задаче решение об отборе участков структур, подлежащих дальнейшему уточнению, зависит от информации обо всех уже отобранных к уточнению участках структуры, то есть, эта задача имеет глобальное правило отбора и алгоритм ее решения ориентирован на поуровневый обход деревьев представления данных. Время работы данного алгоритма складывается из двух частей: затрат первого шага - порядка N ключевых операций и затрат на спуск по дереву до листовых вершин - порядка г ключевых операций для дерева соответствующей глубины. Таким образом, временная сложность алгоритма есть величина порядка 0(N+r).
Максимальная емкостная сложность алгоритма определяется для случая, когда все точки кривой равноудалены от заданной точки (p,q). В этом худшем случае на последнем шаге алгоритма необходимо хранить информацию обо всех т отрезках нижнего уровня аппроксимации кривой. То есть емкостная сложность алгоритма в худшем случае имеет вид 0(т).
В качестве критерия поуровневой оценки искомого значения с целью отбора перспективных участков поиска окончательного решения при движении сверху вниз по структуре представления исходных кривых будем использовать неравенства (2.5) - (2.7). Ключевая операция алгоритма идентична ключевой операции алгоритма 2.1.1.
На первом этапе решения задачи рассматриваются самые верхние кгые уровни иерархического представления всех кривых и для всех кривых формируется единый список составляющих их отрезков, перспективных в плане поиска окончательного решения, для перехода к отсчетам (кг1)-го уровня. В список включены номера кривых и номера отрезков этих кривых с числами А, В для которых не существует другого отрезка структурированных кривых с числами А , В такого, что В А. Очевидно, что минимальное расстояние от заданной точки до исходных кривых будет равно минимальному расстоянию до частей исходных кривых, соответствующих отрезкам, прпавшим в список. Для всех отрезков, попавших в список, отбираются по номерам кривые и для каждой из них, спускаясь по структуре, выбираются существенные отсчеты (kj-I)-zo уровня и тем самым восстанавливаются соответствующие части аппроксимирующих кривых (kj-l)-zo уровня. Для всех отрезков, составляющих эти части, создается список отрезков, удовлетворяющих приведенному выше условию. По этому списку с помощью того же условия формируется новый список и т.д., пока за конечное число шагов не придем к отрезкам кривых самого нижнего уровня. Минимальное из расстояний до этих отрезков и будет искомым расстоянием, а соответствующая кривая — ближайшей к заданной точке кривой из множества кривых.
Допустим, на плоскости заданы кривая последовательностью точек fay), i=l,2,...,n, предварительно обработанная по алгоритмам на базе ЛОХПБФ и представленная в виде УБРД с D- окрестностями, и массив из m точек с координатами (pj,qj,), j=l,2,..,m. Требуется определить ближайшую к заданной исходной кривой точку из массива, то есть: R=min rij{(p [(x,y ;(xl+jy +i)J}. где г if -расстояние от точки (pj,gj), j=I,2,..,m до отрезка с координатами [(ху$; (хі /у,+ и)] (1=1,2, ...,п-1). В качестве критерия поуровневой оценки искомого значения с целью отбора перспективных участков поиска окончательного решения при движении сверху вниз по структуре представления исходной кривой используются неравенства (2.5) - (2.7). Ключевая операция алгоритма идентична ключевой операции алгоритма 2,1.1.
На первом этапе решения задачи рассматривается самый верхний к-ый уровень иерархического представления кривой и формируется список составляющих его отрезков, перспективных в плане поиска окончательного решения, для перехода к отсчетам (к-І)-го уровня. В список включены номера соответствующих точек и номера отрезков с числами А, В для которых не существует другого отрезка структурированной кривой с числами Л , В такого, что В] А. Очевидно, что информация о паре: точка из множества, ближайшая к заданной исходной кривой и соответствующий отрезок k-ого уровня, при отборе по такому критерию непременно будет внесен в список.
Выбор эффективного значения максимальной длины сортируемых отрезков
Для определения оптимальной пороговой величины сортируемых отрезков верхнего уровня, изучалось распределение отрезков по длинам для различных наборов кривых. Для картографической информации это распределение имеет вид нормального распределения Гаусса. Такой вид распределения отрезков по длинам позволяет предположить существование некоторого значения максимальной длины сортируемых отрезков АЭфф, обеспечивающего эффективное значение общего количества рассматриваемых на первом шаге отрезков ВУ Для определения эффективного значения максимальной длины сортируемых отрезков Аэффу введем функцию F(An0F) зависимости общего количества отрезков верхнего уровня, обрабатываемых на первом этапе алгоритмов, от значения пороговой величины А„ор выбираемой максимальной длины сортируемых отрезков верхнего уровня. Для этого разобьем диапазон изменения длин отрезков верхнего уровня на q зон - Ai, А2, ... , Аь ... , Ад. Обозначим через п„ где І є Ah количество отрезков верхнего уровня, значения длин которых лежат в диапазоне At Л Ai+t. В качестве пороговых значений будем выбирать А1„ор, равные граничным значениям длин отрезков, попадающих в зону At. Условимся обозначать число отрезков верхнего уровня, значения длин которых лежат в границах зоны Л „ор, как щ, і є А"ор- Апор.
Здесь первое слагаемое определяет количество отрезков из числа отсортированных, нижние концевые точки которых попадут в область поиска, второе- количество безусловно рассматриваемых "длинных" отрезков.
Эффективность полученного в результате предложенного алгоритма значения АЭфф проверялось для различных наборов данных. На рис.3.б. приведены графики зависимости времени решения задачи поиска точек пересечения и участков совпадения для различных множеств кривых от величины задаваемого значения А„ор и найденные по описанному выше алгоритму значения А3фф. Приведенные данные подтверждают эффективность предложенного метода определения максимальной длины сортируемых отрезков верхнего уровня аппроксимации.
Этот подход реализуется в методе, основанном на множественности объектов. Общая идея метода иллюстрируется на рис.3.7(6). Требование однократности выполнения вспомогательных операций для аппроксимирующих отрезков ведущей кривой приводит к необходимости одновременного спуска по структуре для всех обрабатываемых кривых.
Поиск решения начинается с обработки верхнего уровня структурированного представления кривых. Очевидно, что участки кривых не пересекаются, если не пересекаются D- окрестности соответствующих им аппроксимирующих отрезков. Таким образом, решение об отборе каждой пары отрезков, подлежащих уточнению, может приниматься независимо от других, а задача по своему типу имеет локальное правило отбора. Поэтому при разработке алгоритма можно было бы ориентироваться на прямой порядок обхода деревьев представления. При этом для каждого аппроксимирующего отрезка кривой из первого множества выбираются данные из структуры, определяются экстремальные координаты, коэффициенты проходящей через отрезок прямой, а затем проводятся другие связанные с задачей расчеты. В соответствии с изложенным выше подходом, все предварительные операции для отрезков ведущей кривой из первого множества производятся однократно. При этом изменяется порядок обхода структур. Вместо одновременного прямого обхода структуры для очередной пары кривых, выполняется поуровневый просмотр деревьев ведущей кривой из первого множества и всех кривых из второго множества. Все эти положения учтены в следующем алгоритме определения общих точек для двух множеств кривых.
Отрезки верхнего уровня аппроксимации кривых второго. множества упорядочиваются по не убыванию ординаты их нижней конечной точки, определяется эффективное значение граничной длины сортируемых отрезков Лэфф. Поочередно рассматриваются кривые первого множества. Для каждой из них в цикле обрабатываются отрезки верхнего уровня аппроксимации. Для отрезка производятся вспомогательные вычисления. Определяются экстремальные координаты области поиска кандидатов на пересечение: r=A+d\+Ajw+dm3X; хт\п=хгг, ym\tryM dmm; xmi„rxi+r; утах=У&г. Используя данные об отсортированных отрезках второго множества, методом бинарного поиска определяются те из них, нижние конечные точки которых лежат в области поиска. К ним добавляются все отрезки верхнего уровня второго множества с длиной, превышающей величину А . Для всех таких отрезков осуществляется поиск пересечения их D- окрестности с D- окрестностью текущего отрезка ведущей кривой и, если пересечение найдено, данные заносятся в список. Для всех отрезков кривых второго множества в список помещается одна общая заголовочная запись о соответствующем отрезке ведущей кривой.
Сформированный список обрабатывается путем одновременного восстановления отрезков более низкого уровня для всех его элементов. Для восстановленных отрезков осуществляется поиск пересечения их 23-окрестностей с -окрестностями отрезков ведущей кривой, и, если пересечение найдено, данные заносятся в выходной список. Структура его сохраняется. Список обрабатывается до тех пор, пока ранг всех содержащихся в нем отрезков не будет равен единице. Затем для отрезков из списка формируются записи в выходном массиве о найденных точках пересечения и участках совпадения. Если возможно, участки совпадения сливаются, и алгоритм заканчивает работу.
Алгоритм построения поля квадратов (списка окон) объектной области
Базовой геометрической функцией алгоритма построения поля квадратов объектной области, которая многократно используется при решении задачи, является функция определения положения частей кривых относительно области. Эта функция была адаптирована к случаю, когда область имеет форму квадрата со сторонами, параллельными осям координат, что существенно снизило ее вычислительную сложность.
Поле квадратов — это система списков (один список на каждый квадрат), содержащих информацию об объектах, принадлежащих каждому квадрату, или пересекающих его. Входной информацией для работы алгоритма построения списка окон является метрическое описание линейных и площадных объектов, координаты привязки дискретных объектов, а также координаты левого нижнего и правого верхнего углов прямоугольной рамки, охватывающей объектную область, и шаг дискретизации объектной области / (размер окна). В процессе работы алгоритма необходимо сформировать списки окон поля квадратов. Каждый список содержит информацию об одном окне: количество объектов, взаимодействующих с ним по одному из правил - пересечение или принадлежность; идентификаторы этих объектов - это могут быть коды, номера и т. п,, в зависимости от используемой модели описания объектов; вид взаимодействия; для линейных и площадных объектов - номера начальной и конечной точек участков метрики, принадлежащих квадрату (в случае пересечения). Предлагаемый алгоритм является однопроходным по отношению к объектной области. Если очередной рассматриваемый объект - дискретный, то определяется квадрат, содержащий точку с координатами привязки этого дискретного объекта. Локализация точки в регулярной сетке с заданным шагом очень проста. Для того, чтобы определить номер квадрата по горизонтали, достаточно взять целое от.-., деления абсциссы на шаг сетки и прибавить единицу, аналогично просто определяется номер квадрата по вертикали. Если нижний левый угол рамки объектной области не совпадает с началом координат, вносятся необходимые поправки. Список, соответствующий квадрату, содержащему рассматриваемый дискретный объект, обновляется. Корректируется количество взаимодействующих с ним объектов, вносится информация о новом объекте.
Процесс спуска по структуре на каждом участке может быть прерван на некотором промежуточном уровне, если будет определено, что рассматриваемый квадрат с соответствующим расширением . не взаимодействует с аппроксимирующими отрезками данного уровня. В случае наличия реального взаимодействия, происходит уточнение информации до исходной метрики и соответствующий список окна обновляется.
Отдельная ветвь алгоритма обрабатывает ситуацию, когда обе точки аппроксимирующего отрезка самого верхнего или промежуточного уровня аппроксимации локализованы в одном окне и расстояния от этих точек до сторон квадрата меньше приписанной к этому отрезку величины с?. Очевидно, что в этом случае часть метрики, аппроксимируемая этим отрезком, полностью принадлежит квадрату.
