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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и

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

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

скалярные произведения с имеют наибольшие амплитуды. Тогда искажение будет

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

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

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

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

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

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

Также предполагается, что

и что симметрична:

Большинство реальных изображений удовлетворяют условиям (9.21)-(9.24). При выполнении этих условий справедлива следующая теорема. Теорема 1. Предположим, что удовлетворяет (9.21)-(9.24). Пусть то

где

и

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

изменяется медленно, как функция от . В диапазоне сжатия изображений его можно считать постоянным: Из (9.26) и (9.27) следует, что также постоянны. Как уже было отмечено, в этом случае . Следовательно, вычисляется в (9.25) путем масштабирования и умножения нелинейной ошибки аппроксимации на постоянные множители:

Так как из (9.28) следует, что

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

Искажение D в (9.29) существенно зависит от ошибки аппроксимации сигнала векторами выбранными в базисе G. Для оптимального кодирования с преобразованием базис G должен точно аппроксимировать каждый из сигналов малым числом базисных векторов. Если рассматривать как реализацию случайного вектора Y, желательно было бы найти базис, минимизирующий по всем реализациям. Из теории известно, что оптимальным для аппроксимации сигнала Y с использованием векторов является базис Карунена-Лоэва, но в данном случае это свойство оптимальности теряется, так как число векторов меняется в зависимости от реализации. В некоторых случаях известно, как найти базис, который минимизирует максимальную ошибку — для целого класса сигналов. Например, базис вейвлетов является оптимальным в этом минимаксном смысле

для кусочно-регулярных сигналов, которые описываются пространствами Бесова.