Теория и практика вейвлет-преобразования / entire

Известными методами конструирования сбалансированных мультивейвлетов являются:

1)получение сбалансировнных мультивейвлетов из комплексных фильтров Добеши;

2)балансировка существующих мультивейвлетов.

Недостатком мультивейвлетов, полученных первым способом, является
то, что значение их маски M(0)	не удовлетворяет условию (8.32).

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

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

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

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

128

Глава 9

ПОТЕНЦИАЛЬНЫЕ ХАРАКТЕРИСТИКИ КОДИРОВАНИЯ ИЗОБРАЖЕНИЯ С ПРИМЕНЕНИЕМ ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ

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

дирования D(R ) пропорциональна 2−2R , где R - среднее число бит на пик-

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

( R < 1 бит/пиксел).

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

9.1. Основные формулы и теоремы теории связи, относящиеся к кодированию с преобразованием при высоких скоростях

(>1бит/пиксел)

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

вектором Y размерностью N.		Хотя оно является двумерным, для простоты
обозначений отдельные пикселы обозначаются как Y [n]. Кодер с преобразо-
ванием	декомпозирует эти	изображения по ортонормальному базису
G = {gm	}0≤m :

N −1

Y = ∑A[m]gm .

m=0

Каждый коэффициент A[m] есть случайная величина, определяемая как

129

N −1	[n].
A[m]= Y , g m = ∑Y [n]g m*
n =0

Для построения конечного кода каждый коэффициент A[m] аппроксими-

руется квантованной переменной	ˆ
	A[m]. Далее рассматриваются только ска-

лярные квантователи как наиболее часто встречающиеся при кодировании с преобразованием.

9.1.1.Скалярное квантование с ограниченной энтропией

Скалярный квантователь Q аппроксимирует случайную переменную Х

квантованной переменной	ˆ	= Q(X ), которая может принимать конечное
	X

множество значений. Предполагается, что Х принимает значения в диапазоне
[a,b],	который может соответствовать всей вещественной оси. Интервал
[a,b]	декомпозируется на К интервалов (yk −1 , yk ]1≤k ≤ K переменной длины с
y0 = a	и yk = b . Если x (yk −1 , yk ], то Q(x)= xk	. Для скалярного квантовате-
ля известно, что энтропия
	K
	ˆ	pk
	H (X )= −∑ pk log2

k =1

есть нижняя граница среднего количества бит на символ, используемого для

кодирования значений	ˆ	-	вероятность того, что x (yk −1 , yk ].
	X , где pk

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

энтропией минимизирует		ˆ
		H (X ) для фиксированного среднеквадратичного
искажения	ˆ 2
	D = Ε{(X − X ) }.
Пусть	p(x) есть плотность распределения вероятности отсчетов случай-

ного	источника Х. Считается, что квантователь имеет высокое разрешение,
если	p(x)	примерно постоянна в каждом интервале квантования	(yk −1 , yk	]
размером		k = yk − yk −1. Это будет иметь место в случае, когда размеры		k
достаточно малы относительно скорости изменения p(x). Известно, что рав-

номерные квантователи являются оптимальными среди квантователей с высоким разрешением.

130

Если Q - квантователь с высоким разрешением относительно p(x), то

	ˆ		1
	H (X )≥ H d	(X )−		log	2	(12D).	(9.1)
			2

Это неравенство превращается в равенство, если и только если Q является

2

равномерным квантователем. Тогда D = . 12

Для фиксированного искажения D, при условии соблюдения гипотезы о высоком разрешении, минимальная средняя скорость RX = H (X ) достигается поэтому равномерным квантователем и

RX = H d (X )− log2 .

(9.2)

Зависимость искажения от скорости получается из (9.1):

D(RX	) =	1	22 H d (X )2−2 RX .	(9.3)
	12

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

9.1.2.Зависимость искажения от скорости

Получим зависимость искажения от скорости для коэффициентов A[m]

−

вейвлет-разложения Y = ∑N 1 A[m]gm . Средний бюджет бит, необходимый для

m=0

кодирования	ˆ	= H (A[m]) . Для квантования с высоким
	A[m]= Q(A[m]) есть Rm

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

					N −1
	ления бит должна минимизировать общее число бит R = ∑Rm для заданной
					m=0
	N −1
	суммарной ошибки D = ∑Dm . Пусть		=	R	есть среднее число бит на от-
		R
	m=0			N

131

счет. Применяя множители Лагранжа, можно доказать, что R будет мини-

мальна в случае, если все Dm равны. Тогда

D(

)=

N

22

d 2−2

,

R

H

R

(9.4)

12

где

d есть средняя дифференциальная энтропия:

H

N −1

(A[m]).

d =

1

∑H d

H

N m=0

Искажение (9.4) зависит от базиса вейвлетов G через H d . В общем случае

трудно найти G, минимизирующий	H	d , так	как плотность распределения
вероятности A[m]= Y , gm может зависеть от			gm сложным образом. Если Y

распределен по гауссовскому закону, то коэффициенты A[m] будут гауссовскими случайными переменными в любом базисе. В этом случае плотность распределения вероятности A[m] зависит только от дисперсии σ m2 и

H d (A[m]) = log2 σ m + log2 2πe .

Данное выражение подставляется в (9.4) :

			πe N −1		2	1/ N		−2
D(R )= N									R	.	(9.5)
			6	∏σ m			2
				m=0

N −1

Известно, что ∏σ m2 минимально, если и только если G является базисом

m=0

Карунена-Лоэва для Y, то есть G диагонализирует ковариационную матрицу Y. Таким образом, оптимальным с точки зрения кодирования с преобразованием базисом для гауссовского процесса является базис Карунена-Лоэва. Если Y не является гауссовским (например, в случае изображения), базис Ка- рунена-Лоэва не является априорно оптимальным.

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

индексируемые 1 ≤ k ≤ 3 . При ориентации k и масштабе 2 j вектор вейвлета

132

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

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

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

N

log2 D(R )= 2Hd

+ log2

− 2R ,

12

где 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

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

			N −1
	fˆ = ∑Q(a[m])gm .
			m=0
Ошибка кодирования
			2	N −1
D =	f − fˆ			= ∑	a[m]− Q(a[m])	2 .	(9.6)
				m=0

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

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

	+∞
руются, и вводится функция p(x)≥ 0 для всех x R , такая что ∫ p(x)dx = 1.
Тогда p(x)	−∞
	есть плотность распределения вероятности случайной перемен-

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

134

	1	N −1		+∞
		∑φ(a[m])= ∑φ(x)h[x]≈ ∫φ(x)p(x)dx = Ε{φ(X )}.			(9.7)
	N m=0		x	−∞

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

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

N −1

2 = Ε{X − Q(X )

2 }.

D

=

1

∑

a[m]− Q(a[m])

N

N m =0

Пусть

есть среднее число

бит на коэффициент для кодирования

R

Q(a[m]). Если Q является квантователем с высоким разрешением с шагом ,

то из (9.3) вытекает формула, аналогичная (9.4):

D(

)

=

1

22 Hd (X )2−2

.

R

R

(9.8)

N

12

Как правило, многие вейвлет-коэффициенты

a[m]= f , gm

близки к ну-

лю, и малое их количество имеет большую амплитуду. Поэтому p(x) имеет

острый пик при x = 0 . Если шаг квантования

велик, то p(x) имеет флюк-

,

туирующие значения в интервале −

, где коэффициенты квантуются в

2 2

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

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

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

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

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

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

135

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

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

	если		a[m]	≤ T
0,
b[m]=	если		a[m]	.	(9.9)
1,				> T

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

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

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

N

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

	рого с вероятностью p =	M			принимают значения 1 и с вероятностью 1 − p
		N
	принимают значение 0:
			R0		≤ − p log2 p − (1 − p)log2 (1 − p).	(9.10)
			N
	Для x (0,1] справедливо неравенство −x log2 x ≤ (1 − x)log2 e ,					так что

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

r0	=	R0	≤ log2	N	+ log	2 e .	(9.11)
		M
				M
Для вейвлет-коэффициентов, когда отношение							M	мало, на выходе коде-
							N

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

M

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

казывают, что r0	=	R0	меняется медленно относительно	M	.
		M
				N

136

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

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

		pT (x) =	N	p(x)1		>T }	.	(9.12)
					x
			M	{
Пусть	X T	есть случайная переменная, чья плотность распределения веро-
ятности -	pT	(x). Так как к значащим коэффициентам применима гипотеза

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

r1 =	R1	= H d (X T )− log2 .									(9.13)
	M
В целом кодирование с преобразованием требует R = R0										+ R1 бит.
Для получения оценки ошибки квантования D =						f − fˆ				2	(9.6) суммарное

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

D0 = ∑

a[m]

2

(9.14)

и

a [m ]

≤T

D1 = ∑

a[m]

− Q(a[m])2 .

(9.15)

a[m]

>T

D1

Средняя ошибка квантования на значащий коэффициент

вычисляется

M

с учетом гипотезы о квантовании с высоким разрешением:

D1

=

1

∑

a[m]− Q(a[m])

2 = Ε{X T − Q(X T )

2 }=

2

. (9.16)

12

M

M

a [m ]

>T

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

137