Методы сжатия статических изображений, алгоритм SPIHT (стр. 2 из 2)

Рисунок 3 - пример расположения множеств T_k

Затем, просматривают каждое множество

и проверяют, имеются ли в них значимые коэффициенты , т.е. коэффициенты, удовлетворяющие условию . Если найден в множестве хотя бы один такой коэффициент, то такое множество также считается существенным. Предположим, что в нашем примере значимым множеством является только . Тогда оно разбивается на подмножества , для которых выполняется такая же проверка коэффициентов . И так далее пока не дойдем до множеств, состоящих из одного коэффициента. В результате декодеру передается битовая информация, указывающая, является ли конкретное множество значимым или нет. Благодаря иерархической структуре множеств , общий объем информации о расположении значимых коэффициентов становится меньше, чем простая передача их координат.

Основные шаги кодера SPIHT

Шаг 1: Для заданного сжимаемого изображения вычислить его вейвлетное преобразование, используя подходящие вейвлетные фильтры, разложить его на коэффициенты преобразования qj и представить их в виде целых чисел фиксированной разрядности. Предположим, что коэффициенты представлены в виде целых чисел со знаком, разрядность которых равна 16, причем самый левый бит является знаковым, а в остальных двоичных 15 разрядах записан модуль этого числа. (Отметим, что такое представление отличается от комплементарного представления чисел со знаком, которое традиционно применяется в компьютерах.) Значения этих чисел меняются в диапазоне от - (2¹⁵ - 1) до (2¹⁵ - 1). Присвоим переменной nзначение n= [log2 (2¹⁵ - 1) J = 14.

Шаг 2: Сортировка. Передать число I коэффициентов которые удовлетворяют неравенству 2n< &bsol;c_{, ij}&bsol; < 2n+1. Затем передать I пар координат и I знаков этих коэффициентов.

Шаг 3: Поправка. Передать (n - 1) - ые самые старшие биты всех коэффициентов, удовлетворяющих неравенству &bsol;c{j&bsol; > 2n. Эти коэффициенты были выбраны на шаге сортировки предыдущей итерации цикла (не этой итерации!).

Шаг 4: Итерация. Уменьшить nна 1. Если необходимо сделать еще одну итерацию, пойти на Шаг 2. Обычно последняя итерация совершается при n= 0, но кодер может остановиться раньше. В этом случае наименее важная часть информации (некоторые менее значимые биты всех вейвлетных коэффициентов) не будет передаваться. В этом заключается естественное отбрасывание части информации в методе SPIHT. Это эквивалентно скалярному квантованию, но результат получается лучше, поскольку коэффициенты передаются в упорядоченной последовательности. В альтернативе кодер передает весь образ (то есть, все биты всех вейвлетных коэффициентов), а декодер может остановить процесс декодирования в любой момент, когда восстанавливаемое изображение достигло требуемого качества. Это качество или предопределяется пользователем, или устанавливается декодером автоматически по затраченному времени.

Рассмотрим подробно, что собой представляет кодирование в алгоритме 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.

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