5.3. Частотно-временное дерево
Алгоритм двойного дерева (см. раздел 5.2) обладает некоторой асимметрией. В самом деле, деревья в частотной области строятся над временными сегментами, но не наоборот. Этот недостаток можно устранить, построив дерево, приведенное на рис. 5.4, где кандидатом на дальнейшее разбиение является субсигнал, как во временной, так и в частотной области. Такое дерево еще называют сбалансированным. Ясно, что дерево, представленное на рис. 5.3, является частным случаем этого частотно-временного дерева. Частотно-временное дерево имеет структуру квадродерева. Мы видим, что каждый родительский узел имеет две пары потомков: временные и частотные сегменты.
Обрезание этого дерева осуществляется путем сравнения значений функции стоимости Лагранжа. Сравнение выполняется для пространственной и частотной пары на каждом узле в направлении от листьев дерева к его вершине. В результате выполнения алгоритма получается оптимальное двоичное дерево разбиения по частоте и по времени полной глубины. В этом его отличие от алгоритма одиночного дерева, где обрезанное дерево имеет, как правило, неполную глубину.
Разница между алгоритмами одиночного, двойного и частотновременного дерева может быть легко уяснена, если взглянуть на разбиение частотно-временной плоскости, производимое ими (рис. 5.5).
Отметим, что на рис.5.5(а) каждое деление по частоте относится ко всему сигналу, так как структура дерева не меняется во времени. Разбиение, показанное на рис.5.5(б), невозможно получить при помощи алгоритма одиночного дерева. Вертикальная линия посередине соответствует сегментации во
Рис. 5.5. Примеры разбиения, достигаемые различными алгоритмами: (а) алгоритм одиночного дерева; (б) алгоритм двойного дерева; (в) алгоритм частотно-временного дерева
временной области. Отметим, что двум половинкам сигнала соответствуют разные одиночные деревья. Разбиения, представленного на рис. 5.5 (в), можно достичь только с использованием алгоритма частотно-временного дерева.
Для кодирования изображений алгоритм частотно-временного дерева несложно перенести на двумерный случай. Тогда получается пространственно-частотное дерево.
Недостатком рассмотренных алгоритмов является принципиальное ограничение двоичной сегментацией во времени. Отсюда вытекает также чувствительность временной сегментации к сдвигам исходного сигнала. Для ликвидации этой чувствительности известен алгоритм, основанный на динамическом программировании и названный деревом гибкой пространственной сегментации. При этом разбиение в частотной области остается бинарным, так как используется двухканальный блок фильтров. Данный алгоритм включает в себя как частные случаи все выше рассмотренные алгоритмы. Основным недостатком его является невозможность простого перенесения алгоритма на двумерный случай для кодирования изображений.
