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

Бахарев, Федор Сергеевич

Бесплатный автореферат и диссертация по наукам о земле на тему
Разработка структуры и алгоритмов формирования базы данных для создания цифровой модели рельефа
ВАК РФ 25.00.32, Геодезия

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

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

Бахарев Федор Сергеевич

РАЗРАБОТКА СТРУКТУРЫ И АЛГОРИТМОВ ФОРМИРОВАНИЯ БАЗЫ ДАННЫХ ДЛЯ СОЗДАНИЯ ЦИФРОВОЙ МОДЕЛИ РЕЛЬЕФА

Специальность 25.00.32 — Геодезия

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

6 ДЕК 2012 --

Москва — 2012

005056452

Работа выполнена на кафедре геодезии Московского государственного университета геодезии и картографии (МИИГАиК)

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

Чугреев Игорь Григорьевич

Официальные оппоненты: доктор технических наук, профессор

Шануров Геннадий Анатольевич

кандидат технических наук, руководитель группы ОАО «Госземкадастрсъемка» — ВИСХАГИ Синькова Марина Германовна

Ведущая организация: Федеральное государственное унитарное

предприятие "Центральный ордена «Знак Почёта» научно-исследовательский институт геодезии, аэросъёмки и картографии имени Ф.Н. Красовского" (ФГУП "ЦНИИГАиК")

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

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

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

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

ш кАМ Ю.М.

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

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

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

Задачи исследования:

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

2. Разработка оптимальной структуры БД цифровой модели рельефа.

3. Разработка алгоритмов формирования БД цифровой модели рельефа.

4. Построение, исследование и оценка цифровых моделей рельефа на основе данной структуры и алгоритмов.

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

1. Разработанная на основе предложенных элементов ЦМР структура базы данных позволяет обрабатывать большие объемы данных.

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

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

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

Апробация работы. Основные выводы и положения диссертационной работы докладывались автором в 2010-2012 г. на:

-65-ой научно-технической конференции студентов, аспирантов и молодых учёных МИИГАиК (6-7 апреля 2010 года);

- 66-ой научно-технической конференции студентов, аспирантов и молодых учёных МИИГАиК (5-6 апреля 2011 года);

-67-ой научно-технической конференции студентов, аспирантов и молодых учёных МИИГАиК (3-4 апреля 2012 года).

Публикации. Содержание и результаты диссертационной работы освещены в 5 статьях, из них 3 — в издании, рекомендованном ВАК по специальности 25.00.32 "Геодезия".

Объём диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Общий объём работы составляет 108 страниц машинописного текста, включая 13 таблиц, 41 рисунков и 2 приложения. Список использованных источников включает в себя 45 наименований.

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

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

В главе 1 «Пространственные данные как основа цифровой модели рельефа» приводятся результаты анализа структур и алгоритмов построения ЦМР. Большой вклад в создание современных автоматизированных технологий построения цифровой модели рельефа внесли видные отечественные ученые Б.Н.Делоне, Е.А.Жалковский, Б.К.Малявский, Ю.И.Маркузе, Ю.К.Неумывакин, Ю.Л. Костюк, A.B. Скворцов и многие другие. В их научных трудах сформулированы основополагающие принципы цифрового моделирования, определены подходы к решению задач обработки результатов измерений. Вместе с тем в связи с быстрым ростом производительности вычислительной техники существующие структуры и алгоритмы обработки результатов измерений при построении ЦМР не позволяют обрабатывать большие объемы геодезической информации. Согласно ГОСТ Р 52438-2005, пространственные данные - данные о пространственных объектах и их наборах. Пространственный объект - цифровая модель материального или абстрактного объекта реального или виртуального мира с указанием его идентификатора, координатных и атрибутивных данных. В рамках данной диссертационной работы будем использовать следующее определение:

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

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

Модель пространственных данных описывает объекты ЦМР и их взаимосвязи на логическом уровне. Рассматриваются следующие элементы представления объектов ЦМР:

- "Узлы с соседями";

- "Двойные рёбра";

- "Узлы и треугольники";

- "Узлы, рёбра и треугольники";

- "Узлы, простые рёбра и треугольники".

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

Основные причины этому:

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

- отсутствие типа, указывающего на состояние объекта при работе алгоритма.

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

Таблица 1. Узел

ID Идентификатор Связь объекта в оперативной памяти и в базе данных

X Двойное с плавающей точкой Координаты точки

Type Целое Тип координаты

Таблица 2. Ребро

ID Идентификатор Связь объекта в оперативной памяти и в базе данных

First Идентификатор Идентификатор первого узла

Second Идентификатор Идентификатор второго узла

TriFirstSecond Идентификатор Идентификатор треугольника со стороны при обходе по часовой стрелке с первого узла на второй

TriSecondFirst Идентификатор Идентификатор треугольника со стороны при обходе по часовой стрелке со второго узла на первый

Type Целое Тип ребра (простое, граница, структурное и другие)

ID Идентификатор Связь объекта в оперативной памяти и в базе данных

First Идентификатор Идентификатор первого узла

Second Идентификатор Идентификатор второго узла

Third Идентификатор Идентификатор третьего узла

TriSecondThird Идентификатор Идентификатор треугольника со стороны при обходе по часовой стрелке со второго узла на третий

TriThirdFirst Идентификатор Идентификатор треугольника со стороны при обходе по часовой стрелке с третьего узла на первый

Type Целое Тип треугольника (правильный, неправильный, проверенный и другие)

Для интеграции базы данных с другими ГИС системами решено использовать среду разработки Borland Delphi 7 на языке Object Pascal в виде динамической библиотеки.

В главе 2 «Создание баз данных пространственных объектов цифровой модели рельефа» рассматривается объективно сформировавшаяся на сегодняшний день архитектура системы на основе базы и хранилища данных, представленная на рисунке 1.

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

- разрешение неоднородности программной среды;

- обеспечение распределенного характера организации;

- повышенной безопасности данных;

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

- для эффективного хранения и обработки очень больших объемов информации.

Локальный и сетевой доступ

Средства обработки ЦМР

Хранилище данных

Локальный и сетевой доступ

Средства решения прикладных по ЦМР

Рисунок 1. Общая архитектура информационной системы на основе операционной

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

Оперативная база данных

Сохранение

диссертации использовался программный продукт Access / Jet фирмы "Microsoft".

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

+90

Уровень 1

+90

Уровень 2

+90

—

Регион 11 Регион 12

00 о

90 -90 Уровень 3

Регион 111 0 о Регион 112 ОО О Регион 121 Ni О Регион 122 0

Регион 113 Регион 114 ЧО О Регион 123 00 О Регион 124 (ч) -J О

ы о\ о

о\ о

w о о

-90

-90 -90

Рисунок 2. Пример трех уровней с областями.

Полная структура связей таблиц базы данных отображена на рисунке 3, а пример ЦМР в базе данных представлена на рисунке 4.

Координатная системы

РК КоордСистИндеф

Имя Тип Преобразование СисИдентификатор

Уровни йслои РК УиРИндеф

Уровень

Категория типов

РК КатИндеф

Имя Описания

Тругольники

РК ТреугИндеф

РК1Д1 УзелИндеф_1

БК2 УзелИндеф_2

БКЗ УзелИндеф 3

12 ТреугИндеф_12

ТреугИндеф_23

ТреугИндеф_31

СтильИндеф

УиРИндеф

ТипИндеф

Ребра

РК РебрИндеф

ИК1 УзелИндеф_1

РК2 УзелИндеф_2

ЕКЗ ТреугИндеф_12

ИК4 ТреугИндеф 21

СтильИндеф

УиРИндеф

ТипИндеф

Типы

РК ТипИндеф

FK1.I1 КатИндеф Имя Описания

■ Структ урыные линии Элементы структурной линии

РК СтрукЛинияИндеф

11 Параметр ТипИндеф FK1.I1 РК2.І2 КоордИндеф СтрукЛинияИндеф

Слои

РК СлойИндеф

FK1.I1

Имя

ТипИндеф СтильИндеф

Координаты

РК КоордИндеф

FK2.I2.I5 УиРИндеф

FK3.I3.I6 ОбъектИндеф

17 X

18 У

19 г

FK1.I1 КоордСистИндеф

РК4.І4 ТипИндеф

Узлы

РК УзелИндеф

FK1.I1 12 КоордИндеф ТреугИндеф РебрИндеф

Объекты

РК ОбъектИндеф

ТипИндеф

Горизонтали

РК ГорИндеф

FK1.I1 ОбъектИндеф СлойИндеф СтильИндеф УиРИндеф ТипИндеф Отметка

Откосы

РК ОткИндеф

т,12 ОбъектИндеф

п СлойИндеф

СтильИндеф

УиРИндеф

ТипИндеф

Ось

Растяжение

Длина

Толщина

Бергштрихи

РК БергИндеф

FK1.I1 ОбъектИндеф СлойИндеф СтильИндеф УиРИндеф ТипИндеф Длина

Рисунок 3. Схема структура связей таблиц базы данных ЦМР, представленная в виде ЕЯ-модели.

В главе 3 «Разработка алгоритмов формирования базы данных цифровой модели рельефа» исследуются существующие алгоритмы построения ЦМР на основе триангуляции Делоне. Рассмотрены следующие алгоритмы:

- Простой итеративный алгоритм;

- Итеративный алгоритм "Удаляй и строй";

- Итеративный алгоритм с индексированием центров треугольников квадродеревом;

- Итеративный алгоритм с динамическим кэшированием поиска;

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

- Алгоритм "Разделяй и властвуй";

- Пошаговый алгоритм.

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

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

2. Не адаптированность рассмотренных алгоритмов к работе с базами данных. При работе с большими объемами данных временные затраты будут возрастать не пропорционально.

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

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

Рассмотрим алгоритм проверки "условия минимальной суммы сторон пересечения прямоугольников". Проверка условия всегда начинается с рассматриваемого треугольника (ABC) и новой добавляемой точки (N). Рассмотрим на примере пары треугольников ABC и CBN (рисунок 5).

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

На рисунке 6а показан минимальный охватывающий прямоугольник FDBE треугольника ABC. На рисунке 66 показан прямоугольник GHIC треугольника CBN. На рисунке 6с показан прямоугольник пересечения CGBE прямоугольников FDBE и GHIC.

Рисунок 5. Треугольники ABC и CBN.

а) Ь) с)

Рисунок 6. Минимально охватывающие прямоугольники и их пересечение.

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

Рассмотрим вторую пару треугольников ЛЕШ и А>ГС(рисунок 7).

Рисунок 7. Треугольники ABN и ANC.

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

с н

Ь)

Рисунок 8. Минимально охватывающие прямоугольники и их пересечение.

На рисунке 8а показан минимальный охватывающий прямоугольник FDEN треугольника ABN. На рисунке 86 показан прямоугольник IAGH треугольника ANC. На рисунке 8с показан прямоугольник пересечения FAGN прямоугольников FDEN и ANC.

Заключительный этап. Сравнение сумм сторон полученных прямоугольников CGBE и FAGN(pHcyHOK 9).

г-

8.61

- 36.19

со со

Рисунок 9. Прямоугольники пересечения.

Находим суммы сторон прямоугольников:

СуммасовЕ = CG + СЕ = 75,70 + 8,61 = 84,31 ; Суммардом = FA + FN = 36,19+ 18,31 = 54,5;

Сравниваем полученные суммы. Пара треугольников, для которой получена наименьшая сумма, является удовлетворяющей условию минимальной суммы сторон пересечения прямоугольников. В нашем примере это прямоугольник FAGN для пары треугольников ABN и ANC.

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

Таблица 4. Число арифметических операций алгоритмов проверки

Число операций

Название алгоритма проверки Умножение Сложение и

и деление вычитание

Делоне:

Через уравнение описанной окружности 29 24

С заранее вычисленной окружностью ~ 4..7 ~ 4..6

Сумма противолежащих углов 10 13

Модифицированная сумма углов ~ 7 ~ 9

Предложенный:

Минимальной суммы сторон пересечения 0 6

прямоугольников

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

Докажем это утверждением рассмотрев время работы алгоритмов в зависимости от количества точек на графике (рисунок 10).

—•—Минимальной суммы порой пересечения прямоугольников количество точек

—•—Минимальной суммы сторон пересечения прямоугольников и модифицированная сумма уголов —Модифицированная сумма углов

Рисунок 10. График времени работы алгоритмов.

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

и«иа«:И0*1<Г51Л411К" 1оп9*1»1»: Е Сг0?г0.7«345"

Рисунок 11. Совмещенное изображение триангуляции, построенной по условиям Делоне (красным цветом) и минимальной суммы сторон пересечения прямоугольников (синим цветом).

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

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

Описание алгоритма фильтрации данных.

1. Данные о съемке выгружаются на экран пользователя в заданном масштабе.

2. Определяется область поиска «помех» при построении рельефа (Хтш, Утт,

3. Вычисляется максимальное расстояние между соседними узлами ПЦМР.

4. В соответствии с максимальным расстоянием ПЦМР определяется размер скользящего окна в метрах (или выбирается пользователем из общей плотности точек обрабатываемых данных).

Блок-схема работы функции фильтрации данных представлена на рисунке 12.

Рисунок 12. Блок-схема работы функции фильтрации данных.

Глава 4 «Реализация программного модуля» посвящена реализации разработанной структуры и алгоритмов формирования базы данных объектов для создания цифровой модели рельефа на основе больших объемов данных в программном модуле, внедренном в продукты "Апертура", использующийся в учебном процессе и "Justin" фирмы ООО "JAVAD GNSS", применяемый при производстве топографических работ.

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

разных систем.

По данному изображению можно сделать вывод, что полученные ЦМР на 90 % совпадают, но при этом разработанный модуль выполняется быстрее и может обрабатывать большие объемы данных.

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

Рисунок 14. Абрис второго тестового участка с вышкой.

Точки 0518 и 0519 с высотами (в метрах) 252,47 и 252,91 соответственно значительно выше окружающих их точек 0515, 0523, 0544, 0546, 0545, 0539 с высотами 241,26; 241,27; 241,22; 241,29; 241,27; 241,34 соответственно. После обработки алгоритмом медианной фильтрации данные точки были исключены из рельефа (рисунок 15).

Рисунок 15. Участок ЦМР с исключенными точками углов сотовой вышки

связи.

Для оценки точности построенной ЦМР на втором тестовом участке выполненном в масштабе 1:500. Было выполнено 32 контрольных измерений. Результаты оценки точности приведены в таблице 5.

Имя Север Восток Нист, М НВыч> М Нист - Нвыч, М

100 к 6235545,15 3227692,06 241,08 240,98 -0,10

139 к 6235482,97 3227846,53 235,19 235,17 -0,02

186 к 6235535,31 3228200,55 226,72 226,59 -0ДЗ

233 к 6235482,64 3228115,59 231,87 231,80 -0,07

250 к 6235475,44 3228284,13 229,83 229,88 0,05

254 к 6235471,26 3227717,66 239,85 239,83 -0,02

298 к 6235443,64 3228031,61 229,78 229,62 -0,16

335 к 6235424,74 3227731,26 239,61 239,53 -0,08

339 к 6235428,66 3228218,04 234,08 234,10 0,02

348 к 6235419,02 3227801,45 237,26 237,21 -0,05

366 к 6235411,56 3227966,59 232,79 232,69 -0,10

397 к 6235392,05 3228138,72 236,99 236,98 -0,01

420 к 6235377,2 3228318,66 233,11 233,11 0,00

429 к 6235372,06 3227842,48 237,59 237,44 -0,15

45 к 6235605,37 3227963,73 231,65 231,69 0,04

46 к 6235604,9 3227801,75 238,67 238,66 -0,01

460 к 6235349,31 3228054,5 236,22 236,13 -0,09

483 к 6235338,94 3228263,66 235,44 235,43 -0,01

516 к 6235317,74 3227989,51 233,61 233,58 -0,03

53 к 6235599,28 3227688,28 240,86 240,87 0,01

542 к 6235307,95 3228192,29 238,08 237,99 -0,09

584 к 6235278,37 3227872,32 237,50 237,45 -0,05

623 к 6235255,79 3228114,31 238,19 238,17 -0,02

624 к 6235255,17 3228329,84 235,38 235,49 0,11

627 к 6235254,77 3227801,11 240,76 240,73 -0,03

660 к 6235234,83 3228277,98 237,00 236,99 -0,01

68 к 6235585,42 3227882,81 234,08 234,21 0,13

689 к 6235217,15 3228027,88 235,97 235,94 -0,03

714 к 6235198,03 3228212,23 236,99 237,01 0,02

720 к 6235195,06 3227926,02 235,55 235,55 0,00

723 к 6235194,05 3227828,4 239,60 239,60 0,00

731 к 6235189,96 3228115,04 237,22 237,14 -0,08

Макс = 0,13 м, Мин =-0,16 м, СКО = 0,029 м 1/п = -0,03

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

Заключение.

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

2. Разработанный алгоритм преобразования пикетно-цифровой геоинформации в псевдоматрицу позволяет вести обработку ПЦМР.

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

4. Реализованный на основе полученных автором результатов исследований и разработок программный модуль внедрен в продукты "Апертура" и "Justin", показав свою эффективность.

Список публикаций по теме диссертации:

• Джавад Ашджаи (Javad Ashjaee), Разумовский А.И., Рапопорт Л.Б., Удинцев

В.Г., Бахарев Ф.С. Justin-программа для постобработки спутниковых

измерений JAVAD GNSS // Геопрофи. - 2011. - вып.З. - с.30-33.

• Разумовский А.И., Бахарев Ф.С. Justin Link - офисное приложение //

Геопрофи. - 2012. - вып 1. — с. 18-22.

• Чугреев И.Г., Владимирова М.Р., Бахарев Ф.С. К вопросу о выборе методики

проведения тахеометрических съемок в современных условиях // Известия

высших учебных заведений. Геодезия и аэрофотосъемка. - 2012. - № 2. - с. 20-24.

• Чугреев И.Г., Бахарев Ф.С. Некоторые особенности получения и обработки полевой информации // Известия высших учебных заведений. Геодезия и аэрофотосъемка. -2012. - № 3. — с. 21-23.

• Бахарев Ф.С. Современные структуры баз данных цифровых моделей рельефа // Известия высших учебных заведений. Геодезия и аэрофотосъемка. -2012.-№5.-с. 80-85.

Подписано в печать 09.11.2012 г. Формат А4 Тираж: 100 экз. Заказ № 972 Типография «11-й ФОРМАТ» 115230, Москва, Варшавское ш., 36 (499) 788-78-56

Содержание диссертации, кандидата технических наук, Бахарев, Федор Сергеевич

ВВЕДЕНИЕ.

1. ПРОСТРАНСТВЕННЫЕ ДАННЫЕ КАК ОСНОВА ЦИФРОВОЙ МОДЕЛИ РЕЛЬЕФА.

1.1. пространственные данные.

1.2. модель пространственных данных цифровой модели рельефа.

1.2.1. Регулярные ЦМР.

1.2.2. Нерегулярные ЦМР.

1.3. подходы интеграции базы данных с информационными системами.

2. СОЗДАНИЕ БАЗ ДАННЫХ ПРОСТРАНСТВЕННЫХ ОБЪЕКТОВ ЦИФРОВОЙ МОДЕЛИ РЕЛЬЕФА.

2.1. Архитектура информационной системы на основе баз данных.

2.2. Подходы и имеющиеся решения для создания базы данных.

2.2.1. Компания IBM.

2.2.2. Oracle.

2.2.3. Hewlett Packard.

2.2.4. Sybase.

2.2.5. NCR.

2.2.6. SAS Institute.

2.2.7. Software AG.

2.2.8. Microsoft.

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

3. РАЗРАБОТКА АЛГОРИТМОВ ФОРМИРОВАНИЯ БАЗЫ ДАННЫХ ЦИФРОВОЙ МОДЕЛИ РЕЛЬЕФА

3.1. Алгоритмы построения цифровой модели рельефа.

3.1.1. Простой итеративный алгоритм.

3.1.2. Итеративный алгоритм "Удаляй и строй".

3.1.3. Итеративный алгоритм с индексированием центров треугольников квадродеревом.

3.1.4. Итеративный алгоритм с динамическим кэшированием поиска.

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

3.1.6. Алгоритм "Разделяй и властвуй".

3.1.7. Пошаговый алгоритм.

3.2. Алгоритмы отображения и решение прикладных задач.

3.2.1. Вывод триангуляции на экран.

3.2.2. Фильтрация исходных данных.

3.2.3. Построение горизонталей.

3.2.4. Построение изолиний.

3.2.5. Сглаживание изолиний.

3.3. Разработка нового алгоритма создания цифровой модели рельефа.

4. РЕАЛИЗАЦИЯ ПРОГРАММНОГО МОДУЛЯ.

4.1. Архитектура программного модуля.

4.2. Оценка работы программного модуля.

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

Получение цифровых моделей рельефа (ЦМР) является неотъемлемой частью выполнения любых современных топографо-геодезических работ. Такие модели строятся на основе данных, получаемых различными способами. Основные из них — тахеометрическая съемка, лазерное сканирование, аэрофотосъемка, космические снимки и оцифровка аналоговых материалов [40; 42]. В каждом из них совершенствуются инструменты по сбору данных для построения ЦМР.

В связи с быстрым ростом производительности вычислительной техники стремительно растут объёмы данных, получаемых с них. Например, уже сейчас доступна сеточная модель ЦМР с шагом в 30 м на территорию Земного шара от "ASTER GDEM", что составляет порядка 1,68 триллиона точек. Изучение обширных территорий используется в мониторинге и оценке динамики рельефа, моделировании радиовидимости и др. Но и на малой территории для исследования локальных процессов может потребоваться обработка такого же большого количества точек, которые могут быть представлены и нерегулярным набором. Обработка такого объёма информации без использования баз данных невозможна, а существующие алгоритмы не адаптированы на работу с ними. Поэтому требуется усовершенствование существующих и разработка новых структур и алгоритмов построения ЦМР [27].

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

Решение этих задач требует комплексного подхода к разработке структур и алгоритмов формирования базы данных объектов для создания ЦМР.

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

Задачи исследования;

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

2. Разработка оптимальной структуры БД цифровой модели рельефа.

3. Разработка алгоритмов формирования БД цифровой модели рельефа.

4. Построение, исследование и оценка цифровых моделей рельефа на основе данной структуры и алгоритмов.

Методы исследования.

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

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

Разработанные структуры и алгоритмы встроены в программные продукты "Апертура", использующийся в учебном процессе в МИИГАиК и "Justin" компании ООО "JAVAD GNSS", служащий для обработки спутниковых измерений и обмена данными с устройствами.

Основные положения диссертационной работы докладывались автором в 2010-2012 г. на:

1. 65-ой научно-технической конференции студентов, аспирантов и молодых учёных МИИГАиК, посвящённой 65-летию победы в Великой Отечественной войне (конференция проходила 6-7 апреля 2010 года).

2. 66-ой научно-технической конференции студентов, аспирантов и молодых учёных МИИГАиК, посвящённой 50-й годовщине первого полета человека в космос - лётчика-космонавта СССР Героя Советского Союза Юрия Алексеевича Гагарина (конференция проходила 5-6 апреля 2011 года).

3. 67-ой научно-технической конференции студентов, аспирантов и молодых учёных МИИГАиК, в рамках проводимого в Российской Федерации Года российской истории (конференция проходила 3-4 апреля 2012 года).

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

1. Джавад A. (Javad Ashjaee), Разумовский А.И., Рапопорт Л.Б., Удинцев В.Г., Бахарев Ф.С. Justin - программа для постобработки спутниковых измерений JAVAD GNSS // Геопрофи. - 2011. - Вып. 3. - С. 30-33.

2. Разумовский А.И., Бахарев Ф.С. Justin Link - офисное приложение // Геопрофи. - 2012. - Вып 1. - С. 18-22.

3. Чугреев И.Г., Владимирова М.Р., Бахарев Ф.С. К вопросу о выборе методики проведения тахеометрических съемок в современных условиях // Известия высших учебных заведений. Геодезия и аэрофотосъемка. -2012.- №2.-С. 20-24.

4. Чугреев И.Г., Бахарев Ф.С. Некоторые особенности получения и обработки полевой информации // Известия высших учебных заведений. Геодезия и аэрофотосъемка. - 2012. - № 3. - С. 21-23.

5. Бахарев Ф.С. Современные структуры баз данных цифровых моделей рельефа // Известия высших учебных заведений. Геодезия и аэрофотосъемка. - 2012. - № 5. - С. 80-85.

Заключение Диссертация по теме "Геодезия", Бахарев, Федор Сергеевич

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

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

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

3. Разработанный алгоритм преобразования пикетно-цифровой геоинформации в псевдоматрицу позволяет вести обработку ПЦМР.

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

5. Реализованный на основе полученных автором результатов исследований и разработок программный модуль внедрен в продукты "Апертура" и "Justin", показав свою эффективность.

ЗАКЛЮЧЕНИЕ

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

1. "Google Maps Structure" // Inc. Microimages, 2009.

2. ArcView GIS : Руководство пользователя. M.: Дата+, 2008. - 142 с.

3. Maplnfo Professional : Руководство пользователя (Полное). М. : ESTI MAP, 2004.-517 с.

4. БакнеллД. М. Фундаментальные алгоритмы.-М., 2003.

5. Бахарев Ф. С. Современные структуры баз данных цифровых моделей рельефа // Известия высших учебных заведений. Геодезия и аэрофотосъемка. 2012. - № 5. - С. 80-85.

6. Берлянт А. М. Картография : учебник для студентов вузов, обучающихся по географическим и экологическим специальностям. -М., 2001.-336 с.

7. Боцула A.B., Евграфов И.П., Лалушкин Ю.Л. Анализ требований к ГИС при ее интеграции в комплекс задач ситуационного центра // Материалы форума ГИС97. М.: ГИС-Ассоциация, 1997.-С. 102-104.

8. Варфоломеев И. В., Ермакова И. Г., Савельев А. С. Алгоритмы и структуры данных геоинформационных систем : Методические указания. Красноярск, 2003. - 34 с.

9. Васильев А. Эрнст Аббе и "Карл Цейсс, Иена" // Из истории науки. -Квант. 2000. - № 1 - С. 1-3.

10. Ю.Вейцман В. М. Проектирование экономических информационных систем. Ярославль : МУБиНТ, 2002. - 213 с.

11. Геоинформатика : учебник для студентов вузов, обучающихся по специальностям 012500 "География", 013100 "Природопользование", 013600 "Геоэкология", 351400 "Прикладная математика (по областям)" // под ред. В. С. Тикунов. М.: Академия. - 2005. - 477 с.

12. Гиршберг М. А. Геодезия . М.: Недра, 1967 - С. 75-83.

13. Горев А., Ахаян Р., Макашарипов С. Эффективная работа с СУБД // СПб, 1997.-С. 10-15.

14. ГОСТ Р 52055 2003. Геоинформационное картографирование. Пространственные модели местности. Общие требования. — Введ. 2004 - 01 - 01. - М. : Изд-во стандартов, 2003. - 7 с.

15. ГОСТ Р 52438 2005. Географические информационные системы. Термины и определения. - Введ. 2005 - 12 - 28. - М. : Изд-во стандартов, 2005. - 6 с.

16. ГОСТ Р ИСО 19113-2003. Географическая информация. Принципы оценки качества. Введ. 2003 - 12 — 09. - М. : Изд-во стандартов, 2003. -Зс.

17. П.Григорьев А. О чём не пишут в книгах по Delphi // http://www.delphikingdom.com/ 2003.

18. Гришин В. Н., Панфилова Е. Е. Информационные технологии в профессиональной деятельности. М. : Инфра-М, 2005. - 416 с.

19. Джавад А., Разумовский А. И., Рапопорт JI. Б., Удинцев В. Г., Бахарев Ф. С. Justin программа для постобработки спутниковых измерений JAVAD GNSS // Геопрофи. - 2011. - Вып. 3. - С. 30-33.

20. Козодев А. В., Привезенцев А. И., Фазлиев А. 3. // Вычислительные технологии; 2005. - Т. 10, спец. выпуск - С. 82-91.

21. Кошкарев А. В., Тикунов В. С. Геоинформатика. М. : Картгеоцентр -Геоиздат, 1993.

22. Кузнецов С. Д. Проектирование и разработка корпоративных информационных систем // «Корпоративные базы данных 2010»: Материалы XV ежегодной технической конференции, 22-23 апреля 2010 г. / ИСП РАН, М., 2010.

23. Кузнецов С. Д. Современное состояние и перспективы баз данных // Введение в теорию открытых систем. М. : Центр информационных технологий, 1995. - С. 54-64.

24. Маклин С., Нафтел Дж., Уильяме К. Microsoft .NET Remoting. M. : Русская редакция, 2003. - 384 с.

25. Никитина Т. П. Информационные системы в экономике : учебноепособие.-Ярославль. : МУБиНТ, 2003. С. 90.

26. Петров Ю. А., Шлимович E.JL, Ирюпин Ю.В. Комплексная автоматизация управления предприятием: Информационные технологии теория и практика. - М. : Финансы и статистика, 2001. -160 с.

27. Построение баз геоданных. Пер. с англ. М. : Дата+, 2003. - 426 с.

28. Путятин Е. П., Аверин С. И. Обработка изображений в робототехнике // Машиностроение. 1990. - С. 63-86.

29. Разумовский А. И., Бахарев Ф. С. Justin Link офисное приложение // Геопрофи. - 2012. - Вып 1. - С. 18-22.

30. Середович В.А., Ферулев Д.А. Компьютерные технологии при создании баз данных в топографо-геодезическом производстве. М. : Геодезия и картография, 2007. - Вып. 9. - С. 25-28.

31. Скворцов А. В., Гриценко Ю. Б. Вопросы построения универсальной графической системы для работы с территориально определённой информацией // Геоинформатика. Теория и практика. 1998: - Вып. 1. - С. 169-180.

32. Скворцов A.B. Триангуляция Делоне и её применение. Томск. : Изд-во Томского ун-та, 2002 - С. 11-78.

33. Стрельцов И. Сервер пространственных данных ArcSDE / И. Стрельцов // ArcReview. 2004. - №3 (30).

34. Тайле Э. Концепция и базовые принципы создания и функционирования системы геоинформации AFIS-ALKISATKIS // Геодезия и картография. 2007. - Вып. 9. - С. 46-51.

35. Уильям Г. Инмон (William H. Inmon) "Building the Data1. Warehouse", -1992.

36. Федечкин С. Хранилище данных: вопросы и ответы // PC WEEK. -2003.-№31.-С. 86-90.

37. Хоменко A. Delphi 7. Наиболее полное руководство. СПб. : БХВ-Петербург, 2006. - С. 140-156.

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

39. Чеботарев А.С. Геодезия 4.1. М.: Геодезиздат, 1949. - С. 43-50.

40. Чугреев И. Г., Бахарев Ф.С. Некоторые особенности получения и обработки полевой информации // Известия высших учебных заведений. Геодезия и аэрофотосъемка. 2012. - № 3. - С. 21-23.

41. Чугреев И.Г., Владимирова М.Р., Бахарев Ф.С. К вопросу о выборе методики проведения тахеометрических съемок в современных условиях // Известия высших учебных заведений. Геодезия и аэрофотосъемка, 2012. № 2. - С. 20-24.

42. Шабельникова Т.Г. Геоинформатика в нефтегазовой отрасли // Информационный бюллетень ГИС-Ассоциация, 1998.-С. 137-139.

43. Шекхар Ш., Чаула С. Основы пространственных баз данных. М.: Кудиц-Образ, 2004. - 336 с.

44. Шеннон К. Работы по теории информации и кибернетике. М.: Изд-во иностр. лит., 1963. - 830 с.

45. Широкова С.Л., Ловцкая О.В., Шелепов С.М. Интеркарто-2: ГИС для изучения и картографирования окружающей среды. Иркутск.: Изд-во Ин-та географии СО РАН, 1996. - С. 207-209.

46. Шуленин А., Марк Р., Оленин О., Марк Б. Пятнадцатая ежегодная техническая конференция «Корпоративные базы данных-2010». — : Интернет-альм. 2010. - Режим доступа: http://citforum.ru/seminars/cbd2010/.

Информация о работе

Бахарев, Федор Сергеевич
кандидата технических наук
Москва, 2012
ВАК 25.00.32

Диссертация

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

Автореферат

Похожие работы