4.9.5. QTCQ

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

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

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

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

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

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

Что такое вейвлеты? Вейвлеты расширяют анализ Фурье.

Как вычисляются вейвлеты? Быстрые преобразования делают это.

- Ив Нивергельт, «Вейвлеты делают это проще».