4.9.3. Кодирование в алгоритме SPIHT
Прежде всего отметим, что кодер и декодер должны использовать единый тест при проверке множеств на существенность. Алгоритм кодирования использует три списка, которые называются: список существенных пикселов (LSP, list of significant pixels), список несущественных пикселов (LIP, list of insignificant pixels) и список несущественных множеств (LIS, list of insignificant sets). В эти списки заносятся координаты
так, что в списках LIP и LSP они представляют индивидуальные коэффициенты, а в списке LIS они представляют или множество
(запись типа
), или множество
(запись типа
).
Список LIP содержит координаты коэффициентов, которые были несущественными на предыдущей стадии сортировки. В текущей стадии они проверяются, и если множество является существенным, то они перемещаются в список LSP. Аналогично множества из LIS тестируются в последовательном порядке, и если обнаруживается, что множество стало существенным, то оно удаляется из LIS и разделяется. Новые подмножества, состоящие более чем из одного элемента, помещаются обратно в список LIS, где они позже будут подвергнуты тестированию, а одноэлементные подмножества проверяются и добавляются в список LSP или LIP в зависимости от результатов теста. Стадия поправки передает
-ный самый старший бит записей из списка LSP.
На рис 4.38 показаны детали алгоритма. На рис. 4.39 дана упрощенная версия этого алгоритма.
1. Инициализация: Присвоить переменной значение и передать . Сделать список LSP пустым. Поместить в список LIP координаты всех корней . Поместить в список LIS координаты корней , у которых имеются прямые потомки.
2. Сортировка:
2.1. для каждой записи из списка LIP выполнить:
2.1.1. выдать на выход ;
2.1.2. если , то переместить в список LSP и выдать на выход знак ;
2.2. для каждой записи из списка LIS выполнить:
2.2.1. если запись типа , то
- выдать на выход ;
- если , то
* для каждого выполнить
- выдать на выход ;
- если , то добавить в список LSP, выдать на выход знак ;
- если , то добавить в список LIP;
* если , переместить в конец LIS в виде записи типа и перейти к шагу 2.2.2.; иначе удалить из списка LIS;
2.2.2 если запись имеет тип , то
- выдать на выход ;
- если , то
* добавить каждую в LIS в виде записи типа ;
* удалить из списка LIS;
3. Поправка: для каждой записи из LSP, за исключением включенных в список при последней сортировке (с тем же самым ), выдать на выход -ый самый старший бит числа ;
4. Цикл: уменьшить на единицу и перейти к шагу 2, если необходимо.
|
Рис. 4.38. Алгоритм кодирования SPIHT.
Декодер работает по алгоритму рис. 4.38. Он всегда действует синхронно с кодером, и следующие замечания проясняют совершаемые действия.
1. Шаг 2.2 алгоритма выполняется для всех записей списка LIS. Однако шаг 2.2.1 добавляет некоторые записи в LIS (типа
), а шаг 2.2.2 добавляет другие записи в LIS (типа
). Важно понять, что эти действия применяются ко всем записям шага 2.2 в одной итерации.
2. Величина
уменьшается после каждой итерации, но это не обязательно должно продолжаться до нулевого значения. Цикл можно остановить после любой итерации, в результате произойдет сжатие с частичной потерей данных. Обычно пользователь сам определяет число совершаемых итераций, но он может также задавать допустимый порог отклонения сжатого изображения оригинала (в единицах MSE), а декодер сам определит необходимое число итераций, исходя из уравнений (4.15).
3. Кодер знает точные значения вейвлетных коэффициентов
и использует их для определения битов
(уравнение (4.16)), которые будут посылаться в канал связи (или записываться в сжатый файл). Эти биты будут подаваться на вход декодера, который будет их использовать для вычисления значений
. Алгоритм, выполняемый декодером, в точности совпадает с алгоритмом рис. 4.38, но слово «выход» следует заменить на «вход».
4. Отсортированная информация, ранее обозначаемая
, восстанавливается, когда координаты существенных коэффициентов добавляются в список LSP на шаге 2.1.2 и 2.2.1. Это означает, что вейвлетные коэффициенты с координатами из списка LSP, упорядочены в соответствии с условием

для всех значений
. Декодер восстанавливает этот порядок, так как все три списка (LIS, LIP и LSP) обновляются в той же последовательности, в которой это делает кодер (напомним, что декодер работает синхронно с кодером). Когда декодер вводит данные, эти три списка идентичны спискам кодер в тот момент, когда он выводит эти данные.
5. Кодер начинает работать с готовыми коэффициентами
вейвлетного преобразования образа; он никогда не «видел» настоящего изображения. А декодер должен показывать изображение и обновлять его после каждой итерации. При каждой итерации, когда координаты
коэффициента
помещаются в список LSP в качестве записи, становится известно (и кодеру и декодеру), что
.
1. Установить порог. Поместить в LIP коэффициенты всех корневых узлов. Поместить в LIS все деревья (присвоив им тип ). Сделать список LSP пустым.
2. Сортировка: Проверить все коэффициенты из LSP на существенность:
2.1. Если он существенный, то выдать на выход 1, затем выдать на выход бит знака и переместить этот коэффициент в LSP.
2.2. Если он несущественный, то выдать на выход 0.
3. Проверить на существенность все деревья из LIS в соответствии с типом дерева:
3.1. Для деревьев типа :
3.1.1. Если оно существенное, то выдать на выход 1 и закодировать его первых потомков:
3.1.1.1. Если первый потомок существенный, то выдать на выход 1, затем выдать на выход бит знака и добавить его в список LSP.
3.1.1.2. Если первый потомок несущественный, то выдать на выход 0 и добавить его в LIP.
3.1.1.3. Если этот потомок имеет прямых потомков, переместить дерево в конец списка LIP, присвоив ему тип ; в противном случае удалить его из LIS.
3.1.2. Если оно несущественное, то выдать на выход 0.
3.2. Для деревьев типа :
3.2.1. Если оно существенное, то выдать на выход 1, добавить всех первых потомков в конец списка LIS в виде записи с типом и удалить родительское дерево из LIS.
3.2.2. Если оно несущественное, то выдать на выход 0.
4. Цикл: уменьшить порог на единицу и перейти к шагу 2, если необходимо.
|
Рис. 4.39. Упрошенный алгоритм кодирования SPIHT.
В результате, лучшим приближенным значением
этого коэффициента может служить середина между числами
и
. Тогда декодер устанавливает
(знак числа
вводится декодером сразу после вставки). Во время этапа поправки, когда декодер вводит истинное значение
-го бита коэффициента
, он исправляет значение
, добавляя к нему
, если вводимый бит равен 1, или вычитая
, если этот бит равен 0. Таким образом, декодер способен улучшать показываемое зрителю изображение (уменьшать его расхождение с оригиналом) после прохождения каждого из этапов: сортировки и поправки.
Производительность алгоритма SPIHT можно повысить с помощью энтропийного кодирования выхода, но из опытов известно, что это вносит весьма незначительное улучшение, которое не покрывают временные расходы на его выполнение кодером и декодером. Оказывается, что распределение знаков и индивидуальных битов вейвлетных коэффициентов, производимых на каждой итерации, близко к равномерному, поэтому энтропийное кодирование не дает эффекта сжатия. С другой стороны, биты
и
распределены неравномерно и это может дать выигрыш при таком кодировании.

Рис. 4.40. Шестнадцать коэффициентов и пространственно ориентированное дерево.