автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Исследование методов, разработка алгоритмического и программного обеспечения пространственного анализа графической информации

На правах рукописи

Утешева Тамара Шатовна

ИССЛЕДОВАНИЕ МЕТОДОВ, РАЗРАБОТКА АЛГОРИТМИЧЕСКОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПРОСТРАНСТВЕННОГО АНАЛИЗА ГРАФИЧЕСКОЙ ИНФОРМАЦИИ

Специальность: 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Нижний Новгород, 2005

Работа выполнена в НИИ прикладной математики и кибернетики Нижегородского государственного Университета им. Н.И. Лобачевского

Научный руководитель:

доктор технических наук, профессор Ю. Г. Васин

Официальные оппоненты:

доктор технических наук, Киричук B.C.

Ведущая организация:

доктор технических наук,

профессор В. И. Швецов

Вычислительный центр РАН, г. Москва

Защита состоится «З*7» и ЮИлЛ"

2005 г . -/в чалов а

ер

заседании диссертационного совета Д 212.166.13 Нижегородского государственного университета им. Н. И. Лобачевского по адресу: 603950, г. Нижний Новгород, пр. Гагарина, 23.

С диссертацией можно ознакомится в научной библиотеке Нижегородского государственного университета им. Н.И.Лобачевского.

Автореферат разослан 2005 г.

Ученый секретарь диссертационного совета

кандидат физ.- мат. наук, доцент

В. П. Савельев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

Проблемы вычислительной геометрии в ГИС усугубляются необходимостью осуществлять обработку ГИ очень большого объема в

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

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

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

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

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

Значительный вклад в развитие методов обработки графической

информации и изображений внесли российские ученые А.С. Лебедев, Н.Н.Красильников, Ю.Г. Васин, В.В. Александров, Ю.М. Штарьков, В.А.Виттих, В.М. Шарыганов, В.В. Сергеев, В.А. Сойфер, В.П. Пяткин, а также зарубежные ученые Т. Павлидис, Ф. Препарат, М. Шеймос, У. Претт, Р. Грехем, Д. Роджерс, Д. Баллард, В. Буртон, О. Гунтер, X. Самет и другие.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

"ГИС-Терра";

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

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

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

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

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

Структура и объем работы Диссертация состоит из введения, пяти глав, заключения, списка литературы. Объем основного текста работы - 120 машинописных страниц, список литературы включает 106 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Приведены основные требования, предъявляемые к методам и алгоритмам вычислительной геометрии в ГИС. Сделан вывод о

необходимости развития методов и алгоритмов, обладающих следующими важными достоинствами:

• высокая вычислительная производительность и емкостная эффективность;

• общий методологический подход к решению всех геометрических задач;

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

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

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

В первой главе вводится понятие иерархических структур представления данных в виде бинарных деревьев, усеченных бинарных разностных деревьев (УБРД), усеченных бинарных разностных деревьев с £>-окрестностями (УБРДЦ), а также метода от общего к частному для задач вычислительной геометрии на базе усеченных бинарных разностных деревьев с ГУ- окрестностями.

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

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

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

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

Вводится понятие Б- окрестности и усеченных разностных деревьев с Б - окрестностями.

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

Рис. 1.

На рис. 1. представлено усеченное бинарное разностное дерево с Б-окрестностями, описывающее кривую на плоскости. Здесь х, - отсчеты

вершин верхнего уровня, А. -покоординатные ошибки восстановления.

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

т

кт(а],а2,...,ат), £а, =1, при значении т= 2 £(а|, а2), где а| = а2 = 0.5, для

отсчетов в вершинах каждого уровня дерева справедлив следующий закон восстановления координат (кусочно-линейная аппроксимация):

Здесь х^ - вектор отсчета с координатами (х^ ), г - глубина

усеченного дерева.

Б- окрестности для рассматриваемого случая представляются следующим образом. Каждой вершине дерева поставлены в соответствие

две величины (¡^ и равные максимальному расстоянию от точек

исходной кривой, расположенной между отсчетами

до отрезков, задаваемых этими отсчетами.

, ] = 0-2к-1+\),(1-2к-1 +2),...,(г-1);

здесь К - расстояние между точкой исходной кривой и аппроксимирующим отрезком.

Соответствующие области и есть D-окрестности отрезков (Рис.2.). Таким образом, исходные данные представляются в виде иерархии аппроксимирующих отрезков и соответствующих им D-окрестностей, позволяющих, спускаясь по структуре, получать все более точное описание

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

обработку графической

Рис 2.

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

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

для оценок перспективных направлений дальнейшего поиска окончательного решения.

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

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

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

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

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

Если ключевой операцией рассматриваемого алгоритма является определение расстояния между двумя элементарными составляющими объектов (точка, отрезок, треугольник в R3), и расстояние между участками аппроксимаций на к-ом уровне равно г, то расстояние R, между участками исходных объектов, соответствующих данным участкам аппроксимаций удовлетворяет неравенствам:

maxf 0, r-drd2} <=R<=r+ maxf dh d2},

где di и d2 - значения величин соответствующих D — окрестностей аппроксимирующих элементов, d2 = 0, если второй объект - точка, луч или плоскость в R3.

Таким образом, для каждой пары аппроксимирующих участков (аппроксимирующего участка и точки или луча или плоскости) существует два числа А, В такие, что расстояние R между соответствующими частями исходных кривых удовлетворяют неравенствам А <= R <= В, где А= maxf 0, r-drd2}, В= г + тах{du d2}.

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

S:A- <ш1п{5г.}, 1 <г <N, где N - количество рассматриваемых на

к- ом уровне пар участков аппроксимаций.

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

Критерий отбора участков аппроксимаций, подлежащих дальнейшему восстановлению для задач поиска пересечения объекта (кривая, поверхность) с лучом, имеет вид:

S : {[{р, q, î ), оо) f| ([а, Ь] v Aabc) = l)v(h<d);

где (p.q.s)- координаты точки, из которой исходит луч, h - расстояние от точки, из которой исходит луч до аппроксимирующего отрезка [а, Ь] или аппроксимирующего треугольника abc, d - величина соответствующей D-окрестности.

Критерий отбора перспективных участков аппроксимаций для алгоритма определения положения точки с координатами (p,q) относительно области имеет вид:

S: (ymm-d <q< J>m,n) V (ymax< q < Упы+d) V (h<d),

где J'min» Утях - экстремальные ординаты отрезка, аппроксимирующего участок исходной кривой, определяющей границу области, d - характерная величина его D - окрестности, h - расстояние от рассматриваемой точки до аппроксимирующего отрезка.

Критерием отбора для алгоритма определения участков примыкания двух кривых является неравенство:

S: R <eps + dx + d2,

где R - расстояние между аппроксимирующими отрезками двух кривых, d\ и d2 - размеры соответствующих D - окрестностей этих отрезков, eps -параметр задачи.

Критерий отбора участков аппроксимаций, подлежащих дальнейшему восстановлению, для задачи определения участков совпадения и точек пересечения двух кривых имеет следующий вид: S: ((Л,- h2<0) Л ( h3- h4<0)) V (r,< d, + d2),

Где hi, hi - расстояния от концевых точек первого аппроксимирующего отрезка до прямой, определяемой вторым аппроксимирующим отрезком; hi, h4 - расстояния от концевых точек второго отрезка до прямой,

определяемой первым отрезком; г„ ¡=1,2,3,4 - расстояния от концевых точек одного отрезка до другого отрезка.

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

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

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

аппроксимирующий участок к - го уровня, q - ключевая операция задачи, 5

- критерий отбора рассматриваемой задачи, г - глубина усеченного дерева, N

- количество аппроксимирующих участков к - го уровня.

где

существенные отсчеты, ограничивающие

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

где существенные отсчеты, ограничивающие

Ь- Ъ- Ъ- 1г

аппроксимирующий участок к — го уровня, ;>У :УАХ :.1>У ;,{№}

множество отобранных на предыдущих этапах алгоритма участков структур, подлежащих уточнению.

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

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

порядка О(п]), когда задача состоит в определении взаимного положения с точкой, лучом или плоскостью, и О(щ-пт), когда анализируется пространственное отношение с кривой или поверхностью, нижний уровень иерархического представления которых состоит из АГ? элементарных составляющих.

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

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

Рис.3.

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

Эксперименты показали, что вклад первого шага алгоритмов в общее время решения велик и составляет 45-75%. На Рис.3, приводятся графики изменения числа рассматриваемых пар отрезков по шагам при определении расстояния между двумя кривыми.

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

Обоснован выбор вида и размеров окон локализации поиска для всех предложенных алгоритмов.

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

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

отрезков:

НЛпор) = к-р-{Апор + В)2+ (9)

Здесь первое слагаемое определяет количество отрезков из числа отсортированных, нижние концевые точки которых попадут в область поиска, второе- количество безусловно рассматриваемых "длинных" отрезков.

Величина р - средняя для данного множества плотность отрезков верхнего уровня:

Р (*птах ~ ^' ^тах ~ >тт ^

Слагаемое В и коэффициент к зависят от типа рассматриваемой задачи. Вид функции (9) позволяет предположить наличие минимума вблизи ATJX.

На рис.4, приведен график изменения слагаемых и результирующее значение функции ¥(АЮ), построенные с использованием средних величин А и dдля картографической информации.

«¿лор)

01 5 10 15 20 25 30 35 40 45 50 55 А}фф

рис.4.

Был предложен метод определения эффективного значения Аэфф параметра минимизирующий значение для некоторого

множества кривых.

Эффективность полученного в результате предложенного алгоритма значения Аэфф была подтверждена экспериментально.

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

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

Разработано правило определения связанности отрезка верхнего уровня с Б- окрестностью с соответствующим квадратом. Для этого было введено понятие расширенного квадрата. Правило определения связанности унифицировано выбором параметров расширенного квадрата, равными [/ + 2й?тах х / + 2с1т„Ц, где / - шаг регулярной сетки, dmaK - максимальное значение размера Б- окрестностей всех отрезков верхнего уровня объектной области.

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

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

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

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

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

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

Полученные временные характеристики позволяют сделать вывод о том, что основной вклад в повышение эффективности алгоритмов вносит использование метода от общего к частному на базе представления исходной информации в виде иерархических структур - среднее экспериментально полученное значение - 310 раз. Использование сортировки отрезков верхнего уровня аппроксимаций позволяет снизить время решения задач еще в 1,8 - 2,7 раз. Учет фактора множественности сокращает временные затраты на 20 - 30%. Среднее экспериментально полученное значение снижения временных затрат при применении поля квадратов составило 15-19 раз. А общий выигрыш по времени от применения всех предложенных методов в ходе эксперимента составил в среднем 840 и достигал 2400 раз.

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

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

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

В общем случае процесс сегментации состоит в следующем. Метрической части каждого исходного объекта - линейного или площадного сопоставляется узел сегментной модели:

1) в точке пересечения метрики рассматриваемого объекта с метрикой любого другого объекта из объектной области;

2) в двух точках - начала и конца участка совпадения с некоторой точностью eps с любым другим объектом;

3) в точке, ближайшей к первой или последней точке какого-либо объекта, удаленной не далее, чем на величину eps (сегментация концевыми точками линейных объектов).

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

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

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

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

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

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

Предлагаемый алгоритм является однопроходным по отношению к объектной области.

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

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

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

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

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

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

Основными требованиями, предъявляемыми к разработанному программному обеспечению были:

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

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

Было разработано:

1. Информационное обеспечение:

• Обоснован выбор структуры хранения УБРД с переменным количеством адресных ссылок и кодом вершин дерева.

• Разработаны структуры рабочих массивов для реализации двух основных типов обхода УБРД- прямого и поуровневого.

• Разработан формат представления файла протокола, совместимый с информационным обеспечением системы редактирования объектов ШЖ в общей технологии ГИС-ТЕРРА.

• Разработан формат файла кодов, совместимый с информационно -терминологической системой классификатора и форматом интегрального файла в рамках общей технологии ГИС.

• Разработан формат списков окон.

2. Архитектура программных комплексов:

• Реализована модульная схема построения ПО, обеспечивающая последовательное и вложенное использование модулей.

• Обоснован и реализован эффективный выбор стратегии запросов к базе данных.

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

Все программы были реализованы на языке программирования C+ + . В качестве инструментальных средств для создания и отладки ПО использовалась интегрированная среда разработки Borland C++ Builder.

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

• высокая вычислительная производительность;

• общий методологический подход к решению всех геометрических задач;

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

Библиотека содержит функции для решения следующих задач:

Для определения взаимного положения точек и кривых: определение расстояния от точки до кривой; поиск кривой из множества, ближайшей к заданной точке; поиск точки из множества, ближайшей к заданной кривой;

Для определения взаимного положения точек и областей: определение положения точки относительно области; определение положения точек множества относительно области; определение точек из множества, лежащих в eps-окрестности области вне ее; определения положения части заданных точек из некоторого множества с отнесением точек, лежащих на границе, в соответствии с заданным режимом;

Для определения взаимного положения кривых: определение расстояния между двумя кривыми; определение точек пересечения и участков

совпадения для множества кривых с подмножеством и для двух множеств кривых; поиск близких кривых в заданном множестве;

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

Для определения взаимного положения областей: определение положения множества контуров относительно многосвязной области; для областей из множества построение пересечения с заданной областью;

Для подготовки данных используются функции: программа построения структурированного представления кривой; программа расстановки адресов в структурированном представлении кривой;

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

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

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

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

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

Реализована подсистема формирования пространственно обусловленных связей. Каждый вид связей формируется при помощи отдельного приложения.

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

Подсистема содержит программные средства, позволяющие формировать связи следующих типов:

• Определение точек пересечения и участков совпадения для объектов одной группы или объектов одной группы с объектами другой (таких групп может быть несколько);

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

• Определение объектов, расположенных внутри площадных;

• Определение внутренних контуров площадных объектов;

• Нахождения условных дискретных знаков, расположенных внутри площадных объектов;

• Установление связей между границами и полосой окраски;

• Установление связей между криволинейными подписями и соответствующими линейными объектами.

Комплекс программ используется:

• для установления связей в базах картографических данных;

• в подсистеме контроля качества;

• при решении некоторых других специфических задач.

Предложена и реализована учебно-исследовательская система "Методы и алгоритмы вычислительной геометрии на базе иерархических структур

представления графической информации ". Система предназначена для лабораторной и научно-исследовательской работы студентов 3-4 курсов факультета ВМК, специализирующихся на кафедре «Интеллектуальные информационные системы и геоинформатика».

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

Разработаны и программно реализованы алгоритмы: для определения таимиого положения точек и кривых; для определения взаимного

положения точек и областей; для определения взаимного положения кривых; для определения взаимного положения кривых и областей; для определения взаимного положения областей.

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

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

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

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

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

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

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

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

2. Ю.Г. Васин, А.Д. Крахнов, Т.Ш. Утешева Определение видимости точек поверхности, задаваемой изолиниями // 5-ая Международная конференция "Распознавание образов и анализ изображений: Новые информационные технологии РОАИ-5-2000: Труды конференции -Самара, 2000. -С. 230-232.

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

4. Ю.Г Васин, А.Д. Крахнов, Т.Ш. Утешева Эффективность решения задач дискретной геометрии при определении безопасного маршрута водного транспорта // Всесоюзное научно - техническое совещание "Автоматизация процессов обеспечения безопасности водного транспорта" - Ленинград, 1991. - С. 70-71.

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

6. Ю.Г. Васин, А.И. Земскова, А.Д. Крахнов, Н.Н. Крахнова, Е.М. Мартынова, В.П. Новин, Т.Ш. Утешева Комплекс программных средств для установления пространственно-обусловленных связей объектов в картографических базах данных // Распознавание образов и анализ изображений: Новые информационные технологии РОАИ / Тезисы докладов - Н.Новгород, 1997. - С. 25-26.

7. Ю.Г. Васин, А.Д. Исаев-Иванов, Ю.И. Солодухо, В.И. Малыженков, Т.Ш. Утешева, Т. В. Фирсова Система контроля качества цифровых топографических карт и планов городов // Распознавание образов и анализ изображений: Новые информационные технологии РОАИ / Тезисы докладов.- Н.Новгород, 1997. - С. 27 - 30.

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

9. Ю. Г. Васин, А. Д. Крахнов, Т. Ш. Утешева Методы дискретной геометрии в задачах обработки сложной графической информации // 7 Международная конференция по распознаванию образов и анализу изображений: Новые информационные технологии PRIA-7-2004: Труды конференции - С. Петербург, 2004. - Т.З. - С. 954-956.

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

Подписано в печать 25.05.2005. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1. Зак. 737. Тир. 100.

Типография Нижегородского госуниверситета Лицензия №18-0099 603000, Н. Новгород, ул. Б. Покровская, 37.

1 5 fí ЮЛ 2C05

hч

Аннотация

Введение

Глава 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: вычисление расстояния от точки до поверхности; вычисление расстояния между поверхностью и кривой; вычисление расстояния между двумя поверхностями; алгоритм определения пересечений луча с поверхностью.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.