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 дана упрощенная версия этого алгоритма.

Рис. 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 в качестве записи, становится известно (и кодеру и декодеру), что .

Рис. 4.39. Упрошенный алгоритм кодирования SPIHT.

В результате, лучшим приближенным значением  этого коэффициента может служить середина между числами  и . Тогда декодер устанавливает  (знак числа  вводится декодером сразу после вставки). Во время этапа поправки, когда декодер вводит истинное значение -го бита коэффициента , он исправляет значение , добавляя к нему , если вводимый бит равен 1, или вычитая , если этот бит равен 0. Таким образом, декодер способен улучшать показываемое зрителю изображение (уменьшать его расхождение с оригиналом) после прохождения каждого из этапов: сортировки и поправки.

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

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