Модель стиснення растрових даних.

На практиці існує чотири методи стиснення растрових даних, які застосовуються всередині підсистеми зберігання і редагування даних геоінформаційної системи, але вони не можуть викликатися на етапі вводу інформації в ГІС.

Перший метод стиснення растрових даних називається груповимкодуванням. Його сутність полягає у тому, що для кожної строки растру для однакових значень записуються тільки початкова і кінцева позиція та само значення, яке в ній присутнє. Цей метод діє в межах однієї строки. Приклад:

Вихідна інформація: Результат кодування:

12345678910.......26 1- номер ряду

1111222226...........6 номер кінцевого стовпчика групи

значення атрибуту

1429626 значення атрибуту.

Другий метод стискування растрових даних – ланцюгове кодування. Його сутність полягає у наступному. Якщо розпочати з одного кута растру, визначив його координати та значення чарунки растру, а потім перейти за головним напрямом (униз, уверх, ліворуч, праворуч) поздовж області, записавши число, за допомогою якого подається напрям і ще одно число, яке дорівнює кількості чарунок, на яке ми перемістилися, то для запису області буде потрібно усього кілька чисел. У загальному опису, ми визначаємо координати (Х, У) початку, значення чарунок растру для усієї області, а потім вектори напрямків, що показують напрямок руху далі, де повертати тощо. Звичайно вектори описують кількістю чарунок і напрямків у вигляді чисел 0, 1, 2, 3, що відповідає руху уверх, униз, праворуч та ліворуч (рис.2.6).

 

Рис.2.6 Сутність ланцюгового кодування.

 

Існує ще два підходи до стискування растрової інформації. Кожен з них орієнтований на квадратичні матриці. Перший з них, називається блочним кодуванням (рис. 2.7). Він є модифікацією групового кодування. Замість визначення початкової і кінцевої точок та значення чарунок, ми визначаємо квадратну групу чарунок растру та визначаємо початкову точку, наприклад, центр або кут. Далі, встановлюємо значення чарунки і повідомляємо комп’ютеру ширину квадрата чарунки. Іншими словами, це є двовимірне групове кодування. Таким чином може бути записана кожна квадратна група чарунок, включаючи і окремі чарунки з мінімальною кількістю чисел.

	Рис. 2.7. Сутність блочного кодування.

 

 

Останній метод стискування растрових даних називається методом квадродерева. Як і блочне кодування, квадродерево ґрунтується на квадратних групах чарунок растру, але в даному випадку уся карта послідовно розподіляється на квадрати з однаковим значенням атрибута всередині. Його сутність полягає у наступному. Спочатку квадрат розміром з карту розділяється на чотири квадрати. Якщо один з квадратів не різнорідний (містить чарунки з однаковим значенням атрибуту), то цей квадрат записується і більше участі у розподілі не приймає. Кожний з квадратів, які залишилися, знов розподіляється на чотири квадрати (ПЗ, ПС, ПдЗ, ПдС). Далі знову кожний квадрат перевіряється на однорідність. Всі однорідні квадрати записуються, а кожний з квадратів, що залишилися, у подальшому розподіляються і перевіряються, аж поки уся карта не буде записана, як множина квадратних груп чарунок, кожна з яких має однакове значення атрибуту всередині. Найменшим розміром квадрату є одна чарунка растру. Графічно сутність методу квадродерева показана на рис. 2.8.

 

 

Системи, що базуються на методі квадродерева, називають системами зі змінною дозвільною спроможністю, так як вони можуть оперувати на будь-якому рівні розподілу квадродерева. Їх перевагою є те, що користувачі можуть вирішувати, який рівень дозвільної спроможності їм потрібний. Крім того, завдяки високому ступеню стискування даних у цьому методі, в одній системі можуть зберігатися великі за обсягом бази даних.

Векторні моделі даних.

Векторні структури даних дозволяють подати просторове положення об’єктів явним чином, хоча атрибути об’єктів зберігаються в окремому файлі для наступного доступу до них. Існує кілька способів об’єднання векторних структур даних у векторну модель даних, яка дозволяє нам дослідити взаємозв’язки між покажчиками (характеристиками) всередині одного покриття (шару), або між іншими покриттями. Існує велика кількість різних типів векторних моделей даних, а кожний з типів налічує ще і різні варіанти їх подання. Але ми розглянемо з них три основних типи подання векторних моделей даних: спагеті – модель; топологічна модель; кодування ланцюгів векторів.

Найпростішою векторною структурою є спагеті-модель, яка переводить “одне в одне” графічне зображення карти. Її сутність полягає у тому, що кожний об’єкт карти є як примітив: дуже короткий - для точок; більш довгий - для відрізків прямих; групи відрізків, які з’єднані кінцями – для границь областей. Кожний примітив (об’єкт) – один логічний запис у комп’ютері, що записаний у вигляді строки змінної довжини пар координат (Х, У) (рис. 2.9).

В цій моделі сусідні області повинні мати різні ланцюги спагеті для спільних сторін. Іншими словами, не існує областей, для яких будь-який ланцюг спагеті був би спільним.

	Паперова карта.

Структура даних   Об’єкт Номер Місцеположення Точка Лінія   Область   Пара координат (Х,У). Набір пар координат (Х,У). Набір пар координат (Х,У), перша та остання співпадають.

Цифрова карта у декартових координатах (модель даних).

	Рис. 2.9. Спагеті модель векторних даних.

 

Кожна сторона кожної області має свій унікальний набір ліній і пар координат. Хоча в той же час, спільні сторони областей, які записані окремо у базі даних, повинні мати однакові набори координат (Х,У).

Оскільки спагеті-модель являє собою як би переведену “один до одного” аналогову карту, просторові відношення між об’єктами (топологія), наприклад, як положення суміжних областей, розуміється, але не записується в комп’ютері у явному вигляді. Недоліком такого подання інформації (відсутність топології) є велике додаткове обчислювальне навантаження, що ускладнює виміри та аналіз. Але спагеті – модель дуже ефективна для картографічного відображення, там де аналіз не є головною метою. Крім того, таке подання інформації дуже близьке до умови управління сучасними плоттерами, що спрощує перетворення і підвищує його ефективність.

Другою моделлю подання векторних даних є топологічна модель. Така модель на відміну від попередньої моделі містить топологічну інформацію у явному виді. Це забезпечується включенням в структуру даних інформації про суміжність для усунення необхідності визначення її при виконання багатьох операцій. В основі опису інформації при використанні топологічної моделі покладено використання наборів вузлів та дуг (рис. 2.10).

 

 

 

Вузол – більше, ніж просто точка, звичайно це перетин двох чи більше дуг, і її номер використовується для посилання на будь-яку дугу, якій він належить. Кожна дуга починається та закінчується або в точці перетину з іншою дугою, або у вузлі, який не належить іншим дугам. Дуги утворюються послідовностями відрізків, які поєднані проміжними (формоутворюючими) точками. В такому випадку кожна лінія має два набори чисел: пари координат проміжних точок і номери вузлів. Крім того, кожна дуга має свій ідентифікаційний номер, що використовується для вказування того, які вузли є її початком, а які закінченням.

Області, що обмежуються дугами, також мають свій ідентифікаційний код, що використовується для визначення їх відношень з дугами. Крім того, кожна дуга містить інформацію про номери областей зліва і праворуч від неї, що дозволяє знаходити суміжні області. Така особливість даної моделі дозволяє комп’ютеру знати дійсні відношення між географічними об’єктами.

Іншою моделлю подання векторних даних є кодування ланцюгів векторів. Така векторна модель подання даних усуває неефективність збереження і пошуку, які притаманні базовій топологічній моделі, окремим збереженням кожного типу об’єктів (точки, лінії, області). Ці окремі об’єкти потім зв’язуються в ієрархічну структуру даних, де точки пов’язані через покажчики з лініями, а лінії з областями. Кожний набір відрізків, що називається в даній моделі ланцюгом, починається і закінчується у визначених вузлах (перетин двох ланцюгів). Кожний ланцюг містить явну інформацію про напрямок у формі “початковий – кінцевий вузол”, а також ідентифікатори правих та лівих областей.

Такий спосіб має перевагу окремого зберігання кожного типу об’єктів (точки, лінії, області), ідентифікація яких здійснюється за кодами, що пов’язані з записом їх атрибутів. Так, як списки ланцюгів, що обмежують полігони, зберігаються в явному виді і пов’язані через ідентифікатори з кожним полігоном, то розмір бази даних визначається у більшості випадків числом полігонів, ніж складністю їх геометричних фігур. Це підвищує ефективність зберігання і пошуку.