«Исследование математических методов построения изолиний»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОУВПО «Самарский государственный архитектурно-строительный университет»

Факультет информационных систем и технологий

Кафедра прикладной математики и вычислительной техники

Пояснительная записка

к КУРСОВОЙ РАБОТЕ на тему

«Исследование математических методов построения изолиний»

по дисциплине

МЕТОДОЛОГИЯ НАУЧНЫХ ИССЛЕДОВАНИЙ

СТУДЕНТА ГИП-104

			Подпись, дата	Расшифровка подписи
		ВЫПОЛНИЛ:
		студент
		ПРОВЕРИЛ:
		ОЦЕНКА		/ /

Самара 2008г.

Введение.

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

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

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

Глава 1

Обзор тематики, сопоставление источников, постановка задачи.

Вдедение в ГИС.

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

1.  Оценка состояния природных ресурсов региона и планирование процессов их рационального использования.

2.  Оценка и прогнозирование экологического состояния региона.

3.  Оценка эффективности и прогноз хозяйственного использования территории региона.

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

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

Общее понятие о ГИС.

Что же это такое геоинформационные системы (ГИС)?
Начнем с определения автоматизированной информационной системы обработки данных (системы электронной обработки данных). Автоматизированная информационная система обработки данных - это система, выполняющая процедуры обработки данных для получения информации, полезной для принятия решений. Информационная система в элементарной  форме  это  система  вопросов-ответов для множества данных, которая  включает  в  себя  последовательность  операций: получение данных, их анализ и использование для принятия решений Следовательно, систему электронной обработки данных можно представить как четырехкомпонентную модель (см. рис.1), включающую пользовательский интерфейс и подсистемы ввода, вывода и анализа данных [2].
 
 

Рис.1. - Четырехуровневая модель ГИС.

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

ГИС - это автоматизированная информационная система, предназначенная для картографирования  и анализа объектов (естественных и искусственных), которые существуют, и событий (явлений), которые происходят на Земле [2].

Отсюда приставка "гео"  ( в переводе с греческого - "земля") в названии системы. Итак, основное отличие ГИС от других информационных систем состоит в том, что ГИС имеет дело с пространственно-временными, географически координированными данными. Географически координированные данные - это данные, привязанные к картографической основе, к карте местности, то есть данные, имеющие либо географические координаты (широту и долготу), либо прямоугольные координаты (X, Y,Z), либо почтовые адреса (почтовые индексы, коды), идентифицирующие местоположение на карте [5]. Таким образом, связующим звеном информации в ГИС является география, вот почему широко распространено другое название геинформационных систем - географические информационные системы. Хотя и можно себе представить проектирование специализированных ГИС, ориентированных на решение узких географических задач, и назвать их географическими информационными системами, для авторов данной книги оба названия системы - синонимы.

Основные компоненты ГИС.

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

Кажется, что здесь можно было бы ограничиться декларативным утверждением, что весь арсенал современных достижений в области аппаратно-программного обеспечения автоматизированных информационных систем обработки данных  практически используется и в ГИС. Нам представляется, что нет необходимости подробно останавливаться на аппаратном обеспечении ГИС  или на подсистеме вывода ГИС. Для последней, кстати, важным элементом является представление картографических данных в качестве выходного или промежуточного продукта ГИС, и поэтому имеет смысл подробнее остановиться на этой функциональной компоненте ГИС, а не погружаться в тонкости аппаратно-программного обеспечения подсистемы вывода ГИС. Отсюда, вероятно, предпочтительнее модель ГИС, в основу которой пожен функциональный принцип, когда выделяются компоненты ГИС, играющие ключевую роль в функционировании ГИС. В этом смысле  ГИС любого уровня в системе представляет собой  набор следующих функциональных компонент [2]: подсистема сбора данных; подсистема базы данных (БД), включающая систему управления базой данных (СУБД); подсистема представления, генерации и обработки картографических данных; пользовательский интерфейс и подсистема анализа данных (рис.2).

Рис.2. - Структура ГИС.

 Дадим краткую характеристику каждой из основных компонент
ГИС. Начнем с подсистемы сбора данных [3]. По оценкам специалистов в области геинформационных технологий затраты на сбор и ввод данных при реализации ГИС-проектов в 5-10 раз превышают затраты на аппаратно-программное обеспечение ГИС. Это объясняется тем, что существующие в настоящее время технологии автоматизированного ввода графических и текстовых данных обеспечивают ввод порядка 20% общего объема данных. Поэтому особое значение приобретает дальнейшее развитие автоматизированных методов сбора и ввода всех типов данных
в рамках ГИС. Основная функциональная задача этой подсистемы - создание целостного информационного цифрового образа исследуемого объекта или явления в пространственных границах. Большие потенциальные возможности для сбора данных в ГИС открывает GPS (Global Positioning System) - технология, созданная на основе космических систем глобальной навигации ГЛОНАСС (РОССИЯ) и NAVSTAR (USA) [7]. Эта технология предназначена для сбора высокоточной цифровой информации о местности, фактически топографических данных: географических координат и отметки высоты рельефа в данной точке местности, при этом точность измерений достигает нескольких сантиметров. Для обеспечения возможности импорта цифровых данных от различных источников подсистема сбора и ввода данных ГИС должна иметь программные средства разработки интерфейсов для ввода данных различных форматов. Вообще создание норм по стандартизации и унификации форматов данных, цифровых моделей местности, картографических документов, интерфейсов имеет решающее значение для успешной реализации подсистемы сбора данных ГИС.

Подсистема базы данных (БД) [3], включающая систему управления базой данных (СУБД), - одна из основных компонент ГИС, в значительной степени определяющая эффективность работы ГИС. СУБД ГИС осуществляет автоматический поиск информации в БД, необходимой для обработки пользовательских запросов. Возможности СУБД, а также структура БД и объем содержащейся в ней информации фактически определяет уровень сложности пользовательских запросов, которые система может обработать. Большинство современных ГИС имеет две отдельных СУБД для графических и семантических данных. При этом  в качестве СУБД семантических данных используется одна из широко распространенных СУБД реляционного типа (Oracle, Ingres, FoxBase, FoxPro, PARADOX и другие). Выбранная СУБД семантических данных должна иметь интерфейс с СУБД графических (картографических) данных, которая должна обеспечить: хранение и манипулирование такими графическими объектами, как точечные, линейные и площадные; многоуровневое (послойное) представление графических данных; произвольную выборку и отображение любых фрагментов графических изображений. Такой подход к реализации подсистемы БД ГИС имеет ряд недостатков:

·   необходимость назначения топологических связей между графическими объектами и их семантическими описаниями;

·   недостаточная гибкость табличной организации семантических данных;

·   неспособность распознавать иерархические отношения классов объектов.

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

Характерной особенностью ГИС-технологии является обработка пространственно-временных, географически координированных данных. Отсюда важная  роль  картографических  материалов  и  цифровых изображений  как источников данных при создании геоинформационных фондов ГИС, а также подсистемы представления, генерации и обработки картографических данных [4]. Ядром этой подсистемы является Система цифрового картографирования (СЦК), исполняющая функции ввода,  редактирования оперативного просмотра и интерактивных измерений цифровых карт и  изображений. СЦК должна обеспечивать комфортную среду, как для разработчиков основных компонент ГИС, так и для пользователей. Важной  здесь  представляется технология  совмещения  растрового и векторного форматов представления данных. Назначeниe СЦК - комплeксноe создание и рeдактированиe цифровых карт,  элeмeнтов их информационного обeспeчeния (системы условных знаков и классификатора  информации) с целью  получения и обновления картографических данных и создания модeлeй гeоинформационных процессов.

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

К средствам подсистемы анализа [4] ГИС  (отработки  запросов пользователя) относятся различные процедуры обработки данных, манипулирования пространственными  и  семантическими  данными, выполняемые  при отработке пользовательских запросов. К таким средствам  относятся, например,  операции  наложения  графических  контуров, средства анализа сетевых структур, выделение объектов по заданным признакам, методы и алгоритмы статистического анализа данных, обработка  аэрокосмических изображений  и  т. п.  ГИС  должна обладать большим набором средств анализа пространственных  данных, возможностью их расширения и дополнения, возможностью полного  или частичного их использования при решении конкретной задачи в рамках ГИС-технологии. Для решения  специфических  для  геоинформационной  технологии  задач, система должна обладать также  возможностью  создания  программных интерфейсов с другими системами и программными пакетами, например, системами  автоматизированного проектирования  (AutoCad), программными  пакетами  разработки  экспертных  систем  (Nexpert), пакетами обработки изображений (PCI, Corel Graphics) [9] и т. п.  Многие современные ГИС включают различные пакеты анализа данных. Так  ГИС IDRISI  включает достаточно богатые пакеты прикладных программ  для
анализа  географических  данных и создания  тематических  карт, обработки изображений и статистического анализа данных.

Построение цифровой модели рельефа.

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

Начало исследований в этой области было положено еще в XIX веке работами Александра фон Гумбольдта (Alexander von Humboldt) и более поздними работами других немецких ученых-географов [1]. Сегодня подобное моделирование представляет собой сочетание наук о Земле, геоинформатики и геостатистики и имеет много названий. Например, на Западе оно известно как количественный анализ рельефа (quantitative terrain analysis), геоморфометрия (geomorphometry) или количественная геоморфология [1].

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

Основой для представления данных для ГИС и автоматизированной картографии являются цифровые модели. Под цифровой моделью (ЦМ) географического объекта понимается определенная форма представления исходных данных и способ их структурного описания, позволяющий «вычислять» (восстанавливать) объект путем интерполяции, аппроксимации или экстраполяции. Относительно рельефа такая модель будет называться цифровой моделью рельефа (ЦМР) [12].

Существует два кардинально различающихся способа получения моделей рельефа.

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

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

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

Варианты моделирования могут быть разгруппированы, исходя из принципа моделирования. Прежде всего, стоит упомянуть модели, представленные в виде TIN, построенные на основе триангуляции Делоне. Такие модели используются в проектах и приложениях исследовательской группой GeoFrance3D. Кроме этого, модели TIN могут использоваться при генерации дополнительных данных при их нехватке для интерполяции [10].
Преимуществом триангуляционной модели является то, что в ней нет никаких преобразований исходных данных. С одной стороны, это не дает использовать такие модели для детального анализа, но, с другой стороны, исследователь всегда знает, что в этой модели нет никаких привнесенных ошибок, которыми грешат модели, полученные при использовании других методов интерполяции.

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

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

Восстановление поверхностей реализуется на основе интерполяции исходных данных. Используются TIN, GRID, TGRID модели.

Интерполяция – восстановление функции на заданном интервале по известным ее значениям конечного множества точек, принадлежащих этому интервалу [17].

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

Основные проблемы построения ЦМР и актуальность их решения.

Рельеф является важнейшей характеристикой любой территории и поэтому данные о рельефе необходимы при решении разнообразных задач. В природопользовании такими задачами являются [1]:

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

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

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

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

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

6.  Оценка объемов вскрышных работ при проектировании карьеров для добычи полезных ископаемых.

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

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

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

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

Кроме ошибок в атрибутивных данных, велико количество графических ошибок. В подавляющем большинстве это различные пики, петли на линиях, двойные (дублирующие) изолинии. Существует и ряд технологических недостатков [10]. Как правило, оцифровка ведется «полистно», причем соседние листы могут обрабатываться разными операторами, сшивка листов производится формально, и в результате на стыке листов возникают скачки, изломы (рис 3а). При использовании автоматических режимов векторизации (что далеко не всегда возможно) изолинии часто оказываются излишне сглаженными, что приводит к неоправданному росту объемов материала (рис. 1б). при использовании ручных режимов оцифровки изолинии получаются слишком «ломаными», сильно осциллируют (рис. 1в). Хотя используемые современные средства векторизации формально позволяют избежать всех этих недостатков, реально выдержать технологический оптимум на практике оказывается не всегда возможным.

а) б)

в)

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

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

Краткий обзор ГИС, используемых в России.     

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

Характеризуя свойства полнофункциональных ГИС можно отметить их общие черты.  Все системы работают на платформе Windows. Только некоторые из них имеют версии, работающие под управлением других операционных систем («Горизонт» - MS DOS, Unix, Linux, MC BC, Free BSD, Solaris, ИНТРОС; ПАРК – MS DOS; Arc GIS Arc Info-Solaris, Digital Unix, AIX и др.; ArcView GIS – Unix) [7].

Все системы поддерживают обмен пространственной информацией (экспорт и импорт) со многими ГИС и САПР через основные обменные форматы.

Еще более однородными являются возможности по работе с атрибутивной информацией. Большинство систем обеспечивают работу со всеми основными СУБД через драйверы ODBC, BDE. Первой в ряду поддерживаемых или используемых СУБД стоит Oracle.

В преобладающем большинстве случаев современные полнофункциональные ГИС позволяют расширять свои возможности. Основным способом расширения возможностей является программирование на языках высокого уровня (MS Visual Basic, MS Visual C++, Borland Delphy, Borland C++ Builder) с подключением DLL и OCX-библиотек (ActiveX). Естественно имеются и исключения. Такие системы как MapInfo Professional используют Map Basic, а системы  AricView GIS -  Avenue [7].

Наиболее распространенными зарубежными системами по разным причинам являются ArcView GIS, MapInfo Professioal, MicroStation/J. Аналогичный перечень отечественных систем возглавляют ГеоГраф, Панорама (Карта 2000), ПАРК, GeoLink [7].

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

ArcGIS ArcInfo (разработчик фирма ESRI, США). Полнофункциональная ГИС, состоящая из двух независимо устанавливаемых программных пакетов – ArcInfo Workstation и ArcInfo Desktop. Первый состоит из трех базовых модулей:  ArcMap – отображение, редактирование и анализ данных,  ArcCatalog – доступ к данным и управление ими,  ArcToolbox – инструмент расширенного пространственного анализа, управление проекциями и конвертацией данных. Дополнительные модули обеспечивают решение следующих задач:

- Arc COGO – набор средств и функций для работы с геодезическими данными;

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

- ARC TIN – предназначен для моделирования топографических поверхностей;

 - Arc NETWORK – для моделирования и анализа топологически связанных объектов в виде пространственных сетей, оценки и управление ресурсами, распределенными по сетям, и процессами в таких сетях.

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

ArcGIS ArcView (разработчик фирма ESRI, США). Настольная ГИС, которая предоставляет пользователю средства выбора и просмотра разнообразных геоданных, их редактирования, анализа и вывода (бизнес, наука, образование, управление, социология, демография, экология, транспорт, городское хозяйство).

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

- ArcGIS Spatial Analyst – программный модуль для работы с растровыми поверхностями. Позволяет анализировать характеристики поверхности, а также интерполировать пространственно распределенные данные для визуализации и анализа процессов;

- ArcGis 3D Analyst – программа для создания, визуализации и анализа трехмерных объектов и поверхностей;

- ArcGIS Geostatistical Analyst – новый модуль для интерполяции поверхностей на основе статистического анализа пространственно распределенных данных;

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

MapInfo Professional (разработка фирмы MapInfo Corp. США), одна из самых распространенных настольных ГИС в России. MapInfo специально спроектирован для обработки и анализа информации, имеющей адресную или пространственную привязку.

В MapInfo реализованы:

- поиск географических объектов;

- работа с базами данных;

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

- построение буферных зон вокруг любого объекта или группы объектов;

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

- компьютерный дизайн и подготовку к изданию картографических документов.

ГеоГраф [4] (разработка Центра информационных исследований Института географии РАН, Россия). Дает возможность создавать электронные тематические атласы и композиции карт на основе слоев цифровых карт и связанных с ними таблиц атрибутивных данных. Основные возможности ГеоГраф следующие:

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

- подсистема управления атрибутивными данными, включая подсоединение таблиц, редактирование, выборку, сортировку, запросы по образцу и т. д.

- электронное тематическое картографирование и др.

Панорама (Россия) [4] Построение и обработка цифровых и электронных карт, ведение картографической и атрибутивной баз данных.

Отдельно следует выделить профессиональные многофункциональные  инструментальные ГИС, обеспечивающие возможность непосредственной обработки данных ДЗ. К ним относятся ERDAS IMAGINE, ERMapper и др.

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

ERDAS IMAGINE (разработка Leica) – программный пакет, разработанный специально для обработки и анализа данных дистанционного зондирования, предоставляет полный набор инструментов для анализа данных из любого источника и представление результатов в различных формах – от печатных карт до трехмерных моделей.  ERDAS IMAGINE построен по модульному принципу в виде базовых комплектов – IMAGINE Essential, IMAGINE Advantage и  IMAGINE Professional.

В  ERDAS IMAGINE  реализованы:

- широкие возможности по визуализации и импорту данных (поддерживает более 100 форматов);

- геометрическая коррекция;

- улучшающие преобразования и ГИС-анализ;

- дешифрирование снимков;

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

- создание карт.

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

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

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

·  Интерполяция с помощью полинома Лагранжа;

·  Оптимизация функции методом градиентного спуска;

·  Сплайн-интерполяция.

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

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

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

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

Для разработки программного продукта использовалась программная среда Visual Studio 2005 и язык программирования С#.

В последнее время С и С++ становятся наиболее используемыми языками при разработке коммерческих и бизнес-приложений. Эти языки устраивают многих разработчиков, но в действительности не обеспечивают должной продуктивности разработки. К примеру, процесс написания приложения на С++ часто занимает гораздо больше времени, чем разработка эквивалентного приложения на Visual Basic. Сейчас существуют языки, увеличивающие продуктивность разработки за счет потери в гибкости, которая так привычна и необходима программистам на С/С++. Подобные решения весьма неудобны для разработчиков и нередко предлагают значительно меньшие возможности. Эти языки также не ориентированы на взаимодействие с появляющимися сегодня системами и очень часто не соответствуют существующей практике программирования для Web. Многие разработчики хотели бы использовать современный язык, который позволял бы писать, читать и сопровождать программы с простотой Visual Basic и в то же время давал мощь и гибкость С++, обеспечивал доступ ко всем функциональным возможностям системы, взаимодействовал с существующими программами и легко работал с возникающими Web-стандартами.

Учитывая все подобные пожелания, Microsoft разработала новый язык – С#. Он имеет массу преимуществ: простота, объектная ориентированность, типовая защищенность, «сборка мусора», поддержка совместимости версий и многое другое. Данные возможности позволяют быстро и легко разрабатывать приложения. При создании С# его авторы учитывали достижения многих других языков программирования: С++, С, Java, Visual Basic т. д. Надо заметить, что поскольку С# разрабатывался, что называется, «с нуля», у его авторов была возможность не переносить в него все неудачные особенности любого из предшествующих языков. Особенно это касается проблемы совместимости с предыдущими версиями. В результате получился действительно простой, удобный и современный язык, который по мощности не уступает С++, но существенно повышает продуктивность разработок [15].

Ввиду высокой объектной ориентированности, язык С# великолепно подходит для быстрого конструирования различных компонентов – от высокоуровневой бизнес-логики до системных приложений, использующих низкоуровневый код. Также следует отметить, что С# является и Web-ориентированным – с помощью простых встроенных конструкций языка ваши компоненты легко превратятся в Web-сервисы, к которым можно будет обращаться из Интернета, используя любой язык на любой операционной системе. Дополнительные возможности и преимущества С# перед другими языками приносит использование современных Web-технологий, таких как: XML (Extensible Markup Language) и SOAP (Simple Object Access Protocol). Удобные методы для разработки Web-приложений позволяют программистам, владеющим навыками объектно-проектированного программирования, легко освоиться в разработке Web-сервисов [15].

Рассмотрим перечисленные выше методы:

Интерполяция полиномом Лагранжа [13]:

Пусть на отрезке [a, b] даны n + 1 различных значений аргумента: x, x, ...,  xn и известны для функции y = f(х) соответствующие значения выражений

f(x0) = y0, f(x1) = y1,  . . ., f(xn) = yn.

(1)

Требуется построить полином Ln(x) степени не выше n, имеющий в заданных узлах x, x, ...,  xn те же значения, что и функция f(х), т. е. тaкой, что

Ln(xi) = yi (i = 0, 1, ..., n)

Будем искать Ln(x) в виде:

Ln(x)=l(x)+ l(x)+...+ ln(x),

(6)

где li(x) - полином степени n, причем

li(xk) =

(7)

Очевидно, что требование (7) с учетом (6) обеспечивает выполнение условий (3) (Рисунок 2).

Рисунок 4. li (x) - полином степени n

Так как искомый полином li(x) обращaется в нуль в n точках x,…, xi - ,  xi + , ...,  xn, то он имеет вид

li(x) = Ci (x - x) (x - x) … (x - xi-) (x - xi +) ... (x - xn)

(8)

где Сi - постоянный коэффициент. Полагая в формуле (8) х = xi и учитывая, что li(xi) = yi, получим:

yi = Ci (xi - x)(xi - x) ... (xi - xi -)(xi - xi +) ... (xi - xn).

Отсюда

Сi = .

Заметим, что ни один из множителей не равен нулю. Подставляя Сi a (8), а также с учетом (6), окончaтельно имеем:

(9)

Это и есть интерполяционная формула Лагранжа.

Формуле (9) можно придать более сжатый вид, используя обознaчение

In+(х) = (x - x0) (x - x1) … (x - xn). (10)

Aифференцируя по х это произведение, получим:

I' n+(х) = (x - x) ... (x - xj - ) (x - x j + ) ... (x - xn).

Полагая х = хi (i = , , ..., n), получим:

I' n+(хi)= (xi - x) …(xi - xi -) (xi - xi +) ... (xi - xn). (11)

Подставляя выражения (10) и (11) в формулу (9), получим

Ln(x) = In+(х)

(9’)

Пример 1. Положим n = 1. Ясно, что мы имеем в этом случае две точки и интерполяционная формула Лагранжа дает уравнение прямой, проходящей через две заданные точки. Обозначив абсциссы этих точек через a и b, получим интерполяционный полином в виде

.

Примем n = 2. Тогда получим уравнение параболы, проходящей через три точки. Если обозначить x0 = a, x1 = b, x2 = c, то искомое уравнение имеет вид

Пример 2. Пусть заданы значения x0 =1, x1 =3, x2 =7, x3 =12 и y0 =5.6, y1 =6.7, y2 =8.1, y3 =10.3 определить значение неизвестной функции для х = 6,5.

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

После подстановки заданных значений в формулу Лагранжа получаем:

Определим значение f(х) при х = 6,5:

Кубическая сплайн-интерполяция [16].

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

1)

2) Для любого частичного промежутка -многочлен третьей степени

3)

Для задания надо определить 4 коэффициента для каждого промежутка , т. е. параметров.

Условия 1) требуют чтобы во внутренних узлах сплайн и его производные до 2-го порядка были непрерывны.

Это дает условия для определения параметров, еще условие содержится в 3).

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

Возьмем в качестве граничных условия

4)

Для построения кубического интерполяционного сплайна могут быть использованы различные подходы. Проведем построение сплайна, исходя из условийИз 1) и 2) следует, что S(x) непрерывная функция, линейная на каждом т. е. S(x) - линейный сплайн.

Обозначив , получаем

(33)

для .

Интегрируя (5), получаем

(34)

(35)

и - постоянные интегрирования.

Условия 3) дают:

(36)

Из (36) получаем:

Подставляя и в (7), получаем:

(37)

После преобразования

из (37) получаем

(38)

Из (34) получаем

(39)

Из (39) находим односторонние пределы производной для узла ,

(40)

(41)

Подставляя (40) и (41) в условие непрерывности в узле получаем :

(42)

Дополняя (42) равенствами из условия 4) : , получаем систему уравнений относительно вида :

(43)
с квадратной матрицей .

и квадратной матрицей

Координатами вектора являются значения .

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

Матрица с диагональным преобладанием невырождена. Следовательно, система (42) однозначно разрешима, т. е. существует единственный кубический интерполяционный сплайн. Кроме условий 4) - условий "свободного провисания" интерполяционной кривой в точках и , могут быть известны наклоны интерполяционной кривой в граничных точках. Тогда условия на границах имеют вид:

(44)
Могут быть использованы и другие варианты.

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

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

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

если , то , где , ,

если , , то оценка имеет вид для .

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

Аппроксимация методом градиентного спуска [16].

Общая схема

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

Решается задача минимизации функции j(x) на всём пространстве En. Методы спуска состоят в следующей процедуре построения последовательности {xk}. В качестве начального приближения выбирается любая точка x0ÎEn. Последовательные приближения x1, x2, … строятся по следующей схеме:

1) в точке xk выбирают направление спуска - Sk;

2) находят (k+1)-е приближение по формуле xk+1=xk-hkSk.

Направление Sk выбирают таким образом, чтобы обеспечить неравенство f(xk+1)<f(xk) по крайней мере для малых значений величины hk. На вопрос, какому из способов выбора направления спуска следует отдать предпочтение при решении конкретной задачи, однозначного ответа нет.

Число hk определяет расстояние от точки xk до точки хk+1. Это число называется длиной шага или просто шагом. Основная задача при выборе величины hk - это обеспечить выполнение неравенства j(xk+1)<j(xk).

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

xk+1=xk-hk cos

где - cos=

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

Наибольшее распространение получили следующие алгоритмы:

1. (без коррекции);

2. если ; если

3. , если ; , если; ,если ,

где –угол между градиентами на предыдущем и текущем шаге;

и – заданные пороговые значения выбираются субъективно

(например, ).

Вдали от оптимума направление градиента меняется мало, поэтому шаг можно увеличить (второе выражение), вблизи от оптимума направление резко меняется (угол между градиентами R(x) большой), поэтому h сокращается (третье выражение).

Метод градиентного спуска. 

 Рассмотрим функцию f, считая для определенности, что она зависит от трех переменных x, y,z. Вычислим ее частные производные дf/дх, дf/ду, дf/дz и образуем с их помощью вектор, который называют градиентом функции:

grad f(x, у, z) = дf (х, у, z) /дх*i+дf( x, у, z)/ду*j+дf(x, y, z)/дг*k.

Здесь i, j, k - единичные векторы, параллельные координатным осям. Частные производные характеризуют изменение функции f по каждой независимой переменной в отдельности. Образованный с их помощью вектор градиента дает общее представление о поведении функции в окрестности точки (х, у, z). Направление этого вектора является направлением наиболее быстрого возрастания функции в данной точке. Противоположное ему направление, которое часто называют антиградиентным, представляет собой направление наиболее быстрого убывания функции. Модуль градиента
 
|grad (х, у, z)| =Ö (дf/дх (х, у, z))2 +(дf/ду( x, у, z))2+(дf/дг(x, y, z))2.

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

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

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

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

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

f(x1, ...,xi+ gi, ..., xn) - f(x1, ..., xi, ..., xn) gi

1.Алгоритм с центральной пробой

2. Алгоритм с парными пробами

f(x1, ...,xi+ gi, ..., xn) - f(x1, ..., xi- gi..., xn) 2gi

где gi – пробный шаг по i-й переменной, выбираемый достаточно малым для разностной оценки производной.

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

Df(x1, ...,xi+ gi, ..., xn) - f(x1, ..., xi, ..., xn)

Df(x1, ...,xi+ gi, ..., xn) - f(x1, ..., xi - gi,..., xn)

будет допущена большая ошибка.

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

 На рис. 5 изображены линии уровня функции двух переменных u=f(х, у), , и приведена траектория поиска ее минимума с помощью метода градиентного спуска.

Рис. 5. - Линии уровня функции двух переменных и траектория поиска ее минимума.

Список используемой литературы:

1.  , Фукс обработка исходных данных для построения цифровой модели рельефа местности. - Вестник ТГУ, 2003 № 000 с.281-285.

2.  Вычислительная геометрия: Введение. Пер. с англ. – М.: Мир 1989. – 478с.

3.  Фукс и исследование алгоритмов интерполяции однозначных поверхностей и их использование при построении цифровых моделей рельефа: Диссер. На соискание уч. степ. к. т.н. Томск, ТГУ, 2001