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

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

РАЗРАБОТКА СТРУКТУРЫ И АЛГОРИТМОВ ФОРМИРОВАНИЯ

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

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

АВТОРЕФЕРАТ

диссертации на соискание учёной степени

кандидата технических наук

Москва — 2012

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

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

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

Ведущая организация: Федеральное государственное унитарное предприятие “Центральный ордена «Знак Почёта»

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

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

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

Автореферат разослан «» ноября 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 рисунков и 45 наименований.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

для эффективного хранения и обработки очень больших объемов Чтение, преобразование, запись Локальный и сетевой доступ Средства решения прикладных по ЦМР Рисунок 1. Общая архитектура информационной системы на основе операционной Далее рассматриваются основы и пути решения при создании баз данных. Приводится краткая характеристика продуктов средств управления базой данных (СУБД) ведущих представителей на рынке программного обеспечения. Из анализа сделан вывод о том, что выбор СУБД для реализации баз данных зависит от потребностей и возможностей пользователя. В данной “Microsoft”.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим на примере пары треугольников ABC и CBN (рисунок 5).

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

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

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

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

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

Рассмотрим вторую пару треугольников ABN и ANC(рисунок 7).

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

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

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

прямоугольников CGBE и FAGN(рисунок 9).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Определяется область поиска «помех» при построении рельефа (X min, Ymin, Xmax, Ymax).

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

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

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

НАЧАЛО

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

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

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

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

Рисунок 13. Программный продукт Justin. Отображены три ЦМР, полученные из По данному изображению можно сделать вывод, что полученные ЦМР на 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.

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

Заключение.

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

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

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

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

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

Джавад Ашджаи (Javad Ashjaee), Разумовский А.И., Рапопорт Л.Б., Удинцев измерений JAVAD GNSS // Геопрофи. – 2011. – вып.3. – c.30-33.

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

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

20-24.

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

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