Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

QTCQ

Близким к методу SPIHT является алгоритм QTCQ (quadtree classification and trellis coding, классификация четвертичных деревьев и решетчатое кодирование) из работы [Banister, Fischer 99], который использует меньше списков, чем SPIHT, и явно формирует классы вейвлетных коэффициентов для дальнейшего квантования с помощью методов ACTCQ и TCQ из [Joshi, Crump, Fischer 93].

Этот метод основан на пространственно ориентированных деревьях, построенных для SPIHT. Этот тип деревьев является особым случаем четвертичных деревьев. Алгоритм кодирования является итеративным. На n-той итерации, если обнаружено, что некоторый элемент этого четвертичного дерева является существенным, то четырем верхним элементам дерева присваивается класс п. Одновременно эти элементы становятся корнями четырех новых четвертичных деревьев. Каждое из полученных деревьев проверяется на существенность, перемещаясь вниз по дереву пока не будут обнаружены все существенные элементы. Все вейвлетные коэффициенты, отнесенные к классу п, сохраняются в списке пикселов (LP, list of pixels).

В начале список LP заполнен всеми веивлетными коэффициентами из низкочастотного поддиапазона LFS (lowest frequency subband). Тест на существенность совершается с помощью функции Бт(к), которая определяется по формуле

5 (к) = / *' max(iJ)ek \Cij\ > Г, \ О, иначе,

где Т - это текущий порог существенности, а к - дерево вейвлетных коэффициентов. Алгоритм QTCQ, использующий этот тест, приведен на рис. 4.41.

Алгоритм декодирования QTCQ устроен похоже. Все строки с выводом данных надо заменить на ввод этих данных, а кодирование ACTCQ следует заменить на декодирование ACTCQ.

1. Инициализация:

Заполнить список LP всеми dj из LFS,

Заполнить список LIS всеми родительскими узлами,

Выдать на выход п = [log2 (max|Ci,j| /q)\.

Задать порог Т = q2n, где q - множитель качества.

2. Сортировка:

Для каждого узла к из списка LIS выполнить Выдать на выход St (к) ЕслиSr(k) = 1, то

Для каждого отпрыска к выполнить

Переместить коэффициенты в список LP Добавить в список LIS в виде нового узла Конец Для Удалить к из LIS Конец Если Конец Для

3. Квантование: Для каждого элемента из LP, Квантовать и кодировать его с помощью ACTCQ. (Использовать размер шага TCQ А — \а • q\).

4. Обновление: Удалить все элементы из LP. Присвоить Т = Т/2. Идти на шаг 2.

Рис. 4.41. Кодирование QTCQ (псевдокод).

Реализация метода QTCQ, приведенная в [Banister, Fischer 99], не предусматривает прогрессирующей передачи изображений, однако авторы утверждают, что такое свойство может быть добавлено в программу реализации.