4.9. SPIHT

Алгоритм SPIHT представляет собой метод сжатия изображений. На одном из его этапов применяется вейвлетное преобразование, поэтому он рассматривается в этой главе. Кроме того, основная структура данных этого алгоритма, пространственно ориентированное дерево, использует тот факт, что различные поддиапазоны отражают разные геометрические особенности образа (это обстоятельство было отмечено на стр. 220).

Рис. 4.34. Вейвлет Добеши  в 3073 точках.

В § 4.2 было покачано, что преобразования Хаара можно применять к изображению несколько раз подряд. При этом образуются различные области (поддиапазоны), состоящие из средних и деталей данного образа. Преобразование Хаара является очень простым и наглядным, но для лучшего сжатия стоит использовать другие вейвлетные фильтры, которые лучше концентрируют энергию изображения. Представляется логичным, что различные вейвлетные фильтры будут давать разные коэффициенты сжатия для разных типов изображений. Однако исследователям пока не до конца ясно, как построить наилучший фильтр для каждого типа образов. Независимо от конкретно используемого фильтра, образ разлагается на поддиапазоны так, что нижние поддиапазоны соответствуют высоким частотам изображения, а верхние поддиапазоны отвечают низким частотам образа, в которых концентрируется основная часть энергии изображения (см. рис. 4.35). Поэтому можно ожидать, что коэффициенты деталей изображения уменьшаются при перемещении от высокого уровня к более низкому. Кроме того, имеется определенное пространственное подобие между поддиапазонами (рис. 4.7b). Части образа, такие как пики, занимают одну и ту же пространственную позицию во всех поддиапазонах. Эта особенность вейвлетного разложения используется методом SPIHT, который расшифровывается как «Set partitioning in hierarchical trees» (разложение множества по иерархическим деревьям) (см. [Said, Pearlman 96]).

Рис. 4.35. Поддиапазоны и уровни вейвлетного разложения.

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

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

Следующий пример удачно иллюстрирует это определение. Предположим, что три пользователя ожидают некоторое отправленное им сжатое изображение. При этом им требуется различное качество этого изображения. Первому из них требуется качество, обеспечиваемое 10 KB образа, а второму и третьему пользователю необходимо качество, соответственно, в объеме 20 KB и 50 КВ. Большинству методов сжатия изображения с частичной потерей данных потребуется сжимать исходный образ три раза с разным качеством, для того, чтобы сгенерировать три различных файла, требуемых объемов. А метод SPIHT произведет для этих целей всего один файл, и пользователям будут посланы три начальных фрагмента этого файла, длины которых соответственно равны 10 KB, 20 KB и 50 КВ.

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

Основная цель прогрессирующего метода состоит в скорейшей передаче самой важной части информации об изображении. Эта информация дает самое большое сокращение расхождения исходного и реконструированного образов. Для количественного измерения этого расхождения метод SPIHT использует среднеквадратическую ошибку MSE (mean squared error) (см. уравнение (3.2)),

,

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

.                       (4.15)

Уравнение (4.15) показывает, что MSE уменьшается на , когда декодер получает коэффициент преобразования  (для простоты мы предполагаем, что декодер получает точные значения коэффициентов преобразования, то есть не происходит потери точности из-за ограниченной разрядности компьютерной арифметики). Теперь становится ясно, что самые большие (по абсолютной величине) коэффициенты  несут в себе информацию, которая больше всего сокращает расхождение MSE, поэтому прогрессирующее кодирование должно посылать эти коэффициенты в первую очередь. В этом заключается первый важный принцип SPIHT.

Другой принцип основан на наблюдении, что наиболее значимые биты двоичных представлений целых чисел стремятся быть единицами, когда эти числа приближаются к максимальным значениям. (Например, в 16-битном компьютере число +5 имеет представление 0|000...0101, а большое число +65382 запишется в виде 0|111111101100110. Это наводит на мысль, что старшие биты содержат наиболее значимую часть информации, и их также следует посылать (или записывать в сжатый массив данных) в первую очередь.

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

		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
	знак	s	s	s	s	s	s	s	s	s	s	s	s	s	s	s	s
ст.бит	14	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
	13	а	b	1	1	1	1	0	0	0	0	0	0	0	0	0	0
	12	с	d	е	f	g	h	1	1	1	0	0	0	0	0	0	0
	11	i	j	к	l	m	n	o	p	q	1	0	0	0	0	0	0
мл.бит	0	r	s	t	u	v	w	x	y		…		…		…		z
	i,j	2,3	3,4	3,2	4,4	1,2	3,1	3,3	4,2	4,2	4,1		…		…		4,3

Табл. 4.36. Коэффициенты преобразования, отсортированные по модулю.

Покажем теперь, как кодер метода SPIHT использует указанные принципы для прогрессирующей передачи (или записи в файл) вейвлетных коэффициентов, начиная с самой существенной информации. Предполагается, что вейвлетное преобразование уже применено к изображению (SPIHT является методом кодирования, и он может работать с любым вейвлетным преобразованием) и коэффициенты  уже сохранены в памяти компьютера. Коэффициенты отсортированы по абсолютной величине, и они хранятся в массиве , причем элемент  содержит координаты  коэффициента  так, что  при всех . В табл. 4.36 перечислены гипотетические значения 16 коэффициентов. Каждый коэффициент показан в виде 16-ти битного числа, причем самый старший бит (бит 15) содержит знак этого числа, а остальные 15 битов (с 14 по 0, сверху вниз) содержат модуль коэффициента. Первый коэффициент  равен  (где  - это биты). Второй коэффициент  равен , и так далее.

Упорядоченные данные, которые кодер должен передать, образуют последовательность  вида

.                (4,3).

Кроме того, необходимо передать 16 знаков и 16 коэффициентов в порядке самых значимых битов. Прямая передача должна состоять из 16 чисел

,             ,              ,

,       ,               ,

что, конечно, слишком расточительно. Вместо этого кодер организует цикл, в котором на каждой итерации совершается шаг сортировки и шаг поправки. При первой итерации передается число  (число коэффициентов  из нашего примера, которые удовлетворяют неравенству ), за которым следует пара координат (2,3) и (3,4), а потом знаки первых двух коэффициентов. Это делается на первом проходе сортировки. Эта информация позволит декодеру построить приближенную версию 16 коэффициентов следующим образом. Коэффициенты  и  строятся в виде 16-и битовых чисел . Остальные 14 коэффициентов полагаются равными нулю. Таким образом, самые значимые биты самых больших коэффициентов передаются в первую очередь.

На следующем проходе кодер должен выполнить шаг поправки, но он пропускается при первой итерации цикла.

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

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

, , ,

, , ,

а оставшиеся 10 коэффициентов не меняются, они по-прежнему равны 0.

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

Полученная информация позволит декодеру еще лучше уточнить 16 приближенных коэффициентов. Первые 9 из них равны теперь

, , ,

, , ,

, , ,

а другие коэффициенты остаются нулевыми.

Теперь легко понять основные шаги кодера SPIHT. Они приводятся ниже.

Шаг 1: Для заданного сжимаемого изображения вычислить его вейвлетное преобразование, используя подходящие вейвлетные фильтры, разложить его на коэффициенты преобразования  и представить их в виде целых чисел фиксированной разрядности. (Здесь мы используем термины пиксел и коэффициент для обозначения одних и тех же объектов.) Предположим, что коэффициенты представлены в виде целых чисел со знаком, разрядность которых равна 16, причем самый левый бит является знаковым, а в остальных двоичных 15 разрядах записан модуль этого числа. (Отметим, что такое представление отличается от комплементарного представления чисел со знаком, которое традиционно применяется в компьютерах.) Значения этих чисел меняются в диапазоне от  до . Присвоим переменной  значение  . В нашем приме- pe .

Шаг 2: Сортировка. Передать число  коэффициентов , которые удовлетворяют неравенству . Затем передать  пар координат и  знаков этих коэффициентов.

Шаг 3: Поправка. Передать -ые самые старшие биты всех коэффициентов. удовлетворяющих неравенству . Эти коэффициенты были выбраны на шаге сортировки предыдущей итерации цикла (не этой итерации!).

Шаг 4: Итерация. Уменьшить  на 1. Если необходимо сделать еще одну итерацию, пойти на Шаг 2.

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