(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