5.2. Алгоритм двойного дерева
Хотя вейвлет-пакеты являются более гибким средством декомпозиции сигналов, чем вейвлет-преобразование, они не изменяются, а значит, и не адаптируются во времени (пространстве). Ряд важных классов сигналов (речь, изображения) являются нестационарными во времени и требуют более гибкого разложения. Например, для изображения адаптация может быть достигнута путем выполнения пространственной сегментации и применения алгоритма одиночного дерева к каждому сегменту.
Это приводит к пространственно изменяющимся вейвлет-пакетам. Быстрый алгоритм, позволяющий достигнуть подобного разбиения, получил название алгоритма двойного дерева.
Алгоритм двойного дерева основан на совместном поиске наилучшей (бинарной) пространственной сегментации и частотного разбиения для каждого сегмента сигнала. Данный алгоритм базируется на теории пространственно изменяющихся блоков фильтров. Дадим краткое пояснение работы алгоритма на примере одномерной декомпозиции (рис. 5.3), имея в виду, что переход к двумерному случаю элементарен. Предположим, что сигнал содержит четыре субполосы - A,B,C,D. Мы можем построить одиночное дерево для всего сигнала (ABCD), для двух его половинок после выполнения сегментации (AB или CD) или для каждой из четвертей (A,B,C,D). В конце концов, мы получим избыточное представление сигнала - структуру двойного дерева - древовидную сегментацию во времени и частоте.
Для совместного поиска наилучшей сегментации во времени и лучшего базиса вейвлет-пакетов для каждого сегмента выполняется следующее. Для каждого возможного временного сегмента длиной, кратной степени двойки, выполняется разложение посредством вейвлет-пакетов. Найденные значения
(см. скан)
Рис. 5.3. Полное двойное дерево глубиной 2 для одномерного сигнала. Сплошные линии показывают частотное дерево, штриховые - пространственное
стоимостей Лагранжа сегментов записываются в виде бинарного дерева. Далее к получившемуся дереву применяют алгоритм одиночного дерева для нахождения наилучшей сегментации.
Может быть показано, что число дополнительных бит, которое необходимо послать декодеру для дерева максимальной глубины 
определяется по формуле 
Для изображения размером 512 х 512 и дерева глубиной 5 число бит равно 341 или 0.0013 бит/пиксел.
(см. скан)
Рис. 5.4. Полное частотно-временное дерево глубиной 2 для одномерного сигнала. Сплошные линии показывают частотное дерево, штриховые - пространственное
