4.2.2. Ієрархічні растрові структури

Растрові структури зручні для відображення ієрархічно організованої географічної інформації. Подання растрової інформації у вигляді кількох внутрішньо пов'язаних рівнів, при якому нижній рівень відповідає вихідному поданню растра, що має розмір NxM елементів, а кожний розміщений вище є узагальненням інформації в т комірках нижчого рівня, називається ієрархічною растровою структурою. Ієрархічні растрові структури іноді називають пірамідальними, або деревоподібними.

Частковим, однак таким, що досить часто використовується в ГІС, різновидом ієрархічних растрових структур є квадротомічні структури растрових даних, чи квадродерева (quadtree, Q-tree), які відрізняються тим, що в них кожен вищерозміщений рівень є узагальненням інформації строго за чотирма комірками нижчерозміщеного рівня (рис. 4.2). Завдяки цьому квадродерево має жорстку структуру, що не вимагає додаткового опису. Це — деревоподібний граф, ступінь вершини кожного вузла якого дорівнює 4, тобто розмір комірки кожного вищерозміщеного шару в 4 рази більший, ніж попереднього.

Рис. 4.2. Подання просторового об'єкта з використанням квадротомічної растрової структури

У. Тоблер і 3. Чен (Tobler, Chen, 1986) розглянули пірамідальну структуру, що могла б бути корисною при кодуванні даних для всієї поверхні Землі. Одинична вершина на верхньому рівні піраміди (дерева) представляє повну поверхню Землі. На 15-му рівні розмір комірки порівнянний з тим, що одержують від метеосупутників, на 26-му рівні просторова роздільна здатність порівняна з роздільною здатністю аерофотознімків, а на 30-му рівні — це роздільна здатність сантиметрового масштабу. У ГІС ORRMIS, розробленій в США для цілей регіонального планування, виділено шість рівнів ієрархії. На верхньому рівні, призначеному для збереження агрегованих даних масштабу біома чи континенту, розмір комірок 7,5x7,5 хвилин (площа 15606,6 га), на нижньому — розмір комірок, по яких зберігаються висоти поверхні, 10x10 м (площа 0,01 га). Число максимальних за розміром комірок — 140, мінімальних — більше 200 млн.

Ємність пам'яті, необхідна для збереження пірамідальних структур даних, трохи більша, ніж для збереження вихідного зображення. При послідовному подвоєнні сторони комірок при переході від нижчого рівня до вищого (тобто в квадротомічних растрових структурах даних) це збільшення становить близько 30%. Однак воно, безумовно, виправдовується підвищенням інформативності й універсальності бази даних, а також ефективності ряду алгоритмів обробки просторових даних.

4.2.3. Стиснення растрових даних

Зменшення витрат машинної пам'яті для збереження растрових даних досягається використанням алгоритмів стиснення. Одним із простих і досить ефективних методів стиснення растрових даних є групове кодування (run-length encoding), що використовує просторову автокорельованість даних, особливо чітко виражену на класифікованих картах, тобто на картах контурів або ареалів, у межах яких всі комірки містять однакове значення). Так, у межах даного ґрунтового контуру на ґрунтовій карті, ландшафтного контуру на ландшафтній карті і т.ін. всі комірки растра мають те саме значення, що відповідає, наприклад, номеру даного таксона в легенді відповідної карти.

Групове кодування полягає в кодуванні інформації, яка міститься в кожному рядку вихідної матриці за допомогою пар значень, перше з яких являє собою кількість однакових значень кодованого елемента, що йдуть один за одним, друге — значення елемента. У такому випадку матриця, зображена на рис. 4.1 редукується до вигляду:

2,2 6,1

2,2 6,1

8,1

5,1 1,3 2,1

5,1 2,3 1,1

6,1 1,3 1,1

8,1

8,1

У тому самому випадку, коли немає необхідності подання даних за рядками, вона зводиться до такого вигляду:

2,2 6,1 2,2 19,1 1,3 7,1 2,3 7,1 1,3 17,1.

Як бачимо, інформація, подана на рис. 4.1, кодується за допомогою 31 чи 20 чисел, замість 64 при записі у форматі 1:1. Таким чином, ємність пам'яті, що займається, в цьому випадку, становитиме 48% і 31% вихідної відповідно.

У тому випадку, коли растрове зображення представлене двома значеннями — 1 і 0, перше з яких відповідає, наприклад, коміркам, які розміщені всередині контуру об'єкта, що відслідковується, друге — поза ним, для стиснення інформації використовується рядковий код (row code), який являє собою послідовність груп з трьох чисел, розділених крапкою з комою. Перше число — це номер рядка, а наступні два — номери комірок у рядку, що мають ненульові значення. У разі наявності в рядку груп комірок з ненульовими значеннями через кому вказуються номери початкової і кінцевої комірок для кожної групи.

Інформація, що міститься в растрі, поданому на рис. 4.1, у припущенні, що це — карта природної рослинності і у комірках, що відповідають природним ценозам — степовим і лісовим (значення 2 і 3 на рис. 4.1), міститься значення 1, а в комірках, що відповідають ріллі (значення 1 на рис. 4.1), міститься значення 0. За допомогою рядкового коду вона подається у такому вигляді:

1 1,2; 2 1,2; 4 6,6; 5 6,7; 6 7,7,

тобто записується в пам'яті комп'ютера 15 цифрами (23% вихідної ємності).

Ефективним способом стиснення растрової інформації є використання квадротомічних структур даних (рис. 4.2). Особливістю квадродерев є те, що вони дозволяють зберігати й обробляти тільки значущі фрагменти растра. Перехід на нижчі рівні в квадродереві здійснюється лише для просторово неоднорідних комірок даного рівня. Якщо комірка є однорідною, вона кодується на даному рівні. Саме це в поєднанні з жорстко заданою архітектонікою даної ієрархічної структури і відсутністю необхідності зберігати інформацію з незначущих фрагментів растра забезпечує значну економію машинної пам'яті. Крім цього, жорстко задана архітектоніка Q-дерева дозволяє здійснювати швидкий доступ до даних.