4.9.2. Пространственно ориентированное дерево

Множества  создаются и разделяются с помощью специальной структуры данных, которая называется пространственно ориентированным деревом. Эта структура определяется с использованием пространственных соотношений между вейвлетными коэффициентами и различными уровнями пирамиды поддиапазонов. Многочисленные наблюдения показывают, что поддиапазоны каждого уровня пирамиды демонстрируют определенную пространственную симметрию (см. рис. 4.7b). Любые пространственные особенности изображения такие, как прямые края, равномерные области, остаются легко различимыми на всех уровнях.

Пространственно ориентированные деревья проиллюстрированы на рис. 4.37 для изображения размером 16х16. На этом рисунке показаны два уровня, уровень 1 (высокочастотный) и уровень 2 (низкочастотный). Каждый уровень разделен на 4 поддиапазона. Поддиапазон LL2 (низкой частоты) разделен на 4 группы из 2х2 коэффициентов в каждой группе. На рис. 4.37а обозначена верхняя левая группа, а на рис. 4.37b выделена нижняя правая группа. В каждой группе (за исключением самой верхней левой) каждый из 4 ее коэффициентов становится корнем пространственно ориентированного дерева. Стрелками показан пример связи между различными уровнями деревьев. Жирные стрелки указывают, как каждая группа из 4х4 коэффициентов уровня 2 становится родителем для четырех таких же групп из уровня 1. В общем случае, коэффициент с координатами  является родителем четырех коэффициентов с координатами , ,  и .

Корни пространственно ориентированных деревьев из нашего примера находятся в поддиапазоне LL2 (в общем случае они находятся в самом верхнем левом поддиапазоне LL, который может иметь любые размеры), причем каждый вейвлетный коэффициент уровня 1 за исключением серого коэффициента (а также исключая листья) служит корнем некоторого пространственно ориентированного поддерева. Листья всех этих деревьев расположены на уровне 1 пирамиды поддиапазонов.

В нашем примере поддиапазон LL2 размера 4x4 разделен на четыре группы по 2х2 коэффициентов, и три коэффициента из этих четырех становятся корнями деревьев. Поэтому общее число деревьев в нашем примере равно 12. В общем случае число деревьев равно 3/4 от размера высшего поддиапазона LL.

Каждый из 12 корней поддиапазона LL2 в нашем примере является родителем четырех потомков, которые расположены на том же уровне. Однако потомки этих потомков уже расположены на уровне 1. Это правило остается верным и в общем случае. Корни деревьев расположены в самом высоком уровне вместе со своими непосредственными потомками, а все следующие потомки любых четырех коэффициентов уровня  расположены в уровне .

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

1. : Множество координат четырех отпрысков узла . Если узел  является листом пространственно ориентированного дерева, то множество  пусто.

2. : Множество координат всех прямых потомков узла .

3. : Множество координат корней всех пространственно ориентированных деревьев (3/4 от числа вейвлетных коэффициентов в самом верхнем поддиапазоне LL).

4. : Разность множеств . Это множество содержит всех потомков узла  за вычетом четырех его отпрысков.

Рис. 4.37. Пространственно ориентированные деревья для SPIHT.

Пространственно ориентированные деревья используются для создания и разбиения множеств . Это делается с помощью следующих правил.

1. Начальными множествами являются      и  при всех . В нашем примере было 12 корней, значит, в начале будет 24 множества: 12 множеств, состоящих из одних корней и еще 12 множеств, состоящих из всех прямых потомков этих корней.

2. Если множество  является существенным, то его разбивают на  плюс еще четыре одноэлементных множества с четырьмя отпрысками . Другими словами, если некоторый прямой потомок узла  является существенным, то его четыре отпрыска становятся четырьмя новыми множествами, а все его остальные прямые потомки образуют другое множество (тест на существенность находится в правиле 3).

3. Если множество  является существенным, то оно разбивается на четыре множества , где  - это отпрыски узла .

Мы объяснили, что такое пространственно ориентированные деревья, и описали правила разделения множеств. Теперь можно приступать к разбору алгоритма кодирования.