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

В целях упрощения записи объединим два НЧ фильтра c[n] и d[n] в единую матрицу коэффициентов мультифильтра:

c[2k]	c[2k + 1]	(8.8)
M[k]=	.
d[2k]	d[2k + 1]

Тогда z -преобразование НЧ мультифильтра анализа можно представить в виде

H0 (z)= Tt (z)= ∑M[k]z−k .	(8.9)
k
Аналогично выписываются выражения для H1 (z), G0 (z) и	G1 (z), то есть,

соответственно, для ВЧ мультифильтра анализа, НЧ и ВЧ мультифильтров синтеза. Далее, определив входной сигнал как X(z)= [X 0 (z), X1 (z)]t , получим известное равенство для выходного сигнала блока фильтров:

X(z)= 1 {[G 0 (z)H 0 (z)+ G1 (z)H1 (z)]X(z)+
2	(z)H 0	(− z)+ G1 (z)H1 (− z)]X(− z)}.
+ [G 0			(8.10)

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

Из верхней строки (8.10) получим условие полного восстановления

[G0 (z)H0 (z)+ G1 (z)H1 (z)]= 2I2 ,

а из нижней строки – условие отсутствия элайзинга:

[G0 (z)H0 (− z)+ G1 (z)H1 (− z)]= O2 .

Введем понятие модуляционной матрицы

Hm	H0 (z)		H0	(− z)
	(z)=	(z)		.
	H1		H1 (− z)

Тогда появляется возможность объединить эти два условия в одно:

118

(8.11)

(8.12)

(8.13)

[G0 (z)G1 (z)]Hm (z) = 2[I2 ,O2 ].	(8.14)
Может быть показано, что решением является:
G0 (z) = 2U−1 (z),	(8.15)
G1 (z) = −2U−1 (z)H0 (− z)H1−1 (− z),	(8.16)
где
U(z) = H0 (z)- H0 (− z)H1−1 (− z)H1 (z).	(8.17)

Свойство ортогональности блока фильтров означает, что оператор (8.1) должен быть унитарным, или Tt T = I . Отсюда следует, что

				~	~		(8.18)
				Hm (z)Hm (z) = Hm (z)Hm (z) = I2 ,
~	t	(z	−1	) называется парасопряженной матрицей для матрицы H(z).
где H(z) = H
Тогда получаем уравнения:
				~	~	(− z) = I2 ,	(8.19)
				H0 (z)H0	(z)+ H0 (− z)H0
				~	~		(8.20)
				H1 (z)H1 (z)+ H1 (− z)H1 (− z) = I2 ,
				~	~	(− z) = O2 ,	(8.21)
				H0 (z)H1	(z)+ H0 (− z)H1
				~	~	(− z) = O2 .	(8.22)
				H1 (z)H0	(z)+ H1 (− z)H0

Отсюда можно получить условия для обеспечения полного восстановления и отсутствия элайзинга:

~		(z) ,	(8.23)
G0 (z)= H0
~	(z).		(8.24)
G1 (z) = H1
119

Линейность фазы последовательностей c[n] и d[n] не является достаточным условием того, чтобы мультифильтр T(z) имел линейную фазу. Этого

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

Мультифильтр T(z) называется линейно-фазовым, если существуют вещественные числа c0 и c1 , такие что

	Tij (z) = αij z2ci c j Tij (z−1 ),	(8.25)
где αij	- одна из следующих функций: αij = 1 или αij	= −1, или αij = (−1)i+ j ,
или αij	= −(−1)i+ j .

8.1.2.Построение блоков мультифильтров

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

импульсные характеристики. Аналогично K -канальный блок мультифильтров с L фазами эквивалентен K × L блоку фильтров. Таким образом, все

известные результаты для N -канальных блоков фильтров могут быть непосредственно перенесены на случай блоков мультифильтров. Например, ясно, что существует линейно-фазовый ортонормальный двухканальный КИХ блок мультифильтров с двумя фазами, так как существует аналогичный ему четырехканальный блок фильтров.

8.1.3. Итерирование блоков мультифильтров

Пусть каскадно включены n блоков мультифильтров интерполяции. Результирующая передаточная матрица запишется в виде

n−1
T(n ) (z) = ∏ T(z2i ).	(8.26)

i=0

Тогда получим следующий выходной сигнал:

120

(n )	−1	2	X		0	(z4 )
Y (z) = (1	z	)T(n)(z		X			(8.27)
			)		1	(z4 ) .

В данном случае мы имеем две импульсные характеристики, определяемые выражениями

C(n ) (z) = T	(z2 )+ z−1T	(z2 ),	(8.28)
00	10
D(n ) (z) = T	(z2 )+ z−1T	(z2 ).	(8.29)
01	11

Легко показать, что если T - унитарная матрица, то T(n ) - также унитарна. Также понятно, что свойство линейной фазы мультифильтра сохраняется при

проведении итераций. Например, T(z2 )T(z) имеет линейную фазу с коэффициентами 3c0 , c1 − 2c0 .

	8.2. Мультивейвлеты
Так же, как	и в случае вейвлетов, масштабирующая функция
φ(t) = [φ0 (t),...,φr−1 (t)]t	является решением масштабирующего уравнения
	N
	φ(t) = ∑M[k]φ(2t − k ),	(8.30)

k =0

где M[k]- матрица вещественных коэффициентов размером r × r , называе-

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

∞

Ö(ω ) = lim Φ(n ) (ω ) = ∏ M(ω / 2i ). (8.31)

n→∞

i=1

Исследованию сходимости этого предела посвящен ряд работ. Основные результаты следующие. Различают безусловную сходимость (для любой частоты ω ) и условную. Доказана теорема о том, что необходимыми условиями безусловной сходимости являются

Ö(0) ≠ 0;M(0) = I, M(π ) = 0 .

(8.32)

121

Кроме того, маска M(ω ) должна удовлетворять условию Смита-Барнуэлла:

M(ω )Mt (− ω )+ M(ω + π )Mt (− ω + π ) = I .

(8.33)

Условная сходимость подробно рассмотрена в работах П.Массопуста и на страницах нашей книги не обсуждается.

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

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

Пример. Пусть даны две кусочно-линейные функции:

		φ1 (t) = 1,										φ2				1
					0 ≤ t < 1,									(t) =	3(t − 2 ),			0 ≤ t < 1,				(8.34)
			0,		в других случаях,									0,		в других случаях.
Эти	функции			изображены					на рис.8.1. Их целочисленные сдвиги
φ1 ( −l ),φ2 ( −l ),l Z					образуют				ортонормальный базис замкнутого подпро-
странства			V0 L2 ( ), состоящего из кусочно-линейных на целочисленных
интервалах			функций. Далее,						пусть			V j	-	подпространство,							натянутое на
функции 2 j / 2φ1 (2 j				−l ),2 j / 2φ2 (2 j					−l ), l Z и содержащее все функции, которые
кусочно-линейны на интервалах [2− j l,2− j (l + 1)]. Легко показать, что
					φ1	=		1	0		φ1 (2		)	1	0		φ1 (2 −1)			.		(8.35)
					φ2		−	3 1			φ2	(2	)	+ 3	1		φ2 (2 −1)
								2	2					2	2
1														1.5
														1
0.8
														0.5
0.6														0	0.2	0.4		0.6			0.8	1
														-0.5
0.4
														-1
0.2														-1.5
0	0.2		0.4	0.6		0.8		1

Рис.8.1. Кусочно-линейные ортогональные масштабирующие функции

122

Из этого выражения следует, что		φ1 ,φ2 V0 V1 . Аналогично Vj Vj+1 .
Ортогональные	проекции f j (t)	некоторой	функции f L2 ( ) на
подпространства	Vj есть не что иное, как последовательные приближения
линейными функциями, сходящиеся к f (t) при			j → ∞ . Таким образом, мы

получаем вложенную структуру подпространств, известную как кратномасштабный анализ (КМА - глава 2):

∞	( ),	∞
Vj = L2		!Vj = {0}.	(8.36)
j=−∞		j=−∞

Однако в нашем случае КМА порождается двумя функциями φ1 ,φ2 . Подпространства Vj , используемые здесь, не могут быть порождены

сдвигами и растяжениями одной функции.

Рассмотрим еще две кусочно-линейные функции (рис.8.2):

	6t −1,	0 < t,1/ 2,		6t −1,	0 < t,1/ 2,
ψ1	(t) = 6t − 5,	1/ 2 < t < 1,	ψ1	(t) = 6t −5,	1/ 2 < t < 1,	(8.37)
		в других случаях,			в других случаях .
	0,			0,

Пусть Wj	есть подпространство L2 ( ), натянутое на базисы 2 j / 2ψ1 (2 j −l) и
2 j / 2ψ 2 (2 j	−l). Целочисленные сдвиги ψ1 ( −l),ψ 2 ( −n),l, n Z ортогональны

друг другу и целочисленным сдвигам φ1 ,φ2 , что делает подпространство W0 ортогональным V0 . Функции ψ1 ,ψ 2 кусочно-линейны на половине интервала.

Поэтому W0	V1 . В частности,
		ψ1	1	3 φ1		(2 )	1		3		φ1	(2 −1)
		ψ 2	= 2	2	φ2	(2 ) + −	2	2			φ2	(2 −1)		.	(8.38)
			0	1		0		−	1
2							2
1							1
0	0.4	0.6	0.8	1			0	0.2		0.4			0.6	0.8	1
0.2
-1						-1
-2						-2

Рис. 8.2. Кусочно-линейные ортогональные вейвлеты ψ1 ,ψ 2

123

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

φ1 ,φ2 ,ψ1 ,ψ 2 :

φ1 (2 ) =	1	φ1	−	3	φ2	+	1	ψ	1	, φ1 (2 −1) =	1 φ1 +		3 φ2		− 1ψ1 ,			(8.39)
	2			4			4				2		4		4
φ2 (2 ) =	1	φ2	+	3	ψ1	+	1	ψ	2	, φ2 (2 −1) =	1	φ2 +	3	ψ1 − 1		ψ	2 .	(8.40)
	4			4			2				4		4		2
Следовательно,	V1		есть		ортогональная сумма							V0	и		W0 .		Аналогично
Vj Wj = Wj+1 и	L2 ( ) = Wj . Значит, сдвиги и растяжения ψ1 ,ψ 2																	образуют
				j Z						L2 ( ).
ортогональный базис пространства

8.3. Обработка сигналов в базисе мультивейвлетов

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

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

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

124

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

Интересный метод, основанный на аппроксимационных свойствах вейв- лет-преобразования, был предложен Д.Джеронимо. Он применим к семейству так называемых GHM мультивейвлетов, названных так по начальным буквам фамилий их исследователей (Geronimo, Hardin, Massopust). Это – ортогональные симметричные мультивейвлеты. Пример масштабирующих функций

приведен на рис.8.3.
Из рис.8.3 видно, что функция φ0 (t)	равна нулю при целом t . Масштаби-
рующая функция φ1 (t ) ненулевая при t = 1 и равна нулю при других целых
t . Пусть функция f (l ) принадлежит подпространству		V0 , порождаемому
сдвигами масштабируемых функций GHM. Это означает, что			f (l ) может
быть записана как линейная комбинация этих сдвигов:
f (l ) = ∑v1,(0n)φ0 (l − n)+ v2,(0n)φ1 (l − n).			(8.41)
n
Предположим, что отсчеты входной последовательности		f [n] следуют в два
раза чаще, чем отсчеты f (l ):
f [2n]= f (n),	f [2n + 1]= f (n + 1/ 2).		(8.42)

	2.5				2.5
					2
	2
					1.5
	1.5
					1
	1
					0.5
	0.5
					0
	0
					-0.5	0.5	1	1.5	2
	-0.5	0.5 1	1.5	2

Рис.8.3. Масштабирующие функции мультивейвлетов: φ0 (t),φ1 (t )

125

Из рис.8.3 и равенств (8.41) и (8.42) следует, что
			f [2n]= φ1 (1)v2,n ,			(8.43)
	f [2n + 1]= φ1 (3/ 2)v2,n + φ0 (1/ 2)v1,n+1 + φ1 (1/ 2)v2,n+1 .					(8.44)
Отсюда могут быть получены коэффициенты v1,n , v2,n :
v1,n	=	φ1 (1)f [2n −1]− φ1 (1/ 2)f [2n − 2]− φ1 (3/ 2)f [2n]			,	(8.45)
			φ1 (1)φ0 (1/ 2)
v2,n	=	f [2n]
		φ1 (1)	.			(8.46)

Эти выражения могут быть несколько упрощены с учетом симметрии φ1 (t) (φ1 (1/ 2) = φ1 (3/ 2)) . Таким образом, любой входной сигнал длины N может быть разделен на две последовательности v1,n , v2,n длиной N / 2 .

Дополнительным преимуществом аппроксимационного метода является то, что он хорошо согласуется с методом симметричного продолжения сигнала на границах. То есть последовательности v1,n , v2,n также будут обладать

свойством симметрии.

Пусть имеются две входные последовательности (одна четной длины и одна – нечетной):

s01	s11	s21	...	s1N −1		sN2 .	(8.47)
s02	s12	s22	...	sN2	−1

В результате симметричного отражения сигнала получаем

...

s21

s11

s01

s01

s11

...

s1N

−2

s1N −1

s1N −1 ...

...

s22

s12

s02

s02

s12

...

sN2

−1

sN2

sN2

−1 ... .

(8.48)

После одного шага каскадного алгоритма получится четыре симметричные последовательности (две на выходе НЧ фильтра и две на выходе ВЧ фильтра).

126

8.4. Сбалансированные мультивейвлеты

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

Пусть входной сигнал f [n]= 1 . После аппроксимации и фильтрации мы получим две разные последовательности. В случае GHM мультифильтров

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

f (2n)= φ1 (1)v2,n ,	(8.49)
f (2n −1) = φ1 (1/ 2)(v2,n + v2n−1 )+ φ0 (1/ 2)v1,n .	(8.50)

Таким образом, аппроксимационный метод можно рассматривать, как введение некоторой пре/постфильтрации входного сигнала.

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

сбалансированная масштабирущая функция: для случая r = 2 вектор [1,1]t должен быть правым собственным вектором, соответствующим собственному значению 1 маски M(0). Это означает, что φ (0) = [1,1]t .

1
0
0	1
Рис. 8.4. Воспроизведение входного сигнала	f [n]= 1 блоком
GHM мультифильтров

127