Войти
Уголок tool-программСтатьи

К вопросу о неизвестных высотах SRTM

Автор:

версия документа: 0.9

Введение
Как оно бывает
Алгоритм
Ссылки
Код
Рисунок 1
Рисунок 2
Рисунок 3

Введение


  Периодически в проектах, где отсутствует дизайнер ландшафтов, готовый денно и нощно создавать красивые и притом реалистичные пейзажи для обширных игровых пространств (признайся читатель, у тебя прямо сейчас никого похожего на примете нет?), возникает желание воспользоваться картами высот, взятыми где-нибудь на просторах Интернета.
  Карта высот обычно представляет собой равномерный непрерывный грид (прямоугольный кусок карты высот), привязанный к определённым географическим координатам. Существует немало различных форматов файлов гридов и организаций публикующих их в открытом виде с рекламными, образовательными, научными и, дай бог понять, какими ещё целями.
  Одной из этих прекрасных организаций предоставляющих такие данные является NASA запустившая и успешно выполнившая проект Shuttle Radar Topography Mission (SRTM). Следует отметить, что порой использование некоторых гридов в России запрещены законодательством без санкции свыше. Особенно это касается данных с коммерческих спутников разрешением два и менее метров на пиксель, однако в игровой индустрии такая точность реальных данных редко нужна. Применяя фрактальные алгоритмы, можно не ухудшая реалистичности пейзажа получить более высокое разрешение.
  В результате миссии NASA по топографической съёмке общественности стали доступны карты высот с разрешением около 90х90 м сначала версии 1, а потом и SRTM v2. Первая версия представляла собой сырые гриды. Береговая линия в них нечётко выделена (касается рек, озёр и морей), что связанно с особенностями радарной съёмки и на картах высот присутствуют участки, для которых высоты не были определены, т.н. void spaces, которые я придумал называть по-простому, антифактами.
  Надо сказать эти неопределённые области весьма неудобны при практическом применении, поскольку неприятно видеть как посреди поля из ниоткуда возникает дыра глубиной -32768 метров.
  Версия два SRTM выделила чёткие границы водных поверхностей, а также подкорректировала высоты для тех участков (пиков и впадин), которые с высокой погрешностью усреднялись по окружающим. Однако антифакты кое-где так и остались.
  Статья разъясняет, как с помощью методов элементарной математики избавиться от этих белых пятен на картах местности, а точнее достроить высоты так, чтобы никто и не догадался, что где-то когда-то отсутствовали данные. Вопрос насколько такие высоты соответствуют реальным данным, мы оставим за рамками этой статьи.
  Статья полезна прежде всего тем, кто когда-нибудь сталкивался с подобными проблемами в процессе импорта карт высот.

Как оно бывает


  Сразу оговорюсь, что интерполяцию мы будем проводть с помощью метода обратных взвешенных расстояний (Inverse Distance Weights, IDW) который легко воспринимается, легко реализуется и даёт неплохие результаты, впрочем уступая конечно же по точности кригингу  на гридах с ярко выраженным изменением типа рельефа (разброса соседних высот).
  Обратим внимание на рисунок 1. В верхнем ряду изображена карта высот до применения алгоритма: раскрашенная повысотно, и два анализа положения точек относительно окружающих с различными параметрами радиуса поиска. Последние два изображения приведены в большей степени для оценки красоты изображения до и после. Красным цветом изображены области антифактов. Второй ряд картинок представляет собой исправленный грид. В третьем ряду приведены производные по горизонтали и вертикали (зелёным и синим цветом) опять же в большей степени для полноты картины что стало после интерполяции, чем для целей интерполяции.
 

Алгоритм


  1.Сначала находим точки являющиеся антифактами и выясняем порядок в котором мы будем искать в них значения. Порядок нужен такой, чтобы дыра на каждой итерации алгоритма уменьшалась, схлопывалась от границ к центру. Такой подход гарантирует что в месте, где сойдутся интерполируемые высоты не будет никаких скачков высот и видимых разрывов поверхности. Данная операция выполняется с помощью функции AnalyzeRemoveSequence().
  2.Интерполируем высоты в данных точках по IDW алгоритму (вызовы IDW_Sum() и IDW_Value()). Суть этого метода состоит в том чтобы взять линейную комбинацию известных высот с весами обратно пропорциональными расстояниям от этих высот до искомой точки. Или попросту говоря, чем дальше высота, тем меньше она нас интересует. Алгоритм управляется несколькими параметрами.
  Первый это радиус, описывающий окружность с центром в искомой точке, которая охватывает точки (значения высот), которые попадут в расчёт. Второй параметр - это степень w, в которую возводится расстояние при подсчёте веса. Часто это двойка, но широко используются и другие от 1 до 3. Также иногда дополнительно вводится малая константа c. IDW метод можно записать как:
  H(i0)= Sum(i=1, n, H(i) * W(i0, i)

  Где 
  n - число точек попавших в очерченный радиус.
  i0 - точка, значение высоты в которой ищется.
  H(i)- высота в какой-то точке грида i, попавшей в указанный радиус.                
  W(i0, i) = K(i) / Sum(i=1, n, K(i))
  K(i)= 1/(c+D0(I)^w) 
  D0(i)- расстояние от точки i до i0
  Существуют и иные, более упрощенные записи метода.

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

Ссылки


1. "О данных SRTM и их импорте с помощью Arcinfo Workstation",
http://gis-lab.info/qa/srtm.html
2. The Shuttle Radar Topography Mission home page,
http://www2.jpl.nasa.gov/srtm/

Страницы: 1 2 3 Следующая »

26 января 2006