Восстановление двумерных геополей: проблемы и решения

СПИСОК ЛИТЕРАТУРЫ

1. Разевиг В.Д. Проектирование печатных плат в P-CAD 2001. -М.: Солон-Р, 2001. - 557 с.

2. Ненашев А.П., Коледов JI.A. Основы конструирования микроэлектронной аппаратуры. - М.: Радио и связь, 1981. - 109 с.

3. Варне Дж. Электронное конструирование: Методы борьбы с помехами: Пер. с англ. - М.: Мир, 1990. - 246 с.

4. Джонсон Г., Грэхем М. Конструирование высокоскоростных цифровых устройств: начальный курс черной магии: Пер. с англ. - М.: Издательский дом «Вильяме», 2006. - 1016 с.

5. Кутявина С.К., Кошелева С.Ю., Жердев A.A. Оптимизация проектирования печатных плат в среде САПР P-CAD 2001 с учетом конструкторской сложности электронных схем // Современные средства и системы автоматизации: Труды IV науч-но-практ. конф. - Томск, ТУСУР, 2004. - С. 124-128.

6. Стешенко В.Б. P-CAD. Технология проектирования печатных плат. - СПб.: БХВ-Петербург, 2003. - 652 с.

7. Овсищер П.И., Лившиц И.П., Орчинский А.К. и др. Компоновка и конструкции микроэлектронной аппаратуры: Справочное пособие / Под ред. Б.Ф. Высоцкого, В.Б. Пестрякова, O.A. Пятлина. - М.: Радио и связь, 1982. - 270 с.

8. Кутявина С.К., Аришин Е.А. Оптимизация этапов проектирования в средах САПР для повышения качества трассировки ПП // Молодежь и современные информационные технологии: Сб. трудов IV Всеросс. научно-практ. конф. студентов, аспирантов и молодых ученых. - Томск: Изд-во ТПУ, 2006. -С. 72-75.

Поступила 06.06.2007г.

УДК 004.67:514.83

ВОССТАНОВЛЕНИЕ ДВУМЕРНЫХ ГЕОПОЛЕЙ: ПРОБЛЕМЫ И РЕШЕНИЯ

М.В. Копнов, Р.В. Ковин

Институт «Кибернетический центр» ТПУ E-mail: kopnovmv@tpu.ru

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

Введение

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

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

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

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

• как правило, точки опробования представляют собой нерегулярную сеть точек.

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

При восстановлении геополей по мнению большинства исследователей [1, 2] метод должен:

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

• быть устойчивым относительно структуры сети исходных данных;

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

• обеспечивать возможность проведения вариантных расчетов в процессе восстановления геополя;

• быть достаточно технологичным, т. е. достаточно точным и экономичным в расходовании машинных ресурсов.

Среди наиболее успешных коммерческих пакетов, позволяющих решать задачи восстановления геополей, можно отметить программные продукты Spatial Analyst и Geostatistical Analyst для ГИС Arc-GIS фирмы ESRI (США), Vertical Mapper от Ma-

plnfo Corporation (США) для Maplnfo Professional, Encom Discover от Encom (Австралия) для Maplnfo Professional. Среди отечественных разработок можно отметить систему SurfMapper для Maplnfo Professional [3]. Перечисленные пакеты не являются самостоятельными системами, а представляют собой дополнительные модули к указанным универсальным геоинформационным системам. Среди систем, не являющихся геоинформационными, стоит выделить пакет Surfer от Golden Software (США).

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

Детерминистические методы

При использовании детерминистических методов предполагается, что анализируемые данные описываются некоторой детерминистической функцией V(x, у), определенной на исследуемой области S, где (х, у) - координаты точки. Задача состоит в том, чтобы, базируясь на известных данных Vj=V(Xi, yl) - значений, измеренных в точках (х;, у;) - и на другой информации об исследуемом объекте (явлении), построить функцию V(x, у) для всей исследуемой области S. После этого значение гео-поля в любой точке исследуемой области S может быть просто вычислено по формуле.

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

• с учетом всех исходных точек следует рассчитать детерминистическую функцию V(x, у) (это может быть, например, решение системы линейных уравнений или проведение статистических расчетов);

• рассчитать значения геополя в требуемых точках непосредственно по детерминистической функции V(x, у).

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

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

бальные интерполяторы заметно сглаживают поверхность. Поэтому для преодоления таких недостатков используют локальные интерполяторы [4].

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

• нахождение ближайших исходных точек к расчетной точке геополя;

• расчет детерминистической функцию ¥(х, у) на основе найденных точек;

• вычисление значения геополя непосредственно по детерминистической функции ¥(х, у);

• выполнение первых трех этапов для всех рассчитываемых точек геополя.

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

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

Точность восстановления геополей

Известно, что задача восстановления геополя является некорректной [1-5]. Поэтому она может быть решена разными методами и с разной точностью. В каждом методе решения этой задачи вводятся определенные представления о природе геополя. В итоге каждый метод обеспечивает различную интерпретацию исходных данных. Основная сложность заключается в построении наиболее точной поверхности, как можно ближе соответствующей действительности (описываемому явлению). Достижение этой цели связано с рядом «факторов успеха»:

• наличие достаточного количества исходных достоверных данных;

• глубокое понимание исследуемого явления;

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

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

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

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

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

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

кровля пласта >-\ В

/' ^— подошва пласта

кровля пласта \ /Л >___ В

область выклинивания

/ / / деформ-ая подошва ,__ \ пласта

исходная подошва пласта

Рис. 1. Пример уточнения формы нефтяного пласта: а) до редактирования и 6) после

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

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

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

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

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

• для выявления главных (локальных) закономерностей необходимо использовать методы глобального (локального) тренд-анализа;

• использование строгих интерполяторов в условиях, когда исходные данные содержат ошибки, недопустимо.

Проблемы вычислительной эффективности методов

Решение задач восстановления геополей всегда требовало больших объемов памяти и временных затрат. Несмотря на стремительное развитие вычислительной техники остается актуальной проблема вычислительной эффективности методов и алгоритмов восстановления геополей. Ресурсы современных компьютеров позволяют обрабатывать огромные массивы пространственных данных, однако время расчета по-прежнему может быть недопустимо большим. Использование высокоэффективных алгоритмов позволяет сократить время расчета в десятки, а то и сотни раз. К таким алгоритмам можно отнести алгоритмы поиска, использующие пространственное индексирование [6].

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

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

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

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

• рассчитывается значение восстанавливаемого узла регулярной сети;

• если регулярная сеть не восстановлена - выполняется шаг 1.

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

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

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

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

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

2000-1-----—1|||-----———]—.

/

1800---------------у----

Ч /

ф 1600------—[—|—|----^------

^ 1400-

Число ячеек регулярной сети

Рис 2. Сравнение вычислительной эффективности алгоритмов восстановления геополя

Таким образом, алгоритм восстановления геополя можно кратко описать следующим образом:

• с помощью алгоритма Брезенхейма [7] определяются индексы граничных ячеек окружности заданного радиуса;

• выбирается точка исходного набора данных;

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

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

• если не пройдены все точки исходного набора данных - шаг 2;

• для каждой ячейки регулярной сети вычисляется значение уровня поля.

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

Заключение

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

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

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

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

Работа выполнена при поддержке гранта РФФИ №0607-89190.

СПИСОК ЛИТЕРАТУРЫ

1. Аронов В.И. Методы построения карт геолого-геофизических признаков и геометризация залежей нефти и газа на ЭВМ. -М.: Недра, 1990. - 301 с.

2. Каневский М.Ф., Демьянов В.В. Введение в методы анализа данных по окружающей среде // Проблемы окружающей среды и природных ресурсов. - 1999. — № 11. — С. 4-11.

3. Ковин Р.В., Марков Н.Г. Геоинформационные технологии для анализа двумерных геополей. - Томск: Изд-во Том. ун-та, 2006. -166 с.

4. Burrough P.A., McDonnell R.A. Principles of Geographical Information Systems. - Oxford: Oxford University Press, 1998. - 333 p.

5. Gousie M.B., Williams G., Agnitti Т., Doolittle N. CompSurf: An Environment for Exploring Surface Reconstruction Methods on a Grid // Computers & Geosciences. - 2003. - № 9. - P. 1165-1173.

6. Ласло M. Вычислительная геометрия и компьютерная графика на С++ / Пер. с англ. - М.: Изд-во «БИНОМ», 1997. - 304 с.

7. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. - М.: Мир, 1989. - 478 с.

Поступила 16.10.2007 г.