Пример кодирования в алгоритме SPIHT

Предполагается, что изображение размера 4x4 уже преобразовано и полученные 16 коэффициентов сохранены в памяти компьютера в виде целых чисел со знаком длины б бит (знаковый бит, за которым следует 5 битов модуля числа). Алгоритм кодирования инициализирует список LIP одноэлементным множеством, список LIS множеством, а список LSP делает пустым.

Производительность алгоритма SPIHT можно повысить с помощью энтропийного кодирования выхода, но из опытов известно, что это вносит весьма незначительное улучшение, которое не покрывают временные расходы на его выполнение кодером и декодером. Оказывается, что распределение знаков и индивидуальных битов вейвлетных коэффициентов, производимых на каждой итерации, близко к равномерному, поэтому энтропийное кодирование не дает эффекта сжатия. С другой стороны, биты распределены неравномерно, и это может быть хорошо.

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

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

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

Все строки с выводом данных надо заменить на ввод этих данных, а кодирование ACTCQ следует заменить на декодирование ACTCQ.

Квантование: Для каждого элемента из LP, Квантовать и кодировать его с помощью ACTCQ. Реализация метода QTCQ не предусматривает прогрессирующей передачи изображений, однако авторы утверждают, что такое свойство может быть добавлено в программу реализации. Что такое вейвлеты? Вейвлеты расширяют анализ Фурье. Как вычисляются вейвлеты? Быстрые преобразования делают это. — Ив Нивергельт, «Вейвлеты делают это проще».

-----------------------------