4.9.2. Пространственно ориентированное деревоМножества Пространственно ориентированные деревья проиллюстрированы на рис. 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. 4. Рис. 4.37. Пространственно ориентированные деревья для SPIHT. Пространственно ориентированные деревья используются для создания и разбиения множеств 1. Начальными множествами являются 2. Если множество 3. Если множество Мы объяснили, что такое пространственно ориентированные деревья, и описали правила разделения множеств. Теперь можно приступать к разбору алгоритма кодирования.
|