113
7.2.5. Пакеты вейвлетов (алгоритм одиночного дерева)
Вейвлет-преобразование сигнала выполняется путем его пропускания через каскадно соединенные двухканальные схемы А-С. При этом каскадирование производится по низкочастотной области. Причина этого в неявном предположении, что эта область содержит больше информации об исходном сигнале. В результате получается «однобокое» дерево (рис. 7.3(а)). Данное предположение оправданно для многих реальных сигналов. В самом деле, оно означает, что наш сигнал является низкочастотным на большом интервале времени, а высокочастотные составляющие появляются на коротком интервале. Однако для некоторых сигналов это предположение не выполняется.
Метод пакетов вейвлетов основан на определении того, по какой области на данном уровне выгоднее производить каскадирование. Для этого вначале производится каскадирование по обеим субполосам. В результате получается так называемое «полное», «сбалансированное» дерево (рис.7.3(б)), напоминающее дерево, присущее кратковременному преобразованию Фурье. Далее, на основе введенной функции стоимости определяется наилучший путь по этому дереву (рис. 7.3(в)).
(а) (б)
Рис. 7.3. Разбиение частотно-временной плоскости при помощи пакетов вейвлетов: (а) вейвлет-декомпозиция; (б) полная, аналогичная STFT декомпозиция; (в) пример декомпозиции при помощи пакетов вейвлетов
Если исходный блок вейвлет - фильтров был ортогональным, то и схема, соответствующая любой конфигурации дерева, будет ортогональной, так как она есть не что иное, как каскадное соединение ортогональных блоков.
Таким образом, получается базис, адаптированный к сигналу.
7.2.6. Целочисленное вейвлет-преобразование
Рассмотрим методы получения целочисленных вейвлет-коэффициентов изображения. Эти методы могут быть применены для сжатия изображения, как без потерь, так и с потерями. В основе рассматриваемых методов лежит
114
некоторая модификация вейвлет-преобразования, позволяющая производить все вычисления в целочисленном виде. Полученное преобразование не является, строго говоря, вейвлет-преобразованием, но обладает всеми его свойствами [2]. Теоретически при вейвлет-преобразовании потери информации не происходит. Однако при реализации возникают неизбежные ошибки округления вейвлет-коэффициентов. Вместе с тем, в некоторых приложениях обработки изображений полная обратимость преобразования является важной.
Целочисленное вейвлет-преобразование позволяет достичь полного контроля над точностью вычислений. Поэтому оно получило название обратимого вейвлет-преобразования. Кроме того, целочисленность вычислений ускоряет выполнение преобразования.
Рассмотрим два примера, поясняющие обсуждаемые далее методы. Для простоты все выкладки производятся для одного уровня разложения и для
одномерного сигнала четной длины. Пусть {cn0 }nN=−01 - исходный сигнал, где верхний индекс показывает уровень разложения (0), нижний – конкретную
точку сигнала. Пусть {c1 |
}N1 −1 |
и {d 1 |
}N1 −1 |
- составляющие его разложения на первом |
|
n |
|
n=0 |
n |
n=0 |
|
уровне (низкочастотная |
и |
высокочастотная части, соответственно). Здесь |
|||
N1 = N / 2 .
Целочисленное вычисление вейвлет–преобразование (2,2). Это пре-
образование эквивалентно вейвлет-преобразованию Хаара, использующему следующие фильтры декомпозиции:
~ |
~ |
~ |
~ |
=1/ 2 |
h0 |
= h1 |
= g0 |
= −g1 |
Вычисление ведется следующим образом:
dk1 |
= c20k − c20k +1 , |
k = 0,..., N1 −1, |
||||||||
|
|
|
1 |
|
|
|
|
|
|
|
1 |
|
dk |
|
|
0 |
|
|
|
||
ck |
= int |
2 |
|
+ c2k +1 , k = 0,..., N1 − 2 , |
||||||
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
1 |
−1 |
|
|
|
|
c1 = int |
d N1 |
+ c0 |
|
|
||||||
|
|
|
||||||||
|
N1 −1 |
|
|
|
2 |
|
N |
−1 |
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|||
(7.20)
(7.21)
(7.22)
(7.23)
В выражениях (7.22), (7.23) int означает операцию выделения целой части. Таким образом, все элементы {c1n }nN=10−1 и {dn1 }nN=10−1 будут целыми числами. Из (7.21)- (7.23) легко получить алгоритм реконструкции:
c2k +1 |
= ck |
|
|
1 |
|
k = 0,..., N1 −1 |
, |
(7.24) |
− int |
|
|
, |
|||||
0 |
1 |
dk |
|
|
|
|
||
|
|
|
2 |
|
|
|
|
|
c20k |
= dk1 |
+ c20k +1 , |
k = 0,..., N1 −1. |
|
(7.25) |
|||
Вейвлет-преобразование Лэйзи. Вейвлет-преобразование Лэйзи заключается в простом разбиении входного сигнала на четную и нечетную части. На этапах декомпозиции и реконструкции используются одни и те же формулы:
ck1 |
= c20k , |
k = 0,...,.N1 |
−1, |
(7.26) |
|
dk1 |
= c20k +1 , k = 0,..., N1 −1. |
||||
|
|||||
115
Преобразования, используемые в этих примерах, не подходят для кодирования изображений. Однако на их основе могут быть получены значительно более эффективные преобразования. Они могут рассматриваться как стартовая точка для получения алгоритмов целочисленного обратимого вейвлет-преобразования.
Отметим интересное свойство вышеприведенных преобразований. Оно заключается в том, что если пиксели изображения представляются некоторым числом бит, то такое же число бит может быть использовано в компьютере для представления значений вейвлет-коэффициентов. Данное свойство преобразования получило название свойства сохранения точности.
Целочисленное вычисление вейвлет –преобразования (1,3) . Это нелинейное преобразование является разновидностью преобразования, исполь-
зующего биортогональную пару фильтров: hn = {1,0,0}, |
gn = {1/ 4,−1/ 2,1/ 4}. Вычис- |
~ |
~ |
ления начинаются с вейвлета Лэйзи (7.26) с последующим изменением высокочастотных коэффициентов:
|
1 |
|
1 |
1 |
|
|
1,0 |
|
|
|
|
|
||
|
|
ck + ck +1 |
|
|
|
|
|
|||||||
dk |
= int |
|
|
|
− dk |
, |
k = 0,..., N1 |
− 2, |
(7.27) |
|||||
|
2 |
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
1 |
|
1 |
|
1,0 |
|
|
|
|
|
|
|
||
d N1 −1 = cN1 −1 |
− d N1 −1 . |
|
|
|
|
|
|
|
||||||
Реконструкция выполняется следующим образом: |
|
|
|
|||||||||||
|
c20k = ck1 , k = 0,..., N1 −1 , |
|
|
|
(7.28) |
|||||||||
|
|
0 |
|
|
0 |
0 |
+2 |
|
|
1 |
|
|
|
|
|
|
|
|
c2k |
+ c2k |
|
|
|
|
|
||||
|
c2k +1 |
|
|
|
|
|
− dk , k = 0,..., N1 |
− 2, |
|
|||||
|
= int |
|
2 |
|
|
(7.29) |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
0 |
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
cN −1 |
= cN −2 |
− d N1 −1 . |
|
|
|
|
|
|
|
||||
Целочисленное |
вычисление |
|
вейвлет-преобразования (2,6). Данное |
|||||||||||
преобразование эквивалентно использованию следующих фильтров анализа: |
||
~ |
2,1/ 2,0,0}, |
~ |
hn = {0,0,1/ |
gn = {−1/16,−1/16,1/ 2,−1/ 2,1/16,1/16} |
|
Декомпозиция выполняется аналогично преобразованию Хаара с добавлением еще одного шага. Вначале производятся вычисления по формулам (7.21)-(7.23). Вместо d01 в данных формулах теперь используется обозначение
d01,0 . Затем производится изменение высокочастотных коэффициентов по формулам:
|
1 |
|
1 |
1 |
|
|
|
1,0 |
|
|
c0 |
− c1 |
|
|
|
, |
|||
d0 |
= int |
|
4 |
|
− d0 |
||||
|
|
|
|
|
|
|
|
(7.30) |
|
|
|
ck1 |
−1 − ck1 |
|
|
|
|||
1 |
+1 |
|
1,0 |
||||||
dk |
|
|
|
|
|
|
− dk , k =1,..., N1 − 2, |
||
|
|
|
|
||||||
= int |
|
4 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|