Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


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 можно повысить с помощью энтропийного кодирования выхода, но из опытов известно, что это вносит весьма незначительное улучшение, которое не покрывают временные расходы на его выполнение кодером и декодером. Оказывается, что распределение знаков и индивидуальных битов вейвлетных коэффициентов, производимых на каждой итерации, близко к равномерному, поэтому энтропийное кодирование не дает эффекта сжатия. С другой стороны, биты  и  распределены неравномерно и это может дать выигрыш при таком кодировании.

277.jpg

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

 



<< ПредыдущаяОглавлениеСледующая >>