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

Таке представлення називається квадродеревом, оскільки 4 комірки замінюються на 1.

Tobler, Chen обговорюють модифіковану квадросистему для кодування поверхні Землі. Єдиний вузол на вершині представляє всю планету. На 15-му рівні резолюція комірок порівняна з метеорологічними супутниками. На 26-му рівні просторова резолюція порівняна з більшістю аерофотознімків. 30-й рівень - 1-см резолюція, яка підходить для геодезичних контрольних точок для широкого вжитку.

Розглянемо растр з 32 пікселів в стороні. Цей растр вимагає 1024 комірки зберігання. Якщо ми включимо вищі рівні, тоді всього 1365 комірок. Тобто, кількість комірок збільшилась на 33%.

Але цей недолік у деяких застосуваннях не відіграє важливої ролі. Наприклад, коли не потрібна повна резолюція.

Q-дерево -яскравий приклад звичайної проблеми застосувань СУБД: протиріччя вартість зберігання даних - вартість обробки.

Ієрархічна природа q-дерева дозволяє скоротити деякі пошуки. Наприклад, пошук високих точок (але не найвищих). Зауважимо, що відразу відсікається 75% даних на кожному кроці. При пошуку найвищої точки треба продивлятись увесь шар.

Навіть зберігаючи по одному значенню даних в кожному вузлі, за допомогою q-дерева можна ефективно здійснювати дуже специфічні пошуки. Звичайно, такі можливості підсилюються, оскільки ми можемо зберігати у кожній комірці 3 величини: середнє по області, мінімум та максимум. Пошук тоді здійснюється для всього регіону дуже швидко. Але є додаткові витрати на зберігання.

Модифікація q-дерева - представлення максимального блоку (maximum block representation).

Проблеми q-дерева у тому, що вони не є інваріантними (незмінними) відносно зсуву, повороту та масштабу.

Приклад.

Оригінальний растр і q-дерево

Перенесені растр і q-дерево

Що відбувається при переносі об’єкта на один проліт на схід? Він міг би представляти інший

об’єкт того ж типу та розміру, але в іншому місці. Існують деякі спроби вирішення цієї проблеми. Scott и Iyengar запропонували систему, яка базується на наступному:

1) знаходження однорідних кв. регіонів у растрі;

2) кодування розміру блоку і координат верхнього лівого кута блоку.