Автореферат

Москва – 2011

Диссертация выполнена на кафедре Информационно-измерительных систем Московского государственного университета геодезии и картографии (МИИГАиК)

Научный руководитель: доктортехнических наук, профессор Майоров Андрей Александрович

Официальные оппоненты: доктортехнических наук, профессор Цветков Виктор Яковлевич, кандидат технических наук Матвеев Александр Станиславович

Ведущая организация: ФГУП “Госцентр “Природа”

Защита состоится « 15 » декабря 2011 г. в 10 часов на заседании диссертационного совета Д.212.143.03 в Московском государственном университете геодезии и картографии (МИИГАиК) по адресу: 105064 Москва, Гороховский пер., 4, зал заседания Ученого совета.

С диссертацией можно ознакомиться в библиотеке Московского государственного университета геодезии и картографии (МИИГАиК).

Автореферат разослан « 11 » ноября 2011 г.

Ученый секретарь диссертационного совета Климков Ю.М.

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

Актуальность темы.

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

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

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

1. Обзор и анализ методов представления и применения ЦМР.

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

5. Исследование алгоритмов анализаповерхностей.

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

Научная новизна работы.

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

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

Разработан высокопроизводительный алгоритм построения триангуляции Делоне на основе комбинации алгоритмов инкремента и заметающей линии.

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

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

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

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

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

Изложенные в диссертации материалы научных исследований докладывались и обсуждались на 65-ой научно-технической конференции студентов, аспирантов и молодых ученых МИИГАиК (апрель 2010 г.). Структура и объем диссертации.

Диссертация состоит из введения, трёх глав, заключения, списка литературы, приложения и глоссария. Общий объем работы составляет 101 страница машинописного текста, 60 рисунков, 5 таблиц. Публикации.

По материалам диссертации опубликовано 4 работы, две из которых в журнале, включенномв переченьВАК.

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

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

В первой главе “Обобщение цифровых моделей рельефа” представлены понятия о цифровой модели рельефа, методы представлений и применений цифровых моделей рельефа.

Во второй главе “Анализ алгоритмов построения цифровых моделей рельефа” представлены и проанализированы известные алгоритмы построения триангуляции Делоне.

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

В главе 2 представлены алгоритмы: инкремент, заметающая линия и новый алгоритм, который основывается на алгоритме заметающей линии и комбинации с характерного алгоритма инкремента.

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

Алгоритм инкремента. Все инкрементные алгоритмы имеют в своей основе простую идею последовательного добавления точек в частично построенную триангуляцию Делоне. Формально это выглядит так.

Шаг 1. Построениевыпуклой оболочки.

Шаг 2. Триангуляция выпуклой оболочки.

Шаг 3. Выполняется цикл по N для всех точек в соответствии с шагами 4–6.

Шаг 4. Добавляется n-я точка в уже построенную структуру триангуляции, то есть находится треугольник (построенный ранее), в который попадает очередная точка.

Шаг 5. Находится треугольник, содержащий новуюточку.

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

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

Если точка попадает на внутренние треугольники, то разделяем этот треугольникнатри новых треугольника (рис. 1).

Рис. 1. Две ситуации, возникающие при триангуляции после добавления новой внутренней точки. Шаг 6. Проверяются все треугольники на соответствие условию Делоне с соседними треугольниками и выполняются необходимые перестроения (рис. 2).

Рис. 2. Переброска ребра Конец алгоритма

Методы повышения быстродействия вычисления алгоритма инкремента.

1. Построение первоначального треугольника p1p2p3, покрывающего всё множество исходных точек Pi, i=1,2,3,…,N (рис. 3).

000

Рис. 3. Первоначальный треугольник p1p2p3

2. Использование деревадляхранения триангуляций D.

Рис. 4. Эффект добавления точки рr в треугольник ∆1

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

Алгоритм использует простую структуру данных. Если используется ацикличное дерево для хранения и поиска треугольника, тогда трудоёмкость алгоритма оценивается в среднем O (N log N). В худшем O (N²). Блок-схема алгоритма инкремента (рис. 5).

Рис. 5. Блок-схема алгоритма инкремента

Алгоритм “заметающей линии”. Идея алгоритма заметающей линии является весьма простой: во-первых, геометрические элементы сортируются. Тогда вообразим, что заметающая линия l скользит сверху вниз над плоскостью и останавливается на так называемых точках события. Часть проблемы решена, и структура данных обновляется. А другая часть проблемы остаётся не решенной до конца. Граница между решенной и нерешенной частью делится на так называемую береговую линию, которая состоит из связанных цепей параболическихдуг (рис. 6).

Рис. 6. Береговая линия вверх заметающей линии

Каждая параболаопределяется по формуле (2)

2 22

βi  y = ¹x  2 px  p  p  l ², (2)

ix ix iyy

2p  l 

ix y

где ly – значение y-координат заметающей линии, pix, piy – значение координат любой точки pi на параболе.

Рис. 7. Береговая линия попадает на точку

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

Рис. 8. Событие круга

Второе событие (так называемое событие круга) появляется, когда существующая дуга береговой линии уменьшается до точки и исчезает. Событие точки q на рис. 8 является центром круга вершин vi, vj, и vk, c самой низкой точки движения по заметающей линии. Таким образом, любая точка из P не может находиться внутри этого круга, который гарантирует ненарушениесвойствпустого круга.

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

Построение изолиний. Результат построения изолиний показан на рис. 22, трудоёмкость алгоритма, очевидно, является линейной относительно размера триангуляции.

Построение изоконтуров. Изоконтурами между уровнями h1 и h2 называется геометрическое место точек на поверхности, имеющих высоту h є (h1, h2). Результат построенияизоконтуровпоказан на рис. 23.

ОБЛАСТИ ПРИМЕНЕНИЯ РЕЗУЛЬТАТОВ РАБОТЫ

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

 Создание прогнозных пространственных моделей с учетом характерных особенностей ландшафта.

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

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

 Расчет освещенности и ветрового режима для архитектуры и городского планирования, инженерных изысканий, экологического мониторинга.

 Построение зон видимости для телекоммуникационных и сотовых компаний, архитектуры и городского планирования.

 Ортотрансформирование материалов аэрофотосъемки и космической съемки.

 Формирование атрибутивных и геометрических характеристик при создании и обновлении цифровых топографических карт.

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

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

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

(по перечню ВАК 2 статьи)

Майоров А. А., Нгуен Тхе Конг. Эффективный алгоритм построения триангуляции Делоне // Известия высших учебных заведений. Геодезия и аэрофотосъемка. Московский государственный университет геодезии и картографии. 2011. № 1. С. 105-108.
Майоров А. А., Нгуен Тхе Конг. Перспективы развития компьютерных технологий создания цифровых моделей рельефа // Известия высших учебных заведений. Геодезия и аэрофотосъемка. Московский государственный университет геодезии и картографии. 2011. № 4. С. 107-110.
Чан Зыонг, Нгуен Тхе Конг. Разработка алгоритмов и графических программ, предназначенных для цифрового картографирования // Научнотехнический журнал. Ханойский горно-геологический университет. 2004. № 5. С. 47-55.
Чан Хань, Чан Зыонг, Нгуен Тхе Конг. Оптимизация использования ресурсов памяти при программировании уравнивания геодезических сетей // Научно-технический журнал. Ханойский горно-геологический университет. 2005. № 9. С. 68-72.