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.

1. Инициализация:
      Заполнить список LP всеми из LFS,
      Заполнить список LIS всеми родительскими узлами,
      Выдать на выход .
      Задать порог , где - множитель качества.
2. Сортировка:
      Для каждого узла из списка LIS выполнить
        Выдать на выход
        Если , то
          Для каждого отпрыска выполнить
            Переместить коэффициенты в список LP
            Добавить в список LIS в виде нового узла
          Конец Для
          Удалить из LIS
        Конец Если
      Конец Для
3. Квантование: Для каждого элемента из LP,
      Квантовать и кодировать его с помощью ACTCQ.
      (Использовать размер шага TCQ ).
4. Обновление: Удалить все элементы из LP. Присвоить .
      Идти на шаг 2.

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

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

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

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

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