Какой алгоритм используется инструментом ArcGIS Watershed?

10

Кто-нибудь знает, какой тип алгоритма используется в инструменте ArcGIS Watershed (в пакете Spatial Analyst)?

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

Я посмотрел на следующих страницах справки ArcGIS Online:

Так что да, он использует растр направления потока, но какой алгоритм он использует для обхода растра?

Обратите внимание, я не ищу ответы в духе «он использует D8 ..». D8 на самом деле не алгоритм, а модель, помогающая определить алгоритм, который вы бы использовали. То есть вы могли бы реализовать схему D8 в алгоритме поиска в глубину и / или в алгоритм поиска в ширину

Джеймс
источник
Джеймс, я пытаюсь сделать то же самое, то есть создать приложение, которое принимает определенную координату и дает нам водораздел. Я использую Python. Давайте поговорим о нашем прогрессе.
Я также использую Python. Я начинаю с более простой задачи вычисления сетки направления потока и продолжения оттуда.
Джеймс

Ответы:

6

Метод, который я реализовал на нескольких языках и считаю, что ESRI использует (извините, никаких ссылок, кроме Дженсона и Доминге, процитированных в другом месте на этой странице), состоит в том, чтобы начать с предоставленной пользователем ячейки "точки застывания" или ячейки на краю сетки направления потока (fdr), исследуйте ее восемь соседей, чтобы найти, какой из этих прямых течет в текущую ячейку, и назначьте эти ячейки текущему «водоразделу» в выходной сетке. Затем функция рекурсивно вызывает себя один раз для каждого из входящих соседей. Этот процесс повторяется до тех пор, пока все входящие клетки не будут исчерпаны для точки застывания, а затем будет повторяться для всех точек застывания.

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

(см. ниже комментарий Вубера о различных методах рекурсии, если вы собираетесь RYO)

_____________ РЕДАКТИРОВАТЬ _____________

В качестве примера выкопали мой старый C-код (примечание: хотя большинство питонеров могут захотеть бежать из комнаты, это не должно быть слишком плохо). Думаю, это может быть интересно проиллюстрировать. Несмотря на то, что я только сейчас поверхностно знаком с рекурсией в ширину и глубиной, я думаю, что моя рутина действительно в глубину (и что мое описание на естественном языке выше вводит в заблуждение), основываясь на этой публикации в стеке (надеюсь, @) whuber или другой человек умнее меня может подтвердить / опровергнуть).

Код: объяснение: idirэто растр значений направления потока. offsetотносится к центральной ячейке, которая в настоящее время анализируется, и offпроверяет каждого из соседей этой ячейки. Это вызывает другую функцию, does_it_flow_into_meкоторая возвращает логическое значение относительно того, указывает ли flowdir соседней ячейки на текущую ячейку. Если верно для соседа, вернитесь в это место.

void shed(int init_x, int init_y, int basin_id){

int i, j, offset, off, flow_dir;

offset = ((init_y - 1) * nc) + (init_x - 1);
*(basin + offset) = basin_id;


/* kernel analysis */
for (i = -1; i <  2; i++) {
    for (j = -1; j <  2; j++) {
        if ((i) || (j)) {

            off = offset + (j * nc +  i);
            flow_dir = *(idir + off);


            if (does_it_flow_into_me(i,j,flow_dir)){
                shed(init_x+i, init_y+j,basin_id);
            }
        } /*not center */
    } /* do - j */
} /* do - i */
}
Roland
источник
Вы описываете рекурсию в ширину. С помощью небольшого стека вы можете реализовать эффективную рекурсию в глубину, которая требует мало памяти. Основная проблема производительности будет касаться больших водосборов, где мозаичные элементы сетки, возможно, придется многократно менять местами в оперативной памяти. Однако, как обсуждалось в комментариях к другим ответам, реальная проблема касается совмещения с ячейками, в которых нет однозначно определенного направления D8, особенно ячеек, лежащих в обширных плоских горизонтальных участках (таких, как те, которые созданы предварительными процедурами заполнения приемника).
whuber
Определенно проблема мусора в мусоре. То, что я и большинство GIss делаю, не очистит ввод! Звучит так, как будто мне нужно пойти посмотреть на глубину рекурсии, чтобы придать блеск моему взлому.
Роланд
Я не думаю, что это мусор - помните, независимо от того, как реализация разбита, исходный ввод - это сама DEM, а не чья-то кодировка D8 - но это определенно сложная задача. В реальном мире есть много мест, которые настолько плоские, что трудно определить направление потока: любой статический водоем является хорошим примером. По сути, вам нужно найти выходы из озер и других плоских областей, и вам нужно справиться с плоскими участками, которые имеют несколько выходов. Это требует нелокальных поисков, которые трудно сделать.
whuber
Я, вероятно, смущен тогда. Я думаю, что мы обсуждаем help.arcgis.com/en/arcgisdesktop/10.0/help../index.html#//… , который принимает flowdir в качестве входных данных. Не хочу втягивать нас в сорняки, если я недостаточно внимательно прочитаю остальные!
Роланд
Нет, я думаю, что вы правы: когда я перечитываю вопрос, я вижу, что он сосредоточен именно на обработке растра направления потока в качестве входных данных, а не на более общей ситуации, которую я представлял. Так что +1 к вашему ответу за то, что обратились к нему напрямую, с пониманием и полезными указателями.
whuber
4

ArcGIS помощь говорит:

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

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

Существует много альтернатив D8, таких как Rho8, Froh8 и Stream Tubes, но большинство программ ГИС, включая ArcGIS, склонны использовать D8, поскольку он проще и менее требователен к вычислениям, чем другие.


Несколько лет назад я работал над проектом разграничения водоразделов, и мы столкнулись с несколькими проблемами из-за того, что ArcGIS использовал метод D8. Две основные проблемы были

  • D8 допускает только однонаправленный поток. Вода может вытекать только в одном направлении из одной ячейки.
  • Генерируемые потоки потока имели огромное смещение вдоль диагональной оси. Это породило странно выглядящие потоки.

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

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

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

Я обнаружил, что мой простой код, который делал это для растров ASCII, выдает почти аналогичный результат по сравнению с инструментом ArcGIS Watershed. Иногда раньше было несколько ячеек на границе, поэтому я убежден, что ArcGIS следует неизменному алгоритму D8.

Девдатта Тенгше
источник
Спасибо за разработку. Но каков алгоритм использования направлений D8 для поиска водоразделов? Пожалуйста, смотрите комментарии после ответа dmahr .
whuber
Привет, спасибо, но это на самом деле не отвечает на вопрос. Вы ударили по нему предложением «Для этой ячейки вы найдете все ячейки в окрестности, которые способствуют ей. Для каждой из этих соседних ячеек вы найдете ячейки, которые способствуют им и так далее». Есть много разных алгоритмов для реализации этого поиска. Вопрос в том, какой из них
Джеймс
4

Об этом уже спрашивали , хотя, возможно, в несколько ином контексте. Все инструменты геообработки в наборе инструментов гидрологии Spatial Analyst используют модель направления потока D8 , как указано на странице Как работает направление потока :

Существует восемь действительных выходных направлений, относящихся к восьми соседним ячейкам, в которые может перемещаться поток. Этот подход обычно называют моделью потока в восьми направлениях (D8) и следует подходу, представленному в Jenson and Domingue (1988).

Копия статьи Дженсона и Доминге (1988) доступна здесь .

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

dmahr
источник
Итак, я полагаю, что последующим вопросом будет, как этот алгоритм исправлен, чтобы вернуть водосбор?
Джеймс
Инструмент «Водораздел» перемещает растр направления потока от точек заливки. Это инструмент обратного накопления потока, за исключением того, что вместо выходного растра, описывающего количество ячеек, он сообщает идентификатор точки застывания.
dmahr
1
Хорошо, я думаю, мне нужно быть более конкретным. Я знаю концепцию того, что он делает. Я не знаю, какой алгоритм реализован. Т.е. я предполагаю, что это какой-то алгоритм поиска, но он все еще может быть; сначала в ширину, сначала в глубину, итеративно углубляясь в глубину и т. д.
Джеймс
1
спасибо дмахр. @whuber: Насколько я знаю, разные алгоритмы поиска могут давать немного разные результаты? И да, поиск общего алгоритма не является проблемой, но изучение того, как ESRI обрабатывает специфичные для водораздела области (например, плоские части DTM), полезно.
Джеймс
1
Джеймс Пожалуйста, отредактируйте свой вопрос, чтобы прояснить этот последний момент, чтобы эта ветка перестала собирать бесполезные ответы «это D8». (Что это полезно о комментариях D8 в том , что если вы согласны , что D8 приводит к своеобразному направлению потока графа, то есть уникальное правильное решение водосбора проблемы разграничения, поскольку водоразделы свойства самого графа. Таким образом , если есть любые неопределенности, в которых они должны находиться (а) определение «водораздела», (б) способ вычисления направлений D8 или (в) способ обработки горизонтальных ячеек (т. е. без уникального направления D8).)
whuber
0

Чтобы больше обдумать этот вопрос, я провел анализ водораздела по дуге: я взял (заполненную) матрицу высот, рассчитал направление потока и поместил несколько точек, которые соответствуют местоположениям в ранее рассчитанной сети потоков. Я запустил инструмент «водораздел», и он дал мне несколько хороших бассейнов, в значительной степени покрывающих большую часть оставшейся области «вверх по течению» (как и следовало ожидать):

водораздел изображения

Затем я запрограммировал алгоритм быстрого поиска в Python (как ответ выше), который проверяет сетку направления потока и «следит» за путями потока. Для каждого узла я проверяю 8 соседей и, если соседний поток входит в текущий узел, я рекурсивно вызываю ту же функцию с соседним узлом в качестве входного.

Псевдо (ish) код:

class d8():
    def __init__(self, arr):
       self.catchment = set()
       self.arr = arr

    def search(self, node):
        """ Searches all neighbouring nodes to find flow paths """ 

        # add the current node to the catchment
        self.catchment.add(node)

        # search the neighbours, ignore ones we already visited
        for each_neighbour:
            if neighbour is in self.catchment:
               do nothing

            # if the neighbour flows into the current node, visit that neighbour
            elif neighbour_flows_into_me:
               self.search(neighbour)

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

Кто-нибудь знает, что я делаю не так?

Джеймс
источник