18. Особенности сжатия в алгоритме SPIHT

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

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

.

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

Предположим, что вейвлет-коэффициенты  представляются 16 битами, причем, бит №15 будет содержать знак коэффициента, а остальные биты с 0 до 14 – его величину. На первом этапе выполняется их сортировка по убыванию, т.е. они выстраиваются в вектор. Теперь необходимо самую значимую информацию передать в первую очередь. Но это означает, что необходимо сначала взять коэффициенты, лежащие в диапазоне , что гарантирует, что 14-й бит числа установлен в 1, а знак может быть любым. Предположим, что таких коэффициентов два с координатами (2,3) и (3,4). Соответственно на выходе записываем значение 2, за которым следует пара координат (2,3) (3,4), а затем, идут 2 знаковых бита, т.е. записываются биты №15. Имея эту информацию, декодер сможет грубо восстановить эти два коэффициента в виде двух чисел вида s100000000000000, где s – знак числа. Таким образом, самые значимые биты самых значимых коэффициентов передаются в первую очередь.

После этого, из сортированного массива выбираются коэффициенты, удовлетворяющие условию . Предположим, что таких коэффициента 4. Следовательно, число 4 передается на выход, за которым следуют координаты, например, (3,2) (4,4) (1,2) (3,1), знаки этих 4-х коэффициентов и 13-е биты предыдущих двух коэффициентов. Благодаря этой информации, декодер сможет уточнить первые два переданных коэффициента и узнать о следующих 4-х менее важных коэффициентах.

Данная процедура выполняется до тех пор, пока на выход не будут переданы все коэффициенты, описывающие конкретное изображение.

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

Рис. 1. Пример расположения множеств

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