gm = ψ kj , p ,q примерно центрирован в точке (2 j p,2 j q) с квадратной областью

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

Из формулы (9.4) следует, что

где H d есть средняя дифференциальная энтропия вейвлет-коэффициентов при всех масштабах и ориентациях. Из данной формулы следует, что log 2 D(R ) является убывающей функцией с наклоном –2. Однако из практики известно, что для области R < 1 функция log 2 D(R ) убывает значительно

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

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

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

133

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

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

Пусть сигнал f декомпозирован по вейвлет-базису G = {gm }0≤m≤N :

N −1

f = ∑a[m]gm с a[m]= f , gm .

m=0

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

Можно показать, что в случае применения ортонормального базиса, ошибка квантования в области трансформанты будет равна ошибке в области исходного изображения. На этом основано много алгоритмов кодирования. Через h[x] обозначим дискретную гистограмму N коэффициентов a[m], нор-

мализованную так, что ∑x h[x]= 1 . Значения этой гистограммы интерполи-

ной Х. Предполагается, что N – достаточно большое и, следовательно, гистограмма достаточно регулярна, так что для всех функций φ(x) справедливо выражение:

134

Данная гипотеза выполняется для гистограмм большинства «естественных» изображений. Это эквивалентно тому, что коэффициенты a[m] есть

случайная последовательность Х. Заменив φ(x) = x − Q(x)2 , из (9.7) получается

нуль. Следовательно, в этом интервале не выполняется гипотеза о квантовании с высоким разрешением. Это объясняет то, что функция log2 D(R ) имеет

спад порядка − 2R только для R ≥ 1 .

На практике для квантования вейвлет-коэффициентов зачастую применяется «почти» равномерный квантователь. Все интервалы квантования, кроме нулевого, имеют равные размеры , а интервал возле нуля [− T ,T ] - больше,

с отношением θ = T , которое может быть вычислено (обычно θ = 1 ). Для

x > T флюктуации p(x) в каждом интервале квантования относительно ма-

лы, и можно считать, что гипотеза о высоком разрешении квантователя выполняется. Эта гипотеза есть всего лишь аппроксимация, но она достаточно точно описывает свойства квантователя для проведения точных вычислений вплоть до очень низких скоростей кодирования. Для x [−T ,T ] гипотеза о квантовании с высоким разрешением не выполняется.

135

Коэффициенты не квантуются в нуль, если они превышают некоторый порог a[m] > T . Такие коэффициенты обычно называют значимыми. Коди-

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

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

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

p = M индексов m таких, что b[m]= 1. Верхнюю границу для R0 можно по-

N

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

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

ра длин серий средняя битовая скорость r0 = R0 значительно меньше верх-

M

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

136

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

Пусть R1 - число бит, необходимое для кодирования этих коэффициентов. Для M >> 1 М значащих коэффициентов a[m] имеют нормализованную гистограмму, то есть

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

искажение делится на две части: искажение, возникающее в силу квантования незначащих коэффициентов в нуль ( D0 ), и искажение, возникающее в силу квантования значащих коэффициентов ( D1 ): D = D0 + D1 , где

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

137

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

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

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

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

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

подходит для моделирования интересующего нас класса сигналов. Вместо этого вводится предположение о том, что эта экспонента медленно изменяется. Тогда можно определить

d log 2 z

138

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

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

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

139

Так как γ M ≈ γ , из (9.28) следует, что D0 (z) ~ z 2γ −1 и D(R )~ R 1−2γ .

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

где D(R )~ 2−2 R .

Искажение D в (9.29) существенно зависит от ошибки аппроксимации D0

мального кодирования с преобразованием базис G должен точно аппроксимировать каждый из сигналов f малым числом базисных векторов. Если рассматривать f как реализацию случайного вектора Y, желательно было бы най-

известно, что оптимальным для аппроксимации сигнала Y с использованием M векторов является базис Карунена-Лоэва, но в данном случае это свойство оптимальности теряется, так как число векторов меняется в зависимости от реализации. В некоторых случаях известно, как найти базис, который мини-

пример, базис вейвлетов является оптимальным в этом минимаксном смысле

140