9.2. Сжатие изображения при низких скоростях кодирования

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

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

9.2.1. Функция искажение-скорость

Пусть сигнал fдекомпозирован по вейвлет-базису:

с .

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

.

Ошибка кодирования

(9.6)

Можно показать, что в случае применения ортонормального базиса, ошибка квантования в области трансформанты будет равна ошибке в области исходного изображения. На этом основано много алгоритмов кодирования. Через обозначим дискретную гистограммуNкоэффициентов, нормализованную так, что. Значения этой гистограммы интерполируются, и вводится функциядля всех, такая что. Тогдаесть плотность распределения вероятности случайной переменнойХ. Предполагается, чтоN– достаточно большое и, следовательно, гистограмма достаточно регулярна, так что для всех функцийсправедливо выражение:

. (9.7)

Данная гипотеза выполняется для гистограмм большинства «естественных» изображений. Это эквивалентно тому, что коэффициенты есть случайная последовательностьХ. Заменив, из (9.7) получается

Пусть есть среднее число бит на коэффициент для кодирования . ЕслиQявляется квантователем с высоким разрешением с шагом, то из (9.3) вытекает формула, аналогичная (9.4):

(9.8)

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

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

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

. (9.9)

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

Пусть - число бит, требуемое для представления карты значений. ПустьМ– число значащих коэффициентов. Можно записать пропорциюиндексовmтаких, что. Верхнюю границу дляможно получить в предположении, что в позициях «1» и «0» в карте значений нет избыточности. Среднее количество бит для кодирования позиции одного коэффициента тогда будет равным энтропии бинарного источника, символы которого с вероятностьюпринимают значения 1 и с вероятностьюпринимают значение 0:

. (9.10)

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

. (9.11)

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

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

. (9.12)

Пусть есть случайная переменная, чья плотность распределения вероятности -. Так как к значащим коэффициентам применима гипотеза квантования с высоким разрешением, среднее число бит для кодирования амплитуды каждого значащего коэффициента, обозначаемое, вычисляется из (9.2):

. (9.13)

В целом кодирование с преобразованием требует бит.

Для получения оценки ошибки квантования (9.6) суммарное искажение делится на две части: искажение, возникающее в силу квантования незначащих коэффициентов в нуль (D₀ ),и искажение, возникающее в силу квантования значащих коэффициентов ( D₁ ): , где

(9.14)

и

. (9.15)

Средняя ошибка квантования на значащий коэффициент вычисляется с учетом гипотезы о квантовании с высоким разрешением:

. (9.16)

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

. (9.17)

Величинаназывается нелинейной ошибкой аппроксимации, так какМвекторов выбираются в зависимости отf. Оценка скорости убыванияпри увеличенииМизучается в теории аппроксимации функций.

Если провести сортировку по амплитуде, тоk-й коэффициент может быть записан в виде

. (9.18)

Ошибка аппроксимации есть суммаквадратов коэффициентов меньшей амплитуды:

. (9.19)

Ошибка убывает быстро при увеличении, еслиубывает быстро при увеличенииz. Таким образом, можно рассматривать функциюпри, которая интерполирует значения.

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

. (9.20)

Зависимость скорости от искажения при кодировании с низкими скоростями была получена С.Маллатом и Ф.Фальзоном. Для этого он предположил, что вторая производная не превосходит некоторого :

.

. (9.21)