Рассмотрим подробно, что собой представляет кодирование в алгоритме SPIHT

Прежде всего отметим, что кодер и декодер должны использовать единый тест при проверке множеств на существенность. Алгоритм кодирования использует три списка, которые называются: список существенных пикселов (LSP, list of significant pixels), список несущественных пикселов (LIP, list of insignificant pixels) и список несущественных множеств (LIS, list of insignificant sets).
В эти списки заносятся координаты (i,j) так, что в списках LIP и LSP они представляют индивидуальные коэффициенты, а в списке LIS они представляют или множество T>(i,j), или множество C(i,j).
Список LIP содержит координаты коэффициентов, которые были несущественными на предыдущей стадии сортировки. В текущей стадии они проверяются, и если множество является существенным, то они перемещаются в список LSP. Аналогично множества из LIS тестируются в последовательном порядке, и если обнаруживается, что множество стало существенным, то оно удаляется из LIS и разделяется.

Новые подмножества, состоящие более чем из одного элемента, помещаются обратно в список LIS, где они позже будут подвергнуты тестированию, а одноэлементные подмножества проверяются и добавляются в список LSP или LIP в зависимости от результатов теста. Стадия поправки передает n-ный самый старший бит записей из списка LSP.

Декодер работает по алгоритму. Он всегда действует синхронно с кодером, и следующие замечания проясняют совершаемые действия. Шаг 2.2 алгоритма выполняется для всех записей списка LIS. Однако шаг 2.2.1 добавляет некоторые записи в LIS (типа В), а шаг 2.2.2 добавляет другие записи в LIS (типа А).
Важно понять, что эти действия применяются ко всем записям шага 2.2 в одной итерации. Величина п уменьшается после каждой итерации, но это не обязательно должно продолжаться до нулевого значения. Цикл можно остановить после любой итерации, в результате произойдет сжатие с частичной потерей данных.
Обычно пользователь сам определяет число совершаемых итераций, но он может также задавать допустимый порог отклонения сжатого изображения оригинала (в единицах MSE), а декодер сам определит необходимое число итераций, исходя из уравнений. Кодер знает точные значения вейвлетных коэффициентов Cjj и использует их для определения битов Sn, которые будут посылаться в канал связи (или записываться в сжатый файл).
Эти биты будут подаваться на вход декодера, который будет их использовать для вычисления значений cij. Алгоритм, выполняемый декодером, в точности совпадает с алгоритмом, но слово «выход» следует заменить на «вход».

Отсортированная информация, ранее обозначаемая т(к), восстанавливается, когда координаты существенных коэффициентов добавляются в список LSP на шаге 2.1.2 и 2.2.1. Это означает, что вейвлетные коэффициенты с координатами из списка LSP, упорядочены в соответствии с условием для всех значений. Декодер восстанавливает этот порядок, так как все три списка (LIS, LIP и LSP) обновляются в той же последовательности, в которой это делает кодер (напомним, что декодер работает синхронно с кодером).

Когда декодер вводит данные, эти три списка идентичны спискам кодер в тот момент, когда он выводит эти данные. Кодер начинает работать с готовыми коэффициентами вейвлетного преобразования образа; он никогда не «видел» настоящего изображения. А декодер должен показывать изображение и обновлять его после каждой итерации. При каждой итерации, когда координаты коэффициента помещаются в список LSP в качестве записи, становится известно (и кодеру и декодеру).

Сортировка: Проверить все коэффициенты из LSP на существенность: Если он существенный, то выдать на выход 1, затем выдать на выход бит знака и переместить этот коэффициент в LSP. Если он несущественный, то выдать на выход 0.
Проверить на существенность все деревья из LIS в соответствии с типом дерева: Для деревьев типа D: Если оно существенное, то выдать на выход 1 и закодировать его первых потомков: Если первый потомок существенный, то выдать на выход 1, затем выдать на выход бит знака и добавить его в список LSP. Если первый потомок несущественный, то выдать на выход 0 и добавить его в LIP.

Если этот потомок имеет прямых потомков, переместить дерево в конец списка LIP, присвоив ему тип L; в противном случае удалить его из LIS. Если оно несущественное, то выдать на выход 0. Для деревьев типа L : Если оно существенное, то выдать на выход 1, добавить всех первых потомков в конец списка LIS в виде записи с типом D и удалить родительское дерево из LIS. Если оно несущественное, то выдать на выход 0. Цикл: уменьшить порог на единицу и перейти к шагу 2, если необходимо.

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

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