Порядок сканирования

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

2-ой способ: Нечетные строки будем кодировать слева направо, а четные – в обратном направлении (рис.б)(т.е. изменим порядок сканирования) Направление сканирования напоминает движение быка, вспахивающего поле. Отсюда название этого способа сканирования – Boustrophedon (греч. – бык, вспахивающий поле). Теперь при переходе к новой строке первая ячейка является смежной последней ячейке старой строки. Так в линейном разложении растра сохраняется автокорреляция и повышается эффективность кодирования. (Автокорреляция – соседние ячейки растровой модели имеют большую вероятность быть одинаковыми, чем разобщенными).

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

Например. Для растра размером 2 x 2 применяется обычный порядок сканирования. На следующем уровне матрица размера 4 x 4 складывается из четырех матриц размера 2 x 2, расположенных в таком же порядке, как ячейки матрицы 2 x 2. Аналогично формируется линия сканирования любой матрицы порядка 2n. Матрица формируется уровень за уровнем, повторяя один и тот же шаблон размера 2 x 2.

При сканировании растра по Мортону линия сканирования представляет собой фрактал.

Недостатки сканирования по Мортону очевидны. Во-первых, присутствуют скачки, (в примере, от ячейки 7 к ячейке 8). Во-вторых, таким способом можно кодировать только растры размера, кратного двум.

№14 Модель на нерегулярной триангуляционной сетке. Выбор узлов и разбиение. // ДАШИН

1. Нерегулярные триангуляционные сети (Triangulation Irregular Network – TIN) являются альтернативой растровым DEM и используются во многих геоинформационных системах, системах автоматизированного картографи-рования, пакетах построения контуров.

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

2. Рассмотрим задачу выбора размещения точек триангуляции на следующем примере: имеется растровая DEM или оцифрованные изолинии рельефа, необходимо выбрать точки таким образом, чтобы наиболее точно представить поверхность в TIN-модели. Рассмотрим алгоритмы выбора точек DEM. Алгоритм Фаулера – Литтла основан на поиске особых точек поверхности – пиков, хребтов, впадин и т.п. Поверхность проверяется скользящим окном размера 3 x 3. При этом соседи центральной ячейки помечаются плюсом, если их высота больше, и минусом если меньше. Очевидно, точка является пиком, если все восемь ее соседних ячеек помечены минусом. Аналогично, точка является впадиной, если все восемь ее соседних ячеек помечены плюсом. Точка является ущельем или перевалом, если плюсы и минусы вокруг точки образуют хотя бы два полных цикла: { + + – – – – + + } = 2 цикла; { + – + – + – + – } = 4 цикла. Далее слой обрабатывается окном 2 x 2 таким образом, что каждая ячейка по очереди становится во все позиции окна. Точка является гребнем горы, если в каждом из четырех окон она не самая низкая. Аналогично, точка принадлежит протоку, если во всех четырех окнах она не самая высокая. За-тем, начиная от ущелий или впадин, ищутся связные протоки, пока не будут достигнуты пики (поиск можно вести и в обратном направлении). В результате получаются соединенные линиями пики, протоки, впадины, ущелья и перевалы. По выбранным точкам создаются треугольники.

Алгоритм VIP (очень важная точка) в отличие от предыдущего алгоритма, в котором идентифицируются основные особенности местности, проверяет поверхность локально, используя окно 3 x 3. Это упрощение впервые использовано в ГИС ESRI Arc/Info. Ячейка в растровой DEM имеет восемь соседей, образующих четыре тройки (рис. 28-а).

Для каждой тройки ячеек по соответствующей вариограмме рассчитывается коэффициент вариации. Первая тройка имеет нулевой коэффициент вариации, вторая и четвертая – низкий, а третья – высокий коэффициент вариации. Далее оценивается средняя вариация значения узла растровой DEM. Узлы с высокими показателями вариации включаются в результирующее разбиение, остальные отбрасываются. Третий алгоритм выбора точек триангуляции основан на оптимизации существующего разбиения. Для заданной растровой DEM требуется найти такое подмножество точек (заданной мощности), что при соединении их линиями в треугольники получится как можно лучшее представление поверхности. По узлам регулярной сети легко построить исходное разбиение на треугольники. В начале работы алгоритма разбиение полностью соответствует исходной растровой DEM. Далее все точки разбиения поочередно проверяются следующим способом. Точка временно удаляется, соответственно изменяется и разбиение. Затем определяются треугольники, содержащие удаляемую точку, оценивается разность возвышений этой точки, полученных из DEM и из трех верши треугольника. Эта разность записывается в базе данных и удаленная точка восстанавливается. Когда таким образом будут обработаны все точки, нужно удалить точки с наименьшими значениями запом-ненных в базе данных разностей. После того, как выбрано необходимое количество узлов TIN, нужно выбрать способ разбиения поверхности на треугольники. При этом желательно получить близкие к равносторонним треугольники, чтобы произвольная точка поверхности была как можно ближе к узлам TIN, где значения возвышения известны точно. Рассмотрим два способа разбиения на треугольники.

3.Способы хранения TIN: по треугольникам и поточкам. При кодировании сети по треугольникам для каждого треугольника в базе данных создается запись, содержащая его уникальный номер, координаты трех его вершин, а также номера трех смежных с ним треугольников (рис.30-а). Во втором способе (рис. 30-б) для каждой точки разбиения сохраняется ее уникальный номер, координаты и список точек, с которыми она соединена прямыми (по часовой стрелке).