Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Кодирование в алгоритме 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.

На рис 4.38 показаны детали алгоритма. На рис. 4.39 дана упрощенная версия этого алгоритма.

1. Инициализация: Присвоить переменной п значение [log2 maxi,j(cij)J и пере-

дать п. Сделать список LSP пустым. Поместить в список LIP координаты всех корней (i,j) € И.. Поместить в список LIS координаты корней (h j) € "Н, у которых имеются прямые потомки.

2. Сортировка:

2.1. для каждой записи (i,j) из списка LIP выполнить:

2.1.1. выдать на выход Sn(i,j);

2.1.2. если Sn(i,j) = 1, то переместить (i,j) в список LSP и выдать на выход знак c»,j;

2.2. для каждой записи (г, j) из списка LIS выполнить:

2.2.1. если запись типа А, то

• выдать на выход Sn(D(i, j));

• если Sn(D(i,j)) = 1, то

* для каждого (А:, /) € 0(г, j) выполнить

• выдать на выход Sn(fc, /);

• если Sn(k,l) = 1, то добавить (А:,/) в список LSP, выдать на выход знак Ckj;

• если Sn(k,l) = 0, то добавить (к,1) в список LIP;

* если C(i,j) ф 0, переместить (i,j) в конец LIS в виде записи типа В и перейти к шагу 2.2.2.; иначе удалить (г, j) из списка LIS;

2.2.2. если запись имеет тип В, то

• выдать на выход Sn(C(i, j));

если Sn(C(i,j)) = 1, то

* добавить каждую (к, I) 0(i, j) в LIS в виде записи типа А;

* удалить (г, j) из списка LIS;

3. Поправка: для каждой записи (г, j) из LSP, за исключением включенных в

список при последней сортировки (с тем же самым п), выдать на выход п-ый самый старший бит числа |ct,j|;

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. Кодер знает точные значения вейвлетных коэффициентов C{j и использует их для определения битов Sn(уравнение (4.16)), которые будут посылаться в канал связи (или записываться в сжатый файл). Эти биты будут подаваться на вход декодера, который будет их использовать для вычисления значений C{j. Алгоритм, выполняемый декодером, в точности совпадает с алгоритмом рис. 4.38, но слово «выход» следует заменить на «вход».

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

|>g2lcm(*)lJ > |>g2lcm(*+l)U

для всех значений к. Декодер восстанавливает этот порядок, так как все три списка (LIS, LIP и LSP) обновляются в той же последовательности, в которой это делает кодер (напомним, что декодер работает синхронно с кодером). Когда декодер вводит данные, эти три списка идентичны спискам кодер в тот момент, когда он выводит эти данные.

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

2n < \aj\ <2n+1.

1. Установить порог. Поместить в LIP коэффициенты всех корневых узлов. По-

местить в LIS все деревья (присвоив им тип D). Сделать список LSP пустым.

2. Сортировка: Проверить все коэффициенты из LSP на существенность:

2.1. Если он существенный, то выдать на выход 1, затем выдать на выход бит знака и переместить этот коэффициент в LSP.

2.2. Если он несущественный, то выдать на выход 0.

3. Проверить на существенность все деревья из LIS в соответствии с типом

дерева:

3.1. Для деревьев типа D :

3.1.1. Если оно существенное, то выдать на выход 1 и закодировать его первых потомков:

3.1.1.1. Если первый потомок существенный, то выдать на выход 1, затем выдать на выход бит знака и добавить его в список LSP.

3.1.1.2. Если первый потомок несущественный, то выдать на выход 0 и добавить его в LIP.

3.1.1.3. Если этот потомок имеет прямых потомков, переместить дерево в конец списка LIP, присвоив ему тип L; в противном случае удалить его из LIS.

3.1.2. Если оно несущественное, то выдать на выход 0.

3.2. Для деревьев типа L :

3.2.1. Если оно существенное, то выдать на выход 1, добавить всех первых потомков в конец списка LIS в виде записи с типом D и удалить родительское дерево из LIS.

3.2.2. Если оно несущественное, то выдать на выход 0.

4. Цикл: уменьшить порог на единицу и перейти к шагу 2, если необходимо.

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

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

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

18 6 8 -7 3 -5 13 1 2 1-63 2-2 4-2

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