Тема 3. Методи формалізації просторово-розподіленої інформації

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

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

Групове кодування (run-length encoding)

Групове кодування полягає в кодуванні інформації, яка міститься в кожному рядку вихідної матриці за допомогою пар значень, перше з яких являє собою кількість однакових значень кодованого елемента, що йдуть один за одним, друге — значення елемента. У такому випадку матриця, зображена на рис. 4.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), який являє собою послідовність груп з трьох чисел, розділених крапкою з комою. Перше число — це номер рядка, а наступні два — номери комірок у рядку, що маютьненульові значення. У разі наявності в рядку груп комірок з ненульовими значеннями через кому вказуються номери початкової і кінцевої комірок для кожної групи.

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